Combinatorial and Algebraic Propeties of Nonnegative Matrices

Citation

Mehta, Jenish Chetan (2022) Combinatorial and Algebraic Propeties of Nonnegative Matrices. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/3vxb-6778. https://resolver.caltech.edu/CaltechTHESIS:06062022-043503154

Abstract

We study the combinatorial and algebraic properties of Nonnegative Matrices. Our results are divided into three different categories.

1. We show the first quantitative generalization of the 100 year-old Perron-Frobenius theorem, a fundamental theorem which has been used within diverse areas of mathematics. The Perron-Frobenius theorem shows that any irreducible nonnegative matrix R will have a largest positive eigenvalue r, and every other eigenvalue λ is such that Reλ < R and |λ| ≤ r. We capture the notion of irreducibility through the widely studied notion of edge expansion φ of R which intuitively measures how well-connected the underlying digraph of R is, and show a quantitative relation between the spectral gap Δ = 1-Reλ/r (where λ ≠ r has the largest real part) of R to the edge expansion φ as follows.

(1/15) • [(Δ(R))/n] ≤ φ(R) ≤ √[2 • Δ(R)].

This also provides a more general result than the Cheeger-Buser inequalities since it applies to any nonnegative matrix.

2. We study constructions of specific nonsymmetric matrices (or nonreversible Markov Chains) that have small edge expansion but large spectral gap, taking us in a direction more novel and unexplored than studying symmetric matrices with constant edge expansion that have been extensively studied. We first analyze some known but less studied Markov Chains, and then provide a novel construction of a nonreversible chain for which

φ(R) ≤ [(Δ(R))/√n],

obtaining a bound exponentially better than known bounds. We also present a candidate construction of matrices for which

φ(R) ≤ 2[(Δ(R))/n]

which is the most beautiful contribution of this thesis. We believe these matrices have properties remarkable enough to deserve study in their own right.

3. We connect the edge expansion and spectral gap to other combinatorial properties of nonsymmetric matrices. The most well-studied property is mixing time, and we provide elementary proofs of the relation between mixing time and the edge expansion, and also other bounds relating the mixing time of a nonreversible chain to the spectral gap and to its additive symmetrization. Further, we provide a unified view of the notion of capacity and normalized capacity, and show the monotonicity of capacity of nonreversible chains amongst other results for nonsymmetric matrices. We finally discuss and prove interesting lemmas about different notions of expansion and show the first results for tensor walks or nonnegative tensors.

Thesis Files