Which method of matrix determinant calculation is this?

Question

This is the approach John Carmack uses to calculate the determinant of a 4x4 matrix. From my investigations i have determined that it starts out like the laplace expansion theorem but then goes on to calculate 3x3 determinants which doesn't seem to agree with any papers i've read.

 // 2x2 sub-determinants
 float det2_01_01 = mat[0][0] * mat[1][1] - mat[0][1] * mat[1][0];
 float det2_01_02 = mat[0][0] * mat[1][2] - mat[0][2] * mat[1][0];
 float det2_01_03 = mat[0][0] * mat[1][3] - mat[0][3] * mat[1][0];
 float det2_01_12 = mat[0][1] * mat[1][2] - mat[0][2] * mat[1][1];
 float det2_01_13 = mat[0][1] * mat[1][3] - mat[0][3] * mat[1][1];
 float det2_01_23 = mat[0][2] * mat[1][3] - mat[0][3] * mat[1][2];

 // 3x3 sub-determinants
 float det3_201_012 = mat[2][0] * det2_01_12 - mat[2][1] * det2_01_02 + mat[2][2] * det2_01_01;
 float det3_201_013 = mat[2][0] * det2_01_13 - mat[2][1] * det2_01_03 + mat[2][3] * det2_01_01;
 float det3_201_023 = mat[2][0] * det2_01_23 - mat[2][2] * det2_01_03 + mat[2][3] * det2_01_02;
 float det3_201_123 = mat[2][1] * det2_01_23 - mat[2][2] * det2_01_13 + mat[2][3] * det2_01_12;

 return ( - det3_201_123 * mat[3][0] + det3_201_023 * mat[3][1] - det3_201_013 * mat[3][2] + det3_201_012 * mat[3][3] );

Could someone explain to me how this approach works or point me to a good write up which uses the same approach?

NOTE
If it matters this matrix is row major.

Answer 1

It seems to be the method that involves using minors. The mathematical aspect can be found on wikipedia at

http://en.wikipedia.org/wiki/Determinant#Properties%5Fcharacterizing%5Fthe%5Fdeterminant

Basically you reduce the matrix to something smaller and easier to compute, and sum those results up (it involves some (-1) factors which should be described on the page i linked to).

Answer 2

He uses the standard formula where you can compute, in pseudocode,

det(M) = sum(M[0, i] * det(M.minor[0, i]) * (-1)^i)

Here minor[0, i] is a matrix you obtain by crossing out 0-th row and i-th column from your original matrix and (-1)*i stands for i-th power of -1.

The same (up to an overall sign) formula will work if you take a different row or if you make a loop over a column. If you think about how det is defined, it's pretty self-explanatory. Note how for 2-matrix this becomes:

det(M) = M[0, 0] * M[1, 1] * (+1) + M[0, 1] * M[1, 0] * (-1)

or, by row 1 rather then 0,

-det(M) = M[1, 0] * M[0, 1] * (+1) + M[1, 1] * M[0, 0] * (-1)

– you should recognize the standard formula for determinant of 2x2 matrix.

Similarly, for a 3-matrix composed as N = [[a, b, c], [d, e, f], [g, h, i]] this leads to the formula

det(N) = a * det([[e, f], [h, i]]) - b * det([[d, f], [g, i]]) + c * det([[d, e], [g, h]])

which of course becomes the textbook formula

a*e*i + b*f*g +  c*d*h - c*e*g - a*f*h - b*d*i

once you expand each of 2x2 determinants.

Now if you take a 4-matrix X, you will see that to compute det(X) you need to compute determinants of 4 minors, each minor being a 3x3 matrix; but you can also expand them further so you'll have the determinants of 6 2x2 matrices with some coefficients. You should really try it yourself similarly to what is above for 3x3 matrices.