What is the probability that $Ax = y$ for a random matrix $A$? Let $m, q,$ and $n$ be integers and $m$ be much greater than $n$. Let $q$ also be a prime number.
Consider an $m \times n$ matrix $A$. Each entry of $A$ is chosen uniformly at random from $\mathbb{Z}_q$.
For two particular vectors $x \in \mathbb{Z}_{q}^{n \times 1}$  and $y \in \mathbb{Z}_{q}^{m \times 1},$ I am trying to compute
$$\underset{A}{\text{Pr}}~[Ax = y]. $$
All the operations (addition and multiplication) are modulo $q$.

Here's my qualitative intuition.
Since $A$ should be full rank with high probability, I believe that the image of $A$ should be uniformly distributed and that the probability in question should be $\frac{1}{q^{m}}$.
 A: If $x$ is the zero vector then of course the probability will be either $0$ or $1$ (depending on $y$), because $Ax$ will always be $0$ as well. Otherwise, suppose without loss of generality that $x_n \ne 0$.
We can write $Ax$ as $A_1 x_1 + A_2 x_2 + \dots + A_n x_n$, where $A_i \in \mathbb Z_q^m$ is the $i^{\text{th}}$ column of $A$. Let's pick $A$ randomly in two stages: first pick $A_1$ through $A_{n-1}$, and second pick $A_n$.
Regardless of what happens in the first stage, we will have $A x = y$ if and only if
$$
    A_n = \frac1{x_n}\left(y - A_1 x_1 - A_2 x_2 - \dots - A_{n-1} x_{n-1}\right).
$$
(Here, $\frac1{x_n}$ is the inverse of $x_n$ modulo $q$.)
This happens with probability $\frac1{q^m}$, because there is only one possible value in $\mathbb Z_q^m$ that $A_n$ can have.
Note that it is not necessary to assume anything about the relative sizes of $m$ and $n$. No matter what they are, if $A$ is chosen uniformly at random and $x$ is not the zero vector, then $Ax$ is uniformly distributed.
