# Non-valid modulus when using LinearSolve

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

• Please paste in your code to the question, not a screenshot, as it's too tedious to type out. – flinty Aug 14 '20 at 17:05
• Updated my post with the matrix in question. – LightsOutTorus Aug 14 '20 at 17:07
• 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. – flinty Aug 14 '20 at 17:15
• 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. – flinty Aug 14 '20 at 17:39
• 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. – Daniel Lichtblau Aug 15 '20 at 21:06

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.