Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Is deciding if an integer square matrix has determinant $\pm 1$ faster that calculating the determinant of the matrix?

share|cite|improve this question
could you expand a bit on how this question is similar to detection of unimodularity, where every sub-determinant has to be in $\lbrace 0,\pm 1\rbrace$ – Suvrit Sep 3 '12 at 8:55
I don't know if this is 'faster', but consider the sequence of elementary operations which reduces a square integer matrix $A$ to it's Smith Normal form. We have an algorithm which determines the elementary divisors of $A$, and if any of these elementary divisors is $\neq \pm 1$, then we'll know $A$ is not unimodular. Any step in the reduction implements a euclidean algorithm to compute gcd's. That is, we are constantly reducing rows and colomns. If $A$ is unimodular, then we'll have computed all its elementary divisors, and their product is of course $detA$. So reducing $A$ to its Jordan – J. Martel Sep 3 '12 at 18:02
normal form, either $A$ is not unimodular and we shall eventually determine an elementary divisor $\neq \pm 1$ (which of course, may only occur at the last step), or we determine all of its elementary divisors to be $\pm 1$, and then we've just computed the determinant. So maybe the right question is simply whether or not computing the Smith normal form is faster than computing the determinant. – J. Martel Sep 3 '12 at 18:05
@J.Martel: I was thinking in terms of matrices with rational entries instead of integers; btw., computation of determinant is essentially an $O(n^3)$ procedure (Gaussian elimination); I guess the SNF is not much faster, if at all? – Suvrit Sep 4 '12 at 8:22
In fact, thanks to LU decomposition, computing the determinant is at least as fast as computing a matrix product. So we can compute the determinant exactly in $O(n^{2.376}). See Similarly, in Storjohann's paper "Near Optimal Algorithms for Computing Smith Normal Forms of Integer Matrices" he shows a similar inequality. That is, for an integer square matrix, computing its SNF is at least as fast as computing a matrix product. – Mark Bell Sep 4 '12 at 9:43

1 Answer 1

From Santha and Tan, "Verifying the determinant in parallel":

"for the determinant, there doesn't seem to be a simpler way to verify it than the computation itself."

Other notes:

Matrix multiplication, inversion, and determinant-finding are all equally complex. I will quote from Kaltofen and Villard, "Computing the sign or the value of the determinant of an integer matrix, a complexity survey":

In algebraic complexity—i.e. when counting the number of operations in an abstract domain—we refer to Strassen [52] and Bunch & Hopcroft [13] for the reduction of the problem of computing the determinant to matrix multiplication. Conversely, Strassen [53] and Bunch & Hopcroft [13] reduce matrix multiplication to matrix inversion, and Baur & Strassen reduce matrix inversion to computing the determinant [7]

Since unimodularity amounts to invertibility, your question is equivalent to "is determining invertibility easier than actually computing the inverse (if it exists)?"

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.