On computing the determinant over a ring

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× 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.