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.

Suppose \(A\) is a \(kn \times n\) matrix and \(B\) is a \(n \times kn\) matrix. In other words, \(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. Their product \(C\) is a \(kn \times kn\) matrix of the form \(\begin {bmatrix} A_1B_1 & \cdots & A_1B_k \\ \vdots & \ddots & \vdots \\ A_kB_1 & \cdots & A_kB_k \end{bmatrix}\) and we can use Strassen’s algorithm to compute each term of this matrix. Since there are \(k^2\) terms to compute via Strassen’s algorithm, we know that this will take \(\Theta(k^2 n^{\lg7})\) time.

Computing \(B \cdot A\) will result in an \(n \times n\) matrix which we calculate as \(C = \sum\limits_{i=1}^{k}B_{i} \cdot A_{i}\). We can use Strassen’s algorithm to compute each of these \(k\) matrix products, and therefore \(B \cdot A\) can be computed in \(\Theta(k n^{\lg7})\) time.