Orthonormal Basis Question: Linear Algebra

Question

I've been staring at this proof for a long time so any suggestions would be of great help! Prove that for any $m\times n$ matrix $A$ there is an orthonormal Basis $B =\{ v_1,\ldots,v_n\}$ of $\mathbb R^n$ such that the vectors $A v_1,\ldots,A v_n$ are orthogonal. Note that some of the vectors $A v_i$ may be zero.

Answer 1

Here's a suggestion: Suppose you found those vectors. Then one must have $Av_j \cdot Av_1 = 0$ for all $j = 2, \ldots, n$. That can also be written as $v_j \cdot A^TAv_1=0$ for all $j = 2, \ldots, n$. Since $A^TAv_1$ must be orthogonal to all the other vectors in the basis, it follows that $A^TAv_1$ must be a multiple of $v_1$ (possibly 0). That makes $v_1$ an eigenvector of $A^TA$. Same with the other vectors $v_2, \ldots, v_n$.

Now use the fact that $A^TA$ is a symmetric matrix to conclude that it has an orthonormal eigenbasis.

(The argument above is used in finding the Singular Value Decomposition of $A$)

Answer 2

We know that $A^tA$ is symmetric (you can easily verify this.)

Then $A^tA$ must be orthogonally diagonalizable, i.e., there is an orthonormal basis $B = \{v_1, ..., v_n\}$ of $\mathbb R^n$ that consists of normalized, pairwise-orthogonal, eigenvectors of $A^tA$, by the Spectral Theorem.

Now we return to the action of $A$ and see that, for any $i,j$, the inner product is:

\begin{align*} \langle A v_i ,A v_j \rangle &= \langle A^tA v_i, v_j \rangle \\ &= \langle \lambda_i v_i, v_j \rangle\\ &= \lambda_i \langle v_i, v_j \rangle \\ &=\lambda_i \cdot 0 \\ &= 0 \end{align*}

which proves the result.