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

CC BY-SA 3.0
2012-02-26T21:21:18.043Z
Thank you for your reply with link to very interesting paper.
StuL
CC BY-SA 3.0
2012-02-26T21:30:09.520Z
Also I believe there are more efficient algorithms since the authors of this paper solved more general problem (for any commutative ring).
StuL
CC BY-SA 3.0
2012-02-27T00:39:05.453Z
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
CC BY-SA 3.0
2012-02-27T03:40:46.810Z
@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
CC BY-SA 3.0
2012-02-27T08:20:17.510Z
@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)$.
StuL
CC BY-SA 3.0
2012-02-27T08:24:00.033Z
@SureshVenkat The answer is really interesting and useful, but this is not exactly what I wanted to know ($\mathbb{Z}_m$ versus Commutative Ring issue). So I would like to wait for better answers.
StuL
CC BY-SA 3.0
2013-07-20T03:41:40.507Z
It would be interesting to know the worst case running time of this algorithm (in terms of the relevant input size/precision/etc). Does anyone know it? I am not familiar to it.
Juan Bermejo Vega
CC BY-SA 3.0
2012-02-26T21:03:28.633Z
2012-02-26T21:03:28.633Z
Sasho Nikolov
<p>To solve this problem there is a <a href="http://dl.acm.org/citation.cfm?id=237084" rel="nofollow">fast deterministic algorithm</a> based on <a href="http://en.wikipedia.org/wiki/Smith_normal_form" rel="nofollow">Smith normal forms</a> 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. </p>

<p>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,</p>

<blockquote>
  <p>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$ <a href="http://dl.acm.org/citation.cfm?id=237084" rel="nofollow">[1]</a>.</p>
</blockquote>

<p>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).</p>

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

<p><strong>Notes:</strong> 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 <a href="http://www.cs.berkeley.edu/~virgi/matrixmult.pdf" rel="nofollow">2.3727</a>.</p>

CC BY-SA 3.0
2012-02-27T19:39:32.207Z
isn't $\theta$ what is usually denoted $\omega$?
Sasho Nikolov
CC BY-SA 3.0
2012-02-27T20:15:05.663Z
Maybe, I do not know the most common notation for this.
Juan Bermejo Vega
CC BY-SA 3.0
2012-02-27T20:33:22.990Z
I think you are right, I will change it to be "mainstream"
Juan Bermejo Vega
CC BY-SA 3.0
2012-02-27T11:33:06.943Z
2013-07-20T03:39:52.857Z
2013-07-20T03:39:52.857Z
Juan Bermejo Vega
<p>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.  </p>

CC BY-SA 3.0
2012-02-27T10:08:24.207Z
Thank you! It is like something I was looking for. Is this a common practice for determinants? (references are welcome).
StuL
CC BY-SA 3.0
2012-02-27T11:41:51.673Z
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
CC BY-SA 4.0
2023-08-03T21:02:22.760Z
@MarkusBläser How do you use Hensel lifting for det mod $p^2$ if you know det mod $p$ where $p$ is a prime?
Turbo
CC BY-SA 3.0
2012-02-27T09:47:02.787Z
2012-02-27T09:47:02.787Z
Markus Bläser
<p>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).</p>

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

<p>If it happened that there is some different approach, I also curious about it.</p>

<p>Thanks in advance.</p>

<p><strong>Update:</strong></p>

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

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

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

CC BY-SA 3.0
2012-02-26T17:10:02.923Z
What do you mean by ``efficient''? The problem is clearly in $P$.
david
CC BY-SA 3.0
2012-02-26T17:24:07.587Z
As far as I know, most algorithms are modifications of Gaussian elimination. The question is more about efficiency of these modifications.
StuL
CC BY-SA 3.0
2012-02-26T18:57:10.210Z
Is $m$ a fixed constant? How is it given?
Michael Blondin
CC BY-SA 3.0
2012-02-26T19:09:26.363Z
$m$ is a given positive integer. Also I assume that in the input all numbers ($m$ and matrix elements) are small (so we could think of additions and multiplications of these numbers).

Also, numbers are small only in the input. Length of all numbers during computation depends on an algorithm applied, of course.
StuL
CC BY-SA 3.0
2012-02-26T19:15:27.037Z
What do you mean by small? Could they be written in unary?
Michael Blondin
CC BY-SA 3.0
2012-02-26T19:23:55.503Z
Sorry for inconvenience. I meant small keeping in mind some irrelevant application.

So, let assume $m$ is an arbitrary positive integer and all elements of a matrix are arbitrary integers. They all both with $m$ are represented in binary.
StuL
CC BY-SA 3.0
2012-02-27T12:49:17.597Z
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
CC BY-SA 3.0
2012-02-27T15:50:41.633Z
@david The question to you is how big could be numbers during your way of computation of integer determinant.
StuL
CC BY-SA 3.0
2012-02-27T18:04:31.837Z
@ValeriySokolov: That is basic linear algebra.  For example, please check Problem 11.5.3 of _Computational Complexity_ by Christos H. Papadimitriou.
Tsuyoshi Ito
CC BY-SA 3.0
2012-02-27T23:02:51.813Z
@ValeriySokolov As I already said, computation of integer determinants is in $P$. In particular, the length of all numbers you get during the computation (using some method) is polynomially bounded in $n$. Tsuyoshi Ito has given a reference for the standard fact that this holds even when using Gaussian elimination. So what is your question about? Are you trying to minimize the exponent in the polynomial running time?
david
CC BY-SA 3.0
2012-02-28T00:18:37.820Z
@david: It is obvious that stated problem is in $P$. The question was how is it bounded, and what algorithms are efficient in practice.
StuL
CC BY-SA 3.0
2012-02-28T08:27:21.003Z
Did yo impose that you know the prime number factorisation at the end? It looks restrictive.
Juan Bermejo Vega
CC BY-SA 3.0
2012-02-28T14:24:12.983Z
@JuanBermejoVega At first time I assumed that the factorization of $m$ is given or is not hard to obtain.
StuL
<ds.algorithms><reference-request><linear-algebra><comp-number-theory>
Determinant modulo m
StuL
# Determinant modulo m

(Asked by: username_0 on 2012-02-26)

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.

**Tags:** ds.algorithms, reference-request, linear-algebra, comp-number-theory
> **Comments:**
> **username_1**: What do you mean by ``efficient''? The problem is clearly in $P$.  
> **username_0**: As far as I know, most algorithms are modifications of Gaussian elimination. The question is more about efficiency of these modifications.  
> **username_2**: Is $m$ a fixed constant? How is it given?  
> **username_0**: $m$ is a given positive integer. Also I assume that in the input all numbers ($m$ and matrix elements) are small (so we could think of additions and multiplications of these numbers).  Also, numbers are small only in the input. Length of all numbers during computation depends on an algorithm applied, of course.  
> **username_2**: What do you mean by small? Could they be written in unary?  
> **username_0**: Sorry for inconvenience. I meant small keeping in mind some irrelevant application.  So, let assume $m$ is an arbitrary positive integer and all elements of a matrix are arbitrary integers. They all both with $m$ are represented in binary.  
> **username_1**: 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$.  
> **username_0**: @david The question to you is how big could be numbers during your way of computation of integer determinant.  
> **username_3**: @ValeriySokolov: That is basic linear algebra.  For example, please check Problem 11.5.3 of _Computational Complexity_ by Christos H. Papadimitriou.  
> **username_1**: @ValeriySokolov As I already said, computation of integer determinants is in $P$. In particular, the length of all numbers you get during the computation (using some method) is polynomially bounded in $n$. Tsuyoshi Ito has given a reference for the standard fact that this holds even when using Gaussian elimination. So what is your question about? Are you trying to minimize the exponent in the polynomial running time?  
> **username_0**: @david: It is obvious that stated problem is in $P$. The question was how is it bounded, and what algorithms are efficient in practice.  
> **username_4**: Did yo impose that you know the prime number factorisation at the end? It looks restrictive.  
> **username_0**: @JuanBermejoVega At first time I assumed that the factorization of $m$ is given or is not hard to obtain.  

---

## 3 answers

### Answer by username_7 on 2012-02-27. Score: 15 | Accepted answer

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.

> **Comments:**
> **username_0**: Thank you! It is like something I was looking for. Is this a common practice for determinants? (references are welcome).  
> **username_7**: 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  
> **username_8**: @MarkusBläser How do you use Hensel lifting for det mod $p^2$ if you know det mod $p$ where $p$ is a prime?  

---

### Answer by username_5 on 2012-02-26. Score: 17

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

> **Comments:**
> **username_0**: Thank you for your reply with link to very interesting paper.  
> **username_0**: Also I believe there are more efficient algorithms since the authors of this paper solved more general problem (for any commutative ring).  
> **username_5**: 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.  
> **username_6**: @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)  
> **username_0**: @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)$.  
> **username_0**: @SureshVenkat The answer is really interesting and useful, but this is not exactly what I wanted to know ($\mathbb{Z}_m$ versus Commutative Ring issue). So I would like to wait for better answers.  
> **username_4**: It would be interesting to know the worst case running time of this algorithm (in terms of the relevant input size/precision/etc). Does anyone know it? I am not familiar to it.  

---

### Answer by username_4 on 2012-02-27. Score: 12

To solve this problem there is a [fast deterministic algorithm](http://dl.acm.org/citation.cfm?id=237084) based on [Smith normal forms](http://en.wikipedia.org/wiki/Smith_normal_form) 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]](http://dl.acm.org/citation.cfm?id=237084).

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](http://en.wikipedia.org/wiki/Shors_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](http://www.cs.berkeley.edu/~virgi/matrixmult.pdf).

> **Comments:**
> **username_5**: isn't $\theta$ what is usually denoted $\omega$?  
> **username_4**: Maybe, I do not know the most common notation for this.  
> **username_4**: I think you are right, I will change it to be "mainstream"  

---

