Having two square matrices $n \times n$ where the values are repeated for entries which are located diagonally with respect to each other, is it possible to get a time complexity $O(n^2\log n)$?
I tried the Strassen method for this kind of matrices but I can't achieve to get that complexity, any tips?
An example of the matrices could be:
$$\begin{pmatrix} 1 & 2 & 3 & 4\\ 5 & 1 & 2 & 3\\ 6 & 5 & 1 & 2\\ 7 & 6 & 5 & 1 \end{pmatrix}$$
Thanks (:
The general purpose matrix multiplication of two $4 \times 4$ matrices requires $64$ elementary multiplications. Using Strassen's algorithm, only $49$ are required.
Due to the special diagonal structure of the matrices, $37$ multiplications are sufficient:
Matrix A:
Matrix B:
Products:
Matrix product $C = A \times B$:
It might be possible to reduce this number even further. No optimization was attempted rather than keeping track of the products which actually occur.