1
$\begingroup$

Suppose you're given a black box $A$, and you're told $A$ can invert a matrix (assuming the matrix is invertible) $M$ in $O(T_A)$. You're also given a black box $B$, and you're told $B$ can multiply two matrices $X$ and $Y$ in $O(T_B)$.

There are two problems as follow:

  • How is it possible to compute $X \times Y$ by just using $A$ in $O(T_A)$?
  • How is it possible to compute $X^{-1}$ by just using $B$ in $O(T_B)$?

Some ideas that come to mind:

We already know that if $X$ is invertible, then:

$$X\times X^{-1}=I$$

where $I$ is an identity matrix. But how can I compute $X^{-1}$? Any hint will be constructive.

$\endgroup$

1 Answer 1

3
$\begingroup$

It was shown in 1969, by Strassen, that matrix multiplication and matrix inversion have the same computational complexity.

Details can be found on Wikipedia.

$\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.