Count of solutions to matrix equations

Question

Given these modular equations:

$$a_{1,1} x_1 + a_{1,2} x_2 + \cdots + a_{1,n} x_n = b_1 \bmod p $$ $$a_{2,1} x_1 + a_{2,2} x_2 + \cdots + a_{2,n} x_n = b_2 \bmod p $$ $$\vdots$$ $$a_{m,1} x_1 + a_{m,2} x_2 + \cdots + a_{m,n} x_n = b_m \bmod p $$

Imagine that all $a_{ij}$ and $b_k$ are given, along with $p$, a prime number.

Also assume that all $a$, $x$, and $b$ are less than $p$.

The only variables we don't know are the $x$ variables. How many solutions are there to this and why?

Answer 1

Since $\mathbf Z/p\mathbf Z$ is a field, the discussion is the same as in any field. Let $r$ be the rank of the left-hand side. Then $r\le \min(m,n)$ and:

• If the bordered matrix has rank $r$, the solutions are in bijection with $(\mathbf Z/p\mathbf Z)^{n-r}$, so there are $p^{n-r}$ of them.
• If the bordered matrix has rank $>r$, the compatibility conditions are not all satisfied, hence there is no solution.

The answer would be the same for any finite field with $q$ element ($q=p^t$ for some prime $p$).