Matrix Inequalities for Iterative Systems

Cover -- Half Title -- Title Page -- Copyright Page -- Dedication -- Acknowledgments -- Preface -- Table of Contents -- Symbol Description -- I: INTRODUCTION -- 1: Notation and Basic Facts -- 1.1 Matrices and Vectors -- 1.1.1 Matrices -- 1.1.2 Vectors -- 1.1.3 Matrix Classes -- 1.2 Graphs -- 1.2.1 Degrees -- 1.2.2 Adjacency Matrix -- 1.3 Number of Walks in Graphs -- 1.3.1 Walks -- 1.3.2 Number of Walks -- 1.4 Entry Sums and Matrix Powers -- 1.4.1 Entry Sums of Matrix Powers -- 1.4.2 Number of Walks and Matrix Powers -- 1.4.3 Local Decomposition -- 1.5 Subsets, Submatrices, and Weighted Entry Sums -- 1.5.1 Selected Walks and Submatrices -- 1.5.2 Weighted Entry Sums -- 1.5.3 Quadratic Forms and Hermitian Matrices -- 1.5.4 Global Decomposition -- 1.6 Elementary Inequalities for Vectors and Sequences -- 1.6.1 The Inequalities of Cauchy, Bunyakovsky, and Schwarz -- 1.6.2 The Inequalities of Rogers and Hölder -- 1.6.3 Chebyshev's Sum Inequality -- 1.6.4 Inequalities for Arithmetic, Geometric, Harmonic, and Power Means -- 2: Motivation -- 2.1 Simple Combinatorial Problems -- 2.2 Automata and Formal Languages -- 2.3 Graph Density, Maximum Clique and Densest k-Subgraph -- 2.4 The Number of Paths and Extremal Graph Theory -- 2.5 Means, Variances, and Irregularity -- 2.6 Random Walks and Markov Chains -- 2.7 Largest Eigenvalue -- 2.8 Population Genetics and Evolutionary Theory -- 2.9 Theoretical Chemistry -- 2.10 Iterated Line Digraphs -- 2.11 Other Applications -- 3: Diagonalization and Spectral Decomposition -- 3.1 Relevant Literature -- 3.2 Similar and Diagonalizable Matrices -- 3.3 Hermitian and Real Symmetric Matrices -- 3.4 Adjacency Matrices and Number of Walks in Graphs -- 3.5 Quadratic Forms for Diagonalizable Matrices -- II: UNDIRECTED GRAPHS / HERMITIAN MATRICES -- 4: General Results -- 4.1 Related Work for Products of Quadratic Forms

4.1.1 The Number of Walks in Graphs -- 4.1.1.1 The Results of Lagarias, Mazo, Shepp, and McKay -- 4.1.1.2 The Results of Dress and Gutman -- 4.1.1.3 Further Results -- 4.1.2 Real Symmetric, Positive-Semidefinite, and Hermitian Matrices -- 4.1.2.1 The Results of Marcus and Newman -- 4.1.2.2 The Results of Lagarias, Mazo, Shepp, and McKay -- 4.2 Generalizations for Products of Quadratic Forms -- 4.2.1 A Generalization of the Inequality by Dress and Gutman -- 4.2.2 The Method of Expectation of Random Variables -- 4.2.3 The Complex-Weighted Sandwich Theorem -- 4.2.3.1 A Related Theorem by Taussky and Marcus -- 4.2.4 Positive-Semidefinite Matrices -- 4.2.5 Negative-Semidefinite Matrices -- 4.2.6 The Density Implication -- 4.3 Related Work for Powers of Quadratic Forms -- 4.3.1 The Results of Erdős, Simonovits, and Godsil -- 4.3.2 The Results of Ilić and Stevanović -- 4.3.3 The Results of Scheuer and Mandel, Mulholland and Smith, Blakley and Roy, Blakley and Dixon, and London -- 4.3.4 The Results of Hyyrö, Merikoski, and Virtanen -- 4.4 Generalizations for Powers of Quadratic Forms -- 4.4.1 More General Results for Walk Numbers -- 4.4.2 A Special Case for the Average Number of Walks -- 4.4.3 The Density Implication -- 4.4.4 Other Theorems Involving Powers -- 4.4.5 The Method of Expectation of Random Variables -- 4.5 The Number of Walks and Degree Powers -- 4.5.1 Related Work -- 4.5.2 Refined Inequalities for Powers of Degrees or Row Sums -- 4.5.3 Other Degree-Related Inequalities -- 4.6 Invalid Inequalities -- 4.6.1 Known Results -- 4.6.2 Extended Results -- 4.7 Relaxed Inequalities Using Geometric Means -- 4.7.1 Remarks on Another Relaxed Inequality -- 4.7.2 An Improved Inequality Implied by Logarithmic Means -- 4.7.3 An Arithmetic-Geometric-Harmonic Mean Inequality -- 5: Restricted Graph Classes -- 5.1 Counterexamples for Special Cases

5.1.1 Bipartite Graphs -- 5.1.2 Forests and Trees -- 5.1.3 Construction of Worst Case Trees -- 5.2 Semiregular Graphs -- 5.3 Trees -- 5.3.1 Stars and Paths -- 5.3.2 Walks of Length 2 and 3 in Trees -- 5.3.3 Walks of Length 4 and 5 in Trees -- 5.3.3.1 (1, n1, n2)-Barbell Graphs (Trees with Diameter 3) -- 5.3.3.2 (2, n1, n2)-Barbell Graphs -- 5.3.3.3 Proof for the w5-Inequality for Trees -- 5.3.4 A Conjecture for Trees -- 5.4 Subdivision Graphs -- 5.4.1 Walks of Length 2 and 3 -- 5.4.2 Walks of Length 4 and 5 -- III: DIRECTED GRAPHS / NONSYMMETRIC MATRICES -- 6: Walks and Alternating Walks in Directed Graphs -- 6.1 Chebyshev's Sum Inequality -- 6.2 Relaxed Inequalities Using Geometric Means -- 6.3 Alternating Matrix Powers and Alternating Walks -- 6.3.1 Definitions and Interpretations -- 6.3.2 A Simple Generalization -- 6.3.3 Related Work -- 6.3.4 Transferring Hermitian Matrix Results to General Matrices -- 6.3.5 Generalizations for Nonnegative Matrices -- 6.3.5.1 Implications for Hermitian Matrices -- 6.3.6 Generalizations for Complex Matrices -- 6.3.6.1 Implications for Hermitian Matrices -- 7: Powers of Row and Column Sums -- 7.1 Degree Powers and Walks in Directed Graphs -- 7.1.1 Related Work -- 7.1.2 Extended Results -- 7.2 Row and Column Sums in Nonnegative Matrices -- 7.3 Other Inequalities for the Number of Walks -- 7.4 Geometric Means -- IV: APPLICATIONS -- 8: Bounds for the Largest Eigenvalue -- 8.1 Matrix Foundations -- 8.1.1 Complex Matrices -- 8.1.2 Normal Matrices -- 8.1.3 Real Symmetric and Hermitian Matrices -- 8.1.4 Nonnegative Matrices -- 8.1.5 Symmetric Nonnegative Matrices -- 8.2 Graphs and Adjacency Matrices -- 8.2.1 Directed Graphs -- 8.2.2 Directed Graphs with Normal Adjacency Matrix -- 8.2.3 Undirected Graphs -- 8.2.4 Other Bounds -- 8.3 Eigenvalue Moments and Energy -- 8.3.1 Energy Bounds -- 8.3.2 Closed Walks Bounds

9: Iterated Kernels -- 9.1 Related Work -- 9.2 Our Results -- 9.2.1 Hermitian Kernels -- 9.2.2 Nonnegative Symmetric Kernels -- 9.2.3 Nonnegative Kernels -- 9.3 Sidorenko's Conjecture -- Conclusion -- Bibliography -- Index