Linear matroids
When is an
times
matrix, the linear matroid
has ground set
and, for independent sets, all
subset of
such that the columns of
indexed by
are linearly independent.
The recommended way to create a linear matroid is by using the
Matroid() function, with a
representation matrix 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 , to create the matroid induced by
:
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
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:
- base_ring()
- characteristic()
- representation()
- representation_vectors()
- is_field_equivalent()
- is_field_isomorphism()
- has_field_minor()
- fundamental_cycle()
- fundamental_cocycle()
- cross_ratios()
- cross_ratio()
- linear_extension()
- linear_coextension()
- linear_extension_chains()
- linear_coextension_cochains()
- linear_extensions()
- linear_coextensions()
BinaryMatroid has all of the LinearMatroid ones, and
TernaryMatroid has all of the LinearMatroid ones, and
QuaternaryMatroid has all of the LinearMatroid ones, and
RegularMatroid has all of the LinearMatroid ones, and
AUTHORS:
Bases: sage.matroids.linear_matroid.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
. Then, the groundset defaults to range(A.ncols()). Any iterable
object
can be given as a groundset. If
is a list, then E[i]
will label the
-th column of
. Another possibility is to specify a
reduced matrix
, to create the matroid induced by
.
INPUT:
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 between BinaryMatroid and other classes. For direct access to the BinaryMatroid 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
Return the base ring of the matrix representing the matroid,
in this case .
EXAMPLES:
sage: M = matroids.named_matroids.Fano()
sage: M.base_ring()
Finite Field of size 2
Return the bicycle dimension of the binary matroid.
The bicycle dimension of a linear subspace is
. The bicycle dimension of a matroid equals the
bicycle dimension of its cocycle-space, and is an invariant for binary
matroids. See [Pen12], [GR01] for more information.
OUTPUT:
Integer.
EXAMPLES:
sage: M = matroids.named_matroids.Fano()
sage: M.bicycle_dimension()
3
Return the value of Brown’s invariant for the binary matroid.
For a binary space , consider the sum
, where
denotes the number of
nonzero entries of a binary vector
. The value of the Tutte
Polynomial in the point
can be expressed in terms of
, see [Pen12]. If
equals
modulo 4 for some
, then
. In this case, Browns invariant is
not defined. Otherwise,
for
some integers
. In that case,
equals the bycycle
dimension of
, and Browns invariant for
is defined as
modulo
.
The Brown invariant of a binary matroid equals the Brown invariant of its cocycle-space.
OUTPUT:
Integer.
EXAMPLES:
sage: M = matroids.named_matroids.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
Return the characteristic of the base ring of the matrix representing
the matroid, in this case .
EXAMPLES:
sage: M = matroids.named_matroids.Fano()
sage: M.characteristic()
2
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.named_matroids.R10()
sage: M = Matroid(ring=GF(2), reduced_matrix=R10.representation(
....: reduced=True, labels=False))
sage: M.is_graphic()
False
sage: K5 = matroids.CompleteGraphic(5)
sage: M = Matroid(ring=GF(2), reduced_matrix=K5.representation(
....: reduced=True, labels=False))
sage: M.is_graphic()
True
sage: M.dual().is_graphic()
False
In a recent paper, Geelen and Gerards [GG12] 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 2-separations especially), it is easy to implement.
Test if the data obey the matroid axioms.
Since this is a linear matroid over the field , this is always
the case.
OUTPUT:
True.
EXAMPLES:
sage: M = Matroid(Matrix(GF(2), [[]]))
sage: M.is_valid()
True
Bases: sage.matroids.basis_exchange_matroid.BasisExchangeMatroid
Linear matroids.
When is an
times
matrix, the linear matroid
has ground
set
and set of independent sets
the columns of
indexed by
are linearly independent
The simplest way to create a LinearMatroid is by giving only a matrix .
Then, the groundset defaults to range(A.ncols()). Any iterable object
E can be given as a groundset. If E is a list, then E[i] will
label the
-th column of
. Another possibility is to specify a
reduced matrix
, to create the matroid induced by
.
INPUT:
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 (currently BinaryMatroid, TernaryMatroid, QuaternaryMatroid, RegularMatroid). For direct access to the LinearMatroid 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
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
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
Return the cross ratio of the four ordered points a, b, c, d after contracting a flat F of codimension 2.
Consider the following matrix with columns labeled by
.
The cross ratio of the ordered tuple equals
. This
method looks at such minors where F is a flat to be contracted,
and all remaining elements other than a, b, c, d are deleted.
INPUT:
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 4-point line in M/F
Return the set of cross ratios that occur in this linear matroid.
Consider the following matrix with columns labeled by
.
The cross ratio of the ordered tuple equals
. The
set of all cross ratios of a matroid is the set of cross ratios of all
such minors.
INPUT:
OUTPUT:
A list of all cross ratios of this linearly represented matroid that occur in rank-2 minors that arise by contracting a flat F in hyperlines (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 = matroids.CompleteGraphic(5)
sage: M.cross_ratios()
set([])
Return the dual of the matroid.
Let be a matroid with ground set
. If
is the set of bases
of
, then the set
is the set of bases of
another matroid, the dual of
.
If the matroid is represented by , then the dual is
represented by
for appropriately sized identity
matrices
.
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
Return the fundamental cycle, relative to B, containing element e.
This is the
fundamental cocircuit
together with an appropriate signing from the field, such that ,
where
is a representation matrix of the dual, and
the vector
corresponding to the output.
INPUT:
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
Return the fundamental cycle, relative to B, containing element e.
This is the
fundamental circuit
together with an appropriate signing from the field, such that ,
where
is the representation matrix, and
the vector
corresponding to the output.
INPUT:
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
Check if self has a minor field isomorphic to N.
INPUT:
OUTPUT:
Boolean.
See also
Todo
This important method can (and should) be optimized considerably. See [Hlineny] p.1219 for hints to that end.
EXAMPLES:
sage: M = matroids.Whirl(3)
sage: matroids.named_matroids.Fano().has_field_minor(M)
False
sage: matroids.named_matroids.NonFano().has_field_minor(M)
True
Test if the matroid has a -minor.
The matroid is a matroid on
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 returns False if is isomorphic to
with
for some
in hyperlines, and True otherwise.
INPUT:
OUTPUT:
Boolean.
EXAMPLES:
sage: M = matroids.named_matroids.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
Test for matroid representation equality.
Two linear matroids and
with representation matrices
and
are field equivalent if they have the same groundset, and the
identity map between the groundsets is an isomorphism between the
representations
and
. That is, one can be turned into the other
using only row operations and column scaling.
INPUT:
OUTPUT:
Boolean.
EXAMPLES:
A BinaryMatroid and LinearMatroid use different representations of the matroid internally, so `` == `` yields False, even if the matroids are equal:
sage: from sage.matroids.advanced import *
sage: M = matroids.named_matroids.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 instances M and N satisfy M == 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
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:
OUTPUT:
Boolean.
EXAMPLES:
sage: M1 = matroids.Wheel(3)
sage: M2 = matroids.CompleteGraphic(4)
sage: M1.is_field_isomorphic(M2)
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
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:
OUTPUT:
Boolean.
EXAMPLES:
sage: M = matroids.named_matroids.Fano()
sage: N = matroids.named_matroids.NonFano()
sage: N.is_field_isomorphism(M, {e:e for e in M.groundset()})
False
sage: from sage.matroids.advanced import *
sage: M = matroids.named_matroids.Fano() \ ['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
Test if the data represent an actual matroid.
Since this matroid is linear, we test the representation matrix.
OUTPUT:
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
Return a linear coextension of this matroid.
A linear coextension of the represented matroid by element
is a matroid represented by
where is a representation matrix of
,
is a new row, and the
last column is labeled by
.
This is the dual method of M.linear_extension().
INPUT:
OUTPUT:
A linear matroid , where
is a matrix such that
the current matroid is
, and
is either given by row
(relative to self.representation()) or has nonzero entries given
by cochain.
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.named_matroids.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
Create a list of cochains that determine the single-element coextensions of this linear matroid representation.
A cochain is a dictionary, mapping elements from the groundset to
elements of the base ring. If represents the current matroid, then
the coextension is given by
, with the entries of
given by the cochain. Note that the matroid does not change when
row operations are carried out on
.
INPUT:
OUTPUT:
A list of cochains, so each single-element 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
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/2, 1: 1}, {0: -1, 1: 1}]
Create a list of linear matroids represented by single-element coextensions of this linear matroid representation.
INPUT:
OUTPUT:
A list of linear matroids represented by single-element coextensions of this linear matroid representation.
If one or more of the above inputs is given, the list is restricted to coextensions
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.named_matroids.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.named_matroids.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
Return a linear extension of this matroid.
A linear extension of the represented matroid by element
is
a matroid represented by
, where
is a representation
matrix of
and
is a new column labeled by
.
INPUT:
OUTPUT:
A linear matroid , where
is a matrix such that
the current matroid is
, and
is either given by col or
is a weighted combination of columns of
, the weigths being given
by chain.
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]
Create a list of chains that determine the single-element 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:
OUTPUT:
A list of chains, so each single-element 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
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: N.linear_extension_chains(F=[0, 1], simple=True,
....: fundamentals=set([1, -1, 1/2, 2]))
[{0: 1, 1: 1}, {0: -1/2, 1: 1}, {0: -2, 1: 1}]
Create a list of linear matroids represented by single-element extensions of this linear matroid representation.
INPUT:
OUTPUT:
A list of linear matroids represented by single-element extensions of this linear matroid representation.
If one or more of the above inputs is given, the list is restricted to matroids
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)
sage: S
[Binary matroid of rank 3 on 7 elements, type (3, 0)]
sage: S[0].is_field_isomorphic(matroids.named_matroids.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.named_matroids.NonFano())
....: for N in S)
True
sage: len(M.linear_extensions(simple=True,
....: fundamentals=[1, -1, 1/2, 2], F=[0, 1]))
1
Return a matrix representing the matroid.
Let be a matroid on
elements with rank
. Let
be an
ordering of the groundset, as output by
M.groundset_list().
A representation of the matroid is an
matrix with the
following property. Consider column i to be labeled by E[i],
and denote by
the submatrix formed by the columns labeled by
the subset
. Then for all
, the columns
of
are linearly independent if and only if
is an
independent set in the matroid.
A reduced representation is a matrix such that
is a
representation of the matroid, where
is an
identity
matrix. In this case, the rows of
are considered to be labeled by
the first
elements of the list E, and the columns by the
remaining
elements.
INPUT:
OUTPUT:
If B == None and reduced == False and order == None then this method will always output the same matrix (except when M._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 only order is not None, the columns of this matrix will be permuted accordingly.
Note
A shortcut for M.representation() is Matrix(M).
EXAMPLES:
sage: M = matroids.named_matroids.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]
Return a dictionary that associates a column vector with each element of the matroid.
See also
EXAMPLES:
sage: M = matroids.named_matroids.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)]
Bases: sage.matroids.linear_matroid.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 . Then, the groundset defaults to range(A.ncols()). Any
iterable object
can be given as a groundset. If
is a list, then
E[i] will label the
-th column of
. Another possibility is to
specify a ‘reduced’ matrix
, to create the matroid induced by
.
INPUT:
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 between QuaternaryMatroid and other classes. For direct access to the QuaternaryMatroid constructor, run:
sage: from sage.matroids.advanced import *
EXAMPLES:
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
Return the base ring of the matrix representing the matroid, in this
case .
EXAMPLES:
sage: M = Matroid(ring=GF(4, 'y'), reduced_matrix=[[1, 0, 1],
....: [0, 1, 1]])
sage: M.base_ring()
Finite Field in y of size 2^2
Return the bicycle dimension of the quaternary matroid.
The bicycle dimension of a linear subspace is
. We use the inner product
, where
is obtained from
by applying the unique nontrivial field automorphism of
.
The bicycle dimension of a matroid equals the bicycle dimension of its rowspace, and is a matroid invariant. See [Pen12].
OUTPUT:
Integer.
EXAMPLES:
sage: M = matroids.named_matroids.Q10()
sage: M.bicycle_dimension()
0
Return the characteristic of the base ring of the matrix representing
the matroid, in this case .
EXAMPLES:
sage: M = Matroid(ring=GF(4, 'y'), reduced_matrix=[[1, 0, 1],
....: [0, 1, 1]])
sage: M.characteristic()
2
Test if the data obey the matroid axioms.
Since this is a linear matroid over the field , this is always
the case.
OUTPUT:
True.
EXAMPLES:
sage: M = Matroid(Matrix(GF(4, 'x'), [[]]))
sage: M.is_valid()
True
Bases: sage.matroids.linear_matroid.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
. Then, the groundset defaults to range(A.ncols()).
Any iterable object
can be given as a groundset. If
is a list, then E[i] will label the
-th column of
.
Another possibility is to specify a ‘reduced’ matrix
, to create the matroid induced by
.
INPUT:
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 between RegularMatroid and other classes. Moreover, it will test whether the input actually yields a regular matroid, unlike this class. For direct access to the RegularMatroid 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)
sage: M
Regular matroid of rank 2 on 4 elements with 5 bases
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', regular=True)
sage: sorted(M.groundset())
['a', 'b', 'c', 'd']
Return the base ring of the matrix representing the matroid, in this
case .
EXAMPLES:
sage: M = matroids.named_matroids.R10()
sage: M.base_ring()
Integer Ring
Count the number of bases.
EXAMPLES:
sage: M = matroids.CompleteGraphic(5)
sage: M.bases_count()
125
ALGORITHM:
Since the matroid is regular, we use Kirchhoff’s Matrix-Tree Theorem. See also Wikipedia article Kirchhoff’s_theorem.
Return the characteristic of the base ring of the matrix representing
the matroid, in this case .
EXAMPLES:
sage: M = matroids.named_matroids.R10()
sage: M.characteristic()
0
Test if the matroid has a -minor.
The matroid is a matroid on
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 returns False if is isomorphic to
with
for some
in hyperlines, and True otherwise.
INPUT:
OUTPUT:
Boolean.
See also
EXAMPLES:
sage: M = matroids.named_matroids.R10()
sage: M.has_line_minor(4)
False
sage: M.has_line_minor(3)
True
sage: M.has_line_minor(k=3, hyperlines=[['a', 'b', 'c'],
....: ['a', 'b', 'd' ]])
True
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.named_matroids.R10()
sage: M.is_graphic()
False
sage: M = matroids.CompleteGraphic(5)
sage: M.is_graphic()
True
sage: M.dual().is_graphic()
False
ALGORITHM:
In a recent paper, Geelen and Gerards [GG12] 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 2-separations especially), it is easy to implement.
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 .
OUTPUT:
Boolean.
EXAMPLES:
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
Bases: sage.matroids.linear_matroid.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 . Then, the groundset defaults to range(A.ncols()). Any
iterable object
can be given as a groundset. If
is a list, then
E[i] will label the
-th column of
. Another possibility is to
specify a ‘reduced’ matrix
, to create the matroid induced by
.
INPUT:
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 between TernaryMatroid and other classes. For direct access to the TernaryMatroid 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)
sage: 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')
sage: M == N
True
Return the base ring of the matrix representing the matroid, in this
case .
EXAMPLES:
sage: M = matroids.named_matroids.NonFano()
sage: M.base_ring()
Finite Field of size 3
Return the bicycle dimension of the ternary matroid.
The bicycle dimension of a linear subspace is
. The bicycle dimension of a matroid equals the
bicycle dimension of its rowspace, and is a matroid invariant.
See [Pen12].
OUTPUT:
Integer.
EXAMPLES:
sage: M = matroids.named_matroids.NonFano()
sage: M.bicycle_dimension()
0
Return the character of the ternary matroid.
For a linear subspace over
with orthogonal basis
the character equals the product of
modulo 3, where the product ranges over the
such that
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 cocycle-space, and is an invariant for ternary
matroids. See [Pen12].
OUTPUT:
Integer.
EXAMPLES:
sage: M = matroids.named_matroids.NonFano()
sage: M.character()
2
Return the characteristic of the base ring of the matrix representing
the matroid, in this case .
EXAMPLES:
sage: M = matroids.named_matroids.NonFano()
sage: M.characteristic()
3
Test if the data obey the matroid axioms.
Since this is a linear matroid over the field , this is always
the case.
OUTPUT:
True.
EXAMPLES:
sage: M = Matroid(Matrix(GF(3), [[]]))
sage: M.is_valid()
True