# 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 '17 at 12:47
• @ Amaury Pouly I have seen it but how ? 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. 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. 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. 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})$$
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.