The determinant of a matrix has a long history in mathematics. It is usually discussed along with Cramer’s rule for the solution of systems of linear equations. As late as the 1950s, the evaluation of 2×2 and 3×3 determinants was taught in high school algebra. For larger matrices, however, the value of the determinant is difficult to compute accurately. Most applications that use matrices don’t use determinants. Researchers in complexity and combinatorics, however, are still interested in the problem of computing the determinant, as well as other scalar functions of square matrices [1].
This paper presents a neat proof of an algorithm first proposed in a text on algorithm design [2]. The proof depends on a clever notation for minors of a matrix used by Knuth [1]. Unfortunately, there are a few typographical errors.
In the equation following “Expanding the determinant,” h appears without a definition. I believe that h should be replaced with k and that the equation should read:
ƒ[iα,jα] = aijƒ[α,α] - (Σ akjƒ[i(α\k),k(α\k)] k ∈ α)
Similarly, in the next equation, h should be replaced with k. Finally, in the equation after “it is therefore sufficient to show,” a factor akj should be added to each term in the two sums. With these changes, the proof goes through nicely.
This paper should be of interest to anyone who encounters determinants in their research. The algorithm and proof are deceptively simple and worth studying.