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.
 A: 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.
A: 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: 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. 
A: 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.
A: @ 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 ?
