19

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.

Community
  • 1
Valeriy Sokolov
  • 353
  • 1
  • 8
  • 3
    What do you mean by ``efficient''? The problem is clearly in $P$. – david Feb 26 '12 at 17:10
  • As far as I know, most algorithms are modifications of Gaussian elimination. The question is more about efficiency of these modifications. – Valeriy Sokolov Feb 26 '12 at 17:24
  • 2
    Is $m$ a fixed constant? How is it given? – Michael Blondin Feb 26 '12 at 18:57
  • $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.

     – Valeriy Sokolov Feb 26 '12 at 19:09
  • 2
    What do you mean by small? Could they be written in unary? – Michael Blondin Feb 26 '12 at 19:15
  • 1
    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.

     – Valeriy Sokolov Feb 26 '12 at 19:23
  • 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
  • @david The question to you is how big could be numbers during your way of computation of integer determinant. – Valeriy Sokolov Feb 27 '12 at 15:50
  • 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
  • 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? – david Feb 27 '12 at 23:02
  • @david: It is obvious that stated problem is in $P$. The question was how is it bounded, and what algorithms are efficient in practice. – Valeriy Sokolov Feb 28 '12 at 00:18
  • 1
    Did yo impose that you know the prime number factorisation at the end? It looks restrictive. – Juan Bermejo Vega Feb 28 '12 at 08:27
  • @JuanBermejoVega At first time I assumed that the factorization of $m$ is given or is not hard to obtain. – Valeriy Sokolov Feb 28 '12 at 14:24

3 Answers3

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

Sasho Nikolov
  • 18,189
  • 2
  • 67
  • 115
  • 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 00: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 03: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 08:20
  • @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. – Valeriy Sokolov Feb 27 '12 at 08:24
  • 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 Jul 20 '13 at 03:41
15

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.

Markus Bläser
  • 2,938
  • 18
  • 19
  • 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
  • @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 Aug 03 '23 at 21:02
12

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.

Juan Bermejo Vega
  • 1,405
  • 1
  • 14
  • 30