Linear algebra problem added Wednesday:

[THIS DOCUMENT COPIES THE QUESTION AND GIVES ANSWERS TAGGED WITH "ANSWER"]

I have made the claim that a symmetric n by n matrix has n orthogonal eigenvectors. (Reminder of what "orthogonal" means: the dot product $LaTeX: \mathbf u^\top\!\mathbf v$ is zero. Then one can normalize them to length = one - "orthonormal" if you ever saw that word - it means that the eigenvectors will be just a rotation of the standard coordinate system.)

This problem shows that. It isn't easy, so a lot of guidance is offered.

First, you shall prove that the eigenvectors must be orthogonal if the eigenvalues are distinct. To see this, let u and v be eigenvectors corresponding to eigenvalues $μ$ ≠ λ .
- Calculate $LaTeX: \mathbf u^\top\!\mathbf A\mathbf v$ and $LaTeX: \mathbf v^\top\!\mathbf A\mathbf u$ . Comparing the two, what do you get?
  ANSWER: They should be equal, as they are 1x1 and thus symmetric, and one is the transpose of the other. Calculating, we get $LaTeX: \mathbf u^\top\!\mathbf A\mathbf v = \mathbf u^\top\lambda\mathbf v$ and $LaTeX: \mathbf v^\top\!\mathbf A\mathbf u=\mathbf v^\top\!\mu\mathbf u$ . Putting them equal and using that u^Tv = v^Tu we have that $LaTeX: (\lambda-\mu)\mathbf u^\top\mathbf v=0.$ Since $μ$ ≠ λ, the dot product is zero.
- Why does the argument fail if the matrix is not symmetric?
  ANSWER: "one is the transpose of the other" fails. $LaTeX: (\mathbf u^\top\!\mathbf A\mathbf v)^\top=\mathbf v^\top\mathbf A\!^\top(\mathbf u^\top)^\top$ , so we need A^T = A.
Recall that the existence of real eigenvalues for symmetric matrices, come from the Lagrange conditions for the problem ; this problem has a solution (by the extreme value theorem), and by the FOC it must be for an eigenvector. Now assume that we have found k<n orthogonal eigenvectors v₁, ..., v_k, and all have length 1; and, let µ₁, ..., µ_k be the associated eigenvalues.
- Let $LaTeX: L(\mathbf x)=\mathbf x^\top\!\mathbf A\mathbf x - \alpha_1\mathbf v_1^\top \mathbf x-\dots- \alpha_k\mathbf v_k^\top \mathbf x-\lambda(\mathbf x^\top\mathbf x-1)$ be the Lagrangian associated to the problem $LaTeX: \max/\min\ \mathbf x^\top\!\mathbf A\mathbf x\quad\text{subject to}\quad\mathbf x^\top\mathbf x=1 \quad\text{and}\quad \mathbf v_j^\top \mathbf x=0\quad (\text{all }j=1,...,k)$
  State the Lagrange conditions.
  ANSWER (rough): The constraints, as well as the first-order condition, which since A is symmetric, becomes $LaTeX: 2\mathbf x^\top\!\mathbf A =2\lambda\mathbf x^\top + \alpha_1\mathbf v_1^\top+\dots + \alpha_k\mathbf v_k^\top$ .
  (It is easier to see the next step if you write as row and not transposed.)
- Take the FOC and multiply it with $LaTeX: \mathbf v_j$ ,remembering it is an eigenvector and that $LaTeX: \mathbf v_j^\top \mathbf x=0$ and that $LaTeX: \mathbf v_j^\top \mathbf v_i=0$ except when i=j. What does that tell you about the multiplier $LaTeX: \alpha_j$ ?
  ANSWER: We get $LaTeX: 2\mathbf x^\top\!\mathbf A \mathbf v_j =2\lambda\mathbf x^\top \mathbf v_j + \alpha_j||\mathbf v_j||^2+0$ . The $LaTeX: \mathbf x^\top \mathbf v_j$ term is zero, and since $LaTeX: \mathbf x^\top\!\mathbf A \mathbf v_j =\mathbf x^\top\lambda_j \mathbf v_j$ for some eigenvalue, the left-hand side is also zero. So $LaTeX: \alpha_j$ is zero.
  Therefore, the Lagrange FOC reduces to $LaTeX: \mathbf x^\top\!\mathbf A =\lambda\mathbf x^\top$ meaning that an x must be an eigenvector to be optimal - and we know that the optimum exists, by the extreme value theorem.
- So that if there are k<n orthogonal eigenvectors, we have just found more; there must be more than k orthogonal eigenvectors. What does that tell you?
  ANSWER: The maximum number of orthogonal eigenvectors, cannot be <n. Therefore it must be n, as there cannot be more than n orthogonal (nonzero!) vectors in $LaTeX: \mathbb R^n.$
  [Is the latter obvious? There cannot be more than n linearly independent vectors, and orthogonality is stronger: If $LaTeX: c_1\mathbf v_1+\dots+c_n\mathbf v_n=0$ for orthogonal nonzero vectors, then dot with $LaTeX: \mathbf v_j$ and get that . This is true for all j, so all the coefficients are zero, proving linear independence.]