If a matrix is triangular, is there a quicker way to tell if it is can be diagonalized?
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.
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.
There is an easy necessary and sufficient condition. Let $c_1,\ldots,c_k$ be the distinct diagonal entries of the triangular matrix $A$ (so if there are repeated values, list each one just once). Then $A$ is diagonalisable if and only if $(X-c_1)\ldots(X-c_k)$ is an annihilating polynomial for$~A$ (in which case it will in fact be the minimal polynomial), in other words if the matrix product $(A-c_1I)\ldots(A-c_kI)$ is the zero matrix.
Proof. If $A$ is diagonalisable, then its minimal polynomial is $(X-\lambda_1)\ldots(X-\lambda_k)$ where $\lambda_i$ runs through the distinct eigenvalues of $A$, and for a triangular matrix the set of eigenvalues equals the set of diagonal entries (by an easy calculation of the characteristic polynomial). Conversely, since $(X-c_1)\ldots(X-c_k)$ has simple roots by construction, if it is an annihilating polynomial for$~A$, then $A$ is diagonalisable.
For instance, for the matrix $$ A = \pmatrix {1 & a & b \\ 0 & 2 & c \\ 0 & 0 & 1 } $$ mentioned in other answers, compute $$ (A-I)(A-2I) = \pmatrix {0 & a & b \\ 0 & 1 & c \\ 0 & 0 & 0 } \pmatrix {-1 & a & b \\ 0 & 0 & c \\ 0 & 0 & -1 } = \pmatrix {0 & 0 & ac-b \\ 0 & 0 & 0 \\ 0 & 0 & 0 }, $$ and conclude that $A$ is diagonalisable iff $ac-b=0$.
In the special case that equal entries are always consecutive on the diagonal, then the given condition easily reduces to the condition that for each such sequence of equal diagonal entries, they form the diagonal of a scalar (i.e., multiple of the identity) diagonal submatrix, in other words that the above-diagonal entries in the block "spanned" by those equal diagonal entries are all zero. This is necessary because if the diagonal entry in question is $c_i$, then the corresponding diagonal submatrix of the product $(A-c_1I)\ldots(A-c_kI)$ will only be zero if the submatrix from the factor $A-c_iI$ is already zero: the other factors have an invertible (triangular) submatrix at that location. It is sufficient by a computation of the product $(A-c_1I)\ldots(A-c_kI)$, where the $c_i$ are ordered by their occurrenc on the diagonal of $A$, as block matrices (subdivided in the obvious way according to groups of equal diagonal entries): by induction on$~i$, the product of the first $i$ factors has its first $i$ "block columns" entirely zero, so ($i=k$) the whole product is zero.
The case where all diagonal entries are distinct is a special case of this special case, and since the diagonal blocks now are $1\times1$ in size (without above-diagonal entries), the matrix will always be diagonalisable.