Suppose we are given a matrix $A$ over real numbers and we want to computer the inverse of matrix $A$. There are various algorithms to do so and it also turn out that we can use matrix multiplication problem to solve matrix inversion problem.

My question: How to prove that matrix inversion is at least as hard as matrix multiplication?

  • 1
    $\begingroup$ The wikipedia article on matrix inversion has an explanation and a reference for that fact. Namely, there exists an inversion algorithm that internally uses multiplication, and it's overall asymptotic complexity is the same as the underlying multiplication algorithm. $\endgroup$ Commented Nov 2, 2017 at 12:47
  • $\begingroup$ @ Amaury Pouly I have seen it but how ? $\endgroup$
    – Complexity
    Commented Nov 2, 2017 at 13:10
  • $\begingroup$ This is a standard divide and conquer algorithm: you write the matrix as a block matrix (with 4 subblocks, each half the size). Then using clever rewriting of the inverse (explained in the wikipedia article), you can write the block inverse with 6 multiplications and two inverses. Write $C(n)$ the complexity of inversion of $n\times n$ matrix and $\omega$ the matrix multiplication complexity exponent. Then $$C(n)=O(n^\omega)+2C(n/2).$$ You can solve this recurrence and get $C(n)=O(n^\omega)$, using Master theorem. $\endgroup$ Commented Nov 2, 2017 at 14:29
  • 1
    $\begingroup$ @AmauryPouly: in what way is this a proof ? There might be an inversion algorithm, say using quicksort, that doesn't require matrix multiplication. $\endgroup$
    – user16034
    Commented Nov 3, 2017 at 17:24
  • 1
    $\begingroup$ See my answer below, I initially answered the wrong direction (I thought the question was about multiplication being harder than inversion) and then added the correct direction. $\endgroup$ Commented Nov 3, 2017 at 17:48

1 Answer 1


If you want to multiply two matrices $A$ and $B$ then observe that $$\begin{pmatrix}I_n&A&\\&I_n&B\\&&I_n\end{pmatrix}^{-1}= \begin{pmatrix}I_n&-A&AB\\&I_n&-B\\&&I_n\end{pmatrix}$$ which gives you $AB$ in the top-right block. It follows that inversion is at least hard as multiplication.

EDIT: I had misread the question, the original answer below shows that multiplication is at least as hard as inversion. Based on the wikipedia article: write block inverse of the matrix as $$\displaystyle {\begin{bmatrix}A & B \\C &D \end{bmatrix}}^{-1}={\begin{bmatrix}A^{-1}+A^{-1}B(D -CA^{-1}B)^{-1}CA^{-1}&-A^{-1}B(D -CA^{-1}B )^{-1}\\-(D-CA^{-1}B)^{-1}CA^{-1}&(D-CA^{-1}B)^{-1}\end{bmatrix}}.$$ Note that $A$ is invertible because it is a submatrix of the original matrix (which is invertible). One can prove that $D-CA^{-1}B$ is invertible because of the following identity ($M$ is the original matrix): $$\det(M)=\det(B)\det(D-CA^{-1}B).$$ Some clever rewriting using Woodbury identity gives $$\displaystyle {\begin{bmatrix}A & B \\C &D \end{bmatrix}}^{-1}={\begin{bmatrix}X&-XBD^{-1}\\-D^{-1}CX&D^{-1}+D^{-1}CXBD^{-1}\end{bmatrix}}$$ where $$X=(A-BD^{-1}C)^{-1}.$$ Let $C(n)$ denote the complexity of matrix inversion for a $n\times n$ matrix. Let $\omega$ be the exponent of the best matrix multiplication algorithm, so that we can multiply two $n\times n$ matrices in time $O(n^\omega)$. Using the formula above, we can express the inverse of an $n\times n$ matrix using:

  • two inverses of half-size ($\frac{n}{2}\times\frac{n}{2}$): $D$ and $X$
  • six multiplications of half-size: $BD^{-1}$, $(BD^{-1})C$, $X(BD^{-1})$, $D^{-1}C$ and $(D^{-1}C)(XBD^{-1})$
  • two additions of half-size

This gives the recurrence $$C(n)=2C(n/2)+6O((\tfrac{n}{2})^\omega)+2O((\tfrac{n}{2})^2).$$ Since $\omega\geqslant 2$, we rewrite the above as $$C(n)=2C(n/2)+O(n^\omega).$$ We can now apply the Master theorem. Using the notation of the wikipedia article, we have $f(n)=Kn^\omega$ for some constant $K$, $a=b=2$ thus $c_{crit}=\log_22=1<\omega$. On the other we have a regularity condition on $f$ since $$af(n/b)=2K(\frac{n}{2})^\omega=2{1-\omega}Kn^\omega\leqslant \frac{1}{2}f(n)$$ because $\omega\geqslant 2$. Thus the theorem tells us that $$C(n)=O(f(n))=O(n^\omega).$$ It follows from that multiplication is at least as hard as inversion.

  • $\begingroup$ You prove the wrong direction. $\endgroup$
    – aaaaajack
    Commented Nov 3, 2017 at 16:25
  • 3
    $\begingroup$ Indeed, I prove the hard direction. I edited my post with the other direction. $\endgroup$ Commented Nov 3, 2017 at 16:40
  • $\begingroup$ @Amaury Pouly Thanks for such an detailed answer. $\endgroup$
    – Complexity
    Commented Nov 3, 2017 at 17:56
  • $\begingroup$ That first line is pure genius. $\endgroup$
    – gnasher729
    Commented Nov 4, 2017 at 15:07
  • $\begingroup$ the Note that A is invertible because it is a submatrix of the original matrix part is wrong. consider a matrix with 1 in the antidiagonal and 0 everywhere else. $\endgroup$ Commented Mar 15 at 20:57

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.