Proving symmetric matrices are diagonalizable

I'm at a loss of how to show this. I know that this is implied by the Spectral Theorem but not sure exactly how to show this in a simple, straightforward proof.

I've tried laying down what I know about symmetric matrices and diagonalizable ones but I'm not too sure what to use when. My guess is I'd have to reason with regards to the eigenvalues but again I'm not sure.

A matrix is symmetric if $A = A^T$. A matrix $A$ is symmetric if it can be expressed in the form $A = QDQ^{T}$. A square matrix $A$ is called diagonalizable if $\exists$ invertible P such that $P^{-1}AP$ is a diagonal matrix.

Would really appreciate any help.

• Of course being diagonalisable doesn't imply being symmetric.
– Vim
Sep 17, 2017 at 1:19
• My mistake, omitted that out.
– SS'
Sep 17, 2017 at 1:25
• Sep 17, 2017 at 1:34
• Those links don't quite have any clear or concise proofs.
– SS'
Sep 17, 2017 at 1:37
• @ChristianBlatter perhaps OP wants proof that is so well structured and simplistic that they can imprint it on their mind and build it from scratch whenever requested. I think it's a meaningful question, to ask about simple, sound alternative proofs. (For example, this answer, if fully fledged, will be much more intuitive than most existing proofs.)
– Vim
Sep 20, 2017 at 4:45

For any symmetric matrix $$A \in \mathbb{R}^{n \times n}$$, consider the objective function,

$$$$\max_x x^T A x \\ \text{Given } \:x^Tx = 1$$$$

The solution (In case of multiple solutions, consider any one) to the above objective function say $$x_1$$ is such that, $$Ax_1 = \lambda_1 x_1$$

(You could show this using Lagrangian function)

Now consider the next objective function,

$$$$\max_x x^T A x \\ \text{Given } \:x^Tx = 1 \text{ and } x^Tx_1 = 0$$$$

The solution (In case of multiple solutions, consider any one) to the above objective function say $$x_2$$ is such that, $$Ax_2 = \lambda_2 x_2$$

(Again you could show this using Lagrangian function)

Continuing this procedure we could find the full set of eigen vectors.

The objective function at any iteration $$i$$ will be,

$$$$\max_x x^T A x \\ \text{Given } \:x^Tx = 1 \text{ and } x^Tx_1 = x^Tx_2 = \cdots x^Tx_{i-1} = 0$$$$

The above objective function will always have a solution as long as the constraint set (which is actually a closed and bounded subset of $$R^n$$) is not an empty set, i.e., $$\{x:x^Tx = 1 \text{ and } x^Tx_1 = x^Tx_2 = \cdots x^Tx_{i-1}\} \neq \phi$$

The constraint set will be empty only when $$x_1, x_2, \dots x_{i-1}$$ span the $$R^n$$, which means they form a full set of orthonormal basic for $$R^n$$ which are actually eigen vectors of $$A$$.

Once you have $$n$$ independent (actually orthonormal) vectors, it is straightforward to show that $$A$$ is diagonalisable.

Let be a symmetric matrix. We prove the claim by induction. For , the statement is trivially true.

Let $$\left(\lambda_1, x_1\right), \left(\lambda_2, x_2\right) \dots \dots \left(\lambda_k, x_k\right)$$ with $$x_i$$’s being independent. Thus we have,

\begin{align} A \left[x_1| x_2| \dots |x_k\right] &= \left[Ax_1|Ax_2|\dots|Ax_k\right] \\ &= \left[ \lambda_1 x_1|\lambda_2 x_2|\dots|\lambda_k x_k \right ] \\ &= \left[x_1|x_2| \dots |x_k\right] \begin{bmatrix} \lambda_1 & & \\ &\lambda_2& \\ & & \ddots \\ & & & \lambda_k \end{bmatrix} \end{align}

Since $$A$$ is symmetric, we can take $$x_i$$'s to be orthonormal. Let $$\left \{y_1, y_2 \dots y_{n-k} \right\}$$ be a set of orthonormal vectors such that $$\left\{ x_1, x_2 \dots x_k ,y_1, y_2, \dots y_{n-k}\right \}$$ form a orthonormal basis for $$\mathbb{R}^n$$

Let $$P_1 = \begin{bmatrix} x_1 &x_2 &\dots &x_k \end{bmatrix} \in \mathbb{R}^{n \times k}$$, $$P_2 = \begin{bmatrix} y_1 &y_2 &\dots &y_{n-k} \end{bmatrix} \in \mathbb{R}^{n \times (n-k)}$$ and $$D_1 = \begin{bmatrix} \lambda_1 & & \\ &\lambda_2& \\ & & \ddots \\ & & & \lambda_k \end{bmatrix}$$.

Thus,

\begin{align} P &= \begin{bmatrix} P_1 &P_2 \end{bmatrix} \\ &= \begin{bmatrix}x_1 &x_2 &\dots &x_k &y_1 &y_2 &\dots &y_{n-k} \end{bmatrix} \\ AP &= \begin{bmatrix} \lambda_1 x_1 &\lambda_2x_2 &\dots &\lambda_k x_k &Ay_1 &Ay_2 &\dots &Ay_{n-k} \end{bmatrix} \\ &=\begin{bmatrix} P_1 D_1 &AP_2 \end{bmatrix} \\ P^T AP &= \begin{bmatrix} P_1 ^T \\ P_2^T \end{bmatrix} \begin{bmatrix} P_1 D_1 &AP_2 \end{bmatrix} \\ &= \begin{bmatrix} P_1 ^T P_1 D_1 &P_1^T A P_2 \\ P_2^T P_1 D_1 &P_2^TAP_2 \end{bmatrix} \\ &= \begin{bmatrix} D_1 &0 \\ 0 &P_2^TAP_2 \end{bmatrix} \end{align}

Since, $$A$$ is symmetric, $$P^T_2 A P_2$$ is also symmetric matrix, but of dimension $$(n-k) \times (n-k)$$. Using induction hypothesis, $$\exists \: Q$$ such that,

$$Q^T P^T_2 A P_2 Q = D_2,$$ where $$D_2$$ is a diagonal matrix of dimension $$(n-k) \times (n-k)$$.

Let $$S =\begin{bmatrix} P_1 &P_2Q \end{bmatrix}$$.

Consider,

\begin{align} S^T A S &= \begin{bmatrix} P_1 ^T \\ Q^T P_2^T \end{bmatrix} A \begin{bmatrix} P_1 &P_2Q\end{bmatrix}\\ &= \begin{bmatrix} P_1 ^T AP_1 &P_1^T A P_2 \\ Q^T P_2^T A P_1 &Q^T P_2^TAP_2 Q \end{bmatrix} \\ &= \begin{bmatrix} P_1 ^T P_1D_1 &P_1^T A P_2 \\ Q^T P_2^T P_1 D_1 &D_2 \end{bmatrix} \\ &= \begin{bmatrix} D_1 &0 \\ 0 &D_2 \end{bmatrix} \end{align}

Hence, $$A$$ is diagonalisable.