Incorrect saturation of integer matrix

[vbraun]

This bug happens with matrices with 76 columns (but not 75) whose entries are random integers -1 or 1. The actual entries matter, but the following random choice is quite reliable at triggering it:

sage: M = matrix(ZZ, 10,76,lambda i,j: randrange(-1,3,2))                                                                                                                                                        
sage: M.right_kernel().basis()[-1].is_zero()
True

Note that a basis vector of the null space should never be zero, so the correct output is always False.

For reference, here is a 6 x 76 matrix that triggers the bug:

M = matrix(ZZ, 
[(1, -1, -1, -1, 1, 1), (-1, -1, 1, -1, 1, -1), (1, 1, 1, -1, 1, -1), 
 (-1, 1, 1, 1, -1, -1), (1, -1, 1, -1, -1, -1), (1, -1, 1, 1, 1, 1), 
 (-1, -1, 1, -1, 1, -1), (-1, 1, -1, -1, -1, -1), (1, -1, 1, 1, -1, -1), 
 (-1, 1, -1, 1, 1, 1), (1, -1, -1, -1, -1, 1), (1, -1, 1, 1, -1, -1), 
 (-1, -1, -1, -1, 1, -1), (1, 1, -1, 1, -1, 1), (-1, 1, -1, 1, 1, -1),
 (1, -1, 1, 1, 1, 1), (-1, -1, 1, 1, -1, -1), (1, -1, 1, 1, -1, -1), 
 (1, -1, 1, 1, -1, 1), (-1, -1, 1, -1, -1, 1), (1, -1, -1, 1, -1, -1), 
 (1, -1, 1, 1, 1, -1), (-1, 1, 1, -1, 1, -1), (1, -1, -1, 1, -1, -1), 
 (-1, -1, 1, -1, -1, -1), (1, 1, -1, 1, 1, -1), (1, 1, -1, 1, 1, -1), 
 (1, 1, 1, -1, 1, -1), (-1, 1, -1, -1, 1, -1), (-1, -1, -1, 1, -1, 1),
 (1, -1, -1, 1, 1, -1), (-1, 1, 1, -1, 1, 1), (-1, 1, 1, 1, 1, -1), 
 (1, -1, -1, 1, -1, -1), (-1, 1, 1, -1, 1, -1), (-1, 1, -1, -1, 1, 1),
 (-1, 1, -1, -1, 1, -1), (-1, 1, -1, 1, -1, -1), (-1, -1, 1, -1, -1, -1),
 (-1, -1, 1, 1, -1, -1), (1, -1, -1, 1, 1, -1), (1, -1, 1, -1, -1, 1), 
 (-1, 1, 1, -1, -1, 1), (-1, -1, -1, 1, -1, -1), (-1, 1, 1, 1, 1, 1),  
 (-1, 1, 1, 1, -1, -1), (-1, 1, 1, 1, -1, -1), (1, -1, -1, 1, -1, 1), 
 (1, 1, -1, -1, -1, 1), (-1, 1, -1, -1, 1, -1), (-1, -1, 1, 1, 1, 1), 
 (-1, -1, -1, 1, 1, 1), (1, -1, 1, 1, -1, 1), (1, -1, 1, 1, 1, 1), 
 (1, -1, 1, 1, -1, -1), (1, -1, -1, -1, -1, 1), (1, -1, -1, 1, -1, 1),
 (-1, 1, -1, 1, -1, -1), (1, -1, -1, 1, 1, -1), (1, -1, 1, -1, -1, 1),
 (-1, -1, -1, 1, -1, 1), (-1, -1, 1, -1, -1, 1), (1, 1, -1, -1, -1, -1),
 (1, 1, 1, 1, -1, -1), (1, 1, -1, 1, 1, -1), (-1, -1, 1, 1, -1, 1), 
 (1, 1, 1, 1, 1, 1), (-1, 1, 1, 1, 1, 1), (1, 1, 1, -1, 1, 1), 
 (1, 1, 1, 1, -1, 1), (1, -1, -1, 1, 1, -1), (1, -1, -1, -1, -1, -1), 
 (1, 1, 1, -1, -1, 1), (-1, 1, -1, 1, 1, 1), (1, 1, 1, -1, -1, -1), 
 (1, -1, 1, 1, 1, 1)]
).transpose()

The actual cause is that there is fallback to pari in algorithm='padic' if the matrix is ill-conditioned, but we did not pass include_zero_rows=False in this case. This is fixed in the patch.

While adding doctests, I noted that pari with flag=4, include_zero_rows=False also gives an incorrect result. The patch also disables this combination, the follow-up ticket #12346 will deal with this and re-enable it once this issue is fixed upstream.

[vbraun]

I built a new iml-1.0.3 spkg but it does not fix the issue.

[vbraun]

I was off-track; IML computes the correct kernel but Sage then returns its saturation. It turns out that computing the saturation introduces the extra null vectors

sage: K = M._rational_kernel_iml().transpose();  K
70 x 76 dense matrix over Integer Ring (type 'print K.str()' to see all of the entries)
sage: K.saturation()
76 x 76 dense matrix over Integer Ring
sage: K.saturation().row(71).is_zero()
True

[vbraun]

75 is the cutoff where the hnf computation switches from algorithm='pari' to algorithm='padic'`. The latter does not always chop off zero rows:

sage: m = matrix([(-2, 1, 9, 2, -8, 1, -3, -1, -4, -1), 
...               (5, -2, 0, 1, 0, 4, -1, 1, -2, 0),
...               (-11, 3, 1, 0, -3, -2, -1, -11, 2, -2), 
...               (-1, 1, -1, -2, 1, -1, -1, -1, -1, 7), 
...               (-2, -1, -1, 1, 1, -2, 1, 0, 2, -4)]).stack(
...               200 * identity_matrix(ZZ, 10))
sage: matrix(ZZ,m).hermite_form(algorithm='padic', include_zero_rows=False)
[  1   0   2   0  13   5   1 166  72  69]
[  0   1   1   0  20   4  15 195  65 190]
[  0   0   4   0  24   5  23  22  51 123]
[  0   0   0   1  23   7  20 105  60 151]
[  0   0   0   0  40   4   0  80  36  68]
[  0   0   0   0   0  10   0 100 190 170]
[  0   0   0   0   0   0  25   0 100 150]
[  0   0   0   0   0   0   0 200   0   0]
[  0   0   0   0   0   0   0   0 200   0]
[  0   0   0   0   0   0   0   0   0 200]
[  0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0]

[vbraun]

The actual cause is that there was a fallback to pari in case of an ill-conditioned matrix (which this one turns out to be), but we did not pass include_zero_rows=False in this case. This is fixed in the patch.

While adding doctests, I noted that pari with flag=4, include_zero_rows=False also gives an incorrect result. The patch also disables this combination, the follow-up ticket #12346 will deal with this and re-enable it once this issue is fixed upstream.

[was]

NOTE: I will give this a positive review once the test suite runs and the four run-on sentences are fixed.

[vbraun]

Updated patch

[vbraun]

The updated patch fixes the (really short) run-on sentences.