Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
r""" 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 :func:`Matroid() <sage.matroids.constructor.Matroid>` function, with a representation matrix `A` as input. This function will intelligently choose one of the dedicated classes :class:`BinaryMatroid`, :class:`TernaryMatroid`, :class:`QuaternaryMatroid`, :class:`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 :mod:`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 :mod:`Matroid <sage.matroids.matroid>` and :mod:`BasisExchangeMatroid <sage.matroids.basis_exchange_matroid>` classes. See the documentation for these classes for an overview. In addition, the following methods are available:
- :class:`LinearMatroid`
- :func:`base_ring() <sage.matroids.linear_matroid.LinearMatroid.base_ring>` - :func:`characteristic() <sage.matroids.linear_matroid.LinearMatroid.characteristic>` - :func:`representation() <sage.matroids.linear_matroid.LinearMatroid.representation>` - :func:`representation_vectors() <sage.matroids.linear_matroid.LinearMatroid.representation_vectors>` - :func:`is_field_equivalent() <sage.matroids.linear_matroid.LinearMatroid.is_field_equivalent>` - :func:`is_field_isomorphism() <sage.matroids.linear_matroid.LinearMatroid.is_field_isomorphism>` - :func:`has_field_minor() <sage.matroids.linear_matroid.LinearMatroid.has_field_minor>` - :func:`fundamental_cycle() <sage.matroids.linear_matroid.LinearMatroid.fundamental_cycle>` - :func:`fundamental_cocycle() <sage.matroids.linear_matroid.LinearMatroid.fundamental_cocycle>` - :func:`cross_ratios() <sage.matroids.linear_matroid.LinearMatroid.cross_ratios>` - :func:`cross_ratio() <sage.matroids.linear_matroid.LinearMatroid.cross_ratio>`
- :func:`linear_extension() <sage.matroids.linear_matroid.LinearMatroid.linear_extension>` - :func:`linear_coextension() <sage.matroids.linear_matroid.LinearMatroid.linear_coextension>` - :func:`linear_extension_chains() <sage.matroids.linear_matroid.LinearMatroid.linear_extension_chains>` - :func:`linear_coextension_cochains() <sage.matroids.linear_matroid.LinearMatroid.linear_coextension_cochains>` - :func:`linear_extensions() <sage.matroids.linear_matroid.LinearMatroid.linear_extensions>` - :func:`linear_coextensions() <sage.matroids.linear_matroid.LinearMatroid.linear_coextensions>`
- :class:`BinaryMatroid` has all of the :class:`LinearMatroid` ones, and
- :func:`bicycle_dimension() <sage.matroids.linear_matroid.BinaryMatroid.bicycle_dimension>` - :func:`brown_invariant() <sage.matroids.linear_matroid.BinaryMatroid.brown_invariant>` - :func:`is_graphic() <sage.matroids.linear_matroid.BinaryMatroid.is_graphic>`
- :class:`TernaryMatroid` has all of the :class:`LinearMatroid` ones, and
- :func:`bicycle_dimension() <sage.matroids.linear_matroid.TernaryMatroid.bicycle_dimension>` - :func:`character() <sage.matroids.linear_matroid.TernaryMatroid.character>`
- :class:`QuaternaryMatroid` has all of the :class:`LinearMatroid` ones, and
- :func:`bicycle_dimension() <sage.matroids.linear_matroid.QuaternaryMatroid.bicycle_dimension>`
- :class:`RegularMatroid` has all of the :class:`LinearMatroid` ones, and
- :func:`is_graphic() <sage.matroids.linear_matroid.RegularMatroid.is_graphic>`
AUTHORS:
- Rudi Pendavingh, Stefan van Zwam (2013-04-01): initial version
Methods ======= """ #***************************************************************************** # Copyright (C) 2013 Rudi Pendavingh <rudi.pendavingh@gmail.com> # Copyright (C) 2013 Stefan van Zwam <stefanvanzwam@gmail.com> # # # Distributed under the terms of the GNU General Public License (GPL) # as published by the Free Software Foundation; either version 2 of # the License, or (at your option) any later version. # http://www.gnu.org/licenses/ #***************************************************************************** from __future__ import print_function, absolute_import
include 'sage/data_structures/bitset.pxi' from cpython.object cimport Py_EQ, Py_NE
from sage.structure.richcmp cimport rich_to_bool from sage.matroids.matroid cimport Matroid from sage.matroids.basis_exchange_matroid cimport BasisExchangeMatroid from .lean_matrix cimport LeanMatrix, GenericMatrix, BinaryMatrix, TernaryMatrix, QuaternaryMatrix, IntegerMatrix, generic_identity from .set_system cimport SetSystem
from sage.matrix.matrix2 cimport Matrix
cdef GF2, GF2_one, GF2_zero
cdef GF3, GF3_one, GF3_zero, GF3_minus_one
# Implementation note: internally we use data structures from lean_matrix # instead of Sage's standard Matrix datatypes. This was done so we can use # highly optimized methods in critical places. Our hope is to do away with # this in the future. To do so, the following needs to be done: # 1. Modify the ``__init__`` methods (the lean_matrix constructors are # incompatible with Sage's matrix constructors) # 2. Look for all lines saying ``# Not a Sage matrix operation`` and provide # alternative implementations # 3. Look for all lines saying ``# Deprecated Sage matrix operation`` and # provide alternative implementations # Below is some code, commented out currently, to get you going.
cdef inline gauss_jordan_reduce(LeanMatrix A, columns):
cdef inline characteristic(LeanMatrix A):
# Implementation using default Sage matrices
# cdef gauss_jordan_reduce(Matrix A, columns): # """ # Row-reduce so the lexicographically first basis indexes an identity submatrix. # """ # cdef long r = 0 # cdef list P = [] # cdef long c, p, row # for c in columns: # is_pivot = False # for row in xrange(r, A.nrows()): # if A.get_unsafe(row, c) != 0: # is_pivot = True # p = row # break # if is_pivot: # A.swap_rows_c(p, r) # A.rescale_row_c(r, A.get_unsafe(r, c) ** (-1), 0) # for row in xrange(A.nrows()): # if row != r and A.get_unsafe(row, c) != 0: # A.add_multiple_of_row_c(row, r, -A.get_unsafe(row, c), 0) # P.append(c) # r += 1 # if r == A.nrows(): # break # return P # # cdef inline characteristic(LeanMatrix A): # # TODO: use caching for increased speed # return A.base_ring().characteristic()
cdef class LinearMatroid(BasisExchangeMatroid): r""" 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 object ``E`` can be given as a groundset. If ``E`` is a list, then ``E[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 of ``matrix`` and ``reduced_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 of ``matrix`` or the number of rows plus the number of columns of ``reduced_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 row-reduced copy.
OUTPUT:
A ``LinearMatroid`` instance based on the data above.
.. NOTE::
The recommended way to generate a linear matroid is through the :func:`Matroid() <sage.matroids.constructor.Matroid>` function. It will automatically choose more optimized classes when present (currently :class:`BinaryMatroid`, :class:`TernaryMatroid`, :class:`QuaternaryMatroid`, :class:`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 """ def __init__(self, matrix=None, groundset=None, reduced_matrix=None, ring=None, keep_initial_representation=True): """ See class definition for full documentation.
EXAMPLES::
sage: from sage.matroids.advanced import * sage: LinearMatroid(matrix=Matrix(GF(5), [[1, 0, 1, 1, 1], ....: [0, 1, 1, 2, 3]])) # indirect doctest Linear matroid of rank 2 on 5 elements represented over the Finite Field of size 5 """ else: raise ValueError("size of groundset does not match size of matrix")
def __dealloc__(self): """ Deallocate the memory.
EXAMPLES::
sage: from sage.matroids.advanced import * sage: M = LinearMatroid(matrix=Matrix(GF(5), [[1, 0, 1, 1, 1], ....: [0, 1, 1, 2, 3]])) # indirect doctest sage: M = None """
cdef list _setup_internal_representation(self, matrix, reduced_matrix, ring, keep_initial_representation): """ Setup the internal representation matrix ``self._A`` and the array of row- and column indices ``self._prow``.
Return the displayed basis. """ cdef LeanMatrix A cdef long r, c cdef list P else: else: else: else:
cpdef _forget(self): """ Remove the internal representation matrix.
When calling ``Matrix(M)`` after this, the lexicographically first basis will be used for the identity matrix.
EXAMPLES::
sage: from sage.matroids.advanced import * sage: M = LinearMatroid(matrix=Matrix(GF(5), [[1, 1, 0, 1, 1], ....: [0, 1, 1, 2, 3]])) sage: A = Matrix(M) sage: M._forget() sage: A == Matrix(M) False """
cpdef base_ring(self): """ 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 """
cpdef characteristic(self): """ 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 """
cdef bint __is_exchange_pair(self, long x, long y) except -1: r""" Check if ``self.basis() - x + y`` is again a basis. Internal method. """
cdef int __exchange(self, long x, long y) except -1: """ Put element indexed by ``x`` into basis, taking out element ``y``. Assumptions are that this is a valid basis exchange.
.. NOTE::
Safe for noncommutative rings. """ cdef long px, py, r
cdef __exchange_value(self, long x, long y): r""" Return the (x, y) entry of the current representation. """
# Sage functions
def _matrix_(self): """ Return a matrix representation of ``self``.
OUTPUT:
A matrix. Either this matrix is equal to the one originally supplied by the user, or its displayed basis is the lexicographically least basis of the matroid.
EXAMPLES::
sage: M = Matroid(matrix=Matrix(GF(5), [[1, 1, 0, 1, 1], ....: [0, 1, 1, 2, 3]])) sage: M._matrix_() [1 1 0 1 1] [0 1 1 2 3] sage: M._forget() sage: M._matrix_() [1 0 4 4 3] [0 1 1 2 3] """
def _repr_(self): """ Return a string representation of ``self``.
EXAMPLES::
sage: M = Matroid(matrix=Matrix(GF(5), [[1, 1, 0, 1, 1], ....: [0, 1, 1, 2, 3]])) sage: repr(M) # indirect doctest 'Linear matroid of rank 2 on 5 elements represented over the Finite Field of size 5' """
# representations
cpdef representation(self, 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 :func:`M.groundset_list() <sage.matroids.basis_exchange_matroid.BasisExchangeMatroid.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``) when ``True``, return a reduced matrix `D` (so `[I\ \ D]` is a representation of the matroid). Otherwise return a full representation matrix. - ``labels`` -- (default: ``None``) when ``True``, return additionally a list of column labels (if ``reduced=False``) or a list of row labels and a list of column labels (if ``reduced=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 to ``lift_map``.
OUTPUT:
- ``A`` -- a full or reduced representation matrix of ``self``; or - ``(A, E)`` -- a full representation matrix ``A`` and a list ``E`` of column labels; or - ``(A, R, C)`` -- a reduced representation matrix and a list ``R`` of row labels and a list ``C`` of column labels.
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.
If a ``lift_map`` is provided, then the resulting matrix will be lifted using the method :func:`lift_cross_ratios() <sage.matroids.utilities.lift_cross_ratios>` See the docstring of this method for further details.
.. 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] """ cdef LeanMatrix A else: raise ValueError("elements in argument ``order`` do not correspond to groundset of matroid.") else: else: else: else: if labels: return (lift_cross_ratios(A._matrix_(), lift_map), order) else: return lift_cross_ratios(A._matrix_(), lift_map) else: else: else: else: if labels or labels is None: return (lift_cross_ratios(A._matrix_(), lift_map), Rl, Cl) else: return lift_cross_ratios(A._matrix_(), lift_map)
cpdef _current_rows_cols(self, B=None): """ Return the current row and column labels of a reduced matrix.
INPUT:
- ``B`` -- (default: ``None``) If provided, first find a basis having maximal intersection with ``B``.
OUTPUT:
- ``R`` -- A list of row indices; corresponds to the currently used internal basis - ``C`` -- A list of column indices; corresponds to the complement of the current internal basis
EXAMPLES::
sage: M = matroids.named_matroids.Fano() sage: A = M._reduced_representation('efg') sage: R, C = M._current_rows_cols() sage: (sorted(R), sorted(C)) (['e', 'f', 'g'], ['a', 'b', 'c', 'd']) sage: R, C = M._current_rows_cols(B='abg') sage: (sorted(R), sorted(C)) (['a', 'b', 'g'], ['c', 'd', 'e', 'f'])
""" self._move_current_basis(B, set())
cpdef LeanMatrix _basic_representation(self, B=None): """ Return a basic matrix representation of the matroid.
INPUT:
- ``B`` -- (default: ``None``) a set of elements of the groundset.
OUTPUT:
A matrix `M` representing the matroid, where `M[B'] = I` for a basis `B'` that maximally intersects the given set `B`. If not provided, the current basis used internally is chosen for `B'`. For a stable representation, use ``self.representation()``.
.. NOTE::
The method self.groundset_list() gives the labelling of the columns by the elements of the matroid. The matrix returned is a LeanMatrix subclass, which is intended for internal use only. Use the ``representation()`` method to get a Sage matrix.
EXAMPLES::
sage: M = Matroid(reduced_matrix=Matrix(GF(7), [[1, 1, 1], ....: [1, 2, 3]])) sage: M._basic_representation() LeanMatrix instance with 2 rows and 5 columns over Finite Field of size 7 sage: matrix(M._basic_representation([3, 4])) [3 6 2 1 0] [5 1 6 0 1]
""" cdef LeanMatrix A cdef long i
cpdef representation_vectors(self): """ Return a dictionary that associates a column vector with each element of the matroid.
.. SEEALSO::
:meth:`M.representation() <LinearMatroid.representation>`
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)] """
cpdef LeanMatrix _reduced_representation(self, B=None): """ Return a reduced representation of the matroid, i.e. a matrix `R` such that `[I\ \ R]` represents the matroid.
INPUT:
- ``B`` -- (default: ``None``) a set of elements of the groundset.
OUTPUT:
A matrix `R` forming a reduced representation of the matroid, with rows labeled by a basis `B'` that maximally intersects the given set `B`. If not provided, the current basis used internally labels the rows.
.. NOTE::
The matrix returned is a LeanMatrix subclass, which is intended for internal use only. Use the ``representation()`` method to get a Sage matrix.
EXAMPLES::
sage: M = Matroid(reduced_matrix=Matrix(GF(7), [[1, 1, 1], ....: [1, 2, 3]])) sage: M._reduced_representation() LeanMatrix instance with 2 rows and 3 columns over Finite Field of size 7 sage: matrix(M._reduced_representation([3, 4])) [2 3 6] [6 5 1] """
# (field) isomorphism
cpdef bint _is_field_isomorphism(self, LinearMatroid other, morphism): # not safe if self == other """ Version of :meth:`<LinearMatroid.is_field_isomorphism>` that does no type checking.
INPUT:
- ``other`` -- A matroid instance, assumed to have the same base ring as ``self``. - ``morphism`` -- a dictionary mapping the groundset of ``self`` to the groundset of ``other``.
OUTPUT:
Boolean.
.. WARNING::
This method is not safe if ``self == other``.
EXAMPLES::
sage: from sage.matroids.advanced import * sage: M = matroids.named_matroids.Fano() \ ['g'] sage: N = BinaryMatroid(Matrix(matroids.Wheel(3))) sage: morphism = {'a':0, 'b':1, 'c': 2, 'd':4, 'e':5, 'f':3} sage: M._is_field_isomorphism(N, morphism) True """ # TODO: ensure this is safe for noncommutative rings global GF2, GF2_zero, GF2_one, GF2_not_defined
cpdef is_field_equivalent(self, 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.
.. SEEALSO::
:meth:`M.equals() <sage.matroids.matroid.Matroid.equals>`, :meth:`M.is_field_isomorphism() <LinearMatroid.is_field_isomorphism>`, :meth:`M.is_field_isomorphic() <LinearMatroid.is_field_isomorphic>`
EXAMPLES:
A :class:`BinaryMatroid` and :class:`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 """ return False
cpdef is_field_isomorphism(self, 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 of ``self`` to the groundset of ``other``. See documentation of the :meth:`M.is_isomorphism() <sage.matroids.matroid.Matroid.is_isomorphism>` method for more on what is accepted as input.
OUTPUT:
Boolean.
.. SEEALSO::
:meth:`M.is_isomorphism() <sage.matroids.matroid.Matroid.is_isomorphism>`, :meth:`M.is_field_equivalent() <LinearMatroid.is_field_equivalent>`, :meth:`M.is_field_isomorphic() <LinearMatroid.is_field_isomorphic>`
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 """ return False return False except (IndexError, TypeError, ValueError): try: for e in self.groundset(): mf[e] = morphism(e) except (TypeError, ValueError): raise TypeError("the morphism argument does not seem to be an isomorphism.") else: raise ValueError("domain of morphism does not contain groundset of this matroid.") raise ValueError("range of morphism does not contain groundset of other matroid.")
else:
cpdef _fast_isom_test(self, other): Fast (field) isomorphism test for some subclasses.
INPUT:
- ``other`` -- A ``LinearMatroid`` instance, of the same subclass as ``self``.
OUTPUT:
- ``None`` -- if the test is inconclusive; - ``True`` -- if the matroids were found to be field-isomorphic - ``False`` -- if the matroids were found to be non-field-isomorphic.
.. NOTE::
Intended for internal usage, in particular by the ``is_field_isomorphic`` method. Matroids are assumed to be in the same subclass.
EXAMPLES::
sage: from sage.matroids.advanced import * sage: M1 = BinaryMatroid(reduced_matrix=Matrix(GF(2), ....: [[1, 1, 0, 1], [1, 0, 1, 1], [0, 1, 1, 1]])) sage: M2 = LinearMatroid(reduced_matrix=Matrix(GF(2), ....: [[1, 1, 0, 1], [1, 0, 1, 1], [1, 1, 0, 1]])) sage: M3 = BinaryMatroid(reduced_matrix=Matrix(GF(2), ....: [[1, 1, 0, 1], [1, 0, 1, 1], [1, 1, 1, 0]])) sage: M2._fast_isom_test(M1) is None True sage: M1._fast_isom_test(M2) Traceback (most recent call last): ... AttributeError: 'sage.matroids.linear_matroid.LinearMatroid' object has no attribute '_invariant' sage: M1._fast_isom_test(M3) is None True sage: Matroid(graphs.WheelGraph(6), regular = True)._fast_isom_test( ....: matroids.Wheel(5)) True """ pass
def is_field_isomorphic(self, 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.
.. SEEALSO::
:meth:`M.is_isomorphic() <sage.matroids.matroid.Matroid.is_isomorphic>`, :meth:`M.is_field_isomorphism() <LinearMatroid.is_field_isomorphism>`, :meth:`M.is_field_equivalent() <LinearMatroid.is_field_equivalent>`
EXAMPLES::
sage: M1 = matroids.Wheel(3) sage: M2 = Matroid(graphs.CompleteGraph(4), regular = True) 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
""" return True return False return False return True return len(self.loops()) == len(other.loops())
return False return False morphism = {} for i in xrange(len(self)): morphism[min(PS[i])] = min(PO[i]) return self._is_field_isomorphism(other, morphism)
return False return False morphism = {} for i in xrange(len(self)): morphism[min(PS[i])] = min(PO[i]) return self._is_field_isomorphism(other, morphism)
def __richcmp__(left, right, op): r""" Compare two matroids.
We take a very restricted view on equality: the objects need to be of the exact same type (so no subclassing) and the internal data need to be the same. For linear matroids, in particular, this means field equivalence.
.. TODO::
In a user guide, write about "pitfalls": testing something like ``M in S`` could yield ``False``, even if ``N.equals(M)`` is ``True`` for some `N` in `S`.
.. WARNING::
This method is linked to __hash__. If you override one, you MUST override the other!
.. SEEALSO::
:meth:`<LinearMatroid.is_field_equivalent>`
EXAMPLES:
See docstring for :meth:`LinearMatroid.equals>` for more::
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 # indirect doctest True sage: M1 == M3 # indirect doctest True """ return NotImplemented else:
def __hash__(self): r""" Return an invariant of the matroid.
This function is called when matroids are added to a set. It is very desirable to override it so it can distinguish matroids on the same groundset, which is a very typical use case!
.. WARNING::
This method is linked to __richcmp__ (in Cython) and __cmp__ or __eq__/__ne__ (in Python). If you override one, you should (and in Cython: MUST) override the other!
EXAMPLES::
sage: M1 = Matroid(groundset='abcde', matrix=Matrix(GF(7), ....: [[1, 0, 1, 1, 1], [0, 1, 1, 2, 3]])) sage: M2 = Matroid(groundset='abcde', matrix=Matrix(GF(7), ....: [[0, 1, 1, 2, 3], [1, 0, 1, 1, 1]])) sage: hash(M1) == hash(M2) True sage: M2 = M1.dual() sage: hash(M1) == hash(M2) False """
# minors, dual
cpdef _minor(self, contractions, deletions): r""" Return a minor.
INPUT:
- ``contractions`` -- An object with Python's ``frozenset`` interface containing a subset of ``self.groundset()``. - ``deletions`` -- An object with Python's ``frozenset`` interface containing a subset of ``self.groundset()``.
.. NOTE::
This method does NOT do any checks. Besides the assumptions above, we assume the following:
- ``contractions`` is independent - ``deletions`` is coindependent - ``contractions`` and ``deletions`` are disjoint.
OUTPUT:
A matroid.
EXAMPLES::
sage: M = Matroid(groundset='abcdefgh', ring=GF(5), ....: reduced_matrix=[[2, 1, 1, 0], ....: [1, 1, 0, 1], [1, 0, 1, 1], [0, 1, 1, 2]]) sage: N = M._minor(contractions=set(['a']), deletions=set([])) sage: N._minor(contractions=set([]), deletions=set(['b', 'c'])) Linear matroid of rank 3 on 5 elements represented over the Finite Field of size 5 """ cdef LeanMatrix M
cpdef dual(self): """ 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
"""
cpdef has_line_minor(self, 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 returns ``True`` if `si(M/F)` is isomorphic to `U_{2, l}` with `l \geq k` for some `F` in ``hyperlines``, and ``False`` otherwise.
INPUT:
- ``k`` -- the length of the line minor - ``hyperlines`` -- (default: ``None``) a set of flats of codimension 2. Defaults to the set of all flats of codimension 2. - ``certificate`` (default: ``False``); If ``True`` returns ``True, F``, where ``F`` is a flat and ``self.minor(contractions=F)`` has a `U_{2,k}` restriction or ``False, None``.
OUTPUT:
Boolean or tuple.
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 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'}))
""" except TypeError: pass
cpdef has_field_minor(self, N): """ Check if ``self`` has a minor field isomorphic to ``N``.
INPUT:
- ``N`` -- A matroid.
OUTPUT:
Boolean.
.. SEEALSO::
:meth:`M.minor() <sage.matroids.matroid.Matroid.minor>`, :meth:`M.is_field_isomorphic() <LinearMatroid.is_field_isomorphic>`
.. 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.named_matroids.Fano().has_field_minor(M) False sage: matroids.named_matroids.NonFano().has_field_minor(M) True """ return True raise ValueError("N must be a matroid.") return False
return False
# cycles, cocycles and cross ratios
cpdef _exchange_value(self, e, f): """ Return the matrix entry indexed by row `e` and column `f`.
INPUT:
- ``e`` -- an element of the groundset. - ``f`` -- an element of the groundset.
``e`` should be in the currently active basis, and ``f`` in the currently active cobasis.
OUTPUT:
The (internal) matrix entry indexed by row `e` and column `f`.
.. WARNING::
Intended for internal use. This method does no checks of any kind.
EXAMPLES::
sage: M = Matroid(Matrix(GF(7), [[1, 0, 1, 1], [0, 1, 1, 4]])) sage: M._exchange_value(1, 3) 4 """
cpdef fundamental_cycle(self, B, e): """ Return the fundamental cycle, relative to ``B``, containing element ``e``.
This is the :meth:`fundamental circuit <sage.matroids.matroid.Matroid.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 matroid - ``e`` -- an element outside the basis
OUTPUT:
A dictionary mapping elements of ``M.fundamental_circuit(B, e)`` to elements of the ring.
.. SEEALSO::
:meth:`M.fundamental_circuit() <sage.matroids.matroid.Matroid.fundamental_circuit>`
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 """ return None
cpdef fundamental_cocycle(self, B, e): """ Return the fundamental cycle, relative to ``B``, containing element ``e``.
This is the :meth:`fundamental cocircuit <sage.matroids.matroid.Matroid.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 matroid - ``e`` -- an element of the basis
OUTPUT:
A dictionary mapping elements of ``M.fundamental_cocircuit(B, e)`` to elements of the ring.
.. SEEALSO::
:meth:`M.fundamental_cocircuit() <sage.matroids.matroid.Matroid.fundamental_cocircuit>`
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 None
cpdef _line_ratios(self, F): """ Return the set of nonzero ratios of column entries after contracting a rank-`r-2` flat ``F``.
.. WARNING::
Intended for internal use. Does no checking.
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._line_ratios(set([2]))) [1, 2, 4] sage: sorted(M._line_ratios([0])) [1, 5] """
cpdef _line_length(self, F): """ Return ``len(M.contract(F).simplify())``, where ``F`` is assumed to be a flat of rank 2 less than the matroid.
.. WARNING::
Intended for internal use. Does no checking.
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: M._line_length([2]) 5 sage: M._line_length([0]) 4 """
cpdef _line_cross_ratios(self, F): """ Return the set of cross ratios of column entries after contracting a rank-`r-2` flat ``F``.
Note that these are only the ordered cross ratios!
.. WARNING::
Intended for internal use. Does no checking.
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._line_cross_ratios(set([2]))) [2, 4] sage: sorted(M._line_cross_ratios([0])) [5] """
cpdef cross_ratios(self, hyperlines=None): r""" Return the set of cross ratios that occur in this linear matroid.
Consider the following matrix with columns labeled by `\{a, b, c, d\}`.
.. MATH::
\begin{matrix} 1 & 0 & 1 & 1\\ 0 & 1 & x & 1 \end{matrix}
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, then ``hyperlines`` defaults to all such flats.
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).
.. SEEALSO::
:meth:`M.cross_ratio() <LinearMatroid.cross_ratio>`
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) sage: M.cross_ratios() set() """
cpdef cross_ratio(self, F, a, b, c, d): r""" 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 `\{a, b, c, d\}`.
.. MATH::
\begin{bmatrix} 1 & 0 & 1 & 1\\ 0 & 1 & x & 1 \end{bmatrix}
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 than ``a, b, c, d`` are deleted.
INPUT:
- ``F`` -- A flat of codimension 2 - ``a, 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 4-point line in M/F
""" raise ValueError("set F must be subset of the groundset") raise ValueError("variables a, b, c, d need to be elements of the matroid") raise ValueError("set F must be a flat; F with a, b must span the matroid")
cpdef _line_cross_ratio_test(self, F, x, fundamentals): r""" Check whether the cross ratios involving a fixed element in a fixed rank-2 minor are in a specified subset.
INPUT:
- ``F`` -- a flat of codimension 2 - ``x`` -- an element outside ``F`` - ``fundamentals`` -- a set of fundamental elements.
OUTPUT:
``True`` if all cross ratios involving ``x`` are in ``fundamentals``; ``False`` otherwise.
.. NOTE::
This method is intended for checking extensions of a matroid, so it is assumed that the cross ratios of `(M/F)-x` are all in the desired subset. Moreover, the set of cross ratios is closed under reordering of the elements, i.e. if `x` is in ``fundamentals`` then also `1/x, 1-x, 1/(1-x), x/(x-1), (x-1)/x` are in it.
.. WARNING::
Intended for internal use. No checks whatsoever on validity of input.
EXAMPLES::
sage: M = Matroid(ring=QQ, reduced_matrix=[[1, 1, 1, 0], ....: [1, 1, 0, 1], [1, 0, 1, 1]]) sage: M._line_cross_ratio_test(set([0]), 6, set([1])) True sage: M._line_cross_ratio_test(set([4]), 6, set([1])) False sage: M._line_cross_ratio_test(set([4]), 6, set([1, 2, 1/2, -1])) True """ except ZeroDivisionError: return False
cpdef _cross_ratio_test(self, x, fundamentals, hyperlines=None): r""" Test if the cross ratios using a given element of this linear matroid are contained in a given set of fundamentals.
INPUT:
- ``x`` -- an element of the ground set - ``fundamentals`` -- a subset of the base ring - ``hyperlines`` (optional) -- a set of flats of rank=full_rank-2
OUTPUT:
Boolean. ``True`` if each cross ratio using ``x`` is an element of ``fundamentals``. If ``hyperlines`` is specified, then the method tests if each cross ratio in a minor that arises by contracting a flat ``F`` in ``hyperlines`` and uses ``x`` is in ``fundamentals``. If ``hyperlines`` is not specified, all flats of codimension 2 are tested.
.. NOTE::
This method is intended for checking extensions of a matroid, so it is assumed that the cross ratios of `M/F\setminus x` are all in the desired subset. Moreover, the set of fundamentals is closed under reordering of the elements, i.e. if `x \in` ``fundamentals`` then also `1/x, 1-x, 1/(1-x), x/(x-1), (x-1)/x` are in it.
EXAMPLES::
sage: M = Matroid(ring=QQ, reduced_matrix=[[1, 1, 1, 0], ....: [1, 1, 0, 1], [1, 0, 1, 1]]) sage: M._cross_ratio_test(6, set([1])) False sage: M._cross_ratio_test(6, set([1, 2, 1/2, -1])) True
""" return True
# linear extension cpdef linear_extension(self, element, chain=None, col=None): r""" 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 to ``self.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 by ``chain``.
.. SEEALSO::
:meth:`M.extension() <sage.matroids.matroid.Matroid.extension>`.
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]
""" cdef LeanMatrix cl cdef long i raise ValueError("extension element is already in groundset") raise ValueError("provided column has too many entries") raise ValueError("provided column has too few entries") raise ValueError("can only specify column relative to fixed representation. Run self._matrix_() first.") else: raise TypeError("chain argument needs to be a dictionary")
cpdef linear_coextension(self, element, cochain=None, row=None): r""" Return a linear coextension of this matroid.
A *linear coextension* of the represented matroid `M` by element `e` is a matroid represented by
.. MATH::
\begin{bmatrix} A & 0\\ -c & 1 \end{bmatrix},
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 :meth:`M.linear_extension() <LinearMatroid.linear_extension>`.
INPUT:
- ``element`` -- the name of the new element. - ``row`` -- (default: ``None``) a row to be appended to ``self.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 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.
.. SEEALSO::
:meth:`M.coextension() <sage.matroids.matroid.Matroid.coextension>`, :meth:`M.linear_extension() <LinearMatroid.linear_extension>`, :meth:`M.dual() <LinearMatroid.dual>`
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 """ cdef LeanMatrix col cdef LeanMatrix rw cdef long i raise ValueError("extension element is already in groundset") raise ValueError("provided row has too many entries") raise ValueError("provided row has too few entries") raise ValueError("can only specify row relative to fixed representation. Run self.representation() first.") else: raise TypeError("cochain argument needs to be a dictionary")
cpdef _linear_extensions(self, element, chains): r""" Return the linear extensions of this matroid representation specified by the given chains.
This is an internal method that does no checking on the input.
INPUT:
- ``element`` -- the name of the new element. - ``chains`` -- a list of dictionaries, each of which maps elements of the ground set to elements of the base ring.
OUTPUT:
A list of linear matroids `N = M([A b])`, where `A` is a matrix such that the current matroid is `M[A]`, and `b` is a weighted combination of columns of `A`, the weights being given by the elements of ``chains``.
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_extensions(6, [{0:1, 5: 1}])[0].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] """ cdef long i, j cdef LeanMatrix M else:
cpdef _linear_coextensions(self, element, cochains): r""" Return the linear coextensions of this matroid representation specified by the given cochains.
Internal method that does no typechecking.
INPUT:
- ``element`` -- the name of the new element. - ``cochains`` -- a list of dictionaries, each of which maps elements of the ground set to elements of the base ring.
OUTPUT:
A list of linear matroids `N = M([A 0; -c 1])`, where `A` is a matrix such that the current matroid is `M[A]`, and `c` has nonzero entries given by ``cochain``.
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_coextensions(6, [{0:1, 5: 1}])[0].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] """ cdef long i, j cdef LeanMatrix M else:
cdef _extend_chains(self, C, f, fundamentals=None): r""" Extend a list of chains for ``self / f`` to a list of chains for ``self``.
See :meth:`linear_extension_chains` for full documentation. """ # assumes connected self, non-loop f, chains with basic support else: else: # generate only chains that satisfy shallow test for 'crossratios in fundamentals' raise ValueError("_extend_chains can only extend chains with basic support")
cpdef _linear_extension_chains(self, F, fundamentals=None): # assumes independent F r""" Create a list of chains that determine single-element extensions of this linear matroid representation.
.. WARNING::
Intended for internal use; does no input checking.
INPUT:
- ``F`` -- an independent set of elements. - ``fundamentals`` -- (default: ``None``) a set elements of the base ring.
OUTPUT:
A list of chains, so each single-element extension of this linear matroid, with support contained in ``F``, is given by one of these 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(F=set([0, 1, 2]))) 8 sage: M._linear_extension_chains(F=set()) [{}] sage: M._linear_extension_chains(F=set([1])) [{}, {1: 1}] sage: len(M._linear_extension_chains(F=set([0, 1]))) 4 sage: N = Matroid(ring=QQ, reduced_matrix=[[1, 1, 0], ....: [1, 0, 1], [0, 1, 1]]) sage: N._linear_extension_chains(F=set([0, 1]), ....: fundamentals=set([1, -1, 1/2, 2])) [{0: 1}, {}, {0: 1, 1: 1}, {0: -1, 1: 1}, {1: 1}] """
else: comp_chains = {} # make chains for each component for comp in C: FM = F & comp A = self._max_independent(self.groundset() - comp) B = self.groundset() - (comp | A) M = self._minor(deletions=B, contractions=A) M._forget() comp_chains[comp] = M._linear_extension_chains(FM, fundamentals)
chains = [{}] # make Cartesian product of component chains for comp in comp_chains: new_chains = [] for c in chains: for d in comp_chains[comp]: c_new = copy(c) c_new.update(d) new_chains.append(c_new) chains = new_chains
cpdef linear_extension_chains(self, F=None, simple=False, fundamentals=None): r""" 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:
- ``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 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
- so that the support of each chain lies in ``F``, if given - so 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.
.. SEEALSO::
:meth:`M.linear_extension() <LinearMatroid.linear_extension>`, :meth:`M.linear_extensions() <LinearMatroid.linear_extensions>`, :meth:`M.cross_ratios() <LinearMatroid.cross_ratios>`
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}] """ else: # --> skips gauss-jordan reduction when taking minors of M # TODO: maybe make this an optional argument for _minor? # TODO: make sure the _representation isn't accidentally recreated anywhere (currently this only happens when self.representation() is called)
cpdef linear_coextension_cochains(self, F=None, cosimple=False, fundamentals=None): r""" 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 `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 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
- so that the support of each cochain lies in ``F``, if given - so 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.
.. SEEALSO::
:meth:`M.linear_coextension() <LinearMatroid.linear_coextension>`, :meth:`M.linear_coextensions() <LinearMatroid.linear_coextensions>`, :meth:`M.cross_ratios() <LinearMatroid.cross_ratios>`
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}] """
cpdef linear_extensions(self, element=None, F=None, simple=False, fundamentals=None): r""" Create a list of linear matroids represented by rank-preserving single-element 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 rank-preserving single-element 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 given - so 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.
.. SEEALSO::
:meth:`M.linear_extension() <LinearMatroid.linear_extension>`, :meth:`M.linear_extension_chains() <LinearMatroid.linear_extension_chains>`, :meth:`M.cross_ratios() <LinearMatroid.cross_ratios>`
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 """ else: if element in self.groundset(): raise ValueError("cannot extend by element already in groundset")
cpdef linear_coextensions(self, element=None, F=None, cosimple=False, fundamentals=None): r""" Create a list of linear matroids represented by corank-preserving single-element 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 corank-preserving single-element 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.
.. SEEALSO::
:meth:`M.linear_coextension() <LinearMatroid.linear_coextension>`, :meth:`M.linear_coextension_cochains() <LinearMatroid.linear_coextension_cochains>`, :meth:`M.cross_ratios() <LinearMatroid.cross_ratios>`
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 """ else: if element in self.groundset(): raise ValueError("cannot extend by element already in groundset")
cpdef is_valid(self): r""" 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.
.. SEEALSO::
:meth:`M.cross_ratios() <LinearMatroid.cross_ratios>`
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 """ except (ArithmeticError, TypeError, ValueError): return False return True
# connectivity
cpdef _is_3connected_shifting(self, certificate=False): r""" Return ``True`` if the matroid is 4-connected, ``False`` otherwise. It can optionally return a separator as a witness.
INPUT:
- ``certificate`` -- (default: ``False``) a boolean; if ``True``, then return ``True, None`` if the matroid is 3-connected, and ``False,`` `X` otherwise, where `X` is a `<3`-separation
OUTPUT:
boolean, or a tuple ``(boolean, frozenset)``
ALGORITHM:
The shifting algorithm
EXAMPLES::
sage: matroids.Uniform(2, 3)._is_3connected_shifting() True sage: M = Matroid(ring=QQ, matrix=[[1, 0, 0, 1, 1, 0], ....: [0, 1, 0, 1, 2, 0], ....: [0, 0, 1, 0, 0, 1]]) sage: M._is_3connected_shifting() False sage: N = Matroid(circuit_closures={2: ['abc', 'cdef'], ....: 3: ['abcdef']}, ....: groundset='abcdef') sage: N._is_3connected_shifting() False sage: matroids.named_matroids.BetsyRoss()._is_3connected_shifting() True sage: M = matroids.named_matroids.R6() sage: M._is_3connected_shifting() False sage: B, X = M._is_3connected_shifting(True) sage: M.connectivity(X)<3 True """ return False, self.components()[0] else: return self.dual()._is_3connected_shifting(certificate)
# the partial matrix
# create mapping between elements and columns
return True, None
cpdef _is_4connected_shifting(self, certificate=False): r""" Return ``True`` if the matroid is 4-connected, ``False`` otherwise. It can optionally return a separator as a witness.
INPUT:
- ``certificate`` -- (default: ``False``) a boolean; if ``True``, then return ``True, None`` if the matroid is 4-connected, and ``False,`` `X` otherwise, where `X` is a `<4`-separation
OUTPUT:
boolean, or a tuple ``(boolean, frozenset)``
ALGORITHM:
The shifting algorithm
EXAMPLES::
sage: M = matroids.Uniform(2, 6) sage: B, X = M._is_4connected_shifting(True) sage: (B, M.connectivity(X)<=3) (False, True) sage: matroids.Uniform(4, 8)._is_4connected_shifting() True sage: M = Matroid(field=GF(2), matrix=[[1,0,0,1,0,1,1,0,0,1,1,1], ....: [0,1,0,1,0,1,0,1,0,0,0,1], ....: [0,0,1,1,0,0,1,1,0,1,0,1], ....: [0,0,0,0,1,1,1,1,0,0,1,1], ....: [0,0,0,0,0,0,0,0,1,1,1,1]]) sage: M._is_4connected_shifting() True """ return self.dual()._is_4connected_shifting(certificate) return self._is_3connected_shifting(certificate)
# the partial matrix
# The whiting out
# remove row x1 and y1
# produce a spanning forest of B # rank 2 matrix and rank 0 matrix # make sure the matrix has rank 2 break # rank 1 matrix and rank 1 matrix # both matrix have rank 1 break if certificate: (certX, certY) = cert_pair cert = set([]) for x in certX: cert.add(dX[x]) for y in certY: cert.add(dY[y]) return False, cert return False return True, None
# Copying, loading, saving
def __copy__(self): """ Create a shallow copy.
EXAMPLES::
sage: M = Matroid(Matrix(GF(7), [[1, 0, 0, 1, 1], [0, 1, 0, 1, 2], ....: [0, 0, 1, 1, 3]])) sage: N = copy(M) # indirect doctest sage: M == N True """ cdef LinearMatroid N else: rows, cols = self._current_rows_cols() N = LinearMatroid(groundset=rows + cols, reduced_matrix=self._A)
def __deepcopy__(self, memo): """ Create a deep copy.
EXAMPLES::
sage: M = Matroid(Matrix(GF(7), [[1, 0, 0, 1, 1], [0, 1, 0, 1, 2], ....: [0, 0, 1, 1, 3]])) sage: N = deepcopy(M) # indirect doctest sage: M == N True """ cdef LinearMatroid N else: rows, cols = self._current_rows_cols() N = LinearMatroid(groundset=deepcopy(rows + cols, memo), reduced_matrix=deepcopy(self._A, memo))
def __reduce__(self): """ Save the matroid for later reloading.
OUTPUT:
A tuple ``(unpickle_lean_linear_matroid, (version, data))``, where ``unpickle_lean_linear_matroid`` is the name of a function that, when called with ``(version, data)``, produces a matroid isomorphic to ``self``. ``version`` is an integer (currently 0) and ``data`` is a tuple ``(A, E, reduced, name)`` where ``A`` is the representation matrix, ``E`` is the groundset of the matroid, ``reduced`` is a boolean indicating whether ``A`` is a reduced matrix, and ``name`` is a custom name.
.. WARNING::
Users should never call this function directly.
EXAMPLES::
sage: M = Matroid(Matrix(GF(7), [[1, 0, 0, 1, 1], [0, 1, 0, 1, 2], ....: [0, 0, 1, 1, 3]])) sage: M == loads(dumps(M)) # indirect doctest True sage: M.rename("U35") sage: loads(dumps(M)) U35 sage: M = Matroid(Matrix(GF(7), [[1, 0, 1], [1, 0, 1]])) sage: N = loads(dumps(M)) sage: N.representation() [1 0 1] [1 0 1] """ cdef LeanMatrix A else: A = self._reduced_representation() rows, cols = self._current_rows_cols() gs = rows + cols reduced = True
# Binary matroid
cdef class BinaryMatroid(LinearMatroid): r""" Binary matroids.
A binary matroid is a linear matroid represented over the finite field with two elements. See :class:`LinearMatroid` for a definition.
The simplest way to create a ``BinaryMatroid`` is by giving only a matrix `A`. 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 `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 of ``matrix`` and ``reduced_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 of ``matrix`` or the number of rows plus the number of columns of ``reduced_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 row-reduced copy. - ``basis`` -- (default: ``None``) When provided, this is an ordered subset of ``groundset``, such that the submatrix of ``matrix`` indexed by ``basis`` is an identity matrix. In this case, no row reduction takes place in the initialization phase.
OUTPUT:
A :class:`BinaryMatroid` instance based on the data above.
.. NOTE::
An indirect way to generate a binary matroid is through the :func:`Matroid() <sage.matroids.constructor.Matroid>` function. This is usually the preferred way, since it automatically chooses between :class:`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 """ def __init__(self, matrix=None, groundset=None, reduced_matrix=None, ring=None, keep_initial_representation=True, basis=None): """ See class definition for full documentation.
.. NOTE::
The extra argument ``basis``, when provided, is an ordered list of elements of the groundset, ordered such that they index a standard identity matrix within ``matrix``.
EXAMPLES::
sage: from sage.matroids.advanced import * sage: BinaryMatroid(matrix=Matrix(GF(5), [[1, 0, 1, 1, 1], ....: [0, 1, 1, 2, 3]])) # indirect doctest Binary matroid of rank 2 on 5 elements, type (1, 7) """ cdef BinaryMatrix A cdef long r, c cdef list P global GF2, GF2_zero, GF2_one, GF2_not_defined
# Setup representation; construct displayed basis else:
# Setup groundset, BasisExchangeMatroid data else: raise ValueError("size of groundset does not match size of matrix") else:
# Setup index of displayed basis else: else:
cpdef base_ring(self): """ Return the base ring of the matrix representing the matroid, in this case `\GF{2}`.
EXAMPLES::
sage: M = matroids.named_matroids.Fano() sage: M.base_ring() Finite Field of size 2 """ global GF2
cpdef characteristic(self): """ Return the characteristic of the base ring of the matrix representing the matroid, in this case `2`.
EXAMPLES::
sage: M = matroids.named_matroids.Fano() sage: M.characteristic() 2 """
cdef bint __is_exchange_pair(self, long x, long y) except -1: r""" Check if ``self.basis() - x + y`` is again a basis. Internal method. """
cdef int __exchange(self, long x, long y) except -1: r""" Replace ``self.basis() with ``self.basis() - x + y``. Internal method, does no checks. """
cdef __fundamental_cocircuit(self, bitset_t C, long x): r""" Fill bitset `C` with the incidence vector of the `B`-fundamental cocircuit using ``x``. Internal method using packed elements. """
cdef __coclosure(self, bitset_t R, bitset_t F): """ Bitpacked version of ``coclosure``.
This function overrides the internal function BasisExchangeMatroid.__coclosure() of the parent class. The implementation should be more efficient for BinaryMatroid, due to the fact that in this class, __fundamental_cocircuit is much faster than __fundamental_circuit. """
cdef __exchange_value(self, long x, long y): r""" Return the (x, y) entry of the current representation. """ else:
def _repr_(self): """ Return a string representation of ``self``.
The type consists of :meth:`BinaryMatroid.bicycle_dimension` and :meth:`BinaryMatroid.brown_invariant`.
EXAMPLES::
sage: M = matroids.named_matroids.Fano() sage: M.rename() sage: repr(M) # indirect doctest 'Binary matroid of rank 3 on 7 elements, type (3, 0)' """
cpdef _current_rows_cols(self, B=None): """ Return the current row and column labels of a reduced matrix.
INPUT:
- ``B`` -- (default: ``None``) If provided, first find a basis having maximal intersection with ``B``.
OUTPUT:
- ``R`` -- A list of row indices; corresponds to the currently used internal basis - ``C`` -- A list of column indices; corresponds to the complement of the current internal basis
EXAMPLES::
sage: M = matroids.named_matroids.Fano() sage: A = M._reduced_representation('efg') sage: R, C = M._current_rows_cols() sage: (sorted(R), sorted(C)) (['e', 'f', 'g'], ['a', 'b', 'c', 'd']) sage: R, C = M._current_rows_cols(B='abg') sage: (sorted(R), sorted(C)) (['a', 'b', 'g'], ['c', 'd', 'e', 'f'])
""" else:
cpdef LeanMatrix _basic_representation(self, B=None): """ Return a basic matrix representation of the matroid.
INPUT:
- ``B`` -- (default: ``None``) a set of elements of the groundset.
OUTPUT:
A matrix `M` representing the matroid, where `M[B'] = I` for a basis `B'` that maximally intersects the given set `B`. If not provided, the current basis used internally is chosen for `B'`. For a stable representation, use ``self.representation()``.
.. NOTE::
The method self.groundset_list() gives the labelling of the columns by the elements of the matroid. The matrix returned is a LeanMatrix subclass, which is intended for internal use only. Use the ``representation()`` method to get a Sage matrix.
EXAMPLES::
sage: M = matroids.named_matroids.Fano() sage: M._basic_representation() 3 x 7 BinaryMatrix [1000111] [0101011] [0011101] sage: matrix(M._basic_representation('efg')) [1 1 0 1 1 0 0] [1 0 1 1 0 1 0] [1 1 1 0 0 0 1] """
cpdef LeanMatrix _reduced_representation(self, B=None): """ Return a reduced representation of the matroid, i.e. a matrix `R` such that `[I\ \ R]` represents the matroid.
INPUT:
- ``B`` -- (default: ``None``) a set of elements of the groundset.
OUTPUT:
A matrix `R` forming a reduced representation of the matroid, with rows labeled by a basis `B'` that maximally intersects the given set `B`. If not provided, the current basis used internally labels the rows.
.. NOTE::
The matrix returned is a LeanMatrix subclass, which is intended for internal use only. Use the ``representation()`` method to get a Sage matrix.
EXAMPLES::
sage: M = matroids.named_matroids.Fano() sage: M._reduced_representation() 3 x 4 BinaryMatrix [0111] [1011] [1101] sage: matrix(M._reduced_representation('efg')) [1 1 0 1] [1 0 1 1] [1 1 1 0] """
# isomorphism
cpdef _is_isomorphic(self, other, certificate=False): """ Test if ``self`` is isomorphic to ``other``.
Internal version that performs no checks on input.
INPUT:
- ``other`` -- A matroid, - optional parameter ``certificate`` -- Boolean.
OUTPUT:
Boolean, and, if certificate = True, a dictionary giving the isomorphism or None
.. NOTE::
Internal version that does no input checking.
EXAMPLES::
sage: M1 = matroids.named_matroids.Fano() sage: M2 = Matroid(ring=GF(2), ....: reduced_matrix=[[1, 0, 1, 1], [0, 1, 1, 1], [1, 1, 0, 1]]) sage: M1._is_isomorphic(M2) True sage: M1._is_isomorphic(M2, certificate=True) (True, {'a': 0, 'b': 1, 'c': 2, 'd': 4, 'e': 3, 'f': 5, 'g': 6})
sage: M1 = matroids.named_matroids.Fano().delete('a') sage: M2 = matroids.Whirl(3) sage: M1._is_isomorphic(M2) False sage: M1._is_isomorphic(M2, certificate=True) (False, None) sage: M1._is_isomorphic(matroids.Wheel(3)) True sage: M1._is_isomorphic(matroids.Wheel(3), certificate=True) (True, {'b': 1, 'c': 2, 'd': 4, 'e': 3, 'f': 5, 'g': 0})
""" else:
cpdef _is_isomorphism(self, other, morphism): r""" Test if a given bijection is an isomorphism.
Version of ``is_isomorphism()`` that does no type checking of ``morphism``.
INPUT:
- ``other`` -- A matroid instance. - ``morphism`` -- a dictionary mapping the groundset of ``self`` to the groundset of ``other``
OUTPUT:
Boolean.
EXAMPLES::
sage: M = matroids.named_matroids.Fano() \ ['a'] sage: N = matroids.named_matroids.Fano() \ ['b'] sage: morphism = {'b':'a', 'c':'c', 'd':'e', 'e':'d', 'f':'f', 'g':'g'} sage: M._is_isomorphism(N, morphism) True """ else:
# invariants cpdef _make_invariant(self): """ Create an invariant.
Internal method; see ``_invariant`` for full documentation.
EXAMPLES::
sage: M = matroids.named_matroids.Fano() sage: M._invariant() # indirect doctest (3, 0, 7, 0, 0, 0, 0, 0) """ cdef BinaryMatrix B cdef long r, d, i, j return else: else: else: else:
else:
cpdef _invariant(self): r""" Return a matroid invariant.
See [Pen2012]_ for more information.
OUTPUT:
A tuple ``(d, b, Lm, L0, Lp, p0, p1, p2)``, with the following interpretation:
- ``d`` is the :meth:`bicycle dimension <BinaryMatroid.bicycle_dimension>`. - ``b`` is the :meth:`Brown invariant <BinaryMatroid.brown_invariant>`. - ``(Lm, L0, Lp)`` is the triple of lengths of the principal tripartition. - ``(p0, p1, p2)`` are the counts of edges in a characteristic graph of the matroid, whose vertices are the union of ``F_-`` and ``F_0`` from the principal tripartition.
EXAMPLES::
sage: from sage.matroids.advanced import * sage: M = BinaryMatroid(matroids.AG(2, 5).representation()) sage: M._invariant() (2, 1, 24, 0, 1, 0, 0, 1) """
cpdef bicycle_dimension(self): r""" 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 cocycle-space, and is an invariant for binary matroids. See [Pen2012]_, [GR2001]_ for more information.
OUTPUT:
Integer.
EXAMPLES::
sage: M = matroids.named_matroids.Fano() sage: M.bicycle_dimension() 3 """
cpdef brown_invariant(self): r""" 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 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 """
cpdef _principal_tripartition(self): r""" Return the principal tripartition of the binary matroid.
The principal tripartition is a partition `(F_{-1}, F_0, F_{1})` of the ground set. A defining property is the following. It is straightforward that if the bicycle dimension of a matroid `M` is `k`, then the bicycle dimension of `M\setminus e' is one of `k-1, k, k + 1` for each element `e` of `M`. Then if `F_i` denotes the set of elements such that the bicycle dimension of `M\setminus e` is `k + i`, we obtain the principal tripartition `(F_{-1}, F_0, F_{1})` of `M`. See [Pen2012]_ and [GR2001]_.
OUTPUT:
``(F_{-1}, F_0, F_{1})``, the principal tripartition of the matroid.
EXAMPLES::
sage: M = matroids.named_matroids.S8() sage: for F in M._principal_tripartition(): print(sorted(F)) ['a', 'b', 'c', 'e', 'f', 'g'] ['d'] ['h'] sage: M.bicycle_dimension() 2 sage: for i in [-1, 0, 1]: print(sorted([e for e in M.groundset() if (M\e).bicycle_dimension() == 2 + i])) ['a', 'b', 'c', 'e', 'f', 'g'] ['d'] ['h'] """ self._make_invariant()
cpdef BinaryMatrix _projection(self): """ Return the projection matrix onto the row space.
This projection is determined modulo the bicycle space. See [Pen2012]_.
INPUT:
- Nothing
OUTPUT:
A binary matrix `P`, so that the `e`-th column of `P` is the incidence vector of a cocycle `C` such that `C-e` is a cycle. Such a `C` is determined up to taking the symmetric difference with bicycles. We output the restriction of `P` to rows and columns that are not in any bicycle.
EXAMPLES::
sage: from sage.matroids.advanced import * sage: M = BinaryMatroid(matrix(matroids.named_matroids.R12())) sage: M._projection() 12 x 12 BinaryMatrix [001110111000] [001101110100] [111011100010] [110111010001] [101100001011] [011100000111] [111000101110] [110100011101] [100010110011] [010001110011] [001011101110] [000111011101]
"""
cpdef BinaryMatrix _projection_partition(self): """ Return the equitable partition of the graph whose incidence matrix is the projection matrix of this matroid.
See method ``._projection()``.
INPUT:
- Nothing
OUTPUT:
An ordered partition.
sage: from sage.matroids.advanced import * sage: M = matroids.named_matroids.R12() sage: N = BinaryMatroid(reduced_matrix=M.representation(reduced=True, ....: labels=False), groundset='abcdefghijkl') sage: N._projection_partition() 2 x 12 BinaryMatrix [110011001100] [001100110011] """
cpdef _fast_isom_test(self, other): r""" Run a quick test to see if two binary matroids are isomorphic.
The test is based on comparing strong invariants. See [Pen2012]_ for a full account of these invariants.
INPUT:
- ``other`` -- a binary matroid.
OUTPUT:
- ``True``, if ``self`` is isomorphic to ``other``; - ``False``, if ``self`` is not isomorphic to ``other``; - ``None``, if this test is inconclusive
EXAMPLES::
sage: M = matroids.named_matroids.S8() sage: N = matroids.named_matroids.S8() sage: M._fast_isom_test(N) is None True """ return q return False
# minors, dual
cpdef _minor(self, contractions, deletions): r""" Return a minor.
INPUT:
- ``contractions`` -- An object with Python's ``frozenset`` interface containing a subset of ``self.groundset()``. - ``deletions`` -- An object with Python's ``frozenset`` interface containing a subset of ``self.groundset()``.
.. NOTE::
This method does NOT do any checks. Besides the assumptions above, we assume the following:
- ``contractions`` is independent - ``deletions`` is coindependent - ``contractions`` and ``deletions`` are disjoint.
OUTPUT:
A matroid.
EXAMPLES::
sage: M = matroids.named_matroids.Fano() sage: N = M._minor(contractions=set(['a']), deletions=set([])) sage: N._minor(contractions=set([]), deletions=set(['b', 'c'])) Binary matroid of rank 2 on 4 elements, type (0, 6) """
# graphicness test cpdef is_graphic(self): """ 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 = Matroid(graphs.CompleteGraph(5), regular = True) 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
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 2-separations especially), it is easy to implement. """ global GF2 cdef int r, c
# now self is graphic iff there is a binary vector x so that M*x = 0 and x_0 = 1, so:
cpdef is_valid(self): r""" 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 """
# representability
cpdef binary_matroid(self, randomized_tests=1, verify = True): r""" Return a binary matroid representing ``self``.
INPUT:
- ``randomized_tests`` -- Ignored. - ``verify`` -- Ignored
OUTPUT:
A binary matroid.
ALGORITHM:
``self`` is a binary matroid, so just return ``self``.
.. SEEALSO::
:meth:`M.binary_matroid() <sage.matroids.matroid.Matroid.binary_matroid>`
EXAMPLES::
sage: N = matroids.named_matroids.Fano() sage: N.binary_matroid() is N True """
cpdef is_binary(self, randomized_tests=1): r""" Decide if ``self`` is a binary matroid.
INPUT:
- ``randomized_tests`` -- Ignored.
OUTPUT:
A Boolean.
ALGORITHM:
``self`` is a binary matroid, so just return ``True``.
.. SEEALSO::
:meth:`M.is_binary() <sage.matroids.matroid.Matroid.is_binary>`
EXAMPLES::
sage: N = matroids.named_matroids.Fano() sage: N.is_binary() True """
def __copy__(self): """ Create a shallow copy.
EXAMPLES::
sage: M = Matroid(Matrix(GF(2), [[1, 0, 0, 1, 1], [0, 1, 0, 1, 2], ....: [0, 0, 1, 1, 3]])) sage: N = copy(M) # indirect doctest sage: M == N True """ cdef BinaryMatroid N cdef list basis else:
def __deepcopy__(self, memo): """ Create a deep copy.
EXAMPLES::
sage: M = Matroid(Matrix(GF(2), [[1, 0, 0, 1, 1], [0, 1, 0, 1, 2], ....: [0, 0, 1, 1, 3]])) sage: N = deepcopy(M) # indirect doctest sage: M == N True """ cdef BinaryMatroid N cdef list basis else: basis = [0] * self.full_rank() for e in self.basis(): basis[self._prow[self._idx[e]]] = e N = BinaryMatroid(groundset=deepcopy(self._E, memo), matrix=deepcopy(self._A, memo), basis=deepcopy(basis, memo))
def __reduce__(self): """ Save the matroid for later reloading.
OUTPUT:
A tuple ``(unpickle_binary_matroid, (version, data))``, where ``unpickle_binary_matroid`` is the name of a function that, when called with ``(version, data)``, produces a matroid isomorphic to ``self``. ``version`` is an integer (currently 0) and ``data`` is a tuple ``(A, E, B, name)`` where ``A`` is the representation matrix, ``E`` is the groundset of the matroid, ``B`` is the currently displayed basis, and ``name`` is a custom name.
.. WARNING::
Users should never call this function directly.
EXAMPLES::
sage: M = Matroid(Matrix(GF(2), [[1, 0, 0, 1], [0, 1, 0, 1], ....: [0, 0, 1, 1]])) sage: M == loads(dumps(M)) # indirect doctest True sage: M.rename("U34") sage: loads(dumps(M)) U34 sage: M = Matroid(Matrix(GF(2), [[1, 0, 1], [1, 0, 1]])) sage: loads(dumps(M)).representation() [1 0 1] [1 0 1] """ else: A = self._A for e in self.basis(): basis[self._prow[self._idx[e]]] = e rows, cols = self._current_rows_cols() gs = rows + cols
cdef class TernaryMatroid(LinearMatroid): r""" Ternary matroids.
A ternary matroid is a linear matroid represented over the finite field with three elements. See :class:`LinearMatroid` for a definition.
The simplest way to create a ``TernaryMatroid`` is by giving only a matrix `A`. 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 `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 of ``matrix`` and ``reduced_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 of ``matrix`` or the number of rows plus the number of columns of ``reduced_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 row-reduced copy. - ``basis`` -- (default: ``None``) when provided, this is an ordered subset of ``groundset``, such that the submatrix of ``matrix`` indexed by ``basis`` 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 :func:`Matroid() <sage.matroids.constructor.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 """ def __init__(self, matrix=None, groundset=None, reduced_matrix=None, ring=None, keep_initial_representation=True, basis=None): """ See class definition for full documentation.
.. NOTE::
The extra argument ``basis``, when provided, is an ordered list of elements of the groundset, ordered such that they index a standard identity matrix within ``matrix``.
EXAMPLES::
sage: from sage.matroids.advanced import * sage: TernaryMatroid(matrix=Matrix(GF(5), [[1, 0, 1, 1, 1], ....: [0, 1, 1, 2, 3]])) # indirect doctest Ternary matroid of rank 2 on 5 elements, type 1+ """ cdef TernaryMatrix A cdef long r, c cdef list P global GF3, GF3_zero, GF3_one, GF3_minus_one, GF3_not_defined
# Setup representation; construct displayed basis else:
# Setup groundset, BasisExchangeMatroid data else: raise ValueError("size of groundset does not match size of matrix") else:
# Setup index of displayed basis else: else:
cpdef base_ring(self): """ Return the base ring of the matrix representing the matroid, in this case `\GF{3}`.
EXAMPLES::
sage: M = matroids.named_matroids.NonFano() sage: M.base_ring() Finite Field of size 3 """ global GF3
cpdef characteristic(self): """ Return the characteristic of the base ring of the matrix representing the matroid, in this case `3`.
EXAMPLES::
sage: M = matroids.named_matroids.NonFano() sage: M.characteristic() 3 """
cdef bint __is_exchange_pair(self, long x, long y) except -1: r""" Check if ``self.basis() - x + y`` is again a basis. Internal method. """
cdef int __exchange(self, long x, long y) except -1: r""" Replace ``self.basis() with ``self.basis() - x + y``. Internal method, does no checks. """
cdef __fundamental_cocircuit(self, bitset_t C, long x): r""" Fill bitset `C` with the incidence vector of the `B`-fundamental cocircuit using ``x``. Internal method using packed elements. """
cdef __coclosure(self, bitset_t R, bitset_t F): """ Bitpacked version of ``coclosure``.
This function overrides the internal function BasisExchangeMatroid.__coclosure() of the parent class. The implementation should be more efficient for TernaryMatroid, due to the fact that in this class, __fundamental_cocircuit is much faster than __fundamental_circuit. """
bitset_add(R, y)
cdef __exchange_value(self, long x, long y): r""" Return the (x, y) entry of the current representation. """
def _repr_(self): """ Return a string representation of ``self``.
The type consists of the ``bicycle_dimension`` and the ``character``.
EXAMPLES::
sage: M = matroids.named_matroids.NonFano() sage: M.rename() sage: repr(M) # indirect doctest 'Ternary matroid of rank 3 on 7 elements, type 0-' """ else:
cpdef _current_rows_cols(self, B=None): """ Return the current row and column labels of a reduced matrix.
INPUT:
- ``B`` -- (default: ``None``) If provided, first find a basis having maximal intersection with ``B``.
OUTPUT:
- ``R`` -- A list of row indices; corresponds to the currently used internal basis - ``C`` -- A list of column indices; corresponds to the complement of the current internal basis
EXAMPLES::
sage: M = matroids.named_matroids.NonFano() sage: A = M._reduced_representation('efg') sage: R, C = M._current_rows_cols() sage: (sorted(R), sorted(C)) (['e', 'f', 'g'], ['a', 'b', 'c', 'd']) sage: R, C = M._current_rows_cols(B='abg') sage: (sorted(R), sorted(C)) (['a', 'b', 'g'], ['c', 'd', 'e', 'f'])
""" else:
cpdef LeanMatrix _basic_representation(self, B=None): """ Return a basic matrix representation of the matroid.
INPUT:
- ``B`` -- (default: ``None``) a set of elements of the groundset.
OUTPUT:
A matrix `M` representing the matroid, where `M[B'] = I` for a basis `B'` that maximally intersects the given set `B`. If not provided, the current basis used internally is chosen for `B'`. For a stable representation, use ``self.representation()``.
.. NOTE::
The method self.groundset_list() gives the labelling of the columns by the elements of the matroid. The matrix returned is a LeanMatrix subclass, which is intended for internal use only. Use the ``representation()`` method to get a Sage matrix.
EXAMPLES::
sage: M = matroids.named_matroids.NonFano() sage: M._basic_representation() 3 x 7 TernaryMatrix [+000+++] [0+0+0++] [00+++0+] sage: matrix(M._basic_representation('efg')) [1 2 0 2 1 0 0] [1 0 2 2 0 1 0] [2 1 1 2 0 0 1] """
cpdef LeanMatrix _reduced_representation(self, B=None): """ Return a reduced representation of the matroid, i.e. a matrix `R` such that `[I\ \ R]` represents the matroid.
INPUT:
- ``B`` -- (default: ``None``) a set of elements of the groundset.
OUTPUT:
A matrix `R` forming a reduced representation of the matroid, with rows labeled by a basis `B'` that maximally intersects the given set `B`. If not provided, the current basis used internally labels the rows.
.. NOTE::
The matrix returned is a LeanMatrix subclass, which is intended for internal use only. Use the ``representation()`` method to get a Sage matrix.
EXAMPLES::
sage: M = matroids.named_matroids.NonFano() sage: M._reduced_representation() 3 x 4 TernaryMatrix [0+++] [+0++] [++0+] sage: matrix(M._reduced_representation('efg')) [1 2 0 2] [1 0 2 2] [2 1 1 2] """
# isomorphism
cpdef _is_isomorphic(self, other, certificate=False): """ Test if ``self`` is isomorphic to ``other``. Internal version that performs no checks on input.
INPUT:
- ``other`` -- A matroid, - optional parameter ``certificate`` -- Boolean.
OUTPUT:
Boolean, and, if certificate = True, a dictionary giving the isomorphism or None
.. NOTE::
Internal version that does no input checking.
EXAMPLES::
sage: M1 = matroids.named_matroids.NonFano().delete('a') sage: M2 = matroids.Whirl(3) sage: M1._is_isomorphic(M2) True
sage: M2 = matroids.Wheel(3) sage: M1._is_isomorphic(M2) False """ return self._is_isomorphic(other), self._isomorphism(other) else:
# invariants
cpdef _make_invariant(self): """ Create an invariant.
Internal method; see ``_invariant`` for full documentation.
EXAMPLES::
sage: M = matroids.named_matroids.NonFano() sage: M._invariant() # indirect doctest (0, 2, 0, 4, 3, 0, 12, 12, 3, 0, 0, 0) """ cdef TernaryMatrix T cdef long i, j, d, r, x, y global GF3
return else: else:
cpdef _invariant(self): r""" Return a matroid invariant.
See [Pen2012]_ for more information.
OUTPUT:
A tuple ``(d, c, L, La, Lb, Lc, p0, p1, p2, p3, p4, p5)``, with the following interpretation:
- ``d`` is the bicycle dimension. - ``c`` is the character. - ``(L, La, Lb, Lc)`` is the triple of lengths of the principal quadripartition. - ``(p0, ..., p5)`` counts of edges in a characteristic graph of the matroid whose vertex set is the ground set of the matroid, restricted to the sets in the principal quadripartition.
EXAMPLES::
sage: M = matroids.named_matroids.NonFano() sage: M._invariant() (0, 2, 0, 4, 3, 0, 12, 12, 3, 0, 0, 0) """
cpdef bicycle_dimension(self): """ 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.named_matroids.NonFano() sage: M.bicycle_dimension() 0 """
cpdef character(self): r""" 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 cocycle-space, and is an invariant for ternary matroids. See [Pen2012]_.
OUTPUT:
Integer.
EXAMPLES::
sage: M = matroids.named_matroids.NonFano() sage: M.character() 2 """ self._make_invariant()
cpdef _principal_quadripartition(self): r""" Return an ordered partition of the ground set.
The partition groups each element `e` of the ground set according to the bicycle dimension and the character of `M/e`, where `M` is the present matroid.
EXAMPLES::
sage: M = matroids.named_matroids.N1() sage: print(M) N1: Ternary matroid of rank 5 on 10 elements, type 0+ sage: P = M._principal_quadripartition() sage: for e in sorted(P[0]): print("{} {}".format(e, M/e)) sage: for e in sorted(P[1]): print("{} {}".format(e, M/e)) a Ternary matroid of rank 4 on 9 elements, type 1- b Ternary matroid of rank 4 on 9 elements, type 1- e Ternary matroid of rank 4 on 9 elements, type 1- f Ternary matroid of rank 4 on 9 elements, type 1- sage: for e in sorted(P[2]): print("{} {}".format(e, M/e)) d Ternary matroid of rank 4 on 9 elements, type 0- i Ternary matroid of rank 4 on 9 elements, type 0- sage: for e in sorted(P[3]): print("{} {}".format(e, M/e)) c Ternary matroid of rank 4 on 9 elements, type 0+ g Ternary matroid of rank 4 on 9 elements, type 0+ h Ternary matroid of rank 4 on 9 elements, type 0+ j Ternary matroid of rank 4 on 9 elements, type 0+
""" self._make_invariant()
cpdef TernaryMatrix _projection(self): """ Return the projection matrix onto the row space.
This projection is determined modulo the bicycle space. See [Pen2012]_.
INPUT:
- Nothing
OUTPUT:
A ternary matrix `P`, so that the `e`-th column of `P` is the signed incidence vector of a cocycle `C` such that `C-e` is a cycle. The bicycles `e`-th column is thus determined up to the bicycle space. We output the restriction of `P` to rows and columns that are not in any bicycle.
EXAMPLES::
sage: from sage.matroids.advanced import * sage: M = TernaryMatroid(matrix(matroids.named_matroids.R12())) sage: M._projection() 12 x 12 TernaryMatrix [++00-0--0+++] [+-+000+0+-+0] [0+-0-00+-+0+] [000000000000] [-0-0-0+-+00+] [000000000000] [-+00+0000+--] [-0+0-00-+0-+] [0+-0+00++++-] [+-+000+0+-+0] [++0000--++00] [+0+0+0-+-00-]
"""
cpdef _fast_isom_test(self, other): r""" Run a quick test to see if two ternary matroids are isomorphic.
The test is based on comparing strong invariants, including bicycle dimension, character, and the principal quadripartition. See also [Pen2012]_ .
INPUT:
- ``other`` -- a ternary matroid.
OUTPUT:
- ``True``, if ``self`` is isomorphic to ``other``; - ``False``, if ``self`` is not isomorphic to ``other``; - ``None``, if the test is inconclusive
EXAMPLES::
sage: M = matroids.named_matroids.T8() sage: N = matroids.named_matroids.P8() sage: M._fast_isom_test(N) False """
# minors, dual
cpdef _minor(self, contractions, deletions): r""" Return a minor.
INPUT:
- ``contractions`` -- An object with Python's ``frozenset`` interface containing a subset of ``self.groundset()``. - ``deletions`` -- An object with Python's ``frozenset`` interface containing a subset of ``self.groundset()``.
.. NOTE::
This method does NOT do any checks. Besides the assumptions above, we assume the following:
- ``contractions`` is independent - ``deletions`` is coindependent - ``contractions`` and ``deletions`` are disjoint.
OUTPUT:
A matroid.
EXAMPLES::
sage: M = matroids.named_matroids.P8() sage: N = M._minor(contractions=set(['a']), deletions=set([])) sage: N._minor(contractions=set([]), deletions=set(['b', 'c'])) Ternary matroid of rank 3 on 5 elements, type 0- """
cpdef is_valid(self): r""" 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 """
# representability
cpdef ternary_matroid(self, randomized_tests=1, verify = True): r""" Return a ternary matroid representing ``self``.
INPUT:
- ``randomized_tests`` -- Ignored. - ``verify`` -- Ignored
OUTPUT:
A binary matroid.
ALGORITHM:
``self`` is a ternary matroid, so just return ``self``.
.. SEEALSO::
:meth:`M.ternary_matroid() <sage.matroids.matroid.Matroid.ternary_matroid>`
EXAMPLES::
sage: N = matroids.named_matroids.NonFano() sage: N.ternary_matroid() is N True """
cpdef is_ternary(self, randomized_tests=1): r""" Decide if ``self`` is a binary matroid.
INPUT:
- ``randomized_tests`` -- Ignored.
OUTPUT:
A Boolean.
ALGORITHM:
``self`` is a ternary matroid, so just return ``True``.
.. SEEALSO::
:meth:`M.is_ternary() <sage.matroids.matroid.Matroid.is_ternary>`
EXAMPLES::
sage: N = matroids.named_matroids.NonFano() sage: N.is_ternary() True """
def __copy__(self): """ Create a shallow copy.
EXAMPLES::
sage: M = Matroid(Matrix(GF(3), [[1, 0, 0, 1, 1], [0, 1, 0, 1, 2], ....: [0, 0, 1, 1, 3]])) sage: N = copy(M) # indirect doctest sage: M == N True """ cdef TernaryMatroid N cdef list basis else:
def __deepcopy__(self, memo): """ Create a deep copy.
EXAMPLES::
sage: M = Matroid(Matrix(GF(3), [[1, 0, 0, 1, 1], [0, 1, 0, 1, 2], ....: [0, 0, 1, 1, -1]])) sage: N = deepcopy(M) # indirect doctest sage: M == N True """ cdef TernaryMatroid N cdef list basis else: basis = [0] * self.full_rank() for e in self.basis(): basis[self._prow[self._idx[e]]] = e N = TernaryMatroid(groundset=deepcopy(self._E, memo), matrix=deepcopy(self._A, memo), basis=deepcopy(basis, memo))
def __reduce__(self): """ Save the matroid for later reloading.
OUTPUT:
A tuple ``(unpickle_ternary_matroid, (version, data))``, where ``unpickle_ternary_matroid`` is the name of a function that, when called with ``(version, data)``, produces a matroid isomorphic to ``self``. ``version`` is an integer (currently 0) and ``data`` is a tuple ``(A, E, B, name)`` where ``A`` is the representation matrix, ``E`` is the groundset of the matroid, ``B`` is the currently displayed basis, and ``name`` is a custom name.
.. WARNING::
Users should never call this function directly.
EXAMPLES::
sage: from sage.matroids.advanced import * sage: M = TernaryMatroid(Matrix(GF(3), [[1, 0, 0, 1], ....: [0, 1, 0, 1], [0, 0, 1, 1]])) sage: M == loads(dumps(M)) # indirect doctest True sage: M.rename("U34") sage: loads(dumps(M)) U34 sage: M = TernaryMatroid(Matrix(GF(3), [[1, 0, 1], [1, 0, 1]])) sage: loads(dumps(M)).representation() [1 0 1] [1 0 1] """ else: A = self._A for e in self.basis(): basis[self._prow[self._idx[e]]] = e rows, cols = self._current_rows_cols() gs = rows + cols
# Quaternary Matroids
cdef class QuaternaryMatroid(LinearMatroid): r""" Quaternary matroids.
A quaternary matroid is a linear matroid represented over the finite field with four elements. See :class:`LinearMatroid` for a definition.
The simplest way to create a ``QuaternaryMatroid`` is by giving only a matrix `A`. 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 `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 of ``matrix`` and ``reduced_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 of ``matrix`` or the number of rows plus the number of columns of ``reduced_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 row-reduced copy. - ``basis`` -- (default: ``None``) When provided, this is an ordered subset of ``groundset``, such that the submatrix of ``matrix`` indexed by ``basis`` 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 :func:`Matroid() <sage.matroids.constructor.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 """ def __init__(self, matrix=None, groundset=None, reduced_matrix=None, ring=None, keep_initial_representation=True, basis=None): """ See class definition for full documentation.
.. NOTE::
The extra argument ``basis``, when provided, is an ordered list of elements of the groundset, ordered such that they index a standard identity matrix within ``matrix``.
EXAMPLES::
sage: from sage.matroids.advanced import * sage: QuaternaryMatroid(matrix=Matrix(GF(4, 'x'), ....: [[1, 0, 1, 1, 1], [0, 1, 1, 1, 1]])) # indirect doctest Quaternary matroid of rank 2 on 5 elements """ cdef QuaternaryMatrix A cdef long r, c cdef list P
# Setup representation; construct displayed basis else:
# Setup groundset, BasisExchangeMatroid data else: raise ValueError("size of groundset does not match size of matrix") else:
# Setup index of displayed basis else: else:
cpdef base_ring(self): """ 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], ....: [0, 1, 1]]) sage: M.base_ring() Finite Field in y of size 2^2 """
cpdef characteristic(self): """ 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], ....: [0, 1, 1]]) sage: M.characteristic() 2 """
cdef bint __is_exchange_pair(self, long x, long y) except -1: r""" Check if ``self.basis() - x + y`` is again a basis. Internal method. """
cdef int __exchange(self, long x, long y) except -1: r""" Replace ``self.basis() with ``self.basis() - x + y``. Internal method, does no checks. """
cdef __fundamental_cocircuit(self, bitset_t C, long x): r""" Fill bitset `C` with the incidence vector of the `B`-fundamental cocircuit using ``x``. Internal method using packed elements. """
cdef __coclosure(self, bitset_t R, bitset_t F): """ Bitpacked version of ``coclosure``.
This function overrides the internal function BasisExchangeMatroid.__coclosure() of the parent class. The implementation should be more efficient for QuaternaryMatroid, due to the fact that in this class, __fundamental_cocircuit is much faster than __fundamental_circuit. """
cdef __exchange_value(self, long x, long y): r""" Return the (x, y) entry of the current representation. """
def _repr_(self): """ Return a string representation of ``self``.
EXAMPLES::
sage: M = Matroid(ring=GF(4, 'x'), matrix=[[1, 0, 1], [0, 1, 1]]) sage: M.rename() sage: repr(M) # indirect doctest 'Quaternary matroid of rank 2 on 3 elements' """
cpdef _current_rows_cols(self, B=None): """ Return the current row and column labels of a reduced matrix.
INPUT:
- ``B`` -- (default: ``None``) If provided, first find a basis having maximal intersection with ``B``.
OUTPUT:
- ``R`` -- A list of row indices; corresponds to the currently used internal basis - ``C`` -- A list of column indices; corresponds to the complement of the current internal basis
EXAMPLES::
sage: M = matroids.named_matroids.Q10() sage: A = M._reduced_representation('efghi') sage: R, C = M._current_rows_cols() sage: (sorted(R), sorted(C)) (['e', 'f', 'g', 'h', 'i'], ['a', 'b', 'c', 'd', 'j']) sage: R, C = M._current_rows_cols(B='abcde') sage: (sorted(R), sorted(C)) (['a', 'b', 'c', 'd', 'e'], ['f', 'g', 'h', 'i', 'j'])
""" else:
cpdef LeanMatrix _basic_representation(self, B=None): """ Return a basic matrix representation of the matroid.
INPUT:
- ``B`` -- (default: ``None``) a set of elements of the groundset.
OUTPUT:
A matrix `M` representing the matroid, where `M[B'] = I` for a basis `B'` that maximally intersects the given set `B`. If not provided, the current basis used internally is chosen for `B'`. For a stable representation, use ``self.representation()``.
.. NOTE::
The method self.groundset_list() gives the labelling of the columns by the elements of the matroid. The matrix returned is a LeanMatrix subclass, which is intended for internal use only. Use the ``representation()`` method to get a Sage matrix.
EXAMPLES::
sage: M = matroids.named_matroids.Q10() sage: M._basic_representation() 5 x 10 QuaternaryMatrix [100001x00y] [01000y1x00] [001000y1x0] [0001000y1x] [00001x00y1] sage: matrix(M._basic_representation('efghi')) [ 1 0 x + 1 1 0 1 0 0 0 1] [ x x + 1 0 0 0 0 0 1 0 1] [ 0 0 x x + 1 0 0 1 0 0 1] [ 1 x 0 1 0 0 0 0 1 1] [ 1 1 1 1 1 0 0 0 0 0] """
cpdef LeanMatrix _reduced_representation(self, B=None): """ Return a reduced representation of the matroid, i.e. a matrix `R` such that `[I\ \ R]` represents the matroid.
INPUT:
- ``B`` -- (default: ``None``) a set of elements of the groundset.
OUTPUT:
A matrix `R` forming a reduced representation of the matroid, with rows labeled by a basis `B'` that maximally intersects the given set `B`. If not provided, the current basis used internally labels the rows.
.. NOTE::
The matrix returned is a LeanMatrix subclass, which is intended for internal use only. Use the ``representation()`` method to get a Sage matrix.
EXAMPLES::
sage: M = matroids.named_matroids.Q10() sage: M._reduced_representation() 5 x 5 QuaternaryMatrix [1x00y] [y1x00] [0y1x0] [00y1x] [x00y1] sage: matrix(M._reduced_representation('efghi')) [ 1 0 x + 1 1 1] [ x x + 1 0 0 1] [ 0 0 x x + 1 1] [ 1 x 0 1 1] [ 1 1 1 1 0] """
cpdef _make_invariant(self): """ Create an invariant.
Internal method; see ``_invariant`` for full documentation.
EXAMPLES::
sage: M = matroids.named_matroids.Q10() sage: M._invariant() # indirect doctest (0, 0, 5, 5, 20, 10, 25) """ cdef QuaternaryMatrix Q, QT cdef long i, j, d, r
return else:
cpdef _invariant(self): r""" Return a matroid invariant.
See [Pen2012]_ for more information.
OUTPUT:
A tuple ``(d, Lm, L0, Lp, p0, p1, p2)``, with the following interpretation:
- ``d`` is the bicycle dimension. - ``(Lm, L0, Lp)`` is the triple of lengths of the principal tripartition. - ``(p0, p1, p2)`` counts of edges in a characteristic graph of the matroid, whose vertices are the union of ``F_-`` and ``F_0`` from the principal tripartition.
EXAMPLES::
sage: M = matroids.named_matroids.Q10() sage: M._invariant() (0, 0, 5, 5, 20, 10, 25)
"""
cpdef bicycle_dimension(self): """ 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.named_matroids.Q10() sage: M.bicycle_dimension() 0 """
cpdef _principal_tripartition(self): r""" Return the principal tripartition of the quaternary matroid.
The principal tripartition is a partition `(F_{-1}, F_0, F_{1})` of the ground set. A defining property is the following. It is straightforward that if the bicycle dimension of a matroid `M` is `k`, then the bicycle dimension of `M\setminus e' is one of `k-1, k, k + 1` for each element `e` of `M`. Then if `F_i` denotes the set of elements such that the bicycle dimension of `M\setminus e` is `k + i`, we obtain the principal tripartition `(F_{-1}, F_0, F_{1})` of `M`. See [Pen2012]_, [GR2001]_.
OUTPUT:
``(F_{-1}, F_0, F_{1})``, the principal tripartition of the matroid.
EXAMPLES::
sage: M = matroids.named_matroids.Q10()\'a' sage: for F in M._principal_tripartition(): print(sorted(F)) ['b', 'c', 'd', 'e', 'h', 'i'] ['f', 'g', 'j'] [] sage: M.bicycle_dimension() 1 sage: for i in [-1, 0, 1]: print(sorted([e for e in M.groundset() if (M\e).bicycle_dimension() == 1 + i])) ['b', 'c', 'd', 'e', 'h', 'i'] ['f', 'g', 'j'] [] """
cpdef _fast_isom_test(self, other): r""" Run a quick test to see if two quaternary matroids are isomorphic.
The test is based on comparing the invariants returned by self._invariant().
INPUT:
- ``other`` -- a quaternary matroid.
OUTPUT:
- ``True``, if ``self`` is isomorphic to ``other``; - ``False``, if ``self`` is not isomorphic to ``other``; - ``None``, if this test is inconclusive
EXAMPLES::
sage: M = matroids.named_matroids.Q10()\'a' sage: N = matroids.named_matroids.Q10()\'b' sage: M._fast_isom_test(N) is None True """ return False
# minors, dual
cpdef _minor(self, contractions, deletions): r""" Return a minor.
INPUT:
- ``contractions`` -- An object with Python's ``frozenset`` interface containing a subset of ``self.groundset()``. - ``deletions`` -- An object with Python's ``frozenset`` interface containing a subset of ``self.groundset()``.
.. NOTE::
This method does NOT do any checks. Besides the assumptions above, we assume the following:
- ``contractions`` is independent - ``deletions`` is coindependent - ``contractions`` and ``deletions`` are disjoint.
OUTPUT:
A matroid.
EXAMPLES::
sage: M = matroids.named_matroids.Q10() sage: N = M._minor(contractions=set(['a']), deletions=set([])) sage: N._minor(contractions=set([]), deletions=set(['b', 'c'])) Quaternary matroid of rank 4 on 7 elements """
cpdef is_valid(self): r""" 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'), [[]])) sage: M.is_valid() True """
def __copy__(self): """ Create a shallow copy.
EXAMPLES::
sage: M = Matroid(Matrix(GF(4, 'x'), [[1, 0, 0, 1, 1], ....: [0, 1, 0, 1, 2], [0, 0, 1, 1, 3]])) sage: N = copy(M) # indirect doctest sage: M == N True """ cdef QuaternaryMatroid N cdef list basis else: basis = [0] * self.full_rank() for e in self.basis(): basis[self._prow[self._idx[e]]] = e N = QuaternaryMatroid(groundset=self._E, matrix=self._A, basis=basis)
def __deepcopy__(self, memo): """ Create a deep copy.
EXAMPLES::
sage: M = Matroid(Matrix(GF(4, 'x'), [[1, 0, 0, 1, 1], ....: [0, 1, 0, 1, 2], [0, 0, 1, 1, -1]])) sage: N = deepcopy(M) # indirect doctest sage: M == N True """ cdef QuaternaryMatroid N cdef list basis else: basis = [0] * self.full_rank() for e in self.basis(): basis[self._prow[self._idx[e]]] = e N = QuaternaryMatroid(groundset=deepcopy(self._E, memo), matrix=deepcopy(self._A, memo), basis=deepcopy(basis, memo))
def __reduce__(self): """ Save the matroid for later reloading.
OUTPUT:
A tuple ``(unpickle_quaternary_matroid, (version, data))``, where ``unpickle_quaternary_matroid`` is the name of a function that, when called with ``(version, data)``, produces a matroid isomorphic to ``self``. ``version`` is an integer (currently 0) and ``data`` is a tuple ``(A, E, B, name)`` where ``A`` is the representation matrix, ``E`` is the groundset of the matroid, ``B`` is the currently displayed basis, and ``name`` is a custom name.
.. WARNING::
Users should never call this function directly.
EXAMPLES::
sage: M = Matroid(Matrix(GF(4, 'x'), [[1, 0, 0, 1], [0, 1, 0, 1], ....: [0, 0, 1, 1]])) sage: M == loads(dumps(M)) # indirect doctest True sage: M.rename("U34") sage: loads(dumps(M)) U34 """ else: A = self._A for e in self.basis(): basis[self._prow[self._idx[e]]] = e rows, cols = self._current_rows_cols() gs = rows + cols
# Regular Matroids
cdef class RegularMatroid(LinearMatroid): r""" 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 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 `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 of ``matrix`` and ``reduced_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 of ``matrix`` or the number of rows plus the number of columns of ``reduced_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 row-reduced copy. - ``basis`` -- (default: ``None``) when provided, this is an ordered subset of ``groundset``, such that the submatrix of ``matrix`` indexed by ``basis`` 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 :func:`Matroid() <sage.matroids.constructor.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 :meth:`self.is_valid() <RegularMatroid.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'] """ def __init__(self, matrix=None, groundset=None, reduced_matrix=None, ring=None, keep_initial_representation=True): """ See class definition for full documentation.
.. NOTE::
The extra argument ``basis``, when provided, is an ordered list of elements of the groundset, ordered such that they index a standard identity matrix within ``matrix``.
EXAMPLES::
sage: from sage.matroids.advanced import * sage: RegularMatroid(matrix=Matrix(ZZ, [[1, 0, 1, 1, 1], ....: [0, 1, 1, 1, 1]])) # indirect doctest Regular matroid of rank 2 on 5 elements with 7 bases """
cdef list _setup_internal_representation(self, matrix, reduced_matrix, ring, keep_initial_representation): """ Setup the internal representation matrix ``self._A`` and the array of row- and column indices ``self._prow``.
Return the displayed basis. """ cdef IntegerMatrix A cdef long r, c cdef list P else: else: else: else:
cpdef base_ring(self): """ Return the base ring of the matrix representing the matroid, in this case `\ZZ`.
EXAMPLES::
sage: M = matroids.named_matroids.R10() sage: M.base_ring() Integer Ring """
cpdef characteristic(self): """ Return the characteristic of the base ring of the matrix representing the matroid, in this case `0`.
EXAMPLES::
sage: M = matroids.named_matroids.R10() sage: M.characteristic() 0 """
cdef bint __is_exchange_pair(self, long x, long y) except -1: r""" Check if ``self.basis() - x + y`` is again a basis. Internal method. """
cdef int __exchange(self, long x, long y) except -1: """ Put element indexed by ``x`` into basis, taking out element ``y``. Assumptions are that this is a valid basis exchange.
.. NOTE::
Safe for noncommutative rings. """ cdef long px, py, r cdef int a, piv, pivi
cdef __exchange_value(self, long x, long y): r""" Return the (x, y) entry of the current representation.
.. NOTE::
This uses get_unsafe(), which returns a Sage ``Integer`` instance, rather than the ``int`` returned by ``get``. The advantage is that cross ratio tests will return rational numbers rather than unwarranted zeroes. """
def _repr_(self): """ Return a string representation of ``self``.
EXAMPLES::
sage: M = matroids.named_matroids.R10() sage: M.rename() sage: repr(M) # indirect doctest 'Regular matroid of rank 5 on 10 elements with 162 bases' """
cpdef bases_count(self): """ Count the number of bases.
EXAMPLES::
sage: M = Matroid(graphs.CompleteGraph(5), regular = True) sage: M.bases_count() 125
ALGORITHM:
Since the matroid is regular, we use Kirchhoff's Matrix-Tree Theorem. See also :wikipedia:`Kirchhoff's_theorem`. """
cpdef _projection(self): """ Return the projection matrix onto the row space.
INPUT:
- Nothing
OUTPUT:
A matrix `P`, defined as follows. If `A` is a representation matrix of the matroid, then `Q = A^T (A A^T)^{-1} A`. Finally, `P` is equal to `Q` multiplied by the number of bases of the matroid.
The matrices `P` and `Q` are independent of the choice of `A`, except for column scaling. The vector `Qx` is the orthogonal projection of the vector `x` onto the row space of `A`. For regular matroids, there is an extended Matrix Tree theorem that derives the fraction of bases containing a subset by computing the determinant of the principal submatrix of `Q` corresponding to that subset. See [Lyo2003]_ . Due to the scaling, the entries of `P` are integers.
EXAMPLES::
sage: from sage.matroids.advanced import * sage: M = RegularMatroid(reduced_matrix=Matrix([[-1, 0, 1], ....: [-1, 1, 0], [0, 1, -1]])) sage: M._projection() [ 8 -4 4 -4 0 4] [-4 8 -4 -4 4 0] [ 4 -4 8 0 4 -4] [-4 -4 0 8 -4 -4] [ 0 4 4 -4 8 -4] [ 4 0 -4 -4 -4 8] """
cpdef _invariant(self): """ Compute a regular matroid invariant.
OUTPUT:
The hash value of a list of pairs `(w, A[w])` and `(w, B[w])` and a number `N`, derived form the projection matrix `P` as obtained from ``self._projection()`` as follows: `A[w]` counts the number of `i` such that `|P[i, i]|=w`, `B[w]` counts the number of pairs `(i, j)` such that `|P[i, j]|=w`, and `N` counts the number of triples `(i,j,k)` so that `P[i,j]*P'j,k]*P[k,i]` is negative.
EXAMPLES::
sage: M = matroids.named_matroids.R10() sage: N = matroids.named_matroids.R10().dual() sage: O = matroids.named_matroids.R12() sage: M._invariant() == N._invariant() True sage: M._invariant() == O._invariant() False """ # TODO: this currently uses Sage matrices internally. Perhaps dependence on those can be eliminated for further speed gains. cdef Matrix P else: else:
cpdef _hypergraph(self): """ Create a bipartite digraph and a vertex partition.
INPUT:
- Nothing.
OUTPUT:
- ``PV`` -- A partition of the vertices of ``G``. - ``tups`` -- A list of pairs ``(x, y)``, where ``x`` denotes the color class of a part and ``y`` the number of elements in that part. - ``G`` -- a graph.
All are derived from the entries of the projection matrix `P`. The partition ``PV`` groups vertices of the form `i` by the value of `P[i, i]`. Whenever `P[i, j]` is nonzero, there are edges `i - (i, j)` and `j - (i, j)`. Finally, the vertices `(i, j)` are grouped by value of `P[i, j]`.
EXAMPLES::
sage: M = matroids.named_matroids.R10() sage: PV, tups, G = M._hypergraph() sage: G Digraph on 55 vertices """ # NEW VERSION, USES SAGE'S GRAPH ISOMORPHISM return (self._hypergraph_vertex_partition, self._hypergraph_tuples, self._r_hypergraph) else: else: # Note that Sage's Graph object attempts a sort on calling G.vertices(), which means vertices have to be well-behaved.
# REMNANT OF THE OLD CODE THAT WAS NOT YET TRANSLATED TO SAGE'S GRAPH ISOMORPHISM. POTENTIAL SPEEDUP? # C = [] # if len(A) < 5: # for i in xrange(P.nrows()): # for j in xrange(i): # if P.get_unsafe(i, j) == 0: # continue # for k in xrange(j): # w = P.get_unsafe(i, j)*P.get_unsafe(j, k)*P.get_unsafe(k, i) # if w < 0: # C.append(frozenset([self._E[i], self._E[j], self._E[k]])) # self._r_hypergraph.add_color_class(C) # self._r_hypergraph = self._r_hypergraph.max_refined() # return self._r_hypergraph
cpdef _is_isomorphic(self, other, certificate=False): """ Test if ``self`` is isomorphic to ``other``.
Internal version that performs no checks on input.
INPUT:
- ``other`` -- A matroid, - optional parameter ``certificate`` -- Boolean.
OUTPUT:
Boolean, and, if certificate = True, a dictionary giving the isomorphism or None
.. NOTE::
Internal version that does no input checking.
EXAMPLES::
sage: M1 = matroids.Wheel(3) sage: M2 = Matroid(groundset = list(range(6)), ....: graph = graphs.CompleteGraph(4), regular = True) sage: M1._is_isomorphic(M2) True sage: M1._is_isomorphic(M2, certificate=True) (True, {0: 0, 1: 1, 2: 2, 3: 3, 4: 5, 5: 4})
sage: M1 = matroids.Wheel(3) sage: M2 = matroids.named_matroids.Fano() sage: M1._is_isomorphic(M2) False sage: M1._is_isomorphic(M2.delete('a')) True sage: M1._is_isomorphic(M2.delete('a'), certificate=True) (True, {0: 'g', 1: 'b', 2: 'c', 3: 'e', 4: 'd', 5: 'f'})
Check that :trac:`17316` was fixed::
sage: from sage.matroids.advanced import * sage: Mnew = RegularMatroid(groundset=range(12), matrix=Matrix(ZZ, ....: [[ 1, 0, 0, 0, 1, 0, 0,-1,-1, 0, 1, 0], ....: [ 0, 1, 0, 0,-1, 1, 0, 0, 0, 0, 0, 0], ....: [ 0, 0, 1, 0, 0,-1, 1, 0, 1, 0,-1, 0], ....: [ 0, 0, 0, 1, 0, 0,-1, 1, 0, 0, 0, 0], ....: [ 0, 0, 0, 0, 0, 1,-1, 0, 0, 1, 1, 0], ....: [ 0, 0, 0, 0, 1, 0, 0,-1,-1, 0, 0, 1]])) sage: Nnew = RegularMatroid(groundset=range(12), matrix=Matrix(ZZ, ....: [[1,0,0,0,0,0,1,1,0,0,1,0], ....: [0,1,0,0,0,0,1,0,1,0,1,0], ....: [0,0,1,0,0,0,1,0,0,1,1,0], ....: [0,0,0,1,0,0,1,1,0,0,0,1], ....: [0,0,0,0,1,0,1,0,1,0,0,1], ....: [0,0,0,0,0,1,1,0,0,1,0,1]])) sage: Mnew.is_isomorphic(Nnew) False sage: len(Mnew.circuits()) == len(Nnew.circuits()) False """ else:
cpdef _fast_isom_test(self, other): r""" Run a quick test to see if two regular matroids are isomorphic.
The test is based on:
* A comparison of the number of bases, which may be computed efficiently through the matrix-tree lemma (see self.bases_count()). * A comparison of the orthogonal projection matrices of both matroids (see self._invariant()). * A isomorphism test which makes use of a hypergraph derived from the orthogonal projection matrix (see self._hypertest()).
INPUT:
- ``other`` -- a regular matroid.
OUTPUT:
- ``True``, if ``self`` is isomorphic to ``other``; - ``False``, if ``self`` is not isomorphic to ``other``; - ``None``, if the test is inconclusive.
EXAMPLES::
sage: M = matroids.named_matroids.R10()\'a' sage: N = matroids.named_matroids.R10()\'b' sage: M._fast_isom_test(N) True """
cdef _hypertest(self, other): """ Test if the hypergraphs associated with ``self`` and ``other`` are isomorphic, and if so return an isomorphism.
INPUT:
- ``other`` -- A ``RegularMatroid`` instance.
OUTPUT:
- a dictionary, if the hypergraphs are isomorphic; ``None`` otherwise.
TESTS:
Check that :trac:`22263` was fixed::
sage: m1 = Matroid(graph='H?ABC~}') sage: m2 = Matroid(graph='H?ACNr}') sage: m1.is_isomorphic(m2) False """
cpdef has_line_minor(self, 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 returns ``True`` if `si(M/F)` is isomorphic to `U_{2, l}` with `l \geq k` for some `F` in ``hyperlines``, and ``False`` otherwise.
INPUT:
- ``k`` -- the length of the line minor - ``hyperlines`` -- (default: ``None``) a set of flats of codimension 2. Defaults to the set of all flats of codimension 2. - ``certificate`` (default: ``False``); If ``True`` returns ``True, F``, where ``F`` is a flat and ``self.minor(contractions=F)`` has a `U_{2,k}` restriction or ``False, None``.
OUTPUT:
Boolean or tuple.
.. SEEALSO::
:meth:`Matroid.has_minor() <sage.matroids.matroid.Matroid.has_minor>`
EXAMPLES::
sage: M = matroids.named_matroids.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'})) """
cpdef _linear_extension_chains(self, F, fundamentals=None): r""" Create a list of chains that determine single-element extensions of this linear matroid representation.
.. WARNING::
Intended for internal use; does no input checking.
INPUT:
- ``F`` -- an independent set of elements. - ``fundamentals`` -- (default: ``None``) a set elements of the base ring.
OUTPUT:
A list of chains, so each single-element regular extension of this linear matroid, with support contained in ``F``, is given by one of these chains.
EXAMPLES::
sage: M = matroids.Wheel(3) sage: len(M._linear_extension_chains(F=set([0, 1, 2]))) 7 sage: M._linear_extension_chains(F=set()) [{}] sage: M._linear_extension_chains(F=set([1])) [{}, {1: 1}] sage: len(M._linear_extension_chains(F=set([0, 1]))) 4 """
cpdef is_graphic(self): """ 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 = Matroid(graphs.CompleteGraph(5), regular = True) sage: M.is_graphic() True sage: M.dual().is_graphic() 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 2-separations especially), it is easy to implement. """
cpdef is_valid(self): r""" 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: 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 """
# representation
cpdef binary_matroid(self, randomized_tests=1, verify = True): r""" Return a binary matroid representing ``self``.
INPUT:
- ``randomized_tests`` -- Ignored. - ``verify`` -- Ignored
OUTPUT:
A binary matroid.
ALGORITHM:
``self`` is a regular matroid, so just cast ``self`` to a BinaryMatroid.
.. SEEALSO::
:meth:`M.binary_matroid() <sage.matroids.matroid.Matroid.binary_matroid>`
EXAMPLES::
sage: N = matroids.named_matroids.R10() sage: N.binary_matroid() Binary matroid of rank 5 on 10 elements, type (1, None)
"""
cpdef is_binary(self, randomized_tests=1): r""" Decide if ``self`` is a binary matroid.
INPUT:
- ``randomized_tests`` -- Ignored.
OUTPUT:
A Boolean.
ALGORITHM:
``self`` is a regular matroid, so just return ``True``.
.. SEEALSO::
:meth:`M.is_binary() <sage.matroids.matroid.Matroid.is_binary>`
EXAMPLES::
sage: N = matroids.named_matroids.R10() sage: N.is_binary() True """
cpdef ternary_matroid(self, randomized_tests=1, verify = True): r""" Return a ternary matroid representing ``self``.
INPUT:
- ``randomized_tests`` -- Ignored. - ``verify`` -- Ignored
OUTPUT:
A ternary matroid.
ALGORITHM:
``self`` is a regular matroid, so just cast ``self`` to a TernaryMatroid.
.. SEEALSO::
:meth:`M.ternary_matroid() <sage.matroids.matroid.Matroid.ternary_matroid>`
EXAMPLES::
sage: N = matroids.named_matroids.R10() sage: N.ternary_matroid() Ternary matroid of rank 5 on 10 elements, type 4+
"""
cpdef is_ternary(self, randomized_tests=1): r""" Decide if ``self`` is a ternary matroid.
INPUT:
- ``randomized_tests`` -- Ignored.
OUTPUT:
A Boolean.
ALGORITHM:
``self`` is a regular matroid, so just return ``True``.
.. SEEALSO::
:meth:`M.is_ternary() <sage.matroids.matroid.Matroid.is_ternary>`
EXAMPLES::
sage: N = matroids.named_matroids.R10() sage: N.is_ternary() True """
# Copying, loading, saving
def __copy__(self): """ Create a shallow copy.
EXAMPLES::
sage: M = matroids.named_matroids.R10() sage: N = copy(M) # indirect doctest sage: M == N True """ cdef RegularMatroid N else: rows, cols = self._current_rows_cols() N = RegularMatroid(groundset=rows + cols, reduced_matrix=self._A)
def __deepcopy__(self, memo): """ Create a deep copy.
EXAMPLES::
sage: M = matroids.named_matroids.R10() sage: N = deepcopy(M) # indirect doctest sage: M == N True """ cdef RegularMatroid N else: rows, cols = self._current_rows_cols() N = RegularMatroid(groundset=deepcopy(rows + cols, memo), reduced_matrix=deepcopy(self._A, memo))
def __reduce__(self): """ Save the matroid for later reloading.
OUTPUT:
A tuple ``(unpickle_regular_matroid, (version, data))``, where ``unpickle_regular_matroid`` is the name of a function that, when called with ``(version, data)``, produces a matroid isomorphic to ``self``. ``version`` is an integer (currently 0) and ``data`` is a tuple ``(A, E, reduced, name)`` where ``A`` is the representation matrix, ``E`` is the groundset of the matroid, ``reduced`` is a boolean indicating whether ``A`` is a reduced matrix, and ``name`` is a custom name.
.. WARNING::
Users should never call this function directly.
EXAMPLES::
sage: from sage.matroids.advanced import * sage: M = matroids.named_matroids.R12() sage: M == loads(dumps(M)) # indirect doctest True sage: M.rename("R_{12}") sage: loads(dumps(M)) R_{12} sage: M = RegularMatroid(Matrix(QQ, [[1, 0, 1], [1, 0, 1]])) sage: N = loads(dumps(M)) sage: N.representation() [1 0 1] [1 0 1] """ cdef LeanMatrix A else: A = self._reduced_representation() rows, cols = self._current_rows_cols() gs = rows + cols reduced = True |