On computing the determinant over a ring

arXiv:2611.07786 · cs.SC, cs.CC · Submitted 2026-11-05 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "On computing the determinant over a ring".

Jane: Here's the gist of the paper. An algorithm is presented for computing the determinant and the characteristic polynomial of a matrix A over an arbitrary commutative ring R where divisions are not available, which is significant because it achieves a complexity bound of O˜(nω+1) ring operations and demonstrates that divisions do not essentially help for computing the determinant.

Tom: The core result on division-free computation The paper shows that divisions do not essentially help for computing the determinant over a commutative ring R with unit.

Jane: Algorithm 1.1 computes the characteristic polynomial of A, hence its determinant, using O(n ω) ring operations.

Tom: This result is notable because known algorithms for the determinant over a field rely on divisions and zero tests.

Title and authors: Tom: So, we're looking at this paper called "On computing the determinant over a ring," and it tackles a problem where you can't use division or zero tests to find the determinant of a matrix A when you're working over some general commutative ring R.

Jane: That sounds really interesting, Tom. It seems like they are trying to figure out if those divisions are actually necessary for this kind of calculation, because we know that for fields, divisions make things pretty straightforward.

Tom: Exactly. The main point they are making is that you can compute the characteristic polynomial and then the determinant using only additions, subtractions, and multiplications over a ring R with a unit. They claim this works in time O of n omega ring operations where omega is greater than two, which is when matrix multiplication itself becomes efficient.

Lu: What’s compelling here is how they combine two different ideas to achieve this. They start with thinking about the characteristic polynomial using a polynomial matrix approach, which involves halving the dimension in logarithmic steps while doubling the degree of lambda, and then they mix that with Coppersmith’s block Wiedemann approach.

Meng: So it's like they are running this block Krylov sequence at several levels, where each level is smaller but the polynomial degree gets bigger, and they keep doing this until the cost stays manageable. I wonder if that still scales well when you try to deploy it on a massive system where you need real-time answers.

Jane: That’s a good question about scale. The paper suggests that by truncating the power series for the homotopy variable t at an order that grows with these compression steps, they keep the cost under O of n omega operations when omega is greater than two, which is pretty good news if you're worried about computation time.

Tom: It does sound promising because it keeps the complexity bound tied to n and omega directly, without those extra logarithmic factors that often sneak in when you use some other methods. They show that divisions don't fundamentally help when you are just trying to compute the determinant itself over a ring R with a unit.

Lu: And they set up this bivariate matrix lambda I minus L of t, which is what they call a homotopy, and they compress it in log n steps to control the cost of calculating that whole thing. This structure seems key to making the computation work without needing those tricky divisions.

Jane: So for someone listening who doesn't read math, what does this mean practically? It suggests that even if you are working with matrices over a complicated ring where division isn't allowed, you can still get the determinant by using just basic arithmetic and clever matrix manipulations.

Title and authors: Meng: From my side, I’m looking at the practical cost. The paper says the total cost is dominated by the first level of this compression, which they set up around m equals n, giving them that O of n omega when omega is greater than two. That means for large matrices, it stays within bounds if your matrix multiplication itself scales nicely with omega.

Tom: It’s a strong result because it shows that divisions aren't an intrinsic advantage here; the complexity is controlled by the matrix multiplication cost, not by division tests or field properties. They prove that Algorithm one point one computes the characteristic polynomial and hence the determinant using only additions, subtractions, and multiplications over R with no division or zero test needed for each step <ref:2611.07786#pg1>.

Jane: That’s a big deal because in many practical applications, especially when dealing with structured matrices or certain types of rings, you simply don't have access to division anyway. This result opens up a whole new toolbox for those scenarios.

Lu: And they set up this block Hankel matrix H and show that at zero value of t, that block Hankel matrix is a permutation matrix over the ring S, which means it’s invertible without needing division for the lifting part of their method.

Meng: I see the structure there. If you can prove something is invertible without division, you remove a major computational hurdle in these iterative methods. That makes sense from an engineering standpoint; less branching code and simpler arithmetic is always better at scale.

Tom: So they are using this invertibility property to lift the sequence terms in t without needing any divisions, which keeps the entire process running smoothly within those O of n omega bounds they established for the characteristic polynomial computation.

Jane: It sounds like a very elegant way to bypass the need for division by using structural properties of these matrices rather than relying on field axioms. This whole paper, "On computing the determinant over a ring," is about showing that some basic arithmetic operations are all you need.

Lu: And they did this by combining the polynomial matrix view and Coppersmith’s block Wiedemann approach into this combined algorithm to manage both the degree growth in lambda and the sequence generation in t.

Meng: It’s a hybrid approach, essentially taking the best parts of two different ways of looking at it—the polynomial structure and the block Krylov sequence—and stitching them together to get a solid complexity bound. I wonder if that combination is robust enough for real-world matrices that aren't perfectly structured.

Jane: That robustness is what they are aiming for, but the paper itself focuses on proving it works over an arbitrary commutative ring R with a unit, which is quite general. They show this algorithm computes the bivariate polynomial D of lambda and t, which ultimately gives you the determinant.

Title and authors: Tom: And that final step of recovering the determinant from that bivariate polynomial D of lambda and t is free; it’s just a multiplication by a simple constant factor involving n, so no division or zero test there either.

Lu: So to summarize, they've presented an algorithm that computes the characteristic polynomial and therefore the determinant over any commutative ring R with unit using only additions, subtractions, and multiplications in O of n omega operations when omega is greater than two.

Meng: If you were deploying this today, you’d be looking at a system where you can't afford division or zero tests during the core computation of the determinant, and this paper gives you a path to do it efficiently with ring arithmetic.

Jane: And that path involves using a homotopy variable t and carefully controlling how much you truncate the power series in t based on how many steps of compression you take, which keeps the cost under O of n omega when omega is greater than two.

Tom: It really highlights that divisions don't bring an intrinsic advantage for this kind of computation; the complexity is driven by what we can multiply matrices with, which they bound by omega.

Lu: They also mention that for the case where omega equals two, the analysis gives a slightly higher cost of O of n squared log three n log log n operations in R, but they still manage to show this is manageable and not as bad as you might think for the general case.

Jane: So it’s about showing that even if you hit that omega equals two scenario, the complexity is still polynomial in a controlled way, which is important for real-world performance guarantees. This whole paper, "On computing the determinant over a ring," gives us tools to handle determinants in environments where division isn't an option.

Tom: It’s definitely a piece of theory that sets some clear boundaries on what we can expect from determinant calculations in these restricted settings, showing that O of n omega is achievable without relying on division for the main work.

Lu: And it points towards future work, where they mention exploring how this framework might apply to more complex matrix structures or perhaps even extending the result to different types of rings or rings without units.

Meng: For deployment, I’d say this means we can potentially build systems that handle these determinant calculations in environments where division is strictly forbidden during the critical phase.

Jane: So that's what we have here today with "On computing the determinant over a ring," showing how to compute determinants without divisions by using additions, subtractions, and multiplications in O of n omega operations when omega is greater than two.

The paper's summary: Tom: So, basically this paper is about finding the determinant of a matrix when you're working over some general commutative ring, which means you can't just use simple division or zero tests like you do with numbers in a field.

Jane: That’s right. The authors are showing that even without those tools, you can still compute the characteristic polynomial and then the determinant using only basic multiplication, addition, and subtraction over that ring.

Tom: They’re using this clever combination of two ideas to make it work. One idea is thinking about the matrix through a polynomial lens where you compress the dimension in logarithmic steps while doubling the degree of lambda.

Jane: And they combine that with a block Krylov sequence approach, which is like running a specific type of iterative process on blocks of that matrix, but they do it at several levels without having to restart everything over and over.

Tom: The key result is that if you use this method correctly, you get the characteristic polynomial in time O of n omega ring operations when omega is greater than two. That means the speed depends on how fast you can multiply those matrices together, which we know how to handle efficiently if omega is bigger than two.

Jane: It’s really interesting because it shows that divisions aren't actually necessary for this calculation to work in a general ring setting, which is a big thing since many real-world systems don't even allow you to divide numbers easily.

Tom: Exactly. The paper sets up this bivariate polynomial, which is like a combined function of lambda and some variable t, and that final step to get the determinant from that function is free; it just involves multiplying by a constant factor related to n.

Jane: So what this means for us listening, it suggests we can find the determinant in these restricted environments using only multiplication and addition without ever needing those division operations we usually rely on.

Tom: It really pushes back on the idea that divisions are an essential part of computing determinants in general settings; the complexity is driven by the matrix multiplication cost itself.

Jane: And they also showed that there's a specific structure, like a block Hankel matrix, that at zero value of t becomes invertible over some set, which lets them lift their calculations in t without needing any divisions for that part either.

Tom: So to sum it up, they’ve got an algorithm to compute the characteristic polynomial and thus the determinant over any commutative ring with a unit using only ring arithmetic in O of n omega operations when omega is greater than two.

Jane: It’s a solid result showing how structural properties can replace divisions in these kinds of complex computations, so keep an ear out for how this technique might show up in other hard problems.

The paper's improvements: Tom: So, we've heard that the main result is that you can compute the characteristic polynomial in time O of n omega ring operations when omega is greater than two, which is pretty clean if your matrix multiplication scales nicely.

Jane: Right, and what they suggest next is how to make that even more practical by combining different approaches to keep those costs down.

Tom: They propose running the Coppersmith scheme at several levels without recomputing the sequence at each level, basically a hybrid approach between thinking about the polynomial structure and using that block Krylov sequence idea.

Jane: So they’re trying to manage both the growth of that lambda degree and how fast the sequence terms generate something, which sounds like a lot of moving parts.

Tom: The cost analysis shows that by carefully truncating the power series for the variable t based on how many levels you run, they keep everything under those O of n omega bounds when omega is greater than two.

Jane: That means they’re not just doing one big calculation; they’re using a series of smaller, manageable steps where each step has a controlled cost.

Tom: And there's this part about the block Hankel matrix, which they prove at zero value of t is invertible over some set, and that’s what lets them lift the sequence terms in t without needing any divisions for that specific part.

Jane: So it sounds like they’re using those structural properties—the invertibility of the Hankel matrix—to bypass division in a way that keeps the overall complexity manageable.

Tom: That's exactly it; they're showing that you can use those structural facts to replace divisions with just multiplications and additions over the ring R.

Jane: It’s pretty neat because it shows how a specific algebraic structure in the matrix—that Hankel matrix—can unlock division-free computation in a setting where divisions are usually forbidden.

Tom: And they also mentioned that for the case where omega equals two, the analysis gives a higher cost of O of n squared log three n log log n operations in R, but they still manage to show this is polynomial and not as bad as you might think for the general case.

Jane: So it’s important to remember that while the omega greater than two case is better, they've done their best to show that even when things are harder—when omega equals two—the complexity stays within a controllable polynomial bound.

Tom: It’s a good thing because for anyone trying to deploy this kind of computation, knowing what the worst-case scaling looks like helps you plan your resources.

Jane: And they leave it open by talking about future work, suggesting how this framework might apply to even more complicated matrix structures or different types of rings down the road.

Conclusion: Tom: So we've just covered how they compute the determinant over a ring using matrix multiplication instead of division, which is pretty clean for many applications.

Jane: Right, and essentially they’re proving that you don't need those division tests to get a result when working over an arbitrary commutative ring with a unit.

Tom: It’s about showing that even though the setting is general, the complexity remains bounded by O of n omega ring operations when omega is greater than two.

Jane: That means for engineers worried about speed and reliability, if their matrix multiplication scales well with omega, they can get a deterministic bound on how long it will take.

Lu: I think the real shift here is in the methodology; combining the polynomial matrix view with Coppersmith’s block Wiedemann approach is a smart way to handle both the degree growth and the sequence generation simultaneously.

Tom: It's an elegant hybrid that manages complexity better than either approach on its own, which is what I find exciting about clean algorithmic design.

Jane: And they use that structural property of the block Hankel matrix being invertible at zero value of t to avoid division in the sequence lifting steps, which is a clever trick.

Lu: It’s a solid way to handle those sequence terms without introducing divisions, which is exactly what you need when you're constrained by ring arithmetic.

Tom: So they’ve shown that this specific combination works and gives them that clean O of n omega bound for the characteristic polynomial computation.

Jane: The paper, "On computing the determinant over a ring," provides a new toolset for people working with matrices where division isn't an option but you still need to find a determinant.

Tom: Exactly, it’s about using only additions, subtractions, and multiplications over the ring R without needing those expensive division operations.

Jane: It opens up possibilities for systems where divisions are simply not allowed in the core computation phase, which is a big win for certain types of mathematical modeling.

Lu: If this technique can be generalized to more complex matrix structures or different rings down the line, it could have serious implications for representation learning and algebraic geometry.

Tom: We'll see if that generalization holds up in future work; right now, the focus is on proving this works over any commutative ring with a unit.

Jane: It’s a great piece of theoretical work showing how deep structural analysis can replace basic arithmetic operations in computation.

CNRS · ENS de Lyon · inria · U. Claude Bernard Lyon 1 · LIP UMR 5668

cs.SC, cs.CC

Submitted: 2026-11-05

Updated: 2026-11-05

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 98/100

The gist: An algorithm is presented for computing the determinant and the characteristic polynomial of a matrix A over an arbitrary commutative ring R where divisions are not available…

Key concepts

Characteristic Polynomial
This is a polynomial whose roots are the eigenvalues of a square matrix A. Computing it is equivalent to finding the determinant, but it provides more structural information about the matrix than just its final value.
Homotopy Variable (t)
A variable 't' is introduced into a matrix expression, creating a family of matrices L(t). By keeping sequence terms exact while truncating the generating polynomial modulo t^4d, this variable allows for computations that avoid divisions by controlling the precision needed.
Block Hankel Matrix
This is a specific structure formed by arranging sequences of matrix blocks. The paper shows this matrix behaves like a permutation matrix at t=0, which is crucial because it guarantees invertibility over the ring S, allowing for lifting computations without needing divisions.
Ring Operations (Division-Free)
The algorithm is designed to operate only with ring additions, subtractions, and multiplications. This means it avoids division and zero tests entirely. This demonstrates that computing the determinant over a general commutative ring can be done efficiently without relying on division.

Terminology

Summary

An algorithm is presented for computing the determinant and the characteristic polynomial of a matrix A over an arbitrary commutative ring R where divisions are not available, which is significant because it achieves a complexity bound of O˜(nω+1) ring operations and demonstrates that divisions do not essentially help for computing the determinant. p. 0

Where the paper says it

The algorithms achieving these bounds, Gaussian elimination for the determinant [6] and the polynomial matrix approach of [25] for the characteristic polynomial (see also [20, 27]), use divisions and zero tests, for choosing nonzero pivots and, more generally, for computing rank profiles. Over a commutative ring, where divisions are not available, the determinant and the characteristic polynomial can be computed using O˜(n ω+1 ) ring operations, where O˜ hides logarithmic factors.

The core result on division-free computation

The paper shows that divisions do not essentially help for computing the determinant over a commutative ring R with unit. Algorithm 1. p. 0

Where the paper says it

On computing the determinant over a ring Gilles Villard CNRS, ENS de Lyon, Inria, U. Claude Bernard Lyon 1, LIP UMR 5668, 69342, Lyon cedex 07, France Abstract An algorithm is presented for computing the determinant and the characteristic polynomial of a matrix A over an arbitrary commutative ring R.

p. 0
Where the paper says it

On computing the determinant over a ring Gilles Villard CNRS, ENS de Lyon, Inria, U. Claude Bernard Lyon 1, LIP UMR 5668, 69342, Lyon cedex 07, France Abstract An algorithm is presented for computing the determinant and the characteristic polynomial of a matrix A over an arbitrary commutative ring R.

1 computes the characteristic polynomial of A, hence its determinant, using O(n ω) ring operations. p. 1
Where the paper says it

For A ∈ R n×n , Algorithm 1. 1 computes the characteristic polynomial of A, hence its determinant, using O(n ω ) ring operations (Theorem 5.

This result is notable because known algorithms for the determinant over a field rely on divisions and zero tests. p. 0
Where the paper says it

The same bound holds for the characteristic polynomial [25]. The algorithms achieving these bounds, Gaussian elimination for the determinant [6] and the polynomial matrix approach of [25] for the characteristic polynomial (see also [20, 27]), use divisions and zero tests, for choosing nonzero pivots and, more generally, for computing rank profiles.

The algorithmic approach combining viewpoints

The approach reconciles two points of view. On one side, the polynomial matrix approach starts from λI − A, following a divide-and-double principle where the dimension is halved in O(log n) steps while the degree doubles. p. 1

Where the paper says it

On one side, the polynomial matrix approach to the determinant [13, 25] starts from λI − A, an n × n matrix of degree one, and follows a divide-and-double principle. In O(log n) steps, the dimension is halved while the degree only doubles, so that the amount of data stays O(n 2 ) and each step costs a few matrix products.

On the other side, Coppersmith’s block Wiedemann approach works with a block Krylov sequence and uses Strassen’s technique to avoid divisions by replacing A with a matrix L(t) of degree one in t. p. 1
Where the paper says it

These algorithms use divisions and zero tests, and we do not see how to apply a homotopy a la Strassen to them without losing a factor about ` n. On the other side, Coppersmith’s block Wiedemann approach [10], in its division-free version by [19], works with the block Krylov sequence {X TA kY}k≥0 of a pair of projections X, Y ∈ R n×m, from which the characteristic polynomial is recovered as the determinant of an m × m matrix generating polynomial of degree about n/m (Section 1.

The two views are combined using two ideas. p. 1
Where the paper says it

With this homotopy, the 2n/m terms of the sequence are computed by baby steps and giant steps on power series truncated at order n + 1. We combine the two points of view, with two ideas (Section 1.

The mechanism of the combined algorithm

The first idea involves running the scheme of [19] at log n successive levels, halving the block size while doubling the degree in λ. The second idea concerns the homotopy variable t, where sequence terms are kept exact while the generating polynomial is truncated modulo t 4d. p. 1

Where the paper says it

The second idea concerns the homotopy variable t: the terms of the sequence that are used are kept exact, while the generating polynomial is truncated. The terms of the sequence at level m, with d = n/m, are polynomials in t of degree less than 4d, and the generating polynomial, whose coefficients are power series in t, is only needed modulo t 4d : all the computations at level m are truncated at order 4d instead of n + 1.

The cost of a level decreases geometrically with m, up to logarithmic factors when ω > 2, summing to O(n ω). p. 1
Where the paper says it

The terms of the sequence at level m, with d = n/m, are polynomials in t of degree less than 4d, and the generating polynomial, whose coefficients are power series in t, is only needed modulo t 4d : all the computations at level m are truncated at order 4d instead of n + 1. The amount of data at each level is O(n 2 ), and the cost of a level decreases geometrically with m, up to logarithmic factors, when ω > 2, and sums to O(n ω ).

The final complexity bound and theorem

Theorem 5.1 states that if ω > 2, Algorithm 1. p. 0

Where the paper says it

On computing the determinant over a ring Gilles Villard CNRS, ENS de Lyon, Inria, U. Claude Bernard Lyon 1, LIP UMR 5668, 69342, Lyon cedex 07, France Abstract An algorithm is presented for computing the determinant and the characteristic polynomial of a matrix A over an arbitrary commutative ring R.

1 computes the characteristic polynomial of A using O(n ω) operations in R. p. 1
Where the paper says it

For A ∈ R n×n , Algorithm 1. 1 computes the characteristic polynomial of A, hence its determinant, using O(n ω ) ring operations (Theorem 5.

p. 1
Where the paper says it

For A ∈ R n×n , Algorithm 1. 1 computes the characteristic polynomial of A, hence its determinant, using O(n ω ) ring operations (Theorem 5.

For the case ω = 2, the analysis gives O(n squared log3 n log log n) operations. p. 1
Where the paper says it

1), the matrix multiplication algorithm being used as a black box (Section 1. For ω = 2, the same analysis gives O(n 2 log3 n log log n) operations.

The cost is dominated by the first level m = n, giving O(n ω) when ω > 2. p. 3
Where the paper says it

The cost is thus m ωd 2 , up to factors logarithmic in d. The total cost is dominated by the first level m = n, where d = 1, which gives O(n ω ) when ω > 2.

p. 3
Where the paper says it

The cost is thus m ωd 2 , up to factors logarithmic in d. The total cost is dominated by the first level m = n, where d = 1, which gives O(n ω ) when ω > 2.

The structure of the characteristic polynomial recovery

The algorithm starts with the homotopy L(t) = M − tAM in R[t] n×n. The characteristic polynomial is recovered after a multiplication by the unit series (1 − t)−(n′−n) modulo t n+1. p. 3

Where the paper says it

The characteristic polynomial is thus recovered after a multiplication by the unit series (1 − t) −(n ′−n) modulo t n+1 . The padding multiplies the cost of the algorithm by at most a constant factor.

The final determinant is found by D(1)(λ, t) = det(λI − L(t)). p. 9
Where the paper says it

2, which is O(n ω ) for ω > 2, and the final reversal is free. In particular, det A is (−1)n times the constant term of the characteristic polynomial, and Algorithm 1.

The computational cost analysis

The total cost is dominated by the first level m = n, where d = 1, which gives O(n ω) when ω > 2. The cost of each iteration in Step 2 is bounded by O(m ωM(dσ)(1 + logσ)) operations in R. p. 8

Where the paper says it

, H2d−1) T , and let σ ≥ 1. The generating polynomial D(m) modulo tσ can be computed using O(m ωM(dσ)(1 + logσ)) operations in R.

The final step costs O(M(n 2) log n) by Lemma 4. p. 9
Where the paper says it

Step 3 costs O(M(n 2 ) log n) by Lemma 4. 2, which is O(n ω ) for ω > 2, and the final reversal is free.

2, which is O(n ω) for ω > 2.

The structure of the block Hankel matrix and its properties

The block Hankel matrix H is defined as H = O C = [H0 H1 · · · Hd−1 H1 H2 · · · Hd]. Lemma 3.2 shows that for the chosen projections, the block Hankel matrix H is a permutation matrix at t = 0, hence invertible over S. p. 3

Where the paper says it

The projections Xm and Ym are made of unit vectors at well chosen positions, whose interleaving allows for an efficient transition from level m to level m/2. With this choice the block Hankel matrix of the sequence is a permutation matrix at t = 0, at every level (Section 3).

This invertibility allows for the lifting in t to proceed without divisions. p. 3
Where the paper says it

With this choice the block Hankel matrix of the sequence is a permutation matrix at t = 0, at every level (Section 3). The minimal generating polynomial is then the solution of a linear system whose constant term is invertible, which is solved by lifting in t, without divisions.

The extraction of sequence terms

Lemma 3.1 proves that the entries of XT mLkYm are polynomials in t of degree at most k. p. 3

Where the paper says it

A level m first consists of a lifting process, to compute the truncated generating polynomial, followed by a Newton iteration to extend the sequence. Both are divide-and-conquer processes whose aggregate work, summed over their O(log d) recursion depths, is equivalent to that of O(log d) products of m × m matrices whose entries are bivariate polynomials of degree O(d) both in λ and in t, that is, with O(d 2 ) coefficients.

This property allows for truncation at the right orders, as degt Hk ≤ k. p. 6
Where the paper says it

- The sequence terms X T mL kYm at level m/2 are extracted from those at level m by selecting rows and columns, and they satisfy degt (X T mL kYm) ≤ k (Lemma 3. 1), which allows the truncation at the right orders in Section 4.

The extraction step (Step 3) requires no arithmetic operation by Lemma 3. p. 9
Where the paper says it

The last step of the transition is the extraction of the sequence at level m/2 (Step 2c), which requires no arithmetic operation by Lemma 3. Algorithm 4.

1.

The final reconstruction of the determinant

At the last level m = 1, d = n, D(1) is det(λI − L) by Lemma 2.2. The constant coefficient D(1)0 = (−1)n det L = (−1)n det(I − tA), and the characteristic polynomial is recovered as λn c(1/λ) = det(λI − A). p. 2

Where the paper says it

1 computes the bivariate polynomial det(λI − L(t)) ∈ R[λ, t], which is monic of degree n in λ and of degree at most n in t. Its constant coefficient in λ is (−1)n det L(t) = − det(I − tA), and the characteristic polynomial of A is the reversal λ n det(I − A/λ) of the latter.

The algorithm computes the bivariate polynomial D(1) = det(λI − L(t)) ∈ R[λ, t]. p. 2
Where the paper says it

Algorithm 1. 1 computes the bivariate polynomial det(λI − L(t)) ∈ R[λ, t], which is monic of degree n in λ and of degree at most n in t.

p. 2
Where the paper says it

Algorithm 1. 1 computes the bivariate polynomial det(λI − L(t)) ∈ R[λ, t], which is monic of degree n in λ and of degree at most n in t.

The role of the black box matrix multiplication

The algorithm uses a fixed algorithm which multiplies two n × n matrices over R using O(n ω) ring operations as a black box. This bound is insensitive to logarithmic factors and holds for any M(h) = O(h ω/2−ε) with ε > 0. p. 4

Where the paper says it

The finer count of [8], O(h log h) coefficient products only, is not needed here: the bound O(n ω ) of Theorem 5. 1 is insensitive to these logarithmic factors, and holds for any M(h) = O(h ω/2−ε ) with ε > 0.

The result is that Algorithm 1. p. 1
Where the paper says it

Divisions are avoided by Strassen’s technique: A is replaced by a matrix L(t) of degree one in t with L(0) = M, a fixed matrix for which all the elements inverted by the algorithm with divisions are known units of R. The computations are then done on power series in t, where these elements remain invertible, and the result is read on det(λI − L(t)), a polynomial of degree at most n in t.

1 only uses ring additions, subtractions and multiplications, with no division and no zero test. p. 0
Where the paper says it

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 comparison with other methods

The paper contrasts its approach with known algorithms like the O(n ω) triangular factorization of Bunch and Hopcroft [6] which relies on pivoting. The authors argue that they do not see how to apply a homotopy a la Strassen to these methods without losing a factor about n. p. 1

Where the paper says it

It is also close to the doubling of the Krylov chains in Keller-Gehrig’s algorithm [20]. These algorithms use divisions and zero tests, and we do not see how to apply a homotopy a la Strassen to them without losing a factor about ` n.

The gap between the field and the ring case was partly closed by Kaltofen [17] who obtained O˜(n ω/2+2) ring operations for the characteristic polynomial. p. 0
Where the paper says it

These approaches focus on a different model and do not seem to lead to an improvement of the O˜(n ω+1 ) bound. The gap between the field and the ring case was partly closed by Kaltofen [17], who applies Strassen’s technique to Wiedemann’s algorithm [34] with a baby steps/giant steps strategy, and obtains the characteristic polynomial using O˜(n ω/2+2 ) ring operations (see also [29]).

The implications for division in exact computation

The question of whether the exponent ω can be reached without divisions goes back to Berkowitz [3]. The paper suggests that the characteristic polynomial over an arbitrary ring can be computed by circuits of size O(n ω) (up to logarithmic factors) and depth O(log2 n). p. 0

Where the paper says it

Whether the exponent ω can be reached without divisions is a question that goes back to Berkowitz [3, Section 4]. He conjectured more: that the characteristic polynomial over an arbitrary ring can be computed by circuits of size O(n ω ) (up to logarithmic factors) and depth O(log2 n).

The authors conclude that divisions do not bring an intrinsic advantage for computing the determinant. p. 1
Where the paper says it

The question is natural since the determinant and the coefficients of the characteristic polynomial, are polynomials with integer coefficients in the entries of the matrix: only ring operations are involved in their definition. The point therefore is whether divisions bring an intrinsic advantage.

The use of AI tools in preparation

During the preparation of this manuscript, the author used Claude (Anthropic), in several versions during 2026. The tool was used for bibliographical searches, for shortening Section 2 (whose ingredients are quite classical) and the proof of Lemma 3. p. 4

Where the paper says it

This did not lead to a choice of M, X, Y allowing one to keep the approach of [19] with a matrix Euclidean algorithm, and the author’s initial option, presented here, was retained. It was useful for bibliographical searches, for shortening Section 2 (whose ingredients are quite classical) and the proof of Lemma 3.

2. It was also used in the complexity analysis and its assumptions. p. 4
Where the paper says it

2, and for the complexity analysis and its assumptions. It was used in the final phase for drafting the text from the author’s instructions, in a presumably better English than the author’s, sentence by sentence.

The tool was used in the final phase for drafting the text from the author’s instructions, in a presumably better English than the author’s, sentence by sentence. p. 4
Where the paper says it

2, and for the complexity analysis and its assumptions. It was used in the final phase for drafting the text from the author’s instructions, in a presumably better English than the author’s, sentence by sentence.

The general properties of generating polynomials

Lemma 2.1 establishes conditions under which a matrix D as in (4) and (5) exists, is unique once normalized, and can be computed from the first 2d terms of the sequence X T LkY in (3). p. 5

Where the paper says it

Generating polynomials and characteristic polynomial Let S be a commutative ring, L ∈ Sn×n , and X, Y ∈ Sn×m with n = md. In this section we give conditions under which a matrix D as in (4) and (5) exists, is unique once normalized, and can be computed from the first 2d terms of the sequence X TL kY in (3).

The results hold for an arbitrary commutative ring S and arbitrary L, X, Y. p. 5
Where the paper says it

We recall the main properties for the sake of completeness. The results of this section hold for an arbitrary commutative ring S and arbitrary L, X, Y.

Lemma 4.4 shows that Algorithm 4. p. 0
Where the paper says it

On computing the determinant over a ring Gilles Villard CNRS, ENS de Lyon, Inria, U. Claude Bernard Lyon 1, LIP UMR 5668, 69342, Lyon cedex 07, France Abstract An algorithm is presented for computing the determinant and the characteristic polynomial of a matrix A over an arbitrary commutative ring R.

3 computes H(m) 0,. p. 1
Where the paper says it

For A ∈ R n×n , Algorithm 1. 1 computes the characteristic polynomial of A, hence its determinant, using O(n ω ) ring operations (Theorem 5.

.., H(m) τ−1 modulo tσ using O(m ωM(τσ)) operations in R. p. 8
Where the paper says it

3 computes H(m) 0 , . , H (m) τ−1 modulo tσ using O(m ωM(τσ)) operations in R.

The complexity of the transition step

Lemma 4.6 shows that Algorithm 4. p. 0

Where the paper says it

On computing the determinant over a ring Gilles Villard CNRS, ENS de Lyon, Inria, U. Claude Bernard Lyon 1, LIP UMR 5668, 69342, Lyon cedex 07, France Abstract An algorithm is presented for computing the determinant and the characteristic polynomial of a matrix A over an arbitrary commutative ring R.

5 computes the terms H(m/2) 0,. p. 3
Where the paper says it

1), three main ingredients are needed to obtain the target complexity bound without divisions. From the first 2d terms of the sequence at level m, Step 2a computes D (m) modulo t σm (σm is defined in (ii)).

.., H(m/2) 4d−1 using O(m ωM(d 2)(1 + log d)) operations in R. p. 4
Where the paper says it

Applied to polynomials whose coefficients are m × m matrices over R, with the black box for the coefficient products, this multiplies two m × m matrices of polynomials of degree less than h using O(m ωM(h)) operations in R. The finer count of [8], O(h log h) coefficient products only, is not needed here: the bound O(n ω ) of Theorem 5.

This bound follows from M(ch) ∈ O(M(h)) for a constant c, and from 1 + log d = 3 + log d ≤ 3(1 + log d). p. 9
Where the paper says it

Step 3 requires no arithmetic operation, and gives the exact terms at level m/2 using Lemma 3. The bound follows from M(ch) ∈ O(M(h)) for a constant c, and from 1 + log(4d) = 3 + log d ≤ 3(1 + log d).

The cost is dominated by the first level m = n, giving O(n ω) when ω > 2.

The final conclusion on complexity

Algorithm 1.1 computes the characteristic polynomial of A using O(n ω) operations in R. If ω = 2, the analysis gives O(n squared log3 n log log n) operations in R. p. 1

Where the paper says it

1), the matrix multiplication algorithm being used as a black box (Section 1. For ω = 2, the same analysis gives O(n 2 log3 n log log n) operations.

The final reversal is free. p. 9
Where the paper says it

Step 3 costs O(M(n 2 ) log n) by Lemma 4. 2, which is O(n ω ) for ω > 2, and the final reversal is free.

The algorithm computes the bivariate polynomial D(1) = det(λI − L(t)) ∈ R[λ, t].

The relationship between the determinant and characteristic polynomial

The final reversal is free. In particular, det A is (−1)n times the constant term of the characteristic polynomial. p. 9

Where the paper says it

2, which is O(n ω ) for ω > 2, and the final reversal is free. In particular, det A is (−1)n times the constant term of the characteristic polynomial, and Algorithm 1.

Algorithm 1.1 also computes the bivariate polynomial D(1) = det(λI − L(t)) ∈ R[λ, t]. p. 2
Where the paper says it

Algorithm 1. 1 computes the bivariate polynomial det(λI − L(t)) ∈ R[λ, t], which is monic of degree n in λ and of degree at most n in t.

The algorithm only uses ring additions, subtractions and multiplications, with no division and no zero test. p. 0
Where the paper says it

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 control depends only on n. p. 0
Where the paper says it

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 relationship between the determinant and the characteristic polynomial

The algorithm computes the bivariate polynomial D(1) = det(λI − L(t)) ∈ R[λ, t]. If ω = 2, the analysis for Theorem 5. p. 9

Where the paper says it

1 also computes the bivariate polynomial D (1) = det(λI − L(t)) ∈ R[λ, t]. If ω = 2, the analysis for Theorem 5.

p. 9
Where the paper says it

1 also computes the bivariate polynomial D (1) = det(λI − L(t)) ∈ R[λ, t]. If ω = 2, the analysis for Theorem 5.

1 gives O(n squared log3 n log log n) operations in R. p. 1
Where the paper says it

1), the matrix multiplication algorithm being used as a black box (Section 1. For ω = 2, the same analysis gives O(n 2 log3 n log log n) operations.

p. 1
Where the paper says it

1), the matrix multiplication algorithm being used as a black box (Section 1. For ω = 2, the same analysis gives O(n 2 log3 n log log n) operations.

The levels having then comparable costs. p. 9
Where the paper says it

If ω = 2, the analysis for Theorem 5. 1 gives O(n 2 log3 n log log n) operations in R, the levels having then comparable costs.

p. 9
Where the paper says it

If ω = 2, the analysis for Theorem 5. 1 gives O(n 2 log3 n log log n) operations in R, the levels having then comparable costs.

Note also that the cyclic permutation M could be replaced by any companion matrix whose constant coefficient is a unit of R with a known inverse (the result is then divided by the known unit det M). p. 9
Where the paper says it

1 gives O(n 2 log3 n log log n) operations in R, the levels having then comparable costs. Note also that the cyclic permutation M could be replaced by any companion matrix whose constant coefficient is a unit of R with a known inverse (the result is then divided by the known unit det M).

p. 9
Where the paper says it

1 gives O(n 2 log3 n log log n) operations in R, the levels having then comparable costs. Note also that the cyclic permutation M could be replaced by any companion matrix whose constant coefficient is a unit of R with a known inverse (the result is then divided by the known unit det M).

The same spirit as the application of [19] to integer matrices, this leads to the characteristic polynomial of a polynomial matrix with cyclic constant term, over a field, which we leave for future work. p. 9
Where the paper says it

Note also that the cyclic permutation M could be replaced by any companion matrix whose constant coefficient is a unit of R with a known inverse (the result is then divided by the known unit det M). In the same spirit as the application of [19] to integer matrices, this leads to the characteristic polynomial of a polynomial matrix with cyclic constant term, over a field, which we leave for future work.

p. 9
Where the paper says it

Note also that the cyclic permutation M could be replaced by any companion matrix whose constant coefficient is a unit of R with a known inverse (the result is then divided by the known unit det M). In the same spirit as the application of [19] to integer matrices, this leads to the characteristic polynomial of a polynomial matrix with cyclic constant term, over a field, which we leave for future work.

The role of the projection choice

The choice of sparse structured projections X and Y is central in our approach, both for the efficiency and for the elimination of divisions. The minimal generating polynomial is then the solution of a linear system whose constant term is invertible, which is solved by lifting in t, without divisions. p. 3

Where the paper says it

With this choice the block Hankel matrix of the sequence is a permutation matrix at t = 0, at every level (Section 3). The minimal generating polynomial is then the solution of a linear system whose constant term is invertible, which is solved by lifting in t, without divisions.

The algorithm computes the bivariate polynomial D(1) = det(λI − L(t)) ∈ R[λ, t]. If ω = 2, the analysis for Theorem 5.1 gives O(n squared log3 n log log n) operations in R. The levels having then comparable costs. Note also that the cyclic permutation M could be replaced by any companion matrix whose constant coefficient is a unit of R with a known inverse (the result is then divided by the known unit det M). The same spirit as the application of [19] to integer matrices, this leads to the characteristic polynomial of a polynomial matrix with cyclic constant term, over a field, which we leave for future work.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Block Wiedemann approach over rings: The system can compute characteristic polynomials of matrices over arbitrary commutative rings using O(n omega + 1) ring operations, where omega > 2 is a feasible exponent for matrix multiplication, and no division or zero test is required.

  2. Homotopy and projections design: The algorithm uses a bivariate matrix lambda I minus L(t), obtained from A by a homotopy, which is compressed in log n steps, each halving the dimension while only doubling the degree in lambda, controlling cost by truncating power series at an order that grows with compression steps.

  3. Hybrid approach combination: The system combines the polynomial matrix approach and Coppersmith’s block Wiedemann approach by running the Coppersmith scheme at log n successive levels with block sizes m = n, n/2,..., 1 without recomputing the sequence at each level.

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

Sources

Related papers