Matroid construction#

Theory#

Matroids are combinatorial structures that capture the abstract properties of (linear/algebraic/…) dependence. Formally, a matroid is a pair \(M = (E, I)\) of a finite set \(E\), the groundset, and a collection of subsets \(I\), the independent sets, subject to the following axioms:

  • \(I\) contains the empty set

  • If \(X\) is a set in \(I\), then each subset of \(X\) is in \(I\)

  • If two subsets \(X\), \(Y\) are in \(I\), and \(|X| > |Y|\), then there exists \(x \in X - Y\) such that \(Y + \{x\}\) is in \(I\).

See the Wikipedia article on matroids for more theory and examples. Matroids can be obtained from many types of mathematical structures, and Sage supports a number of them.

There are two main entry points to Sage’s matroid functionality. The object matroids. contains a number of constructors for well-known matroids. The function Matroid() allows you to define your own matroids from a variety of sources. We briefly introduce both below; follow the links for more comprehensive documentation.

Each matroid object in Sage comes with a number of built-in operations. An overview can be found in the documentation of the abstract matroid class.

Built-in matroids#

For built-in matroids, do the following:

  • Within a Sage session, type matroids. (Do not press Enter, and do not forget the final period “.”)

  • Hit Tab.

You will see a list of methods which will construct matroids. For example:

sage: M = matroids.Wheel(4)
sage: M.is_connected()
True

>>> from sage.all import *
>>> M = matroids.Wheel(Integer(4))
>>> M.is_connected()
True

or:

sage: U36 = matroids.Uniform(3, 6)
sage: U36.equals(U36.dual())
True

>>> from sage.all import *
>>> U36 = matroids.Uniform(Integer(3), Integer(6))
>>> U36.equals(U36.dual())
True

A number of special matroids are collected under a catalog submenu. To see which, type matroids.catalog.<tab> as above:

sage: F7 = matroids.catalog.Fano()
sage: len(F7.nonspanning_circuits())
7

>>> from sage.all import *
>>> F7 = matroids.catalog.Fano()
>>> len(F7.nonspanning_circuits())
7

Constructing matroids#

To define your own matroid, use the function Matroid(). This function attempts to interpret its arguments to create an appropriate matroid. The input arguments are documented in detail below.

EXAMPLES:

sage: A = Matrix(GF(2), [[1, 0, 0, 0, 1, 1, 1],
....:                    [0, 1, 0, 1, 0, 1, 1],
....:                    [0, 0, 1, 1, 1, 0, 1]])
sage: M = Matroid(A)
sage: M.is_isomorphic(matroids.catalog.Fano())
True

sage: M = Matroid(graphs.PetersenGraph())                                            # needs sage.graphs
sage: M.rank()                                                                       # needs sage.graphs
9

>>> from sage.all import *
>>> A = Matrix(GF(Integer(2)), [[Integer(1), Integer(0), Integer(0), Integer(0), Integer(1), Integer(1), Integer(1)],
...                    [Integer(0), Integer(1), Integer(0), Integer(1), Integer(0), Integer(1), Integer(1)],
...                    [Integer(0), Integer(0), Integer(1), Integer(1), Integer(1), Integer(0), Integer(1)]])
>>> M = Matroid(A)
>>> M.is_isomorphic(matroids.catalog.Fano())
True

>>> M = Matroid(graphs.PetersenGraph())                                            # needs sage.graphs
>>> M.rank()                                                                       # needs sage.graphs
9

AUTHORS:

  • Rudi Pendavingh, Michael Welsh, Stefan van Zwam (2013-04-01): initial version

Functions#

sage.matroids.constructor.Matroid(groundset=None, data=None, **kwds)[source]#

Construct a matroid.

Matroids are combinatorial structures that capture the abstract properties of (linear/algebraic/…) dependence. Formally, a matroid is a pair \(M = (E, I)\) of a finite set \(E\), the groundset, and a collection of subsets \(I\), the independent sets, subject to the following axioms:

  • \(I\) contains the empty set

  • If \(X\) is a set in \(I\), then each subset of \(X\) is in \(I\)

  • If two subsets \(X\), \(Y\) are in \(I\), and \(|X| > |Y|\), then there exists \(x \in X - Y\) such that \(Y + \{x\}\) is in \(I\).

See the Wikipedia article on matroids for more theory and examples. Matroids can be obtained from many types of mathematical structures, and Sage supports a number of them.

There are two main entry points to Sage’s matroid functionality. For built-in matroids, do the following:

  • Within a Sage session, type “matroids.” (Do not press Enter, and do not forget the final period “.”)

  • Hit Tab.

You will see a list of methods which will construct matroids. For example:

sage: F7 = matroids.catalog.Fano()
sage: len(F7.nonspanning_circuits())
7

>>> from sage.all import *
>>> F7 = matroids.catalog.Fano()
>>> len(F7.nonspanning_circuits())
7

or:

sage: U36 = matroids.Uniform(3, 6)
sage: U36.equals(U36.dual())
True

>>> from sage.all import *
>>> U36 = matroids.Uniform(Integer(3), Integer(6))
>>> U36.equals(U36.dual())
True

To define your own matroid, use the function Matroid(). This function attempts to interpret its arguments to create an appropriate matroid. The following named arguments are supported:

INPUT:

  • groundset – (optional) If provided, the groundset of the matroid. Otherwise, the function attempts to determine a groundset from the data.

Exactly one of the following inputs must be given (where data must be a positional argument and anything else must be a keyword argument):

  • data – a graph or a matrix or a RevLex-Index string or a list of independent sets containing all bases or a matroid.

  • bases – The list of bases (maximal independent sets) of the matroid.

  • independent_sets – The list of independent sets of the matroid.

  • circuits – The list of circuits of the matroid.

  • nonspanning_circuits – The list of nonspanning circuits of the matroid.

  • flats – The dictionary, list, or lattice of flats of the matroid.

  • graph – A graph, whose edges form the elements of the matroid.

  • matrix – A matrix representation of the matroid.

  • reduced_matrix – A reduced representation of the matroid: if reduced_matrix = A then the matroid is represented by \([I\ \ A]\) where \(I\) is an appropriately sized identity matrix.

  • morphism – A morphism representation of the matroid.

  • reduced_morphism – A reduced morphism representation of the matroid.

  • rank_function – A function that computes the rank of each subset. Can only be provided together with a groundset.

  • circuit_closures – Either a list of tuples (k, C) with C the closure of a circuit, and k the rank of C, or a dictionary D with D[k] the set of closures of rank-k circuits.

  • revlex – the encoding as a string of 0 and * symbols. Used by [Mat2012] and explained in [MMIB2012].

  • matroid – An object that is already a matroid. Useful only with the regular option.

Further options:

  • regular – (default: False) boolean. If True, output a RegularMatroid instance such that, if the input defines a valid regular matroid, then the output represents this matroid. Note that this option can be combined with any type of input.

  • ring – any ring. If provided, and the input is a matrix or reduced_matrix, output will be a linear matroid over the ring or field ring.

  • field – any field. Same as ring, but only fields are allowed.

  • check – (default: True) boolean. If True and regular is true, the output is checked to make sure it is a valid regular matroid.

Warning

Except for regular matroids, the input is not checked for validity. If your data does not correspond to an actual matroid, the behavior of the methods is undefined and may cause strange errors. To ensure you have a matroid, run M.is_valid().

Note

The Matroid() method will return instances of type BasisMatroid, CircuitsMatroid, FlatsMatroid, CircuitClosuresMatroid, LinearMatroid, BinaryMatroid, TernaryMatroid, QuaternaryMatroid, RegularMatroid, or RankMatroid. To import these classes (and other useful functions) directly into Sage’s main namespace, type:

sage: from sage.matroids.advanced import *

>>> from sage.all import *
>>> from sage.matroids.advanced import *

See sage.matroids.advanced.

EXAMPLES:

Note that in these examples we will often use the fact that strings are iterable in these examples. So we type 'abcd' to denote the list ['a', 'b', 'c', 'd'].

  1. List of bases:

    All of the following inputs are allowed, and equivalent:

    sage: M1 = Matroid(groundset='abcd', bases=['ab', 'ac', 'ad',
....:                                       'bc', 'bd', 'cd'])
sage: M2 = Matroid(bases=['ab', 'ac', 'ad', 'bc', 'bd', 'cd'])
sage: M3 = Matroid(['ab', 'ac', 'ad', 'bc', 'bd', 'cd'])
sage: M4 = Matroid('abcd', ['ab', 'ac', 'ad', 'bc', 'bd', 'cd'])
sage: M5 = Matroid('abcd', bases=[['a', 'b'], ['a', 'c'],
....:                             ['a', 'd'], ['b', 'c'],
....:                             ['b', 'd'], ['c', 'd']])
sage: M1 == M2
True
sage: M1 == M3
True
sage: M1 == M4
True
sage: M1 == M5
True

    >>> from sage.all import *
>>> M1 = Matroid(groundset='abcd', bases=['ab', 'ac', 'ad',
...                                       'bc', 'bd', 'cd'])
>>> M2 = Matroid(bases=['ab', 'ac', 'ad', 'bc', 'bd', 'cd'])
>>> M3 = Matroid(['ab', 'ac', 'ad', 'bc', 'bd', 'cd'])
>>> M4 = Matroid('abcd', ['ab', 'ac', 'ad', 'bc', 'bd', 'cd'])
>>> M5 = Matroid('abcd', bases=[['a', 'b'], ['a', 'c'],
...                             ['a', 'd'], ['b', 'c'],
...                             ['b', 'd'], ['c', 'd']])
>>> M1 == M2
True
>>> M1 == M3
True
>>> M1 == M4
True
>>> M1 == M5
True

    We do not check if the provided input forms an actual matroid:

    sage: M1 = Matroid(groundset='abcd', bases=['ab', 'cd'])
sage: M1.full_rank()
2
sage: M1.is_valid()
False

    >>> from sage.all import *
>>> M1 = Matroid(groundset='abcd', bases=['ab', 'cd'])
>>> M1.full_rank()
2
>>> M1.is_valid()
False

    Bases may be repeated:

    sage: M1 = Matroid(['ab', 'ac'])
sage: M2 = Matroid(['ab', 'ac', 'ab'])
sage: M1 == M2
True

    >>> from sage.all import *
>>> M1 = Matroid(['ab', 'ac'])
>>> M2 = Matroid(['ab', 'ac', 'ab'])
>>> M1 == M2
True

  2. List of independent sets:

    sage: M1 = Matroid(groundset='abcd',
....:              independent_sets=['', 'a', 'b', 'c', 'd', 'ab',
....:                               'ac', 'ad', 'bc', 'bd', 'cd'])

    >>> from sage.all import *
>>> M1 = Matroid(groundset='abcd',
...              independent_sets=['', 'a', 'b', 'c', 'd', 'ab',
...                               'ac', 'ad', 'bc', 'bd', 'cd'])

    We only require that the list of independent sets contains each basis of the matroid; omissions of smaller independent sets and repetitions are allowed:

    sage: M1 = Matroid(bases=['ab', 'ac'])
sage: M2 = Matroid(independent_sets=['a', 'ab', 'b', 'ab', 'a',
....:                                'b', 'ac'])
sage: M1 == M2
True

    >>> from sage.all import *
>>> M1 = Matroid(bases=['ab', 'ac'])
>>> M2 = Matroid(independent_sets=['a', 'ab', 'b', 'ab', 'a',
...                                'b', 'ac'])
>>> M1 == M2
True

  3. List of circuits:

    sage: M1 = Matroid(groundset='abc', circuits=['bc'])

    >>> from sage.all import *
>>> M1 = Matroid(groundset='abc', circuits=['bc'])

    A matroid specified by a list of circuits gets converted to a CircuitsMatroid internally:

    sage: from sage.matroids.circuits_matroid import CircuitsMatroid
sage: M2 = CircuitsMatroid(Matroid(bases=['ab', 'ac']))
sage: M1 == M2
True

sage: M = Matroid(groundset='abcd', circuits=['abc', 'abd', 'acd',
....:                                         'bcd'])
sage: type(M)
<class 'sage.matroids.circuits_matroid.CircuitsMatroid'>

    >>> from sage.all import *
>>> from sage.matroids.circuits_matroid import CircuitsMatroid
>>> M2 = CircuitsMatroid(Matroid(bases=['ab', 'ac']))
>>> M1 == M2
True

>>> M = Matroid(groundset='abcd', circuits=['abc', 'abd', 'acd',
...                                         'bcd'])
>>> type(M)
<class 'sage.matroids.circuits_matroid.CircuitsMatroid'>

    Strange things can happen if the input does not satisfy the circuit axioms, and these can be caught by the is_valid() method. So please check that your input makes sense!

    sage: M = Matroid('abcd', circuits=['ab', 'acd'])
sage: M.is_valid()
False

    >>> from sage.all import *
>>> M = Matroid('abcd', circuits=['ab', 'acd'])
>>> M.is_valid()
False

  4. Flats:

    Given a dictionary of flats indexed by their rank, we get a FlatsMatroid:

    sage: M = Matroid(flats={0: [''], 1: ['a', 'b'], 2: ['ab']})
sage: M.is_isomorphic(matroids.Uniform(2, 2)) and M.is_valid()
True
sage: type(M)
<class 'sage.matroids.flats_matroid.FlatsMatroid'>

    >>> from sage.all import *
>>> M = Matroid(flats={Integer(0): [''], Integer(1): ['a', 'b'], Integer(2): ['ab']})
>>> M.is_isomorphic(matroids.Uniform(Integer(2), Integer(2))) and M.is_valid()
True
>>> type(M)
<class 'sage.matroids.flats_matroid.FlatsMatroid'>

    If instead we simply provide a list of flats, then the class computes and stores the lattice of flats upon definition. This can be time-consuming, but after it’s done we benefit from some faster methods (e.g., is_valid()):

    sage: M = Matroid(flats=['', 'a', 'b', 'ab'])
sage: for i in range(M.rank() + 1):  # print flats by rank
....:     print(f'{i}: {sorted([sorted(F) for F in M.flats(i)], key=str)}')
0: [[]]
1: [['a'], ['b']]
2: [['a', 'b']]
sage: M.is_valid()
True
sage: type(M)
<class 'sage.matroids.flats_matroid.FlatsMatroid'>

    >>> from sage.all import *
>>> M = Matroid(flats=['', 'a', 'b', 'ab'])
>>> for i in range(M.rank() + Integer(1)):  # print flats by rank
...     print(f'{i}: {sorted([sorted(F) for F in M.flats(i)], key=str)}')
0: [[]]
1: [['a'], ['b']]
2: [['a', 'b']]
>>> M.is_valid()
True
>>> type(M)
<class 'sage.matroids.flats_matroid.FlatsMatroid'>

    Finally, we can also directly provide a lattice of flats:

    sage: from sage.combinat.posets.lattices import LatticePoset
sage: flats = [frozenset(F) for F in powerset('ab')]
sage: L_M = LatticePoset((flats, lambda x, y: x < y))
sage: M = Matroid(L_M)
sage: M.is_isomorphic(matroids.Uniform(2, 2)) and M.is_valid()
True
sage: type(M)
<class 'sage.matroids.flats_matroid.FlatsMatroid'>

    >>> from sage.all import *
>>> from sage.combinat.posets.lattices import LatticePoset
>>> flats = [frozenset(F) for F in powerset('ab')]
>>> L_M = LatticePoset((flats, lambda x, y: x < y))
>>> M = Matroid(L_M)
>>> M.is_isomorphic(matroids.Uniform(Integer(2), Integer(2))) and M.is_valid()
True
>>> type(M)
<class 'sage.matroids.flats_matroid.FlatsMatroid'>

  5. Graph:

    Sage has great support for graphs, see sage.graphs.graph.

    sage: G = graphs.PetersenGraph()                                            # needs sage.graphs
sage: Matroid(G)                                                            # needs sage.graphs
Graphic matroid of rank 9 on 15 elements

    >>> from sage.all import *
>>> G = graphs.PetersenGraph()                                            # needs sage.graphs
>>> Matroid(G)                                                            # needs sage.graphs
Graphic matroid of rank 9 on 15 elements

    If each edge has a unique label, then those are used as the ground set labels:

    sage: G = Graph([(0, 1, 'a'), (0, 2, 'b'), (1, 2, 'c')])                    # needs sage.graphs
sage: M = Matroid(G)                                                        # needs sage.graphs
sage: sorted(M.groundset())                                                 # needs sage.graphs
['a', 'b', 'c']

    >>> from sage.all import *
>>> G = Graph([(Integer(0), Integer(1), 'a'), (Integer(0), Integer(2), 'b'), (Integer(1), Integer(2), 'c')])                    # needs sage.graphs
>>> M = Matroid(G)                                                        # needs sage.graphs
>>> sorted(M.groundset())                                                 # needs sage.graphs
['a', 'b', 'c']

    If there are parallel edges, then integers are used for the ground set. If there are no edges in parallel, and is not a complete list of labels, or the labels are not unique, then vertex tuples are used:

    sage: # needs sage.graphs
sage: G = Graph([(0, 1, 'a'), (0, 2, 'b'), (1, 2, 'b')])
sage: M = Matroid(G)
sage: sorted(M.groundset())
[(0, 1), (0, 2), (1, 2)]
sage: H = Graph([(0, 1, 'a'), (0, 2, 'b'), (1, 2, 'b'), (1, 2, 'c')],
....:           multiedges=True)
sage: N = Matroid(H)
sage: sorted(N.groundset())
[0, 1, 2, 3]

    >>> from sage.all import *
>>> # needs sage.graphs
>>> G = Graph([(Integer(0), Integer(1), 'a'), (Integer(0), Integer(2), 'b'), (Integer(1), Integer(2), 'b')])
>>> M = Matroid(G)
>>> sorted(M.groundset())
[(0, 1), (0, 2), (1, 2)]
>>> H = Graph([(Integer(0), Integer(1), 'a'), (Integer(0), Integer(2), 'b'), (Integer(1), Integer(2), 'b'), (Integer(1), Integer(2), 'c')],
...           multiedges=True)
>>> N = Matroid(H)
>>> sorted(N.groundset())
[0, 1, 2, 3]

    The GraphicMatroid object forces its graph to be connected. If a disconnected graph is used as input, it will connect the components:

    sage: # needs sage.graphs
sage: G1 = graphs.CycleGraph(3); G2 = graphs.DiamondGraph()
sage: G = G1.disjoint_union(G2)
sage: M = Matroid(G); M
Graphic matroid of rank 5 on 8 elements
sage: M.graph()
Looped multi-graph on 6 vertices
sage: M.graph().is_connected()
True
sage: M.is_connected()
False

    >>> from sage.all import *
>>> # needs sage.graphs
>>> G1 = graphs.CycleGraph(Integer(3)); G2 = graphs.DiamondGraph()
>>> G = G1.disjoint_union(G2)
>>> M = Matroid(G); M
Graphic matroid of rank 5 on 8 elements
>>> M.graph()
Looped multi-graph on 6 vertices
>>> M.graph().is_connected()
True
>>> M.is_connected()
False

    If the keyword regular is set to True, the output will instead be an instance of RegularMatroid.

    sage: G = Graph([(0, 1), (0, 2), (1, 2)])                                   # needs sage.graphs
sage: M = Matroid(G, regular=True); M                                       # needs sage.graphs
Regular matroid of rank 2 on 3 elements with 3 bases

    >>> from sage.all import *
>>> G = Graph([(Integer(0), Integer(1)), (Integer(0), Integer(2)), (Integer(1), Integer(2))])                                   # needs sage.graphs
>>> M = Matroid(G, regular=True); M                                       # needs sage.graphs
Regular matroid of rank 2 on 3 elements with 3 bases

    Note: if a groundset is specified, we assume it is in the same order as G.edge_iterator() provides:

    sage: G = Graph([(0, 1), (0, 2), (0, 2), (1, 2)], multiedges=True)          # needs sage.graphs
sage: M = Matroid('abcd', G)                                                # needs sage.graphs
sage: M.rank(['b', 'c'])                                                    # needs sage.graphs
1

    >>> from sage.all import *
>>> G = Graph([(Integer(0), Integer(1)), (Integer(0), Integer(2)), (Integer(0), Integer(2)), (Integer(1), Integer(2))], multiedges=True)          # needs sage.graphs
>>> M = Matroid('abcd', G)                                                # needs sage.graphs
>>> M.rank(['b', 'c'])                                                    # needs sage.graphs
1

    As before, if no edge labels are present and the graph is simple, we use the tuples (i, j) of endpoints. If that fails, we simply use a list [0..m-1]

    sage: G = Graph([(0, 1), (0, 2), (1, 2)])                                   # needs sage.graphs
sage: M = Matroid(G, regular=True)                                          # needs sage.graphs
sage: sorted(M.groundset())                                                 # needs sage.graphs
[(0, 1), (0, 2), (1, 2)]

sage: G = Graph([(0, 1), (0, 2), (0, 2), (1, 2)], multiedges=True)          # needs sage.graphs
sage: M = Matroid(G, regular=True)                                          # needs sage.graphs
sage: sorted(M.groundset())                                                 # needs sage.graphs
[0, 1, 2, 3]

    >>> from sage.all import *
>>> G = Graph([(Integer(0), Integer(1)), (Integer(0), Integer(2)), (Integer(1), Integer(2))])                                   # needs sage.graphs
>>> M = Matroid(G, regular=True)                                          # needs sage.graphs
>>> sorted(M.groundset())                                                 # needs sage.graphs
[(0, 1), (0, 2), (1, 2)]

>>> G = Graph([(Integer(0), Integer(1)), (Integer(0), Integer(2)), (Integer(0), Integer(2)), (Integer(1), Integer(2))], multiedges=True)          # needs sage.graphs
>>> M = Matroid(G, regular=True)                                          # needs sage.graphs
>>> sorted(M.groundset())                                                 # needs sage.graphs
[0, 1, 2, 3]

    When the graph keyword is used, a variety of inputs can be converted to a graph automatically. The following uses a graph6 string (see the Graph method’s documentation):

    sage: Matroid(graph=':I`AKGsaOs`cI]Gb~')                                    # needs sage.graphs
Graphic matroid of rank 9 on 17 elements

    >>> from sage.all import *
>>> Matroid(graph=':I`AKGsaOs`cI]Gb~')                                    # needs sage.graphs
Graphic matroid of rank 9 on 17 elements

    However, this method is no more clever than Graph():

    sage: Matroid(graph=41/2)                                                   # needs sage.graphs
Traceback (most recent call last):
...
ValueError: This input cannot be turned into a graph

    >>> from sage.all import *
>>> Matroid(graph=Integer(41)/Integer(2))                                                   # needs sage.graphs
Traceback (most recent call last):
...
ValueError: This input cannot be turned into a graph

  6. Matrix:

    The basic input is a Sage matrix:

    sage: A = Matrix(GF(2), [[1, 0, 0, 1, 1, 0],
....:                    [0, 1, 0, 1, 0, 1],
....:                    [0, 0, 1, 0, 1, 1]])
sage: M = Matroid(matrix=A)
sage: M.is_isomorphic(matroids.CompleteGraphic(4))                          # needs sage.graphs
True

    >>> from sage.all import *
>>> A = Matrix(GF(Integer(2)), [[Integer(1), Integer(0), Integer(0), Integer(1), Integer(1), Integer(0)],
...                    [Integer(0), Integer(1), Integer(0), Integer(1), Integer(0), Integer(1)],
...                    [Integer(0), Integer(0), Integer(1), Integer(0), Integer(1), Integer(1)]])
>>> M = Matroid(matrix=A)
>>> M.is_isomorphic(matroids.CompleteGraphic(Integer(4)))                          # needs sage.graphs
True

    Various shortcuts are possible:

    sage: M1 = Matroid(matrix=[[1, 0, 0, 1, 1, 0],
....:                      [0, 1, 0, 1, 0, 1],
....:                      [0, 0, 1, 0, 1, 1]], ring=GF(2))
sage: M2 = Matroid(reduced_matrix=[[1, 1, 0],
....:                              [1, 0, 1],
....:                              [0, 1, 1]], ring=GF(2))
sage: M3 = Matroid(groundset=[0, 1, 2, 3, 4, 5],
....:              matrix=[[1, 1, 0], [1, 0, 1], [0, 1, 1]],
....:              ring=GF(2))
sage: A = Matrix(GF(2), [[1, 1, 0], [1, 0, 1], [0, 1, 1]])
sage: M4 = Matroid([0, 1, 2, 3, 4, 5], A)
sage: M1 == M2
True
sage: M1 == M3
True
sage: M1 == M4
True

    >>> from sage.all import *
>>> M1 = Matroid(matrix=[[Integer(1), Integer(0), Integer(0), Integer(1), Integer(1), Integer(0)],
...                      [Integer(0), Integer(1), Integer(0), Integer(1), Integer(0), Integer(1)],
...                      [Integer(0), Integer(0), Integer(1), Integer(0), Integer(1), Integer(1)]], ring=GF(Integer(2)))
>>> M2 = Matroid(reduced_matrix=[[Integer(1), Integer(1), Integer(0)],
...                              [Integer(1), Integer(0), Integer(1)],
...                              [Integer(0), Integer(1), Integer(1)]], ring=GF(Integer(2)))
>>> M3 = Matroid(groundset=[Integer(0), Integer(1), Integer(2), Integer(3), Integer(4), Integer(5)],
...              matrix=[[Integer(1), Integer(1), Integer(0)], [Integer(1), Integer(0), Integer(1)], [Integer(0), Integer(1), Integer(1)]],
...              ring=GF(Integer(2)))
>>> A = Matrix(GF(Integer(2)), [[Integer(1), Integer(1), Integer(0)], [Integer(1), Integer(0), Integer(1)], [Integer(0), Integer(1), Integer(1)]])
>>> M4 = Matroid([Integer(0), Integer(1), Integer(2), Integer(3), Integer(4), Integer(5)], A)
>>> M1 == M2
True
>>> M1 == M3
True
>>> M1 == M4
True

    However, with unnamed arguments the input has to be a Matrix instance, or the function will try to interpret it as a set of bases:

    sage: Matroid([0, 1, 2], [[1, 0, 1], [0, 1, 1]])
Traceback (most recent call last):
...
ValueError: basis has wrong cardinality

    >>> from sage.all import *
>>> Matroid([Integer(0), Integer(1), Integer(2)], [[Integer(1), Integer(0), Integer(1)], [Integer(0), Integer(1), Integer(1)]])
Traceback (most recent call last):
...
ValueError: basis has wrong cardinality

    If the groundset size equals number of rows plus number of columns, an identity matrix is prepended. Otherwise the groundset size must equal the number of columns:

    sage: A = Matrix(GF(2), [[1, 1, 0], [1, 0, 1], [0, 1, 1]])
sage: M = Matroid([0, 1, 2], A)
sage: N = Matroid([0, 1, 2, 3, 4, 5], A)
sage: M.rank()
2
sage: N.rank()
3

    >>> from sage.all import *
>>> A = Matrix(GF(Integer(2)), [[Integer(1), Integer(1), Integer(0)], [Integer(1), Integer(0), Integer(1)], [Integer(0), Integer(1), Integer(1)]])
>>> M = Matroid([Integer(0), Integer(1), Integer(2)], A)
>>> N = Matroid([Integer(0), Integer(1), Integer(2), Integer(3), Integer(4), Integer(5)], A)
>>> M.rank()
2
>>> N.rank()
3

    We automatically create an optimized subclass, if available:

    sage: Matroid([0, 1, 2, 3, 4, 5],
....:         matrix=[[1, 1, 0], [1, 0, 1], [0, 1, 1]],
....:         field=GF(2))
Binary matroid of rank 3 on 6 elements, type (2, 7)
sage: Matroid([0, 1, 2, 3, 4, 5],
....:         matrix=[[1, 1, 0], [1, 0, 1], [0, 1, 1]],
....:         field=GF(3))
Ternary matroid of rank 3 on 6 elements, type 0-
sage: Matroid([0, 1, 2, 3, 4, 5],                                           # needs sage.rings.finite_rings
....:         matrix=[[1, 1, 0], [1, 0, 1], [0, 1, 1]],
....:         field=GF(4, 'x'))
Quaternary matroid of rank 3 on 6 elements
sage: Matroid([0, 1, 2, 3, 4, 5],                                           # needs sage.graphs
....:         matrix=[[1, 1, 0], [1, 0, 1], [0, 1, 1]],
....:         field=GF(2), regular=True)
Regular matroid of rank 3 on 6 elements with 16 bases

    >>> from sage.all import *
>>> Matroid([Integer(0), Integer(1), Integer(2), Integer(3), Integer(4), Integer(5)],
...         matrix=[[Integer(1), Integer(1), Integer(0)], [Integer(1), Integer(0), Integer(1)], [Integer(0), Integer(1), Integer(1)]],
...         field=GF(Integer(2)))
Binary matroid of rank 3 on 6 elements, type (2, 7)
>>> Matroid([Integer(0), Integer(1), Integer(2), Integer(3), Integer(4), Integer(5)],
...         matrix=[[Integer(1), Integer(1), Integer(0)], [Integer(1), Integer(0), Integer(1)], [Integer(0), Integer(1), Integer(1)]],
...         field=GF(Integer(3)))
Ternary matroid of rank 3 on 6 elements, type 0-
>>> Matroid([Integer(0), Integer(1), Integer(2), Integer(3), Integer(4), Integer(5)],                                           # needs sage.rings.finite_rings
...         matrix=[[Integer(1), Integer(1), Integer(0)], [Integer(1), Integer(0), Integer(1)], [Integer(0), Integer(1), Integer(1)]],
...         field=GF(Integer(4), 'x'))
Quaternary matroid of rank 3 on 6 elements
>>> Matroid([Integer(0), Integer(1), Integer(2), Integer(3), Integer(4), Integer(5)],                                           # needs sage.graphs
...         matrix=[[Integer(1), Integer(1), Integer(0)], [Integer(1), Integer(0), Integer(1)], [Integer(0), Integer(1), Integer(1)]],
...         field=GF(Integer(2)), regular=True)
Regular matroid of rank 3 on 6 elements with 16 bases

    Otherwise the generic LinearMatroid class is used:

    sage: Matroid([0, 1, 2, 3, 4, 5],
....:         matrix=[[1, 1, 0], [1, 0, 1], [0, 1, 1]],
....:         field=GF(83))
Linear matroid of rank 3 on 6 elements represented over the Finite
Field of size 83

    >>> from sage.all import *
>>> Matroid([Integer(0), Integer(1), Integer(2), Integer(3), Integer(4), Integer(5)],
...         matrix=[[Integer(1), Integer(1), Integer(0)], [Integer(1), Integer(0), Integer(1)], [Integer(0), Integer(1), Integer(1)]],
...         field=GF(Integer(83)))
Linear matroid of rank 3 on 6 elements represented over the Finite
Field of size 83

    An integer matrix is automatically converted to a matrix over \(\QQ\). If you really want integers, you can specify the ring explicitly:

    sage: A = Matrix([[1, 1, 0], [1, 0, 1], [0, 1, -1]])
sage: A.base_ring()
Integer Ring
sage: M = Matroid([0, 1, 2, 3, 4, 5], A)
sage: M.base_ring()
Rational Field
sage: M = Matroid([0, 1, 2, 3, 4, 5], A, ring=ZZ)
sage: M.base_ring()
Integer Ring

    >>> from sage.all import *
>>> A = Matrix([[Integer(1), Integer(1), Integer(0)], [Integer(1), Integer(0), Integer(1)], [Integer(0), Integer(1), -Integer(1)]])
>>> A.base_ring()
Integer Ring
>>> M = Matroid([Integer(0), Integer(1), Integer(2), Integer(3), Integer(4), Integer(5)], A)
>>> M.base_ring()
Rational Field
>>> M = Matroid([Integer(0), Integer(1), Integer(2), Integer(3), Integer(4), Integer(5)], A, ring=ZZ)
>>> M.base_ring()
Integer Ring

    A morphism representation of a LinearMatroid can also be used as input:

    sage: M = matroids.catalog.Fano()
sage: A = M.representation(order=True); A
Generic morphism:
  From: Free module generated by {'a', 'b', 'c', 'd', 'e', 'f', 'g'} over
        Finite Field of size 2
  To:   Free module generated by {0, 1, 2} over Finite Field of size 2
sage: A._unicode_art_matrix()
  a b c d e f g
0⎛1 0 0 0 1 1 1⎞
1⎜0 1 0 1 0 1 1⎟
2⎝0 0 1 1 1 0 1⎠
sage: N = Matroid(A); N
Binary matroid of rank 3 on 7 elements, type (3, 0)
sage: N.groundset()
frozenset({'a', 'b', 'c', 'd', 'e', 'f', 'g'})
sage: M == N
True

    >>> from sage.all import *
>>> M = matroids.catalog.Fano()
>>> A = M.representation(order=True); A
Generic morphism:
  From: Free module generated by {'a', 'b', 'c', 'd', 'e', 'f', 'g'} over
        Finite Field of size 2
  To:   Free module generated by {0, 1, 2} over Finite Field of size 2
>>> A._unicode_art_matrix()
  a b c d e f g
0⎛1 0 0 0 1 1 1⎞
1⎜0 1 0 1 0 1 1⎟
2⎝0 0 1 1 1 0 1⎠
>>> N = Matroid(A); N
Binary matroid of rank 3 on 7 elements, type (3, 0)
>>> N.groundset()
frozenset({'a', 'b', 'c', 'd', 'e', 'f', 'g'})
>>> M == N
True

    The keywords morphism and reduced_morphism are also available:

    sage: M = matroids.catalog.RelaxedNonFano("abcdefg")
sage: A = M.representation(order=True, reduced=True); A
Generic morphism:
  From: Free module generated by {'d', 'e', 'f', 'g'} over
        Finite Field in w of size 2^2
  To:   Free module generated by {'a', 'b', 'c'} over
        Finite Field in w of size 2^2
sage: A._unicode_art_matrix()
  d e f g
a⎛1 1 0 1⎞
b⎜1 0 1 1⎟
c⎝0 1 w 1⎠
sage: N = Matroid(reduced_morphism=A); N
Quaternary matroid of rank 3 on 7 elements
sage: N.groundset()
frozenset({'a', 'b', 'c', 'd', 'e', 'f', 'g'})
sage: M == N
True

    >>> from sage.all import *
>>> M = matroids.catalog.RelaxedNonFano("abcdefg")
>>> A = M.representation(order=True, reduced=True); A
Generic morphism:
  From: Free module generated by {'d', 'e', 'f', 'g'} over
        Finite Field in w of size 2^2
  To:   Free module generated by {'a', 'b', 'c'} over
        Finite Field in w of size 2^2
>>> A._unicode_art_matrix()
  d e f g
a⎛1 1 0 1⎞
b⎜1 0 1 1⎟
c⎝0 1 w 1⎠
>>> N = Matroid(reduced_morphism=A); N
Quaternary matroid of rank 3 on 7 elements
>>> N.groundset()
frozenset({'a', 'b', 'c', 'd', 'e', 'f', 'g'})
>>> M == N
True

  7. Rank function:

    Any function mapping subsets to integers can be used as input:

    sage: def f(X):
....:     return min(len(X), 2)
sage: M = Matroid('abcd', rank_function=f)
sage: M
Matroid of rank 2 on 4 elements
sage: M.is_isomorphic(matroids.Uniform(2, 4))
True

    >>> from sage.all import *
>>> def f(X):
...     return min(len(X), Integer(2))
>>> M = Matroid('abcd', rank_function=f)
>>> M
Matroid of rank 2 on 4 elements
>>> M.is_isomorphic(matroids.Uniform(Integer(2), Integer(4)))
True

  8. Circuit closures:

    This is often a really concise way to specify a matroid. The usual way is a dictionary of lists:

    sage: M = Matroid(circuit_closures={3: ['edfg', 'acdg', 'bcfg',
....:     'cefh', 'afgh', 'abce', 'abdf', 'begh', 'bcdh', 'adeh'],
....:     4: ['abcdefgh']})
sage: M.equals(matroids.catalog.P8())
True

    >>> from sage.all import *
>>> M = Matroid(circuit_closures={Integer(3): ['edfg', 'acdg', 'bcfg',
...     'cefh', 'afgh', 'abce', 'abdf', 'begh', 'bcdh', 'adeh'],
...     Integer(4): ['abcdefgh']})
>>> M.equals(matroids.catalog.P8())
True

    You can also input tuples \((k, X)\) where \(X\) is the closure of a circuit, and \(k\) the rank of \(X\):

    sage: M = Matroid(circuit_closures=[(2, 'abd'), (3, 'abcdef'),
....:                               (2, 'bce')])
sage: M.equals(matroids.catalog.Q6())                                       # needs sage.rings.finite_rings
True

    >>> from sage.all import *
>>> M = Matroid(circuit_closures=[(Integer(2), 'abd'), (Integer(3), 'abcdef'),
...                               (Integer(2), 'bce')])
>>> M.equals(matroids.catalog.Q6())                                       # needs sage.rings.finite_rings
True

  9. RevLex-Index:

    This requires the groundset to be given and also needs a additional keyword argument rank to specify the rank of the matroid:

    sage: M = Matroid("abcdef", "000000******0**", rank=4); M
Matroid of rank 4 on 6 elements with 8 bases
sage: list(M.bases())
[frozenset({'a', 'b', 'd', 'f'}),
 frozenset({'a', 'c', 'd', 'f'}),
 frozenset({'b', 'c', 'd', 'f'}),
 frozenset({'a', 'b', 'e', 'f'}),
 frozenset({'a', 'c', 'e', 'f'}),
 frozenset({'b', 'c', 'e', 'f'}),
 frozenset({'b', 'd', 'e', 'f'}),
 frozenset({'c', 'd', 'e', 'f'})]

    >>> from sage.all import *
>>> M = Matroid("abcdef", "000000******0**", rank=Integer(4)); M
Matroid of rank 4 on 6 elements with 8 bases
>>> list(M.bases())
[frozenset({'a', 'b', 'd', 'f'}),
 frozenset({'a', 'c', 'd', 'f'}),
 frozenset({'b', 'c', 'd', 'f'}),
 frozenset({'a', 'b', 'e', 'f'}),
 frozenset({'a', 'c', 'e', 'f'}),
 frozenset({'b', 'c', 'e', 'f'}),
 frozenset({'b', 'd', 'e', 'f'}),
 frozenset({'c', 'd', 'e', 'f'})]

    Only the 0 symbols really matter, any symbol can be used instead of *:

    sage: Matroid(“abcdefg”, revlex=”0++++++++0++++0+++++0+–++—-+–++”, rank=4) Matroid of rank 4 on 7 elements with 31 bases

    It is checked that the input makes sense (but not that it defines a matroid):

    sage: Matroid("abcdef", "000000******0**")
Traceback (most recent call last):
...
TypeError: for RevLex-Index, the rank needs to be specified
sage: Matroid("abcdef", "000000******0**", rank=3)
Traceback (most recent call last):
...
ValueError: expected string of length 20 (6 choose 3), got 15
sage: M = Matroid("abcdef", "*0000000000000*", rank=4); M
Matroid of rank 4 on 6 elements with 2 bases
sage: M.is_valid()
False

    >>> from sage.all import *
>>> Matroid("abcdef", "000000******0**")
Traceback (most recent call last):
...
TypeError: for RevLex-Index, the rank needs to be specified
>>> Matroid("abcdef", "000000******0**", rank=Integer(3))
Traceback (most recent call last):
...
ValueError: expected string of length 20 (6 choose 3), got 15
>>> M = Matroid("abcdef", "*0000000000000*", rank=Integer(4)); M
Matroid of rank 4 on 6 elements with 2 bases
>>> M.is_valid()
False

  10. Matroid:

    Most of the time, the matroid itself is returned:

    sage: M = matroids.catalog.Fano()
sage: N = Matroid(M)
sage: N is M
True

    >>> from sage.all import *
>>> M = matroids.catalog.Fano()
>>> N = Matroid(M)
>>> N is M
True

    But it can be useful with the regular option:

    sage: M = Matroid(circuit_closures={2:['adb', 'bec', 'cfa',
....:                                  'def'], 3:['abcdef']})
sage: N = Matroid(M, regular=True); N                                       # needs sage.graphs
Regular matroid of rank 3 on 6 elements with 16 bases
sage: M == N                                                                # needs sage.graphs
False
sage: M.is_isomorphic(N)                                                    # needs sage.graphs
True
sage: Matrix(N)  # random                                                   # needs sage.graphs
[1 0 0 1 1 0]
[0 1 0 1 1 1]
[0 0 1 0 1 1]

    >>> from sage.all import *
>>> M = Matroid(circuit_closures={Integer(2):['adb', 'bec', 'cfa',
...                                  'def'], Integer(3):['abcdef']})
>>> N = Matroid(M, regular=True); N                                       # needs sage.graphs
Regular matroid of rank 3 on 6 elements with 16 bases
>>> M == N                                                                # needs sage.graphs
False
>>> M.is_isomorphic(N)                                                    # needs sage.graphs
True
>>> Matrix(N)  # random                                                   # needs sage.graphs
[1 0 0 1 1 0]
[0 1 0 1 1 1]
[0 0 1 0 1 1]

The regular option:

sage: M = Matroid(reduced_matrix=[[1, 1, 0],                                    # needs sage.graphs
....:                             [1, 0, 1],
....:                             [0, 1, 1]], regular=True); M
Regular matroid of rank 3 on 6 elements with 16 bases

sage: M.is_isomorphic(matroids.CompleteGraphic(4))                              # needs sage.graphs
True

>>> from sage.all import *
>>> M = Matroid(reduced_matrix=[[Integer(1), Integer(1), Integer(0)],                                    # needs sage.graphs
...                             [Integer(1), Integer(0), Integer(1)],
...                             [Integer(0), Integer(1), Integer(1)]], regular=True); M
Regular matroid of rank 3 on 6 elements with 16 bases

>>> M.is_isomorphic(matroids.CompleteGraphic(Integer(4)))                              # needs sage.graphs
True

By default we check if the resulting matroid is actually regular. To increase speed, this check can be skipped:

sage: M = matroids.catalog.Fano()
sage: N = Matroid(M, regular=True)                                              # needs sage.graphs
Traceback (most recent call last):
...
ValueError: input is not a valid regular matroid
sage: N = Matroid(M, regular=True, check=False); N                              # needs sage.graphs
Regular matroid of rank 3 on 7 elements with 32 bases

sage: N.is_valid()                                                              # needs sage.graphs
False

>>> from sage.all import *
>>> M = matroids.catalog.Fano()
>>> N = Matroid(M, regular=True)                                              # needs sage.graphs
Traceback (most recent call last):
...
ValueError: input is not a valid regular matroid
>>> N = Matroid(M, regular=True, check=False); N                              # needs sage.graphs
Regular matroid of rank 3 on 7 elements with 32 bases

>>> N.is_valid()                                                              # needs sage.graphs
False

Sometimes the output is regular, but represents a different matroid from the one you intended:

sage: M = Matroid(Matrix(GF(3), [[1, 0, 1, 1], [0, 1, 1, 2]]))
sage: N = Matroid(Matrix(GF(3), [[1, 0, 1, 1], [0, 1, 1, 2]]),                  # needs sage.graphs
....:             regular=True)
sage: N.is_valid()                                                              # needs sage.graphs
True
sage: N.is_isomorphic(M)                                                        # needs sage.graphs
False

>>> from sage.all import *
>>> M = Matroid(Matrix(GF(Integer(3)), [[Integer(1), Integer(0), Integer(1), Integer(1)], [Integer(0), Integer(1), Integer(1), Integer(2)]]))
>>> N = Matroid(Matrix(GF(Integer(3)), [[Integer(1), Integer(0), Integer(1), Integer(1)], [Integer(0), Integer(1), Integer(1), Integer(2)]]),                  # needs sage.graphs
...             regular=True)
>>> N.is_valid()                                                              # needs sage.graphs
True
>>> N.is_isomorphic(M)                                                        # needs sage.graphs
False