Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-23T06:06:23.412Z Has data issue: false hasContentIssue false

SOME COUNTING QUESTIONS FOR MATRIX PRODUCTS

Published online by Cambridge University Press:  09 October 2023

MUHAMMAD AFIFURRAHMAN*
Affiliation:
School of Mathematics and Statistics, University of New South Wales, Sydney NSW 2052, Australia
Rights & Permissions [Opens in a new window]

Abstract

Given a set X of $n\times n$ matrices and a positive integer m, we consider the problem of estimating the cardinalities of the product sets $A_1 \cdots A_m$, where $A_i\in X$. When $X={\mathcal M}_n(\mathbb {Z};H)$, the set of $n\times n$ matrices with integer elements of size at most H, we give several bounds on the cardinalities of the product sets and solution sets of related equations such as $A_1 \cdots A_m=C$ and $A_1 \cdots A_m=B_1 \cdots B_m$. We also consider the case where X is the subset of matrices in ${\mathcal M}_n(\mathbb {F})$, where $\mathbb {F}$ is a field with bounded rank $k\leq n$. In this case, we completely classify the related product set.

Type
Research Article
Copyright
© The Author(s), 2023. Published by Cambridge University Press on behalf of Australian Mathematical Publishing Association Inc.

1 Introduction

1.1 Set-up and motivation

For positive integers n and H, let ${\mathcal M}_n(\mathbb {Z};H)$ be the set of $n\times n$ integer matrices

$$ \begin{align*}A=(a_{ij})_{i,j=1}^n\end{align*} $$

with $|a_{ij}|\leq H$ for $i,j=1,\ldots ,n$ . We see that ${\mathcal M}_n(\mathbb {Z};H)$ is of cardinality $(2H+1)^{n^2}$ .

We consider some questions in arithmetic statistics of the matrices in ${\mathcal M}_n(\mathbb {Z};H)$ (where $H\to \infty $ ) and ${\mathcal M}_n(\mathbb {F})$ (where $\mathbb {F}$ is a field), where n is fixed. In particular, we are interested on the product set

$$ \begin{align*} \{A_1\cdots A_m \colon A_i \in X_i\}, \end{align*} $$

where $X_i \subseteq {\mathcal M}_n(\mathbb {Z};H)$ or $X_i \subseteq {\mathcal M}_n(\mathbb {F})$ for $i=1,\ldots , m$ .

For the first case, we derive some bounds on the cardinality of the set where $X_i={\mathcal M}_n(\mathbb {Z};H)$ and also give some bounds on related equations over ${\mathcal M}_n(\mathbb {Z};H)$ . For the second case, we completely describe the set in the case where $X_i$ is the set of matrices with rank at most $k_i\leq n$ .

Several similar problems over matrix rings with an additive combinatorics flavour have been studied, mostly for matrices over finite fields. For example, [Reference Ferguson, Hoffman, Luca, Ostafe and Shparlinski6] studies the distribution of singular and unimodular matrices over subsets of a matrix ring, [Reference Demiroğlu-Karabulut, Koh, Pham, Shen and Vinh Le2, Reference Helfgott9, Reference Helfgott10, Reference Van The and Vinh19] study expansion phenomena over matrix rings and [Reference Mohammadi, Pham and Wang15, Reference Nguyen and Vinh16, Reference Xie and Ge20] study the number of solutions of some equations in ${\mathcal M}_n(\mathbb {F}_q)$ , where $\mathbb {F}_q$ is the finite field whose cardinality is a prime power q.

In another direction, Ahmadi and Shparlinski [Reference Ahmadi and Shparlinski1] study the arithmetic statistics of ${\mathcal M}_{m,n}(H;\mathbb {F}_p)$ , the set of $m\times n$ matrices in $\mathbb {F}_p$ (where p is prime) whose entries are bounded by H. Also, El-Baz et al. [Reference El-Baz, Lee and Strömbergsson4] give asymptotic counts of the number of $d\times n$ integer matrices with a bounded norm whose rank (reduced modulo a prime p) is a fixed number r.

1.2 Integer matrices with bounded entries

For ${\mathcal M}_n(\mathbb {Z};H)$ , we count the number of tuples of matrices in ${\mathcal M}_n(\mathbb {Z};H)$ that satisfy some given multiplicative relations. This can be seen as a dual of the results of Ostafe and Shparlinski [Reference Ostafe and Shparlinski17], who consider counting the numbers of matrices in ${\mathcal M}_n(\mathbb {Z};H)$ that are multiplicatively dependent (that is, they satisfy a multiplicative relation but it is not given in advance).

Our main problem for ${\mathcal M}_n(\mathbb {Z};H)$ is to estimate the cardinality of

(1.1) $$ \begin{align} {\mathcal W}_{m,n}(\mathbb{Z};H)=\{ A_1 \cdots A_m \colon A_1, \ldots ,A_m \in {\mathcal M}_n(\mathbb{Z};H)\} \end{align} $$

for fixed m and n.

For $n=1$ , the question of estimating $\#{\mathcal W}_{m,n}(\mathbb {Z};H)$ is known as Erdős’ multiplication table problem, popularised by Erdős [Reference Erdős5]. Ford [Reference Ford8] gave an asymptotic formula for this quantity when $m=2$ and Koukoulopoulos [Reference Koukoulopoulos14] generalised Ford’s result for all $m>2$ . Our problem is a noncommutative analogue.

We first observe that ${\mathcal M}_{n}(\mathbb {Z};H)\subseteq {\mathcal W}_{m,n}(\mathbb {Z};H)$ . This gives a trivial lower bound

$$ \begin{align*} \# {\mathcal W}_{m,n}(\mathbb{Z};H) \gg H^{n^2}. \end{align*} $$

By noting that there are $O(H^{n^2})$ choices for each of $A_1,\ldots ,A_m$ , we have a trivial upper bound

$$ \begin{align*}\# {\mathcal W}_{m,n}(\mathbb{Z};H)= O(H^{mn^2})\end{align*} $$

for all m. These two bounds are improved in Theorem 2.3.

While proving Theorem 2.3, we also give some bounds on the number of solutions of related equations in $ {\mathcal M}_n(\mathbb {Z};H)$ , such as

(1.2) $$ \begin{align}A_1 \cdots A_m=C \end{align} $$

for a fixed matrix C, and

(1.3) $$ \begin{align}A_1 \cdots A_m=B_1 \cdots B_m. \end{align} $$

We consider these problems over both the sets ${\mathcal M}_{n}(\mathbb {Z};H)$ and ${\mathcal M}_{n}^*(\mathbb {Z};H)$ , the set of nonsingular matrices in ${\mathcal M}_{n}(\mathbb {Z};H)$ .

When $n=1$ , these problems are equivalent to bounding the number of divisors of a positive integer k. In this case, the result is well known (see Lemma 3.4). However, the situation becomes trickier in higher dimensions due to matrix noncommutativity and the absence of an analogue of prime number factorisation for matrices.

We now define some related notation. For a set of $n\times n$ matrices ${\mathcal M}$ and a matrix C, denote

(1.4) $$ \begin{align} {\mathcal T}_m({\mathcal M},C) = \{(A_1, \ldots, A_m) \in {\mathcal M}^m \colon A_1 \cdots A_m=C \}. \end{align} $$

Also, define

$$ \begin{align*} {\mathcal T}_{m}({\mathcal M})= \{(A_1,\ldots,A_m, B_1,\ldots,B_m) \in {\mathcal M}^{2m}: A_1\cdots A_m = B_1\cdots B_m\}. \end{align*} $$

Using this notation, we see that the number of solutions of (1.2) and (1.3) is $\#{\mathcal T}_m({\mathcal M}_{n}(\mathbb {Z};H),C)$ and $\#{\mathcal T}_m({\mathcal M}_{n}(\mathbb {Z};H))$ , respectively. We first note that for any C,

$$ \begin{align*}\#{\mathcal T}_m({\mathcal M}_{n}(\mathbb{Z};H),C) \ll H^{mn^2-1}\end{align*} $$

by fixing all entries of $A_2,\ldots ,A_{m}$ and all, except one, entries of $A_1$ . Furthermore, if C is nonsingular, we see that any matrices $A_2,\ldots ,A_m$ lead to at most one matrix $A_1$ that satisfies (1.2). Therefore, in this case,

$$ \begin{align*}\#{\mathcal T}_m({\mathcal M}^*_{n}(\mathbb{Z};H),C)=\#{\mathcal T}_m({\mathcal M}_{n}(\mathbb{Z};H),C)\ll H^{(m-1)n^2}.\end{align*} $$

By using the same argument, we see that

$$ \begin{align*} \#{\mathcal T}_m({\mathcal M}^*_n(\mathbb{Z};H)) \leq \#{\mathcal T}_m({\mathcal M}_n(\mathbb{Z};H)) \ll H^{2mn^2}. \end{align*} $$

These trivial upper bounds are improved in Theorem 2.1 and Corollary 2.2.

For the lower bounds, we observe that

$$ \begin{align*} \#{\mathcal T}_m({\mathcal M}^*_n(\mathbb{Z};H))\gg H^{mn^2} \end{align*} $$

by taking $A_i=B_i$ for $i=1,\ldots ,m$ and noticing that there are asymptotically $H^{n^2}$ matrices in ${\mathcal M}^*_n(\mathbb {Z};H)$ . Also,

$$ \begin{align*} \#{\mathcal T}_m({\mathcal M}_n(\mathbb{Z};H))\gg H^{(2m-2)n^2} \end{align*} $$

by taking $A_m=B_m=O_n$ in the related equation.

1.3 Matrices over an arbitrary field

For ${\mathcal M}_n(\mathbb {F})$ , we let $S_1, \ldots , S_m \subseteq {\mathcal M}_n(\mathbb {F})$ be some subsets of $ {\mathcal M}_n(\mathbb {F})$ with some prescribed properties. We study sets of the form

$$ \begin{align*} \{A_1\cdots A_m \colon A_i \in S_i\text{ for }i=1,\ldots,m \}. \end{align*} $$

We explore the question where $S_i$ , with $i=1,\ldots ,m$ , are the sets of all $n\times n$ matrices with bounded rank $k_i\leq n$ . This is done in Theorem 2.4 and Corollary 2.5, using the matrix construction in Theorem 3.5.

1.4 Notation

We recall that the notation $U= O(V)$ , $U\ll V$ and $V\gg U$ are equivalent to $|U| \leq cV$ for some positive constant c. Throughout this work, all implied constants may depend only on m and n. We write $U(x){\kern-1.2pt}={\kern-1.2pt}o(V(x))$ if $\lim _{x\to \infty } (U(x)/V(x)){\kern-1.2pt}={\kern-1.2pt}0$ . We write $U \sim V$ if $U=O(V)$ and $V=O(U)$ . We also write $U=V^{o(1)}$ if, for a given $\varepsilon>0$ , we have $V^{-\varepsilon }\leq |U| \leq V^{\varepsilon }$ for large enough V.

We denote the zero $n\times n$ matrix by $O_{n}$ and the zero vector (whose size is taken depending on the context) by $\textbf {0}$ .

2 Main results

2.1 Integer matrices with bounded entries

We first consider the equation $A_1 \ldots A_m=C$ , where $C $ is fixed. We obtain the following uniform bounds for the cardinality of ${\mathcal T}_m({\mathcal M}_{n}(\mathbb {Z};H),C)$ (defined in (1.4)).

Theorem 2.1. Let C be an $n\times n$ matrix. Then, uniformly in m and n,

$$ \begin{align*} \#{\mathcal T}_m({\mathcal M}_{n}(\mathbb{Z};H),C) \leq \begin{cases} H^{(m-1)(n^2-n)+o(1)} &\text{if }C\text{ is nonsingular for all } m,\\ H^{n^2+o(1)} &\text{if }C\neq O_n\text{ is singular and }m=2,\\ H^{mn^2-n+o(1)} &\text{if }C\neq O_n\text{ is singular and }m\geq 3. \end{cases} \end{align*} $$

Furthermore, when $C=O_n$ where $O_n$ is the zero $n\times n$ matrix,

$$ \begin{align*}H^{(m-1)n^2} \ll \#{\mathcal T}_m({\mathcal M}_{n}(\mathbb{Z};H),O_{n}) \leq H^{(m-1)n^2+o(1)}. \end{align*} $$

It would be interesting to tighten these bounds. For the case $C=O_n$ , it is also interesting to obtain a better error term on the asymptotic cardinality of $\#{\mathcal T}_m({\mathcal M}_{n}(\mathbb {Z};H),O_{n})$ , as $H\to \infty $ .

Next, we give some upper bounds on the number of solutions of the equation

$$ \begin{align*}A_1\cdots A_m = B_1\cdots B_m,\end{align*} $$

where either all matrices are in ${\mathcal M}_n(\mathbb {Z};H)$ or all are in ${\mathcal M}^*_n(\mathbb {Z};H)$ (in other words, all matrices are nonsingular). We obtain the following bounds as a corollary of Theorem 2.1.

Corollary 2.2. For all $m,n\geq 2$ , we have $\#{\mathcal T}_m({\mathcal M}^*_n(\mathbb {Z};H))\leq H^{(2m-1)n^2-(m-1)n+o(1)}$ . Also,

$$ \begin{align*} \#{\mathcal T}_2({\mathcal M}_n(\mathbb{Z};H))\leq \begin{cases} H^{3n^2-n+o(1)} &\text{if }m=2,\\ H^{2mn^2-2n+o(1)} &\text{if }m\geq 3. \end{cases} \end{align*} $$

It would be interesting to reduce the gap between the upper and lower bounds of these quantities.

Finally, we give some bounds on $\#{\mathcal W}_{m,n}(\mathbb {Z};H)$ , defined in (1.1).

Theorem 2.3. For all $m,n\geq 2$ , we have $H^{n^2+mn-n+o(1)}\leq \#{\mathcal W}_{m,n}(\mathbb {Z};H)$ . If $m\geq 6$ ,

$$ \begin{align*}\#{\mathcal W}_{m,n}(\mathbb{Z},H)=o(H^{mn^2}).\end{align*} $$

It would be very interesting to reduce the gap between these two bounds. We believe that the upper bound remains true for $2\leq m \leq 5$ .

2.2 Matrices over an arbitrary field

In the spirit of the problems for ${\mathcal M}(\mathbb {Z};H)$ in the preceding section, we first consider the set

$$ \begin{align*} \{ AB \colon A \in S_1,\: B\in S_2 \}, \end{align*} $$

where $S_1,\:S_2$ are subsets of ${\mathcal M}_n(\mathbb {F})$ with some prescribed properties. In this section, we take $S_1$ and $S_2$ as the set of matrices in ${\mathcal M}_n(\mathbb {F})$ with some bounded rank $k\leq n$ .

More precisely, let ${\mathcal M}_n(\mathbb {F};k)$ denote the set of matrices in ${\mathcal M}_n(\mathbb {F})$ with rank at most k. We see that ${\mathcal M}_n(\mathbb {F};n)={\mathcal M}_n(\mathbb {F})$ and ${\mathcal M}_n(\mathbb {F};n-1)={\mathcal M}_n^{0}(\mathbb {F})$ , the set of all singular matrices in ${\mathcal M}_n(\mathbb {F})$ . Denote

$$ \begin{align*} S_{n}(\mathbb{F};k_1,k_2)=\{ AB \colon A\in {\mathcal M}_n(\mathbb{F};k_1),B\in {\mathcal M}_n(\mathbb{F};k_2) \}. \end{align*} $$

Theorem 2.4. Let n be a positive integer. For any nonnegative integers $k_1$ and $k_2$ with $k_1,k_2\leq n$ ,

$$ \begin{align*} S_{n}(\mathbb{F};k_1,k_2)= {\mathcal M}_n(\mathbb{F};\min{(k_1,k_2)}).\end{align*} $$

In particular, by setting $k_1=k_2=n-1$ in Theorem 2.4, we see that any singular matrix in ${\mathcal M}_n(\mathbb {F})$ can be represented as a product of two singular matrices. By inducting on m, Theorem 2.4 can be generalised as follows.

Corollary 2.5. For any nonnegative integers $m,\:n\geq 2$ and $ k_1, \ldots , k_m \leq n$ ,

$$ \begin{align*} \{ A_1 \cdots A_m \colon A_i\in {\mathcal M}_n(\mathbb{F};k_i) \}= {\mathcal M}_n(\mathbb{F};\min{(k_1, \ldots,k_m)}). \end{align*} $$

If $\mathbb {F}$ is a finite field, then the formula for $\#{\mathcal M}_n(\mathbb {F};k)$ is known (see Fisher [Reference Fisher7]).

3 Preliminary results

We first need an equivalent to counting ${\mathcal W}_{m,n}(\mathbb {Z};H)$ for $n=1$ , by counting the cardinality of the set

$$ \begin{align*} {\mathcal A}_m(H)= \{a_1 \cdots a_n \colon a_1, \ldots, a_m \in \mathbb{Z}, |a_i|\leq H\text{ for }i=1,\ldots,m\}. \end{align*} $$

Koukoulopoulos [Reference Koukoulopoulos14, Corollary 1] gave the following result on the product sets of positive integers not less than H.

Lemma 3.1. For $m\geq 2$ , let $\rho =(m+1)^{1/m}$ and

$$ \begin{align*}Q(u):=\int_1^u\log t\,dt=u\log u-u+1\quad(u>0).\end{align*} $$

Then,

$$ \begin{align*} \# {\mathcal A}_{m}(H)\sim \frac{H^m}{(\log H)^{Q(1/{\log\rho})}(\log\log H)^{{3}/{2}}}. \end{align*} $$

Some of our arguments on bounding ${\mathcal M}_n(\mathbb {Z};H)$ are based on the properties of integral matrices with bounded norm. We quote the following results from Shparlinski [Reference Shparlinski18] and Katznelson [Reference Katznelson12].

Lemma 3.2. Fix an integer d. Uniformly, there are $O(H^{n^2-n}\log H)$ matrices in ${\mathcal M}_n(\mathbb {Z};H)$ of determinant d. Also, when $d=0$ , there are asymptotically $H^{n^2-n}\log H$ matrices in ${\mathcal M}_n(\mathbb {Z};H)$ of determinant $0$ .

Duke et al. [Reference Duke, Rudnick and Sarnak3, Example 1.6] gave an asymptotic formula for the quantities in Lemma 3.2 when $d\neq 0$ is fixed. However, this bound cannot be used in our arguments because d is not fixed.

We also use the following property of integral matrices from Katznelson [Reference Katznelson13, Theorem 1(2)].

Lemma 3.3. Let k be an integer with $1\leq k < n$ . Then, there are $H^{nk+o(1)}$ matrices in ${\mathcal M}_n(\mathbb {Z};H)$ of rank k.

We also use a well-known result concerning the number of divisors $\tau (k)$ of a positive integer k (see for example [Reference Iwaniec and Kowalski11, Equation (1.81)]).

Lemma 3.4. We have $\tau (k)=k^{o(1)}$ as $k\to \infty $ .

Finally, to prove Theorem 2.4, we need the following new result on decomposition of a matrix with a fixed rank k which we prove in Section 8.

Theorem 3.5. Let $A\in {\mathcal M}_n(\mathbb {F})$ with $\operatorname {rank} A=k$ . Then, there exists $B\in {\mathcal M}_n(\mathbb {F})$ with $\operatorname {rank} B = k$ such that $BA=A$ .

4 Proof of Theorem 2.1

4.1 The case of nonsingular C

We first notice that in the equation $A_1 \cdots A_m=C$ , where C is nonsingular, all of $ A_1, \ldots , A_{m} $ are also nonsingular. This implies that each choice of $ A_1, \ldots , A_{m-1} $ gives at most a unique matrix $A_m$ . Therefore, we now only count $A_i$ for $i=1,\ldots , m-1$ .

We know that $\det A_i\mid \det C$ . Therefore, from Lemma 3.4, there are

$$ \begin{align*}\lvert \det C \rvert ^{o(1)}\leq H^{o(1)}\end{align*} $$

possible values d of $\det A_i$ . From Lemma 3.2, there are at most $H^{n^2-n+o(1)}$ matrices in ${\mathcal M}_n(\mathbb {Z};H)$ with determinant d. Therefore, there are at most $H^{n^2-n+o(1)}$ possible matrices $A_i$ , for $i=1,\ldots , m-1$ , which satisfy the equation. Multiplying these bounds proves the initial statement of the theorem.

4.2 The case of singular nonzero C

We first prove the bound for general m. We know that in the equation

$$ \begin{align*}A_1\cdots A_m=C, \end{align*} $$

at least one of $A_1, \ldots , A_m$ (suppose $A_1$ ) is singular. By Lemma 3.2, there are at most $H^{n(n-1)+o(1)}$ possible choices of $A_1$ . Since there are $H^n$ choices for other matrices, we can multiply the bounds to complete the proof.

We now consider the case $m=2$ . We bound $\#{\mathcal W}_{2,n}(H,C)$ , where C is a fixed nonzero singular matrix of size $n\times n$ , with $n\geq 2$ . Consider the equation $AB=C$ . Without loss of generality, let A be singular and $\operatorname {rank} A=k\geq 1$ . We write A, B and C in the form:

where $X_1$ , $X_2$ and X are $k\times k$ matrices, $Y_1$ , $Y_2$ and Y are $(n-k)\times (n-k)$ matrices, $V_1$ , $V_2$ and V are $k\times (n-k)$ matrices, and $W_1$ , $W_2$ and W are $(n-k)\times k$ matrices. Since $\operatorname {rank} A=k$ , we know that A has at least a nonsingular $k\times k$ submatrix. Without loss of generality, we may assume that $X_1$ is nonsingular. We then consider the matrix equation:

In particular, looking at the first row of the above equations, we obtain the system of equations

$$ \begin{align*} X_2&=X_1^{-1}(X-V_1W_2),\\ V_2&=X_1^{-1}(V-V_1Y_2). \end{align*} $$

The first equation implies that fixed A, C and $W_2$ give a unique $X_2$ . The second equation implies that fixed A, C and $Y_2$ give a unique $V_2$ . Therefore, for a fixed A, $W_2$ and $Y_2$ , we get at most one possible matrix B that satisfies the equation $AB=C$ . By Lemma 3.3, there are $H^{nk+o(1)}$ matrices $A\in {\mathcal M}_n(\mathbb {Z};H)$ such that $\operatorname {rank} A=k$ . However, there are $O(H^{(n-k)k})$ possible choices of $W_2$ and $O(H^{(n-k)^2})$ possible choices of $Y_2$ . These observations imply that for a fixed C, there are at most

$$ \begin{align*}H^{nk+o(1)} \cdot H^{(n-k)k} \cdot H^{(n-k)^2} = H^{n^2+o(1)}\end{align*} $$

different pairs $(A,B)$ such that $AB=C$ and $\operatorname {rank} A=k$ . Summing over all possible k completes the proof.

4.3 The case of $C=O_n$

The lower bound can be attained by considering that any tuple of matrices $(A_1,\ldots ,A_m)$ with $A_1=O_n$ , where $O_n$ is the zero $n\times n$ matrix, satisfies the equation

$$ \begin{align*} A_1\cdots A_m=O_n. \end{align*} $$

This implies that there are at least $H^{(m-1)n^2}$ different possible tuples of matrices that satisfy this equation.

Now, we prove the upper bound. Suppose that $(A_1,\ldots ,A_m)$ satisfy the equation. From Sylvester’s rank inequality and induction,

$$ \begin{align*} \operatorname{rank} A_1 \cdots A_m\geq \sum_{i=1}^{n} \operatorname{rank} A_i - (m-1)n. \end{align*} $$

In our case, since $\operatorname {rank} O_n=0$ , this inequality implies

$$ \begin{align*} (m-1)n\geq \sum_{i=1}^{m} \operatorname{rank} A_i. \end{align*} $$

Now, we let $\operatorname {rank} A_i=k_i$ for $i=1,\ldots , m$ . From Lemma 3.3, there are $H^{nk+o(1)} $ matrices in ${\mathcal M}_n(\mathbb {Z};H)$ of rank k. Therefore, from the inequality above,

$$ \begin{align*} \#{\mathcal T}_m({\mathcal M}_{n}(\mathbb{Z};H),O_{n}) &\leq \sum_{\substack{0\leq k_1, \ldots,k_m \leq n\\ k_1+ \cdots+k_m\leq (m-1)n}} H^{nk_1+o(1)} \cdots H^{nk_m+o(1)}\\ &\leq \sum_{k_1+ \cdots+k_m\leq (m-1)n} H^{n(k_1+\cdots+k_m)+o(1)} \\ &\leq \sum_{k_1+ \cdots+k_m\leq (m-1)n} H^{n(m-1)n+o(1)} \\ &= H^{(m-1)n^2+o(1)}. \end{align*} $$

This completes the proof of the upper bound.

5 Proof of Corollary 2.2

5.1 The nonsingular case

Consider the equation

(5.1) $$ \begin{align} A_1 \cdots A_m=B_1 \cdots B_m, \end{align} $$

where $A_i, B_i \in {\mathcal M}_n^*(\mathbb {Z};H)$ for $i=1,\ldots ,m$ . For each choice of $( B_1, \ldots , B_m )$ , we see that, by Theorem 2.1, there are at most $O(H^{(m-1)(n^2-n)})$ possible m-tuples of matrices $(A_1,\ldots ,A_m)$ that satisfy (5.1). However, there are at most $O(H^{n^2})$ possible matrices $B_i$ for $i=1,\ldots ,m$ . Multiplying these bounds proves the statement.

5.2 The general case

We first give an upper bound for the case $m\geq 3$ . In contrast to the previous case, we now allow the matrices to be singular. We first consider the case where all matrices in the equation

$$ \begin{align*} A_1\cdots A_m=B_1\cdots B_m \end{align*} $$

are nonsingular. Recalling the result in the previous section, there are at most $H^{(2m-1)n^2-(m-1)n+o(1)}$ solutions in this case.

Next, we consider the case where at least one of the matrices is singular. Without loss of generality, suppose $A_1$ is singular. This implies that at least one of $B_1,\ldots ,B_m$ (without loss of generality, $B_1$ ) is also singular. Then, from Lemma 3.3, there are at most $H^{n(n-1)+o(1)}$ choices for $A_1$ and $B_1$ . Since there are $H^n$ possible choices for the other matrices, there are $H^{2mn^2-2n+o(1)}$ possible solutions in this case. Combining both cases, we see that

$$ \begin{align*} \#{\mathcal T}_n({\mathcal M}_n(\mathbb{Z};H))\ll \max\{H^{2mn^2-2n+o(1)}, H^{(2m-1)n^2-(m-1)n+o(1)}\} =H^{2mn^2-2n+o(1)}.\end{align*} $$

We now proceed to improve this bound for $m=2$ . Using the argument for general m, we see that there are at most $H^{3n^2-n+o(1)}$ solutions to the equation $AB=CD$ where all of them are nonsingular. Next, we count the solutions of $AB=CD$ , where at least one of A, B, C and D is singular. Without loss of generality, we fix $CD$ , where C is singular. By Lemma 3.2, this can be achieved in $H^{2n^2-n+o(1)}$ ways. By Theorem 2.1, we see that in this case, there are at most $H^{n^2+o(1)}$ possible pairs of matrices $(A,B)$ such that $AB=CD$ . Multiplying these bounds, we find that there exist at most $H^{3n^2-n+o(1)}$ solutions of the equation $ AB=CD$ , where at least one of A, B, C and D is singular. Combining both cases, we see that

$$ \begin{align*} \#{\mathcal T}_2({\mathcal M}_n(\mathbb{Z};H))\ll H^{3n^2-n+o(1)}, \end{align*} $$

which completes the proof.

6 Proof of Theorem 2.3

6.1 Upper bound

We will prove a stronger bound than the one stated in Theorem 2.3, namely

(6.1) $$ \begin{align} \#{\mathcal W}_{m,n}(\mathbb{Z};H) = O\bigg(\frac{H^{mn^2}}{(\log H)^{Q(1/{\log\rho})-1}(\log\log H)^{{3}/{2}}}\bigg), \end{align} $$

where $\rho =m^{1/(m-1)}$ and $Q(u):=u\log u-u+1.$

We first notice that the absolute values of the entries in ${\mathcal W}_{m,n}(\mathbb {Z};H)$ are bounded above by $n^{m-1}H^m$ . Hence, ${\mathcal W}_{m,n}(\mathbb {Z};H)\subseteq {\mathcal M}_{m,n}(\mathbb {Z};n^{m-1}H^m)$ .

Now, let ${\mathcal D}$ be the set of all possible values of $\det A_1\cdots \det A_m$ . We recall that $|\det A|\leq n^{m-1}H^m$ for any $A \in {\mathcal M}_n(\mathbb {Z};H)$ . Therefore, by Lemma 3.1,

$$ \begin{align*} \#{\mathcal D} &= O\bigg(\frac{(H^n)^m}{(\log H^n)^{Q(1/{\log\rho})}(\log\log H^n)^{{3}/{2}}}\bigg)\\ & = O\bigg(\frac{H^{mn}}{(\log H)^{Q(1/{\log\rho})}(\log\log H)^{{3}/{2}}}\bigg). \end{align*} $$

From Lemma 3.2, there are $O(H^{m(n^2-n)}\log H)$ matrices in ${\mathcal M}_{m,n}(\mathbb {Z};n^{m-1}H^m)$ with determinant d, for each $d\in {\mathcal D}$ . Therefore,

$$ \begin{align*} {\mathcal W}_{m,n}(\mathbb{Z};H)\leq \#{\mathcal D} \cdot O(H^{n^2-n}\log H) \leq O\bigg(\frac{H^{mn^2}}{(\log H)^{Q(1/{\log\rho})-1}(\log\log H)^{{3}/{2}}}\bigg), \end{align*} $$

which completes the proof of (6.1).

It remains to prove that (6.1) implies $\#{\mathcal W}_{m,n}(\mathbb {Z};H)=o(H^{mn^2})$ for $m\geq 6$ . To prove this, we notice that the function $f(m)=Q({1}/{\log (m^{1/(m-1)})})$ is increasing in m and $f(6)\geq 1$ . Therefore, in this case, the denominator of the right-hand side of (6.1) implies

$$ \begin{align*}\#{\mathcal W}_{m,n}(\mathbb{Z};H)=o(H^{mn^2})\end{align*} $$

for $m\geq 6$ , proving the desired upper bound.

Finally, note that (6.1) remains true for $2\leq m \leq 5$ . However, since $f(5)$ is smaller than $1$ , that alone does not imply $\#{\mathcal W}_{m,n}(\mathbb {Z};H)=o(H^{mn^2})$ in this case.

6.2 Lower bound

We consider the lower bound of $\#{\mathcal W}_{m,n}^*(\mathbb {Z};H)$ . From Theorem 2.1, there are at most $H^{(m-1)(n^2-n)+o(1)}$ different possible solutions to the equation $A_1 \cdots A_m=C$ , where $A_i \in {\mathcal M}_n(\mathbb {Z};H)$ (for $1\leq i \leq m$ ) and C is a fixed nonsingular matrix.

We also see that there are asymptotically $H^{n^2}$ nonsingular matrices in ${\mathcal M}_n(\mathbb {Z};H)$ . Therefore, if we count the number of $(m+1)$ -tuples $(A_1,\ldots ,A_m,C)$ that satisfy $A_1 \cdots A_m=C$ and $C\in {\mathcal W}^*_{m,n}(\mathbb {Z};H)$ ,

$$ \begin{align*} (\#{\mathcal W}^*_{m,n}(\mathbb{Z};H))H^{(m-1)(n^2-n)+o(1)} \geq H^{mn^2+o(1)} \iff \#{\mathcal W}^*_{m,n}(\mathbb{Z};H) \geq H^{n^2+mn-n+o(1)}. \end{align*} $$

Since ${\mathcal W}^*_{m,n}(\mathbb {Z};H)\subseteq {\mathcal W}_{m,n}(\mathbb {Z};H)$ , the lower bound is proven.

7 Proof of Theorem 2.4

Let $n\geq 2$ be a positive integer and $k_1,k_2$ nonnegative integers with $0\leq k_1,k_2\leq n$ . Without loss of generality, suppose $k_1 \leq k_2$ . Since

$$ \begin{align*} \operatorname{rank} AB\leq \min{(\operatorname{rank} A, \operatorname{rank} B)} \end{align*} $$

for any matrices A and B, we see that the rank of a matrix in $S_n(\mathbb {F};k_1,k_2)$ is at most $k_1$ . This implies that $S_n(\mathbb {F};k_1,k_2)\subseteq {\mathcal M}_n(\mathbb {F};k_1)$ .

Now we prove that any matrix C in ${\mathcal M}_n(\mathbb {F};k_1)$ can be represented as a product of two matrices $XY$ , where $\operatorname {rank} X \leq k_1$ and $\operatorname {rank} Y \leq k_2$ . By Theorem 3.5, there exists a matrix B with $\operatorname {rank} B= k_1\leq k_2$ that satisfies $BC=C$ . This implies that ${\mathcal M}_n(\mathbb {F};k_1)\subseteq S_n(\mathbb {F};k_1,k_2)$ , which concludes the proof.

8 Proof of Theorem 3.5

If $k=n$ , we pick $B=I$ . If $k=0$ , we pick $B=O_n$ . Suppose that $1\leq k<n$ . Since $\operatorname {rank} A=k$ , the nullity $\text {null}(A)=n-k$ . This implies that there exist $n-k$ linearly independent vectors $\mathbf {v}_1, \ldots ,\mathbf {v}_{n-k} \in \mathbb {F}^n$ such that $\textbf {v}_i^\intercal A=\textbf {0}$ for all $i=1,\ldots , n-k$ .

Consider an $ (n-k)\times n$ matrix $C'$ with

$$ \begin{align*} C'=[\textbf{v}_1 \mid \cdots \mid \textbf{v}_{n-k}]^\intercal. \end{align*} $$

Let its reduced row echelon form be

$$ \begin{align*} C=[\textbf{w}_1 \mid \cdots \mid \textbf{w}_{n-k}]^\intercal. \end{align*} $$

First, we see that the vectors $\{\textbf {w}_1, \ldots , \textbf {w}_{n-k}\}$ are linearly independent. Also, $\textbf {w}_i^\intercal A=\textbf {0}$ for $i=1,\ldots , n-k$ . However, we observe the following properties of C from the definition of the reduced row echelon form:

  1. (1) the leading nonzero component of $\textbf {w}_i$ is 1; suppose that the leading 1 of $\textbf {w}_i$ in C is in column $z_i$ ;

  2. (2) if a column of C has a leading 1, its other components are zero;

  3. (3) $z_1<\cdots <z_{n-k}$ .

Now define $\mathbf {b}_{z_i}=-\mathbf {w}_i$ for $i=1,\ldots ,n-k$ , with $z_i$ defined as above. Also, let $\mathbf {b}_j=\textbf {0}$ for the remaining indices j so that $\textbf {b}_j$ is defined for all $j=1,\ldots ,n$ . Let

$$ \begin{align*}B'=[\mathbf{b}_1 \mid \cdots \mid \mathbf{b}_n]^\intercal.\end{align*} $$

Then $B^{\prime }_{z_iz_i}=-1$ for $i=1,\ldots ,n-k$ . Also, $B^{\prime }_{jz_i}=0$ if $j\neq z_i$ . Furthermore, since $\textbf {b}_{i}^\intercal A=\textbf {0}$ for $i=1,\ldots ,n$ , we have $B'A=O_n$ . Therefore, letting $B=B'+I$ ,

$$ \begin{align*} BA = (B' + I) A = A.\end{align*} $$

This implies that B satisfies the first part of our theorem.

Now we calculate the rank of B. By the definition of the vectors $\mathbf {b}_i$ , we see that the $z_i$ th column of B is $\textbf {0}$ for $i=1,\ldots ,n-k$ . Thus, B has at least $n-k$ zero columns and $\operatorname {rank} B\leq k$ . However, if $j\neq z_i$ for any i, the jth row of B consists only of a $1$ in its jth component and zeros in the other components. Therefore, these k rows are linearly independent which implies $\operatorname {rank} B \geq k$ . Therefore, $\operatorname {rank} B=k$ , which concludes the proof.

Acknowledgements

The author would like to thank Alina Ostafe and Igor Shparlinski for many ideas, comments and corrections during the preparation of this work. The author would also like to thank the anonymous reviewers for their suggestions.

Footnotes

The author is supported by an UNSW Tuition Fee Scholarship and Australian Research Council Grant DP200100355.

References

Ahmadi, O. and Shparlinski, I. E., ‘Distribution of matrices with restricted entries over finite fields’, Indag. Math. (N.S.) 18 (2007), 327337.10.1016/S0019-3577(07)00013-4CrossRefGoogle Scholar
Demiroğlu-Karabulut, Y., Koh, D., Pham, T., Shen, C.-Y. and Vinh Le, A., ‘Expanding phenomena over matrix rings’, Forum Math. 31 (2019), 951970.10.1515/forum-2019-0032CrossRefGoogle Scholar
Duke, W., Rudnick, Z. and Sarnak, P., ‘Density of integer points on affine homogeneous varieties’, Duke Math. J. 71 (1993), 143–79.10.1215/S0012-7094-93-07107-4CrossRefGoogle Scholar
El-Baz, D., Lee, M. and Strömbergsson, A., ‘Effective equidistribution of primitive rational points on expanding horospheres’, Preprint, 2023, arXiv:2212.07408.10.4171/JEMS/1238CrossRefGoogle Scholar
Erdős, P.. ‘An asymptotic inequality in the theory of numbers’, Vestnik Leningrad. Univ. 15 (1960), 4149.Google Scholar
Ferguson, R., Hoffman, C., Luca, F., Ostafe, A. and Shparlinski, I. E., ‘Some additive combinatorics problems in matrix rings’, Rev. Mat. Complut. 23 (2010), 501513.10.1007/s13163-010-0029-4CrossRefGoogle Scholar
Fisher, S. D., ‘Classroom notes: matrices over a finite field’, Amer. Math. Monthly 73 (1966), 639641.10.2307/2314805CrossRefGoogle Scholar
Ford, K., ‘The distribution of integers with a divisor in a given interval’, Ann. of Math. (2) 168 (2008), 367433.10.4007/annals.2008.168.367CrossRefGoogle Scholar
Helfgott, H. A., ‘Growth and generation in $\mathrm{SL}_2(\mathbb{Z}/ p\mathbb{Z})$ ’, Ann. of Math. (2) 167 (2008), 601623.10.4007/annals.2008.167.601CrossRefGoogle Scholar
Helfgott, H. A., ‘Growth in $\mathrm{SL}_3(\mathbb{Z}/ p\mathbb{Z})$ ’, J. Eur. Math. Soc. (JEMS) 13 (2011), 761851.10.4171/JEMS/267CrossRefGoogle Scholar
Iwaniec, H. and Kowalski, E., Analytic Number Theory (American Mathematical Society, Providence, RI, 2004).Google Scholar
Katznelson, Y. R., ‘Singular matrices and a uniform bound for congruence groups of ${\mathrm{SL}}_n(\mathbb{Z})$ ’, Duke Math. J. 69 (1993), 121136.10.1215/S0012-7094-93-06906-2CrossRefGoogle Scholar
Katznelson, Y. R., ‘Integral matrices of fixed rank’, Proc. Amer. Math. Soc. 120 (1994), 667675.10.1090/S0002-9939-1994-1169034-3CrossRefGoogle Scholar
Koukoulopoulos, D., ‘Localized factorizations of integers’, Proc. Lond. Math. Soc. (3) 101 (2010), 392426.10.1112/plms/pdp056CrossRefGoogle Scholar
Mohammadi, A., Pham, T. and Wang, Y., ‘An energy decomposition theorem for matrices and related questions’, Canad. Math. Bull., to appear. Published online (15 May 2023).10.4153/S000843952300036XCrossRefGoogle Scholar
Nguyen, T. and Vinh, L. A., ‘A point-plane incidence theorem in matrix rings’, Discrete Appl. Math. 322 (2022), 166170.10.1016/j.dam.2022.08.012CrossRefGoogle Scholar
Ostafe, A. and Shparlinski, I. E., ‘Integer matrices with a given characteristic polynomial and multiplicative dependence of matrices’, Preprint, 2023, arXiv:2203.03880.Google Scholar
Shparlinski, I. E., ‘Some counting questions for matrices with restricted entries’, Linear Algebra Appl. 432 (2010), 155160.10.1016/j.laa.2009.07.036CrossRefGoogle Scholar
Van The, N. and Vinh, L. A., ‘Expanding phenomena over higher dimensional matrix rings’, J. Number Theory 216 (2020), 174–91.Google Scholar
Xie, C. and Ge, G., ‘Some sum-product estimates in matrix rings over finite fields’, Finite Fields Appl. 79 (2022), 101997.10.1016/j.ffa.2022.101997CrossRefGoogle Scholar