Here we prove the second theorem about inverses:

Theorem. If A is an n by n square matrix, then the following statements are equivalent.

  1. A is invertible.
  2. The system Av=b has at least one solution for every column-vector b.
  3. The system Av=b has exactly one solution for every column-vector b (here v is the column-vector of unknowns).
  4. The system Av=b has only the trivial solution (0,0,0,...0) (see Homogeneous systems).
  5. The reduced row-echelon form of A is the identity matrix.
  6. A is a product of elementary matrices.

Proof. We shall prove that 1 implies 2, 2 implies 3, 3 implies 4, 4 implies 5, 5 implies 6 and 6 implies 1. This will mean that all these conditions are equivalent.

If A is invertible then as we have seen before Av=b has one solution v=A-1b. Thus 1 implies 2.

Suppose that the system Av=b has at least one solution for every b. We need to prove that this system has exactly one solution. By contradiction, suppose that it has more than one solutions. Using the Gauss-Jordan procedure we can transform the matrix A to the reduced row echelon form A' using a sequence of row operations p1,...,pm. Then by the theorem about systems of linear equations, the system has free unknowns. Since A' is a square matrix in the reduced row echelon form, it must have a zero row. By definition, this row must be at the bottom of A'. Let b' to be the column vector (0,...,0,1). Then the system A'v=b' does not have a solution since it contains an equation of the form 0=1. Applying the inverses of the row operations p1,...,pm in the opposite order (pm-1,...,p1-1) to the augmented matrix [A' | b'], we get a matrix of the form [A | b] for some b, which is the augmented matrix of the system of equations Av=b. This system is equivalent to the system A'v=b', so it has no solutions. This contradicts our assumptions that the system Av=b has at least one solution for every b. This contradiction completes the proof. Thus 2 implies 3.

If the system Av=b has exactly one solution for every b then in particular it has exactly one solution for b=0, so 3 implies 4.

If the system Av=0 has exactly one solution then it cannot have free unknowns (see the proof of the Theorem about homogeneous systems of equations.) Therefore every unknown is a leading. Therefore the reduced row-echelon system which is equivalent to Av=0 has the form

			 x1          = 0
			     x2      = 0
				....
				    xn=0

Thus the augmented matrix [A,0] of the system Av=0 can be reduced to the augmented matrix [I,0] by a sequence of row operations. If we forget about the last column and apply these operations to A, we get I. This proves that 4 implies 5.

Suppose that the reduced row-echelon form of A is I. This means that one can get I from A by a sequence of row operations. By the theorem about elementary matrices, every application of a row operation is equivalent to a multiplication by an elementary matrix. Therefore

			EmEm-1...E2E1A=I

By the lemma, each Ei is an invertible matrix therefore


		A=E1-1  E2-1  ...Em-1                                 (1)


The right hand side of this equality is a product of elementary matrices, because the inverse of an elementary matrix is again an elementary matrix (see the lemma about inverses of elementary matrices). This proves that 5 implies 6.

Suppose that A is a product of elementary matrices E1,...,En. By the lemma about inverses of elementary matrices the matrices E1,...,En are invertible. By the first theorem about inverses the product of invertible matrices is an invertible matrix. So A is an invertible matrix. This proves that 6 implies 1.

The theorem is proved.