History of Determinant Computation

1. Introduction

Computing the determinant of an $n \times n$ matrix -- this problem has captivated mathematicians and computer scientists for over 340 years. Since Seki Takakazu and Leibniz discovered the concept of determinants as a tool for solving systems of equations in the 17th century, computational complexity has been dramatically reduced from $O(n!)$ to $O(n^3)$, and then to $O(n^{2.371\ldots})$.

This article surveys when and how determinant computation methods evolved, and organizes the genealogy of these methods in a systematic diagram.

2. The Dawn: From Systems of Equations to Determinants (17th Century)

2.1 Seki Takakazu (1683)

The history of determinants begins with the Japanese mathematician Seki Takakazu. In his 1683 work Kai Fukudai no Ho (Method of Solving Hidden Problems), Seki independently developed computational techniques equivalent to determinants for solving systems of equations.

Although Seki did not use the term "determinant," he provided general methods for computing the determinant of $2 \times 2$, $3 \times 3$, $4 \times 4$, and $5 \times 5$ matrices. This predates Leibniz's work by approximately 10 years.

2.2 Leibniz (1693)

In Europe, Gottfried Wilhelm Leibniz described in a 1693 letter to l'Hôpital the conditions for a system of equations to have a solution using determinant-like expressions. Leibniz represented coefficients with double subscripts $a_{ij}$ and described the conditions for the existence of solutions through combinations of products and signs.

The work of Seki and Leibniz was completely independent, making it a remarkable case of Eastern and Western mathematics arriving at the same concept simultaneously.

3. The Age of Formulas (18th Century)

3.1 Cramer's Rule (1750)

Gabriel Cramer published in his 1750 work a formula expressing the solution of a system of $n$ linear equations in terms of determinants.

Here $A_j$ is the matrix obtained by replacing the $j$-th column of the coefficient matrix $A$ with the constant terms.

Cramer's rule is theoretically elegant, but computing $\det(A)$ directly from the definition requires summing $n!$ terms, resulting in $O(n \cdot n!)$ operations for $n$ unknowns. For $n = 20$, approximately $20! \approx 2.4 \times 10^{18}$ operations are needed, making it impractical not only by hand but even by computer.

3.2 Laplace Expansion (1772)

Pierre-Simon Laplace gave in 1772 a general method for expanding a determinant in terms of complementary minors. This is known as cofactor expansion (Laplace expansion).

This recursive method is structurally clear and is often used in theoretical proofs. However, the computational complexity is recursively $T(n) = n \cdot T(n-1)$, which ultimately yields $O(n!)$.

Note that in 1771, Vandermonde was the first to treat determinants as independent mathematical objects rather than mere accessories of systems of equations. This was an important turning point in the development of determinant theory.

4. Gaussian Elimination: From $O(n!)$ to $O(n^3)$ (19th Century)

4.1 Gauss's Elimination Method (1801)

Carl Friedrich Gauss systematized the elimination method in his 1801 Disquisitiones Arithmeticae. The technique of transforming a matrix into upper triangular form via elementary row operations and computing the determinant as the product of diagonal entries reduced the complexity in one stroke to $O(n^3)$.

The difference between $O(n!)$ and $O(n^3)$ is dramatic:

For $n \leq 4$, $n!$ is actually smaller, and Laplace expansion is perfectly adequate. $n = 5$ is the crossover point, where both methods require roughly the same amount of computation. For $n \geq 10$, the gap widens rapidly, and the superiority of Gaussian elimination becomes overwhelming. In other words, "$O(n^3)$ is not always faster" -- for small matrices, direct expansion from the definition suffices, and the power of elimination manifests as $n$ grows.

Gauss was also one of the first to use the word "determinant" (though in a somewhat different context from today's usage).

Determinant computation via elimination is discussed in detail in Deriving the Determinant: Row Reduction and Upper Triangular Matrices.

4.2 Cauchy and the Systematization of Determinants (1812)

Augustin-Louis Cauchy systematically organized determinant theory in his 1812 paper "Mémoire sur les fonctions qui ne peuvent obtenir que deux valeurs égales et de signes contraires par suite des transpositions opérées entre les variables qu'elles renferment," establishing the term "determinant" in its modern sense. He proved many fundamental properties in this paper, including the symmetry of rows and columns and the multiplicativity of determinants ($\det(AB) = \det(A)\det(B)$).

4.3 Dodgson Condensation (1866)

Charles Dodgson, better known as Lewis Carroll, the author of Alice's Adventures in Wonderland, published in 1866 a method called condensation. Based on the Desnanot-Jacobi identity, it computes the determinant by successively reducing the matrix. The complexity is $O(n^3)$, but it represents an interesting alternative approach to Gaussian elimination. However, it suffers from numerical instability due to potential division by zero at intermediate steps.

5. The Computer Era: LU Decomposition and Numerical Stability (20th Century)

5.1 LU Decomposition and Partial Pivoting

With the advent of computers in the 20th century, Gaussian elimination was formalized as LU decomposition. A matrix $A$ is factored into the product of a lower triangular matrix $L$ and an upper triangular matrix $U$:

The determinant can then be computed as the product of diagonal entries:

In 1948, Alan Turing introduced partial pivoting, greatly improving numerical stability. In floating-point arithmetic, rounding errors accumulate, making it essential to select the largest element as the pivot at each step.

5.2 LAPACK and Practical Implementations

LU decomposition became a core algorithm in LAPACK (Linear Algebra PACKage) and is used as the standard method in major numerical computing environments such as NumPy, MATLAB, and Julia. With $O(n^3)$ complexity and small constant factors, it is the most widely used method in practice.

5.3 The Bareiss Algorithm (1968)

Erwin Bareiss published in 1968 a fraction-free elimination method. For integer matrices, it performs computations entirely in the integers, avoiding the introduction of fractions at intermediate stages.

Standard Gaussian elimination involves division, so even for integer matrices, rational numbers appear as intermediate results. The Bareiss algorithm maintains integer values throughout by incorporating appropriate divisions. The complexity remains $O(n^3)$, but it is particularly valuable in symbolic computation.

6. The Dawn of Fast Algorithms (1969--)

6.1 The Strassen Breakthrough (1969)

In 1969, Volker Strassen published a groundbreaking algorithm that performs matrix multiplication faster than $O(n^3)$. While the standard product of $2 \times 2$ matrices requires 8 multiplications, Strassen reduced this to 7 through an ingenious combination of operations.

Applying this recursively yields:

This overturned the long-held belief that $O(n^3)$ was optimal, demonstrating that the "$O(n^3)$ barrier" does not exist.

6.2 Computational Equivalence of Determinants and Matrix Multiplication

Determinant computation can be reduced to matrix multiplication. Specifically:

• LU decomposition can be performed in the same $O(n^\omega)$ complexity as matrix multiplication (Block LU decomposition)
• The determinant is the product of diagonal entries of LU decomposition, so it is also $O(n^\omega)$
• The matrix inverse is also $O(n^\omega)$ (Bunch-Hopcroft, 1974)

Here $\omega$ is called the matrix multiplication exponent, where $O(n^\omega)$ denotes the order of computation required to multiply two $n \times n$ matrices.

6.3 Historical Progress on $\omega$

Since Strassen, intensive research has been devoted to lowering the upper bound on $\omega$:

7. The Cutting Edge: Is $\omega = 2$ Achievable?

7.1 Theoretical Lower Bound

The product of two $n \times n$ matrices has $n^2$ entries. Since the inputs consist of $2n^2$ entries, simply reading all of them requires $\Omega(n^2)$ computation. Therefore:

There remains a gap between the current best record $\omega \leq 2.3713\ldots$ and the lower bound $\omega \geq 2$. Many researchers conjecture that $\omega = 2$ holds, but it has not been proven.

7.2 The Practicality Barrier

The theoretically best algorithm is not necessarily practical. Fast algorithms since Strassen share common challenges:

• Huge constant factors: The constants hidden in $O$ notation are extremely large, so the theoretical advantage manifests only for astronomically large matrices (galactic algorithm)
• Numerical stability: Fast algorithms tend to be numerically unstable
• Memory efficiency: Recursive subdivision complicates memory access patterns

In practice, for matrices of size a few hundred to a few thousand, LAPACK's LU decomposition ($O(n^3)$) is the fastest, and even for very large matrices, Strassen's algorithm ($O(n^{2.807})$) is the practical limit. The $O(n^{2.37\ldots})$ algorithms have never been used in practice.

8. Genealogy: Three Lineages

Determinant computation methods can be broadly classified into three lineages.

The relationships among the three lineages can be summarized as follows:

• Lineage 1 (definition-based) has $O(n!)$ complexity and is inefficient, but remains active in theoretical discussions and proofs
• Lineage 2 (elimination-based) runs in $O(n^3)$ and is the practical standard
• Lineage 3 (fast matrix multiplication-based) achieves $O(n^{2.37\ldots})$ in theory but has not reached practical use
• Lineages 2 and 3 are theoretically equivalent through block LU decomposition: speeding up matrix multiplication directly translates to faster LU decomposition

9. Summary

Looking back over 340 years of history, determinant computation has progressed through three stages: "factorial time to polynomial time to the pursuit of theoretical limits." The first revolution was Gauss's improvement from $O(n!)$ to $O(n^3)$, and the second was Strassen's breaking of the $O(n^3)$ barrier. Whether $\omega = 2$ can be achieved remains one of the greatest open problems in mathematics and computer science, and research continues to this day.