Eigenvalues, multiplicities and graphs / Charles R. Johnson, College of William and Mary, Williamsburg, Virginia, Carlos M. Saiago, Universidade Nova de Lisboa.

Format:

Book

Author/Creator:

Johnson, Charles R., author.

Saiago, Carlos M., author.

Series:

Cambridge tracts in mathematics ; 211.

Cambridge tracts in mathematics ; 211

Language:

English

Subjects (All):

Eigenvalues.

Matrices.

Symmetric matrices.

Trees (Graph theory).

Physical Description:

xxii, 291 pages : illustrations ; 24 cm.

regular print

Place of Publication:

Cambridge, United Kingdom : Cambridge University Press, 2018.

Summary:

The arrangement of nonzero entries of a matrix, described by the graph of the matrix, limits the possible geometric multiplicities of the eigenvalues, which are far more limited by this information than algebraic multiplicities or the numerical values of the eigenvalues. This book gives a unified development of how the graph of a symmetric matrix influences the possible multiplicities of its eigenvalues. While the theory is richest in cases where the graph is a tree, work on eigenvalues, multiplicities and graphs has provided the opportunity to identify which ideas have analogs for non-trees, and those for which trees are essential. It gathers and organizes the fundamental ideas to allow students and researchers to easily access and investigate the many interesting questions in the subject

Contents:

Background

Introduction

Parter-Wiener, etc. theory

Maximum multiplicity for trees, I

Multiple eigenvalues and structure

Maximum multiplicity, II

The minimum number of distinct eigenvalues

Construction techniques

Multiplicity lists for generalized stars

Double generalized stars

Linear trees

Nontrees

Geometric multiplicities for general matrices over a field.

Machine generated contents note: 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.1g4.5.2 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^truction Techniques

7.1g4.5.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 Auction

7.1g4.5.2 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.

Notes:

Includes bibliographical references (pages 281-286) and index.

ISBN:

110709545X

9781107095458

OCLC:

991790102