# Proof that Gauss-Jordan elimination works

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.

-
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