CODEWITHSUNDEEP
python-3.xsage
Elle Najt
Elle Najt

Reputation: 233

Sage giving me a basis of the wrong rank for a linear matroid, or, what am I doing wrong?

Here is a minimal working example:

import numpy as np
import sage

D = np.array([[-1., -1., -1.,  0.,  0.,  0.,  1.],
       [ 1.,  0.,  0., -1.,  1.,  0.,  0.],
       [ 0.,  1.,  0.,  0., -1.,  1.,  0.],
       [ 0.,  0.,  1.,  0.,  0., -1.,  0.],
       [ 0.,  0.,  0.,  1.,  0.,  0., -1.],
       [ 1.,  1.,  1.,  1.,  1.,  1.,  1.]])

I = Matrix(D)
M = Matroid(I)

for base in M.bases():
    A = I[:, list(base) ]
    print(np.linalg.matrix_rank(A))
    if np.linalg.matrix_rank(A) == 4:
        print(base)

When I run this on my computer, it tells me that one of the basis has rank 4, instead of 5. M.rank() verifies that 5 is the rank of the matroid, and indeed most of the basis are of that rank. However, in a matroid all the basis are of the same rank, so I'm confused about what's going wrong.

That basis is {0, 1, 3, 4, 6}, which gives the matrix:

array([[-1., -1.,  0.,  0.,  1.],
       [ 1.,  0., -1.,  1.,  0.],
       [ 0.,  1.,  0., -1.,  0.],
       [ 0.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  1.,  0., -1.],
       [ 1.,  1.,  1.,  1.,  1.]])

Which one can check separately has rank 4. (For instance, with wolframalpha.) One can also verify that I am slicing into I correctly.

The other possibility I investigated was whether the column order got mixed up when passing to the matroid class. However, calling M.representation() returns the matrix D, so I don't think this is the case.

Upvotes: 1

Views: 71

Answers (1)

Samuel Lelièvre
Samuel Lelièvre

Reputation: 3453

It's a floating-point problem. If instead you use

D = np.array([
        [-1, -1, -1,  0,  0,  0,  1],
        [ 1,  0,  0, -1,  1,  0,  0],
        [ 0,  1,  0,  0, -1,  1,  0],
        [ 0,  0,  1,  0,  0, -1,  0],
        [ 0,  0,  0,  1,  0,  0, -1],
        [ 1,  1,  1,  1,  1,  1,  1]])

then the problem does not occur.

Upvotes: 2

Related Questions