I know Strassen and other methods can achieve better than $O(n^3)$ for general square matrix multiplication. I am curious of the spacial case where the multiplication is between a $n*m$ matrix $A$ with its transpose $A^T$ .
Is there known algorithm that computes this case fast?
thanks
Best Answer
I'm guessing you were thinking of asymptotic optimisations (rather than any practical tricks) but unfortunately I don't think it would be possible to get an asymptotic speed up for this product. If we assume we can compute the product of an $n\times m$ matrix $A$ with its transpose in $O(f(n,m))$ time then we could compute the product of two $n\times n$ matrices $B$ and $C$ in $O(f(2n,2n))$ time by computing the product $$ AA^T= \left( \begin{array}{c|c} B & 0 \\ \hline C^T & 0 \end{array}\right) \left( \begin{array}{c|c} B^T & C \\ \hline 0 & 0 \end{array}\right)= \left( \begin{array}{c|c} BB^T & BC \\ \hline C^TB^T & C^TC \end{array}\right) $$ and just looking at the upper right corner. So assuming $f$ is some sensible function this will still be $O(f(n,m))$ and so asymptotically the same as computing the transpose product, hence the transpose product won't be able to beat the normal product asymptotically.
If there are any gaps in this analysis please let me know!