7.102 bug in Linsolve in Maple V.4 (7.8.97)

7.102.1 W. Edwin Clark

Be careful with Linsolve mod 2. Here’s an example of what can happen. (with Maple VR4 on both Mac and Solaris)

[By the way can someone tell me how to look at the code for the procedure Linsolve mod p. The obvious method doesn’t work, ie, using interface(verboseproc=2); eval(Linsolve);

> with(linalg): 
> A:=matrix([[0,0,0,1,0,1],[1,1,1,0,0,0],[0,0,1,1,1,0],[0,0,0,1,1,1]]); 
 
                       [0    0    0    1    0    1] 
                       [                          ] 
                       [1    1    1    0    0    0] 
                  A := [                          ] 
                       [0    0    1    1    1    0] 
                       [                          ] 
                       [0    0    0    1    1    1] 
 
> b:=vector([1,1,1,1]); 
 
                          b := [1, 1, 1, 1] 
 
> x:=Linsolve(A,b) mod 2; 
 
         x := [_t[2] + _t[6], _t[2], _t[6], _t[6], 1, _t[6]] 
 
> map(`mod`,evalm(A &* x - b),2); 
 
                             [1, 1, 0, 0]
 

Clearly this should be zero.

Another problem is that if A has more rows than columns Linsolve(A,b) mod 2 returns an error message.

The bug is removed with Maple V Release 5. (U. Klein)

Here’s a work-around for the first problem. For the second one can apply Gausselim mod 2 to the augmented matrix and then delete the zero rows.

> B:=augment(A,transpose(matrix([[1,1,1,1]]))); 
 
                     [0    0    0    1    0    1    1] 
                     [                               ] 
                     [1    1    1    0    0    0    1] 
                B := [                               ] 
                     [0    0    1    1    1    0    1] 
                     [                               ] 
                     [0    0    0    1    1    1    1] 
 
> Gausselim(B) mod 2; 
 
                  [1    1    1    0    0    0    1] 
                  [                               ] 
                  [0    0    1    1    1    0    1] 
                  [                               ] 
                  [0    0    0    1    0    1    1] 
                  [                               ] 
                  [0    0    0    0    1    0    0] 
 
> x:=linsolve(delcols(B,7..7),col(B,7)); 
 
     x := [1 - _t[1] - _t[2], _t[1], _t[2], 1 - _t[2], 0, _t[2]] 
 
> map(`mod`,evalm(A &* x - cb),2); 
 
                             [0, 0, 0, 0]
 

7.102.2 Robert Israel (13.8.97)

The bug is not just in mod 2, but for any modulus when the matrix A is not square. For example, with Edwin’s example,

> A:=matrix([[0,0,0,1,0,1],[1,1,1,0,0,0],[0,0,1,1,1,0],[0,0,0,1,1,1]]); 
> b:=vector([1,1,1,1]); 
> x:= Linsolve(A,b) mod 10; 
         x := [9 _t[2] + 9 _t[6], _t[2], _t[6], 9 _t[6], 1, _t[6]] 
 
> map(`mod`,evalm(A &* x - b),10); 
                          [9, 9, 0, 0]
 

| [By the way can someone tell me how to look at the code ...

Try this:

> interface(verboseproc=2); 
> readlib(`mod/Linsolve`);
 

The bug appears to be near the end of the procedure, in the line

x[j] := Normal((B[i, m + 1] - t)*s) mod p
 

which should be

x[j] := Normal((B[i, n + 1] - t)*s) mod p
 

After making this change in the procedure, it seems to work correctly.

> x:= Linsolve(A,b) mod 10; 
      x := [1 + 9 _t[2] + 9 _t[6], _t[2], _t[6], 1 + 9 _t[6], 0, _t[6]] 
 
> map(`mod`,evalm(A &* x - b),10); 
                [0, 0, 0, 0]