Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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).

share|improve this question
2  
A solution $\pmod 6$ yields a solution $\pmod 3$ and a solution $\pmod 2$. Can you work backwards from a pair of solutions $\pmod 2$ and $\pmod 3$ to get a solution $\pmod 6$? –  Thomas Andrews Jan 9 '12 at 14:22
add comment

2 Answers 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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.