# 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!

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.

• Even less work is needed: $$\pmatrix{3&1&2}\cdot H\cdot\pmatrix{0\\2\\1}.$$ 12 multiplications and 8 additions. Sep 6, 2018 at 15:40
• @celtschk You are totally right. I'll edit this Sep 6, 2018 at 15:58
• How are you counting to get the $12$ multiplications and $8$ additions? Sep 7, 2018 at 11:00
• Multiplying $H$ with the left vector yields $3\times 3$ multiplications. We have to add two of such products to get the entries of the result, which yields $3\times 2$ additions. Multiplying the two remaining vectors yields 3 multiplications and two additional additions. Of course, if we don't count the multiplications with $0$ at the beginning, it's only $9$ multiplications and $6$ additions. Sep 7, 2018 at 11:13

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!

• Definitely not dull. I like creative usage of Cayley Hamilton! +1 Sep 6, 2018 at 8:16
• Is $A=H$? If so, you may want to consistently use $H$ throughout. Sep 6, 2018 at 12:52
• @MeniRosenfeld Yes, of course. Gonna correct it. Thanks! Sep 6, 2018 at 12:58