# 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 det_{6} in our notation.
It transforms an arbitrary matrix into an upper triangular matrix,
then applies det_{5}, 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 M_{1,1} = x and M_{i,1} = y,
subtract the first row, times y/x, from the i^{th} row.
This does not change the determinant.
Now the first entry in the i^{th} 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 M_{2,2} is 0.
If it is, find a lower row to swap with, so that M_{2,2} is nonzero.
If everything in column 2, below row 1, is 0, move on to column 3.
Stop at column j when M_{2,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 M_{2,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 M_{2,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 n^{3} and space n^{2}, assuming a bound on the size of the entries in the matrix.