# 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.

• Quicker than what? What is your current way? – 5xum Dec 3 '15 at 19:34
• You are in part asking for clarification of what "my book" says. It might be helpful for you to give a citation of the book, at least the title and author. – hardmath Dec 7 '15 at 17:36
• One way would just be to notice that the Laplace Expansion of any triangular matrix always gives a polynomial with elements that are only those of the principal diagonal, no matter whether the matrix is upper triangular or lower triangular. – Morgormir Feb 15 '16 at 12:58
• The currently accepted answer only deals with a very special case, and it is of very little help for the more general (triangular) case. – Marc van Leeuwen Feb 15 '16 at 13:21

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.

• Distinct meaning they are all different (eigenvalues), or that they have 1 and only 1 eigenvector basis for each eigenvalue? – Jane Doe Dec 3 '15 at 19:36
• @BNSlug: Distinct, as different. If, then. It's a sufficient condition. Thus, if all the diagonal elements of a triangular matrix are pairwise different, then the matrix can be diagonalized. – Orest Bucicovschi Dec 3 '15 at 19:39
• Alright, thanks, and this only works for upper triangular? Why is that, isn't the upper just the transpose of the lower, and doing that shouldn't change the diagonal elements. – Jane Doe Dec 3 '15 at 19:42
• @BNSlug: Ah, it works also for lower, sorry, now I get it. – Orest Bucicovschi Dec 3 '15 at 19:58
• @BNSlug: Not diagonaliz since the sum of all the geometric multiplicities should also be $9$. but it's $8$ in fact ( equivalently: the algebraic mult should be the geom mult .... in general it's just $\ge$. ) – Orest Bucicovschi Dec 3 '15 at 20:36

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

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.

• @ hardmath , about the fist part, when you change the ordering of the diagonal, using a permutation of the vectors of the basis, the matrix is no longer triangular ( see the image of the last vector of the basis) Possibly, it does not matter. About the second part, I think that the result is true; yet, a priori, the proof is not obvious... – loup blanc Dec 4 '15 at 9:59
• @loupblanc: Thanks. If the row and column permutations are performed on adjacent pairs of rows/columns, then triangularity is preserved and the diagonal entries may be sorted by this procedure (transpositions of adjacent entries). I'll edit to make this clear. For "the second part", have you seen the earlier linked answer? If you still have doubts I will add to my answer. – hardmath Dec 4 '15 at 12:34
• By the way this is also true for lower triangular matrices (didn't see this in your answer) – Morgormir Feb 15 '16 at 12:54
• @Morgormir: It is "also true" in the sense that $A$ is diagonalizable if and only if $A^T$ is diagonalizable. So everything done for upper triangular matrices has an immediate application to lower triangular matrices via analyzing the transpose. Just look at the transpose of a similarity transformation, e.g. $(P A P^{-1})^T = P^{-T} A^T P^T$. – hardmath Feb 15 '16 at 13:05
• There is no need at all for all this complexity; see the answer I just posted. – Marc van Leeuwen Feb 15 '16 at 13:15

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.

• @ Marc van Leeuwen , I just read your answer. Of course, you are right; yet, that I find interesting, about this question, is the complexity of the eventual solutions. In particular, note that, if all the eigenvalues are double, then the complexity of your solution is a priori $O(n^4)$. Can we prove that no solution has a $o(n^3)$ complexity ? – loup blanc Mar 23 '16 at 13:10

You can compute more quickly its characteristic polynomial, so its minimal polynomial and conclude. But note that $A=\begin{pmatrix}1&1\\0&1\end{pmatrix}$ is triangular but not diagonalisable whereas $B=\begin{pmatrix}1&1\\0&2\end{pmatrix}$ is triangular and diagonalisable, so in all thes cases you will have a little study to do.

• However here the requirements for the theorem are not respected, i.e. distinct values along the main diagonal – Morgormir Feb 15 '16 at 12:53

@ hardmath ,for the point 1, how do you do with the matrix $\begin{pmatrix}1&a&b\\0&2&c\\0&0&1\end{pmatrix}$?

For point 2, I saw your link; it contains only straightforward posts. Here we need a proof as follows: let $A=\begin{pmatrix}P_p&Q&R\\0&J_q&S\\0&0&T_r\end{pmatrix}$ where $P,J,T$ are triangular matrices s.t. $J-I_q$ is nilpotent and $P-I_p,T-I_r$ are invertible. If $[x,y,z]^T\in\ker(A-I_n)$ then $Px+Qy+Rz=x,Jy+Sz=y,Tz=z$; then $z=0,(J-I_q)y=0,x=(P-I_p)^{-1}Qy$. Finally $dim(\ker(A-I_n))=dim(\ker(J-I_q))$ and we are done.

EDIT 1. We can do the same reasoning with $((A-I)^2,(J-I)^2),((A-I)^3,(J-I)^3),\cdots$. Assume that $P,T$ each has a sole eigenvalue $\lambda,\mu$ s.t. $\lambda,\mu,1$ are distinct; according to the Jordan theory, $A$ is similar to $diag(P,J,T)$.

EDIT 2. @ hardmath , I was reading you. On the second point, we agree. By contrast, I cannot write a simple procedure to solve the first point. For instance let $A$ be a triangular $5\times 5$ matrix with diagonal $[1,0,1,0,1]$; if we use the transposition $(2,5)$, then we obtain the matrix $B=\begin{pmatrix}1&a_{1,5}&a_{1,3}&a_{1,4}&a_{1,2}\\0&1&0&0&0\\0&a_{3,5}&1&a_{3,4}&0\\0&a_{4,5}&0&0&0\\0&a_{2,5}&a_{2,3}&a_{2,4}&0\end{pmatrix}$; there are $5$ non-zero elements above the diagonal and the same number below. Moreover the $3$ conditions which express the diagonalizability, with respect to the eigenvalue $1$, link all these $10$ entries of $A$...

Let $\lambda_1,\cdots,\lambda_k$ be the distinct eigenvalues of the $n\times n$ matrix $A$. Considering $A$, before or after the permutation, we can calculate the $rank(A-\lambda_jI)$, $j=1,\cdots,k$; each calculation is in $O(n^2)$; thus if $k\approx n/3$ (for example), then the total complexity is in $O(n^3)$, that is not interesting. I think that we can do the job in $O(n^2)$. How to prove that ?

• I take your points and will respond to them with further edits in my answer. – hardmath Dec 4 '15 at 19:10
• I think I've given made my answer sufficiently detailed to respond to your points. Please let me know if anything remains in need of clarification. – hardmath Dec 7 '15 at 17:31
• My sketch of the transpositions deals with the swapping of two adjacent diagonal entries. So if it is desired to swap positions $2$ and $5$, I would do it in stages. Each adjacent swap is $O(n)$ effort. Sorting all the diagonal entries is overkill as we only need contiguity of equal entries. I'm thinking about posting a question about minimizing the number of swaps needed. – hardmath Dec 8 '15 at 15:02
• @ hardmath , yes the complexity of the calculation associated to an adjacent swap is $O(n)$. Unfortunately, if the diagonal of $A$ has the form $[1,0,1,0,\cdots,1,0,1,0]$, then we need $\approx n^2/8$ adjacent swaps. – loup blanc Dec 8 '15 at 19:45