How to prove that matrix inversion is at least as hard as matrix multiplication?
If you want to multiply two matrices $A$ and $B$ then observe that
$$\begin{pmatrix}I_n&amp;A&amp;\\&amp;I_n&amp;B\\&amp;&amp;I_n\end{pmatrix}^{-1}=
\begin{pmatrix}I_n&amp;-A&amp;AB\\&amp;I_n&amp;-B\\&amp;&amp;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 &amp; B \\C &amp;D \end{bmatrix}}^{-1}={\begin{bmatrix}A^{-1}+A^{-1}B(D -CA^{-1}B)^{-1}CA^{-1}&amp;-A^{-1}B(D -CA^{-1}B )^{-1}\\-(D-CA^{-1}B)^{-1}CA^{-1}&amp;(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 &amp; B \\C &amp;D \end{bmatrix}}^{-1}={\begin{bmatrix}X&amp;-XBD^{-1}\\-D^{-1}CX&amp;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&lt;\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.