Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
A small tweak of the Strassen algorithm can be used to invert a matrix; see the bottom of the mathworld page. The wikipedia page is comparing the Gauss-Jordan method of matrix inversion with the Strassen method of matrix inversion; and the Strassen method of matrix multiplication with the usual, direct, method of matrix multiplication (there is no indication whatsoever that they are doing "Gauss-Jordan" for multiplication). –  Arturo Magidin Jun 22 '11 at 21:02
    
thanks, it says that the formula applies only to $2 \times 2$ matrices? or it just refers to the $2 \times 2$ block partitioning into submatrices? –  lurscher Jun 22 '11 at 21:10
1  
I don't know the algorithm myself well enough; I programmed Strassen's algorithm for multiplication once, but that was over 20 years ago; but google search gives, for example, the code Mathematica uses. I think you just recursively go down to the 2x2 case, where the problem can be solved directly, and then use Strassen's method to "lift" it to a full matrix. –  Arturo Magidin Jun 22 '11 at 21:13
    
that makes sense; that would be the answer to my question. If you paste in answer format i will accept it –  lurscher Jun 22 '11 at 21:21

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
    
i understand that, but it was not clear how to express the inversion elements from the multiplication operations in those specific algorithms –  lurscher Jun 22 '11 at 21:22

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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