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\dots 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. Related to this result, we also give some bounds on the cardinalities of the set of solutions of the related equations such as $A_1\dots A_m=C$ and $A_1\dots A_m=B_1\dots 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\le n$. In this case, we completely classify the related product set.

12 pages