1
$\begingroup$

I have a system of homogeneous linear equations over $\mathbb{Z}_6$. The coefficients of the variables are all 1 (maybe this helps). The number of equations is very small compared to the number of variables (more precisely, I can keep the number of equations constant while the number of variables can be as high as I wish).

I want to say that there are "a lot" of solutions to this equation system, and over a field it would have been easy; the rank of the corresponding matrix would have been small compared to the number of variables, and so the dimension of the solution space would have been high.

However, over $\mathbb{Z}_6$ all the "traditional" linear algebra I know ceases to work. So, can I still use similar claims? If so, how? Is there a book dealing with linear algebra over rings (maybe not general rings; $\mathbb{Z_n}$ is all I need).

  • 0
    Indeed. Chinese Remainder Theorem.2018-11-08

2 Answers 2

2

In general, if we can write $n=ab$ with $a,b$ relatively prime, then then there is a ring isomorphism $\mathbb Z_n = \mathbb Z_a \times \mathbb Z_b$. That means that if $\{q_i(x_1,...,x_k)\}$ is a set of polynomial with integer variables, then the number of solutions to $q_i(x_1,...,x_k)=0$ in $\mathbb Z_n$ is equal to the number of solutions in $\mathbb Z_a$ times the number of solutions in $\mathbb Z_b$.

If $n$ is square-free, then, we just take the product of the number of solutions to $\{q_i\}$ in $\mathbb Z_p$, where $p$ runs over all prime factors of $n$.

But if $n$ is not square-free, then you can only reduce the problem to finding solutions in $\mathbb Z_{p^k}$.

Now, given that your equations are linear, you might be able to do additional tinkering.

0

There is the book: Linear algebra over commutative rings by Bernard R. McDonald, but it is not that computational. If your matrices are small and dense, then you can use fraction-free Gaussian elimination methods such as this one. In general, these methods are based on Bareiss algorithm.