If a matrix is triangular, is there a quicker way to tell if it is can be diagonalized?

I hope it is alright to ask something like this here, I am having trouble keeping up with all the special cases and my book is being kind of vague.

I know how to do the standard method of finding diagonal matrices, but I know that triangular matrices are special and my book makes a connection, but it is hard to tell what it is.

Thanks.

Solution 1:

For these two cases the diagonalizability of upper triangle matrix $A$ can be recognized "by inspection":

• If all diagonal entries are distinct, $A$ is diagonalizable.
• If all diagonal entries are equal, $A$ is diagonalizable only if $A$ itself is diagonal, as shown in Diagonalizable properties of triangular matrix.

The bulk of this post will address intermediate cases, where some but not all diagonal entries are equal. Diagonal values $d_i = A_{i,i}$ appearing more than once will be said to be repeated.

Suppose that repeated diagonal entries appear only in contiguous blocks, i.e. if $d_i = d_j$, then also $d_m = d_j$ for all indices $m$ between $i$ and $j$.

Then $A$ is diagonalizable if and only if each square block corresponding to a repeated diagonal entry is a diagonal matrix. That is, if $\lambda = d_i = \ldots = d_{i+k-1}$ is repeated $k$ times, the corresponding diagonal submatrix is $k\times k$ matrix $\lambda I$.

A formal proof of this easily visualized criterion is given at the end of the answer.

What about cases where the repeated diagonal entries are not known to appear in contiguous blocks? It is possible to "sort" the diagonal entries so that the repeated values are grouped together by applying a sequence of similarity transformations that preserve upper triangularity as well as the multiplicities (both algebraic and geometric) of the eigenvalues.

An outline of such a similarity transformation sequence is given in the following Example. The computational complexity is $O(n)$ for each swap that is performed.

Example (suggested by loupblanc)

Consider the $3\times 3$ matrix whose repeated diagonal entries are not contiguous:

$$ A = \begin{bmatrix} 1 & a & b \\ 0 & 2 & c \\ 0 & 0 & 1 \end{bmatrix} $$

To test the diagonalizability of the matrix, we check if the algebraic and geometric multiplicities of all eigenvalues agree. This is necessary and sufficient for existence of a complete basis of eigenvectors, hence for diagonalizability.

The algebraic multiplicity of an eigenvalue here is the number of times it appears on the diagonal. The geometric multiplicity is always at least one. Values appearing only once do not need further checking, as the multiplicities are both one.

In the example at hand, we are thus concerned only with eigenvalue $\lambda = 1$ and its geometric multiplicity. This is the nullity of $A-\lambda I$:

$$ A - \lambda I = \begin{bmatrix} 0 & a & b \\ 0 & 1 & c \\ 0 & 0 & 0 \end{bmatrix} $$

Because this is already upper triangular, we are close to its row echelon form:

$$ \begin{bmatrix} 0 & 1 & c \\ 0 & 0 & b-ac \\ 0 & 0 & 0 \end{bmatrix} $$

Thus the matrix $A - \lambda I$ has rank one if and only if $b-ac = 0$, so that the algebraic multiplicity of $\lambda = 1$ (two) agrees with the geometric multiplicity (nullity $ = 3 -$ rank) if and only if $b-ac$ is zero.

We next show that the same conclusion can be reached by rearranging the diagonal entries into contiguous blocks. Begin by swapping the last two rows and last two columns of $A$:

$$ PAP^{-1} = \begin{bmatrix} 1 & b & a \\ 0 & 1 & 0 \\ 0 & c & 2 \end{bmatrix}$$

This creates a subdiagonal entry, but the $2\times 2$ block involved is similar to its transpose, which we can show explicitly provided the diagonal entries there are distinct and the off-diagonal entry is nonzero:

$$ \begin{bmatrix} 1 & \frac{w}{u-v} \\ \frac{w}{u-v} & 0 \end{bmatrix} \begin{bmatrix} u & w \\ 0 & v \end{bmatrix} = \begin{bmatrix} u & 0 \\ w & v \end{bmatrix} \begin{bmatrix} 1 & \frac{w}{u-v} \\ \frac{w}{u-v} & 0 \end{bmatrix} $$

Setting $u=1,v=2,w=c$ and taking:

$$ S = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & \frac{w}{u-v} \\ 0 & \frac{w}{u-v} & 0 \end{bmatrix}\; , S^{-1} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & \frac{u-v}{w} \\ 0 & \frac{u-v}{w} & -\left( \frac{u-v}{w} \right)^2 \end{bmatrix} $$

we then have a similarity transformation $S^{-1} P A P^{-1} S$ that sorts the diagonal entries of $A$:

$$ S^{-1} P A P^{-1} S = \begin{bmatrix} 1 & b-ac & -bc \\ 0 & 1 & c \\ 0 & 0 & 2 \end{bmatrix} $$

Thus we again conclude the matrix $A$ is diagonalizable if and only if $b-ac=0$.

An $n\times n$ matrix $A$ is diagonalizable iff there exists a complete basis of eigenvectors. An equivalent property is that for each eigenvalue $\lambda$ the algebraic and geometric multiplicities agree, so that the geometric multiplicities (dimensions of the eigenspaces for various $\lambda$) add up to $n$, as the algebraic multiplicities must.

The algebraic multiplicity of $\lambda$ is the number of times that eigenvalue appears on the diagonal of an upper triangular matrix. Thus the harder part of checking diagonalizability is computing geometric multiplicity of $\lambda$.

The geometric multiplicity of eigenvalue $\lambda$ is the nullity of $A - \lambda I$, because this is just an abbreviated way of saying the dimension of the eigenspace corresponding to $\lambda$.

We now state and prove a proposition about equality of algebraic and geometric multiplicity of eigenvalues $\lambda$ of an upper triangular matrix $A$.

Prop. Suppose that $n\times n$ upper triangular matrix $A$ has eigenvalue $\lambda$ appearing $k \gt 1$ times in contiguous locations on the diagonal: $$ \lambda = d_i = \ldots = d_{i+k-1} $$ Then the nullity of $A - \lambda I$ is $k$ if and only if the super-diagonal entries $A_{j,m}$ are zero for all: $$ i \le j \lt m \le i+k-1 $$

The nullity of $A - \lambda I$ is the difference $n - \operatorname{rank}(A-\lambda I)$, so it suffices compute whether or not $\operatorname{rank}(A-\lambda I)=n-k$.

Since there are $n-k$ nonzero entries on the diagonal of $A-\lambda I$, and these will give rise to leading ones in the row-echelon form of $A-\lambda I$, the rank of $A-\lambda I$ is at least $n-k$.

The super-diagonal entries of $A-\lambda I$ are zero in exactly the same locations as the super-diagonal entries of $A$. So in the case that the $k\times k$ block corresponding to repeated diagonal value $\lambda$ has all super-diagonal entries equal zero, the only leading ones in the row echelon form of $A-\lambda I$ correspond to the $n-k$ nonzero diagonal entries noted above.

On the other hand if any super-diagonal entries in the $k\times k$ block corresponding to repeated diagonal value $\lambda$ are nonzero, it implies at least one additional leading one will appear in a row between $i$ and $i+k-1$ of the row-echelon form of $A - \lambda I$.

Therefore the rank of $A - \lambda I$ is $n-k$ if and only if all the super-diagonal entries of the $k\times k$ block corresponding to repeated diagonal entry $\lambda$ are zero. Thus the proposition is established.

Cor. The algebraic and geometric multiplicities of all eigenvalues of $A$ agree if and only if the condition described in the Proposition holds for each eigenvalue $\lambda$ of $A$. If this is true $A$ is diagonalizable, and otherwise not.

Note that the condition in the Proposition is vacuously true for any eigenvalue of multiplicity one, since there are no super-diagonal entries to check.

Solution 2:

A quick way: if all the eigenvalues are distinct, then it's diagonalizable. Now, for an upper triangular matrix, the eigenvalues are just the diagonal elements.