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$ and $B$ are two $kn \times n$ matrices such that: $A = \begin {bmatrix} A_1 \\ \vdots \\ A_k \end {bmatrix}$ and $B = \begin {bmatrix} B_1 \cdots B_k \end {bmatrix}$

Hence, $A \times B$ is a $kn \times kn$ matrix equal to $% $ , 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.

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 compute $B \times A$ in $\Theta(kn^{\lg 7})$ time.