Theorem: Let $A$ be a real $n \times n$ symmetric matrix. Then $A$ has an orthonormal basis of eigenvectors and can be written as $A = Q\Lambda Q^T$ where $Q$ is orthogonal.

Proof by induction on $n$:

Base case ($n = 1$): Any $1 \times 1$ matrix $A = [a]$ is already diagonal with eigenvector $1$.

Inductive step: Assume the theorem holds for $(n-1) \times (n-1)$ symmetric matrices. Let $A$ be $n \times n$ symmetric.

Step 1: Existence of a real eigenvalue and eigenvector.

Since $A$ is real and symmetric, the characteristic polynomial $p_A(\lambda) = \det(A - \lambda I)$ has real coefficients. Over $\mathbb{C}$, it has at least one root $\lambda_1$.

We showed earlier that this eigenvalue is real (for symmetric matrices). Let $\mathbf{v}_1$ be a corresponding eigenvector with $\|\mathbf{v}_1\| = 1$.

Step 2: Extend to orthonormal basis.

Extend $\{\mathbf{v}_1\}$ to an orthonormal basis $\{\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n\}$ of $\mathbb{R}^n$ using Gram-Schmidt.

Form orthogonal matrix $Q_1 = [\mathbf{v}_1 | \mathbf{v}_2 | \cdots | \mathbf{v}_n]$.

Step 3: Block structure in new basis.

Compute $Q_1^TAQ_1$. The first column of $AQ_1$ is: $A\mathbf{v}_1 = \lambda_1\mathbf{v}_1$

Therefore, the first column of $Q_1^TAQ_1$ is: $Q_1^T(\lambda_1\mathbf{v}_1) = \lambda_1Q_1^T\mathbf{v}_1 = \lambda_1\mathbf{e}_1 = \begin{pmatrix} \lambda_1 \\ 0 \\ \vdots \\ 0 \end{pmatrix}$

By symmetry of $Q_1^TAQ_1$ (since $(Q_1^TAQ_1)^T = Q_1^TA^TQ_1 = Q_1^TAQ_1$), the first row is also $[\lambda_1, 0, \ldots, 0]$.

Thus: $Q_1^TAQ_1 = \begin{bmatrix} \lambda_1 & \mathbf{0}^T \\ \mathbf{0} & B \end{bmatrix}$

where $B$ is $(n-1) \times (n-1)$ and symmetric (as a submatrix of a symmetric matrix).

Step 4: Apply induction to $B$.

By the inductive hypothesis, $B$ has an orthonormal eigenvector basis. There exists orthogonal $(n-1) \times (n-1)$ matrix $R$ such that: $R^TBR = \Lambda_2 = \text{diag}(\lambda_2, \ldots, \lambda_n)$

Step 5: Combine the transformations.

Define $n \times n$ orthogonal matrix: $Q_2 = \begin{bmatrix} 1 & \mathbf{0}^T \\ \mathbf{0} & R \end{bmatrix}$

Then: $Q_2^T(Q_1^TAQ_1)Q_2 = \begin{bmatrix} 1 & \mathbf{0}^T \\ \mathbf{0} & R^T \end{bmatrix}\begin{bmatrix} \lambda_1 & \mathbf{0}^T \\ \mathbf{0} & B \end{bmatrix}\begin{bmatrix} 1 & \mathbf{0}^T \\ \mathbf{0} & R \end{bmatrix}$ $= \begin{bmatrix} \lambda_1 & \mathbf{0}^T \\ \mathbf{0} & R^TBR \end{bmatrix} = \begin{bmatrix} \lambda_1 & \mathbf{0}^T \\ \mathbf{0} & \Lambda_2 \end{bmatrix} = \Lambda$

Step 6: Construct the full orthogonal diagonalization.

Let $Q = Q_1Q_2$. Then $Q$ is orthogonal (product of orthogonal matrices), and: $Q^TAQ = (Q_1Q_2)^TA(Q_1Q_2) = Q_2^TQ_1^TAQ_1Q_2 = \Lambda$

Thus $A = Q\Lambda Q^T$.

Step 7: Orthonormality of eigenvectors.

The columns of $Q$ are orthonormal (since $Q$ is orthogonal) and are eigenvectors of $A$ with eigenvalues $\lambda_1, \ldots, \lambda_n$ (the diagonal entries of $\Lambda$).

By induction, the spectral theorem holds for all $n$. ∎