5
$\begingroup$

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.

$\endgroup$
1
  • 3
    $\begingroup$ 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. $\endgroup$ Commented Jun 29, 2012 at 15:07

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – A.S
    Commented Jun 29, 2012 at 6:56
  • 1
    $\begingroup$ @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. $\endgroup$
    – Erick Wong
    Commented Jun 29, 2012 at 7:33
0
$\begingroup$

Assumption: Square Invertible matrix.

Gauss-Jordan method is typically taught after Gaussian Elimination method for solving System of linear equations. So, I'm assuming you know about Gaussian Elimination.

Consider system of linear equations $Ax=b$.

$Ax=b$.....................................(1)

$Ux = c$.....................................(2)

$Ix = A^{-1}b$...............................(3)

We can go from step (2) to step (3) in Gauss-Jordan method only if we assume that U has full set of n pivots.

If some pivot is zero, we cannot use it to eliminate elements above it for reaching Identity matrix.

If A is invertible => A has full set of n pivots => We can go from U to I.

$\therefore$ For all invertible matrix A, Gauss-Jordan method works.

If $b = I$

then $x=A^{-1}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .