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!
2 Answers
$\begingroup$
$\endgroup$
4
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.
-
2$\begingroup$ Even less work is needed: $$\pmatrix{3&1&2}\cdot H\cdot\pmatrix{0\\2\\1}.$$ 12 multiplications and 8 additions. $\endgroup$– celtschkSep 6, 2018 at 15:40
-
$\begingroup$ @celtschk You are totally right. I'll edit this $\endgroup$ Sep 6, 2018 at 15:58
-
$\begingroup$ How are you counting to get the $12$ multiplications and $8$ additions? $\endgroup$ Sep 7, 2018 at 11:00
-
$\begingroup$ 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. $\endgroup$ Sep 7, 2018 at 11:13
$\begingroup$
$\endgroup$
3
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!
-
1$\begingroup$ Definitely not dull. I like creative usage of Cayley Hamilton! +1 $\endgroup$ Sep 6, 2018 at 8:16
-
$\begingroup$ Is $A=H$? If so, you may want to consistently use $H$ throughout. $\endgroup$ Sep 6, 2018 at 12:52
-
$\begingroup$ @MeniRosenfeld Yes, of course. Gonna correct it. Thanks! $\endgroup$ Sep 6, 2018 at 12:58