discopt / cmr

Combinatorial Matrix Recognition
https://discopt.github.io/cmr/
MIT License
8 stars 4 forks source link

regular matroid: matrix camion-signed but not totally unimodular(?) #11

Closed mel-koch closed 2 years ago

mel-koch commented 3 years ago

The matroid represented by the following matrix is regular. I might be mistaken but I think the Camion-signed version has to be totally unimodular. In this case the cmr-camion command states that it is Camion-signed but the cmr-tu command states that it is not totally unimodular.

 14 15
 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1
 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1
 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1
 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1
 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1
 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1
 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1
 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1
 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1
 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1
 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1
 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1
 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1
 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
discopt commented 3 years ago

Consider the submatrix indexed by rows 1, 12, 13, 14 and columns 12,13,14,15:

1 1 1 1
1 0 0 1
0 1 0 1
0 0 1 1

It is not regular for the following reason: carry out a binary pivot on the top-right element, which gives you

1 1 1 1
0 1 1 1
1 0 1 1
1 1 0 1

Now removal of the first row gives you a representation matrix of the fano matroid F_7. This shows that the matroid represented by your matrix contains F_7 as a minor and hence it is not regular.

alessiodali commented 3 years ago

Now removal of the first row gives you a representation matrix of the fano matroid F_7. This shows that the matroid represented by your matrix contains F_7 as a minor and hence it is not regular.

Hello! I am quite confused: I have just checked for regularity of the given matroid both via Sage and Macaulay2 (in the latter case using the "Matroids" package), and I got a "yes" with both systems. What am I missing?

discopt commented 3 years ago

The correspondence of TU of a matrix A to regularity of the matroid M holds if A is the compact representation matrix, i.e., the columns of the matrix [A | I] define the matroid M. Is that the case for you? So a 14x15 matrix defines a matroid with 29 elements. I assume that this is not the case?!

discopt commented 3 years ago

I added a clarification to the docs: https://discopt.github.io/cmr/matroids.html