I’ve spoken vehemently before about my dislike of determinants, and in a straight forward computational lower level marices-and-vectors subject I’ll have nothing to do with them. However, I am currently teaching engineers, who seem enamoured of determinants. They love things like Cramer’s rule (hideously inefficient as it is), and it must be admitted that determinants do make their presence felt in other places: Jacobians for multiple changes of variables, Wronskians, etc. So I’ve been teaching determinants and how to compute them by hand.
I assumed that having been teaching determinants for years off and on, that I’d come across most methods for their computation. But no!
So this post gathers a few methods together. I’ll be brief, plenty of sordid details can be found on each method online.
This is the one we learn at our mothers’ knees, so to speak, as mathematical toddlers. It can be defined recursively as follows
For an matrix, pick any row or column. For simplicity’s sake, suppose we pick row , with elements . Then
where is the minor of , and which is defined to be the determinants of what’s left when every element in the same row and column of is removed.
It’s instructive to determine the cost of this calculation. Suppose are the numbers of multiplications and addtions respective;y, required to compute an determinant. We have and . (We shall treat subtraction as having the same cost as addition.)
By the expansion rule above, an determinant requires the computation of different determinants, with extra multiplications and additions. Thus:
The following table shows how these values increase:
It’s clear from the definition, and rammed home by this table, that the work required to compute a determinant by this method is of order . Thus, very inefficient.
General Laplace expansion
Some authors call this the Laplace expansion, and the version above then is a just a particular case of it. Curiously enough I’d never come across it until quite recently. The idea is quite simple; the main difficulty is finding good notation to describe it. Right, here goes.
Suppose we have an matrix , and suppose we pick rows, with indices
and also pick columns, with indices
So are simple lists of length containing strictly increasing row and column indices. We then define the matrix
to be the matrix whose -th element is . That is, consists of all the "intersections" of rows in with columns in . We also define to be the matrix obtained when all the rows in and columns in are removed.
For example, suppose
Let and . Then
Given all this, the generalized version of the Laplace expansion theorem claims that
where the sum is taken over all possible sets of columns, and is the sum of all the row and column indices. Clearly the original Laplace expansion is just this with . For some nice examples, with pictures, see this elegant exposition by David Eberly.
But is this generalized method any better than simply using ? Well, suppose that the least possible number of multiplications and additions to obtain an determinant using any Laplace expansion are respectively.
Suppose we perform the generalized expansion for an determinant with a particular . There will be determinants to evaluate, and the same number of determinants. These all need to be multiplied, and the products added. This means that
By symmetry, these values will be the same for and . So the smallest value will be obtained by computing these values for all and choosing the value which produces the smallest values for (since multiplication is more computationally expensive than addition, we must minimize the number of multiplications).
This gives the following table:
We can see that these values are smaller than those in the first table above, but they are still not sub-exponential (at least, I don’t think they are.)
I think I’ll split this into multiple posts. That’s enough for one.