7
$\begingroup$

I am a bit confused with this wikipedia article, hoping someone can clarify it. Looking at the Strassen algorithm page it is clear that this is an algorithm for reducing multiplication operations.

Why is a matrix multiplication algorithm touted as a matrix inversion algorithm? last time i checked it was totally odd to apply Gauss-Jordan elimination to multiply matrices

thanks

  • 0
    that ma$k$es sense; that would be the answer to my question. If you paste in answer format i will accept $it$2011-06-22

2 Answers 2

4

Gauss Jordan algorithm is effecting manipulations on the lines of the matrix to invert. Each operation is equivalent to multiply your matrix on the left side by a matrix of the form $I_n +\lambda E_{ij}$ where $E_{ij}$ is an elementary matrix: $E_{ij}=(e^{ij}_{kl})_{1\leq k,l\leq n}$ where $e^{ij}_{kl}=1$ if $k=i$ and $l=j$, and $0$ otherwise.
So each time you are making such an operation, you are actually multiplying your matrix by some other matrix, so all your line operations are actually equivalent to multiply your matrix by a series of matrix of the form $I_n +\lambda E_{ij}$.

HTH

  • 0
    i understand that, but it was not clear how to express the inversion elements from the multiplication operations in those specific algorithms2011-06-22
4

On the the wikipedia article for invertible matrices they show how you can design matrix inversion by blocks, which obtains the same complexity as multiplication. Pretty neat.