Bases of representable/vector matroids in Sage

Posted on by

A matroid M is specified by a set X of “points” and a collection B of “bases, where X \subset 2^X, satisfying certain conditions (see, for example, Oxley’s book, Matroid theory).

One way to construct a matroid, as it turns out, is to consider a matrix M with coefficients in a field F. The column vectors of M are indexed by the numbers J = \{1,2,\dots,n\}. The collection B of subsets of J associated to the linearly independent column vectors of M of cardinality r = rank_F(M) forms a set of bases of a matroid having points X=J.

How do you compute B? The following Sage code should work.



def independent_sets(mat):
    """
    Finds all independent sets in a vector matroid.

    EXAMPLES:
        sage: M = matrix(GF(2), [[1,0,0,1,1,0],[0,1,0,1,0,1],[0,0,1,0,1,1]])
        sage: M
        [1 0 0 1 1 0]
        [0 1 0 1 0 1]
        [0 0 1 0 1 1]
        sage: independent_sets(M)  
        [[0, 1, 2], [], [0], [1], [0, 1], [2], [0, 2], [1, 2], 
        [0, 1, 4], [4], [0, 4], [1, 4], [0, 1, 5], [5], [0, 5], 
        [1, 5], [0, 2, 3], [3], [0, 3], [2, 3], [0, 2, 5], [2, 5], 
        [0, 3, 4], [3, 4], [0, 3, 5], [3, 5], [0, 4, 5], [4, 5], 
        [1, 2, 3], [1, 3], [1, 2, 4], [2, 4], [1, 3, 4], [1, 3, 5], 
        [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5]]
        sage: M = matrix(GF(3), [[1,0,0,1,1,0],[0,1,0,1,0,1],[0,0,1,0,1,1]])
        sage: independent_sets(M)
        [[0, 1, 2], [], [0], [1], [0, 1], [2], [0, 2], [1, 2], 
        [0, 1, 4], [4], [0, 4], [1, 4], [0, 1, 5], [5], [0, 5], 
        [1, 5], [0, 2, 3], [3], [0, 3], [2, 3], [0, 2, 5], [2, 5], 
        [0, 3, 4], [3, 4], [0, 3, 5], [3, 5], [0, 4, 5], [4, 5], 
        [1, 2, 3], [1, 3], [1, 2, 4], [2, 4], [1, 3, 4], [1, 3, 5], 
        [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]
        sage: M345 = matrix(GF(2), [[1,1,0],[1,0,1],[0,1,1]])
        sage: M345.rank()
        2
        sage: M345 = matrix(GF(3), [[1,1,0],[1,0,1],[0,1,1]])
        sage: M345.rank()
        3
    """
    F = mat.base_ring()
    n = len(mat.columns())
    k = len(mat.rows())
    J = Combinations(n,k)
    indE = []
    for x in J:
        M = matrix([mat.column(x[0]),mat.column(x[1]),mat.column(x[2])])
        if k == M.rank():     # all indep sets of max size
            indE.append(x)
            for y in powerset(x): # all smaller indep sets
                if not(y in indE):
                    indE.append(y)
    return indE

def bases(mat, invariant = False):
    """
    Find all bases in a vector/representable matroid.

    EXAMPLES:
        sage: M = matrix(GF(2), [[1,0,0,1,1,0],[0,1,0,1,0,1],[0,0,1,0,1,1]])
        sage: bases(M)

        [[0, 1, 2],
         [0, 1, 4],
         [0, 1, 5],
         [0, 2, 3],
         [0, 2, 5],
         [0, 3, 4],
         [0, 3, 5],
         [0, 4, 5],
         [1, 2, 3],
         [1, 2, 4],
         [1, 3, 4],
         [1, 3, 5],
         [1, 4, 5],
         [2, 3, 4],
         [2, 3, 5],
         [2, 4, 5]]
        sage: L = [x[1] for x in bases(M, invariant=True)]; L.sort(); L
         [5, 16, 17, 33, 37, 44, 45, 48, 81, 84, 92, 93, 96, 112, 113, 116]
    """
    r = mat.rank()
    ind = independent_sets(mat)
    B = []
    for x in ind:
        if len(x) == r:
            B.append(x)
    B.sort()
    if invariant == True:
        B = [(b,sum([k*2^(k-1) for k in b])) for b in B]
    return B

Leave a comment