Stein's method and the rank distribution of random matrices over finite fields

Introduction

For readability and notational agreement with the examples that follow, we suppress $m$ in the definition of these distributions. Throughout, we also adopt the convention that an empty product takes the value 1. One of our main results, Theorem 1.1, provides sharp upper and lower bounds on the total variation distance between ${\mathcal{Q}}_{q,n}$, the distribution of $Q_{q,n}$ in (1) and its limit in (3), denoted ${\mathcal{Q}}_{q}$. Recall that the total variation distance between two probability distributions $P_{1},P_{2}$ on a finite set $S$ is given by

The upper bound in Theorem 1.1 appears quite difficult to compute directly by substituting the expressions for the point probabilities given in (1) and (3) into the defining expressions for the total variation distance in (4). In particular, even when $m=0,n=2$, the $p_{k,n}$ are not monotonic in $k$. On the other hand, use of Stein’s method Stn , CGS makes for a quite tractable computation. In Sections 4–7, we also apply our methods to ensembles of random matrices with symmetry constraints, in particular, to symmetric, symmetric with zero diagonal, skew symmetric, skew centrosymmetric and Hermitian matrices.

Next, we give five pointers to the large literature on the rank distribution of random matrices over finite fields, demonstrating that the subject is of interest. First, one of the earliest systematic studies of ranks of random matrices from the finite classical groups is due to Rudvalis and Shinoda RS , Sh . They determine the rank distribution of random matrices from finite classical groups, and relate distributions such as ${\mathcal{Q}}_{q}$ of (3) to identities of Euler. Second, ranks of random matrices from finite classical groups appear in works on the “Cohen–Lenstra heuristics” of number theory; see Wa for the finite general linear groups and Mal for the finite symplectic groups. Third, the rank distribution of random matrices over finite fields is useful in coding theory; see BS and Chapter 15 of MS . Fourth, the distribution of ranks of uniformly chosen random matrices over finite fields has been used to test random number generators DGM , and there is interest in the rate of convergence to ${\mathcal{Q}}_{q}$. Fifth, there is work on ranks of random matrices over finite fields where the matrix entries are independent and identically distributed, but not necessarily uniform. For example, the paper CRR uses a combination of Möbius inversion, finite Fourier transforms and Poisson summation, to find conditions on the distribution of matrix entries under which the probability of a matrix being invertible tends to $p_{0}$ as $n\rightarrow\infty$. Further results in this direction, including rank distributions of sparse matrices, can be found in BKW , Co1 , Co2 , KK . It would be valuable (but challenging) to extend our methods to these settings.

The organization of this paper is as follows. Section 2 provides some general tools for our application of Stein’s method, and useful bounds on products such as $\prod_{i}(1-1/q^{i})$. The development followed here is along the lines of the “comparison of generators” method as in GR and H . Section 3 treats the rank distribution of uniformly chosen $n\times(n+m)$ matrices over a finite field, proving Theorem 1.1. Section 4 treats the rank distribution of random symmetric matrices over a finite field. Section 5 provides results for the rank distribution of a uniformly chosen symmetric matrix with 0 diagonal; these are called “symplectic” matrices in Chapter 15 of MS , which uses their rank distribution in the context of error correcting codes. The same formulas for the rank distribution of symmetric matrices with zero diagonal also apply to the rank distribution of random skew-symmetric matrices, when $q$ is odd. Section 6 treats the rank distribution of random skew centrosymmetric matrices over finite fields, and Section 7 treats the rank distribution of random Hermitian matrices over finite fields. The Appendix gives an algebraic proof, for the special case $m=0$ of square matrices, of the crucial fact (proved probabilistically in Section 3 in general) that if $Q_{n}$ has distribution ${\mathcal{Q}}_{q,n}$ of (1), then $E(q^{Q_{n}})=2-1/q^{n}$.

In the interest of notational simplicity, in Sections 4–7, the specific rank distributions of the $n\times n$ matrices of interest, and their limits, will apply only locally in the section or subsection that contains them, and will there be consistently denoted by ${\mathcal{Q}}_{q,n}$ and ${\mathcal{Q}}_{q}$, respectively.

Preliminaries

We begin with a general result for obtaining characterizations of discrete integer distributions. We note that a version of Lemma 2.1 can be obtained by replacing $f(x)$ by $f(x)b(x)$ in Theorem 2.1 of LS , followed by a reversal of the interval $[a,b]$, with similar remarks applying to the use of Proposition 2.1 and Corollary 2.1 of GR . However, the following lemma and its short, simple proof contain the precise conditions used throughout this work and keep the paper self-contained.

then a random variable $X$ having distribution ${\mathcal{L}}(Y)$ satisfies

For example, when $Y$ has the Poisson distribution ${\mathcal{P}}(\lambda)$ with parameter $\lambda$, then $r_{k}=e^{-\lambda}\lambda^{k}/k!$, and we obtain

Setting $b(k)=k$ and $a(k)=\lambda$ yields the standard characterization of the Poisson distribution bhj ,

Now replacing $P(Q\in A\cap U_{k})$ and $P(Q\in A)$ in the first and second term, respectively, by

canceling the resulting common factor demonstrates that the solution $f_{A}$ satisfies

with equality when $A=U_{k}$. Since $f_{A^{c}}(k)=-f_{A}(k)$ the bound (13) holds for $|f_{A}(k+1)|$.

Lemma 2.3 collects some bounds that will be useful. We first state the simple inequality

valid for $a_{i}\in,i=1,\ldots,n$, and easily shown by induction.

The first claim is Lemma 3.5 of NP , and arguing as there yields the second claim. Thus,

which is positive for $q\geq 2$. The next inequality now follows by applying the one just shown to obtain

it is easy to see that the second claim of Lemma 2.3 implies the first.

Uniform matrices over finite fields

The following lemma is our first application of the characterizations provided by Lemma 2.1.

If $Q$ has the ${\mathcal{Q}}_{q}$ distribution then

for all functions $f$ for which these expectations exist.

If $Q_{n}$ has the ${\mathcal{Q}}_{q,n}$ distribution, then

for all functions $f$ for which these expectations exist.

An application of Lemma 2.1 with $a(k)=q$ and $b(k)=(q^{k}-1)(q^{k+m}-1)$ yields (15). Similarly, from (1) we obtain

An application of Lemma 2.1 with $a(k)=q(1-q^{-n+k-1})$, $b(k)=(q^{k}-1)(q^{k+m}-1)$, noting $a(n+1)=0$, yields (16).

Here, we calculate $E(q^{Q_{n}})$ using the characterization (16). An algebraic proof for the case $m=0$ of Lemma 3.2 appears in the Appendix. After reading the first version of this paper, Dennis Stanton has shown us a proof of this special case using the $q$-Chu–Vandermonde summation formula.

If $Q_{n}$ has the ${\mathcal{Q}}_{q,n}$ distribution on $U_{n}=\{0,1,\ldots,n\}$ given by (1), then

Applying the characterization (16) with the choice $f(x)=q^{kx}$, we obtain

Letting $c_{k}=Eq^{kQ_{n}}$ yields the recursion

Since ${\mathcal{Q}}_{q,n}$ is a probability distribution, $c_{0}=1$, and setting $k=-1$ in (18) yields the claim.

In the remainder of this section, we consider the Stein equation (8), with

where we have applied the last part of Lemma 2.3. For $m=0$, using the first inequality of Lemma 2.3 in the last step gives that

Now consider the case $k\geq 1$. By (13) and (19), we have

and by neglecting the term $P(Q\in U_{k})$ in (20) and applying (3) we obtain

where for the third inequality we have applied (14).

As the left-hand side is increasing in $k\geq 1$, it suffices to prove the claim for $k=1$. In this case, the claim may be rewritten as

As $q\geq 2$, the result is a consequence of the two easily verified inequalities

Hence, for $k\geq 1$, using $q\geq 2$, we obtain

where the final inequality used that $2/q^{m+3}\leq 1/q^{m+2}$, and that $\sum_{l=2}^{\infty}\frac{1}{2^{2+l}}\leq 1/4$, thus completing the proof of the lemma.

Proof of Theorem 1.1 We first compute the lower bound on the total variation distance by estimating the difference of the two distributions at $k=0$. In particular, by (4), (1) and (3),

The fourth inequality used Lemma 2.3, and the last that $q\geq 2$.

For the upper bound, with $h_{A}(k)={\mathbf{1}}(k\in A)$ we obtain

where we have applied (16) in the third equality. Applying Lemmas 3.3 and 3.2 gives that for $m\geq 1$,

For $m=0$, applying Lemmas 3.3 and 3.2 gives that

When $m=0$, the limit distribution ${\mathcal{Q}}_{q}$ also arises in the study of the dimension of the fixed space of a random element of $\operatorname{GL}(n,q)$. More precisely, Rudvalis and Shinoda RS prove that for $k$ fixed, as $n\rightarrow\infty$ the probability that a random element of $\operatorname{GL}(n,q)$ has a $k$ dimensional fixed space tends to $p_{k}$. See F3 for another proof.

Symmetric matrices over finite fields

If $Q$ has the ${\mathcal{Q}}_{q}$ distribution then

for all functions $f$ for which these expectations exist.

If $Q_{n}$ has the ${\mathcal{Q}}_{q,n}$ distribution then

for all functions $f$ for which these expectations exist.

Setting $a(k)=1$ and $b(k)=q^{k}-1$ applying Lemma 2.1 yields the first result.

If $n$ and $k$ are of the same parity, then $n-k=2h$ for some $h$, and we have

In this case, we set $a(k)=1$ and $b(k)=q^{k}-1$.

If $k$ and $n$ are of opposite parity, then $n-k=2h+1$ for some $h$ and we obtain

In this case, we set $a(k)=1-q^{-n+k-1}$ and $b(k)=q^{k}-1$.

Writing $a(k)=1-{\mathbf{1}}_{n-k+1}q^{-n+k-1}$ and $b(k)=q^{k}-1$ combines both cases. Noting that $a(n+1)=0$ an application of Lemma 2.1 completes the proof.

If $Q_{n}$ has distribution ${\mathcal{Q}}_{q,n}$ then

Setting $f(x)={\mathbf{1}}_{n-x}$ in (25) yields

Since ${\mathbf{1}}_{n-Q_{n}}{\mathbf{1}}_{n-Q_{n}-1}=0$, we obtain

In the remainder of this section, we consider the Stein equation (8) for the target distribution ${\mathcal{Q}}_{q}$ with

where we applied the third inequality in Lemma 2.3.

In particular, for all $k\geq 1$ we obtain

and the proof is now completed by using the fact that for all $q\geq 2$

The upper bound on the first factor used the second assertion of Lemma 2.3. Indeed,

The upper bound on the second factor used that

Proof of Theorem 4.1 For the lower bound, one computes from the formula for $p_{0,n}$ in (4), in the case $n=2m$ is even, that

Thus, the total variation distance between ${\mathcal{Q}}_{q,n}$ and ${\mathcal{Q}}_{q}$ is at least

The second inequality used Lemma 2.3, and the final inequality that $q\geq 2$.

When $n=2m+1$ is odd, we obtain similarly that

and the result easily follows. The last two steps used Lemmas 4.3 and 4.4, respectively.

Symmetric matrices over finite fields with zero diagonal

We begin the proof of Theorem 5.1 by developing characterizations of the two distributions of interest.

If $Q$ has the ${\mathcal{Q}}_{q}$ distribution, then

for all functions $f$ for which these expectations exist.

If $Q_{n}$ has the ${\mathcal{Q}}_{q,n}$ distribution then

for all functions $f$ for which these expectations exist.

Setting $a(k)=q^{2}$ and $b(k)=(q^{2k-1}-1)(q^{2k}-1)$, applying Lemma 2.1 yields the first result.

Similarly, the second claim can be shown using Lemma 2.1 and (27) to yield

upon setting $a(k)=q^{2}-q^{-2(m-k)}$ and $b(k)=(q^{2k-1}-1)(q^{2k}-1)$, noting that $a(m+1)=0$.

If $Q_{n}$ has distribution ${\mathcal{Q}}_{q,n}$, then

For $k$ any integer, letting $f(x)=q^{kx}$ in (5.2) yields

Setting $c_{k}=Eq^{kQ_{n}}$, this identity yields

Substituting $k=-2$ and using that $c_{0}=1$ we obtain

In the remainder of this subsection we consider the Stein equation (8) for the target distribution ${\mathcal{Q}}_{q}$ with

where the second inequality used Lemma 2.3.

and the proof is now completed using the fact that for all $q\geq 2$

The upper bound on the first factor used part 2 of Lemma 2.3. The upper bound on the second factor used that

Proof of Theorem 5.1 From the formula for $p_{0,n}$, one has that

The argument in the proof of Theorem 4.1 now shows that total variation distance between ${\mathcal{Q}}_{q,n}$ and ${\mathcal{Q}}_{q}$ is at least $0.18/q^{n+1}$.

For the upper bound, arguing as in the proof of Theorem 4.1 we obtain

as claimed. Note that Lemma 5.3 was used in the fourth equality, and Lemma 5.4 in the second to last inequality.

2 Case of n𝑛n odd

Our main result is the following theorem.

We again begin by developing characterizing equations for the distributions under study.

If $Q$ has the ${\mathcal{Q}}_{q}$ distribution, then

for all functions $f$ for which these expectations exist.

If $Q_{n}$ has the ${\mathcal{Q}}_{q,n}$ distribution then

for all functions $f$ for which these expectations exist.

Setting $a(k)=q^{2}$ and $b(k)=(q^{2k+1}-1)(q^{2k}-1)$, Lemma 2.1 yields the first claim. Similarly, the second can be shown by applying (30) to yield

and then invoking Lemma 2.1 with $a(k)=q^{2}-q^{-2(m-k)}$ and $b(k)=(q^{2k+1}-1)(q^{2k}-1)$, noting $a(m+1)=0$.

If $Q_{n}$ has distribution ${\mathcal{Q}}_{q,n}$ then

For $k$ any integer, letting $f(x)=q^{kx}$ in (5.6) yields

Setting $c_{k}=E[q^{kQ_{n}}]$, this identity yields

Substituting $k=-2$ and using that $c_{0}=1$ we obtain

In the remainder of this subsection, we consider the Stein equation (8) for the target distribution ${\mathcal{Q}}_{q}$ with

where the second inequality used Lemma 2.3.

and the proof is now completed by using the fact that for all $q\geq 2$,

The inequality $\prod_{i=4}^{\infty}(1-q^{-i})^{-1}\leq 1.137$ is obtained by applying part 2 of Lemma 2.3. We also used that

Proof of Theorem 5.5 From the formula (30) for $p_{0,n}$, we obtain

Thus, now applying (29), the total variation distance between ${\mathcal{Q}}_{q,n}$ and ${\mathcal{Q}}_{q}$ is at least

The second inequality used the fourth claim of Lemma 2.3.

as claimed, where we have applied Lemmas 5.7 and 5.8 in the second to last equality, and inequality, respectively.

Skew centrosymmetric matrices over finite fields

Suppose that $n$ is even. Waterhouse W shows that the total number of skew centrosymmetric matrices is $q^{(n/2)^{2}}$, that all such matrices have even rank, and that the proportion of $n\times n$ skew centrosymmetric matrices of rank $n-2k$ is equal to

Comparing this expression with (1) for the case $m=0$ with $n$ replaced by $n/2$ shows that it is sufficient to prove that

are equal to $\prod_{i=1}^{n/2}(1-1/q^{i})$. Hence, the following corollary is immediate from Theorem 1.1.

Now suppose that $n$ is odd. Waterhouse W shows that the total number of skew centrosymmetric matrices is $q^{(n-1)^{2}/4+(n-1)/2}$, that all such matrices have even rank and that the number of $n\times n$ skew centrosymmetric matrices of rank $2h$ is equal to

is the proportion of skew centrosymmetric matrices of rank $n-2k-1$. The main result in this section is Theorem 6.2, which provides bounds on the total variation distance between ${\mathcal{Q}}_{q,n}$, the distribution given in (34), and ${\mathcal{Q}}_{q}$, given by

For $n\geq 1$ odd, and $q\geq 2$, we have that

We begin with the following characterization lemma.

If $Q$ has the ${\mathcal{Q}}_{q}$ distribution, then

for all functions $f$ for which these expectations exist.

If $Q_{n}$ has the ${\mathcal{Q}}_{q,n}$ distribution, then

for all functions $f$ for which these expectations exist.

For the first assertion, one calculates that

Taking $a(k)=q$ and $b(k)=(q^{k}-1)(q^{k+1}-1)$ in Lemma 2.1, the first assertion follows.

For the second assertion, one calculates that

Taking $a(k)=q-q^{k-(n-1)/2}$ and $b(k)=(q^{k}-1)(q^{k+1}-1)$, noting that $a((n-1)/2+1)=0$, the second assertion follows by Lemma 2.1.

Lemma 6.4 calculates the expected value of $q^{Q_{n}}$.

If $Q_{n}$ has distribution ${\mathcal{Q}}_{q,n}$, then

Let $c_{k}=E[q^{kQ_{n}}]$, and set $f(x)=q^{kx}$ in (36). Elementary manipulations yield the recurrence

The result now follows by setting $k=-1$ and using that $c_{0}=1$.

In the remainder of this section, we consider the Stein equation (8) for the target distribution ${\mathcal{Q}}_{q}$ with

where we have applied (14) in the second inequality, and used that $q\geq 2$.

where (14) was applied in the fourth inequality.

Proof of Theorem 6.2 From the formula (34) for $p_{0,n}$, one computes that

Thus, using (35), the total variation distance between ${\mathcal{Q}}_{q,n}$ and ${\mathcal{Q}}_{q}$ is at least

It follows that the total variation distance between ${\mathcal{Q}}_{q,n}$ and ${\mathcal{Q}}_{q}$ is at least $1/(4q^{(n+3)/2})$.

For the upper bound, arguing as in Theorem 1.1,

By Lemmas 6.4 and 6.5, this quantity is at most

Hermitian matrices over finite fields

Hence, the proportion of such matrices with rank $n-k$ is given by

In this section we compute total variation bounds between the distribution (37), denoted ${\mathcal{Q}}_{q,n}$, and the distribution

which we denote here by ${\mathcal{Q}}_{q}$.

The distribution (38) also arises as a limiting law in the study of the dimension of the fixed space of a random element of the finite unitary group $U(n,q)$. More precisely, the paper RS proves that for $k$ fixed, the chance that a uniformly chosen random element of $U(n,q)$ has a $k$ dimensional fixed space tends to $p_{k}$ as $n\rightarrow\infty$. See F3 for another proof.

The main theorem of this section is the following result.

The following lemma characterizes the two distributions of interest in this section.

If $Q$ has the ${\mathcal{Q}}_{q}$ distribution, then

for all functions $f$ for which these expectations exist.

If $Q_{n}$ has the ${\mathcal{Q}}_{q,n}$ distribution, then

for all functions $f$ for which these expectations exist.

For the first assertion, one calculates from (38) that

Taking $a(k)=q$ and $b(k)=q^{2k}-1$ in Lemma 2.1, the first assertion follows.

For the second assertion, one calculates that

Taking $a(k)=q-(-1)^{n-k+1}q^{k-n}$ and $b(k)=q^{2k}-1$ in Lemma 2.1, and noting $a(n+1)=0$, the second assertion follows.

Next, we handle the moment $E[q^{Q_{n}}]$. Unlike all our other moment computations where we obtain equality, here we derive an upper bound.

If $Q_{n}$ has the ${\mathcal{Q}}_{q,n}$ distribution, then

Setting $f(x)=q^{-x}$ in (39) implies that

In the remainder of this section, we consider the Stein equation (8) for the target distribution ${\mathcal{Q}}_{q}$ with

By (38), (40) and the third claim of Lemma 2.3,

Thus, $1-p_{0}\leq 1/q+1/q^{5}\leq 1.1/q$, and hence $|f_{A}(1)|\leq 1.1/q^{2}$, for all $q\geq 2$.

using $k\geq 1$ in the final inequality. Now using that $d_{q}$ and $s_{q}$ are decreasing for $q\geq 2$, and that

Now we present the proof of the main result of this section, Theorem 7.1.

Proof of Theorem 7.1 We first compute a lower bound for the case where $n$ is odd. From (37), we have

where the fourth inequality used the third claim of Lemma 2.3. Thus, the total variation distance between ${\mathcal{Q}}_{q,n}$ and ${\mathcal{Q}}_{q}$ is at least $\frac{1}{2}[p_{0}-p_{0,n}]\geq 0.07/q^{n+1}$.

Now we compute a lower bound for $n$ even. From (37),

where the fourth inequality used the third claim of Lemma 2.3. Thus, the total variation distance between ${\mathcal{Q}}_{q,n}$ and ${\mathcal{Q}}_{q}$ is at least $\frac{1}{2}[p_{0,n}-p_{0}]\geq 0.09/q^{n+1}$.

For the upper bound, arguing as in the proof of Theorem 4.1,

for $n\geq 1$. The third inequality used Lemmas 7.3 and 7.4.

The distribution $p_{k,n}$ of (37) holds for $q\geq 3$. Over this range, the bounds of Theorem 7.1 may be slightly improved by applying (7) and (7) to replace 1.8 in Lemma 7.4 by 1.4, and then using this value in (7). One may similarly improve the lower bound by replacing 0.14 by 0.38 in (7), and 0.18 by 0.41 in (7), resulting in

Appendix

The main purpose of this appendix is to give an algebraic proof of Lemma 3.2 in the special case that $m=0$. The proof assumes familiarity with rational canonical forms of matrices (i.e., the theory of Jordan forms over finite fields), and with cycle index generating functions. Background on these topics can be found in F1 or St , or in the survey F2 .

Proof of Lemma 3.2 when $m=0$ The sought equation is

From the expression for $p_{k,n}$ in (1) specialized to the case $m=0$, it is clear that if one multiplies (48) by $q^{t}(1-1/q)\cdots(1-1/q^{n})$ where $t$ is sufficiently large as a function of $n$, then both sides become polynomials in $q$. Since polynomials in $q$ agreeing for infinitely many values of $q$ are equal, it is enough to prove the result for infinitely many values of $q$, so we demonstrate it for $q$ a prime power.

From the cycle index for $\operatorname{Mat}(n,q)$ (Lemma 1 of St ), it follows that

From the cycle index for $\operatorname{GL}(n,q)$ (Lemma 1 of St ), it follows that

Summarizing, it follows from (Appendix) and (51) that

The third equality used (51) and the final equality is from Lemma 6 of St and page 19 of A .

Next, we can use group theory to find an alternate expression for

Indeed, by the theory of rational canonical forms, $q^{l(\lambda_{z-1}(\alpha))}$ is the number of fixed points of $\alpha$ in its action on the underlying $n$ dimensional vector space $V$. By Burnside’s lemma (page 95 of VW ), the average number of fixed points of a finite group acting on a finite set is the number of orbits of the action on the set. For $\operatorname{GL}(n,q)$ acting on $V$, there are two such orbits, consisting of the zero vector and the set of nonzero vectors. Thus,

Comparing the final equations of the previous two paragraphs gives that

Thus, by (49), $E(q^{Q_{n}})$ is $\frac{|\operatorname{GL}(n,q)|}{q^{n^{2}}}$ multiplied by the coefficient of $u^{n}$ in

From page 19 of A , the coefficient of $u^{n}$ in

is equal to $[(1-1/q)(1-1/q^{2})\cdots(1-1/q^{n})]^{-1}$. Thus,

where the last equality used that $|\operatorname{GL}(n,q)|=q^{n^{2}}(1-1/q)\cdots(1-1/q^{n})$.

We close this section with two remarks about the distribution ${\mathcal{Q}}_{q,n}$ in (1) (for general $m$) from the Introduction.

From Be , there is a natural Markov chain on $\{0,1,\ldots,n\}$ which has ${\mathcal{Q}}_{q,n}$ as its stationary distribution. This chain has transition probabilities

This Markov chain describes how the rank of a matrix evolves by adding a uniformly chosen rank one matrix at each step.

Following a suggestion of Dennis Stanton, we indicate how Lemma .1 can be used to derive the product formula for $p_{k,n}$ in the Introduction. By replacing $k$ by $n$, $n$ by $n+m$, and $r$ by $n-k$ in (54), we get that the probability that a random $n\times(n+m)$ matrix has rank $n-k$ is equal to

Plugging into the $q$-binomial theorem (page 78 of Br )

It follows from elementary manipulations that this is equal to

Acknowledgements

The authors thank Dennis Stanton and the referees for helpful comments.

References