The material we covered is the second half of Lecture 2 and first half of Lecture 3 in Spielman's notes.
-(note that below I use C(i,j) for the (i,j)'th entry in the matrix C, as opposed to class where I used subscripts)
1. We proved Feidler's Theorem that for a Laplacian of a weighted path, an eigenvector of the k'th smallest eigenvalue changes sign *at most* times.
I stated this as *exactly* k times, but as was noted in class this does not make sense when the eigenvalue has multiplicity>1. So what is correct is the `at most' statement,
and the `exactly' statement is true only when the k'th smallest eigenvalue has multiplicity one.
2. I had a problem with the proof of the above theorem at the following point: We had a symmetric matrix C such that for any vector x x^T*C*x = \sum_i lambda_i *(x_i)^2.
I wanted to say that this implies the lambda_i's are eigenvalues of C. This is true since in the bilinear form x^T*C*x, for a symmetric C, the coefficient of x_i*x_j is 2*C(i,j) , so the equality above implies C is a diagonal matrix with C(i,i) =lambda_i in the diagonal. What I claimed about certain unit vectors being eigenvectors was not true.
Ariel Gabizon > Comments and Announcements about course on Spectral Methods - Fall 2010, Technion >