Recent Advances in Approximation Algorithms Spring 2015 Lecture 1 and 2: Random Spanning Trees

Disclaimer: These notes have not been subjected to the usual scrutiny reserved for formal publications. In these lectures we prove the matrix tree theorem and Burton, Pemantle theorem. 1.1 Overview of Eigenvalues of Symmetric Matrices Let A ∈ Rn×n be a symmetric matrix. Recall that λ is an eigenvalue of A with corresponding eigenvector x, if Ax = λx. It is easy to see that if x1 is an eigenvector of λ1 and x2 is an eigenvector of λ2 and λ1 6 = λ2, then x1 is orthogonal to x1, 〈x1, x2 〉 = 0. Even if there is a multiplicity of eigenvalues, i.e., λ1 = λ2, we still assume that we have an eigenvector corresponding to each eigenvalue such that for any i ≥ j, xi is orthogonal to xj. To justify that, notice that when we have eigenvalues with multiplicity k it means that the there is a corresponding linear space of dimension k corresponding to those eigenvalues. So we can choose k orthonormal vectors in that linear space and assign each of them to one of those k equal eigenvalues. The variational characterization of eigenvalues gives a way of estimating eigenvalues as solutions of an optimization problem. If λ1 ≤ λ2 ≤... λn are the eigenvalues of A, then λk = min x1,...,xk orthogonal max x 6=0 xᵀAx xᵀx: x ∈ span{x1,..., xk} (1.1) = max x1,...,xn−k+1 orthogonal min x 6=0 xᵀAx xᵀx: x ∈ span{x1,..., xn−k+1 xᵀAx in is usually considered as the natural quadratic form of the matrix A. Perhaps one of the main use of this characterization is to prove bounds on the eigenvalues without actually computing them. Recall that all eigenvalues of every symmetric matrix is real. By spectral theorem, for any symmetric matrix A with real eigenvalues λ1,..., λn and corresponding eigenvectors x1,..., xn we can write, A = n∑ i=1 λixix ᵀ i. Using the above characterization we can define f(A) for an arbitrary function f, just by acting f on the eigenvalues of A. f(A):= n∑ i=1 f(λi)xix ᵀ i. For example, let f(t) = 1/t if t 6 = 0 and f(t) = 0 otherwise. Then we can define the pseudo-inverse of A as follows