Among the n eigenvalues of an n-by-n matrix may be several repetitions (the
number of which counts toward the total of n). For general matrices over a gen-
eral 〠eld, these multiplicities may be algebraic (the number of appearances as
a root of the characteristic polynomial) or geometric (the dimension of the cor-
responding eigenspace). These multiplicities are quite important in the analysis
of matrix structure because of numerical calculation, a variety of applications,
and for theoretical interest. We are primarily concerned with geometric multi-
plicities and, in particular but not exclusively, with real symmetric or complex
Hermitian matrices, for which the two notions of multiplicity coincide.
It has been known for some time, and is not surprising, that the arrange-
ment of nonzero entries of a matrix, conveniently described by the graph
of the matrix, limits the possible geometric multiplicities of the eigenvalues.
Much less limited by this information are either the algebraic multiplicities
or the numerical values of the (distinct) eigenvalues. So, it is natural to study
exactly how the graph of a matrix limits the possible geometric eigenvalue
multiplicities.
Author(s): Charles R. Johnson, Carlos M. Saiago
Series: Cambridge Tracts in Mathematics 211
Publisher: Cambridge University Press
Year: 2018
Language: English
Pages: 315
Contents......Page 8
Preface......Page 14
List of Terms and Symbols......Page 17
0.1 Matrices......Page 24
0.1.2 Interlacing Eigenvalues......Page 25
0.1.4 Eigenvector Structure When a Submatrix Has the Same Eigenvalue......Page 26
0.1.7 M-matrices......Page 27
0.2.1 Definitions......Page 28
0.2.2 Trees......Page 29
0.2.3 Graphs and Matrices......Page 30
0.3 Other Background......Page 31
1.1 Problem Definition......Page 33
1.2 Matrices versus Graphs......Page 34
1.3 Early History......Page 35
1.4 The Interlacing Constraint......Page 36
1.5 Overview......Page 37
2.2 An Example......Page 39
2.3 General Theory of the Existence of Parter Vertices for Trees......Page 41
2.4 Characterization of Parter Vertices......Page 48
2.5 The Possible Changes in Status of One Vertex upon Removal of Another......Page 51
2.6 At Least Two Multiplicities Equal to 1......Page 65
2.7 Eigenstructure of Tridiagonal Hermitian Matrices and Their Principal Submatrices......Page 68
2.8 Nontrees......Page 70
2.9 Tree-Like Vertices......Page 72
3.2 Path Covers and Path Trees......Page 74
3.3 (T) = Maximum p − q......Page 76
3.4 M(T) = P(T), (T), n − mr(T)......Page 81
3.5 Calculation of M(T) and Bounds......Page 83
3.5.1 Calculation of M(T) in Linear Time......Page 84
3.5.2 Estimation of M(T) from the Degree Sequence of T......Page 87
4.1 Perturbation of Diagonal Entries and Vertex Status......Page 92
4.2 Parter Vertices, Parter Sets and Fragmentation......Page 97
4.3 The Fundamental Decomposition......Page 102
4.4 Eigenspace Structure and Vertex Classification......Page 105
4.5.1 Basic Inequalities......Page 113
4.5.2 Classification of Edges in Trees Based on the Classification of Their Vertices......Page 118
5.1 The Structure of Matrices with a Maximum Multiplicity Eigenvalue......Page 119
5.2 NIM Trees......Page 124
5.3 The Second Maximum Multiplicity......Page 131
6.2 The Diameter and a Lower Bound for c(T )......Page 133
6.3 The Method of Branch Duplication: Combinatorial and Algebraic......Page 135
6.4 Converse to the Diameter Lower Bound for Trees......Page 145
6.5 Trees of Diameter 7......Page 150
6.6 The Function C(d) and Disparity......Page 152
6.7 The Minimum Number of Multiplicities Equal to 1......Page 155
6.8.1 A Lower Bound for the Cardinality of a Fragmenting Parter Set......Page 157
6.8.2 The Relative Position of a Single Multiple Eigenvalue......Page 159
6.8.3 Vertex Degrees......Page 163
6.8.4 Two Multiple Eigenvalues......Page 167
7.2 Eigenvalues for Paths and Subpaths......Page 169
7.3 The Method of Assignments......Page 170
7.4 Derivation of a Multiplicity List via Assignment: An Example......Page 172
7.5 A 13-Vertex Example......Page 173
7.6 The Implicit Function Theorem (IFT) Approach......Page 174
7.7 More IFT, Examples, Vines......Page 179
7.8 Polynomial Constructions......Page 183
8.1 Introduction......Page 190
8.2 A Characterization of Generalized Stars......Page 191
8.3 The Case of Simple Stars......Page 192
8.4 An Inverse Eigenvalue Problem for Generalized Stars......Page 196
8.5 The Multiplicity Lists......Page 197
8.6 The IEP versus Ordered Multiplicity Lists......Page 200
8.7 The Upward Multiplicity Lists......Page 204
8.8 c(T ) and U(T )......Page 206
9.1 Introduction......Page 209
9.2 Observations about Double Generalized Stars......Page 210
9.3 The Multiplicity Lists......Page 213
9.4 Double Paths......Page 219
10.1 Introduction......Page 223
10.2 The Second Superposition Principle for Linear Trees......Page 224
10.3 Possible Multiplicity Lists for Linear Trees......Page 226
10.4 Cases of Sufficiency of Linear Trees......Page 230
10.5 Special Results for Linear Trees......Page 232
11.2 The Complete Graph......Page 234
11.3 The Cycle......Page 236
11.4 A Tree + an Edge......Page 237
11.4.1 A Graph + an Edge......Page 243
11.5 The Graphs G for Which M(G) = 2......Page 245
11.6 Graphs Permitting Just Two Distinct Eigenvalues......Page 248
11.7 Nearly Complete Graphs......Page 251
12.1 Preliminaries......Page 255
12.2 Geometric Parter-Wiener, etc. Theory......Page 257
12.3 The Geometric Downer Branch Mechanism for General Matrices over a Field......Page 262
12.4 The Maximum Geometric Multiplicity for a Tree......Page 266
12.5 The Minimum Number of Distinct Eigenvalues in a Diagonalizable Matrix Whose Graph Is a Tree......Page 268
A.3 Trees on 5 Vertices (3 trees)......Page 270
A.6 Trees on 8 Vertices (23 trees)......Page 271
A.7 Trees on 9 Vertices (47 trees)......Page 273
A.8 Trees on 10 Vertices (106 trees)......Page 276
A.9 Trees on 11 Vertices (235 trees)......Page 282
B.1 Diameter < 7 Seeds......Page 299
B.2 Diameter 7 Seeds and Classification of Their Families Using Assignments......Page 300
B.3 Unfoldings in Each of the Three Families for Which c(T ) Is Demonstrably 8......Page 302
Bibliography......Page 304
Index......Page 310
