Opened 10 years ago

Closed 10 years ago

# Incorrect saturation of integer matrix

Reported by: Owned by: vbraun jason, was critical sage-5.0 linear algebra hnf echelon_form was, cremona, nbruin sage-5.0.beta6 Volker Braun William Stein None of the above - read trac for reasoning.

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.

### comment:1 Changed 10 years ago by vbraun

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

### comment:2 Changed 10 years ago by vbraun

• Cc was cremona nbruin added
• Report Upstream changed from N/A to Not yet reported upstream; Will do shortly.

### comment:3 Changed 10 years ago by vbraun

• Keywords saturation added; IML kernel 76 removed
• Report Upstream changed from Not yet reported upstream; Will do shortly. to N/A
• Summary changed from Incorrect kernel of integer matrix (IML bug?) to Incorrect saturation of integer matrix

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
```

### comment:4 Changed 10 years ago by vbraun

• Keywords hnf echelon_form added; saturation removed

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))
[  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]
```

### comment:5 Changed 10 years ago by vbraun

• Authors set to Volker Braun
• Priority changed from major to critical
• Report Upstream changed from N/A to None of the above - read trac for reasoning.
• Status changed from new to needs_review

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.

### comment:6 Changed 10 years ago by vbraun

• Description modified (diff)

### comment:7 Changed 10 years ago by was

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

Updated patch

### comment:8 Changed 10 years ago by vbraun

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

### comment:9 Changed 10 years ago by was

• Status changed from needs_review to positive_review

### comment:10 Changed 10 years ago by jdemeyer

• Reviewers set to William Stein

### comment:11 Changed 10 years ago by jdemeyer

• Merged in set to sage-5.0.beta6
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.