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)
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
5
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$.
-
2$\begingroup$ I see. Can you please be more specific about finding the number of solutions in case it is underdetermined? $\endgroup$– A123321Commented Mar 17, 2013 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$– vonbrandCommented Mar 17, 2013 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$– A123321Commented Mar 20, 2013 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$– A123321Commented Mar 20, 2013 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$– vonbrandCommented Mar 20, 2013 at 23:23
$\begingroup$
$\endgroup$
1
It's 2 raised to the power of size of null-space. The reason is that once you have a solution, adding any linear combination of vectors in null-space gives you a valid solution.
This problem comes out when counting number of solutions to "lights out" puzzle, example of solving it in Mathematica using NullSpace operation:
graph = GridGraph[{4, 4}]
n = Length@VertexList@graph;
target = Table[1, {n}];
mat = AdjacencyMatrix[graph] + IdentityMatrix[n];
result = LinearSolve[mat, target, Modulus -> 2];
Print["sample solution: ", result]
Print["number of solutions: ", 2^Length@NullSpace[mat, Modulus -> 2]]
-
1$\begingroup$ This is true of the system is homogeneous (all constant terms are zero). $\endgroup$ Commented Dec 21, 2019 at 22:59