Finding a certain entry in a matrix Can we find the entry $s_{23}$ of $S=H^3$ where $H=\pmatrix{2&-1&0\\3&1&2\\-1&1&1}
$ without finding $S$. I know that $s_{23}$ is given by multiplying the second row of $H^2$ and the third coloumn of $H$ but it is dull. Thank you for any hints!
 A: If you don't want to calculate $H^3$ or $H^2$, you can take the vector $v=\begin{pmatrix}0&0&1\end{pmatrix}^T$ and calculate $w=H \cdot H \cdot H \cdot v = H \cdot H \cdot \begin{pmatrix}0&2&1\end{pmatrix}^T$. The entry $s_{23}$ will be the second coordinate of $w$.
You need 18 multiplications and 12 additions to calculate this. Calculating $H^2$ would need 27 multiplications and 18 additions. I don't know whether this is still too 'dull' for you ;)
This works since $s_{23}$ is the $e_2$-component of the image of $e_3$ under $S$.
Edit: Even less work is needed by a comment of celtschk. We may extract the $e_2$-component of $H H \begin{pmatrix}0&2&1\end{pmatrix}^T$ by multiplying with $\begin{pmatrix}0&1&0\end{pmatrix}$ from the left. Therefore, we can calculate $$s_{23} = \begin{pmatrix}0&1&0\end{pmatrix} HH \begin{pmatrix}0&2&1\end{pmatrix}^T = \begin{pmatrix}3&1&1\end{pmatrix} H \begin{pmatrix}0\\2\\1\end{pmatrix}$$ with 12 multiplications and 8 additions.
A: The characteristic polynomial of $H$ is $$X^3-4X^2+6X-3.$$
Therefore $$H^3=4H^2-6H+3I=H(4H-6I)+3I.$$
The element $(H^3)_{23}$ is then the product of the second row of $H$ times the third column of $4H-6I$ (plus nothing since $3I$ has element $(2,3)$ equal to $0$).
We need $18$ products and $12$ additions to get the polynomial, plus the expanding of terms. After that we need 1 addition (from the -6I), 3 multiplications (from the 4H), plus 3 multiplications and 2 additions from the second row-third column product.
But hey, this way is not dull!
