Lean matrices#

Internal data structures for the LinearMatroid class and some subclasses. Note that many of the methods are cdef, and therefore only available from Cython code.

Warning

Intended for internal use by the LinearMatroid classes only. End users should work with Sage matrices instead. Methods that are used outside lean_matrix.pyx and have no equivalent in Sage’s Matrix have been flagged in the code, as well as where they are used, by # Not a Sage matrix operation or # Deprecated Sage matrix operation.

AUTHORS:

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

class sage.matroids.lean_matrix.BinaryMatrix[source]#

Bases: LeanMatrix

Binary matrix class. Entries are stored bit-packed into integers.

INPUT:

  • m – Number of rows.

  • n – Number of columns.

  • M – (default: None) Matrix or BinaryMatrix instance. Assumption: dimensions of M are at most m by n.

  • ring – (default: None) ignored.

EXAMPLES:

sage: from sage.matroids.lean_matrix import *
sage: A = BinaryMatrix(2, 2, Matrix(GF(7), [[0, 0], [0, 0]]))
sage: B = BinaryMatrix(2, 2, ring=GF(5))
sage: C = BinaryMatrix(2, 2)
sage: A == B and A == C
True

>>> from sage.all import *
>>> from sage.matroids.lean_matrix import *
>>> A = BinaryMatrix(Integer(2), Integer(2), Matrix(GF(Integer(7)), [[Integer(0), Integer(0)], [Integer(0), Integer(0)]]))
>>> B = BinaryMatrix(Integer(2), Integer(2), ring=GF(Integer(5)))
>>> C = BinaryMatrix(Integer(2), Integer(2))
>>> A == B and A == C
True
base_ring()[source]#

Return \(GF(2)\).

EXAMPLES:

sage: from sage.matroids.lean_matrix import *
sage: A = BinaryMatrix(4, 4)
sage: A.base_ring()
Finite Field of size 2

>>> from sage.all import *
>>> from sage.matroids.lean_matrix import *
>>> A = BinaryMatrix(Integer(4), Integer(4))
>>> A.base_ring()
Finite Field of size 2
characteristic()[source]#

Return the characteristic of self.base_ring().

EXAMPLES:

sage: from sage.matroids.lean_matrix import *
sage: A = BinaryMatrix(3, 4)
sage: A.characteristic()
2

>>> from sage.all import *
>>> from sage.matroids.lean_matrix import *
>>> A = BinaryMatrix(Integer(3), Integer(4))
>>> A.characteristic()
2
class sage.matroids.lean_matrix.GenericMatrix[source]#

Bases: LeanMatrix

Matrix over arbitrary Sage ring.

INPUT:

  • nrows – number of rows

  • ncols – number of columns

  • M – (default: None) a Matrix or GenericMatrix of dimensions at most m*n.

  • ring – (default: None) a Sage ring.

Note

This class is intended for internal use by the LinearMatroid class only. Hence it does not derive from SageObject. If A is a LeanMatrix instance, and you need access from other parts of Sage, use Matrix(A) instead.

If the constructor is fed a GenericMatrix instance, the ring argument is ignored. Otherwise, the matrix entries will be converted to the appropriate ring.

EXAMPLES:

sage: M = Matroid(ring=GF(5), matrix=[[1, 0, 1, 1, 1], [0, 1, 1, 2, 3]])  # indirect doctest
sage: M.is_isomorphic(matroids.Uniform(2, 5))
True

>>> from sage.all import *
>>> M = Matroid(ring=GF(Integer(5)), matrix=[[Integer(1), Integer(0), Integer(1), Integer(1), Integer(1)], [Integer(0), Integer(1), Integer(1), Integer(2), Integer(3)]])  # indirect doctest
>>> M.is_isomorphic(matroids.Uniform(Integer(2), Integer(5)))
True
base_ring()[source]#

Return the base ring of self.

EXAMPLES:

sage: from sage.matroids.lean_matrix import GenericMatrix
sage: A = GenericMatrix(3, 4, ring=GF(5))
sage: A.base_ring()
Finite Field of size 5

>>> from sage.all import *
>>> from sage.matroids.lean_matrix import GenericMatrix
>>> A = GenericMatrix(Integer(3), Integer(4), ring=GF(Integer(5)))
>>> A.base_ring()
Finite Field of size 5
characteristic()[source]#

Return the characteristic of self.base_ring().

EXAMPLES:

sage: from sage.matroids.lean_matrix import GenericMatrix
sage: A = GenericMatrix(3, 4, ring=GF(5))
sage: A.characteristic()
5

>>> from sage.all import *
>>> from sage.matroids.lean_matrix import GenericMatrix
>>> A = GenericMatrix(Integer(3), Integer(4), ring=GF(Integer(5)))
>>> A.characteristic()
5
class sage.matroids.lean_matrix.LeanMatrix[source]#

Bases: object

Lean matrices

Sage’s matrix classes are powerful, versatile, and often very fast. However, their performance with regard to pivoting (pretty much the only task performed on them within the context of matroids) leaves something to be desired. The LeanMatrix classes provide the LinearMatroid classes with a custom, light-weight data structure to store and manipulate matrices.

This is the abstract base class. Most methods are not implemented; this is only to fix the interface.

Note

This class is intended for internal use by the LinearMatroid class only. Hence it does not derive from SageObject. If A is a LeanMatrix instance, and you need access from other parts of Sage, use Matrix(A) instead.

EXAMPLES:

sage: M = Matroid(ring=GF(5), matrix=[[1, 0, 1, 1, 1], [0, 1, 1, 2, 3]])  # indirect doctest
sage: M.is_isomorphic(matroids.Uniform(2, 5))
True

>>> from sage.all import *
>>> M = Matroid(ring=GF(Integer(5)), matrix=[[Integer(1), Integer(0), Integer(1), Integer(1), Integer(1)], [Integer(0), Integer(1), Integer(1), Integer(2), Integer(3)]])  # indirect doctest
>>> M.is_isomorphic(matroids.Uniform(Integer(2), Integer(5)))
True
base_ring()[source]#

Return the base ring.

EXAMPLES:

sage: from sage.matroids.lean_matrix import LeanMatrix
sage: A = LeanMatrix(3, 4)
sage: A.base_ring()
Traceback (most recent call last):
...
NotImplementedError: subclasses need to implement this.

>>> from sage.all import *
>>> from sage.matroids.lean_matrix import LeanMatrix
>>> A = LeanMatrix(Integer(3), Integer(4))
>>> A.base_ring()
Traceback (most recent call last):
...
NotImplementedError: subclasses need to implement this.
characteristic()[source]#

Return the characteristic of self.base_ring().

EXAMPLES:

sage: from sage.matroids.lean_matrix import GenericMatrix
sage: A = GenericMatrix(3, 4, ring=GF(5))
sage: A.characteristic()
5

>>> from sage.all import *
>>> from sage.matroids.lean_matrix import GenericMatrix
>>> A = GenericMatrix(Integer(3), Integer(4), ring=GF(Integer(5)))
>>> A.characteristic()
5
ncols()[source]#

Return the number of columns.

EXAMPLES:

sage: from sage.matroids.lean_matrix import LeanMatrix
sage: A = LeanMatrix(3, 4)
sage: A.ncols()
4

>>> from sage.all import *
>>> from sage.matroids.lean_matrix import LeanMatrix
>>> A = LeanMatrix(Integer(3), Integer(4))
>>> A.ncols()
4
nrows()[source]#

Return the number of rows.

EXAMPLES:

sage: from sage.matroids.lean_matrix import LeanMatrix
sage: A = LeanMatrix(3, 4)
sage: A.nrows()
3

>>> from sage.all import *
>>> from sage.matroids.lean_matrix import LeanMatrix
>>> A = LeanMatrix(Integer(3), Integer(4))
>>> A.nrows()
3
class sage.matroids.lean_matrix.PlusMinusOneMatrix[source]#

Bases: LeanMatrix

Matrix with nonzero entries of \(\pm 1\).

INPUT:

  • nrows – number of rows

  • ncols – number of columns

  • M – (default: None) a Matrix or GenericMatrix of dimensions at most m*n

Note

This class is intended for internal use by the LinearMatroid class only. Hence it does not derive from SageObject. If A is a LeanMatrix instance, and you need access from other parts of Sage, use Matrix(A) instead.

This class is mainly intended for use with the RegularMatroid class, so entries are assumed to be \(\pm 1\) or \(0\). No overflow checking takes place!

EXAMPLES:

sage: M = Matroid(graphs.CompleteGraph(4).incidence_matrix(oriented=True),  # indirect doctest
....:             regular=True)
sage: M.is_isomorphic(matroids.Wheel(3))
True

>>> from sage.all import *
>>> M = Matroid(graphs.CompleteGraph(Integer(4)).incidence_matrix(oriented=True),  # indirect doctest
...             regular=True)
>>> M.is_isomorphic(matroids.Wheel(Integer(3)))
True
base_ring()[source]#

Return the base ring of self.

EXAMPLES:

sage: from sage.matroids.lean_matrix import PlusMinusOneMatrix
sage: A = PlusMinusOneMatrix(3, 4)
sage: A.base_ring()
Integer Ring

>>> from sage.all import *
>>> from sage.matroids.lean_matrix import PlusMinusOneMatrix
>>> A = PlusMinusOneMatrix(Integer(3), Integer(4))
>>> A.base_ring()
Integer Ring
characteristic()[source]#

Return the characteristic of self.base_ring().

EXAMPLES:

sage: from sage.matroids.lean_matrix import PlusMinusOneMatrix
sage: A = PlusMinusOneMatrix(3, 4)
sage: A.characteristic()
0

>>> from sage.all import *
>>> from sage.matroids.lean_matrix import PlusMinusOneMatrix
>>> A = PlusMinusOneMatrix(Integer(3), Integer(4))
>>> A.characteristic()
0
class sage.matroids.lean_matrix.QuaternaryMatrix[source]#

Bases: LeanMatrix

Matrices over GF(4).

INPUT:

  • m – Number of rows

  • n – Number of columns

  • M – (default: None) A QuaternaryMatrix or LeanMatrix or (Sage) Matrix instance. If not given, new matrix will be filled with zeroes. Assumption: M has dimensions at most m times n.

  • ring – (default: None) A copy of GF(4). Useful for specifying generator name.

EXAMPLES:

sage: from sage.matroids.lean_matrix import *
sage: A = QuaternaryMatrix(2, 2, Matrix(GF(4, 'x'), [[0, 0], [0, 0]]))
sage: B = QuaternaryMatrix(2, 2, GenericMatrix(2, 2, ring=GF(4, 'x')))
sage: C = QuaternaryMatrix(2, 2, ring=GF(4, 'x'))
sage: A == B and A == C
True

>>> from sage.all import *
>>> from sage.matroids.lean_matrix import *
>>> A = QuaternaryMatrix(Integer(2), Integer(2), Matrix(GF(Integer(4), 'x'), [[Integer(0), Integer(0)], [Integer(0), Integer(0)]]))
>>> B = QuaternaryMatrix(Integer(2), Integer(2), GenericMatrix(Integer(2), Integer(2), ring=GF(Integer(4), 'x')))
>>> C = QuaternaryMatrix(Integer(2), Integer(2), ring=GF(Integer(4), 'x'))
>>> A == B and A == C
True
base_ring()[source]#

Return copy of \(GF(4)\) with appropriate generator.

EXAMPLES:

sage: from sage.matroids.lean_matrix import *
sage: A = QuaternaryMatrix(2, 2, ring=GF(4, 'f'))
sage: A.base_ring()
Finite Field in f of size 2^2

>>> from sage.all import *
>>> from sage.matroids.lean_matrix import *
>>> A = QuaternaryMatrix(Integer(2), Integer(2), ring=GF(Integer(4), 'f'))
>>> A.base_ring()
Finite Field in f of size 2^2
characteristic()[source]#

Return the characteristic of self.base_ring().

EXAMPLES:

sage: from sage.matroids.lean_matrix import *
sage: A = QuaternaryMatrix(200, 5000, ring=GF(4, 'x'))
sage: A.characteristic()
2

>>> from sage.all import *
>>> from sage.matroids.lean_matrix import *
>>> A = QuaternaryMatrix(Integer(200), Integer(5000), ring=GF(Integer(4), 'x'))
>>> A.characteristic()
2
class sage.matroids.lean_matrix.RationalMatrix[source]#

Bases: LeanMatrix

Matrix over the rationals.

INPUT:

  • nrows – number of rows

  • ncols – number of columns

  • M – (default: None) a Matrix or GenericMatrix of dimensions at most m * n

EXAMPLES:

sage: M = Matroid(graphs.CompleteGraph(4).incidence_matrix(oriented=True))  # indirect doctest
sage: M.is_isomorphic(matroids.Wheel(3))
True

>>> from sage.all import *
>>> M = Matroid(graphs.CompleteGraph(Integer(4)).incidence_matrix(oriented=True))  # indirect doctest
>>> M.is_isomorphic(matroids.Wheel(Integer(3)))
True
base_ring()[source]#

Return the base ring of self.

EXAMPLES:

sage: from sage.matroids.lean_matrix import RationalMatrix
sage: A = RationalMatrix(3, 4)
sage: A.base_ring()
Rational Field

>>> from sage.all import *
>>> from sage.matroids.lean_matrix import RationalMatrix
>>> A = RationalMatrix(Integer(3), Integer(4))
>>> A.base_ring()
Rational Field
characteristic()[source]#

Return the characteristic of self.base_ring().

EXAMPLES:

sage: from sage.matroids.lean_matrix import RationalMatrix
sage: A = RationalMatrix(3, 4)
sage: A.characteristic()
0

>>> from sage.all import *
>>> from sage.matroids.lean_matrix import RationalMatrix
>>> A = RationalMatrix(Integer(3), Integer(4))
>>> A.characteristic()
0
class sage.matroids.lean_matrix.TernaryMatrix[source]#

Bases: LeanMatrix

Ternary matrix class. Entries are stored bit-packed into integers.

INPUT:

  • m – Number of rows.

  • n – Number of columns.

  • M – (default: None) Matrix or TernaryMatrix instance. Assumption: dimensions of M are at most m by n.

  • ring – (default: None) ignored.

EXAMPLES:

sage: from sage.matroids.lean_matrix import *
sage: A = TernaryMatrix(2, 2, Matrix(GF(7), [[0, 0], [0, 0]]))
sage: B = TernaryMatrix(2, 2, ring=GF(5))
sage: C = TernaryMatrix(2, 2)
sage: A == B and A == C
True

>>> from sage.all import *
>>> from sage.matroids.lean_matrix import *
>>> A = TernaryMatrix(Integer(2), Integer(2), Matrix(GF(Integer(7)), [[Integer(0), Integer(0)], [Integer(0), Integer(0)]]))
>>> B = TernaryMatrix(Integer(2), Integer(2), ring=GF(Integer(5)))
>>> C = TernaryMatrix(Integer(2), Integer(2))
>>> A == B and A == C
True
base_ring()[source]#

Return GF(3).

EXAMPLES:

sage: from sage.matroids.lean_matrix import *
sage: A = TernaryMatrix(3, 3)
sage: A.base_ring()
Finite Field of size 3

>>> from sage.all import *
>>> from sage.matroids.lean_matrix import *
>>> A = TernaryMatrix(Integer(3), Integer(3))
>>> A.base_ring()
Finite Field of size 3
characteristic()[source]#

Return the characteristic of self.base_ring().

EXAMPLES:

sage: from sage.matroids.lean_matrix import *
sage: A = TernaryMatrix(3, 4)
sage: A.characteristic()
3

>>> from sage.all import *
>>> from sage.matroids.lean_matrix import *
>>> A = TernaryMatrix(Integer(3), Integer(4))
>>> A.characteristic()
3
sage.matroids.lean_matrix.generic_identity(n, ring)[source]#

Return a GenericMatrix instance containing the \(n imes n\) identity matrix over ring.

EXAMPLES:

sage: from sage.matroids.lean_matrix import *
sage: A = generic_identity(2, QQ)
sage: Matrix(A)
[1 0]
[0 1]

>>> from sage.all import *
>>> from sage.matroids.lean_matrix import *
>>> A = generic_identity(Integer(2), QQ)
>>> Matrix(A)
[1 0]
[0 1]