Proof of Theorem OBUTR

This theorem is a statement about matrices and similarity. We can convert it to a statement about linear transformations, matrix representations and bases (Theorem SCB). Suppose that $A$ is an $n\times n$ matrix, and define the linear transformation $\ltdefn{S}{\complex{n}}{\complex{n}}$ by $\lt{S}{\vect{x}}=A\vect{x}$. Then Theorem UTMR gives us a basis $B=\set{\vectorlist{v}{n}}$ for $\complex{n}$ such that a matrix representation of $S$ relative to $B$, $\matrixrep{S}{B}{B}$, is upper triangular.

Now convert the basis $B$ into an orthogonal basis, $C$, by an application of the Gram-Schmidt procedure (Theorem GSP). This is a messy business computationally, but here we have an excellent illustration of the power of the Gram-Schmidt procedure. We need only be sure that $B$ is linearly independent and spans $\complex{n}$, and then we know that $C$ is linearly independent, spans $\complex{n}$ and is also an orthogonal set. We will now consider the matrix representation of $S$ relative to $C$ (rather than $B$). Write the new basis as $C=\set{\vectorlist{y}{n}}$. The application of the Gram-Schmidt procedure creates each vector of $C$, say $\vect{y}_j$, as the difference of $\vect{v}_j$ and a linear combination of $\vectorlist{y}{j-1}$. We are not concerned here with the actual values of the scalars in this linear combination, so we will write \begin{align*} \vect{y}_j &=\vect{v}_j-\sum_{k=1}^{j-1}b_{jk}\vect{y}_k \end{align*} where the $b_{jk}$ are shorthand for the scalars. The equation above is in a form useful for creating the basis $C$ from $B$. To better understand the relationship between $B$ and $C$ convert it to read \begin{align*} \vect{v}_j &=\vect{y}_j+\sum_{k=1}^{j-1}b_{jk}\vect{y}_k \end{align*}

In this form, we recognize that the change-of-basis matrix $\cbm{B}{C}=\matrixrep{I_{\complex{n}}}{B}{C}$ (Definition CBM) is an upper triangular matrix. By Theorem SCB we have \begin{align*} \matrixrep{S}{C}{C}&=\cbm{B}{C}\matrixrep{S}{B}{B}\inverse{\cbm{B}{C}} \end{align*} The inverse of an upper triangular matrix is upper triangular (Theorem ITMT), and the product of two upper triangular matrices is again upper triangular (Theorem PTMT). So $\matrixrep{S}{C}{C}$ is an upper triangular matrix.

Now, multiply each vector of $C$ by a nonzero scalar, so that the result has norm 1. In this way we create a new basis $D$ which is an orthonormal set (Definition ONS). Note that the change-of-basis matrix $\cbm{C}{D}$ is a diagonal matrix with nonzero entries equal to the norms of the vectors in $C$.

Now we can convert our results into the language of matrices. Let $E$ be the basis of $\complex{n}$ formed with the standard unit vectors (Definition SUV). Then the matrix representation of $S$ relative to $E$ is simply $A$, $A=\matrixrep{S}{E}{E}$. The change-of-basis matrix $\cbm{D}{E}$ has columns that are simply the vectors in $D$, the orthonormal basis. As such, Theorem CUMOS tells us that $\cbm{D}{E}$ is a unitary matrix, and by Definition UM has an inverse equal to its adjoint. Write $U=\cbm{D}{E}$. We have \begin{align*} \adjoint{U}AU &=\inverse{U}AU&&\knowl{./knowls/theorem.UMI.knowl}{\text{Theorem UMI}}\\ &=\inverse{\cbm{D}{E}}\matrixrep{S}{E}{E}\cbm{D}{E}\\ &=\matrixrep{S}{D}{D}&&\knowl{./knowls/theorem.SCB.knowl}{\text{Theorem SCB}}\\ &=\cbm{C}{D}\matrixrep{S}{C}{C}\inverse{\cbm{C}{D}}&&\knowl{./knowls/theorem.SCB.knowl}{\text{Theorem SCB}} \end{align*}

The inverse of a diagonal matrix is also a diagonal matrix, and so this final expression is the product of three upper triangular matrices, and so is again upper triangular (Theorem PTMT). Thus the desired upper triangular matrix, $T$, is the matrix representation of $S$ relative to the orthonormal basis $D$, $\matrixrep{S}{D}{D}$.