calculating the determinant of an $n \times n$ integer matrix

Question

I want to write a polynomial algorithm for calculating the determinant of an $n \times n$ integer matrix. There are various codes in different programming languages on the web but unfortunately I am not good at understanding codes which are written by other people. Normally, what steps will it take to calculate the determinant of an $n \times n$ integer matrix, then I can write the algorithm and compute its time complexity on my own.

Answer 1

One method is to use Gaussian elimination to reduce the matrix to upper triangular form. The determinant is then the product of the diagonal matrix elements. The problem with this method when matrix elements are integers is that Gaussian elimination will produce fractions in general. For large matrices, the denominators of these fractions can blow up rather fast.

One way around this is to work modulo a prime, $p$. This is equivalent to working over the finite field $\mathbf{F}_p.$ Since division can be performed in a finite field, you don't have to worry about the fraction problem. Of course the answer you obtain will only be correct modulo $p.$ If you happen to know that your determinant is between $0$ and $p,$ then you're done at this point. Hadamard's determinant bound can be used to place an upper bound on the absolute value of the answer. If this upper bound is $h,$ then as long as $p>2h,$ you will be able to recover the answer. (You need $2h$ because the answer might be negative.)

Hadamard's bound also gets big very quickly, and most of the time is far bigger than the actual determinant, which means that you may have to use a $p$ that is impractically large. An alternative is to perform the calculation modulo several primes $p_1,\ldots,p_k$ whose product is larger than $2h.$ The Chinese remainder theorem can then be used to reconstruct the answer.

A different method is to use Dodgson condensation. All of these suggestions are taken form Henri Cohen's book, A Course in Computational Algebraic Number Theory, which I highly recommend. If this isn't enough detail to get you started, let me know, and I'll try to expand on this answer.