2
$\begingroup$

Let $A,B\in\mathbb{F}^{n\times n}$ be two $n\times n$ matrices over the underlying field $\mathbb{F}$. In addition, $A$ is guaranteed to be a symmetric matrix, i.e, $A=A^{T}$. We assume complexity measure to be the number of field operations over $\mathbb{F}$. Now consider at the following problem:-

Given $A,B$ and $AB$ as input, can we compute $AB^{T}$ in $o(n^{\omega})$ time?

Here $\omega$ is the exponent of matrix multiplication. Note that $AB^{T}=A^{T}B^{T}=(BA)^{T}$. Thus computing $BA$ in $o(n^{\omega})$ time is also enough.

$\endgroup$

1 Answer 1

8
$\begingroup$

No. Consider block matrices $A = \left(\begin{matrix} 0 & 0 \\ 0 & X \end{matrix}\right)$ (with symmetric $X$) and $B = \left(\begin{matrix} 0 & Y \\ 0 & 0 \end{matrix} \right)$. Computing $AB^T$ from $A$, $B$ and $AB$ means computing $XY^T$ from $X$ and $Y$, since $AB = 0$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.