1
$\begingroup$

Is it possible, according to the current state of knowledge, that orthogonal matrices can be multiplied faster than arbitrary matrices?

More precisely, let $T(N)$ denote the worst-case time of the fastest algorithm to multiply two arbitrary $N\times N$ matrices (in the real RAM model). Let $T_{\rm O}(N)$ denotes the worst-case time to multiply two orthogonal $N\times N$ matrices. Is there a proof that $T_{\rm O}(N) = \Omega(T(N))$?

It seems intuitive to me that $T_{\rm O}(N) = \Theta(T(N))$, but I couldn't come up with any proof. Below are my thoughts and failed attempt.


I became interested in this question at the prompting of a question on math stack exchange. It is easy to show that, for example, $T_{\rm S}(N) = \Omega(T(N))$, where $T_{\rm S} $ is the worst-case time to multiply two symmetric $N\times N$ matrices. This follows directly by reduction by embedding the arbitrary matrices $A$ and $B$ into the larger symmetric product

$$ \begin{bmatrix} 0 & A \\ A^\top & 0 \end{bmatrix}\begin{bmatrix} 0 & B^\top \\ B & 0 \end{bmatrix} = \begin{bmatrix} AB & 0 \\ 0 & B^\top A^\top \end{bmatrix}. $$

However, the analogous emebedding of a matrix $A$ (normalized to be a contraction) into an orthogonal matrix

$$ A \mapsto \begin{bmatrix} A & (I - AA^\top)^{1/2} \\ (I - A^\top A)^{1/2} & -A^\top \end{bmatrix} $$

requires at least $\Omega(T(N))$ operations to construct any way I am aware of, so I was unable to prove the result by the same embedding trick.

Is there a more clever proof that $T_{\rm O}(N) = \Omega(T(N))$?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.