# Non-valid modulus when using LinearSolve

Mathematica Asked by LightsOutTorus on November 26, 2020

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

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.

Correct answer by flinty on November 26, 2020