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.