6

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.

Xavier
  • 99
  • 1
    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 05 '11 at 01: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. ain't a mathematician Oct 05 '11 at 01:09

1 Answers1

8

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

Robert Israel
  • 448,999
  • Can you provide an example with a small matrix please? Thanks – Ajned Sep 02 '21 at 13:17
  • 1
    For example, $$A = \pmatrix{0 & 1 & 1\cr 0 & 0 & 1\cr 0 & 0 & 0\cr}$$ is the adjacency matrix of the directed graph with vertices $1,2,3$ and arcs $1 \to 2$, $1 \to 3$ and $2 \to 3$. $$A^2 = \pmatrix{0 & 0 & 1\cr 0 & 0 & 0\cr 0 & 0 & 0}$$ because there is one $2$-step path $1 \to 2 \to 3$ from $1$ to $3$ and no other $2$-step paths. – Robert Israel Sep 03 '21 at 02:17