Modular computation of the determinant

Consider a square matrix $ A$ of order $ n$ with coefficients in $ {\mathbb{Z}}$ . It is known that $ {\det}(A)$ , the determinant of $ A$ , can be computed in at most $ 2 n^3$ operations in $ {\mbox{${\mathbb{Q}}$}}$ by means of Gaussian elimination. Let us estimate the growth of the coefficients. For simplicity, assume After $ k-1$ pivoting stages the current matrxi $ A^{(k-1)}$ looks like

$\displaystyle \left( \begin{array}{cccccccc} * & & & & & & & \\ 0 & * & & & & &...
...{ij}^{(k)} & \cdots \\ & & &\vdots & \vdots & & \vdots & \\ \end{array} \right)$ (110)

The entries of the matrix for $ k < i \leq n$ and $ k \leq j \leq n$ change according to the formula

$\displaystyle a_{ij}^{(k+1)} = a_{ij}^{(k)} - \frac{ a_{ik}^{(k)} }{ a_{kk}^{(k)} } a_{kj}^{(k)}.$ (111)

We consider the following numbers. From Relation (111) we obtain

$\displaystyle b_k \ \leq \ 2 {b_{k-1}^4} \ \leq \ 4 {b_{k-2}^{4^2}} \ \leq \ \cdots \ \leq \ 2^k {b_0}^{4^k}$ (112)

This shows an exponential upper bound. (However a polynomial bound in $ b_0, n$ can be established but the proof is far from trivial and the formula still not very encouraging.)

In what follows, we present an approach whose goal is to control the growth of the intermediate computations when calculating the determinant of $ A$ . Let $ d$ be this determinant. Let us choose a prime number $ p \in {\mbox{${\mathbb{Z}}$}}$ such that

$\displaystyle p \ > \ 2 \mid d \mid$ (113)

Let $ r$ be the determinant of $ A$ regarded as a matrix over $ {\mbox{${\mathbb{Z}}$}}/p{\mbox{${\mathbb{Z}}$}}$ and let us choose for representing $ {\mbox{${\mathbb{Z}}$}}/p{\mbox{${\mathbb{Z}}$}}$ the integers in the symmetric range

$\displaystyle -\frac{p-1}{2} \cdots \frac{p-1}{2}$ (114)

Hence we have

$\displaystyle -\frac{p}{2} < r < \frac{p}{2} \ \ {\rm and} \ \ -\frac{p}{2} < d < \frac{p}{2}$ (115)

leading to

$\displaystyle -p < d - r < p$ (116)

Observe that $ {\det}(A)$ is a polynomial in the coefficients of $ A$ . For instance with $ n =2$ we have

$\displaystyle {\det}(A) \ = \ a_{11} \, a_{22} - a_{12} \, a_{21}$ (117)

which shows that $ {\det}(A)$ (for $ n =2$ ) is a polynomial in $ a_{11}, \, a_{22}, \, a_{12}, \, a_{21}$ . Observe also the map

$\displaystyle h: \begin{array}{rcl} {\mbox{${\mathbb{Z}}$}} & \longrightarrow &...
...{Z}}$}} \\ x & \longrightarrow & x \mod{\, p} = {\overline{x}}^p \\ \end{array}$ (118)

is a ring homomorphism. In other words for every $ x, y \in {\mbox{${\mathbb{Z}}$}}$ we have

$\displaystyle {\overline{x + y }}^p \ = \ {\overline{x}}^p + {\overline{y}}^p \...
...\ {\rm and} \ \ \ \ {\overline{x y }}^p \ = \ {\overline{x}}^p {\overline{y}}^p$ (119)

Hence for $ n =2$ we have

$\displaystyle {\overline{{\det}(A)}}^p \ = \ {\overline{a_{11}}}^p \ {\overline{a_{22}}}^p - {\overline{a_{12}}}^p \ {\overline{a_{21}}}^p$ (120)

More generally we have

$\displaystyle {\overline{{\det}(A)}}^p \ = \ {\det}(A \mod{\, p})$ (121)

that is

$\displaystyle d \equiv r \mod{\, p}$ (122)

which means that $ p$ divides $ d -r$ . This with Relation (116) leads to

$\displaystyle d = r$ (123)

Hence the determinant of $ A$ as a matrix over $ {\mbox{${\mathbb{Z}}$}}$ is equal to the determinant of $ A$ regarded as a matrix over $ {\mbox{${\mathbb{Z}}$}}/p{\mbox{${\mathbb{Z}}$}}$ . Therefore the computation of the determinant of $ A$ as a matrix over $ {\mbox{${\mathbb{Z}}$}}$ can be done modulo $ p$ , which provides a control on the intermediate computations. Now we have to answer the following questions:
  1. How to choose $ p$ ?
  2. What do we win?
For choosing $ p$ we need an a-priori bound for the determinant of $ A$ . This is given by the following Hadamard's inequality.

Theorem 7   Let $ B$ be the maximal absolute value of an entry of $ A$ . Then we have

$\displaystyle \mid d \mid \ \leq \ n^{n/2} \, B^n$ (124)

Example 4   Consider

$\displaystyle A \ = \ \left( \begin{array}{cc} 4 & 5 \\ 6 & -7 \end{array} \right)$ (125)

Gaussian elimination leads to

$\displaystyle A \ = \ \left( \begin{array}{cc} 4 & 5 \\ 0 & -29/2 \end{array} \right)$ (126)

Hence $ {\det}(A) = -58$ . The Hadamard's inequality gives

$\displaystyle \mid {\det}(A) \mid \ \leq \ 2^1 \, 7^2 = 98$ (127)

The number $ p =199$ is prime and satisfies $ p > 2 \times 98$ . Gaussian elimination $ \mod{\, p}$ leads to

$\displaystyle A \ = \ \left( \begin{array}{cc} 4 & 5 \\ 0 & 85 \end{array} \right)$ (128)

So $ {\det}(A \mod{\, p}) = 141 = -58$ in $ {\mbox{${\mathbb{Z}}$}}/199{\mbox{${\mathbb{Z}}$}}$ .

Let us study what is the cost of this approach. Let us denote by $ C$ the determinant bound of Hadamard's inequality. Assume that our machine words are $ N$ -bit long. We make the following observations. Therefore we have proved the following theorem

Theorem 8   The determinant of a square matrix with order $ n$ , coefficients in $ {\mathbb{Z}}$ and $ B$ as the maximal absolute value of a coefficient can be computed in $ {\cal O}(n^3 \, n^2 \, ({\log} n + {\log} B)^2)$ word operations.

This is not in fact a big progress w.r.t. Gaussian elimination over $ {\mathbb{Q}}$ . But this can be improved using a small primes modular computation as follows.

Algorithm 5  

\fbox{
\begin{minipage}{10 cm}
\begin{description}
\item[{\bf Input:}] $A=(a_{ij...
...\
\> \> $d$\ := $d - m$\ \\
\> {\bf return}($d$)
\end{tabbing}\end{minipage}}

Proof. Recall that $ {\det}(A)$ is a polynomial expression in the coefficients of $ A$ . Hence by using the ring homomorphism between $ {\mbox{${\mathbb{Z}}$}}$ and $ {\mbox{${\mathbb{Z}}$}}/{m_i}{\mbox{${\mathbb{Z}}$}}$ for $ i = 0 \cdots r-1$ we have

$\displaystyle {\det}(A) \equiv d_i \mod{\, m_i}$ (130)

Using the ring isomorphism of Corollary 2

$\displaystyle {\mbox{${\mathbb{Z}}$}}/m \ \simeq \ {\mbox{${\mathbb{Z}}$}}/{m_0} \times \cdots \times {\mbox{${\mathbb{Z}}$}}/{m_{r-1}}$ (131)

we deduce

$\displaystyle {\det}(A) \equiv d \mod{\, m}$ (132)

where $ m$ is the product of the moduli $ m_0, \ldots, m_{r-1}$ . Now observe that

\begin{displaymath}\begin{array}{rcl} m & = & m_0 \cdots m_{r-1} \\ & \geq & 2^r...
... & 2 \, n^{n/2} \, B^n \\ & \geq & 2 \mid d \mid \\ \end{array}\end{displaymath} (133)

Hence actually we have $ {\det}(A) = d$ . $ \qedsymbol$

Example 5   Consider again

$\displaystyle A \ = \ \left( \begin{array}{cc} 4 & 5 \\ 6 & -7 \end{array} \right)$ (134)

We choose the four primes $ 2,3,5,7$ so that $ m = 210$ . We get

\begin{displaymath}\begin{array}{ccc} {\det}(A) \equiv 0 \mod{\, 2} & \ \ & {\de...
... 2 \mod{\, 5} & \ \ &{\det}(A) \equiv -2 \mod{\, 7} \end{array}\end{displaymath} (135)

The solutions of the system $ d \equiv d_i \mod{\, m_i}$ for $ 1 \leq i \leq 4$ are in

$\displaystyle -58 + 210 {\mbox{${\mathbb{Z}}$}} \ = \ \{ \ldots, -268, -58, 152, 362, \ldots \}$ (136)

Finally $ {\det}(A) = -58$ again.

Based on this small primes modular computation approach one could prove the following theorem

Theorem 9   The determinant of a square matrix with order $ n$ , coefficients in $ {\mathbb{Z}}$ and $ B$ as the maximal absolute value of a coefficient can be computed in $ {\cal O}(n^4 {\log}^2(n \, B) ({\log}^2 n + {\log}^2 B))$ word operations.

Proof. See Theorem 5.12 in [GG99] $ \qedsymbol$

Remark 10   With Algorithm 5 we achieve the following goals. Moreover the computations of the modular determinants (the $ d_i$ 's) are pairwise independent and thus can be distributed.

Marc Moreno Maza
2008-01-07