Triangularizing Complex Matrices

What Triangularization Asks For

A complex square matrix need not already be upper triangular, and it need not be diagonalizable. Triangularization asks for a basis in which its matrix has zeros below the main diagonal. The key idea is to choose an eigenvector as the first basis vector: that makes the first column simple, leaving a smaller square matrix to handle by induction.

Throughout, matrices act on column vectors in \(\mathbb{C}^n\). An eigenvalue of \(\mathbf{A}\in\mathbb{C}^{n\times n}\) is a scalar \(\lambda\in\mathbb{C}\) for which there is a nonzero vector \(\mathbf{v}\) satisfying \(\mathbf{A}\mathbf{v}=\lambda\mathbf{v}\). A matrix \(\mathbf{U}\) is upper triangular if \(u_{ij}=0\) whenever \(i>j\). Two square matrices \(\mathbf{A}\) and \(\mathbf{U}\) are similar if \(\mathbf{U}=\mathbf{P}^{-1}\mathbf{A}\mathbf{P}\) for some invertible matrix \(\mathbf{P}\) of the same size. The columns of \(\mathbf{P}\) are the basis vectors used to represent \(\mathbf{A}\) in the new basis.

Why a Complex Matrix Has an Eigenvector

The induction needs an eigenvector at every positive dimension. This is where the scalar field matters. The Fundamental Theorem of Algebra states that every nonconstant polynomial with complex coefficients has a complex root. For a square matrix, the relevant polynomial is its characteristic polynomial \(p_{\mathbf{A}}(\lambda)=\det(\mathbf{A}-\lambda\mathbf{I}_n)\).

Proof. The determinant expansion shows that \(p_{\mathbf{A}}(\lambda)\) is a polynomial of degree \(n\) with leading coefficient \((-1)^n\). In particular, it is nonconstant. By the Fundamental Theorem of Algebra, there is a \(\lambda\in\mathbb{C}\) such that \(p_{\mathbf{A}}(\lambda)=0\). By the determinant criterion for a square matrix, \(\det(\mathbf{A}-\lambda\mathbf{I}_n)=0\) means that \(\mathbf{A}-\lambda\mathbf{I}_n\) has a nonzero vector \(\mathbf{v}\) in its null space. Thus \((\mathbf{A}-\lambda\mathbf{I}_n)\mathbf{v}=\mathbf{0}\), or \(\mathbf{A}\mathbf{v}=\lambda\mathbf{v}\), as required. \(\square\)

The lemma supplies a first eigenvector, but it does not by itself triangularize the whole matrix. The remaining step is to arrange a basis so that the part not yet handled is an \((n-1)\times(n-1)\) matrix. Once that block is triangularized, its change of basis must be applied without disturbing the first eigenvector.

The Induction Argument

Proof. We use induction on \(n\). If \(n=1\), then \(\mathbf{A}\) already has one entry and is upper triangular. Now let \(n\ge2\), and assume the theorem holds for matrices of size \((n-1)\times(n-1)\).

By the lemma, choose an eigenvalue \(\lambda\) and a corresponding nonzero eigenvector \(\mathbf{v}_1\). Extend \(\mathbf{v}_1\) to a basis \((\mathbf{v}_1,\dots,\mathbf{v}_n)\) of \(\mathbb{C}^n\), and let \(\mathbf{Q}\) be the matrix with these basis vectors as columns. Such an extension can be made by appending standard basis vectors not already in the current span until the list spans \(\mathbb{C}^n\). Since the columns of \(\mathbf{Q}\) form a basis, \(\mathbf{Q}\) is invertible.

In this basis, the first column of \(\mathbf{Q}^{-1}\mathbf{A}\mathbf{Q}\) is \(\lambda\mathbf{e}_1\): indeed, \(\mathbf{A}\mathbf{v}_1=\lambda\mathbf{v}_1\), whose coordinate vector in this basis is \((\lambda,0,\dots,0)^\top\). Therefore, for some row \(\mathbf{r}\) and some \(\mathbf{B}\in\mathbb{C}^{(n-1)\times(n-1)}\), the matrix has block form

By the induction hypothesis, there is an invertible \(\mathbf{S}\in\mathbb{C}^{(n-1)\times(n-1)}\) such that \(\mathbf{S}^{-1}\mathbf{B}\mathbf{S}=\mathbf{U}\), where \(\mathbf{U}\) is upper triangular. Set \(\mathbf{D}=\begin{bmatrix}1&\mathbf{0}\\ \mathbf{0}&\mathbf{S}\end{bmatrix}\), which is invertible with \(\mathbf{D}^{-1}=\begin{bmatrix}1&\mathbf{0}\\ \mathbf{0}&\mathbf{S}^{-1}\end{bmatrix}\). Block multiplication gives

This last matrix is upper triangular: its lower-left block is zero, its first diagonal block is the scalar \(\lambda\), and its lower-right block \(\mathbf{U}\) is upper triangular. Finally, set \(\mathbf{P}=\mathbf{Q}\mathbf{D}\), which is invertible as a product of invertible matrices. Then

which is upper triangular. This proves the induction step and therefore the theorem for every \(n\ge1\). \(\square\)

The upper-right row changes from \(\mathbf{r}\) to \(\mathbf{r}\mathbf{S}\). This is necessary: changing the basis in the lower-dimensional block changes how the first row acts on that block. The zero lower-left block remains zero, which is why the resulting matrix stays upper triangular.

Worked Constructions

Why the Scalar Field Matters

The theorem is stated over \(\mathbb{C}\) because the eigenvector step is guaranteed by the Fundamental Theorem of Algebra. Over \(\mathbb{R}\), an eigenvalue need not exist. For instance, the real matrix \(\begin{bmatrix}0&-1\\1&0\end{bmatrix}\) has characteristic polynomial \(\lambda^2+1\), which has no real root. The induction cannot begin with a real eigenvector in that case. Considering the same matrix over \(\mathbb{C}\) supplies eigenvalues \(i\) and \(-i\), so the complex theorem applies.

Triangularization is also weaker than diagonalization: upper-triangular entries above the diagonal may remain nonzero. In the induction proof, the only task for the smaller block is to become upper triangular; there is no requirement that it become diagonal. The diagonal entries of the final matrix are complex numbers, but this proof does not yet establish any further formula about them.

Common Pitfall: Forgetting to Transform the Upper-Right Block

When changing the basis in the lower-right block, it is incorrect to replace \(\mathbf{B}\) by \(\mathbf{S}^{-1}\mathbf{B}\mathbf{S}\) while leaving the upper-right row \(\mathbf{r}\) unchanged. The full block multiplication gives \(\mathbf{r}\mathbf{S}\), not \(\mathbf{r}\). In the 3×3 example, the original upper-right row is \((1,0)\), and the lower-block change of basis is \(\mathbf{S}=\begin{bmatrix}1&1\\i&-i\end{bmatrix}\). The correct row is

If one incorrectly keeps \((1,0)\), the proposed triangular matrix would have first row \((2,1,0)\). Multiplying that incorrect matrix by \(\mathbf{P}\) gives first row \((2,1,0)\), whereas the first row of \(\mathbf{A}\mathbf{P}\) is \((2,1,1)\). Thus \(\mathbf{A}\mathbf{P}\ne\mathbf{P}\mathbf{T}\), exposing the error. The reliable check is to multiply the proposed matrices and verify \(\mathbf{A}\mathbf{P}=\mathbf{P}\mathbf{T}\).