2
$\begingroup$

I have a system of linear equations I want to solve mod 4, and I happen to know the solution, but I get an error when trying to solve it using LinearSolve. I define the matrix M on line 31, define my known solution, b on line 32, and verify it on line 33. But trying to solve it using LinearSolve I get the error Matrix is not valid modulo 4. Here's the print of my inputs and outputs:

Here's a print of the inputs and the error I get.

Edit:

Here's the matrix in question

M := {{1, 1, 1, 1, 0, 0, 1, 0, 0},
{1, 1, 1, 0, 1, 0, 0, 1, 0},
{1, 1, 1, 0, 0, 1, 0, 0, 1},
{1, 0, 0, 1, 1, 1, 1, 0, 0},
{0, 1, 0, 1, 1, 1, 0, 1, 0},
{0, 0, 1, 1, 1, 1, 0, 0, 1},
{1, 0, 0, 1, 0, 0, 1, 1, 1},
{0, 1, 0, 0, 1, 0, 1, 1, 1},
{0, 0, 1, 0, 0, 1, 1, 1, 1}}

and the solution

b := {0, 1, 0, 1, 0, 1, 2, 3, 2}.

$\endgroup$
  • 1
    $\begingroup$ Please paste in your code to the question, not a screenshot, as it's too tedious to type out. $\endgroup$ – flinty Aug 14 at 17:05
  • 1
    $\begingroup$ Updated my post with the matrix in question. $\endgroup$ – LightsOutTorus Aug 14 at 17:07
  • $\begingroup$ Det[M, Modulus -> 4] is zero, but you can find solutions using FindInstance[M.Array[x, 9] == {0, 0, 0, 0, 2, 0, 0, 0, 0}, Array[x, 9], Modulus -> 4] . I'm a little spooked that LinearSolve couldn't do it though. $\endgroup$ – flinty Aug 14 at 17:15
  • 1
    $\begingroup$ From the docs: Some functions require that Modulus be set to a prime, or a power of a prime. $\mathbb{Z}_n$ is a finite field when n is prime. 4 is 2^2 but perhaps because PowerMod[2, -1, 4] ... PowerMod::ninv: 2 is not invertible modulo 4. you cannot use it here as 2 has no multiplicative inverse and integers mod 4 do not form a finite field. You may have to stick with FindInstance then. $\endgroup$ – flinty Aug 14 at 17:39
  • 1
    $\begingroup$ Where the "usual" row reduction fails due to lack of multiplicative inverses, the function to consider using is HermiteDecomposition. That's what Solve will be using under the hood in this case. $\endgroup$ – Daniel Lichtblau Aug 15 at 21:06
1
$\begingroup$

The problem is caused by the integers mod 4 not forming a finite field and 2 having no unique multiplicative inverse. This prevents RowReduce from doing its job, even with Method->"DivisionFreeRowReduction".

PowerMod[2, -1, 4]
(* PowerMod::ninv: 2 is not invertible modulo 4. *)

One possibility is to use FindInstance:

FindInstance[M.Array[x, 9] == {0, 0, 0, 0, 2, 0, 0, 0, 0}, Array[x, 9], Modulus -> 4]

But better is Solve which works because it can generate a class of solutions with generated parameters unlike LinearSolve. Setting the generated parameters to zero yields the solution b.

Mod[Values[
  Solve[M.Array[x, 9] == {0, 0, 0, 0, 2, 0, 0, 0, 0}, Array[x, 9], 
    Modulus -> 4] /. C[_] :> 0
  ], 4]

(* {{0, 1, 0, 1, 0, 1, 2, 3, 2}} *)

Other solutions appear with C[_]:>1 or C[_]:>3 (modulo 4):

{{2, 3, 2, 3, 2, 3, 2, 3, 2}}

... and many more are possible from the family:

fam = {2 C[1], 1 + 2 C[2], 2 C[3], 1 + 2 C[4], 2 C[1] + 2 C[2] + 2 C[4], 
 1 + 2 C[1] + 2 C[3] + 2 C[4], 2 + 2 C[1] + 2 C[2] + 2 C[3] + 2 C[4], 
 3 + 2 C[3] + 2 C[4], 2 + 2 C[2] + 2 C[4]};

rules = Thread[{C[1], C[2], C[3], C[4]} -> #] & /@ Tuples[{0, 1, 2, 3}, 4];
DeleteDuplicates[Mod[fam /. rules, 4]];

(*
{0,1,0,1,0,1,2,3,2}
{0,1,0,3,2,3,0,1,0}
{0,1,2,1,0,3,0,1,2}
{0,1,2,3,2,1,2,3,0}
{0,3,0,1,2,1,0,3,0}
{0,3,0,3,0,3,2,1,2}
{0,3,2,1,2,3,2,1,0}
{0,3,2,3,0,1,0,3,2}
{2,1,0,1,2,3,0,3,2}
{2,1,0,3,0,1,2,1,0}
{2,1,2,1,2,1,2,1,2}
{2,1,2,3,0,3,0,3,0}
{2,3,0,1,0,3,2,3,0}
{2,3,0,3,2,1,0,1,2}
{2,3,2,1,0,1,0,1,0}
{2,3,2,3,2,3,2,3,2}
*)

You may want to read this answer which goes into more detail.

| improve this answer | |
$\endgroup$

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.