Image of a linear transformation with a matrix in $\mathbb Z_m$

Question

Let us say we have a $s \times t$ matrix $A$ over $\mathbb Z_m$, the ring of integers modulo $m$.

I am interested in the image of a function $f: \mathbb Z_m^t \to \mathbb Z_m^s$, defined as $$ f(\mathbf x) = A \mathbf x, $$ for all $\mathbf x \in \mathbb Z_m^t$.

If $m$ is prime then $\mathbb Z_m = \mathbb F_m$ is a finite field and the size of the image is obviously $m^{\mathrm{rank} A}$. The image is just a vector subspace of $\mathbb F_m^s$.

If $A$ consist of one row only (i.e. $f(\mathbf x) = a_1 x_1 + \dotsb + a_t x_t$) then the image is $$ \{ 0, d, 2d, \dotsc, \left( \frac md - 1 \right)d \}, $$ where $d = \gcd(a_1, \dotsc, a_t, m-1)$.

But what is the answer in general case?

Answer 1

Over integers, any matrix $A \in \mathbb Z^{s \times t}$ has the Smith normal form: $$ D = P A Q, $$ where $\det P, \det Q = \pm 1$ (and hence invertible over $\mathbb Z$), and $D = diag(\alpha_1, \alpha_2, \dotsc, \alpha_{\min(s,t)})$. The elements $\alpha_1, \alpha_2, \dotsc, \alpha_{\min(s,t)}$ are invariant factors and have the following properties:

• $\alpha_i$ divides $\alpha_{i+1}$
• the product $\alpha_1 \alpha_2 \dotsb \alpha_{i}$ is equal to gcd of all $i \times i$ minors of $A$. For convenience, we can set $\alpha_i = 0$ for $i > \min(s,t)$.

We can now take both parts of $D = P A Q$ modulus $m$. Determinants of $P$ and $Q$ stays $\pm 1$ and therefore, the matrices stay invertible. Altogether, we can write (this time, already over $\mathbb Z_m$): $$ A \mathbf x = P^{-1} D Q^{-1} \mathbf x $$ Since $Q^{-1}$ is invertible over $\mathbb Z_m$, it defines a permutation of $\mathbb Z_m^t$. Analogously, $P^{-1}$ defines a permutation of $\mathbb Z_m^s$.

Therefore, the image of $f(\mathbf x) = A \mathbf x$ can be mapped bijectively to $(\alpha_1 x_1, \alpha_2 x_2, \dotsc, \alpha_t x_t)$ when $x_1, \dotsc, x_t$ run through $\mathbf Z_m$. Note that here $\alpha_1, \dotsc, \alpha_t$ are modulus-$m$ of the original integer values. Also, because of taking modulus $m$, some $\alpha_i$ can become zeroes for $i \ge i_0$ for some $i_0$.

Now, the entries $\alpha_i x_i$ behave independently of each other and each of them has image $$ \{ 0, d_i, 2d_i, \dotsc, \left( \frac m{d_i} - 1 \right)d_i \}, $$ where $d_i = gcd(\alpha_i, m)$.