3
$\begingroup$

I have implemented Gaussian elimination for solving system of linear equations in the field of modulo prime remainders. If there is a pivot equal to zero I assume the system has no solution but how to calculate number of solutions of such systems when all pivots are non-zero? (i.e. one and more solutions)

$\endgroup$
2
$\begingroup$

The integers modulo a prime form a field, so all assumptions done applying Gaussian eliminations work exactly the same. Luckily, there are no numerical instability problems. The system can be inconsistent (no solutions), underdetermined (several solutions modulo $p$) or have a unique solution modulo $p$.

$\endgroup$
  • 2
    $\begingroup$ I see. Can you please be more specific about finding the number of solutions in case it is underdetermined? $\endgroup$ – A123321 Mar 17 '13 at 0:31
  • 3
    $\begingroup$ Just as the typical real case, it means that you can express the values of the variables in terms of a subset of them. If this subset has $k$ variables (the rank of the matrix), there will be $p^k$ solutions. $\endgroup$ – vonbrand Mar 17 '13 at 0:35
  • $\begingroup$ I can't come up with a system where it wouldn't work now but I think that there might be such a system: if you choose a free variable (one of $p$ options) in such way it wouldn't match the rest of system. $\endgroup$ – A123321 Mar 20 '13 at 21:32
  • $\begingroup$ According to user anon (math.stackexchange.com/users/11763/anon) from Mathematics chat the proper solution is $p^{dim_{F_{p}} ker A}$. Unfortunately I don't know how to implement that into my code. $\endgroup$ – A123321 Mar 20 '13 at 23:07
  • 1
    $\begingroup$ @Andrew123321, just get how many of the vectors are linearly independent (by reducing the matrix), that is what they call $\operatorname{dim}_{\mathbb{F}_p} \operatorname{ḱer} A$. $\endgroup$ – vonbrand Mar 20 '13 at 23:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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