A matroid M is specified by a set X of “points” and a collection B of “bases, where , 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 . The collection B of subsets of J associated to the linearly independent column vectors of M of cardinality forms a set of bases of a matroid having points .

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

You must be logged in to post a comment.