Some Theorems and Finding the Inverse of a Matrix

Theorem: If the GJSF of A is S, then A=ES for some nonsingular matrix E.

Proof: The proof of this is easy: Elem.A=S using our matrix Elem above. Elem is nonsingular, so A=Inverse[Elem].S. Take E=Inverse[Elem].

We have a few more theoretical results from these ideas.

Theorem: A matrix is nonsingular if and only if its GJSF is the identity matrix.

Proof: Let S be the GJSF of an nxn matrix A, so A=ES from the last theorem.
If A is nonsingular, then so is S, since E is automatically nonsingular and therefore Inverse[A]=Inverse[S].Inverse[E]. Now, since S is nonsingular, it must have n linearly independent columns. Since S is also in GJSF, that means each column must be a pivot column (read the requirements to be in GJSF again!) with a leading 1. But that means S is the identity matrix!

Conversely, if S=I, the identity matrix, then A=EI=E which is nonsingular, so A is nonsingular.

If you understand the workings of these ideas we've been discussing, these proofs are not hard at all.

Let's take a small detour from our theorems to look at an important computational tool that follows from the last theorem. If A is nonsingular, its GJSF is I. That means that it is possible to go from A to I using only finitely many elementary row operations, or Elem.A=I. It looks like Elem is Inverse[A]! Technically, this is only a left inverse, since we only have multiplication on the left to get I. However, we KNOW A is nonsingular, so Elem must be the "real" inverse as well (this is not as clear if it is not known in advance that A is nonsingular). This gives us a means of finding the inverse of a matrix, and/or testing if it is nonsingular. If we fing the GJSF of A and it is not the identity matrix, then A is singular from the last theorem. If it is the identity, then Elem is the inverse. Let's try it.

  Clear[M,MI,rrMI]
  M={{1,2,-3,1},{-1,3,-3,-2},{2,0,1,5},{3,1,-2,5}};
  MatrixForm[M]

  MatrixForm[RowReduce[M]]

Is M nonsingular?

  Clear[B,BI,rrBI]
  B={{1,1,2,1},{0,-2,0,0},{1,2,1,-2},{0,3,2,1}};
  MatrixForm[B]

  MatrixForm[RowReduce[B]]

Is B nonsingular? If so, what is Inverse[B]?

  BI=AppendRows[B,IdentityMatrix[4]];
  MatrixForm[BI]

  rrBI=RowReduce[BI];
  invB=TakeColumns[rrBI,-4];
  MatrixForm[invB]

Is this really Inverse[B]? Let's see.

  MatrixForm[invB.B]
  MatrixForm[B.invB]

As you just saw, theory and computation go together quite nicely. Let's continue with some theorems.

Theorem: Two matrices A and B are row equivalent if and only if B=EA for some nonsingular matrix E.

Proof: If A and B are row equivalent, then there is a finite sequence of elementary row operations leading from A to B. As we saw above, this led to the matrix E (Elem), producing B=EA. Now conversely, if B=EA, with E nonsingular, by the last theorem, the GJSF of E is I, so there are elementary row operations leading from E to I, say E=E1.E2. . . . Es.I. So B=E1.E2. . . . Es.A, which shows we can go from A to B with a finite number of elementary row operations, so A and B are row equivalent.

This next theorem is easy to see but tedious to prove, so we state it without proof. It is quite important; it makes certain we have no problems with our calulations.

Theorem: The GJSF of a matrix is unique; that is, there is one and only one GJSF for a matrix

Up to Linear Algebra Part I