Determinants, Gaussian Elimination

Gaussian Elimination

Gauss (biography) developed the only practical algorithm for computing the determinant of large matrices, and it is still in use today. The procedure is known as gaussian Elimination, or det6 in our notation. It transforms an arbitrary matrix into an upper triangular matrix, then applies det5, as described in the previous section.

This procedure assumes R is a field, or at least R is an integral domain that can be embedded in its fraction field.

If the upper left entry is 0, look down the first column and find a nonzero entry. If there are none then the column is 0, and so is the determinant. Otherwise swap the two rows, so that the upper left entry is nonzero. This negates the determinant; make a note of that.

Move down the first column and perform a row operation whenever the entry is nonzero. If M1,1 = x and Mi,1 = y, subtract the first row, times y/x, from the ith row. This does not change the determinant. Now the first entry in the ith row is 0. When we're finished with the first column, only the top entry is nonzero.

Move to the second column and ask whether M2,2 is 0. If it is, find a lower row to swap with, so that M2,2 is nonzero. If everything in column 2, below row 1, is 0, move on to column 3. Stop at column j when M2,j is nonzero, or there is a nonzero entry below it that can participate in a swap. Remember to negate the determinant if you need to swap rows. Once the nonzero entry is established, run down the column and perform row subtraction operations, so that the rest of the column becomes 0.

When gaussian elimination is complete, we have an upper triangular matrix. Multiply the diagonal entries together to get the determinant. The result is 0 iff some of the diagonal entries are 0. If we find, for instance, that M2,2 is 0, with all zeros below it, we can stop right there. Something to the right may be nonzero, and all entries down and to the right of that may be nonzero as well, but these are all above the main diagonal. Starting with M2,2, the main diagonal is all zeros. Of course this doesn't happen very often; the determinant of a matrix is usually nonzero.

This algorithm loops over columns, then loops over rows below the main diagonal, then loops over columns to the right of the column being cleared. This runs in time n3 and space n2, assuming a bound on the size of the entries in the matrix.