In the chapter 7 of the book "Introduction to Linear Algebra" by Gilbert Strang,in order to find the second largest eigenvalue,the book gives an equation to reduce the size of S
to n-1,I paste the picture,S is a symmetric matrix,$\lambda_{1}$ is the largest eigenvalue of S,and I dont know how to get this equation 13.
Thanks a lot!
Best Answer
Since $[\mathbf{q}_1 .. \mathbf{q}_n]$ are mutually orthogonal, they form a basis, so you can express any vector as a linear combination of the $\mathbf{q}_i$'s:
$$\mathbf{v} = a_1 \cdot \mathbf{q}_1 + \dots +a_n \cdot \mathbf{q}_n \tag{1}\label{eq1}$$
In particular, you can write a column of $\mathbf{S} \cdot \mathbf{Q}_1$ as
$$ \mathbf{S} \cdot \mathbf{Q}_{1j} = a_{1j} \cdot \mathbf{q}_1 + \dots + a_{nj} \cdot \mathbf{q}_n = \begin{bmatrix}\mathbf{q}_1 & \cdots & \mathbf{q}_n \end{bmatrix} \cdot \begin{bmatrix} a_{1j} \\ \vdots \\ a_{nj} \end{bmatrix} \tag{2}\label{eq2} $$
When we do this for all columns
$$ \mathbf{S} \cdot \mathbf{Q}_{1} = \begin{bmatrix}\mathbf{q}_1 & \cdots & \mathbf{q}_n \end{bmatrix} \cdot \begin{bmatrix} a_{11} & \cdots & a_{1n} \\ \vdots & \ddots & \vdots \\ a_{n1} & \cdots & a_{nn} \end{bmatrix} \tag{3}\label{eq3} $$
The elements $a_{ij}$ can be computed by left-multiplying both sides of equation \eqref{eq3} by $\begin{bmatrix}\mathbf{q}_1 & \cdots & \mathbf{q}_n \end{bmatrix}^{-1}$, and the inverse is the transpose because the $\mathbf{q}_k$ are orthonormal.
$$ \mathbf{A} = \mathbf{Q}_1^T \cdot \mathbf{S} \cdot \mathbf{Q}_1 \tag{4}\label{eq4} $$
Since $\mathbf{S} \mathbf{q}_1 = \lambda_1 \mathbf{q}_1$, we know that $\mathbf{q}_1$ is an eigenvector, so equation \eqref{eq3} becomes
$$ \mathbf{S} \cdot \mathbf{Q}_{1} = \begin{bmatrix}\mathbf{q}_1 & \cdots & \mathbf{q}_n \end{bmatrix} \cdot \begin{bmatrix} \lambda_{1} & a_{12} & \cdots & a_{1n} \\ 0 & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & a_{n2} & \cdots & a_{nn} \end{bmatrix} \tag{5}\label{eq5} $$
which is of the form
$$ \mathbf{S} \cdot \mathbf{Q}_{1} = \begin{bmatrix}\mathbf{q}_1 & \cdots & \mathbf{q}_n \end{bmatrix} \cdot \begin{bmatrix} \lambda_{1} & \mathbf{w}^{T} \\ \mathbf{0} & \mathbf{S}_{n-1} \end{bmatrix} \tag{6}\label{eq6} $$
Finally, when $\mathbf{S}$ is symmetric, by \eqref{eq4} it is easy to show that $\mathbf{A}$ is symmetric, from which we conclude that $\mathbf{w}^T = \mathbf{0}^T$ and $\mathbf{S}_{n-1}$ is symmetric.