Theorem A transformation is invertible ⇔ It is onto and one-to-one.
Proof By definition of invertibility, the 1st property implies the 2nd and the 3rd. Then by this result, the 2nd property implies the 4th, and the 3rd implies the 5th. The 4th property means that all rows of A are pivot. The 5th property means that all columns of A are pivot. For a square matrix, either case implies that the reduced row echelon form of A is the identity matrix I. This completes the proof for the following implications.
1 ⇒ 2 ⇒ 4 ⇒ 6 ⇒ 8
1 ⇒ 3⇒ 5 ⇒ 7 ⇒ 8
Thus it remains to show that the 8th property implies the 1st. The idea is to show that our method for computing the inverse, which was based on the assumption that the 8th property holds, indeed gives us the inverse matrix.
The method is to use row operations (presumably the same ones that change A to I) to change [A I] to [I B]. By taking columns 1, 2, ..., n, n + i only, we see that [A ei] can be row operated to become [I bi], where ei is the i-th standard basis vector, and BI is the i-th column of B. By thinking of [A ei] as the augmented matrix of the system Ax = ei, the solution of the system is the same as the solution of Ix = BI Since Ix = BI clearly has x = BI as the unique solution, we have Abi = ei. Then we conclude
AB = [Ab1, Ab2, ..., Abn] = [e1 e2 ... en] = I.
To show B is really the inverse of A, we still need to establish BA = I. The following argument shows that this is a consequence of AB = I and A is a square matrix.
AB = I
⇒ Ax = b has solution for any b (2 ⇒ 4)
⇒ Solution of Ax = b is unique (by basic principle of linear algebra)
AB = I
⇒ A(BA) = (AB)A = IA = A = AI
⇒ A(i-th column of BA) = Aei (by this equality)
⇒ i-th column of BA = ei (by solution of Ax = b unique)
⇒ BA = [e1 e2 ... en] = I.