Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

What are the known efficient algorithms for computing a determinant of an integer matrix with coefficients in $\mathbb{Z}_m$, the ring of residues modulo $m$. The number $m$ may not be prime but composite (so computations are performed in ring, not a field).

As far as I know (read below), most algorithms are modifications of Gaussian elimination. The question is about the computational efficiency of these procedures.

If it happened that there is some different approach, I also curious about it.

Thanks in advance.

Update:

Let me explain the source of this question. Assume, $m$ is a prime number. So $\mathbb{Z}_m$ is a field. And in this case we can perform all computations using numbers less than $m$, so we have some nice upper bound on all operations on numbers: addition, multiplication and inversion --- all needed operations to run Gaussian elimination.

On the other hand we can not perform inversion for some numbers in case $m$ not a prime. So we need some tricks to compute determinant.

And now I am curious what are the known tricks to do the job and whether such tricks could be found in and papers of books.

share|improve this question
3  
What do you mean by ``efficient''? The problem is clearly in $P$. –  david Feb 26 '12 at 17:10
2  
Is $m$ a fixed constant? How is it given? –  Michael Blondin Feb 26 '12 at 18:57
2  
What do you mean by small? Could they be written in unary? –  Michael Blondin Feb 26 '12 at 19:15
5  
I still don't understand the question. The determinant of an integer matrix can be computed in polynomial time, so you can just take this value modulo $m$. No need to perform divisions in $Z_m$ or find the factorization of $m$. –  david Feb 27 '12 at 12:49
2  
@ValeriySokolov: That is basic linear algebra. For example, please check Problem 11.5.3 of Computational Complexity by Christos H. Papadimitriou. –  Tsuyoshi Ito Feb 27 '12 at 18:04

3 Answers 3

up vote 15 down vote accepted

If you know the factorization of $m = p_1^{e_1} \cdots p_n^{e_n}$ you can compute modulo each $p_i^{e_i}$ separately and then combine the results using Chinese remaindering. If $e_i = 1$, then computing modulo $p_i^{e_i}$ is easy, since this is a field. For larger $e_i$, you can use Hensel lifting.

share|improve this answer
    
Thank you! It is like something I was looking for. Is this a common practice for determinants? (references are welcome). –  Valeriy Sokolov Feb 27 '12 at 10:08
6  
These are standard techniques from comnputer algebra. Have a look at Modern Computer Algebra by von zur Gathen and Gerhard or any other book on computer algebra. For your specific problem, see also the following paper by Pan, Yu & Stewart comet.lehman.cuny.edu/vpan/pdf/pan146.pdf –  Markus Bläser Feb 27 '12 at 11:41

There is a combinatorial algorithm by Mahajan and Vinay that works over commutative rings: http://cjtcs.cs.uchicago.edu/articles/1997/5/contents.html

share|improve this answer
    
Thank you for your reply with link to very interesting paper. –  Valeriy Sokolov Feb 26 '12 at 21:21
    
Also I believe there are more efficient algorithms since the authors of this paper solved more general problem (for any commutative ring). –  Valeriy Sokolov Feb 26 '12 at 21:30
    
by "there are" do you mean "known" or "exist" (but have not been found yet)? it's a reasonable guess, but I am a little skeptical that the structure of the ring of intigers modulo a small composite number can help you all that much. if i'm wrong, i'd find that interesting. –  Sasho Nikolov Feb 27 '12 at 0:39
1  
@ValeriySokolov to be fair, since the answer does answer your question, you might consider accepting it (or if you wish to wait for possibly better answers that would not be unreasonable) –  Suresh Venkat Feb 27 '12 at 3:40
    
@SashoNikolov I have found that Wolfram Mathematica somehow computes this. In "Implementation Notes" they say: Det uses modular methods and row reduction, constructing a result using the Chinese remainder theorem. I would like to know what exactly they do, but a quick search gave me nothing. As for "small composite $m$" it only means that I want to consider complexity of additions and multiplications in this ring to be $O(1)$. That is all factors like $O(\log m)$ are considered as $O(1)$. –  Valeriy Sokolov Feb 27 '12 at 8:20

To solve this problem there is a fast deterministic algorithm based on Smith normal forms whose worst-case complexity is upper-bounded by the cost of matrix-multiplication over the integers modulo $m$. For any matrix $A$, the algorithm outputs its Smith normal form, from where $\text{det}(A)$ can be easily computed.

More concretely, define $\omega$ so that two $n \times n$ matrices with coefficients taken from $\mathbb{Z}_m$ can be multiplied using $O(n^{\omega})$ basic arithmetic operations on $\mathbb{Z}_m$ (integer addition, multiplication, exponentiation, etc). Then,

Given a matrix $A\in \mathbb{Z}_m^{n \times n}$, there exists a deterministic algorithm that computes $\text{det}(A)$ using $O(n^{\omega})$ basic arithmetical operations over $\mathbb{Z}_m$ [1].

When this was written in 1996 there was no asymptotically faster alternative (the paper mentions the prior existence of algorithms with the same bound but I do not know which ones, or whether they are probabilistic).

Update (July 17, 2013): a nice bonus feature of this algorithm is that it runs in polynomial time for arbitrary composite $m$ without knowing a prime-nuber factorization of $m$! This is good since there are no known efficient (classical) algorithms for factoring (of course, if you had a quantum computer, then you could apply Shor's algorithm). If you do have the factorization then the algorithm Markus suggested seems way simpler to implement.

Notes: in the paper, the complexity of "basic arithmetical operations" is $O(\log^2 m)$ if you use standard integer arithmetic, but you can achieve $O(M(\log m)\log \log m)$ with faster techniques. $M(t)$ bounds the cost of multiplying two $t$-bit integers. The current record for $\omega$ is 2.3727.

share|improve this answer
    
isn't $\theta$ what is usually denoted $\omega$? –  Sasho Nikolov Feb 27 '12 at 19:39
    
Maybe, I do not know the most common notation for this. –  Juan Bermejo Vega Feb 27 '12 at 20:15
    
I think you are right, I will change it to be "mainstream" –  Juan Bermejo Vega Feb 27 '12 at 20:33

Your Answer

 
discard

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.