CaltechTHESIS
  A Caltech Library Service

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.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:Spectral Gap, Edge Expansion, Mixing time
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Computer Science
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Schulman, Leonard J. (advisor)
  • Vidick, Thomas G. (advisor)
Thesis Committee:
  • Umans, Christopher M. (chair)
  • Schulman, Leonard J.
  • Vidick, Thomas Georges
  • Bruck, Jehoshua
Defense Date:8 December 2021
Non-Caltech Author Email:jenishc (AT) gmail.com
Record Number:CaltechTHESIS:06062022-043503154
Persistent URL:https://resolver.caltech.edu/CaltechTHESIS:06062022-043503154
DOI:10.7907/3vxb-6778
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:14949
Collection:CaltechTHESIS
Deposited By: Jenish Mehta
Deposited On:23 Jun 2022 20:48
Last Modified:04 Aug 2022 19:18

Thesis Files

[img] PDF - Final Version
Creative Commons Attribution Non-commercial.

1MB

Repository Staff Only: item control page