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 Answers

- Jon Church on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- haakon.io on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP