Matrix Inequalities for Iterative Systems

Description

The book reviews inequalities for weighted entry sums of matrix powers. Applications range from mathematics and CS to pure sciences. It unifies and generalizes several results for products and powers of sesquilinear forms derived from powers of Hermitian, positive-semidefinite, as well as nonnegative matrices. It shows that some inequalities are valid only in specific cases. How to translate the Hermitian matrix results into results for alternating powers of general rectangular matrices? Inequalities that compare the powers of the row and column sums to the row and column sums of the matrix powers are refined for nonnegative matrices. Lastly, eigenvalue bounds and derive results for iterated kernels are improved. Content: INTRODUCTION Notation and Basic Facts Matrices and Vectors Graphs Number of Walks in Graphs Entry Sums and Matrix Powers Subsets, Submatrices, and Weighted Entry Sums Elementary Inequalities for Vectors and Sequences Motivation Simple Combinatorial Problems Automata and Formal Languages Graph Density, Maximum Clique and Densest k-Subgraph The Number of Paths and Extremal Graph Theory Means, Variances, and Irregularity Random Walks and Markov Chains Largest Eigenvalue Population Genetics and Evolutionary Theory Theoretical Chemistry Iterated Line Digraphs Other Applications Diagonalization and Spectral Decomposition Relevant Literature Similar and Diagonalizable Matrices Hermitian and Real Symmetric Matrices Adjacency Matrices and Number of Walks in Graphs Quadratic Forms for Diagonalizable Matrices UNDIRECTED GRAPHS / HERMITIAN MATRICES General Results Related Work for Products of Quadratic Forms Generalizations for Products of Quadratic Related Work for Powers of Quadratic Forms Generalizations for Powers of Quadratic Forms The Number of Walks and Degree Powers Invalid Inequalities Relaxed Inequalities Using Geometric Means Restricted Graph Classes Counterexamples for Special Cases Semiregular Graphs Trees Subdivision Graphs DIRECTED GRAPHS / NONSYMMETRIC MATRICES Walks and Alternating Walks in Directed Graphs Chebyshev's Sum Inequality Relaxed Inequalities Using Geometric Means Alternating Matrix Powers and Alternating Walks Powers of Row and Column Sums Degree Powers and Walks in Directed Graphs Row and Column Sums in Nonnegative Matrices Other Inequalities for the Number of Walks Geometric Means APPLICATIONS Bounds for the Largest Eigenvalue Matrix Foundations Graphs and Adjacency Matrices Eigenvalue Moments and Energy Iterated Kernels Related Work Our Results Sidorenko's Conjecture