1

I am attempting to write an explicit formula for the individual elements of a matrix that has been exponentiated to the $n$th power. Let $P$ be an $n\times n$ matrix and let $p_{ij}^{(n)}$ be the $(i,j)$th entry of the matrix $P^n$. How can I write out an explicit formula for $p_{ij}^{(n)}$?

I know that $$p_{ij}^{(2)} = \sum_{k=1}^n p_{ik}p_{kj}$$

and I'm fairly sure that

$$p_{ij}^{(3)} = \sum_{r=1}^n p_{rj}\left(\sum_{k=1}^n p_{ik}p_{kj}\right) = \sum_{r=1}^n \sum_{k=1}^np_{rj}p_{ik}p_{kj}$$

But even with this, I'm struggling to generalize for arbitrary $n$. Any help would be appreciated.

BSplitter
  • 1,553
  • Your approach is right. For $n$th power you need $n-1$ intermediate index name as you've done in he third power case with 2 intermediate variables. – coffeemath Jul 30 '18 at 04:01
  • So I can see that I would have $n-1$ summations, but would be the arguments of those summations, exactly? – BSplitter Jul 30 '18 at 04:06
  • Is the matrix diagonizable? –  Jul 30 '18 at 04:25
  • @Geronimo I'm not sure. I believe so, but I'd have to study up on diagonalizability again. The matrices I'm concerned about are irreducible transition matrices used in Markov chains, so each row should sum to one. – BSplitter Jul 30 '18 at 04:34

2 Answers2

1

You have to use more indices to express the entry of $P^n$.

To be more precise for any matrix $P$ with entries $P_{ij}$, the entries of the matrix $P^n$, given by $(P^n)_{ij}$ are given by : $$ (P^n)_{ij} = \sum_{a_1,a_2,...,a_{n-1} = 1}^n P_{ia_1}P_{a_1a_2}\ldots P_{a_{n-2}a_{n-1}}P_{a_{n-1}j} $$

so the number of indices changes with the power. This formula can easily proved by induction, as you saw for the case $n=2$ to $n=3$ by substitution.

Note that the problem of having $n-1$ summations is solved by iterating over a different set that contains all the possible types of indices : this is why we can combine $a_1,...,a_{n-1}$ into one summation.

Furthermore, a very similar formula applies for the product of $n$ matrices in an admissible order (number of columns of left matrix equals number of rows of the right matrix). More precisely , if $A_i$, $i=1,...,n$ are $c_i \times d_i$ matrices such that $c_{i+1} = d_i$ for all $i=1,...,n-1$, then the product $\prod A_i$ will have entries given by a similar summation, which I leave you to figure out, where each $a_i$ in the index set will not vary from $1$ to $n$, but something else. The expression for entries of the power is a special case of this formula, which can also be proved by induction.

Sarvesh Ravichandran Iyer
  • 76,105
0

If your matrix is diagonalizable then we have, $A \in \mathbb{C}^{n \times n} $

$$ A = V \Lambda V^{*}$$

$$ A^{n} = V\Lambda^{n} V^{*} $$

now matrix multiplication is

$$ (AB)_{ik} = \sum_{k=1}^{n} a_{ij}b_{jk} $$ then we have

$$ ((AB)C))_{il} = \sum_{k=1}^{p} \sum_{j=1}^{n} a_{ij}b_{jk} c_{kl} $$

$$ (A)_{il}^{c} = \sum_{k=1}^{p} \sum_{j=1}^{n} v_{ij} \lambda_{jk}^{c}v_{kl}^{t}$$ now all $ \lambda^{c} $ is the entries exponentiatied.