# 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. Nov 2, 2017 at 12:47
• @ Amaury Pouly I have seen it but how ? Nov 2, 2017 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. Nov 2, 2017 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.
– user16034
Nov 3, 2017 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. Nov 3, 2017 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})$$
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.