Math 2500: Linear Algebra

Subsubsection 2.6.3.1 Matrix Inverses

The main point of this section is to start focusing on the first big problem in linear algebra. How can you tell, in advance, that a system of \(n\) equations in \(n\) unknowns will have a solution?

Of course, like all things we have been studying, this will have several different faces, all of which are equivalent. The one front and center right now is this: When does an \(n \times n\) square matrix have an inverse?

Subsubsection 2.6.3.2 Finding an Inverse: Gauss-Jordan Elimination

There is an effective method for finding the inverse, and it is Gauss-Jordan elimination. (This is sometimes just called Gaussian elimination.) Essentially, you wish to solve \(n\) different systems \(Ax= b\) of size \(n\times n\) all at the same time, with specially chosen right hand sides.

The process is an algorithm, so it is very specific. If you do this some other way, you aren't doing Gauss-Jordan Elimination. The name is applied to the process.

Gauss-Jordan Elimination

• Augment: Tack on a copy of the identity matrix of the same size to the right hand side of your matrix. It should now look like \((A \mid I)\text{.}\)
• Forward Pass:
  • preparation: If necessary, use a row swap to make a non-zero entry in the upper left entry.
  • make zeros: The upper left entry is our first pivot. Use the operation of adding a multiple of the first row to the other rows to kill the entries below this first pivot.
  • step down: Step down to the second row and repeat the above, but ignoring rows and columns above and to the left. Repeat as necessary till you run out of rows.
• Backward Pass: This is also nested, like the forward pass, except that instead of working down and to the right, you begin at the lower right with the last pivot and work up and to the left. When complete, the matrix should have at most one non-zero entry in each row. This entry will be a pivot.
• Rescale: rescale rows to make the pivots into \(1\)'s.

At the end of the whole process, you should have something that looks like this: \((I \mid B)\text{.}\) The wonderful part: \(B\) is the inverse of \(A\text{.}\) Well, almost. The process can fail! If along the line you find that the left hand block of your big augmented matrix doesn't have \(n\) pivots in it, then your matrix was not invertible.

What you have computed in the left hand block with the Gauss-Jordan elimination is the reduced row-echelon form of your original matrix.

Subsubsection 2.6.3.3 The Big Theorem: invertibility, singularity, and the determinant

What is the key?

This is huge. The algorithm is not difficult, and it answers an important question exactly.

Note that we said a square matrix was singular when it did not have enough pivots. So what the above says is that a matrix is invertible if and only if it is non-singular.

Subsubsection 2.6.3.4 A simple test

We can use the above to make a simple numerical test of when a matrix is invertible. First do the forward pass of elimination to obtain an upper triangular matrix. Take the product of the diagonal entries. This will be zero if and only if one of the diagonal entries is zero, which will only happen if there are fewer than \(n\) pivots. This product is then helpful enough to test for invertibility, and so it deserves its own name: the determinant. We shall learn more about this quantity later.