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