Editing Spectral theory (section)

==Spectral theorem and Rayleigh quotient==
[[Optimization problem]]s may be the most useful examples about the combinatorial significance of the eigenvalues and eigenvectors in symmetric matrices, especially for the [[Rayleigh quotient]] with respect to a matrix '''M'''.

'''Theorem''' ''Let '''M''' be a symmetric matrix and let '''x''' be the non-zero vector that maximizes the [[Rayleigh quotient]] with respect to '''M'''. Then, '''x''' is an eigenvector of '''M''' with eigenvalue equal to the [[Rayleigh quotient]]. Moreover, this eigenvalue is the largest eigenvalue of&nbsp;'''M'''. ''

'''Proof'''   Assume the spectral theorem. Let the eigenvalues of '''M''' be <math>\lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n</math>. Since the <math>\{v_i\}</math> form an [[orthonormal basis]], any vector x can be expressed in this [[Basis (linear algebra)|basis]] as

: <math>x = \sum_i v_i^T x v_i</math>

The way to prove this formula is pretty easy. Namely,

: <math>\begin{align}
v_j^T \sum_i v_i^T x v_i
= {} & \sum_{i} v_i^{T} x v_j^{T} v_i \\[4pt]
= {} & (v_j^T x ) v_j^T v_j \\[4pt]
= {} & v_j^T x
\end{align}</math>
evaluate the [[Rayleigh quotient]] with respect to ''x'':

: <math>\begin{align}
x^T M x
= {} & \left(\sum_i (v_i^T x) v_i\right)^T M \left(\sum_j (v_j^T x) v_j\right) \\[4pt]
= {} & \left(\sum_i (v_i^T x) v_i^T\right) \left(\sum_j (v_j^T x) v_j\lambda_j \right) \\[4pt]
= {} & \sum_{i,j} (v_i^T x) v_i^T(v_j^T x) v_j\lambda_j \\[4pt]
= {} & \sum_j (v_j^T x)(v_j^T x)\lambda_j \\[4pt]
= {} & \sum_{j} (v_j^T x)^2\lambda_j\le\lambda_n \sum_j (v_j^T x)^2 \\[4pt]
= {} & \lambda_n x^T x,
\end{align}</math>
where we used [[Parseval's identity]] in the last line. Finally we obtain that
:<math>\frac{x^T M x}{x^T x}\le \lambda_n</math>

so the [[Rayleigh quotient]] is always less than <math>\lambda_n</math>.<ref>Spielman, Daniel A. "Lecture Notes on Spectral Graph Theory" Yale University (2012) http://cs.yale.edu/homes/spielman/561/ .</ref>