Proof that the method of Gauss/Jordan yields the inverse of a matrix

Question

I have trouble in solving the following exercise: let A be an invertible matrix. Consider the matrix A|I where I is the identity matrix. Prove that the matrix obtained by transforming A|I in it's row-echelon form is equal to I|B where B is the inverse matrix of A. Any help would be appreciated.

Answer 1

Let $e_1$, $e_2$, ..., $e_n$ denote the columns of the identity matrix. When you solve the system $Ax=e_i$, you find a unique column $v_i$ such that $Av_i=e_i$. What's this column? When you consider the matrix $[A\;|\;e_i]$ and bring it to row echelon form, you get $[I\;|\;v_i]$.

Thus when you do the row echelon form reduction of $[A\;|\;I]$ you're doing $n$ simultaneous reductions; there's no difference in the steps you perform in each reduction $[A\;|\;e_i]\to[I\;|\;v_i]$ because you find the same pivots in each row, so in the first $n$ columns, and never use the last column for the elimination.

Thus the row echelon form you get is exactly $[I\;|\;v_1\; v_2\; \dots\; v_n]$ and $$ A[v_1\; v_2\; \dots\; v_n]=[e_1\;e_2\;\dots\;e_n]=I $$ by definition of $v_1$, $v_2$, ..., $v_n$.

Answer 2

Hints:

(1) Any elementary row (column) operation on $\,A\,$ is like multiplying $\,A\,$ from the left (from the right) by an elementary matrix $\,E_j\,$ ($\,F_j\;$)

(2) We know (I hope...) all the elementary matrices are invertible

(3) After you're done with the algorithm, you got

$$A\to E_rE_{r-1}\cdot\ldots\cdot E_1AF_1\cdot\ldots F_s=I$$

(4) If $\,A,B,P,Q\,$ are square matrices of the same order, with $\,P,Q\,$ invertible, then

$$PAQ=B\iff A=P^{-1}BQ^{-1}$$

Edit: As noted in the comments by Sami, you can not mix row/columns operations, so you must choose either $\,E_j$'s or $\,F_j$'s but don't mix them.

Answer 3

In the matrix $A|I$ imagine we place in the middle the matrix inverse $B$ and we have $$AB|I$$ which means obviously that $AB=I$ and an elementary row operation on A is multiplying A from the left by an elementary matrix $E_j $ until we find the matrix $I$ so we find $$\underbrace{E_rE_{r-1}\cdots E_1A}_{=I}B|E_rE_{r-1}\cdots E_1I$$ hence we find that $$B=E_r E_{r-1}\cdots E_1$$ and we can do the same method for the elementary column operations.