34 Chapter 34 Multiplicity Lists for the Eigenvalues of Symmetric Matrices with a Given Graph

34
Multiplicity Lists for
the Eigenvalues of
Symmetric Matrices
with a Given Graph
Charles R. Johnson
College of William and Mary
António Leal Duarte
Universidade de Coimbra
Carlos M. Saiago
Universidade Nova de Lisboa
Multiplicities and Parter Vertices. . . . . . . . . . . . . . . . . . . . . 34-2
Maximum Multiplicity and Minimum Rank . . . . . . . . . 34-4
The Minimum Number of Distinct Eigenvalues . . . . . . 34-7
The Number of Eigenvalues Having Multiplicity 1 . . . . 34-7
Existence/Construction of Trees with Given
Multiplicities. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34-8
34.6 Generalized Stars. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34-10
34.7 Double Generalized Stars . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34-11
34.8 Vines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34-15
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34-15
34.1
34.2
34.3
34.4
34.5
This chapter assumes basic terminology from graph theory in Chapter 28; a good general graph theory
reference is [CL96]. For standard terms or concepts from matrix analysis, see Part 1: Basic Linear Algebra,
particularly Chapter 4.3, and Chapter 8; a good general matrix reference is [HJ85]. As we will be interested
in properties of A that are permutation similarity invariant, primarily eigenvalues and their multiplicities,
we will generally view a graph as unlabeled, except when referencing by labels is convenient.
For a given simple graph G on n vertices, let S(G ) (respectively, H(G )) denote the set of all n×n real
symmetric (respectively, complex Hermitian) n×n matrices A = [ai j ] such that for i = j , ai j = 0 if and
only if there is an edge between i and j .
Our primary interest lies in the following very general question. Given G , what are all the possible lists
of multiplicities for the eigenvalues that occur among matrices in S(G ) (respectively, H(G ))? Much of
our focus here is on the case in which G = T is a tree.
It is important to distinguish two possible interpretations of “multiplicity list.” Since the eigenvalues
of a real symmetric or complex Hermitian matrix are real numbers, they may be placed in numerical
order. If the multiplicities are placed in an order corresponding to the numerical order of the underlying
eigenvalues, then we refer to such a way of listing the multiplicities as ordered multiplicities. If, alternatively,
the multiplicities are simply listed in nonincreasing order of the values of the multiplicities themselves, we
refer to such a list as unordered multiplicities. For example, if A has eigenvalues −3, 0, 0, 1, 2, 2, 2, 5, 7, the
list of ordered multiplicities is (1, 2, 1, 3, 1, 1), while the list of unordered multiplicities is (3, 2, 1, 1, 1, 1). In
either case, such a list means that there are exactly 6 different eigenvalues, of which 4 have multiplicity 1.
34-1
34-2
Handbook of Linear Algebra
If a graph G is not connected, then the multiplicity lists for G may be deduced from those of its components via superposition. Also, graphs with many edges admit particularly rich collections of multiplicity
lists. For example, the complete graph admits all multiplicity lists with the given number of eigenvalues,
except the list in which all eigenvalues are the same. For these reasons, a natural beginning for the study
of multiplicity lists for S(G ) or H(G ) is the case in which G = T , a tree. In addition, trees present several
attractive features for this problem, so much of the research in this area, and this chapter, focuses on trees.
34.1
Multiplicities and Parter Vertices
Definitions:
Let G be a simple graph.
For an n×n real symmetric or complex Hermitian matrix A = [ai j ], the graph of A, denoted by G (A),
is the simple graph on n vertices, labeled 1, 2, . . . , n, with an edge between i and j if and only if ai j = 0.
Let S(G ) (respectively, H(G )), denote the set of all n×n real symmetric (respectively, complex Hermitian) matrices A such that G (A) = G (where G has n vertices). No restriction is placed upon the diagonal
entries of A by G , except that they are real.
If G is the subgraph of G induced by β, A(G ) can be used to denote A(β) and A[G ] to denote A[β].
Given a tree T , the components of T \ { j } are called branches of T at j .
If A ∈ H(G ), λ ∈ σ (A), and j is an index such that α A( j ) (λ) = α A (λ) + 1, then j is called a Parter
index or Parter vertex (for λ, A and G ) (where α A (λ) denotes the multiplicity of λ). Some authors refer
to such a vertex as a Parter–Wiener vertex or a Wiener vertex.
If j is a Parter vertex for an eigenvalue λ of an A ∈ H(G ) such that λ occurs as an eigenvalue of at least
three direct summands of A( j ), j is called a strong Parter vertex.
A downer vertex i in a graph G (for λ ∈ σ (A) and A ∈ H(G )) is a vertex i such that α A(i ) (λ) =
α A (λ) − 1.
A downer branch of a tree T at j is a branch Ti at j , determined by a neighbor i of j such that i is a
downer vertex in Ti (for λ and A[Ti ]).
If a branch of a tree at a vertex j is a path and the neighbor of j in this branch is a pendant vertex of
this path, the branch is a pendant path at j .
Facts:
1. If A ∈ H(G ), then trivially A(i ) ∈ H(G \ {i }).
2. [HJ85] (Interlacing Inequalities) If an n×n Hermitian matrix A has eigenvalues λ1 ≤ λ2 ≤ · · · ≤ λn
and A(i ) has eigenvalues βi,1 ≤ βi,2 ≤ · · · ≤ βi,n−1 , then λ1 ≤ βi,1 ≤ λ2 ≤ βi,2 ≤ · · · ≤ βi,n−1
≤ λn , i = 1, . . . , n.
3. If λ is an eigenvalue of an Hermitian matrix A, then α A (λ) − 1 ≤ α A(i ) (λ) ≤ α A (λ) + 1 for
i = 1, . . . , n.
4. If T is a tree, then any matrix of H(T ) is diagonally unitarily similar to one in S(T ).
5. [JLS03a](Parter–Wiener Theorem: Generalization) Let T be a tree and A ∈ S(T ). Suppose that
there exists an index i and a real number λ such that λ ∈ σ (A) ∩ σ (A(i )). Then
r There is in T a Parter vertex j for λ.
r If α (λ) ≥ 2, then j may be chosen so that δ ( j ) ≥ 3 and so that there are at least three
A
T
components T1 , T2 , and T3 of T \ { j } such that α A[Tk ] (λ) ≥ 1, k = 1, 2, 3.
r If α (λ) = 1, then j may be chosen so that there are two components T and T of T \{ j } such
A
1
2
that α A[Tk ] (λ) = 1, k = 1, 2.
6. [JLS03a] For A ∈ S(T ), T a tree, j is a Parter vertex for λ if and only if there is a downer branch
at j for λ.
Multiplicity Lists for the Eigenvalues of Symmetric Matrices with a Given Graph
34-3
7. [JL] Suppose that G is a simple graph on n vertices that is not a tree. Then
r There is a matrix A ∈ S(G ) with an eigenvalue λ such that there is an index j so that α (λ) =
A
α A( j ) (λ) = 1 and α A(i ) (λ) ≤ 1 for every i = 1, . . . , n.
r There is a matrix B ∈ S(G ) with an eigenvalue λ such that α (λ) ≥ 2 and α
B
B(i ) (λ) = α B (λ) − 1,
for every i = 1, . . . , n.
8. [JLSSW03] Let T be a tree and λ1 < λ2 be eigenvalues of A ∈ S(T ) that share a Parter vertex in T .
Then there is at least one λ ∈ σ (A) such that λ1 < λ < λ2 .
9. Let T be a tree and A ∈ S(T ). If T is a pendant path of a vertex j of T , then T is a downer branch
for each eigenvalue of the direct summand A[T ].
10. Let T be a path and A ∈ S(T ). Then each eigenvalue of A has multiplicity 1.
11. Let A be an n×n irreducible real symmetric tridiagonal matrix. Then
r A has distinct eigenvalues.
r In A(i ), there are at most min{i − 1, n − i } interlacing equalities and this number may occur.
r For each interlacing equality that does occur, the relevant eigenvalues must be an eigenvalue (of
multiplicity 1) of both irreducible principal submatrices of A(i ).
See Example 3 below.
Examples:
1. In general, one might expect that in passing from A to A(i ), multiplicities typically decline. However,
Fact 5 is counter to this intuition in the case for trees. A rather complete statement has evolved
through a series of papers ([Par60], [Wie84], [JLS03a]). In particular, Fact 5 says that when T is
a tree and α A (λ) ≥ 2, there must be a strong Parter vertex because, by interlacing, the hypothesis
λ ∈ σ (A) ∩ σ (A(i )) must be satisfied for any i . However, i itself need not be a Parter vertex. Even
when α A (λ) ≥ 2, it can happen that α A( j ) (λ) = α A (λ) + 1 with δT ( j ) = 1 or δT ( j ) = 2 or λ
appears in only one or two components of T \ { j }, even if δT ( j ) ≥ 3. There may, as well, be several
Parter vertices and even several strong Parter vertices. Much information about Parter vertices may
be found in [JLSSW03] and [JLS03a]. Let λ, µ ∈ R, λ = µ, and consider real symmetric matrices
whose graphs are the following trees, assuming that every diagonal entry corresponds to the label
of the corresponding vertex.
r The vertex v is a Parter vertex for λ in real symmetric matrices for which the graph is each of
the trees in Figure 34.1. We also note that, depending on the tree T , several different vertices
of T could be Parter for an eigenvalue of the same matrix in S(T ). The matrices A[T1 ] and
A[T2 ] each have u and v as Parter vertices for λ.
T1
T2
λ
λ
u
λ
T3
v
λ
λ
u
v
λ
v
λ
λ
λ
λ
λ
δT 1 (v ) = 1
αA [T 1 ] (λ) = 2
δT 2 (v ) = 2
αA [T 2 ] (λ) = 2
δT 3 (v ) = 3
αA [T 3 ] (λ) = 2
αA [T 1 − v ] (λ) = 3
αA [T 2 − v ] (λ) = 3
αA [T 3 − v ] (λ) = 3
FIGURE 34.1 Examples of Parter vertices.
34-4
Handbook of Linear Algebra
r Also, depending on the tree T , the same vertex could be
a Parter vertex for different eigenvalues of a matrix in
S(T ). The vertex v is a Parter vertex for λ and µ in a real
symmetric matrix A for which the graph is the tree in
Figure 34.2. Such a matrix A has λ and µ as eigenvalues
with α A (λ) = 2 = α A (µ). Since it is clear that we have FIGURE 34.2 Vertex v is a Parter
α A(v) (λ) = 3 = α A(v) (µ), it means that v is Parter for λ vertex for λ and µ.
and µ.
2. Though a notion of “Parter vertex” can be defined for nontrees, Fact 7 is the converse to Fact 5 that
.
shows that its remarkable conclusions are generally valid only for trees.
Consider the matrix J 3 whose graph is the cycle C 3 (the possible multiplicities for the eigenvalues
of a matrix whose graph is a cycle was studied in [Fer80]), which is not a tree. The matrix J 3 has
eigenvalues 0, 0, 3. Since the removal of any vertex from C 3 leaves a path, we conclude that there is
no Parter vertex for the multiple eigenvalue 0.
3. If a graph G is a path on n vertices, then G is a tree and if the vertices are labeled consecutively,
any matrix in S(G ) is an irreducible tridiagonal matrix. Conversely, the graph of an irreducible
real symmetric tridiagonal matrix is a path. The very special spectral structure of such matrices has
been of interest for some time for a variety of reasons. Two well-known classical facts are that all
eigenvalues are distinct (i.e., all 1s is the only multiplicity list) and, if a pendant vertex is deleted,
the interlacing inequalities are strict. Both statements follow from Fact 5, but more can be gotten
from Fact 5 as well. If A is n × n real symmetric and 1 ≤ i ≤ n, then as many as n − 1 of the
eigenvalues of A(i ) might coincide with some eigenvalue of A. We refer to such an occurrence as
an “interlacing equality.” If a pendant vertex is removed from a path, no interlacing equalities can
occur, but if an interior vertex is removed, interlacing equalities can occur. The complete picture
in this regard may be also be deduced from Fact 5.
34.2
Maximum Multiplicity and Minimum Rank
Definitions:
Let G be a simple graph.
The maximum multiplicity of G , M(G ), is the maximum multiplicity for a single eigenvalue among
matrices in S(G ).
The minimum rank of G is mr(G ) = min A∈S(G ) rank(A).
The path cover number of G , P (G ), is the minimum number of induced paths of G that do not
intersect, but do cover all vertices of G .
(T ) = max[ p − q ] over all ways in which q vertices may be deleted from G , so as to leave p paths.
Isolated vertices count as (degenerate) paths.
The maximum rank deficiency for G is m(G ) = n − mr (G ), where the order of G is n.
Facts:
Let G be a simple connected graph of order n.
1. If G is a path, P (G ) = 1; otherwise P (G ) > 1.
2. There may be many minimum path covers. See Example 2.
3. Maximizing sets of removed vertices (used in the computation of (G )) are not unique; even the
number of removed vertices is not unique. See Example 3.
Multiplicity Lists for the Eigenvalues of Symmetric Matrices with a Given Graph
34-5
FIGURE 34.3 Two of the forbidden graphs for mr(G ) = 2.
4.
5.
6.
7.
8.
[Fie69] M(G ) = 1 if and only if G is a path.
M(G ) = n − 1 if and only if G is the complete graph K n .
M(G ) = m(G ).
[JL99] For a tree T , M(T ) = (T ) = P (T ) = m(T ).
[JS02] For any tree T , let HT denote the subgraph of T induced by the vertices of degree at least 3.
For a tree T , (T ) can be computed by the following algorithm. See Example 4.
Algorithm 1: Computation of (T )
Given a tree T .
1. Set Q = ∅ and T = T .
2. While HT = ∅:
Remove from T all vertices v of HT such that δT (v) − δ HT (v) ≥ 2
and add these vertices to Q.
3. (T ) = p − |Q| where p is the number of components (all of which are paths) in T \Q.
9. [JL99], [BFH04] (G ) ≤ M(G ) and (G ) ≤ P (G ).
10. [BFH04], [BFH05] If n ≥ 2, P (K n ) < M(K n ), where K n is the complete graph on n vertices. If G
is unicyclic (i.e., has a unique cycle), then P (G ) ≥ M(G ) and strict inequality is possible.
11. [BFH04] Minimum rank (and, thus, maximum multiplicity) of a graph with a cut vertex can be
computed from the minimum ranks of induced subgraphs.
12. [BHL04] If H is an induced subgraph of G , then mr(H) ≤ mr(G ). Furthermore, mr(G ) =2
(i.e., M(G ) = n − 2) if and only if G does not contain as an induced subgraph one of the following
four forbidden graphs: the path on 4 vertices P4 , the complete tripartite graph K 3,3,3 , the two graphs
shown in Figure 34.3. Other characterizations are also given.
Examples:
1. Considering the tree T in Figure 34.4, we have P (T ) = 2
1
5
(e.g., 1-3-2 and 5-4-6 constitute a minimal path cover of the
4
3
vertices) and, of course, (T ) = 2, as removal of vertex 4
leaves the 3 paths 1-3-2, 5, and 6 (and neither can be improved
2
6
upon). Note that if submatrices A[{1, 2, 3}], A[{5}], and A[{6}]
of A ∈ S(T ) are constructed so that λ is an eigenvalue of each
(this is always possible and no higher multiplicity in any of them FIGURE 34.4 A tree with path cover
is possible), then α A (λ) ≥ 3 − 1 = 2, which is the maximum number 2.
possible.
2. Consider the tree T on 12 vertices in Figure 34.5. It is not difficult to see that the path cover number
of T , P (T ), is 4. However, it can be achieved by different collections of paths. For example, P (T )
can be achieved from the collection of 4 paths of T , 1-2-3, 4-5-6, 7-8 and 12-9-10-11. Similarly,
34-6
Handbook of Linear Algebra
11
1
3
6
10
2
5
9
4
12
8
7
FIGURE 34.5 A tree with path cover number 4.
the paths of T , 1-2-3, 4-5-8-7, 6 and 12-9-10-11, form a collection of vertex disjoint paths (each
one is an induced subgraph of T ) that cover all the vertices of T .
3. Consider the tree T on 12 vertices in Figure 34.5. As we can see in Table 34.1, (T ) can be achieved
for q = 1, 2, 3. When q = 2, there are 3 different sets of vertices whose removal from T leaves 6
components (paths), i.e., p − q = 4.
4. The algorithm in Fact 8 applied to the tree T in Figure 34.6 gives, in one step, a subset of vertices
of T , Q = {v 2 , v 3 , v 4 , v 5 }, with cardinality 4 and such that T \Q has 13 components, each of which
is a path. Therefore, (T ) = 13 − 4 = 9.
Note that, in any stage of the process to determine (T ), we may not choose just any vertex with
degree greater than or equal to 3.
TABLE 34.1
(T ) for the tree T in Figure 34.5
Removed Vertices from T
5
5, 2
5, 9
5, 10
2, 5, 9
2, 5, 10
q
1
2
2
2
3
3
p − q (= (T ))
4
4
4
4
4
4
p
5
6
6
6
7
7
v5
v4
v1
v2
v3
FIGURE 34.6 A tree T with (T ) = 9.
Multiplicity Lists for the Eigenvalues of Symmetric Matrices with a Given Graph
34-7
FIGURE 34.7 A tree of diameter 6 for which the minimum number of distinct eigenvalues is 8 > 6 + 1.
34.3
The Minimum Number of Distinct Eigenvalues
Definitions:
Let T be a tree.
The diameter of T , d(T ), is the maximum number of edges in a path occurring as an induced subgraph
of T .
The minimum number of distinct eigenvalues of T , N (T ), is the minimum, among A ∈ S(T ),
number of distinct eigenvalues of A.
Facts:
1. [JL02a] Let T be a tree. Then N (T ) ≥ d(T ) + 1.
2. [JSa2] If T is a tree such that d(T ) < 5, then there exist matrices in S(T ) attaining as few distinct
eigenvalues as d(T ) + 1.
Examples:
1. Since each entry in a multiplicity list represents a distinct eigenvalue, the “length” of a list represents
the number of different eigenvalues. This number can be as large as n (the number of vertices), of
course, but it cannot be too small. Restrictions upon length limit the possible multiplicity lists. Just
as a path has many distinct eigenvalues, a long (chordless) path occurring as an induced subgraph
of a tree forces a large number of distinct eigenvalues.
2. For many trees T , there exist matrices in S(T ) attaining as few distinct eigenvalues as d(T ) + 1.
However, for the tree T in Figure 34.7, d(T ) = 6 and, in [BF04], the authors have shown that
N (T ) = 8 > d(T )+1. It is not known how to deduce the minimum number of distinct eigenvalues
from the structure of the tree, in general.
34.4
The Number of Eigenvalues Having Multiplicity 1
Definitions:
Given a tree T , let U(T ) be the minimum number of 1s among multiplicity lists occurring for T .
Facts:
1. [JLS03a] For any tree T , the largest and smallest eigenvalues of any A ∈ S(T ) necessarily have
multiplicity 1.
2. [JLS03a] For any tree T on n ≥ 2 vertices, U(T ) ≥ 2 and, for each n, there exist trees T for which
U(T ) = 2.
3. Let T be a tree on n vertices. U(T ) ≥ 2N (T ) − n. In particular, U(T ) ≥ 2(d(T ) + 1) − n.
34-8
Handbook of Linear Algebra
Examples:
1. As with the length of lists, it is relatively easy to have many
1s in a multiplicity list. The more interesting issue is how few of
1s may occur among lists for a given tree T . It certainly depends
. . . ..
upon the tree, as the star (see Figure 34.8) may have just two 1s,
while a path (see Figure 34.9) always has as many as the number
FIGURE 34.8 A star.
of vertices.
2. If T has a diameter that is large relative to its number of vertices (a path is an extremal example),
then it may have to have a minimum number of distinct eigenvalues, which forces U(T ) to be much
greater than 2. However, U(T ) may be greater than 2 for other reasons. For example, for the tree T
in Figure 34.10, d(T ) = 4, n = 8, but U(T ) = 3. It is not known how U(T ) is determined by T ,
and it appears to be quite subtle.
34.5
Existence/Construction of Trees with Given Multiplicities
Definitions:
For a given graph G , the collection of all multiplicity lists is denoted by L(G ). If it is not clear from the
context, we will distinguish the unordered lists as Lu (G ) from the ordered lists Lo (G ).
General Inverse Eigenvalue Problem (GIEP) for S(T ): Given a vertex v of a tree T , what are all the
sequences of real numbers that may occur as eigenvalues of A and A(v), as A runs over S(T )?
Inverse Eigenvalue Problem (IEP) for S(T ): What are all possible spectra that occur among matrices
in S(T ), T being a tree?
A tree T has equivalence of the ordered multiplicity lists and the IEP if a spectrum occurs for some
matrix in S(T ) whenever it is consistent with some list of ordered multiplicities of Lo (T ).
Facts:
1. [Lea89] Let T be a tree on n vertices and v be a vertex of T . Let λ1 , λ2 , . . . , λn and µ1 , µ2 , . . . , µn−1
be real numbers. If
λ1 < µ1 < λ2 < · · · < µn−1 < λn ,
then there exists a matrix A in S(T ) with eigenvalues λ1 , λ2 , . . . , λn , and such that, A(v) has
eigenvalues µ1 , µ2 , . . . , µn−1 .
2. For any tree T on n vertices and any given sequence of n distinct real numbers, there exists a matrix
. . .
FIGURE 34.9 A path.
FIGURE 34.10 A tree T on 8 vertices with d(T ) = 4 and U(T ) = 3.
Multiplicity Lists for the Eigenvalues of Symmetric Matrices with a Given Graph
5
7
4
2
34-9
8
3
6
1
9
10
FIGURE 34.11 A tree for which there is not equivalence between ordered multiplicity lists and the IEP.
in S(T ) having these numbers as eigenvalues.
3. Any path has equivalence of the ordered multiplicity lists and the IEP.
4. [BF04] There exists a tree for which the equivalence of the ordered multiplicity lists and the IEP is
not verified. (See Example 1.)
Examples:
1. For remarkably many small trees and many of the families of trees to be discussed in the next
section, the ordered multiplicity lists are equivalent to the IEP. This is not always the case. Extremal
multiplicity lists for large numbers of vertices can force numerical relations upon the eigenvalues,
as in the tree T shown in Figure 34.11.
Let A be the adjacency matrix of T (i.e., the 0,1-matrix in S(T ) with all diagonal entries 0). The
Parter–Wiener Theorem (Fact 5 Section 34.1) guarantees that αA (0) = 4, and likewise guarantees two eigenvalues of multiplicity 2 (the nonzero eigenvalues of A[{2, 3, 4}] = A[{5, 6, 7}] =
A[{8, 9, 10}], so √
the ordered
list
A is√
(1, 2, 4, 2, 1). In fact, direct computation shows
√ multiplicity
√
√of √
that σ (A) = (− 5, − 2, − 2, 0, 0, 0, 0, 2, 2, 5).
However, it is not possible to prescribe arbitrary real numbers as the eigenvalues with this ordered
multiplicity list. If A = [ai j ] ∈ S(T ) has eigenvalues λ1 < λ2 < λ3 < λ4 < λ5 with multiplicities
1, 2, 4, 2, 1, respectively, then λ1 +λ5 = λ2 +λ4 . The method used to establish this restriction comes
from [BF04]. By the Parter–Wiener Theorem and an examination of subsets of vertices, a11 = λ3 .
The restriction then follows from comparison of the traces of A and A(1).
It is not known for which trees the determination of all possible ordered multiplicity lists is equivalent to the solution of the IEP. Even when the two are not equivalent for some ordered list, they
may be for all other ordered lists.
2. In the construction of multiplicity lists for a tree, it is often useful (and, perhaps necessary) to know
the solution of the GIEP (or some weak form of it) for some of the subtrees of the tree.
It is often more difficult (than giving necessary restrictions) to construct matrices A ∈ S(T ) with
a given, especially extremal, multiplicity list, even when that list does occur. There are three basic
approaches besides ad hoc methods and computer assisted solution of equations. They are
(a) Manipulation of polynomials, viewing the nonzero entries as variables and targeting a desired
characteristic polynomial (see [Lea89] for an initial reference; this method, based on some nice
formulas for the characteristic polynomial in the case of a tree (see, e.g., [Par60], [MOD89]),
can be quite tedious for larger, more complicated trees).
(b) Careful use of the implicit function theorem (initiated in [JSW]).
(c) Division of the tree into understood parts and using the interlacing inequalities to give lower
bounds that are forced to be attained by known constraints (this is along the lines of the
brief discussion in Example 1 Section 34.2 involving (T ), but for larger trees can lead to
complicated simultaneity conditions).
As an example of method (c) and its subtleties (see also Example 2 Section 34.7), consider again
the tree T in Figure 34.4. Since P (T ) = 2, the maximum multiplicity is 2, and because d(T ) = 3,
there must be at least four distinct eigenvalues, two of which have multiplicity 1. This leaves the
34-10
Handbook of Linear Algebra
question of whether the list (2, 2, 1, 1) (which would have to be the ordered list (1, 2, 2, 1)) can
occur. It can, but this is the nontrivial example with smallest number of vertices. Suppose that the
two multiple eigenvalues are λ and µ. We want A ∈ S(T ) with α A (λ) = 2 and α A (µ) = 2. Each
must have a Parter vertex, which must be either vertex 3 or 4. One must be for λ (and not µ) and
the other for µ (and not λ), as two consecutive eigenvalues cannot share a Parter vertex (Fact 8
section 34.1). So assume that 3 is Parter for λ and 4 for µ. Then, we must have A[{1}] = λ = A[{2}]
and λ ∈ σ (A[{4, 5, 6}]); and A[{5}] = µ = A[{6}] and µ ∈ σ (A[{1, 2, 3}]). A calculation
(or other methods) shows this can be achieved simultaneously.
34.6
Generalized Stars
Definitions:
A tree T in which there is at most one vertex of degree greater than two is a generalized star.
In a generalized star, a vertex v is a central vertex if its neighbors are pendant vertices of their branches,
and each branch is a path. (Note that, under this definition, a path is a (degenerate) generalized star, in
which any vertex is a central vertex. When referring to a path as a generalized star, one vertex has been
fixed as the central vertex.)
For a central vertex v of a generalized star T , each branch of T at v is called an arm of T ; the lengths
of an arm are the number of vertices in the arm.
Supposing that v is a central vertex of a generalized star T , with δT (v) = k. Denote by T1 , . . . , Tk its
arms and by l 1 , . . . , l k the lengths of T1 , . . . , Tk , respectively.
A star on n vertices is a tree in which there is a vertex of degree n − 1.
Let u = (u1 , . . . , ub ), u1 ≥ · · · ≥ ub , and v = (v 1 , . . . , v c ), v 1 ≥ · · · ≥ v c , be two nonincreasing
partitions of integers M and N, respectively. If M < N, denote by ue the partition of N obtained from u
appending 1s to the partition u. Note that if M = N, then ue = u.
Facts:
1. A star is trivially a generalized star.
2. If u and v are two nonincreasing partitions of integers M and N, respectively, M ≤ N, such that
u1 + · · · + us ≤ v 1 + · · · + v s for all s (interpreting us or v s as 0 when s exceeds b or c , respectively),
then trivially v majorizes ue , denoted ue v. See Preliminaries.
3. [JLS03b] Let T be a generalized star on n vertices with central vertex v of degree k, l 1 , . . . , l k be
the lengths of the arms T1 , . . . , Tk , and f (x), g 1 (x), . . . , g k (x) be monic polynomials with all their
roots real in which deg f = n, deg g 1 = l 1 , . . . , deg g k = l k . There exists A ∈ S(T ) such that A
has characteristic polynomial f (x) and A[Ti ] has characteristic polynomial g i (x) if and only if
r Each g (x) has only simple roots.
i
r If λ is a root of g (x) · · · g (x) of multiplicity m ≥ 1, then λ is a root of f (x) of multiplicity
1
k
m − 1.
r The roots of f (x) that are not roots of g (x) · · · g (x) are simple and strictly interlace the set of
1
k
roots of g 1 (x) · · · g k (x) (multiple roots counting only once).
4. [JL02b] Let T be a generalized star on n vertices with central vertex of degree s and arm lengths
l 1 ≥ · · · ≥ l s . Then ( p1 , . . . , pr ) ∈ Lu (T ) if and only if
r r
i =1
pi = n.
r r ≥ l + l + 1.
1
2
r +1
r p = p
h
h + 1 = · · · = pr = 1, in which h = 2 .
r (p , p , . . . , p
∗
∗
1
2
r −l 1 −1 ) (l 1 − 1, . . . , l l 1 − 1).
34-11
Multiplicity Lists for the Eigenvalues of Symmetric Matrices with a Given Graph
T1
T2
v1
T3
v2
v3
FIGURE 34.12 T1 , T2 , and T3 are generalized stars on 9 vertices with central vertices v 1 , v 2 , and v 3 , respectively.
5. [JLS03b] Let T be a generalized star on n vertices with central vertex of degree s and arm lengths
l 1 ≥ · · · ≥ l s . Let λ1 < · · · < λr be any sequence of real numbers. Then there exists a matrix A ∈
S(T ) with distinct eigenvalues λ1 < · · · < λr and list of ordered multiplicities q = (q 1 , . . . , qr ) if
and only if q satisfies the following conditions:
r r
i =1
q i = n.
r If q > 1, then 1 < i < r and q
i
i − 1 = 1 = qi + 1 .
r (q + 1, . . . , q + 1) (l , . . . , l )∗ , in which q ≥ · · · ≥ q are the entries of the r -tuple
i1
ih
e
1
s
i1
ih
(q 1 , . . . , qr ) greater than 1.
(That is, when T is a generalized star, there is equivalence of the ordered multiplicity lists and the IEP.)
Examples:
1. Let T1 , T2 , and T3 be the generalized stars in Figure 34.12. We have
Lu (T1 ) = {(1, 1, 1, 1, 1, 1, 1, 1, 1), (2, 1, 1, 1, 1, 1, 1, 1)},
Lu (T2 ) = {(1, 1, 1, 1, 1, 1, 1, 1, 1), (2, 1, 1, 1, 1, 1, 1, 1), (2, 2, 1, 1, 1, 1, 1),
(3, 1, 1, 1, 1, 1, 1), (3, 2, 1, 1, 1, 1), (3, 3, 1, 1, 1), (4, 1, 1, 1, 1, 1),
(4, 2, 1, 1, 1)},
and
Lu (T3 ) = {(1, 1, 1, 1, 1, 1, 1, 1, 1), (2, 1, 1, 1, 1, 1, 1, 1), (2, 2, 1, 1, 1, 1, 1),
(3, 1, 1, 1, 1, 1, 1), (3, 2, 1, 1, 1, 1), (3, 3, 1, 1, 1), (4, 1, 1, 1, 1, 1),
(4, 2, 1, 1, 1), (5, 1, 1, 1, 1), (6, 1, 1, 1), (7, 1, 1)}.
34.7
Double Generalized Stars
Definitions:
A double generalized star is a tree resulting from joining the central vertices of two generalized stars
T1 and T2 by an edge. Such a tree will be denoted by D(T1 , T2 ).
A double star is a double generalized star D(T1 , T2 ) in which T1 and T2 are stars.
34-12
Handbook of Linear Algebra
i1
j1
i2
j2
ik
. . .
. . .
. . .
. . .
jl
i p−1
ip
j q−1
jq
FIGURE 34.13 A double path.
A double path is a double generalized star D(T1 , T2 ) in which T1 and T2 are paths. When we refer to
a double path T on n = p + q vertices we suppose T is represented as in Figure 34.13, in which the
only constraint on the connecting edge {i k , jl } is that not both k ∈ {1, p} and l ∈ {1, q }. The upper (i )
path has k − 1 vertices to the left of the connecting vertex and another p − k vertices to the right; set
s 1 = min{k − 1, p − k}, s 2 = min{l − 1, q − l }, and s = min{q , p, s 1 + s 2 }.
Let G be a tree. Let v be a vertex of G of degree k and G 1 , . . . , G k be the components of G \ {v} having
order l 1 , . . . , l k , respectively. To the tree G is associated the generalized star, Sv (G ), with central vertex
v of degree k, and with arms T1 , . . . , Tk of lengths l 1 , . . . , l k , respectively.
Let u1 and u2 be adjacent vertices of a tree G . Denote by G u1 the connected component of G \{u2 } that
contains u1 and by G u2 the connected component of G \{u1 } that contains u2 . Put S1 = Su1 (G u1 ) and
S2 = Su2 (G u2 ). Now, to the tree G is associated the double generalized star D(S1 , S2 ), which is denoted
by Du1 ,u2 (G ).
Given a vertex v of a tree T and an eigenvalue λ of a matrix A ∈ S(T ), λ is an upward eigenvalue of A
at v if α A(v) (λ) = α A (λ) + 1, and α A (λ) is an upward multiplicity of A at v.
If q = q (A) = (q 1 , . . . , qr ) is the list of ordered multiplicities of A, define the list of upward multiplicities of A at v, denoted by q̂ , as the list with the same entries as q but in which any upward multiplicity
q i of A at v is marked as q̂ i in q̂ .
Given a generalized star T with central vertex v, we denote by L̂o (T ) the set of all lists of upward
multiplicities at v occurring among matrices in S(T ).
Facts:
1. A double path is a tree whose path cover number is 2.
2. [JLS03b] Let T be a generalized star on n vertices with central vertex v of degree k and arm lengths
l 1 ≥ · · · ≥ l k . Let λ1 < · · · < λr be any sequence of real numbers. Then there exists a matrix A in
S(T ) with distinct eigenvalues λ1 < · · · < λr and a list of upward multiplicities q̂ = (q 1 ,
. . . , qr )
if and only if q̂ satisfies the following conditions:
r r
i =1
q i = n.
r If q is an upward multiplicity in q̂ , then 1 < i < r and neither q
i
i −1 nor q i −1 is an upward
multiplicity in q̂ .
r (q + 1, . . . , q + 1) (l , . . . , l )∗ , in which q ≥ · · · ≥ q are the upward multiplicities
i1
ih
e
1
k
i1
ih
of q̂ .
. . . , bs 1 ) ∈
3. [JLS03b] (Superposition Principle) Let D(T1 , T2 ) be a double generalized star, b̂ = (b1 ,
. . . , c s 2 ) ∈ L̂o (T2 ). Construct any b + = (b1+ , . . . , bs+1 +t1 ) and c + = (c 1+ , . . . , c s+2 +t2 )
L̂o (T1 ), and ĉ = (c 1 ,
subject to the following conditions:
r t , t ∈ N and s + t = s + t .
1 2
0
1
1
2
2
r b + (respectively, c + ) is obtained from b̂ (respectively, ĉ ) by inserting t (respectively, t ) 0s.
1
2
r b + and c + cannot both be 0.
i
i
r If b + > 0 and c + > 0, then at least one of the b + or c + must be an upward multiplicity of b̂ or ĉ .
i
i
i
i
Multiplicity Lists for the Eigenvalues of Symmetric Matrices with a Given Graph
34-13
Then b + + c + ∈ Lo (D(T1 , T2 )). Moreover, a ∈ Lo (D(T1 , T2 )) if and only if there are b̂ ∈ L̂o (T1 ),
ĉ ∈ L̂o (T2 ) such that a = b + + c + .
4. Let T be a tree, v be a vertex of T , and v 1 , v 2 be adjacent vertices of T . Then
r L (S (T )) ⊆ L (T ), L (S (T )) ⊆ L (T ).
u v
u
o v
o
r L (D
u
v 1 ,v 2 (T )) ⊆ Lu (T ), Lo (Dv 1 ,v 2 (T )) ⊆ Lo (T ).
5. [JL02b] Let T be a double path on n = p + q vertices and suppose that A ∈ S(T ). Then
r The maximum multiplicity of an eigenvalue of A is 2.
r The diameter of G is max{ p, q , p + q − (s + s )} − 1, so that A has at least max{ p, q , p + q −
1
2
(s 1 + s 2 )} distinct eigenvalues.
r A has at most s multiplicity 2 eigenvalues.
r The possible list of unordered multiplicities for T , L (T ), consists of all partitions of p + q into
u
parts each one not greater than two and with at most s equal to 2.
r Any list in L (T ) has at least n − 2s 1s.
u
Examples:
1. Let T1 and T2 be the stars in Figure 34.14 with central vertices v 1 and v 2 , respectively, and G be the
double star D(T1 , T2 ). By Fact 2, we have that
L̂o (T1 ) = {(1, 2̂, 1), (1, 1̂, 1, 1), (1, 1, 1̂, 1), (1, 1, 1, 1)}
and
L̂o (T2 ) = {(1, 1̂, 1), (1, 1, 1)}.
Applying the Superposition Principle (Fact 3) to the lists of upward multiplicities of T1 and T2 , it
follows that
Lo (G ) = {(1, 3, 2, 1), (1, 2, 3, 1), (1, 3, 1, 1, 1), (1, 1, 3, 1, 1), (1, 1, 1, 3, 1),
(1, 2, 2, 1, 1), (1, 2, 1, 2, 1), (1, 1, 2, 2, 1), (1, 2, 1, 1, 1, 1),
(1, 1, 2, 1, 1, 1), (1, 1, 1, 2, 1, 1), (1, 1, 1, 1, 2, 1), (1, 1, 1, 1, 1, 1, 1)}.
For example, (1, 3, 2, 1) ∈ Lo (G ) because b̂ = (1, 2̂, 1) ∈ L̂o (T1 ), ĉ = (1, 1̂, 1) ∈ L̂o (T2 ), and
(1, 3, 2, 1) = b + + c + = (1, 2̂, 1, 0) + (0, 1, 1̂, 1).
T1
T2
v1
v2
D (T1 , T2 )
v1
FIGURE 34.14 Stars and a double star.
v2
34-14
Handbook of Linear Algebra
i1
i2
i3
i4
i5
j1
j2
j3
j4
j5
i6
FIGURE 34.15 A double path on 11 vertices.
2. Consider the double path T on 11 vertices in Figure 34.15. Let T1 be the path with vertices
i 1 , . . . , i 6 and T2 be the path with vertices j1 , . . . , j5 (subgraphs of T induced by the mentioned
vertices). Because T1 and T2 are generalized stars with central vertices i 3 and j3 , respectively, from
Fact 2 we conclude that b̂ = (1, 1̂, 1, 1̂, 1, 1) ∈ L̂o (T1 ) and ĉ = (1, 1̂, 1, 1̂, 1) ∈ L̂o (T2 ). Since, for
example,
(1, 2, 2, 2, 2, 1, 1) = b + + c + = (0, 1, 1̂, 1, 1̂, 1, 1) + (1, 1̂, 1, 1̂, 1, 0, 0),
by the Superposition Principle, we conclude that (1, 2, 2, 2, 2, 1, 1) ∈ Lo (T ) and, therefore,
(2, 2, 2, 2, 1, 1, 1) ∈ Lu (T ). We may construct a matrix A ∈ S(T ) with list of multiplicities
(2, 2, 2, 2, 1, 1, 1) in the following way.
Pick real numbers λ1 > µ1 > λ2 > µ2 > λ3 > µ3 > λ4 . Construct A1 with graph T1
such that A1 has eigenvalues λ1 , µ1 , λ2 , µ2 , λ3 , λ4 and such that the eigenvalues of A1 [{i 1 , i 2 }] and
A1 [{i 4 , i 5 , i 6 }] are µ1 , µ2 and µ1 , µ2 , µ3 , respectively; construct A2 with graph T2 such that A2 has
eigenvalues µ1 , λ2 , µ2 , λ3 , µ3 and such that the eigenvalues of both A2 [{ j1 , j2 }] and A2 [{ j4 , j5 }] are
λ2 , λ3 . According to Fact 3 section 34.6, these constructions are possible. Now construct A with
graph T and such that A[T1 ] = A1 and A[T2 ] = A2 . Then i 3 is a strong Parter vertex for µ1 , µ2 ,
while j3 is a strong Parter for λ2 , λ3 and so (2, 2, 2, 2, 1, 1, 1) is the list of unordered multiplicities
of A.
3. Regarding Fact 4, the results for generalized stars or double generalized stars may be extended
to a general tree T by associating with T either a generalized star or a double generalized star
according to the given definitions. (See also [JLS03b, Theorem 10] for a corresponding result for
the GIEP.)
Note that, under our definition, there are many different possibilities to associate either a generalized star or a double generalized star to a given tree T , and so Fact 3 provides many possible lists
for L(T ). The natural question is to ask whether all the elements of L(T ) can be obtained in this
manner. The answer is no. It suffices to note that the path cover number of T will be, in general,
strictly greater than that of either of Sv (T ) or Dv 1 ,v 2 (T ) for any possible choice of v, v 1 , and v 2 . So
any lists for which the maximum multiplicity occurs cannot generally be obtained from the inclusions in Fact 4. For example, the tree T in Figure 34.16 has path cover number 3, which is strictly
greater than the maximum path cover number 2, of any generalized star or double generalized star
associated with T .
FIGURE 34.16 A tree with path cover number 3.
Multiplicity Lists for the Eigenvalues of Symmetric Matrices with a Given Graph
34.8
34-15
Vines
Definitions:
A binary tree is a tree in which no vertex has degree greater than 3.
A vine is a binary tree in which every degree 3 vertex is adjacent to at least one vertex of degree 1 and
no two vertices of degree 3 are adjacent.
Facts:
1. [JSW] Let T be a vine on n vertices. The set Lu (T ) consists of all sequences that are majorized by
the sequence s = (P (T ), 1, . . . , 1) (s being a partition of n).
(The description of Lu (T ) was given by using the implicit function theorem technique referred to
in section 34.5.)
References
[BF04] F. Barioli and S.M. Fallat. On two conjectures regarding an inverse eigenvalue problem for acyclic
symmetric matrices. Elec. J. Lin. Alg. 11:41–50 (2004).
[BFH04] F. Barioli, S. Fallat, and L. Hogben. Computation of minimal rank and path cover number for
graphs. Lin. Alg. Appl. 392: 289–303 (2004).
[BFH05] F. Barioli, S. Fallat, and L. Hogben. On the difference between the maximum multiplicity and
path cover number for tree-like graphs. Lin. Alg. Appl. 409: 13–31 (2005).
[BHL04] W.W. Barrett, H. van der Holst, and R. Loewy. Graphs whose minimal rank is two. Elec. J. Lin.
Alg. 11:258–280 (2004).
[BL05] A. Bento and A. Leal-Duarte. On Fiedler’s characterization of tridiagonal matrices over arbitrary
fields. Lin. Alg. Appl. 401:467–481 (2005).
[BG87] D. Boley and G.H. Golub. A survey of inverse eigenvalue problems. Inv. Prob. 3:595–622 (1987).
[CL96] C. Chartrand and L. Lesniak. Graphs & Digraphs. Chapman & Hall, London, 1996.
[Chu98] M.T. Chu. Inverse eigenvalue problems. SIAM Rev. 40:1–39 (1998).
[CDS95] D. Cvetković, M. Doob, and H. Sachs. Spectra of Graphs. Johann Ambrosius Barth Verlag,
Neidelberg, 1995.
[FP57] K. Fan and G. Pall. Imbedding conditions for Hermitian and normal matrices. Can. J. Math.
9:298–304 (1957).
[Fer80] W. Ferguson. The construction of Jacobi and periodic Jacobi matrices with prescribed spectra.
Math. Comp. 35:1203–1220 (1980).
[Fie69] M. Fiedler. A characterization of tridiagonal matrices. Lin. Alg. Appl. 2:191–197 (1969).
[GM74] J. Genin and J. Maybee. Mechanical vibration trees. J. Math. Anal. Appl. 45:746–763 (1974).
[HJ85] R. Horn and C.R. Johnson. Matrix Analysis. Cambridge University Press, New York, 1985.
[JL99] C.R. Johnson and A. Leal-Duarte. The maximum multiplicity of an eigenvalue in a matrix whose
graph is a tree. Lin. Multilin. Alg. 46:139–144 (1999).
[JL02a] C.R. Johnson and A. Leal-Duarte. On the minimum number of distinct eigenvalues for a symmetric
matrix whose graph is a given tree. Math. Inequal. Appl. 5(2):175–180 (2002)
[JL02b] C.R. Johnson and A. Leal-Duarte. On the possible multiplicities of the eigenvalues of an Hermitian
matrix whose graph is a given tree. Lin. Alg. Appl. 348:7–21 (2002).
[JL] C.R. Johnson and A. Leal-Duarte. Converse to the Parter–Wiener theorem: the case of non-trees.
Discrete Math. (to appear).
[JLSSW03] C.R. Johnson, A. Leal-Duarte, C.M. Saiago, B.D. Sutton, and A.J. Witt. On the relative position
of multiple eigenvalues in the spectrum of an Hermitian matrix with a given graph. Lin. Alg. Appl.
363:147–159 (2003).
34-16
Handbook of Linear Algebra
[JLS03a] C.R. Johnson, A. Leal-Duarte, and C.M. Saiago. The Parter–Wiener theorem: refinement and
generalization. SIAM J. Matrix Anal. Appl. 25(2):352–361 (2003).
[JLS03b] C.R. Johnson, A. Leal-Duarte, and C.M. Saiago. Inverse eigenvalue problems and lists of multiplicities of eigenvalues for matrices whose graph is a tree: the case of generalized stars and double
generalized stars. Lin. Alg. Appl. 373:311–330 (2003).
[JLS] C.R. Johnson, R. Loewy, and P. Smith. The graphs for which the maximum multiplicity of an
eigenvalue is two, (manuscript).
[JS02] C.R. Johnson and C.M. Saiago. Estimation of the maximum multiplicity of an eigenvalue in terms
of the vertex degrees of the graph of a matrix. Elect. J. Lin. Alg. 9:27–31 (2002).
[JSa] C.R. Johnson and C.M. Saiago. The trees for which maximum multiplicity implies the simplicity of
other eigenvalues. Discrete Mathematics, (to appear).
[JSb] C.R. Johnson and C.M. Saiago. Branch duplication for the construction of multiple eigenvalues in
an Hermitian matrix whose graph is a tree. Lin. Multilin. Alg. (to appear).
[JS04] C.R. Johnson and B.D. Sutton. Hermitian matrices, eigenvalue multiplicities, and eigenvector
components. SIAM J. Matrix Anal. Appl. 26(2):390–399 (2004).
[JSW] C.R. Johnson, B.D. Sutton, and A. Witt. Implicit construction of multiple eigenvalues for trees,
(preprint).
[Lea89] A. Leal-Duarte. Construction of acyclic matrices from spectral data. Lin. Alg. Appl. 113:173–182
(1989).
[Lea92] A. Leal-Duarte. Desigualdades Espectrais e Problemas de Existência em Teoria de Matrizes.
Dissertação de Doutoramento, Coimbra, 1992.
[MOD89] J.S. Maybee, D.D. Olesky, P. Van Den Driessche, and G. Wiener. Matrices, digraphs, and determinants. SIAM J. Matrix Anal. Appl. 10(4):500–519 (1989).
[Nyl96] P. Nylen. Minimum-rank matrices with prescribed graph. Lin. Alg. Appl. 248:303–316 (1996).
[Par60] S. Parter. On the eigenvalues and eigenvectors of a class of matrices. J. Soc. Ind. Appl. Math.
8:376–388 (1960).
[Sai03] C.M. Saiago. The Possible Multiplicities of the Eigenvalues of an Hermitian Matrix Whose Graph Is
a Tree. Dissertação de Doutoramento, Universidade Nova de Lisboa, 2003.
[She04] D. Sher. Observations on the multiplicities of the eigenvalues of an Hermitian matrix with a
tree graph. University of William and Mary, Research Experiences for Undergraduates program,
summer 2004. (Advisor: C.R. Johnson)
[Wie84] G. Wiener. Spectral multiplicity and splitting results for a class of qualitative matrices. Lin. Alg.
Appl. 61:15–29 (1984).