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.

Step 1: The division of these matrices results in 8 single-value matrices. I have omitted documenting this step since it is just as simple to reference values of the input matrices for subsequent steps.

Step 2: Note that every \(S_i\) is a single-valued matrix represented here as an integer for simplicity’s sake.

\[\begin{equation} \begin{split} 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{split} \end{equation}\]

Step 3:

\[\begin{equation} \begin{split} 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{split} \end{equation}\]

Step 4:

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