next up previous
Next: Cramer's rule Up: Summary of relevant Previous: Matrix algebra

Determinants

A very useful function from square matrices to scalars is the determinant. Its definition is not usually relevant to computation, being defined in terms of a sum of products:

where the sum is taken over all permutations of and the sign of the permutation is 0 if it is a product of 3-cycles and 1 otherwise. However, one can see from the definition that the determinant of an integer matrix is an integer, which is a useful fact.

Determinants can be calculated by expansion by minors, also called the method of Laplace or Laplace expansion, or by Gaussian elimination, which is much cheaper in fixed-precision arithmetic. To expand a determinant by minors, choose a row or column of the (n by n) matrix, say for example the row . Then for each entry in the row, form the n-1 by n-1 matrix that you get by deleting the row and column of the entry. Compute these n smaller order determinants, and call the determinant corresponding to by the name (if the matrix is 1 by 1, the determinant is just the entry). Then we compute the final determinant as

This recursive procedure is most useful when most of the are zero, whence we do not actually need to form or compute the order n-1 determinants.

Determinants are useful because the linear equations Ax = b have a unique solution precisely when . We will see that this is not the whole story when data errors or uncertainty enter the picture.

Exercises

  1. The Maple statement det(A, sparse) will find the determinant of A by expansion by minors, which is the classical method taught in high school. This method is appropriate if A is sparse. Experiment with dense matrices and the time() command to see if det(A) or det(A,sparse) is faster, and by how much.
  2. Expansion by minors means that the cost of doing one determinant of an n by n matrix is equivalent to doing n determinants of n-1 by n-1 matrices, plus n multiplications and n-1 additions. Use this decomposition to estimate the growth of the cost of taking determinants by minors, and compare with the classical estimate of for taking determinants by Gaussian Elimination in fixed-precision arithmetic. Maple does not work in fixed-precision (unless you ask it to) so life isn't quite as simple as that, but nonetheless this calculation can give one an idea of the relative expense.


next up previous
Next: Cramer's rule Up: Summary of relevant Previous: Matrix algebra



Robert Corless
Wed Jan 31 11:33:59 EST 1996