Let \(A\) be an \(n\times n\) complex matrix. Prove that there exists a unitary matrix \(U\) such that \[ B=UAU^{-1} \] is upper triangular.
Solution
We prove the assertion by induction on \(n\).
1. The assertion holds for \(n=1\).
Every \(1\times1\) matrix is already upper triangular, so one may take \(U=(1)\).
2. Suppose \(n>1\). There is a unitary matrix \(Q\) whose first columnis a unit eigenvector of \(A\).
By the fundamental theorem of algebra, the characteristic polynomial of \(A\) has a root \(\lambda\in\CC\). Choose a nonzero vector \(v_1\) with \[ Av_1=\lambda v_1 \] and normalize it so that \(\norm{v_1}=1\). Extend \(v_1\) to an orthonormal basis \[ v_1,v_2,\ldots,v_n \] of \(\CC^n\), and let \(Q\) be the matrix with these vectors as its columns. Then \(Q\) is unitary.
3. Relative to this basis,\[ Q^*AQ = \begin{pmatrix} \lambda&r\\ 0&C \end{pmatrix} \]for some row \(r\) and some \((n-1)\times(n-1)\) complex matrix \(C\).
2. Since\(Av_1=\lambda v_1\), that column is\[ \begin{pmatrix} \lambda\\ 0\\ \vdots\\ 0 \end{pmatrix}. \]The remaining entries form the indicated row block \(r\) and squareblock \(C\).
4. There is a unitary \((n-1)\times(n-1)\) matrix \(W\) such that\[ WCW^{-1} \]is upper triangular.
This is the induction hypothesis applied to the complex matrix \(C\).
5. Set\[ V= \begin{pmatrix} 1&0\\ 0&W \end{pmatrix}, \qquad U=VQ^*. \]Then \(U\) is unitary and \(UAU^{-1}\) is upper triangular.
Both \(V\) and \(Q^*\) are unitary, hence so is their product \(U\). Using step 3, \[ UAU^{-1} = V(Q^*AQ)V^{-1} = \begin{pmatrix} \lambda&rW^{-1}\\ 0&WCW^{-1} \end{pmatrix}. \] By step 4, the lower-right block is upper triangular. Therefore the whole matrix is upper triangular.
6. Q.E.D.
Step 1 is the base case, and steps 2 through 5 prove the induction step. Hence the assertion holds for every \(n\geq1\).