Proof of Schur's Triangularization Theorem

The Goal: Upper Triangular Form by an Orthonormal Change of Basis

Schur’s triangularization theorem says that a complex square matrix can be made upper triangular by changing to a suitable orthonormal basis. The orthonormal requirement matters: the change of basis is unitary, so it preserves lengths and inner products. The proof builds that basis one vector at a time. First choose an eigenvector; then arrange the remaining basis vectors so that the matrix left over on their coordinates can be handled by induction.

For a complex matrix \(\mathbf{A}\), its conjugate transpose is \(\mathbf{A}^{*}\). A square matrix \(\mathbf{U}\) is unitary if \(\mathbf{U}^{*}\mathbf{U}=\mathbf{U}\mathbf{U}^{*}=\mathbf{I}\). Its columns are then an orthonormal basis of \(\mathbb{C}^n\). In that basis the matrix of the same linear map is \(\mathbf{U}^{*}\mathbf{A}\mathbf{U}\). A matrix is upper triangular if all entries below its main diagonal are zero.

The theorem is about complex matrices; its proof uses the fact that every complex square matrix has an eigenvalue. Indeed, its characteristic polynomial has a complex root by the Fundamental Theorem of Algebra. The proof of that theorem belongs to complex analysis. Once an eigenvalue \(\lambda\) is available, \(\det(\mathbf{A}-\lambda\mathbf{I})=0\) implies that \(\mathbf{A}-\lambda\mathbf{I}\) has a nonzero vector in its null space, which is an eigenvector.

Preparing an Orthonormal Basis

The first step is to make the eigenvector the first vector of an orthonormal basis. The following basis-extension fact explains why this can always be done.

Proof. Begin with the linearly independent list consisting of \(\mathbf{q}_1\). Consider the standard basis vectors in order, adding a vector whenever it is not in the span of the vectors already selected. The resulting list is linearly independent and spans \(\mathbb{C}^n\), because it contains enough of the standard basis vectors to span that space. Apply Gram–Schmidt while keeping \(\mathbf{q}_1\) as the first vector. At each later stage, subtract from the next selected vector its projections onto the orthonormal vectors already constructed. The remainder is orthogonal to those vectors. It is nonzero: if it were zero, the selected vector would belong to the span of the earlier ones, contradicting the independence of the selected list. Normalize each remainder. The result is an orthonormal basis beginning with \(\mathbf{q}_1\). \(\square\)

Here the projection coefficient for a unit vector \(\mathbf{q}_j\) and a vector \(\mathbf{v}\) is \(\mathbf{q}_j^{*}\mathbf{v}\); the vector left after subtracting the projections is \(\mathbf{v}-\sum_j(\mathbf{q}_j^{*}\mathbf{v})\mathbf{q}_j\). This formula matches the inner-product convention that the inner product is linear in its first slot.

The Induction: Isolate the Complementary Block

Suppose \(\mathbf{A}\mathbf{q}_1=\lambda\mathbf{q}_1\), where \(\mathbf{q}_1\) is a unit eigenvector. Extend it to an orthonormal basis, and let \(\mathbf{Q}_0\) be the matrix whose columns are that basis. Because those columns are an orthonormal basis, \(\mathbf{Q}_0\) is unitary. In this basis the first column of \(\mathbf{Q}_0^{*}\mathbf{A}\mathbf{Q}_0\) has \(\lambda\) at the top and zero entries underneath: applying \(\mathbf{A}\) to the first basis vector gives \(\lambda\mathbf{q}_1\). Consequently the matrix has block form

where \(\mathbf{r}\) is a row and \(\mathbf{B}\in\mathbb{C}^{(n-1)\times(n-1)}\). No special property of \(\mathbf{B}\) has been assumed. The induction hypothesis says that \(\mathbf{B}\) can itself be made upper triangular by a unitary change of basis.

Proof of Schur’s Triangularization Theorem. We use induction on \(n\). If \(n=1\), the matrix is already upper triangular. Now let \(n\geq2\) and assume the theorem holds for all complex \((n-1)\times(n-1)\) matrices. Choose an eigenvalue \(\lambda\) of \(\mathbf{A}\) and a corresponding unit eigenvector \(\mathbf{q}_1\). Such an eigenvalue and nonzero eigenvector exist by the characteristic-polynomial argument above; a nonzero eigenvector can be normalized by dividing by its norm. Extend \(\mathbf{q}_1\) to an orthonormal basis and form \(\mathbf{Q}_0\). As shown, \(\mathbf{Q}_0^{*}\mathbf{A}\mathbf{Q}_0\) has the block form displayed above. By the induction hypothesis, there is a unitary \(\mathbf{S}\in\mathbb{C}^{(n-1)\times(n-1)}\) such that \(\mathbf{S}^{*}\mathbf{B}\mathbf{S}\) is upper triangular. Set \(\mathbf{D}=\begin{bmatrix}1&\mathbf{0}\\\mathbf{0}&\mathbf{S}\end{bmatrix}\), which is unitary, and \(\mathbf{U}=\mathbf{Q}_0\mathbf{D}\), which is also unitary because \(\mathbf{U}^{*}\mathbf{U}=\mathbf{D}^{*}\mathbf{Q}_0^{*}\mathbf{Q}_0\mathbf{D}=\mathbf{D}^{*}\mathbf{D}=\mathbf{I}\). Then

The bottom-left block is zero, and the bottom-right block is upper triangular. The first row may contain arbitrary entries, which are allowed above the diagonal. Therefore the whole matrix is upper triangular. This proves the induction step and the theorem for every \(n\geq1\). \(\square\)

The induction does not require \(\mathbf{A}\) to be normal, self-adjoint, or invertible. The only eigenvalue input is over \(\mathbb{C}\); the remaining argument is an orthonormal basis construction and block multiplication. At each stage, the selected eigenvector accounts for one diagonal entry, while the complementary block is a smaller complex square matrix to which the same theorem applies.

Worked Changes of Basis

Common Pitfall: An Arbitrary Similarity Is Not Unitary

A general change of basis can also produce an upper triangular matrix, but it does not establish Schur’s theorem unless the change of basis is unitary. For the first example, take the eigenvector \(\frac{1}{\sqrt{2}}\begin{bmatrix}1\\1\end{bmatrix}\) and append \(\begin{bmatrix}0\\1\end{bmatrix}\). The resulting matrix \(\mathbf{P}=\begin{bmatrix}1/\sqrt{2}&0\\1/\sqrt{2}&1\end{bmatrix}\) is not unitary: its columns have inner product \(1/\sqrt{2}\ne0\). Treating \(\mathbf{P}^{*}\) as if it were \(\mathbf{P}^{-1}\) gives the incorrect change-of-basis calculation

which is not upper triangular. The correction is to complete the eigenvector with an orthogonal unit vector, as in the first worked example, and use \(\mathbf{Q}^{*}=\mathbf{Q}^{-1}\). More generally, for a nonunitary basis matrix the change-of-basis formula uses \(\mathbf{P}^{-1}\mathbf{A}\mathbf{P}\), not \(\mathbf{P}^{*}\mathbf{A}\mathbf{P}\). Schur’s theorem promises the stronger, specifically unitary, form.

Why the Block Argument Is Useful

The proof gives more than an existence statement: it identifies the structure that makes the induction work. An eigenvector produces a first column with zeros below its diagonal entry. The remaining coordinates form a smaller square block, and a unitary basis change confined to those coordinates leaves the first column fixed. This is why the block matrix \(\begin{bmatrix}1&\mathbf{0}\\\mathbf{0}&\mathbf{S}\end{bmatrix}\) is used: it transforms the complementary block without disturbing the eigenvector already selected.

When checking a proposed Schur form, verify both parts of the claim: the basis matrix is unitary, and the conjugated matrix is upper triangular. A triangular-looking result alone does not verify that the change of basis preserved the inner product. Conversely, the product \(\mathbf{U}^{*}\mathbf{A}\mathbf{U}\) is the correct expression precisely because unitarity gives \(\mathbf{U}^{-1}=\mathbf{U}^{*}\).