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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: