On the complexity of computing determinants

We present new baby steps/giant steps algorithms of asymptotically fast running time for dense matrix problems. Our algorithms compute the determinant, characteristic polynomial, Frobenius normal form and Smith normal form of a dense n × n matrix A with integer entries in \(\left( {n^{3.2} \log \left\| A \right\|} \right)^{1 + o(1)} \) and \(\left( {n^{2.697263} \log \left\| A \right\|} \right)^{1 + o(1)} \) bit operations; here \(\left\| A \right\|\) denotes the largest entry in absolute value and the exponent adjustment by “+o(1)” captures additional factors \(C_1 (\log n)^{C_2 } \left( {\log \log \left\| A \right\|} \right)^{C_3 } \) for positive real constants C₁, C₂, C₃. The bit complexity \(\left( {n^{3.2} \log \left\| A \right\|} \right)^{1 + o(1)} \) results from using the classical cubic matrix multiplication algorithm. Our algorithms are randomized, and we can certify that the output is the determinant of A in a Las Vegas fashion. The second category of problems deals with the setting where the matrix A has elements from an abstract commutative ring, that is, when no divisions in the domain of entries are possible. We present algorithms that deterministically compute the determinant, characteristic polynomial and adjoint of A with n^3.2+o(1) and O(n^2.697263) ring additions, subtractions and multiplications.

Authors and Affiliations

1. Department of Mathematics, North Carolina State University, Raleigh, NC, 27695-8205, U.S.A.

   Erich Kaltofen

2. Laboratoire LIP, École Normale Supérieure de Lyon, 46, Allée d’Italie, 69364, Lyon Cedex 07, France

   Gilles Villard

Corresponding author

Correspondence to Erich Kaltofen.

To B. David Saunders on the occasion of his 60th birthday

Reprints and permissions