The Laplace method:

[Graphics:HTMLFiles/Laplace_1.gif]

First create a minor matrix using the Delete function which just removes the ith element from the list:

myMinor[M_, i_, j_] := Transpose[Delete[Transpose[Delete[M, i]], j]]

Now evaluate the determinant using the expansion along the first row. The simplest case of 1x1 matrix has to be treated separately since the minor is not determined then.  Otherwise the evaluation is a straightforward implementation of the Laplace's formula.  Note how the reccurence is implemented: myDet appears on both sides.  One needs [[1]] after the Dimensions functions since this function produces a list of two elements (equal to each other in our case).  list[[1]] picks the first element from the list.

myDet[M_] := (n = Dimensions[M][[1]] ; If[n1, M[[1, 1]], Underoverscript[∑, j = 1, arg3] (-1)^(1 + j) M[[1, j]] myDet[myMinor[M, 1, j]]])

rantab[n_] := Table[Random[], {i, n}, {j, n}]

t4 = rantab[4]

( 0.7604411785085877`    0.6359358145412913`    0.6198705156720374`    0.7534236474215 ...          0.3250223118245828`    0.331497665595022`     0.21504731075419564`   0.22835347855084526`

Timing[myDet[t4]]

FormBox[RowBox[{{, RowBox[{RowBox[{0.01,  , Second}], ,, RowBox[{-, 0.0285459}]}], }}], TraditionalForm]

It takes vary little time to evaluate a 4x4 determinant by Laplace's expansion.

Timing[Det[t4]]

FormBox[RowBox[{{, RowBox[{RowBox[{0.,  , Second}], ,, RowBox[{-, 0.0285459}]}], }}], TraditionalForm]

However,  the amount of time for Mathematica's Det is not measurable,  so let's go to a larger size:

t9 = rantab[9] ;

Notice ";" at the end of command to suppress output.

Timing[myDet[t9]]

FormBox[RowBox[{{, RowBox[{RowBox[{71.172,  , Second}], ,, RowBox[{-, 0.0498203}]}], }}], TraditionalForm]

Timing[Det[t9]]

FormBox[RowBox[{{, RowBox[{RowBox[{0.,  , Second}], ,, RowBox[{-, 0.0498203}]}], }}], TraditionalForm]

Thus, the timing becomes nonnegligible for 9x9 matrices (this is on an 800 MHz Pentium III),  while the Det function from Mathematica still takes an unmeasurable amount of time. The timinig of Laplace method increases as n!:  9!/4! = 15120,  which is the same order of magnitude as the ratio of CPU times in the two calculations. Now let's try Mathematica's Det on a really large problem,  where Laplace's expansion would run forever (literaly, see below):

t1000 = rantab[1000] ;

Timing[Det[t1000]]

FormBox[RowBox[{{, RowBox[{RowBox[{14.631,  , Second}], ,, 1.120409970314435*10^744}], }}], TraditionalForm]

One has to go to a matrix size as large as 1000 to have Mathematica work for a few seconds.  Clearly,  it uses an algorithm different from Laplace's expansion.

One way to get the values of a determinant quickly without using Det is to diagonalize a matrix first:

Timing[Product[Eigenvalues[t9][[i]], {i, 9}]]

FormBox[RowBox[{{, RowBox[{RowBox[{0.,  , Second}], ,, RowBox[{RowBox[{-, 0.0498203}], +, RowBox[{1.24937*10^-19,  , }]}]}], }}], TraditionalForm]

So this method is much quicker than the Laplace's method.  However,  tried on a matrix of dimension 1000, it runs too long to wait for it.  Let's try size 100:

t100 = rantab[100] ;

Timing[Product[Eigenvalues[t100][[i]], {i, 100}]]

FormBox[RowBox[{{, RowBox[{RowBox[{4.717,  , Second}], ,, RowBox[{7.68895*10^24, +, RowBox[{1.55582*10^9,  , }]}]}], }}], TraditionalForm]

This is not bad taking into account that Laplace calculation would take 71*100!/9! = 10^152 seconds (this is quite a bit more than the age of the Universe which is now believed to be about 10^17 seconds).

Timing[Det[t100]]

FormBox[RowBox[{{, RowBox[{RowBox[{0.01,  , Second}], ,, 7.68895*10^24}], }}], TraditionalForm]

Thus, not suprisingly,  direct Det is much faster than going through diagonalization.


Created by Mathematica  (September 29, 2003)