# Determine if a matrix is unimodular

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

-
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 en.wikipedia.org/wiki/LU_decomposition#Theoretical_complexity. 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