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})$ (a theoretical upper bound; the practical standard is LU decomposition with pivoting, at $O(n^3)$).

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 (the formula holds when $\det(A) \neq 0$).

Cramer's rule is theoretically elegant, but computing $\det(A)$ directly from the definition requires summing $n!$ terms, so each of the $n+1$ determinants $\det(A)$ and $\det(A_1), \ldots, \det(A_n)$ costs $O(n \cdot n!)$, for $O(n^2 \cdot n!)$ in total. For $n = 20$, a single determinant already has $20! \approx 2.4 \times 10^{18}$ terms, 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 cofactors, that is, minors with signs attached. This is known as cofactor expansion (Laplace expansion).

Here $i$ is the fixed row used for the expansion, and $M_{ij}$ is the minor obtained by deleting row $i$ and column $j$. 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)$ (Widespread in the 19th Century)

4.1 Gauss and the Elimination Method (1809–1810)

Carl Friedrich Gauss used the elimination method systematically in 1809–1810 in computing the orbit of the asteroid Pallas (the normal equations of least squares), and from there it spread among human computers (hence the name "Gaussian elimination" today). The method itself is much older: it appears in the Chinese Nine Chapters on the Mathematical Art and in Newton (around 1670). Transforming a matrix into upper triangular form via elementary row operations and taking the product of the diagonal entries gives the determinant (swapping two rows flips the sign and scaling a row scales the determinant, so these are recorded). This takes only $O(n^3)$ operations.

The difference between $O(n!)$ and $O(n^3)$ is dramatic (the table compares $n!$ and $n^3$ directly, ignoring constant factors, as a rough guide):

Ignoring constant factors, $n!$ and $n^3$ cross near $n = 5$, the crossover point. Counting actual multiplications (including divisions), however, cofactor expansion takes $2, 9, 40, 205$ and elimination $3, 10, 23, 44$ (for $n = 2$ to $5$), so cofactor expansion uses fewer for $n \leq 3$ and elimination uses fewer for $n \geq 4$. 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" (in his 1801 Disquisitiones Arithmeticae, for the discriminant of a quadratic form, 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

In the 20th century, Gaussian elimination was formalized as LU decomposition, which became central to numerical computation with the advent of computers. 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:

LU decomposition was introduced in 1938 by the Polish astronomer Tadeusz Banachiewicz. In 1948, Alan Turing analysed the rounding errors of elimination and LU decomposition, and it became widely recognized that in floating-point arithmetic partial pivoting, choosing at each step the entry of largest absolute value in the current column as the pivot, is important for numerical stability (it works stably for most matrices, though not for every matrix). Because rows are swapped, the factorization becomes $PA = LU$ ($P$ a permutation matrix), and with the diagonal of $L$ set to 1, $\det(A) = \operatorname{sgn}(P) \prod_{i=1}^{n} u_{ii}$ (the sign flips when the number of row swaps is odd).

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: the infimum of the exponents such that, for every $\varepsilon > 0$, two $n \times n$ matrices can be multiplied in $O(n^{\omega + \varepsilon})$ operations. $O(n^\omega)$ itself is not necessarily attained, but following convention we write $O(n^\omega)$.

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 record as of 2024, $\omega < 2.3714$, 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 (in the sense of algebraic complexity) 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 elimination (named after Gauss), improving 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 major open problems in theoretical computer science and algebraic complexity, and research continues to this day.

Frequently asked questions