On the Spectrum of the Singular Values of Z-Shaped Graph Matrices

The talk is based on the paper, On Mixing Distributions Via Random Orthogonal Matrices and the Spectrum of the Singular Values of Multi-Z Shaped Graph Matrices by Wenjun Cai, and, Aaron Potechin. arXiv link.

Abstract

Graph matrices are a type of matrix whose entries are functions of a random input such as a $G(n,1/2)$ graph. Thus, graph matrices have entries which are random but are generally not independent. Mathematically, little is known about graph matrices except for rough norm bounds. While these rough norm bounds are sufficient for many applications, we can hope to analyze graph matrices more precisely. Wigner’s Semicircle Law is a classic result in random matrix theory which says that if $M$ is an $n \times n$ symmetric matrix with random entries drawn independently from a distribution with mean 0 and variance 1 (and bounded moments) then as $n \to \infty$, the spectrum of the eigenvalues of $\frac{M}{\sqrt{n}}$ approaches $\frac{\sqrt{4-x^2}}{2\pi}$. In this talk, I will describe an analogue of Wigner’s Semicircle Law for Z-shaped graph matrices. I will begin by introducing graph matrices and why they are useful. I will then give a derivation of Wigner’s Semicircle Law and describe how the analysis can be generalized to find the spectrum of the singular values of Z-shaped graph matrices. Finally, I will briefly describe our follow-up work on this topic and some open problems.