0
$\begingroup$

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?

$\endgroup$
  • 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$ – Amaury Pouly Nov 2 '17 at 12:47
  • $\begingroup$ @ Amaury Pouly I have seen it but how ? $\endgroup$ – Complexity Nov 2 '17 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$ – Amaury Pouly Nov 2 '17 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$ – Yves Daoust Nov 3 '17 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$ – Amaury Pouly Nov 3 '17 at 17:48
9
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.