Expanders, Property Testing and the PCP theorem

Some linear algebra

Posted in lectures by HQN on September 21, 2008

I mentioned the Perron-Frobenius theorem in the lecture. There are two versions of the theorem, one for positive matrices and one for non-negative matrices. Define the spectral radius $\rho(\mathbf A) = \max\{|\lambda|\}$, where the max goes over all eigenvalues $\lambda$ of $\mathbf A$. Here $|\lambda|$ is the modulus of $\lambda$, as we allow complex eigenvalues.

Theorem 1 (Perron-Frobenius, positive matrices). Let $\rho$ be the spectral radius of a positive matrix $\mathbf A$. Then,

1. $\rho$ is positive
2. $\rho$ is an (real) eigenvalue of $\mathbf A$
3. there exists a positive $\rho$-eigenvector $\mathbf x$, i.e. $\mathbf{Ax} =\rho \mathbf{x, x>0}$
4. $\rho$ has geometric and algebraic multiplicity $1$, i.e. $\rho$ is a single root of $\det(\lambda\mathbf{I-A})=0$ and the $\rho$-eigenspace has dimension $1$
5. $|\lambda|<\rho$ for all other eigenvalues $\lambda \neq \rho$ of $\mathbf A$, i.e. $\rho$ is the unique eigenvalue of maximum modulus

Theorem 2 (Perron-Frobenius, non-negative matrices). Let $\rho$ be the spectral radius of a non-negative matrix $\mathbf A$. Then,

1. $\rho$ is non-negative
2. $\rho$ is an (real) eigenvalue of $\mathbf A$
3. there exists a non-negative $\rho$-eigenvector $\mathbf x$, i.e. $\mathbf{Ax} =\rho \mathbf{x, x\geq 0}$

Theorem 2 follows from Theorem 1 by a perturbing the non-negative matrix (so that it becomes positive), then take a limit. See my favourite linear algebra book for the proofs of these theorems.