Linear matroids#
When \(A\) is an \(r\) times \(E\) matrix, the linear matroid \(M[A]\) has ground set \(E\) and, for independent sets, all \(F\) subset of \(E\) such that the columns of \(M[A]\) indexed by \(F\) are linearly independent.
Construction#
The recommended way to create a linear matroid is by using the
Matroid()
function, with a
representation matrix \(A\) as input. This function will intelligently choose
one of the dedicated classes BinaryMatroid
, TernaryMatroid
,
QuaternaryMatroid
, RegularMatroid
when appropriate. However,
invoking the classes directly is possible too. To get access to them, type:
sage: from sage.matroids.advanced import *
See also sage.matroids.advanced
. In both cases, it is possible to
provide a reduced matrix \(B\), to create the matroid induced by \(A = [ I B ]\):
sage: from sage.matroids.advanced import *
sage: A = Matrix(GF(2), [[1, 0, 0, 1, 1, 0, 1], [0, 1, 0, 1, 0, 1, 1],
....: [0, 0, 1, 0, 1, 1, 1]])
sage: B = Matrix(GF(2), [[1, 1, 0, 1], [1, 0, 1, 1], [0, 1, 1, 1]])
sage: M1 = Matroid(A)
sage: M2 = LinearMatroid(A)
sage: M3 = BinaryMatroid(A)
sage: M4 = Matroid(reduced_matrix=B)
sage: M5 = LinearMatroid(reduced_matrix=B)
sage: isinstance(M1, BinaryMatroid)
True
sage: M1.equals(M2)
True
sage: M1.equals(M3)
True
sage: M1 == M4
True
sage: M1.is_field_isomorphic(M5)
True
sage: M2 == M3 # comparing LinearMatroid and BinaryMatroid always yields False
False
Class methods#
The LinearMatroid
class and its derivatives inherit all methods from the
Matroid
and
BasisExchangeMatroid
classes.
See the documentation for these classes for an overview. In addition, the
following methods are available:

BinaryMatroid
has all of theLinearMatroid
ones, andTernaryMatroid
has all of theLinearMatroid
ones, andQuaternaryMatroid
has all of theLinearMatroid
ones, andRegularMatroid
has all of theLinearMatroid
ones, and
AUTHORS:
Rudi Pendavingh, Stefan van Zwam (20130401): initial version
Methods#
 class sage.matroids.linear_matroid.BinaryMatroid#
Bases:
LinearMatroid
Binary matroids.
A binary matroid is a linear matroid represented over the finite field with two elements. See
LinearMatroid
for a definition.The simplest way to create a
BinaryMatroid
is by giving only a matrix \(A\). Then, the groundset defaults torange(A.ncols())
. Any iterable object \(E\) can be given as a groundset. If \(E\) is a list, thenE[i]
will label the \(i\)th column of \(A\). Another possibility is to specify a reduced matrix \(B\), to create the matroid induced by \(A = [ I B ]\).INPUT:
matrix
– (default:None
) a matrix whose column vectors represent the matroid.reduced_matrix
– (default:None
) a matrix \(B\) such that \([I\ \ B]\) represents the matroid, where \(I\) is an identity matrix with the same number of rows as \(B\). Only one ofmatrix
andreduced_matrix
should be provided.groundset
– (default:None
) an iterable containing the element labels. When provided, must have the correct number of elements: the number of columns ofmatrix
or the number of rows plus the number of columns ofreduced_matrix
.ring
– (default:None
) ignored.keep_initial_representation
– (default:True
) decides whether or not an internal copy of the input matrix should be preserved. This can help to see the structure of the matroid (e.g. in the case of graphic matroids), and makes it easier to look at extensions. However, the input matrix may have redundant rows, and sometimes it is desirable to store only a rowreduced copy.basis
– (default:None
) When provided, this is an ordered subset ofgroundset
, such that the submatrix ofmatrix
indexed bybasis
is an identity matrix. In this case, no row reduction takes place in the initialization phase.
OUTPUT:
A
BinaryMatroid
instance based on the data above.Note
An indirect way to generate a binary matroid is through the
Matroid()
function. This is usually the preferred way, since it automatically chooses betweenBinaryMatroid
and other classes. For direct access to theBinaryMatroid
constructor, run:sage: from sage.matroids.advanced import *
EXAMPLES:
sage: A = Matrix(GF(2), 2, 4, [[1, 0, 1, 1], [0, 1, 1, 1]]) sage: M = Matroid(A) sage: M Binary matroid of rank 2 on 4 elements, type (0, 6) sage: sorted(M.groundset()) [0, 1, 2, 3] sage: Matrix(M) [1 0 1 1] [0 1 1 1] sage: M = Matroid(matrix=A, groundset='abcd') sage: sorted(M.groundset()) ['a', 'b', 'c', 'd'] sage: B = Matrix(GF(2), 2, 2, [[1, 1], [1, 1]]) sage: N = Matroid(reduced_matrix=B, groundset='abcd') sage: M == N True
 base_ring()#
Return the base ring of the matrix representing the matroid, in this case \(\GF{2}\).
EXAMPLES:
sage: M = matroids.catalog.Fano() sage: M.base_ring() Finite Field of size 2
 bicycle_dimension()#
Return the bicycle dimension of the binary matroid.
The bicycle dimension of a linear subspace \(V\) is \(\dim(V\cap V^\perp)\). The bicycle dimension of a matroid equals the bicycle dimension of its cocyclespace, and is an invariant for binary matroids. See [Pen2012], [GR2001] for more information.
OUTPUT:
Integer.
EXAMPLES:
sage: M = matroids.catalog.Fano() sage: M.bicycle_dimension() 3
 binary_matroid(randomized_tests=1, verify=True)#
Return a binary matroid representing
self
.INPUT:
randomized_tests
– Ignored.verify
– Ignored
OUTPUT:
A binary matroid.
ALGORITHM:
self
is a binary matroid, so just returnself
.See also
EXAMPLES:
sage: N = matroids.catalog.Fano() sage: N.binary_matroid() is N True
 brown_invariant()#
Return the value of Brown’s invariant for the binary matroid.
For a binary space \(V\), consider the sum \(B(V):=\sum_{v\in V} i^{v}\), where \(v\) denotes the number of nonzero entries of a binary vector \(v\). The value of the Tutte Polynomial in the point \((i, i)\) can be expressed in terms of \(B(V)\), see [Pen2012]. If \(v\) equals \(2\) modulo 4 for some \(v\in V\cap V^\perp\), then \(B(V)=0\). In this case, Browns invariant is not defined. Otherwise, \(B(V)=\sqrt{2}^k \exp(\sigma \pi i/4)\) for some integers \(k, \sigma\). In that case, \(k\) equals the bycycle dimension of \(V\), and Browns invariant for \(V\) is defined as \(\sigma\) modulo \(8\).
The Brown invariant of a binary matroid equals the Brown invariant of its cocyclespace.
OUTPUT:
Integer.
EXAMPLES:
sage: M = matroids.catalog.Fano() sage: M.brown_invariant() 0 sage: M = Matroid(Matrix(GF(2), 3, 8, [[1, 0, 0, 1, 1, 1, 1, 1], ....: [0, 1, 0, 1, 1, 0, 0, 0], ....: [0, 0, 1, 0, 0, 1, 1, 0]])) sage: M.brown_invariant() is None True
 characteristic()#
Return the characteristic of the base ring of the matrix representing the matroid, in this case \(2\).
EXAMPLES:
sage: M = matroids.catalog.Fano() sage: M.characteristic() 2
 is_binary(randomized_tests=1)#
Decide if
self
is a binary matroid.INPUT:
randomized_tests
– Ignored.
OUTPUT:
A Boolean.
ALGORITHM:
self
is a binary matroid, so just returnTrue
.See also
EXAMPLES:
sage: N = matroids.catalog.Fano() sage: N.is_binary() True
 is_graphic()#
Test if the binary matroid is graphic.
A matroid is graphic if there exists a graph whose edge set equals the groundset of the matroid, such that a subset of elements of the matroid is independent if and only if the corresponding subgraph is acyclic.
OUTPUT:
Boolean.
EXAMPLES:
sage: R10 = matroids.catalog.R10() sage: M = Matroid(ring=GF(2), reduced_matrix=R10.representation( ....: reduced=True, labels=False)) sage: M.is_graphic() False sage: K5 = Matroid(graphs.CompleteGraph(5), regular=True) # needs sage.graphs sage: M = Matroid(ring=GF(2), reduced_matrix=K5.representation( # needs sage.graphs sage.rings.finite_rings ....: reduced=True, labels=False)) sage: M.is_graphic() # needs sage.graphs sage.rings.finite_rings True sage: M.dual().is_graphic() # needs sage.graphs False
ALGORITHM:
In a recent paper, Geelen and Gerards [GG2012] reduced the problem to testing if a system of linear equations has a solution. While not the fastest method, and not necessarily constructive (in the presence of 2separations especially), it is easy to implement.
 is_valid()#
Test if the data obey the matroid axioms.
Since this is a linear matroid over the field \(\GF{2}\), this is always the case.
OUTPUT:
True
.EXAMPLES:
sage: M = Matroid(Matrix(GF(2), [[]])) sage: M.is_valid() True
 class sage.matroids.linear_matroid.LinearMatroid#
Bases:
BasisExchangeMatroid
Linear matroids.
When \(A\) is an \(r\) times \(E\) matrix, the linear matroid \(M[A]\) has ground set \(E\) and set of independent sets
\(I(A) =\{F \subseteq E :\) the columns of \(A\) indexed by \(F\) are linearly independent \(\}\)
The simplest way to create a LinearMatroid is by giving only a matrix \(A\). Then, the groundset defaults to
range(A.ncols())
. Any iterable objectE
can be given as a groundset. IfE
is a list, thenE[i]
will label the \(i\)th column of \(A\). Another possibility is to specify a reduced matrix \(B\), to create the matroid induced by \(A = [ I B ]\).INPUT:
matrix
– (default:None
) a matrix whose column vectors represent the matroid.reduced_matrix
– (default:None
) a matrix \(B\) such that \([I\ \ B]\) represents the matroid, where \(I\) is an identity matrix with the same number of rows as \(B\). Only one ofmatrix
andreduced_matrix
should be provided.groundset
– (default:None
) an iterable containing the element labels. When provided, must have the correct number of elements: the number of columns ofmatrix
or the number of rows plus the number of columns ofreduced_matrix
.ring
– (default:None
) the desired base ring of the matrix. If the base ring is different, an attempt will be made to create a new matrix with the correct base ring.keep_initial_representation
– (default:True
) decides whether or not an internal copy of the input matrix should be preserved. This can help to see the structure of the matroid (e.g. in the case of graphic matroids), and makes it easier to look at extensions. However, the input matrix may have redundant rows, and sometimes it is desirable to store only a rowreduced copy.
OUTPUT:
A
LinearMatroid
instance based on the data above.Note
The recommended way to generate a linear matroid is through the
Matroid()
function. It will automatically choose more optimized classes when present (currentlyBinaryMatroid
,TernaryMatroid
,QuaternaryMatroid
,RegularMatroid
). For direct access to theLinearMatroid
constructor, run:sage: from sage.matroids.advanced import *
EXAMPLES:
sage: from sage.matroids.advanced import * sage: A = Matrix(GF(3), 2, 4, [[1, 0, 1, 1], [0, 1, 1, 2]]) sage: M = LinearMatroid(A) sage: M Linear matroid of rank 2 on 4 elements represented over the Finite Field of size 3 sage: sorted(M.groundset()) [0, 1, 2, 3] sage: Matrix(M) [1 0 1 1] [0 1 1 2] sage: M = LinearMatroid(A, 'abcd') sage: sorted(M.groundset()) ['a', 'b', 'c', 'd'] sage: B = Matrix(GF(3), 2, 2, [[1, 1], [1, 2]]) sage: N = LinearMatroid(reduced_matrix=B, groundset='abcd') sage: M == N True
 base_ring()#
Return the base ring of the matrix representing the matroid.
EXAMPLES:
sage: M = Matroid(matrix=Matrix(GF(5), [[1, 0, 1, 1, 1], ....: [0, 1, 1, 2, 3]])) sage: M.base_ring() Finite Field of size 5
 characteristic()#
Return the characteristic of the base ring of the matrix representing the matroid.
EXAMPLES:
sage: M = Matroid(matrix=Matrix(GF(5), [[1, 0, 1, 1, 1], ....: [0, 1, 1, 2, 3]])) sage: M.characteristic() 5
 cross_ratio(F, a, b, c, d)#
Return the cross ratio of the four ordered points
a, b, c, d
after contracting a flatF
of codimension 2.Consider the following matrix with columns labeled by \(\{a, b, c, d\}\).
\[\begin{split}\begin{bmatrix} 1 & 0 & 1 & 1\\ 0 & 1 & x & 1 \end{bmatrix}\end{split}\]The cross ratio of the ordered tuple \((a, b, c, d)\) equals \(x\). This method looks at such minors where
F
is a flat to be contracted, and all remaining elements other thana, b, c, d
are deleted.INPUT:
F
– A flat of codimension 2a, b, c, d
– elements of the groundset
OUTPUT:
The cross ratio of the four points on the line obtained by contracting
F
.EXAMPLES:
sage: M = Matroid(Matrix(GF(7), [[1, 0, 0, 1, 1, 1], ....: [0, 1, 0, 1, 2, 4], ....: [0, 0, 1, 3, 2, 6]])) sage: M.cross_ratio([0], 1, 2, 3, 5) 4 sage: M = Matroid(ring=GF(7), matrix=[[1, 0, 1, 1], [0, 1, 1, 1]]) sage: M.cross_ratio(set(), 0, 1, 2, 3) Traceback (most recent call last): ... ValueError: points a, b, c, d do not form a 4point line in M/F
 cross_ratios(hyperlines=None)#
Return the set of cross ratios that occur in this linear matroid.
Consider the following matrix with columns labeled by \(\{a, b, c, d\}\).
\[\begin{split}\begin{matrix} 1 & 0 & 1 & 1\\ 0 & 1 & x & 1 \end{matrix}\end{split}\]The cross ratio of the ordered tuple \((a, b, c, d)\) equals \(x\). The set of all cross ratios of a matroid is the set of cross ratios of all such minors.
INPUT:
hyperlines
– (optional) a set of flats of the matroid, of rank \(r  2\), where \(r\) is the rank of the matroid. If not given, thenhyperlines
defaults to all such flats.
OUTPUT:
A list of all cross ratios of this linearly represented matroid that occur in rank2 minors that arise by contracting a flat
F
inhyperlines
(so by default, those are all cross ratios).See also
EXAMPLES:
sage: M = Matroid(Matrix(GF(7), [[1, 0, 0, 1, 1, 1], ....: [0, 1, 0, 1, 2, 4], ....: [0, 0, 1, 3, 2, 5]])) sage: sorted(M.cross_ratios()) [2, 3, 4, 5, 6] sage: M = Matroid(graphs.CompleteGraph(5), regular=True) # needs sage.graphs sage: M.cross_ratios() # needs sage.graphs set()
 dual()#
Return the dual of the matroid.
Let \(M\) be a matroid with ground set \(E\). If \(B\) is the set of bases of \(M\), then the set \(\{E  b : b \in B\}\) is the set of bases of another matroid, the dual of \(M\).
If the matroid is represented by \([I_1\ \ A]\), then the dual is represented by \([A^T\ \ I_2]\) for appropriately sized identity matrices \(I_1, I_2\).
OUTPUT:
The dual matroid.
EXAMPLES:
sage: A = Matrix(GF(7), [[1, 1, 0, 1], ....: [1, 0, 1, 1], ....: [0, 1, 1, 1]]) sage: B =  A.transpose() sage: Matroid(reduced_matrix=A).dual() == Matroid( ....: reduced_matrix=B, ....: groundset=[3, 4, 5, 6, 0, 1, 2]) True
 fundamental_cocycle(B, e)#
Return the fundamental cycle, relative to
B
, containing elemente
.This is the
fundamental cocircuit
together with an appropriate signing from the field, such that \(Av=0\), where \(A\) is a representation matrix of the dual, and \(v\) the vector corresponding to the output.INPUT:
B
– a basis of the matroide
– an element of the basis
OUTPUT:
A dictionary mapping elements of
M.fundamental_cocircuit(B, e)
to elements of the ring.See also
EXAMPLES:
sage: M = Matroid(Matrix(GF(7), [[1, 0, 1, 1], [0, 1, 1, 4]])) sage: v = M.fundamental_cocycle([0, 1], 0) sage: [v[0], v[2], v[3]] [1, 1, 1] sage: frozenset(v.keys()) == M.fundamental_cocircuit([0, 1], 0) True
 fundamental_cycle(B, e)#
Return the fundamental cycle, relative to
B
, containing elemente
.This is the
fundamental circuit
together with an appropriate signing from the field, such that \(Av=0\), where \(A\) is the representation matrix, and \(v\) the vector corresponding to the output.INPUT:
B
– a basis of the matroide
– an element outside the basis
OUTPUT:
A dictionary mapping elements of
M.fundamental_circuit(B, e)
to elements of the ring.See also
EXAMPLES:
sage: M = Matroid(Matrix(GF(7), [[1, 0, 1, 1], [0, 1, 1, 4]])) sage: v = M.fundamental_cycle([0, 1], 3) sage: [v[0], v[1], v[3]] [6, 3, 1] sage: frozenset(v.keys()) == M.fundamental_circuit([0, 1], 3) True
 has_field_minor(N)#
Check if
self
has a minor field isomorphic toN
.INPUT:
N
– A matroid.
OUTPUT:
Boolean.
See also
Todo
This important method can (and should) be optimized considerably. See [Hli2006] p.1219 for hints to that end.
EXAMPLES:
sage: M = matroids.Whirl(3) sage: matroids.catalog.Fano().has_field_minor(M) False sage: matroids.catalog.NonFano().has_field_minor(M) True
 has_line_minor(k, hyperlines=None, certificate=False)#
Test if the matroid has a \(U_{2, k}\)minor.
The matroid \(U_{2, k}\) is a matroid on \(k\) elements in which every subset of at most 2 elements is independent, and every subset of more than two elements is dependent.
The optional argument
hyperlines
restricts the search space: this method returnsTrue
if \(si(M/F)\) is isomorphic to \(U_{2, l}\) with \(l \geq k\) for some \(F\) inhyperlines
, andFalse
otherwise.INPUT:
k
– the length of the line minorhyperlines
– (default:None
) a set of flats of codimension 2. Defaults to the set of all flats of codimension 2.certificate
(default:False
); IfTrue
returnsTrue, F
, whereF
is a flat andself.minor(contractions=F)
has a \(U_{2,k}\) restriction orFalse, None
.
OUTPUT:
Boolean or tuple.
EXAMPLES:
sage: M = matroids.catalog.N1() sage: M.has_line_minor(4) True sage: M.has_line_minor(5) False sage: M.has_line_minor(k=4, hyperlines=[['a', 'b', 'c']]) False sage: M.has_line_minor(k=4, hyperlines=[['a', 'b', 'c'], ....: ['a', 'b', 'd' ]]) True sage: M.has_line_minor(4, certificate=True) (True, frozenset({'a', 'b', 'd'})) sage: M.has_line_minor(5, certificate=True) (False, None) sage: M.has_line_minor(k=4, hyperlines=[['a', 'b', 'c'], ....: ['a', 'b', 'd' ]], certificate=True) (True, frozenset({'a', 'b', 'd'}))
 is_field_equivalent(other)#
Test for matroid representation equality.
Two linear matroids \(M\) and \(N\) with representation matrices \(A\) and \(B\) are field equivalent if they have the same groundset, and the identity map between the groundsets is an isomorphism between the representations \(A\) and \(B\). That is, one can be turned into the other using only row operations and column scaling.
INPUT:
other
– A matroid.
OUTPUT:
Boolean.
EXAMPLES:
A
BinaryMatroid
andLinearMatroid
use different representations of the matroid internally, so `` == `` yieldsFalse
, even if the matroids are equal:sage: from sage.matroids.advanced import * sage: M = matroids.catalog.Fano() sage: M1 = LinearMatroid(Matrix(M), groundset=M.groundset_list()) sage: M2 = Matroid(groundset='abcdefg', ....: reduced_matrix=[[0, 1, 1, 1], ....: [1, 0, 1, 1], ....: [1, 1, 0, 1]], field=GF(2)) sage: M.equals(M1) True sage: M.equals(M2) True sage: M.is_field_equivalent(M1) True sage: M.is_field_equivalent(M2) True sage: M == M1 False sage: M == M2 True
LinearMatroid
instancesM
andN
satisfyM == N
if the representations are equivalent up to row operations and column scaling:sage: M1 = Matroid(groundset='abcd', ....: matrix=Matrix(GF(7), [[1, 0, 1, 1], [0, 1, 1, 2]])) sage: M2 = Matroid(groundset='abcd', ....: matrix=Matrix(GF(7), [[1, 0, 1, 1], [0, 1, 1, 3]])) sage: M3 = Matroid(groundset='abcd', ....: matrix=Matrix(GF(7), [[2, 6, 1, 0], [6, 1, 0, 1]])) sage: M1.equals(M2) True sage: M1.equals(M3) True sage: M1 == M2 False sage: M1 == M3 True sage: M1.is_field_equivalent(M2) False sage: M1.is_field_equivalent(M3) True sage: M1.is_field_equivalent(M1) True
 is_field_isomorphic(other)#
Test isomorphism between matroid representations.
Two represented matroids are field isomorphic if there is a bijection between their groundsets that induces a field equivalence between their representation matrices: the matrices are equal up to row operations and column scaling. This implies that the matroids are isomorphic, but the converse is false: two isomorphic matroids can be represented by matrices that are not field equivalent.
INPUT:
other
– A matroid.
OUTPUT:
Boolean.
EXAMPLES:
sage: M1 = matroids.Wheel(3) sage: M2 = Matroid(graphs.CompleteGraph(4), regular=True) # needs sage.graphs sage: M1.is_field_isomorphic(M2) # needs sage.graphs True sage: M3 = Matroid(bases=M1.bases()) sage: M1.is_field_isomorphic(M3) Traceback (most recent call last): ... AttributeError: 'sage.matroids.basis_matroid.BasisMatroid' object has no attribute 'base_ring'... sage: from sage.matroids.advanced import * sage: M4 = BinaryMatroid(Matrix(M1)) sage: M5 = LinearMatroid(reduced_matrix=Matrix(GF(2), [[1, 0, 1], ....: [1, 1, 0], [0, 1, 1]])) sage: M4.is_field_isomorphic(M5) True sage: M1 = Matroid(groundset=[0, 1, 2, 3], matrix=Matrix(GF(7), ....: [[1, 0, 1, 1], [0, 1, 1, 2]])) sage: M2 = Matroid(groundset=[0, 1, 2, 3], matrix=Matrix(GF(7), ....: [[1, 0, 1, 1], [0, 1, 2, 1]])) sage: M1.is_field_isomorphic(M2) True sage: M1.is_field_equivalent(M2) False
 is_field_isomorphism(other, morphism)#
Test if a provided morphism induces a bijection between represented matroids.
Two represented matroids are field isomorphic if the bijection
morphism
between them induces a field equivalence between their representation matrices: the matrices are equal up to row operations and column scaling. This implies that the matroids are isomorphic, but the converse is false: two isomorphic matroids can be represented by matrices that are not field equivalent.INPUT:
other
– A matroid.morphism
– A map from the groundset ofself
to the groundset ofother
. See documentation of theM.is_isomorphism()
method for more on what is accepted as input.
OUTPUT:
Boolean.
EXAMPLES:
sage: M = matroids.catalog.Fano() sage: N = matroids.catalog.NonFano() sage: N.is_field_isomorphism(M, {e:e for e in M.groundset()}) False sage: from sage.matroids.advanced import * sage: M = matroids.catalog.Fano().delete(['g']) sage: N = LinearMatroid(reduced_matrix=Matrix(GF(2), ....: [[1, 0, 1], [1, 1, 0], [0, 1, 1]])) sage: morphism = {'a':0, 'b':1, 'c': 2, 'd':4, 'e':5, 'f':3} sage: M.is_field_isomorphism(N, morphism) True sage: M1 = Matroid(groundset=[0, 1, 2, 3], matrix=Matrix(GF(7), ....: [[1, 0, 1, 1], [0, 1, 1, 2]])) sage: M2 = Matroid(groundset=[0, 1, 2, 3], matrix=Matrix(GF(7), ....: [[1, 0, 1, 1], [0, 1, 2, 1]])) sage: mf1 = {0:0, 1:1, 2:2, 3:3} sage: mf2 = {0:0, 1:1, 2:3, 3:2} sage: M1.is_field_isomorphism(M2, mf1) False sage: M1.is_field_isomorphism(M2, mf2) True
 is_valid()#
Test if the data represent an actual matroid.
Since this matroid is linear, we test the representation matrix.
OUTPUT:
True
if the matrix is over a field.True
if the matrix is over a ring and all cross ratios are invertible.False
otherwise.
Note
This function does NOT test if the cross ratios are contained in the appropriate set of fundamentals. To that end, use
M.cross_ratios().issubset(F)
where
F
is the set of fundamentals.See also
EXAMPLES:
sage: M = Matroid(ring=QQ, reduced_matrix=Matrix(ZZ, ....: [[1, 0, 1], [1, 1, 0], [0, 1, 1]])) sage: M.is_valid() True sage: from sage.matroids.advanced import * # LinearMatroid sage: M = LinearMatroid(ring=ZZ, reduced_matrix=Matrix(ZZ, ....: [[1, 0, 1], [1, 1, 0], [0, 1, 1]])) sage: M.is_valid() False
 linear_coextension(element, cochain=None, row=None)#
Return a linear coextension of this matroid.
A linear coextension of the represented matroid \(M\) by element \(e\) is a matroid represented by
\[\begin{split}\begin{bmatrix} A & 0\\ c & 1 \end{bmatrix},\end{split}\]where \(A\) is a representation matrix of \(M\), \(c\) is a new row, and the last column is labeled by \(e\).
This is the dual method of
M.linear_extension()
.INPUT:
element
– the name of the new element.row
– (default:None
) a row to be appended toself.representation()
. Can be any iterable.cochain
– (default:None
) a dictionary that maps elements of the ground set to elements of the base ring.
OUTPUT:
A linear matroid \(N = M([A 0; c 1])\), where \(A\) is a matrix such that the current matroid is \(M[A]\), and \(c\) is either given by
row
(relative toself.representation()
) or has nonzero entries given bycochain
.Note
The minus sign is to ensure this method commutes with dualizing. See the last example.
See also
EXAMPLES:
sage: M = Matroid(ring=GF(2), matrix=[[1, 1, 0, 1, 0, 0], ....: [1, 0, 1, 0, 1, 0], ....: [0, 1, 1, 0, 0, 1], ....: [0, 0, 0, 1, 1, 1]]) sage: M.linear_coextension(6, {0:1, 5: 1}).representation() [1 1 0 1 0 0 0] [1 0 1 0 1 0 0] [0 1 1 0 0 1 0] [0 0 0 1 1 1 0] [1 0 0 0 0 1 1] sage: M.linear_coextension(6, row=[0,1,1,1,0,1]).representation() [1 1 0 1 0 0 0] [1 0 1 0 1 0 0] [0 1 1 0 0 1 0] [0 0 0 1 1 1 0] [0 1 1 1 0 1 1]
Coextending commutes with dualizing:
sage: M = matroids.catalog.NonFano() sage: chain = {'a': 1, 'b': 1, 'f': 1} sage: M1 = M.linear_coextension('x', chain) sage: M2 = M.dual().linear_extension('x', chain) sage: M1 == M2.dual() True
 linear_coextension_cochains(F=None, cosimple=False, fundamentals=None)#
Create a list of cochains that determine the singleelement coextensions of this linear matroid representation.
A cochain is a dictionary, mapping elements from the groundset to elements of the base ring. If \(A\) represents the current matroid, then the coextension is given by \(N = M([A 0; c 1])\), with the entries of \(c\) given by the cochain. Note that the matroid does not change when row operations are carried out on \(A\).
INPUT:
F
– (default:self.groundset()
) a subset of the groundset.cosimple
– (default:False
) a boolean variable.fundamentals
– (default:None
) a set elements of the base ring.
OUTPUT:
A list of cochains, so each singleelement coextension of this linear matroid representation is given by one of these cochains.
If one or more of the above inputs is given, the list is restricted to chains
so that the support of each cochain lies in
F
, if givenso that the cochain does not generate a series extension or coloop, if
cosimple = True
so that in the coextension generated by this cochain, the cross ratios are restricted to
fundamentals
, if given.
EXAMPLES:
sage: M = Matroid(reduced_matrix=Matrix(GF(2), ....: [[1, 1, 0], [1, 0, 1], [0, 1, 1]])) sage: len(M.linear_coextension_cochains()) 8 sage: len(M.linear_coextension_cochains(F=[0, 1])) 4 sage: len(M.linear_coextension_cochains(F=[0, 1], cosimple=True)) 0 sage: M.linear_coextension_cochains(F=[3, 4, 5], cosimple=True) [{3: 1, 4: 1, 5: 1}] sage: N = Matroid(ring=QQ, ....: reduced_matrix=[[1, 1, 0], [1, 0, 1], [0, 1, 1]]) sage: N.linear_coextension_cochains(F=[0, 1], cosimple=True, ....: fundamentals=set([1, 1, 1/2, 2])) [{0: 2, 1: 1}, {0: 1, 1: 1}, {0: 1/2, 1: 1}]
 linear_coextensions(element=None, F=None, cosimple=False, fundamentals=None)#
Create a list of linear matroids represented by corankpreserving singleelement coextensions of this linear matroid representation.
INPUT:
element
– (default:None
) the name of the new element of the groundset.F
– (default:None
) a subset of the ground set.cosimple
– (default:False
) a boolean variable.fundamentals
– (default:None
) a set elements of the base ring.
OUTPUT:
A list of linear matroids represented by corankpreserving singleelement coextensions of this linear matroid representation. In particular, the coextension by a loop is not generated.
If one or more of the above inputs is given, the list is restricted to coextensions
so that the new element lies in the cospan of
F
, if given.so that the new element is no coloop and is not in series with another element, if
cosimple = True
.so that in the representation of the coextension, the cross ratios are restricted to
fundamentals
, if given. Note that it is assumed that the cross ratios of the input matroid already satisfy this condition.
EXAMPLES:
sage: M = Matroid(ring=GF(2), ....: reduced_matrix=[[1, 0, 1], [1, 1, 0], [0, 1, 1]]) sage: len(M.linear_coextensions()) 8 sage: S = M.linear_coextensions(cosimple=True) sage: S [Binary matroid of rank 4 on 7 elements, type (3, 7)] sage: F7 = matroids.catalog.Fano() sage: S[0].is_field_isomorphic(F7.dual()) True sage: M = Matroid(ring=QQ, ....: reduced_matrix=[[1, 0, 1], [1, 1, 0], [0, 1, 1]]) sage: S = M.linear_coextensions(cosimple=True, ....: fundamentals=[1, 1, 1/2, 2]) sage: len(S) 7 sage: NF7 = matroids.catalog.NonFano() sage: any(N.is_isomorphic(NF7.dual()) for N in S) True sage: len(M.linear_coextensions(cosimple=True, ....: fundamentals=[1, 1, 1/2, 2], ....: F=[3, 4])) 1
 linear_extension(element, chain=None, col=None)#
Return a linear extension of this matroid.
A linear extension of the represented matroid \(M\) by element \(e\) is a matroid represented by \([A\ \ b]\), where \(A\) is a representation matrix of \(M\) and \(b\) is a new column labeled by \(e\).
INPUT:
element
– the name of the new element.col
– (default:None
) a column to be appended toself.representation()
. Can be any iterable.chain
– (default:None
) a dictionary that maps elements of the ground set to elements of the base ring.
OUTPUT:
A linear matroid \(N = M([A\ \ b])\), where \(A\) is a matrix such that the current matroid is \(M[A]\), and \(b\) is either given by
col
or is a weighted combination of columns of \(A\), the weights being given bychain
.See also
EXAMPLES:
sage: M = Matroid(ring=GF(2), matrix=[[1, 1, 0, 1, 0, 0], ....: [1, 0, 1, 0, 1, 0], ....: [0, 1, 1, 0, 0, 1], ....: [0, 0, 0, 1, 1, 1]]) sage: M.linear_extension(6, {0:1, 5: 1}).representation() [1 1 0 1 0 0 1] [1 0 1 0 1 0 1] [0 1 1 0 0 1 1] [0 0 0 1 1 1 1] sage: M.linear_extension(6, col=[0, 1, 1, 1]).representation() [1 1 0 1 0 0 0] [1 0 1 0 1 0 1] [0 1 1 0 0 1 1] [0 0 0 1 1 1 1]
 linear_extension_chains(F=None, simple=False, fundamentals=None)#
Create a list of chains that determine the singleelement extensions of this linear matroid representation.
A chain is a dictionary, mapping elements from the groundset to elements of the base ring, indicating a linear combination of columns to form the new column. Think of chains as vectors, only independent of representation.
INPUT:
F
– (default:self.groundset()
) a subset of the groundset.simple
– (default:False
) a boolean variable.fundamentals
– (default:None
) a set elements of the base ring.
OUTPUT:
A list of chains, so each singleelement extension of this linear matroid representation is given by one of these chains.
If one or more of the above inputs is given, the list is restricted to chains
so that the support of each chain lies in
F
, if givenso that the chain does not generate a parallel extension or loop, if
simple = True
so that in the extension generated by this chain, the cross ratios are restricted to
fundamentals
, if given.
EXAMPLES:
sage: M = Matroid(reduced_matrix=Matrix(GF(2), ....: [[1, 1, 0], [1, 0, 1], [0, 1, 1]])) sage: len(M.linear_extension_chains()) 8 sage: len(M.linear_extension_chains(F=[0, 1])) 4 sage: len(M.linear_extension_chains(F=[0, 1], simple=True)) 0 sage: M.linear_extension_chains(F=[0, 1, 2], simple=True) [{0: 1, 1: 1, 2: 1}] sage: N = Matroid(ring=QQ, ....: reduced_matrix=[[1, 1, 0], [1, 0, 1], [0, 1, 1]]) sage: L = N.linear_extension_chains(F=[0, 1], simple=True, ....: fundamentals=set([1, 1, 1/2, 2])) sage: result = [{0: 1, 1: 1}, {0: 1/2, 1: 1}, {0: 2, 1: 1}] sage: all(D in L for D in result) True
 linear_extensions(element=None, F=None, simple=False, fundamentals=None)#
Create a list of linear matroids represented by rankpreserving singleelement extensions of this linear matroid representation.
INPUT:
element
– (default:None
) the name of the new element of the groundset.F
– (default:None
) a subset of the ground set.simple
– (default:False
) a boolean variable.fundamentals
– (default:None
) a set elements of the base ring.
OUTPUT:
A list of linear matroids represented by rankpreserving singleelement extensions of this linear matroid representation. In particular, the extension by a coloop is not generated.
If one or more of the above inputs is given, the list is restricted to matroids
so that the new element is spanned by
F
, if givenso that the new element is not a loop or in a parallel pair, if
simple=True
so that in the representation of the extension, the cross ratios are restricted to
fundamentals
, if given. Note that it is assumed that the cross ratios of the input matroid already satisfy this condition.
EXAMPLES:
sage: M = Matroid(ring=GF(2), ....: reduced_matrix=[[1, 0, 1], [1, 1, 0], [0, 1, 1]]) sage: len(M.linear_extensions()) 8 sage: S = M.linear_extensions(simple=True); S [Binary matroid of rank 3 on 7 elements, type (3, 0)] sage: S[0].is_field_isomorphic(matroids.catalog.Fano()) True sage: M = Matroid(ring=QQ, ....: reduced_matrix=[[1, 0, 1], [1, 1, 0], [0, 1, 1]]) sage: S = M.linear_extensions(simple=True, ....: fundamentals=[1, 1, 1/2, 2]) sage: len(S) 7 sage: any(N.is_isomorphic(matroids.catalog.NonFano()) ....: for N in S) True sage: len(M.linear_extensions(simple=True, ....: fundamentals=[1, 1, 1/2, 2], F=[0, 1])) 1
 orlik_terao_algebra(R=None, ordering=None, **kwargs)#
Return the OrlikTerao algebra of
self
.INPUT:
R
– (default: the base ring ofself
) the base ringordering
– (optional) an ordering of the ground set
See also
EXAMPLES:
sage: M = matroids.Wheel(3) sage: OS = M.orlik_terao_algebra(); OS OrlikTerao algebra of Wheel(3): Regular matroid of rank 3 on 6 elements with 16 bases over Integer Ring sage: OS.base_ring() Integer Ring sage: M.orlik_terao_algebra(QQ).base_ring() Rational Field sage: G = SymmetricGroup(3); # needs sage.groups sage: OTG = M.orlik_terao_algebra(QQ, invariant=G) # needs sage.groups sage: # needs sage.groups sage: G = SymmetricGroup(4) sage: action = lambda g, x: g(x + 1)  1 sage: OTG1 = M.orlik_terao_algebra(QQ, invariant=(G,action)) sage: OTG2 = M.orlik_terao_algebra(QQ, invariant=(action,G)) sage: OTG1 is OTG2 True
 representation(B=None, reduced=False, labels=None, order=None, lift_map=None)#
Return a matrix representing the matroid.
Let \(M\) be a matroid on \(n\) elements with rank \(r\). Let \(E\) be an ordering of the groundset, as output by
M.groundset_list()
. A representation of the matroid is an \(r \times n\) matrix with the following property. Consider column \(i\) to be labeled by \(E[i]\), and denote by \(A[F]\) the submatrix formed by the columns labeled by the subset \(F \subseteq E\). Then for all \(F \subseteq E\), the columns of \(A[F]\) are linearly independent if and only if \(F\) is an independent set in the matroid.A reduced representation is a matrix \(D\) such that \([I\ \ D]\) is a representation of the matroid, where \(I\) is an \(r \times r\) identity matrix. In this case, the rows of \(D\) are considered to be labeled by the first \(r\) elements of the list
E
, and the columns by the remaining \(n  r\) elements.INPUT:
B
– (default:None
) a subset of elements. When provided, the representation is such that a basis \(B'\) that maximally intersects \(B\) is an identity matrix.reduced
– (default:False
) whenTrue
, return a reduced matrix \(D\) (so \([I\ \ D]\) is a representation of the matroid). Otherwise return a full representation matrix.labels
– (default:None
) whenTrue
, return additionally a list of column labels (ifreduced=False
) or a list of row labels and a list of column labels (ifreduced=True
). The default setting,None
, will not return the labels for a full matrix, but will return the labels for a reduced matrix.order
– (default:None
) an ordering of the groundset elements. If provided, the columns (and, in case of a reduced representation, rows) will be presented in the given order.lift_map
– (default:None
) a dictionary containing the cross ratios of the representing matrix in its domain. If provided, the representation will be transformed by mapping its cross ratios according tolift_map
.
OUTPUT:
A
– a full or reduced representation matrix ofself
; or(A, E)
– a full representation matrixA
and a listE
of column labels; or(A, R, C)
– a reduced representation matrix and a listR
of row labels and a listC
of column labels.
If
B == None
andreduced == False
andorder == None
then this method will always output the same matrix (except whenM._forget()
is called): either the matrix used as input to create the matroid, or a matrix in which the lexicographically least basis corresponds to an identity. If onlyorder
is notNone
, the columns of this matrix will be permuted accordingly.If a
lift_map
is provided, then the resulting matrix will be lifted using the methodlift_cross_ratios()
See the docstring of this method for further details.Note
A shortcut for
M.representation()
isMatrix(M)
.EXAMPLES:
sage: M = matroids.catalog.Fano() sage: M.representation() [1 0 0 0 1 1 1] [0 1 0 1 0 1 1] [0 0 1 1 1 0 1] sage: Matrix(M) == M.representation() True sage: M.representation(labels=True) ( [1 0 0 0 1 1 1] [0 1 0 1 0 1 1] [0 0 1 1 1 0 1], ['a', 'b', 'c', 'd', 'e', 'f', 'g'] ) sage: M.representation(B='efg') [1 1 0 1 1 0 0] [1 0 1 1 0 1 0] [1 1 1 0 0 0 1] sage: M.representation(B='efg', order='efgabcd') [1 0 0 1 1 0 1] [0 1 0 1 0 1 1] [0 0 1 1 1 1 0] sage: M.representation(B='abc', reduced=True) ( [0 1 1 1] [1 0 1 1] [1 1 0 1], ['a', 'b', 'c'], ['d', 'e', 'f', 'g'] ) sage: M.representation(B='efg', reduced=True, labels=False, ....: order='gfeabcd') [1 1 1 0] [1 0 1 1] [1 1 0 1] sage: from sage.matroids.advanced import lift_cross_ratios, lift_map, LinearMatroid sage: R = GF(7) sage: A = Matrix(R, [[1, 0, 6, 1, 2],[6, 1, 0, 0, 1],[0, 6, 3, 6, 0]]) sage: M = LinearMatroid(reduced_matrix=A) sage: M.representation(lift_map=lift_map('sru')) # needs sage.rings.finite_rings [ 1 0 0 1 0 1 1 1] [ 0 1 0 z + 1 1 0 0 1] [ 0 0 1 0 1 1 z  1 0]
 representation_vectors()#
Return a dictionary that associates a column vector with each element of the matroid.
See also
EXAMPLES:
sage: M = matroids.catalog.Fano() sage: E = M.groundset_list() sage: [M.representation_vectors()[e] for e in E] [(1, 0, 0), (0, 1, 0), (0, 0, 1), (0, 1, 1), (1, 0, 1), (1, 1, 0), (1, 1, 1)]
 class sage.matroids.linear_matroid.QuaternaryMatroid#
Bases:
LinearMatroid
Quaternary matroids.
A quaternary matroid is a linear matroid represented over the finite field with four elements. See
LinearMatroid
for a definition.The simplest way to create a
QuaternaryMatroid
is by giving only a matrix \(A\). Then, the groundset defaults torange(A.ncols())
. Any iterable object \(E\) can be given as a groundset. If \(E\) is a list, thenE[i]
will label the \(i\)th column of \(A\). Another possibility is to specify a ‘reduced’ matrix \(B\), to create the matroid induced by \(A = [I\ \ B]\).INPUT:
matrix
– (default:None
) a matrix whose column vectors represent the matroid.reduced_matrix
– (default:None
) a matrix \(B\) such that \([I\ \ B]\) represents the matroid, where \(I\) is an identity matrix with the same number of rows as \(B\). Only one ofmatrix
andreduced_matrix
should be provided.groundset
– (default:None
) an iterable containing the element labels. When provided, must have the correct number of elements: the number of columns ofmatrix
or the number of rows plus the number of columns ofreduced_matrix
.ring
– (default:None
) must be a copy of \(\GF{4}\).keep_initial_representation
– (default:True
) boolean. Decides whether or not an internal copy of the input matrix should be preserved. This can help to see the structure of the matroid (e.g. in the case of graphic matroids), and makes it easier to look at extensions. However, the input matrix may have redundant rows, and sometimes it is desirable to store only a rowreduced copy.basis
– (default:None
) When provided, this is an ordered subset ofgroundset
, such that the submatrix ofmatrix
indexed bybasis
is an identity matrix. In this case, no row reduction takes place in the initialization phase.
OUTPUT:
A
QuaternaryMatroid
instance based on the data above.Note
The recommended way to generate a quaternary matroid is through the
Matroid()
function. This is usually the preferred way, since it automatically chooses betweenQuaternaryMatroid
and other classes. For direct access to theQuaternaryMatroid
constructor, run:sage: from sage.matroids.advanced import *
EXAMPLES:
sage: # needs sage.rings.finite_rings sage: GF4 = GF(4, 'x') sage: x = GF4.gens()[0] sage: A = Matrix(GF4, 2, 4, [[1, 0, 1, 1], [0, 1, 1, x]]) sage: M = Matroid(A) sage: M Quaternary matroid of rank 2 on 4 elements sage: sorted(M.groundset()) [0, 1, 2, 3] sage: Matrix(M) [1 0 1 1] [0 1 1 x] sage: M = Matroid(matrix=A, groundset='abcd') sage: sorted(M.groundset()) ['a', 'b', 'c', 'd'] sage: GF4p = GF(4, 'y') sage: y = GF4p.gens()[0] sage: B = Matrix(GF4p, 2, 2, [[1, 1], [1, y]]) sage: N = Matroid(reduced_matrix=B, groundset='abcd') sage: M == N False
 base_ring()#
Return the base ring of the matrix representing the matroid, in this case \(\GF{4}\).
EXAMPLES:
sage: M = Matroid(ring=GF(4, 'y'), reduced_matrix=[[1, 0, 1], # needs sage.rings.finite_rings ....: [0, 1, 1]]) sage: M.base_ring() # needs sage.rings.finite_rings Finite Field in y of size 2^2
 bicycle_dimension()#
Return the bicycle dimension of the quaternary matroid.
The bicycle dimension of a linear subspace \(V\) is \(\dim(V\cap V^\perp)\). We use the inner product \(< v, w >=v_1 w_1^* + ... + v_n w_n^*\), where \(w_i^*\) is obtained from \(w_i\) by applying the unique nontrivial field automorphism of \(\GF{4}\).
The bicycle dimension of a matroid equals the bicycle dimension of its rowspace, and is a matroid invariant. See [Pen2012].
OUTPUT:
Integer.
EXAMPLES:
sage: M = matroids.catalog.Q10() # needs sage.rings.finite_rings sage: M.bicycle_dimension() # needs sage.rings.finite_rings 0
 characteristic()#
Return the characteristic of the base ring of the matrix representing the matroid, in this case \(2\).
EXAMPLES:
sage: M = Matroid(ring=GF(4, 'y'), reduced_matrix=[[1, 0, 1], # needs sage.rings.finite_rings ....: [0, 1, 1]]) sage: M.characteristic() # needs sage.rings.finite_rings 2
 is_valid()#
Test if the data obey the matroid axioms.
Since this is a linear matroid over the field \(\GF{4}\), this is always the case.
OUTPUT:
True
.EXAMPLES:
sage: M = Matroid(Matrix(GF(4, 'x'), [[]])) # needs sage.rings.finite_rings sage: M.is_valid() # needs sage.rings.finite_rings True
 class sage.matroids.linear_matroid.RegularMatroid#
Bases:
LinearMatroid
Regular matroids.
A regular matroid is a linear matroid represented over the integers by a totally unimodular matrix.
The simplest way to create a
RegularMatroid
is by giving only a matrix \(A\). Then, the groundset defaults torange(A.ncols())
. Any iterable object \(E\) can be given as a groundset. If \(E\) is a list, thenE[i]
will label the \(i\)th column of \(A\). Another possibility is to specify a ‘reduced’ matrix \(B\), to create the matroid induced by \(A = [ I B ]\).INPUT:
matrix
– (default:None
) a matrix whose column vectors represent the matroid.reduced_matrix
– (default:None
) a matrix \(B\) such that \([I\ \ B]\) represents the matroid, where \(I\) is an identity matrix with the same number of rows as \(B\). Only one ofmatrix
andreduced_matrix
should be provided.groundset
– (default:None
) an iterable containing the element labels. When provided, must have the correct number of elements: the number of columns ofmatrix
or the number of rows plus the number of columns ofreduced_matrix
.ring
– (default:None
) ignored.keep_initial_representation
– (default:True
) boolean. Decides whether or not an internal copy of the input matrix should be preserved. This can help to see the structure of the matroid (e.g. in the case of graphic matroids), and makes it easier to look at extensions. However, the input matrix may have redundant rows, and sometimes it is desirable to store only a rowreduced copy.basis
– (default:None
) when provided, this is an ordered subset ofgroundset
, such that the submatrix ofmatrix
indexed bybasis
is an identity matrix. In this case, no row reduction takes place in the initialization phase.
OUTPUT:
A
RegularMatroid
instance based on the data above.Note
The recommended way to generate a regular matroid is through the
Matroid()
function. This is usually the preferred way, since it automatically chooses betweenRegularMatroid
and other classes. Moreover, it will test whether the input actually yields a regular matroid, unlike this class. For direct access to theRegularMatroid
constructor, run:sage: from sage.matroids.advanced import *
Warning
No checks are performed to ensure the input data form an actual regular matroid! If not, the behavior is unpredictable, and the internal representation can get corrupted. If in doubt, run
self.is_valid()
to ensure the data are as desired.EXAMPLES:
sage: A = Matrix(ZZ, 2, 4, [[1, 0, 1, 1], [0, 1, 1, 1]]) sage: M = Matroid(A, regular=True); M # needs sage.graphs Regular matroid of rank 2 on 4 elements with 5 bases sage: sorted(M.groundset()) # needs sage.graphs [0, 1, 2, 3] sage: Matrix(M) # needs sage.graphs [1 0 1 1] [0 1 1 1] sage: M = Matroid(matrix=A, groundset='abcd', regular=True) # needs sage.graphs sage: sorted(M.groundset()) # needs sage.graphs ['a', 'b', 'c', 'd']
 base_ring()#
Return the base ring of the matrix representing the matroid, in this case \(\ZZ\).
EXAMPLES:
sage: M = matroids.catalog.R10() sage: M.base_ring() Integer Ring
 bases_count()#
Count the number of bases.
EXAMPLES:
sage: M = Matroid(graphs.CompleteGraph(5), regular=True) # needs sage.graphs sage: M.bases_count() # needs sage.graphs 125
ALGORITHM:
Since the matroid is regular, we use Kirchhoff’s MatrixTree Theorem. See also Wikipedia article Kirchhoff%27s_theorem.
 binary_matroid(randomized_tests=1, verify=True)#
Return a binary matroid representing
self
.INPUT:
randomized_tests
– Ignored.verify
– Ignored
OUTPUT:
A binary matroid.
ALGORITHM:
self
is a regular matroid, so just castself
to a BinaryMatroid.See also
EXAMPLES:
sage: N = matroids.catalog.R10() sage: N.binary_matroid() Binary matroid of rank 5 on 10 elements, type (1, None)
 characteristic()#
Return the characteristic of the base ring of the matrix representing the matroid, in this case \(0\).
EXAMPLES:
sage: M = matroids.catalog.R10() sage: M.characteristic() 0
 has_line_minor(k, hyperlines=None, certificate=False)#
Test if the matroid has a \(U_{2, k}\)minor.
The matroid \(U_{2, k}\) is a matroid on \(k\) elements in which every subset of at most 2 elements is independent, and every subset of more than two elements is dependent.
The optional argument
hyperlines
restricts the search space: this method returnsTrue
if \(si(M/F)\) is isomorphic to \(U_{2, l}\) with \(l \geq k\) for some \(F\) inhyperlines
, andFalse
otherwise.INPUT:
k
– the length of the line minorhyperlines
– (default:None
) a set of flats of codimension 2. Defaults to the set of all flats of codimension 2.certificate
(default:False
); IfTrue
returnsTrue, F
, whereF
is a flat andself.minor(contractions=F)
has a \(U_{2,k}\) restriction orFalse, None
.
OUTPUT:
Boolean or tuple.
See also
EXAMPLES:
sage: M = matroids.catalog.R10() sage: M.has_line_minor(4) False sage: M.has_line_minor(4, certificate=True) (False, None) sage: M.has_line_minor(3) True sage: M.has_line_minor(3, certificate=True) (True, frozenset({'a', 'b', 'c', 'g'})) sage: M.has_line_minor(k=3, hyperlines=[['a', 'b', 'c'], ....: ['a', 'b', 'd' ]]) True sage: M.has_line_minor(k=3, hyperlines=[['a', 'b', 'c'], ....: ['a', 'b', 'd' ]], certificate=True) (True, frozenset({'a', 'b', 'c'}))
 is_binary(randomized_tests=1)#
Decide if
self
is a binary matroid.INPUT:
randomized_tests
– Ignored.
OUTPUT:
A Boolean.
ALGORITHM:
self
is a regular matroid, so just returnTrue
.See also
EXAMPLES:
sage: N = matroids.catalog.R10() sage: N.is_binary() True
 is_graphic()#
Test if the regular matroid is graphic.
A matroid is graphic if there exists a graph whose edge set equals the groundset of the matroid, such that a subset of elements of the matroid is independent if and only if the corresponding subgraph is acyclic.
OUTPUT:
Boolean.
EXAMPLES:
sage: M = matroids.catalog.R10() sage: M.is_graphic() False sage: M = Matroid(graphs.CompleteGraph(5), regular=True) # needs sage.graphs sage: M.is_graphic() # needs sage.graphs sage.rings.finite_rings True sage: M.dual().is_graphic() # needs sage.graphs False
ALGORITHM:
In a recent paper, Geelen and Gerards [GG2012] reduced the problem to testing if a system of linear equations has a solution. While not the fastest method, and not necessarily constructive (in the presence of 2separations especially), it is easy to implement.
 is_ternary(randomized_tests=1)#
Decide if
self
is a ternary matroid.INPUT:
randomized_tests
– Ignored.
OUTPUT:
A Boolean.
ALGORITHM:
self
is a regular matroid, so just returnTrue
.See also
EXAMPLES:
sage: N = matroids.catalog.R10() sage: N.is_ternary() True
 is_valid()#
Test if the data obey the matroid axioms.
Since this is a regular matroid, this function tests if the representation matrix is totally unimodular, i.e. if all square submatrices have determinant in \(\{1, 0, 1\}\).
OUTPUT:
Boolean.
EXAMPLES:
sage: # needs sage.graphs sage: M = Matroid(Matrix(ZZ, [[1, 0, 0, 1, 1, 0, 1], ....: [0, 1, 0, 1, 0, 1, 1], ....: [0, 0, 1, 0, 1, 1, 1]]), ....: regular=True, check=False) sage: M.is_valid() False sage: M = Matroid(graphs.PetersenGraph()) sage: M.is_valid() True
 ternary_matroid(randomized_tests=1, verify=True)#
Return a ternary matroid representing
self
.INPUT:
randomized_tests
– Ignored.verify
– Ignored
OUTPUT:
A ternary matroid.
ALGORITHM:
self
is a regular matroid, so just castself
to a TernaryMatroid.See also
EXAMPLES:
sage: N = matroids.catalog.R10() sage: N.ternary_matroid() Ternary matroid of rank 5 on 10 elements, type 4+
 class sage.matroids.linear_matroid.TernaryMatroid#
Bases:
LinearMatroid
Ternary matroids.
A ternary matroid is a linear matroid represented over the finite field with three elements. See
LinearMatroid
for a definition.The simplest way to create a
TernaryMatroid
is by giving only a matrix \(A\). Then, the groundset defaults torange(A.ncols())
. Any iterable object \(E\) can be given as a groundset. If \(E\) is a list, thenE[i]
will label the \(i\)th column of \(A\). Another possibility is to specify a ‘reduced’ matrix \(B\), to create the matroid induced by \(A = [I\ \ B]\).INPUT:
matrix
– (default:None
) a matrix whose column vectors represent the matroid.reduced_matrix
– (default:None
) a matrix \(B\) such that \([I\ \ B]\) represents the matroid, where \(I\) is an identity matrix with the same number of rows as \(B\). Only one ofmatrix
andreduced_matrix
should be provided.groundset
– (default:None
) an iterable containing the element labels. When provided, must have the correct number of elements: the number of columns ofmatrix
or the number of rows plus the number of columns ofreduced_matrix
.ring
– (default:None
) ignored.keep_initial_representation
– (default:True
) boolean. Decides whether or not an internal copy of the input matrix should be preserved. This can help to see the structure of the matroid (e.g. in the case of graphic matroids), and makes it easier to look at extensions. However, the input matrix may have redundant rows, and sometimes it is desirable to store only a rowreduced copy.basis
– (default:None
) when provided, this is an ordered subset ofgroundset
, such that the submatrix ofmatrix
indexed bybasis
is an identity matrix. In this case, no row reduction takes place in the initialization phase.
OUTPUT:
A
TernaryMatroid
instance based on the data above.Note
The recommended way to generate a ternary matroid is through the
Matroid()
function. This is usually the preferred way, since it automatically chooses betweenTernaryMatroid
and other classes. For direct access to theTernaryMatroid
constructor, run:sage: from sage.matroids.advanced import *
EXAMPLES:
sage: A = Matrix(GF(3), 2, 4, [[1, 0, 1, 1], [0, 1, 1, 1]]) sage: M = Matroid(A); M Ternary matroid of rank 2 on 4 elements, type 0 sage: sorted(M.groundset()) [0, 1, 2, 3] sage: Matrix(M) [1 0 1 1] [0 1 1 1] sage: M = Matroid(matrix=A, groundset='abcd') sage: sorted(M.groundset()) ['a', 'b', 'c', 'd'] sage: B = Matrix(GF(2), 2, 2, [[1, 1], [1, 1]]) sage: N = Matroid(ring=GF(3), reduced_matrix=B, groundset='abcd') # needs sage.rings.finite_rings sage: M == N # needs sage.rings.finite_rings True
 base_ring()#
Return the base ring of the matrix representing the matroid, in this case \(\GF{3}\).
EXAMPLES:
sage: M = matroids.catalog.NonFano() sage: M.base_ring() Finite Field of size 3
 bicycle_dimension()#
Return the bicycle dimension of the ternary matroid.
The bicycle dimension of a linear subspace \(V\) is \(\dim(V\cap V^\perp)\). The bicycle dimension of a matroid equals the bicycle dimension of its rowspace, and is a matroid invariant. See [Pen2012].
OUTPUT:
Integer.
EXAMPLES:
sage: M = matroids.catalog.NonFano() sage: M.bicycle_dimension() 0
 character()#
Return the character of the ternary matroid.
For a linear subspace \(V\) over \(GF(3)\) with orthogonal basis \(q_1, \ldots, q_k\) the character equals the product of \(q_i\) modulo 3, where the product ranges over the \(i\) such that \(q_i\) is not divisible by 3. The character does not depend on the choice of the orthogonal basis. The character of a ternary matroid equals the character of its cocyclespace, and is an invariant for ternary matroids. See [Pen2012].
OUTPUT:
Integer.
EXAMPLES:
sage: M = matroids.catalog.NonFano() sage: M.character() 2
 characteristic()#
Return the characteristic of the base ring of the matrix representing the matroid, in this case \(3\).
EXAMPLES:
sage: M = matroids.catalog.NonFano() sage: M.characteristic() 3
 is_ternary(randomized_tests=1)#
Decide if
self
is a binary matroid.INPUT:
randomized_tests
– Ignored.
OUTPUT:
A Boolean.
ALGORITHM:
self
is a ternary matroid, so just returnTrue
.See also
EXAMPLES:
sage: N = matroids.catalog.NonFano() sage: N.is_ternary() True
 is_valid()#
Test if the data obey the matroid axioms.
Since this is a linear matroid over the field \(\GF{3}\), this is always the case.
OUTPUT:
True
.EXAMPLES:
sage: M = Matroid(Matrix(GF(3), [[]])) sage: M.is_valid() True
 ternary_matroid(randomized_tests=1, verify=True)#
Return a ternary matroid representing
self
.INPUT:
randomized_tests
– Ignored.verify
– Ignored
OUTPUT:
A binary matroid.
ALGORITHM:
self
is a ternary matroid, so just returnself
.See also
EXAMPLES:
sage: N = matroids.catalog.NonFano() sage: N.ternary_matroid() is N True