How quickly can you multiply a \(kn \times n\) matrix by an \(n \times kn\) matrix, using Strassen’s algorithm as a subroutine? Answer the same question with the order of the input matrices reversed.
Let us assume \(A\) is \(kn \times n\) matrix and \(B\) is a \(n \times kn\) matrix such that:
\[A = \begin {bmatrix} A_1 \\ \vdots \\ A_k \end {bmatrix}\]and
\[B = \begin {bmatrix} B_1 \cdots B_k \end {bmatrix}\]Where each \(A_i\) and \(B_i\) is a \(n \times n\) matrix.
Hence, \(A \times B\) is a \(kn \times kn\) matrix equal to
\[\begin {bmatrix} A_1B_1 & \cdots & A_1B_k \\ \vdots & \ddots & \vdots\\ A_kB_1 & \cdots & A_kB_k \end{bmatrix}\]where each product \(A_iB_i\) is a \(n \times n\) matrix.
We can calculate each product \(A_iB_i\) using Strassens’s algorithm in \(\Theta(n^{\lg 7})\) time and there are \(k^2\) such matrices. Hence, we can compute \(A \times B\) in \(\Theta(k^2 n^{\lg 7})\) time.
Reversed Order
If we reverse the order of the input matrices, we are basically calculating \(B \times A\), which is a \(n \times n\) matrix equal to \(\sum_{i = 1}^k A_iB_i\).
In this case we need to perform \(k\) matrix multiplication of \(n \times n\) matrices using Straseen’s algorithm and \(k - 1\) additions to add those products. Hence, we can multiply the matrices in \(\Theta(kn^{\lg 7})\) time.