On Determinants of Random Symmetric Matrices over Z_{m}

Richard P. Brent Computer Sciences Laboratory Australian National University

Brendan D. McKay Computer Science Department Australian National University

Report TR-CS-88-03

February 1988 Republished October 1998

Abstract We determine the probability that a random n by n symmetric matrix over {1, 2, …, m}

has determinant divisible by m.

1 Introduction

Let m be an integer. The m-rank of an integer matrix A is the greatest integer k such that A has a k by k submatrix (not necessarily contiguous) whose determinant is nonzero mod m, or 0 if there is no such matrix. If m is a prime, the m-rank is equivalent to the usual rank over the field GF (m). In this paper we assume that the elements a_{ij} of A are chosen at random, independently and uniformly, from Z_{m} = {1, 2, …, m}, subject to the condition that a_{ij} = a_{ji}, i.e., that A is symmetric. For corresponding results without the symmetry constraint, see [1].

Let P (n, m) denote the probability that a random n by n symmetric matrix A over Z_{m} has m-rank n, and define Q(n, m) = 1 − P (n, m). Thus, Q(n, m) is the probability that det(A) = 0 (mod m). As in Lemma 1.1 of [1], we have

Lemma 1.1 Suppose m = p_{1}^{μ_{1}}p_{2}^{μ_{2}} ⋯ p_{k}^{μ_{k}}, where p_{1}, p_{2}, …, p_{k} are distinctive primes. Then

Q(n, m) = ∏_{i=1}^{k} Q(n, p_{i}^{μ_{i}}).

In view of Lemma 1.1, we restrict our attention to the case that m is a prime power, say m = p^{μ}. It is useful to define q = 1/p.

As in [1], our principal tool is Gaussian elimination, but in this case we have to use forms of Gaussian elimination which preserve symmetry. This is discussed in Section 2. Then, in Section 3, we use symmetric Gaussian elimination to show that P (n, p^{μ}) satisfies a five-term recurrence relation. In Section 4 we show that the five-term recurrence can be reduced to a three-term recurrence. Finally, in Section 5 we show that the three-term recurrence can be solved explicitly.

The solution depends on the parity of n and μ, and is well-known for μ = 1, but appears to be new for μ > 1. To conclude Section 5, we deduce some inequalities from the explicit solution.

TR-CS-88-03 retyped by Frances Page at Oxford University Computing Laboratory, October 1998.

Revision \begin{matrix}c \\ ◯ \end{matrix} 1988 Charles Babbage Research Centre appeared in Ars Combinatoria 26A(1988), 57–64.

TR-CS-88-03 copyright \begin{matrix}c \\ ◯ \end{matrix} 1988, 1998 the authors. rpb101tr typeset using L^{A}TEX.

An interesting problem is to determine the probability that a random n by n symmetric matrix A over Z_{m} has given m-rank r, where r < n. The case μ = 1 has been solved by Carlitz [2] (provided p ≠ 2), and the unsymmetric case has been considered in [1], but the general symmetric case remains open.

Another open problem is to determine the probability that det(A) mod m takes a given (nonzero) value d. Small examples show that this probability depends on d. For example, if μ = 1, k = ⌈n/2⌉, (d|p) is the Legendre symbol,

s = \{ \begin{matrix}0, & if p = 2 or n is odd, \\ (d|p)(−1)^{k(p−1)/2}, & otherwise, \end{matrix}

and Π is defined as in Section 5, then the probability is

(\frac{q}{1 − q} ) \frac{Π_{2k}(q)}{Π_{k}(q^{2})} (1 + sq^{k}).

2 Symmetric Gaussian Elimination

Suppose that A, n, m = p^{μ} and P (n, m) are as in Section 1. Lemmas 2.1 and 2.2 describe symmetric versions of Gaussian elimination.

Lemma 2.1 Suppose that n > 1 and a_{11} ≠ 0 (mod p). Then there is a matrix U such that

UAU^{T} = ( \begin{matrix}a_{11} & 0 & ⋯ & 0 \\ 0 \\ ⋮ & & A′ \\ 0 \end{matrix} ) (mod p^{μ})  (2.1)

where A′ is a random n − 1 by n − 1 symmetric matrix.

Proof. Define

U = ( \begin{matrix}1 \\ λ_{2} & 1 & & 0 \\ λ_{3} & & ... \\ ⋮ & & 0 & ... \\ λ_{n} & & & & 1 \end{matrix} )

where

a_{11}λ_{j} = −a_{1j} (mod m) for j = 2, 3, …, n.  (2.2)

Observe that λ_{2}, …, λ_{n} exist (since a_{11} ≠ 0 (mod p)) and (2.1) clearly holds. Also, A′ depends linearly on the random symmetric matrix

( \begin{matrix}a_{22} & ⋯ & a_{2n} \\ ⋮ & ... & ⋮ \\ a_{n2} & ⋯ & a_{nn} \end{matrix} ) ,

and thus is random over Z_{m}. □

Lemma 2.2 Suppose that n > 2, a_{11} = 0 (mod p), and a_{12} ≠ 0 (mod p). Then there is a matrix V such that

VAV^{T} = ( \begin{matrix}a_{11} & & a_{12} \\ & & & 0 \\ a_{21} & & a_{22} \\ & 0 & & A′′ \end{matrix} ) (mod p^{μ})  (2.3)

where A′′ is a random n − 2 by n − 2 symmetric matrix.

Proof. Define

V = ( \begin{matrix}1 \\ 0 & 1 & & 0 \\ λ_{3} & μ_{3} & 1 \\ ⋮ & ⋮ & & ... \\ λ_{n} & μ_{n} & 0 & & 1 \end{matrix} ) ,

where

( \begin{matrix}a_{11} & a_{12} \\ a_{21} & a_{22} \end{matrix} ) ( \begin{matrix}λ_{j} \\ μ_{j} \end{matrix} ) = − ( \begin{matrix}a_{1j} \\ a_{2j} \end{matrix} ) (mod m)

for j = 3, …, n. Observe that μ_{j} and λ_{j} exist (j = 3, …, n) since

det ( \begin{matrix}a_{11} & a_{12} \\ a_{21} & a_{22} \end{matrix} ) ≠ 0 (mod p).

It is easy to see that (2.3) holds. Also, A′′ depends linearly on the random symmetric matrix

( \begin{matrix}a_{33} & ⋯ & a_{3n} \\ ⋮ & ... & ⋮ \\ a_{n3} & ⋯ & a_{nn} \end{matrix} )

and thus is random over Z_{m}. □

3 A five-term recurrence for P (n, p^{μ})

It is convenient to define

P (0, p^{μ}) = 1 for μ > 0

and (3.1) P (n, p^{μ}) = 0 for μ ≤ 0.

Theorem 3.1 If n > 0, μ > 0, and boundary conditions are given by (3.1), then

P (n, p^{μ}) = (1 − q)P (n − 1, p^{μ}) + q(1 − q^{n−1})P (n − 2, p^{μ})
+ q^{n}(1 − q)P (n − 1, p^{μ−1}) + q^{n+1}P (n, p^{μ−2}).  (3.2)

Proof. Let A be a random symmetric n × n matrix over Z_{m}, m = p^{μ}. The four terms on the right side of (3.2) arise from four mutually exclusive cases:

1. a_{11} ≠ 0 (mod p).

2. a_{11} = 0 (mod p) and some a_{1j} ≠ 0 (mod p).

3. a_{1j} = 0 (mod p) for j = 1, …, n and a_{11} ≠ 0 (mod p^{2}).

4. a_{1j} = 0 (mod p) for j = 1, …, n and a_{11} = 0 (mod p^{2}).

In case 1, which occurs with probability 1−q, we apply Lemma 2.1; since det(A) = a_{11} det(A′) (mod p^{μ}) we have det(A) ≠ 0 (mod p^{μ}) iff det(A′) ≠ 0 (mod p^{μ}), which occurs with conditional probability P (n − 1, p^{μ}).

In case 2, which occurs with probability q(1 − q^{n−1}), we can assume that a_{12} ≠ 0 (mod p) by making a suitable permutation of rows and columns, if necessary. We then apply Lemma 2.2, obtaining det(A) = (a_{11}a_{22} − a_{12}^{2}) det(A′′) (mod p^{μ}), so det(A) ≠ 0 (mod p^{μ}) iff det(A′′) ≠ 0 (mod p^{μ}), which occurs with conditional probability P (n − 2, p^{μ}).

In case 3, which occurs with probability q^{n}(1 − q), we can reduce A to the form (2.1) because (2.2) is solvable. Thus det(A) = a_{11} det(A′) (mod p^{μ}) and det(A) ≠ 0 (mod p^{μ}) iff det(A′) ≠ 0 (mod p^{μ−1}), which occurs with conditional probability P (n − 1, p^{μ−1}).

Finally, in case 4, which occurs with probability q^{n+1}, we can divide the first row and column of A by p, add random multiples of p^{μ−1} to elements in the first row (and to corresponding elements in the first column), add a random multiple of p^{μ−2} to the (1,1) element, and obtain a new random symmetric matrix A such that

det(A) = p^{2} det(A) (mod p^{μ}),

so det(A) ≠ 0 (mod p^{μ}) with conditional probability P (n, p^{μ−2}). □

4 A three-term recurrence

The five-term recurrence (3.2) with boundary conditions (3.1) can be used to calculate P (n, p^{μ}) in O(nμ) arithmetic operations. However, to obtain inequalities and asymptotic results it is useful to have an explicit solution. To obtain such a solution, we first reduce (3.2) to a threeterm recurrence for P (n, p^{μ}) (n odd).

Theorem 4.1 If μ > 0 and boundary conditions are given by (3.1), then for odd n ≥ 3,

P (n, p^{μ}) = (1 − q^{n})P (n − 2, p^{μ}) + q^{n}P (n, p^{μ−2})  (4.1)

and for odd n ≥ 1,

P (n − 1, p^{μ}) = \frac{P (n, p^{μ}) − q^{n}P (n, p^{μ−1})}{1 − q^{n}}.  (4.2)

Remarks. Equation (4.1) is a three-term recurrence from which P (n, p^{μ}) can be calculated for odd n. Equation (4.2) then determines P (n, p^{μ}) for even n. Equations (4.1) and (4.2) do not hold for all n ≥ 3; for example, (4.2) fails if n is even and μ is odd. In the unsymmetric case [1], (4.2) holds for both even and odd n.

Proof (of Theorem 4.1) Let

P_{n} = P_{n}(x) = ∑_{μ=1}^{∞} P (n, p^{μ})x^{μ}  (4.3)

be a generating function for P (n, p^{μ}). From the boundary conditions (3.1) we have

P_{0} = x/(1 − x).  (4.4)

Theorem 3.1 gives

(1 − q^{n+1}x^{2})P_{n} = (1 − q)(1 + q^{n}x)P_{n−1} + q(1 − q^{n−1})P_{n−2}  (4.5)

for n ≥ 1. Thus, for odd n = 2k + 1 ≥ 1 we have

(1 − q^{2k+2}x^{2})P_{2k+1} = (1 − q)(1 + q^{2k+1}x)P_{2k} + q(1 − q^{2k})P_{2k−1}  (4.6)

and for even n = 2k + 2 ≥ 2 we have

(1 − q^{2k+3}x^{2})P_{2k+2} = (1 − q)(1 + q^{2k+2}x)P_{2k+1} + q(1 − q^{2k+1})P_{2k}.  (4.7)

Both (4.6) and (4.7) hold for k ≥ 0, and with the boundary condition (4.4) they define P_{n} for all n ≥ 0.

Assume for the moment that (4.1) and (4.2) are correct. From (4.1) with n = 2k +3 we have

P_{2k+3} = (\frac{1 − q^{2k+3}}{1 − q^{2k+3}x^{2}} ) P_{2k+1}  (4.8)

and from (4.2) with n = 2k + 1 we have

P_{2k} = (\frac{1 − q^{2k+1}x}{1 − q^{2k+1}}) P_{2k+1}.  (4.9)

Clearly (4.8) and (4.9) for k ≥ 0 and (4.4) define P_{n} for all n ≥ 0. Thus, it is sufficient to show that (4.8) and (4.9) for k ≥ 0 imply (4.6) and (4.7) for k ≥ 0.

From (4.8) and (4.9) we have

P_{1} = (\frac{1 − q}{1 − qx}) P_{0}  (4.10)

P_{2} = (\frac{1 − q^{3}x}{1 − q^{3}x^{2}} ) P_{1},  (4.11)

which satisfy (4.6) and (4.7) with k = 0. Thus, we may assume k ≥ 1. Equation (4.8) with k replaced by k − 1 gives

P_{2k−1} = (\frac{1 − q^{2k+1}x^{2}}{1 − q^{2k+1}} ) P_{2k+1}.  (4.12)

Substituting (4.9) and (4.12) in the right side of (4.8) and simplifying, we obtain (1−q^{2k+2}x^{2})P_{2k+1}, so (4.6) holds. Similarly, some algebra shows that (4.8) and (4.9) imply (4.7).

Thus, the same generating function P_{n}, n ≥ 0, is defined by (4.1) and (4.2) as by (4.5). □

We can now give an explicit formula for the generating function P_{n}.

Theorem 4.2 If k ≥ 0, then

P_{2k+1}(x) = (\frac{x}{1 − x}) (\frac{1 − qx^{2}}{1 − qx} ) ∏_{j=0}^{k} (\frac{1 − q^{2j+1}}{1 − q^{2j+1}x^{2}} )  (4.13)

and

P_{2k}(x) = (\frac{1 − q^{2k+1}x}{1 − q^{2k+1}}) P_{2k+1}(x).  (4.14)

Proof. Equation (4.13) follows by induction from (4.8), using (4.4) and (4.10). Equation (4.14) is just (4.9). □

5 An explicit solution and some bounds

From Theorem 4.2 we can obtain an explicit solution for P (n, p^{μ}), and hence for Q(n, p^{μ}). Define

Π_{n}(q) = ∏_{j=1}^{n} (1 − q^{j})

and

T_{β}(k, s) = \{ \begin{matrix}1, & if k = 0, \\ ∑_{j=0}^{s} q^{βj} \frac{Π_{k+j−1}(q^{2})}{Π_{j}(q^{2})Π_{k−1}(q^{2})}, & if k ≥ 1. \end{matrix}  (5.1)

Our explicit solution may be written in terms of T_{1} and T_{3}:

Theorem 5.1 If n ≥ 1, μ ≥ 1, k = ⌊n/2⌋, and s = ⌊(μ − 1)/2⌋ then

P (n, p^{μ}) = \frac{Π_{2k}(q)}{(1 − q)Π_{k}(q^{2})} ((1 − q^{2k+1})T_{3}(k, s) − q^{μ}(1 − q^{n})T_{1}(k, s)) .  (5.2)

Proof. We may show by induction on k from (4.1) that

P (2k + 1, p^{μ}) = \frac{Π_{2k+1}(q)}{(1 − q)Π_{k}(q^{2})} (T_{3}(k, s) − q^{μ}T_{1}(k, s)) .  (5.3)

Considering the cases μ = 2s + 1 and μ = 2s + 2 separately, it follows from (4.2) that

P (2k, p^{μ}) = P (2k + 1, p^{μ}) + q^{2k+μ} \frac{Π_{2k}(q)}{Π_{k}(q^{2})} T_{1}(k, s).  (5.4)

After some simplification we see that (5.2) holds both for n = 2k and n = 2k + 1. □

Equation (5.2) is inconvenient for numerical computation as P (n, p^{μ}) is close to 1 unless p^{μ} is small. In order to deduce a convenient expression for Q(n, p^{μ}) = 1 − P (n, p^{μ}), we use the following identities for T_{1} and T_{3}.

Lemma 5.1 If k ≥ 0 and s ≥ 0 then

T_{1}(k, s) = \frac{Π_{k}(q^{2})}{Π_{2k}(q)} (1 − q^{s+1} ∑_{j=0}^{k−1} q^{2j} \frac{Π_{2j}(q)Π_{j+s}(q^{2})}{Π_{j}(q^{2})^{2}Π_{s}(q^{2})}) .  (5.5)

and

T_{3}(k, s) = \frac{Π_{k}(q^{2})}{Π_{2k+1}(q)} (1 − q − q^{3s+3} ∑_{j=0}^{k−1} q^{2j} \frac{Π_{2j+1}(q)Π_{j+s}(q^{2})}{Π_{j}(q^{2})^{2}Π_{s}(q^{2})}) .  (5.6)

Proof. (5.5) and (5.6) may be proved by induction on k. The proof is similar to the proof of Theorem 2.1 of [1], so details are omitted. □

If we substitute (5.5) into (5.2) the factor Π_{k}(q^{2})/Π_{2k}(q) cancels. This gives a convenient explicit solution for Q(n, p^{μ}).

Theorem 5.2 If n ≥ 1, μ ≥ 1, k = ⌊n/2⌋, and s = ⌊(μ − 1)/2⌋ then

Q(n, p^{μ}) = \frac{q^{μ}(1 − q^{n}) − R}{1 − q}  (5.7)

where

R = q^{s+1} ∑_{j=0}^{k−1} (q^{μ}(1 − q^{n}) − q^{2s+2}(1 − q^{2j+1})) q^{2j} \frac{Π_{2j}(q)Π_{j+s}(q^{2})}{Π_{j}(q^{2})^{2}Π_{s}(q^{2})}  (5.8)

and

0 ≤ R < q^{3μ/2}.  (5.9)

Proof. Equations (5.7) and (5.8) follow from Theorem 5.1 and Lemma 5.1 after some simplification. Since μ ≤ 2s + 2 and n ≥ 2k, we have q^{μ}(1 − q^{n}) > q^{2s+2}(1 − q^{2j+1}) for 0 ≤ j ≤ k − 1, so R ≥ 0 (with equality only when k = 0). It is clear from (5.8) that R = O(q^{μ+s+1}) = O(q^{3μ/2}), and computation shows that R < q^{3μ/2} (the worst case is n large, μ = 2s+1 large and q = 1/2). □

We now show that P (n, p^{μ}) has the expected monotonicity properties.

Theorem 5.3 For n ≥ 0 and μ ≥ 0,

P (n + 1, p^{μ}) ≤ P (n, p^{μ}) ≤ P (n, p^{μ+1}).  (5.10)

Proof. The inequality P (n, p^{μ}) ≤ P (n, p^{μ+1}) follows by induction on n + μ from the recurrence (3.2), since the coefficients on the right side of (3.2) are independent of μ.

To prove P (n+1, p^{μ}) ≤ P (n, p^{μ}) we consider several cases. If n is even the inequality follows from (5.4). If n = 2k + 1 is odd and μ = 2s + 2 is even then, from Theorem 5.1,

P (2k + 1, p^{2s+2}) − P (2k + 2, p^{2s+2}) = q^{2k+2s+3}(1 + q)\frac{Π_{2k+1}(q)}{Π_{k}(q^{2})} T_{1}(k + 1, s) ≥ 0.

Finally, if n = 2k + 1 and μ = 2s + 1 are odd then, from Theorem 5.1,

P (2k + 1, p^{2s+1}) − P (2k + 2, p^{2s+1})

= q^{2k+2s+2} \frac{Π_{2k+1}(q)}{Π_{k}(q^{2})} (T_{1}(k + 1, s) − q^{s} \frac{Π_{k+s}(q^{2})}{Π_{s}(q^{2})})

≥ 0.

□

Corollary 5.1 lim_{n→∞} Q(n, p^{μ}) exists and lies in the interval [q^{μ}, q^{μ}/(1 − q)]. Moreover,

lim_{n→∞} P (n, p^{μ}) = \frac{Π_{∞}(q)}{(1 − q)Π_{∞}(q^{2})} ∑_{j=0}^{s} \frac{q^{3j} − q^{μ+j}}{Π_{j}(q^{2})}

and

lim_{n→∞} Q(n, p^{μ}) = (q^{μ} − \frac{Π_{∞}(q)}{Π_{∞}(q^{2})} ∑_{j=s+1}^{∞} \frac{q^{μ+j} − q^{3j}}{Π_{j}(q^{2})} ) /(1 − q),

where s = ⌊(μ − 1)/2⌋.

Proof. The limit exists by monotonicity in n, and the bounds follow from this monotonicity and Theorem 5.2. The explicit limits follow from Theorem 5.1 and Lemma 5.1 respectively. □

References

[1] R. P. Brent and B. D. McKay, Determinants and ranks of random matrices over Z_{m}, Discrete Math. 66 (1987) 35-49.

[2] L. Carlitz, Representations by quadratic forms in a finite field, Duke Math. J. 21 (1954) 123-137.