4.2-1

Use Strassen’s algorithm to compute the matrix product

\[ \begin{pmatrix} 1 & 3 \\ 7 & 5 \end{pmatrix} \begin{pmatrix} 6 & 8 \\ 4 & 2 \end{pmatrix} \]

Show your work.

Sol’n

\[ \begin{align*} S_1 & = B_{12} - B_{22} = 8 - 2 = 6, \\ S_2 & = A_{11} + A_{12} = 1 + 3 = 4, \\ S_3 & = A_{21} + A_{22} = 7 + 5 = 12, \\ S_4 & = B_{21} - B_{11} = 4 - 6 = -2, \\ S_5 & = A_{11} + A_{22} = 1 + 5 = 6, \\ S_6 & = B_{11} + B_{22} = 6 + 2 = 8, \\ S_7 & = A_{12} - A_{22} = 3 - 5 = -2, \\ S_8 & = B_{21} + B_{22} = 4 + 2 = 6, \\ S_9 & = A_{11} - A_{21} = 1 - 7 = -6, \\ S_{10} & = B_{11} + B_{12} = 6 + 8 = 14. \end{align*} \]

\[ \begin{align*} P_1 & = A_{11} \cdot S_1 = 1 \cdot 6 = 6, \\ P_2 & = S_2 \cdot B_{22} = 4 \cdot 2 = 8, \\ P_3 & = S_3 \cdot B_{11} = 12 \cdot 6 = 72, \\ P_4 & = A_{22} \cdot S_4 = 5 \cdot -2 = -10, \\ P_5 & = S_5 \cdot S_6 = 6 \cdot 8 = 48, \\ P_6 & = S_7 \cdot S_8 = -2 \cdot 6 = -12, \\ P_7 & = S_9 \cdot S_{10} = -6 \cdot 14 = -84. \end{align*} \]

\[ \begin{align*} C_{11} & = P_5 + P_4 - P_2 + P_6 = 48 + (-10) - 8 + (-12) = 18, \\ C_{12} & = P_1 + P_2 = 6 + 8 = 14, \\ C_{21} & = P_3 + P_4 = 72 + (-10) = 62, \\ C_{22} & = P_5 + P_1 - P_3 - P_7 = 48 + 6 - 72 - (-84) = 66, \\ \end{align*} \]