Proof that an $n \times n$ real symmetric matrix has $n$ real eigenvalues How to show that an $n \times n$ real symmetric matrix has $n$ real eigenvalues
$$
\lambda_n \geqslant \dots \geqslant  \lambda_1
$$ 
with corresponding eigenvectors $\mathbf v_n, \dots,\mathbf v_1$ such that
$$
\mathbf v_i^T \mathbf v_j = \delta_{ij}.
$$
I am struggling a bit on how to start this proof. I tried looking online but could not find anything. Perhaps I am looking in the wrong direction, would it be the same to prove that such a matrix would have $n$ real orthogonal eigenvectors and thus $n$ real eigenvalues? Hints on where to start this proof would be appreciated. 
 A: This is actually fairly straightforward. Let the symmetric matrix be $A$. Let's start with the classic result:

Let $\lambda$ be an eigenvalue of $A$ with eigenvector $v$. Then $\lambda \in \mathbb{R}$.

Proof: $v^{\dagger} v$ is real for any complex vector. By definition,
$$ \lambda v^{\dagger}v = v^{\dagger} A v. $$
Taking conjugate transpose on both sides,
$$ \bar{\lambda} v^{\dagger} v = (v^{\dagger} Av)^{\dagger} = v^{\dagger} A^{\dagger} v = v^{\dagger} A v = \lambda v^{\dagger} v. $$
Since $v \neq 0$, $\lambda=\bar{\lambda}$ and so $\lambda$ is real. $\square$
(And further, therefore the eigenvectors are all real since $A$ is real, and we can go back to normal transposes.)
Now, having done that, we need to show that $A$ has an eigenvalue. There are two ways of doing this: firstly, we can just write down the characteristic polynomial $\det{(\lambda I-A)}$, and find its roots, which consist of the eigenvalues. Alternatively, consider the function
$$ R(x) = \frac{x^T A x }{x^Tx}, $$
often called the Rayleigh quotient. One can prove that the minimiser of this quotient is an eigenvector. (It turns out to be equivalent to minimising $x^T A x$ subject to $x^T x=1$, and then you can use Lagrange multipliers and derive that a minimiser must be an eigenvector. Further, it's a continuous function on a compact set and hence it attains its minimum.) Indeed, the minimum produces the smallest eigenvector (this is easy to check: suppose not, &c.)
Now we need the other classic result:

Eigenvectors with different eigenvalues are orthogonal.

Proof: Let $\lambda,v$ and $\mu,u$ be eigenvalues and their eigenvectors. Then
$$ \lambda u^Tv = u^T A v = (v^T A^T u)^T = (v^T Au)^T = \mu (v^T u)^T = u^T v, $$
so if $\lambda \neq \mu$, $u^Tv=0$. $\square$
Now we can derive an algorithm to produce orthonormal eigenvectors. Go back to the minimisation problem, $ x^T A x $ on the sphere $x^Tx=1$. We have already noticed that the minimum gives the smallest eigenvalue $\lambda_1$ and an eigenvector $v_1$ corresponding to it. Now add in an extra condition: $v_1^T x=0$. This is a closed set because $x \mapsto v_1^Tx$ is continuous. Hence the minimisation problem
$$  x^T A x, \quad \text{subject to }  x^Tx=1, \quad v_1^Tx=0 $$
has a minimiser, which you can check gives you another eigenvector $v_2$ and eigenvalue $\lambda_2 \geqslant \lambda_1$. It should be fairly obvious what's going to happen now: add in $v_2^T x=0$ to the conditions on $x$, solve the minimisation problem ...
This algorithm terminates when the set of admissable vectors becomes empty, which can only occur when we have found $n$ vectors for $x$ to be orthogonal to: the $n$ eigenvectors we have found form an orthonormal basis as required.
(Alternatively, you can go about diagonalising $A$ one eigenvalue at a time, but it's quite tedious: you have to write it as a direct sum of eigenspaces, and it looks more complicated than using the Rayleigh quotient, but it generalises to other fields more easily.)
A: Since $|\lambda I-A|$ is of degree $n$, it has $n$ roots and so $A$ has $n$ eigenvalues.
Let $\lambda_i$ be any eigenvalue of $A$ and $x\ne 0$ be an eigenvector for $\lambda_i$. Then $Ax=\lambda_i x$. So $\overline{x}^TAx=\lambda_i \overline{x}^Tx$. By taking conjugate transpose of it, we have
$$
\overline{x}^T\overline{A}^Tx=\overline{x}^TAx=\overline{\lambda_i}\overline{x}^Tx=\lambda_i \overline{x}^Tx
$$
So $\overline{\lambda_i}={\lambda_i}$ for $\overline{x}^Tx>0$. Thus $\lambda_i$ is real.
Since all eigenvalues of $A$ are real, so are eigenvectors of $A$. Let $x_1$ be a real normalized eigenvector for $\lambda_1$, i.e. $Ax_1=\lambda_1 x_1$. Then $x_1$ can be expanded to an orthonormal base of $x_1, \cdots, x_n$. Let $S=(x_1, \cdots, x_n)$. Then $S^{-1}=S^T$. Note that
$$
AS=A(x_1,x_2,\cdots, x_n)=S\pmatrix{\lambda_1 & *\\ 0& B_1}=SB
$$
So $S^{-1}AS=S^TAS=B$. Moreover, since $A$ is symmetric, $B^T=B$, i.e.
$$
B=\pmatrix{\lambda_1 & 0\\ 0& B_1}
$$
where $B_1$ is $(n-1)\times (n-1)$ and symmetric. By induction hypothesis, there is an orthogonal matrix $S_1$ that $B_1S_1=S_1\Lambda_1$, where $\Lambda_1$ is diagonal. Hence
$$
\pmatrix{\lambda_1 & 0\\ 0& B_1}\pmatrix{1 & 0\\ 0& S_1}=\pmatrix{1 & 0\\ 0& S_1}\pmatrix{\lambda_1 & 0\\ 0& \Lambda_1}
$$
Let
$$
B=\pmatrix{\lambda_1 & 0\\ 0& B_1}\quad\text{}\quad Q=\pmatrix{1 & 0\\ 0& S_1}\quad\text{}\quad \Lambda=\pmatrix{1 & 0\\ 0& \Lambda_1}
$$
Then $BQ=Q\Lambda$. Let $P=SQ$. Then $P$ is orthogonal. Thus we have
$$P^TAP=\Lambda$$
Clearly, $\Lambda=\operatorname{Diag}{(\lambda_1, \cdots, \lambda_n)}$ and each column of $P$ is an eigenvector of $A$.
