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
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP