Non-valid modulus when using LinearSolve

Question

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:
.
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}.

flinty · Accepted Answer

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.

Non-valid modulus when using LinearSolve

One Answer

Add your own answers!

Ask a Question