Eigenvalues, Multiplicities and Graphs

Contents
Preface
List of Terms and Symbols
0 Background
	0.1 Matrices
		0.1.1 Hermitian / Real Symmetric Matrices
		0.1.2 Interlacing Eigenvalues
		0.1.3 Rank Inequalities and Change in Hermitian Multiplicities
		0.1.4 Eigenvector Structure When a Submatrix Has the Same Eigenvalue
		0.1.5 Perron-Frobenius Theory of Nonnegative Matrices
		0.1.6 Entries of Matrix Powers
		0.1.7 M-matrices
	0.2 Graphs
		0.2.1 Definitions
		0.2.2 Trees
		0.2.3 Graphs and Matrices
		0.2.4 Graphs and Characteristic Polynomial Formulae
	0.3 Other Background
1 Introduction
	1.1 Problem Definition
	1.2 Matrices versus Graphs
	1.3 Early History
	1.4 The Interlacing Constraint
	1.5 Overview
2 Parter-Wiener, etc. Theory
	2.1 Introduction
	2.2 An Example
	2.3 General Theory of the Existence of Parter Vertices for Trees
	2.4 Characterization of Parter Vertices
	2.5 The Possible Changes in Status of One Vertex upon Removal of Another
	2.6 At Least Two Multiplicities Equal to 1
	2.7 Eigenstructure of Tridiagonal Hermitian Matrices and Their Principal Submatrices
	2.8 Nontrees
	2.9 Tree-Like Vertices
3 Maximum Multiplicity for Trees, I
	3.1 Introduction
	3.2 Path Covers and Path Trees
	3.3 (T) = Maximum p − q
	3.4 M(T) = P(T), (T), n − mr(T)
	3.5 Calculation of M(T) and Bounds
	3.5.1 Calculation of M(T) in Linear Time
	3.5.2 Estimation of M(T) from the Degree Sequence of T
4 Multiple Eigenvalues and Structure
	4.1 Perturbation of Diagonal Entries and Vertex Status
	4.2 Parter Vertices, Parter Sets and Fragmentation
	4.3 The Fundamental Decomposition
	4.4 Eigenspace Structure and Vertex Classification
	4.5 Removal of an Edge
	4.5.1 Basic Inequalities
	4.5.2 Classification of Edges in Trees Based on the Classification of Their Vertices
5 Maximum Multiplicity, II
	5.1 The Structure of Matrices with a Maximum Multiplicity Eigenvalue
	5.2 NIM Trees
	5.3 The Second Maximum Multiplicity
6 The Minimum Number of Distinct Eigenvalues
	6.1 Introduction
	6.2 The Diameter and a Lower Bound for c(T )
	6.3 The Method of Branch Duplication: Combinatorial and Algebraic
	6.4 Converse to the Diameter Lower Bound for Trees
	6.5 Trees of Diameter 7
	6.6 The Function C(d) and Disparity
	6.7 The Minimum Number of Multiplicities Equal to 1
	6.8 The Relative Position of Multiple Eigenvalues in Ordered Lists
		6.8.1 A Lower Bound for the Cardinality of a Fragmenting Parter Set
		6.8.2 The Relative Position of a Single Multiple Eigenvalue
		6.8.3 Vertex Degrees
		6.8.4 Two Multiple Eigenvalues
7 Construction Techniques
	7.1 Introduction
	7.2 Eigenvalues for Paths and Subpaths
	7.3 The Method of Assignments
	7.4 Derivation of a Multiplicity List via Assignment: An Example
	7.5 A 13-Vertex Example
	7.6 The Implicit Function Theorem (IFT) Approach
	7.7 More IFT, Examples, Vines
	7.8 Polynomial Constructions
8 Multiplicity Lists for Generalized Stars
	8.1 Introduction
	8.2 A Characterization of Generalized Stars
	8.3 The Case of Simple Stars
	8.4 An Inverse Eigenvalue Problem for Generalized Stars
	8.5 The Multiplicity Lists
	8.6 The IEP versus Ordered Multiplicity Lists
	8.7 The Upward Multiplicity Lists
	8.8 c(T ) and U(T )
9 Double Generalized Stars
	9.1 Introduction
	9.2 Observations about Double Generalized Stars
	9.3 The Multiplicity Lists
	9.4 Double Paths
10 Linear Trees
	10.1 Introduction
	10.2 The Second Superposition Principle for Linear Trees
	10.3 Possible Multiplicity Lists for Linear Trees
	10.4 Cases of Sufficiency of Linear Trees
	10.5 Special Results for Linear Trees
11 Nontrees
	11.1 Introduction and Observations
	11.2 The Complete Graph
	11.3 The Cycle
	11.4 A Tree + an Edge
	11.4.1 A Graph + an Edge
	11.5 The Graphs G for Which M(G) = 2
	11.6 Graphs Permitting Just Two Distinct Eigenvalues
	11.7 Nearly Complete Graphs
	12 Geometric Multiplicities for General Matrices over a Field
	12.1 Preliminaries
	12.2 Geometric Parter-Wiener, etc. Theory
	12.3 The Geometric Downer Branch Mechanism for General Matrices over a Field
	12.4 The Maximum Geometric Multiplicity for a Tree
	12.5 The Minimum Number of Distinct Eigenvalues in a Diagonalizable Matrix Whose Graph Is a Tree
Appendix A: Multiplicity Lists for Trees on Fewer Than 12 Vertices
	A.1 Tree on 3 Vertices (1 tree)
	A.2 Trees on 4 Vertices (2 trees)
	A.3 Trees on 5 Vertices (3 trees)
	A.4 Trees on 6 Vertices (6 trees)
	A.5 Trees on 7 Vertices (11 trees)
	A.6 Trees on 8 Vertices (23 trees)
	A.7 Trees on 9 Vertices (47 trees)
	A.8 Trees on 10 Vertices (106 trees)
	A.9 Trees on 11 Vertices (235 trees)
Appendix B: Seeds for Branch Duplication
	B.1 Diameter < 7 Seeds
	B.2 Diameter 7 Seeds and Classification of Their Families Using Assignments
	B.3 Unfoldings in Each of the Three Families for Which c(T ) Is Demonstrably 8
Bibliography
Index