Take the 2-minute tour ×
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|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
    
Sorry I misread the answers paper, their definition of unimodular used in Theorem 1 is more general to cover non-square matrices. I'll edit the question and remove the reference. –  Mark Bell Sep 3 '12 at 9:22
    
assuming unit costs for arithmetic operations, probably the decision problem is as hard as the computation. for example, take a diagonal matrix.... –  Suvrit Sep 3 '12 at 12:18
1  
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
1  
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

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.