Combination of an entry of a matrix in multiplicative form

Question

Suppose $A$ is a $n\times n$ matrix with each entry $a_{ij}$. We all know the entry indexed by $(i,j)$ of $A^2$ would be $a_{ij}^{(2)}=\sum\limits_{k=1}^{n} a_{ik}a_{kj}$. My question is: Can we follow this strategy and express $a_{ij}^{(q)}$ as the sum of something? Here, assume $q$ is arbitrary. My guess is we can write $a_{ij}^{(3)}=\sum\limits_{k=1,h=1}^{n} a_{ik}a_{kh}a_{hj}$? If this is true, is there any way to make notations in $a_{ij}^{(q)}$ clean and easy to follow, e.g. constructing an indexed sequence?

Answer 1

In general for matrices $A$ and $B$, the $(i,j)$ entry of the product $A B$ is

$$ C_{ij} = \sum_k A_{ik}B_{kj} $$

So you can indeed use this recursively to calculate powers of $A$, e.g.

\begin{eqnarray} A^2_{ij} &=& \sum_{k_1} A_{i{k_1}}A_{{k_1}j} \\ A^3_{ij} &=& \sum_{k_1} (A^2_{i{k_1}})A_{{k_1}j} = \sum_{k_1} \left(\sum_{k_2} A_{i{k_2}}A_{{k_2}{k_1}}\right)A_{{k_1}j} = \sum_{k_1, k_2} A_{i k_2} A_{k_2 k_1} A_{k_1 j}\\ &\vdots& \\ A_{ij}^n &=& \sum_{k_1 k_2 \cdots k_n} A_{i k_n} A_{k_{n}k_{n-1}}\cdots A_{k_1 j} \end{eqnarray}

That being said, if you are planning to calculate a power of $A$ maybe you're better off with another method. To give you an example, if $A$ is diagonalizable $A = U \Lambda U^{-1}$, for $\Lambda = {\rm diag}(\lambda_1, \lambda_2, \cdots)$ , then

\begin{eqnarray} A &=& U \Lambda U^{-1} \\ A^2 &=& (U \Lambda U^{-1})(U \Lambda U^{-1}) = U\Lambda^2 U^{-1}\\ &\vdots&\\ A^n &=& U \Lambda^n U^{-1} \end{eqnarray}

where

$$ \Lambda^n = {\rm diag}(\lambda_1^n, \lambda_2^n, \cdots) $$