Algorithm computes matrix determinants over rings without division

On computing the determinant over a ring

Symbolic ComputationComputational Complexity

Summary

Calculating the determinant of a matrix is key in many math and computer problems, but it can be tricky over general number systems called rings. The authors present an algorithm that computes the determinant and related polynomials purely using additions, subtractions, and multiplications—no division or checking for zeros needed. Their method cleverly reduces the matrix size step-by-step while controlling complexity, making the process efficient and predictable.

What this means in practice

  • For symbolic computation developers: Implement determinant and characteristic polynomial computations over rings without needing division operations, improving reliability in symbolic algebra systems.
  • For computer algebra system engineers: Optimize algorithms handling matrices over arbitrary rings by integrating division-free determinant calculations, enhancing mathematical software robustness.

Authors

Gilles Villard

Abstract

An algorithm is presented for computing the determinant and the characteristic polynomial of a matrix $A$ over an arbitrary commutative ring R. The algorithm uses $O(n^ω)$ ring additions, subtractions and multiplications, where $ω>2$ is a feasible exponent for matrix multiplication, that is, such that two $n\times n$ matrices over R can be multiplied using $O(n^ω)$ ring operations. The algorithm involves no division and no zero test, and its control depends only on $n$: for each $n$ it is a straight-line program. The approach combines a polynomial matrix point of view and a block Krylov point of view on the characteristic polynomial, which makes Strassen's elimination of divisions efficient. A bivariate matrix $λI-L(t)$, obtained from $A$ by a homotopy, is compressed in $\log n$ steps, each of which halves the dimension while only doubling the degree in $λ$. The cost of the homotopy is controlled by truncating the power series in $t$ at an order that only grows with the compression steps, from a constant to $n$.