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.

Gauss-Jordan elimination is a technique that can be used to calculate the inverse of matrices (if they are invertible). It can also be used to solve simultaneous linear equations.

However, after a few google searches, I have failed to find a proof that this algorithm works for all $n \times n$, invertible matrices. How would you prove that the technique of using Gauss-Jordan elimination to calculate matrices will work for all invertible matrices of finite dimensions (we allow swapping of two rows)?

Induction on $n$ is a possible idea: the base case is very clear, but how would you prove the inductive step?

We are not trying to show that an answer generated using Gauss-Jordan will be correct. We are trying to show that Gauss-Jordan can apply to all invertible matrices.

Note: I realize that there is a similar question here, but this question is distinct in that it asks for a proof for invertible matrices.

share|improve this question
2  
You should prove that each of the operations involved in the algorithm (swapping rows, adding a multiple of one row to another row, multiplying a row by a nonzero constant) do not change the rank of the matrix; then show that, under a suitable definition of "simplify", after a suitable number of steps of the algorithm any matrix that is not in row-echelon form can be turned into a "simpler" matrix by the algorithmic step. –  Arturo Magidin Jun 29 '12 at 15:07

1 Answer 1

up vote 2 down vote accepted

This is one of the typical cases where the most obvious reason something is true is because the associated algorithm cannot possibly fail.

Roughly speaking, the only way Gauss-Jordan can ever get stuck is if (at any intermediate point) there is a column containing too many zeroes, so there is no row that can be swapped in to produce a non-zero entry in the expected location. However, if this does happen, it is easy to see that the matrix is non-invertible, and since the row operations did not cause this, it must have been the original matrix that is to blame.

share|improve this answer
    
OK. But how do you show that "the only way it can get stuck is if there is a column containing too many zeroes?" I was looking for something a little more rigorous. –  Andrew Salmon Jun 29 '12 at 6:56
1  
@AndrewSalmon Think of all the operations that are needed: the only one that can fail is division by zero. It's not particularly quantitative, but I don't see how it isn't rigorous. –  Erick Wong Jun 29 '12 at 7:33

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.