5
$\begingroup$

LinearSolve claims there is no solution to m.x==b mod 26.

m = {{5, 16, 12, 25, 23, 12, 20, 16}, {8, 22, 14, 13, 18, 17, 7, 
    9}, {18, 0, 13, 14, 11, 1, 18, 23}, {8, 17, 8, 1, 9, 24, 19, 
    19}, {19, 2, 15, 2, 14, 24, 15, 18}, {4, 0, 14, 16, 6, 20, 23, 
    18}, {11, 8, 20, 25, 15, 5, 5, 4}};
b = {{4, 19, 7, 0, 19, 0, 13, 24}, {8, 17, 17, 4, 6, 20, 11, 0}, {17, 
   8, 19, 8, 4, 18, 19, 14}, {14, 10, 15, 11, 0, 2, 4, 19}, {7, 4, 9, 
   20, 17, 24, 5, 20}, {17, 19, 7, 4, 17, 18, 0, 8}, {3, 8, 13, 19, 4,
    17, 12, 4}}
LinearSolve[m, b, Modulus -> 26]

(* RowReduce::nmod: {{1,24,18,5,15,18,4,24,6,9,<<6>>},{0,8,0,21,10,15,5,21,8,11,<<6>>},{0,0,14,18,8,6,8,10,16,24,<<6>>},{0,0,0,10,16,2,16,10,16,22,<<6>>},{0,0,0,0,10,24,20,4,12,4,<<6>>},{0,0,0,0,0,12,4,18,14,20,<<6>>},{0,0,0,0,0,0,20,8,14,22,<<6>>}}
is not valid modulo 26. *)

(* LinearSolve::nosol: Linear equation encountered that has no solution. *)

But solving over rationals and then reducing modulo 26 gives perfectly valid solution:

x=PolynomialMod[LinearSolve[m, b], 26]

(* {{18, 0, 18, 5, 14, 10, 7, 5}, {23, 12, 13, 4, 14, 18, 4, 8}, {12, 13,
   8, 15, 14, 22, 20, 1}, {19, 8, 5, 21, 15, 3, 6, 14}, {9, 19, 6, 8, 
  6, 13, 16, 23}, {20, 0, 19, 9, 6, 19, 13, 18}, {15, 5, 25, 12, 11, 
  10, 2, 24}, {0, 0, 0, 0, 0, 0, 0, 0}} *)

Which can be verified by:

Mod[m . x, 26] == b

(* True *)

Is it a bug or am I missing something? (My version is 13.0.1.0)

Update:

The answer in the provided link is not good.

  1. LinearSolve has no problem to return solution over rationals that is singular over rationals same way as is singular over modulo 26. Why it should not return solution over modulo then?

  2. There is even Method->"DivisionFreeRowReduction" that says "division free" - which means no division (no matrix inversion) should be used. Nevertheless the method fails too.

  3. The answer in the link does not address the problem as a bug - which is evident it is a bug. Equivalent of LinearSolve in Sagemath has no problems with it whether over rationals or over modulo 26.

$\endgroup$
0

0