Lemma 1 Let ( λ , u ⃗ ) (\lambda, \vec{u}) ( λ , u ) A ∈ S n A \in S^{n} A ∈ S n
∃ U , U is orthornormal : U ⊤ A U = [ λ 0 … 0 0 ⋮ 0 [ B ] ] and B ∈ S n − 1 \exist U, U \text{ is orthornormal}: \\
U^{\top} A U = \begin{bmatrix}
\lambda & \begin{matrix} 0 & \dots & 0 \end{matrix} \\
\begin{matrix} 0 \\ \vdots \\ 0 \end{matrix} &
\begin{bmatrix}B\end{bmatrix}
\end{bmatrix} \\
\text{and } B \in S^{n-1} ∃ U , U is orthornormal : U ⊤ A U = ⎣ ⎡ λ 0 ⋮ 0 0 … 0 [ B ] ⎦ ⎤ and B ∈ S n − 1 Intuition for this lemma: We want to prove the multiplicity equality property by induction, each time we can just count the multiplicity for the current λ \lambda λ λ \lambda λ A A A B B B
Proof of Lemma 1 :
We will construct U U U
U = [ u ⃗ [ U 1 ] ] U = \begin{bmatrix}
\vec{u} &\begin{bmatrix}
U_1
\end{bmatrix}
\end{bmatrix} U = [ u [ U 1 ] ] Seems like we can use gram-schmidt to construct U 1 U_1 U 1
Consider the multiplication of U ⊤ A U U^{\top} A U U ⊤ A U
U ⊤ A U = [ u ⃗ ⊤ [ U 1 ⊤ ] ] [ A ] [ u ⃗ [ U 1 ] ] = [ u ⃗ ⊤ [ U 1 ⊤ ] ] [ A u ⃗ A U 1 ] = [ u ⃗ ⊤ [ U 1 ⊤ ] ] [ λ u ⃗ A U 1 ] = [ λ u ⃗ ⊤ u ⃗ u ⃗ ⊤ A U 1 U 1 ⊤ λ u ⃗ [ B = U 1 ⊤ A U 1 ] ] = [ λ 0 ⋯ 0 0 ⃗ [ B = U 1 ⊤ A U 1 ] ] \begin{split}
U^{\top}AU &= \begin{bmatrix}
\vec{u}^{\top} \\ \begin{bmatrix} U_1^{\top} \end{bmatrix}
\end{bmatrix}
\begin{bmatrix}
A
\end{bmatrix}
\begin{bmatrix}
\vec{u} &\begin{bmatrix} U_1 \end{bmatrix}
\end{bmatrix} \\
&= \begin{bmatrix}
\vec{u}^{\top} \\ \begin{bmatrix} U_1^{\top} \end{bmatrix}
\end{bmatrix}
\begin{bmatrix}
A\vec{u} &AU_1
\end{bmatrix} \\
&= \begin{bmatrix}
\vec{u}^{\top} \\ \begin{bmatrix} U_1^{\top} \end{bmatrix}
\end{bmatrix}
\begin{bmatrix}
\lambda\vec{u} &AU_1
\end{bmatrix} \\
&= \begin{bmatrix}
\lambda \vec{u}^{\top}\vec{u} &\vec{u}^{\top}AU_1 \\
U_1^{\top} \lambda \vec{u} &\begin{bmatrix} B = U_1^{\top} AU_1 \end{bmatrix}
\end{bmatrix} \\
&= \begin{bmatrix}
\lambda &\begin{matrix}0 & \cdots & 0 \end{matrix} \\
\vec{0} &\begin{bmatrix} B = U_1^{\top} AU_1 \end{bmatrix}
\end{bmatrix}
\end{split} U ⊤ A U = [ u ⊤ [ U 1 ⊤ ] ] [ A ] [ u [ U 1 ] ] = [ u ⊤ [ U 1 ⊤ ] ] [ A u A U 1 ] = [ u ⊤ [ U 1 ⊤ ] ] [ λ u A U 1 ] = [ λ u ⊤ u U 1 ⊤ λ u u ⊤ A U 1 [ B = U 1 ⊤ A U 1 ] ] = [ λ 0 0 ⋯ 0 [ B = U 1 ⊤ A U 1 ] ] u ⃗ ⊤ A U 1 = u ⃗ ⊤ A ⊤ undefined Because A is symmetric U 1 = ( A u ⃗ ) ⊤ U 1 = λ u ⃗ ⊤ U 1 = 0 ⃗ ⊤ \vec{u}^{\top}AU_1 = \vec{u}^{\top}\underbrace{A^{\top}}_{\mathclap{\text{Because $A$ is symmetric}}}U_1 = (A\vec{u})^{\top}U_1 = \lambda \vec{u}^{\top}U_1=\vec{0}^{\top} u ⊤ A U 1 = u ⊤ Because A is symmetric A ⊤ U 1 = ( A u ) ⊤ U 1 = λ u ⊤ U 1 = 0 ⊤ Proof of the multiplicity equality property Since we proved in Lemma 1 that B ∈ S n − 1 B \in S^{n-1} B ∈ S n − 1
B = V ⊤ Λ V B = V^{\top}\Lambda V B = V ⊤ Λ V We know also:
U ⊤ A U = [ λ ⋯ 0 0 ⋮ 0 B ] U^{\top}AU = \begin{bmatrix}
\lambda &\begin{matrix}\cdots &0 \end{matrix} \\
\begin{matrix} 0 \\ \vdots \\ 0 \end{matrix} &B
\end{bmatrix} U ⊤ A U = ⎣ ⎡ λ 0 ⋮ 0 ⋯ 0 B ⎦ ⎤ Therefore
V U ⊤ A U V ⊤ = [ λ ⋯ 0 0 ⋮ 0 [ V B V ⊤ = Λ ] ] VU^{\top}AUV^{\top} = \begin{bmatrix}
\lambda &\begin{matrix}\cdots &0 \end{matrix} \\
\begin{matrix} 0 \\ \vdots \\ 0 \end{matrix} &\begin{bmatrix} VBV^{\top} = \Lambda \end{bmatrix}
\end{bmatrix} V U ⊤ A U V ⊤ = ⎣ ⎡ λ 0 ⋮ 0 ⋯ 0 [ V B V ⊤ = Λ ] ⎦ ⎤