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

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?

• 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. – Amaury Pouly Nov 2 '17 at 12:47
• @ Amaury Pouly I have seen it but how ? – Complexity Nov 2 '17 at 13:10
• 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. – Amaury Pouly Nov 2 '17 at 14:29
• @AmauryPouly: in what way is this a proof ? There might be an inversion algorithm, say using quicksort, that doesn't require matrix multiplication. – Yves Daoust Nov 3 '17 at 17:24
• 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. – Amaury Pouly Nov 3 '17 at 17:48

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 inversion is at least as hard as multiplication.

• You prove the wrong direction. – aaaaajack Nov 3 '17 at 16:25
• Indeed, I prove the hard direction. I edited my post with the other direction. – Amaury Pouly Nov 3 '17 at 16:40
• @Amaury Pouly Thanks for such an detailed answer. – Complexity Nov 3 '17 at 17:56
• That first line is pure genius. – gnasher729 Nov 4 '17 at 15:07