SOME COUNTING QUESTIONS FOR MATRIX PRODUCTS

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.

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, [6] studies the distribution of singular and unimodular matrices over subsets of a matrix ring, [2, 9, 10, 19] study expansion phenomena over matrix rings and [15, 16, 20] 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 [1] 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. [4] 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 [17], 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 [5]. Ford [8] gave an asymptotic formula for this quantity when $m=2$ and Koukoulopoulos [14] 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 [7]).

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 [14, 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 [18] and Katznelson [12].

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. [3, 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 [13, 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 [11, 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.