# Taking powers of a triangular matrix?

So there is a formula for the $n$th power of a matrix in Jordan normal form. Is there a formula for the $n$th power of a general triangular matrix? If not, are there known formulas for "nice" upper triangular matrices? Like those consisting of all 1s and 0s.

-
For an upper triangular matrix that can be written as $D + N$ where $D$ is diagonal and $N$ is strictly upper-triangular (hence nilpotent) and such that $D$ and $N$ commute (in particular if $D$ is scalar), it is very easy to compute the powers explicitly in terms of the powers of $D$ and $N$. In general I think you should just find the Jordan normal form or use special structure of the matrix in question. – Qiaochu Yuan Oct 5 '11 at 1:07
Well, the diagonal elements are easy, and there's a neat formula for the superdiagonal entries, involving sums of the form $\sum\limits_{k=0}^{n-1} x^k y^{n-k-1}$... – J. M. Oct 5 '11 at 1:09

If $A$ is an $n \times n$ upper triangular matrix, $m$ is a positive integer and $i \le j$, $(A^m)_{ij} = \sum \prod_{k=1}^m A_{i_{k-1} i_k}$ where the sum is over all nondecreasing $m+1$-tuples
$i = i_0 \le i_1 \le \ldots \le i_m = j$ starting at $i$ and ending at $j$. In particular, if $A$ consists only of 1's and 0's, $(A^m)_{ij}$ is the number of $m$-step paths from $i$ to $j$ in the directed graph with adjacency matrix $A$.