Eigenvalues, Multiplicities and Graphs

Description

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. 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