Possible bug in Sage 6.2...?

[Dillon Mayhew]

Hi all,

I can't understand some sage matroid behaviour.

Suppose we want to create a catalogue of regular matroids, like so:

from sage.matroids.advanced import *
def Grow(List):
ListPlus=[]
for M in List:
ListPlus.extend(M.linear_extensions(element=len(M),simple=True))
ListPlus.extend(M.linear_coextensions(element=len(M),cosimple=True))
ListPlus=get_nonisomorphic_matroids(ListPlus)
return ListPlus

Regular={}
Regular[6]=[matroids.Wheel(3)]
Regular[7]=Grow(Regular[6])
Regular[8]=Grow(Regular[7])
Regular[8].append(matroids.Wheel(4))
Regular[9]=Grow(Regular[8])
Regular[10]=Grow(Regular[9])
Regular[10].append(matroids.Wheel(5))
Regular[11]=Grow(Regular[10])
Regular[12]=Grow(Regular[11])
Regular[12].append(matroids.Wheel(6))

Now the matroid N is the dual of M(K3,4).

N=Matroid(reduced_matrix=matrix(GF(2),[[1,1,0,0,1,0],[1,0,1,0,1,0],[1,0,0,1,1,0],[1,1,0,0,0,1],[1,0,1,0,0,1],[1,0,0,1,0,1]]))

N does not appear in the regular catalogue.

[i for i in range(len(Regular[12])) if Regular[12][i].is_isomorphic(N)]

[]

By modifying the Grow command, we can get it to appear.

List=[]
for M in Regular[11]:
List.extend(M.linear_extensions(element=len(M),simple=True))
List=get_nonisomorphic_matroids(List)

[i for i in range(len(List)) if List[i].is_isomorphic(N)]

[24]

Can anybody explain this?

Cheers,

Dillon

[Rudi Pendavingh]

Hi Dillon,

I think the problem is your definition of N:

N=Matroid(reduced_matrix=matrix(GF(2),[[1,1,0,0,1,0],[1,0,1,0,1,0],[1,0,0,1,1,0],[1,1,0,0,0,1],[1,0,1,0,0,1],[1,0,0,1,0,1]]))

This produces a LinearMatroid over GF(2), whereas the matroids in your Regular[12] are all RegularMatroids. The following should solve the problem, since it creates N as a RegularMatroid:

N=Matroid(reduced_matrix=matrix(GF(2),[[1,1,0,0,1,0],[1,0,1,0,1,0],[1,0,0,1,1,0],[1,1,0,0,0,1],[1,0,1,0,0,1],[1,0,0,1,0,1]]), regular=True)

Sage can only test isomorphism directly if the matroids are stored in the same type. Of course a RegularMatroids can easily be turned into a LinearMatroid over GF(2), I know, but Sage does not know. We chose this as standard behaviour (M, N not same type => M.isomorphic(N) returns False), since here appears to be no proper way to automatically handle this in general without investing significant cpu time. I mean, how to resolve regular and GF(2) is clear, but there are many other combinations and we also did not want to silently resolve the problem in some cases and not in others, since that is even more confusing. 

But now that you bring it up, we could consider a different answer (e.g. no answer, ‘None’ rather than False) or an error message when someone attempts to test isomorphism between types, because I can see how the current behaviour may lead to silent errors. 

Cheers,

Rudi

[Stefan van Zwam]

Hi Rudi,

>
> Sage can only test isomorphism directly if the matroids are stored in the same type.

I think you're confusing is_isomorphic and is_field_isomorphic. The former *should* test abstract isomorphism between any pair of matroids.

So the question is: is N really not part of the list at first, or is the isomorphism test not finding it? I'll experiment a little bit soon.

--Stefan

[Rudi Pendavingh]

Hi Stefan,

>> Sage can only test isomorphism directly if the matroids are stored in the same type.
>
> I think you're confusing is_isomorphic and is_field_isomorphic. The former *should* test abstract isomorphism between any pair of matroids.
>

You’re right of course, sorry about that. I should not answer e-mail before my first coffee.

> So the question is: is N really not part of the list at first, or is the isomorphism test not finding it? I'll experiment a little bit soon.
>

My experiment says N is in the list, but that the matroid M in Regular[12] which is isomorphic to N shows the following curious behavour:

N=Matroid(reduced_matrix=matrix(GF(2),[[1,1,0,0,1,0],[1,0,1,0,1,0],[1,0,0,1,1,0],[1,1,0,0,0,1],[1,0,1,0,0,1],[1,0,0,1,0,1]]))

N2=Matroid(reduced_matrix=matrix(GF(2),[[1,1,0,0,1,0],[1,0,1,0,1,0],[1,0,0,1,1,0],[1,1,0,0,0,1],[1,0,1,0,0,1],[1,0,0,1,0,1]]), regular=True)

N.is_isomorphic(N2)
True

M.is_isomorphic(N)
False

M.is_isomorphic(N2)
True

Now what is up with that?

—Rudi

[Stefan van Zwam]

The problem seems to be in the _weak_invariant() method: if N is as defined below, and M is the matroid in the catalog, we get:

sage: (N._weak_invariant(), M._weak_invariant())
(-7774345140401701701, -4449946732485601636)

That's when the isomorphism test decides these guys are different.

--Stefan

[Rudi Pendavingh]

But N2._weak_invariant() also gives -7774345140401701701, and M.is_isomorphic(N2) yields True.

—Rudi

> --
>
> ---
> You received this message because you are subscribed to the Google Groups "sage-matroid" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-matroid...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[Stefan van Zwam]

On Nov 5, 2014, at 8:34 AM, Rudi Pendavingh wrote:

> But N2._weak_invariant() also gives -7774345140401701701, and M.is_isomorphic(N2) yields True.

That's because RegularMatroid._is_isomorphic does this:

if type(other) == RegularMatroid:
return self.is_field_isomorphic(other)
else:
return LinearMatroid._is_isomorphic(self, other)

The _weak_invariant test only comes into play in the "else" clause.

--Stefan

[Dillon Mayhew]

Right, so the weak_invariant is not acting as an invariant on
isomorphism classes? Doesn't that have an effect on the general
isomorphism test (not just within the regular matroid type)?

D.

[Stefan van Zwam]

It does, and must be a bug. It involves hashing, so in the worst case it’s a Python or Cython bug.

For the time being, convert everything to binary matroids before doing a membership test like that.

—Stefan.

[Dillon Mayhew]

On Thu, Nov 6, 2014 at 12:45 PM, Stefan van Zwam
<stefan...@gmail.com> wrote:
> It does, and must be a bug. It involves hashing, so in the worst case it’s a Python or Cython bug.
>
> For the time being, convert everything to binary matroids before doing a membership test like that.

That will avoid the issue then?

D.

[Stefan van Zwam]

> On Nov 5, 2014, at 5:50 PM, Dillon Mayhew <dillon...@gmail.com> wrote:
>
> On Thu, Nov 6, 2014 at 12:45 PM, Stefan van Zwam
> <stefan...@gmail.com> wrote:
>> It does, and must be a bug. It involves hashing, so in the worst case it’s a Python or Cython bug.
>>
>> For the time being, convert everything to binary matroids before doing a membership test like that.
>
> That will avoid the issue then?

Probably. It depends on which class is misreporting the weak invariant. I'll do more tests tomorrow morning.

--Stefan

[Stefan van Zwam]

Actually, it won't avoid the issue. The weak_invariant reported by the matroid in your generated list is different from the invariants of the LinearMatroid, BasisMatroid, BinaryMatroid and RegularMatroid that I constructed from the matrix.

This is weird.

--Stefan

[Stefan van Zwam]

Ok, maybe my guess that _weak_invariant was to blame, was wrong. It seems like it's the isomorphism test for regular matroids. Look:

Mnew = RegularMatroid(groundset=range(12), matrix=Matrix(ZZ,

[[ 1, 0, 0, 0, 1, 0, 0,-1,-1, 0, 1, 0],

 [ 0, 1, 0, 0,-1, 1, 0, 0, 0, 0, 0, 0],

 [ 0, 0, 1, 0, 0,-1, 1, 0, 1, 0,-1, 0],

 [ 0, 0, 0, 1, 0, 0,-1, 1, 0, 0, 0, 0],

 [ 0, 0, 0, 0, 0, 1,-1, 0, 0, 1, 1, 0],

 [ 0, 0, 0, 0, 1, 0, 0,-1,-1, 0, 0, 1]]))

Nnew = RegularMatroid(groundset=range(12), matrix=Matrix(ZZ,

[[1,0,0,0,0,0,1,1,0,0,1,0],

 [0,1,0,0,0,0,1,0,1,0,1,0],

 [0,0,1,0,0,0,1,0,0,1,1,0],

 [0,0,0,1,0,0,1,1,0,0,0,1],

 [0,0,0,0,1,0,1,0,1,0,0,1],

 [0,0,0,0,0,1,1,0,0,1,0,1]]))

 

print Mnew._weak_invariant()

print Nnew._weak_invariant()

print Mnew.is_isomorphic(Nnew)

-4449946732485601636
-7774345140401701701
True

BM = BasisMatroid(Mnew)
print BM._weak_invariant()
print BM

-4449946732485601636
Matroid of rank 6 on 12 elements with 432 bases

BN = BasisMatroid(Nnew)
print BN._weak_invariant()
print BN

-7774345140401701701
Matroid of rank 6 on 12 elements with 432 bases

BM.is_isomorphic(BN)

False

So it seems is_isomorphic() gives false positives for regular matroids. To show they really are different:

len(Mnew.circuits()) - len(Nnew.circuits())

-7

This means my earlier advice, of going to BinaryMatroid instances for isomorphism tests, would circumvent the bug.

--Stefan.

[Stefan van Zwam]

I reported the bug on Sage's Trac system:

http://trac.sagemath.org/ticket/17316

Now the harder job of finding time to fix it... we're calling Sage's graph isomorphism test at some point in this, I pray the problem is not in there.

[Rudi Pendavingh]

Hi Stefan,

I think I have found the bug. If M and N are RegularMatroids, the existence of an isomorphism between M._hypergraph() and N._hypergraph() is necessary but not sufficient for the isomorphism of M and N.

Regular matroids are isomomorphic if their projection matrices are isomorphic up to symmetric rescaling of row/column pairs by -1. The hypergraph of M arises from M._projection_matrix(), distinguishes the absolute values of the entries but completely ignores their signs, so that an isomorphism of the hypergraphs will be a mapping that maps the projection matrix up to sign. 

I do not recall implementing _hypertest at all, but maybe I am just repressing the memory now that it is buggy :).. 

The easiest fix is letting hypertest return False if the hypergraphs are not isomorphic; True only if the hypergraphs are isomorphic  *and* the one returned isomorphism of the hypergraphs is indeed a field isomorphism; None otherwise.

Adding some or all `negative triangles' from the projection matrix to the hypergraph may be a good secondary test if the above is inconclusive. in the end we want a hypergraph morphism that has exactly the same `negative cycles’ as the projection matrix. I do not see a very quick and clean way to get that signed graph isomorphism test in there, but I will think about it. The `remnant of the old code’ in _hypergraph seems to do something to this effect, not sure if that hypergraph will give a perfect invariant though, there may be zeros in the matrix.

I cannot work on the code right now moment. I upgraded to Yosemite, which is not supported. But the easy fix should be easy to implement if you don’t want to wait. :).

Best,

Rudi

PS

Mnew._projection()

271

[ 216   72   72   72   36  -36   36  -36  -36  -36  108 -108]
[  72  216   72   72 -108  108   36  -36  -36  -36  -36   36]
[  72   72  216   72   36  -36   36  -36  108  108  -36   36]
[  72   72   72  216   36  -36 -108  108  -36  -36  -36   36]
[  36 -108   36   36  216 -108  -36  -72  -72   36   36   72]
[ -36  108  -36  -36 -108  216  -72  -36  -36   72   72   36]
[  36   36   36 -108  -36  -72  216 -108   36  -72  -72  -36]
[ -36  -36  -36  108  -72  -36 -108  216   72  -36  -36  -72]
[ -36  -36  108  -36  -72  -36   36   72  216  108  -36  -72]
[ -36  -36  108  -36   36   72  -72  -36  108  216   72   36]
[ 108  -36  -36  -36   36   72  -72  -36  -36   72  216 -108]
[-108   36   36   36   72   36  -36  -72  -72   36 -108  216]

Nnew._projection()

274

[ 216  -72  -72 -108   36   36   36  108  -36  -36   72  -36]
[ -72  216  -72   36 -108   36   36  -36  108  -36   72  -36]
[ -72  -72  216   36   36 -108   36  -36  -36  108   72  -36]
[-108   36   36  216  -72  -72   36  108  -36  -36  -36   72]
[  36 -108   36  -72  216  -72   36  -36  108  -36  -36   72]
[  36   36 -108  -72  -72  216   36  -36  -36  108  -36   72]
[  36   36   36   36   36   36  216   72   72   72  108  108]
[ 108  -36  -36  108  -36  -36   72  216  -72  -72   36   36]
[ -36  108  -36  -36  108  -36   72  -72  216  -72   36   36]
[ -36  -36  108  -36  -36  108   72  -72  -72  216   36   36]
[  72   72   72  -36  -36  -36  108   36   36   36  216 -108]
[ -36  -36  -36   72   72   72  108   36   36   36 -108  216]

[Michael Welsh]

> On 12/11/2014, at 1149, Rudi Pendavingh <rudi.pe...@gmail.com> wrote:
>
> I cannot work on the code right now moment. I upgraded to Yosemite, which is not supported. But the easy fix should be easy to implement if you don’t want to wait. :).

Yeah it is. Just get the latest RCs (allegedly). I've been too busy/pre-occupied to test it myself.

[Rudi Pendavingh]

Well, counting negative triangles in the projection matrices will at least distinguish Stefan’s two matroids:

def count_negative_triangles(M):

    t=0

    P=M._projection()

    for i in range(12):

        for j in range(i):

            for k in range(j):

                if P[i][j]*P[j][k]*P[k][i]<0:

                    t=t+1

    return t

count_negative_triangles(Mnew)

96

count_negative_triangles(Nnew)

124

Seems a good idea to at least include this in the r_invariant code, which already takes |E|^3 time due to the computation of the projection matrix. This will not make the other code safe though, just hide this counterexample.

—Rudi

[Stefan van Zwam]

Just a quick update: Rudi fixed the bug, it was reviewed and is included in Sage 6.5.beta1. Unfortunately it is still present in the just-released version 6.4.1.

--Stefan.