sign_vectors.oriented_matroids

Oriented matroids

We define some matrix:

sage: A = matrix([[2, -1, -1]])
sage: A
[ 2 -1 -1]

Cocircuits

Now, we compute the cocircuits of the oriented matroid corresponding to the kernel of the matrix A:

sage: from sign_vectors.oriented_matroids import *
sage: ccA = cocircuits_from_matrix(A)
sage: ccA
{(0+-), (--0), (0-+), (++0), (+0+), (-0-)}

Covectors

We can also use the cocircuits to compute all covectors of the corresponding oriented matroid:

sage: covectors_from_cocircuits(ccA)
{(000),
 (---),
 (0+-),
 (++-),
 (--0),
 (0-+),
 (--+),
 (++0),
 (+0+),
 (+++),
 (-0-),
 (-+-),
 (+-+)}
sage: covectors_from_matrix(A)
{(000),
 (---),
 (0+-),
 (++-),
 (--0),
 (0-+),
 (--+),
 (++0),
 (+0+),
 (+++),
 (-0-),
 (-+-),
 (+-+)}

Topes

Next, we compute the topes:

sage: tA = topes_from_cocircuits(ccA)
sage: tA
{(---), (++-), (--+), (+++), (-+-), (+-+)}
sage: topes_from_matrix(A)
{(---), (++-), (--+), (+++), (-+-), (+-+)}

Face enumeration

Next, we compute all covectors separated by their rank:

sage: face_enumeration(tA)
[{(000)},
 {(0+-), (--0), (0-+), (++0), (+0+), (-0-)},
 {(---), (-+-), (++-), (--+), (+++), (+-+)}]

By passing dual=False, we can compute the covectors of the dual oriented matroid:

sage: cocircuits_from_matrix(A, dual=False)
{(+--), (-++)}

Functions

cocircuits_from_matrix(M[, dual])

Compute a set of cocircuits determined by the matrix M.

cocircuits_from_topes(topes)

Compute all cocircuits from the topes.

covectors_from_cocircuits(cocircuits)

Use an iterable of cocircuits to compute all covectors of the corresponding oriented matroid.

covectors_from_matrix(M[, dual, algorithm, ...])

Return the covectors of the oriented matroid corresponding to the matrix M.

covectors_from_topes(topes[, separate])

Compute all covectors from the topes.

face_enumeration(covectors)

Compute all covectors with less rank than the given covectors.

lower_faces(covectors)

Compute the lower faces of given covectors.

topes_from_cocircuits(cocircuits)

Use the cocircuits of an oriented matroid to compute the topes.

topes_from_matrix(M[, dual])

Return the topes of the oriented matroid corresponding to the matrix M.

Classes

Cocircuits(M)

Class used to compute cocircuits and circuits.

OrientedMatroid(M)

class sign_vectors.oriented_matroids.Cocircuits(M: sage.matrix.constructor.matrix)

Class used to compute cocircuits and circuits.

TESTS:

sage: from sign_vectors.oriented_matroids import *
sage: M = matrix([[1, 2, 4, 0], [0, 1, 2, 0]])
sage: cc = Cocircuits(M)
sage: cc.element([1, 2, 3])
Traceback (most recent call last):
...
ValueError: The indices [1, 2, 3] correspond to the zero vector!
sage: cc.elements()
{(0+-0), (000-), (0-+0), (000+)}
sage: cc.minors
{(0, 1): 1, (0, 2): 1, (0, 3): 0, (1, 2): 0, (1, 3): 0, (2, 3): 0}
elements(dual: bool = True, prevent_multiples: bool = True) → set[sign_vectors.sign_vectors.SignVector]

Return a list of elementary vectors

generator(dual: bool = True, prevent_multiples: bool = True, reverse: bool = False) → collections.abc.Generator[sign_vectors.sign_vectors.SignVector]

Return a generator of elementary vectors

class sign_vectors.oriented_matroids.OrientedMatroid(M)
sign_vectors.oriented_matroids.cocircuits_from_matrix(M, dual: bool = True)

Compute a set of cocircuits determined by the matrix M.

INPUT:

  • M – a matrix with real arguments.

  • dual – a boolean (default: True)

OUTPUT:

  • If dual is true, returns a set of cocircuits determined by the kernel of the matrix M.

  • If dual is false, returns a set of cocircuits determined by the row space of the matrix M.

EXAMPLES:

sage: from sign_vectors.oriented_matroids import *
sage: A = matrix([[2, -1, -1]])
sage: A
[ 2 -1 -1]
sage: cocircuits_from_matrix(A)
{(0+-), (--0), (0-+), (++0), (+0+), (-0-)}
sage: B = matrix([[1, 0, 0, 0], [0, 1, 0, 2], [0, 0, 1, -1]])
sage: B
[ 1  0  0  0]
[ 0  1  0  2]
[ 0  0  1 -1]
sage: cocircuits_from_matrix(B, dual=False)
{(-000), (00-+), (0-0-), (0--0), (0+0+), (00+-), (0++0), (+000)}
sign_vectors.oriented_matroids.cocircuits_from_topes(topes)

Compute all cocircuits from the topes.

INPUT:

  • topes – an iterable of topes.

OUTPUT:

A set of cocircuits of the corresponding oriented matroid.

EXAMPLES:

We define some matrix and compute the topes of the corresponding oriented matroid:

sage: from sign_vectors.oriented_matroids import *
sage: A = matrix([[2, -1, -1]])
sage: A
[ 2 -1 -1]
sage: tA = topes_from_matrix(A)
sage: tA
{(---), (++-), (--+), (+++), (-+-), (+-+)}
sage: cocircuits_from_topes(tA)
{(0+-), (--0), (0-+), (++0), (+0+), (-0-)}
sign_vectors.oriented_matroids.covectors_from_cocircuits(cocircuits)

Use an iterable of cocircuits to compute all covectors of the corresponding oriented matroid.

INPUT:

  • cocircuits – an iterable of cocircuits of an oriented matroid.

OUTPUT:

  • a set of all covectors of the oriented matroid.

ALGORITHM:

This function is based on an algorithm in [Fin01].

Fin01(1,2,3,4)

Finschi, L.: „A graph theoretical approach for reconstruction and generation of oriented matroids“. PhD thesis. Zurich: ETH Zurich, 2001. doi: 10.3929/ethz-a-004255224.

EXAMPLES:

First, we need cocircuits. For this purpose, we compute the cocircuits corresponding to some matrix:

sage: from sign_vectors.oriented_matroids import *
sage: A = matrix([[2, -1, -1]])
sage: A
[ 2 -1 -1]
sage: ccA = cocircuits_from_matrix(A)
sage: ccA
{(0+-), (--0), (0-+), (++0), (+0+), (-0-)}
sage: covectors_from_cocircuits(ccA)
{(000),
 (---),
 (0+-),
 (++-),
 (--0),
 (0-+),
 (--+),
 (++0),
 (+0+),
 (+++),
 (-0-),
 (-+-),
 (+-+)}
sign_vectors.oriented_matroids.covectors_from_matrix(M, dual: bool = True, algorithm: Optional[str] = None, separate: bool = False)

Return the covectors of the oriented matroid corresponding to the matrix M.

INPUT:

  • M – a matrix.

  • dual – a boolean (default: True)

  • algorithm – either None (default), "face_enumeration" or "fe"

  • separate – a boolean (default: False)

OUTPUT:

Returns a set of covectors of an oriented matroid corresponding to the matrix M.

  • If dual is true, the returned covectors will be determined by the kernel of the matrix M.

  • If dual is false, the returned covectors will be determined by the row space of the matrix M.

  • If algorithm is "face_enumeration" or the shortcut "fe", applies the algorithm face enumeration.

  • If separate is true, returns a list of sets of covectors, separated by their rank by applying the algorithm face enumeration.

  • If separate is false, returns a set of covectors.

See also

face_enumeration()

EXAMPLES:

sage: from sign_vectors.oriented_matroids import *

We define some matrix:

sage: A = matrix([[2, -1, -1]])
sage: A
[ 2 -1 -1]
sage: covectors_from_matrix(A)
{(000),
 (---),
 (0+-),
 (++-),
 (--0),
 (0-+),
 (--+),
 (++0),
 (+0+),
 (+++),
 (-0-),
 (-+-),
 (+-+)}
sage: covectors_from_matrix(A, separate=True)
[{(000)},
 {(0+-), (--0), (0-+), (++0), (+0+), (-0-)},
 {(---), (-+-), (++-), (--+), (+++), (+-+)}]
sage: covectors_from_matrix(A, algorithm="face_enumeration", separate=True)
[{(000)},
 {(0+-), (--0), (0-+), (++0), (+0+), (-0-)},
 {(---), (-+-), (++-), (--+), (+++), (+-+)}]

TESTS:

sage: covectors_from_matrix(zero_matrix(1, 4), dual=False, separate=False)
{(0000)}
sage: covectors_from_matrix(zero_matrix(1, 4), dual=False, separate=True)
[{(0000)}]
sign_vectors.oriented_matroids.covectors_from_topes(topes, separate: bool = False)

Compute all covectors from the topes.

INPUT:

  • topes – an iterable of topes.

  • separate – a boolean (default: False)

OUTPUT:

The set of covectors of the corresponding oriented matroid.

  • If separate is false, returns a list of covectors. The covectors are sorted by rank. (default)

  • If separate is true, returns a list of lists of covectors, separated by their rank.

See also

face_enumeration()

EXAMPLES:

We define some matrix and compute the topes of the corresponding oriented matroid:

sage: from sign_vectors.oriented_matroids import *
sage: A = matrix([[2, -1, -1]])
sage: A
[ 2 -1 -1]
sage: tA = topes_from_matrix(A)
sage: tA
{(---), (++-), (--+), (+++), (-+-), (+-+)}
sage: covectors_from_topes(tA)
{(000),
 (---),
 (0+-),
 (++-),
 (--0),
 (0-+),
 (--+),
 (++0),
 (+0+),
 (+++),
 (-0-),
 (-+-),
 (+-+)}
sage: covectors_from_topes(tA, separate=True)
[{(000)},
 {(0+-), (--0), (0-+), (++0), (+0+), (-0-)},
 {(---), (-+-), (++-), (--+), (+++), (+-+)}]
sign_vectors.oriented_matroids.face_enumeration(covectors)

Compute all covectors with less rank than the given covectors.

INPUT:

  • covectors – an iterable of all covectors of same rank r of an oriented matroid.

OUTPUT:

Returns a list of sets. Every set consists of all covectors of the same rank smaller than or equal to r of the oriented matroid.

ALGORITHM:

This function is based on an algorithm in [FST91]. See also [Fin01].

See also

lower_faces() covectors_from_topes() covectors_from_matrix()

EXAMPLES:

We define some matrix and compute the topes of the corresponding oriented matroid:

sage: from sign_vectors.oriented_matroids import *
sage: A = matrix([[2, -1, -1]])
sage: A
[ 2 -1 -1]
sage: tA = topes_from_matrix(A)
sage: tA
{(---), (++-), (--+), (+++), (-+-), (+-+)}
sage: face_enumeration(tA)
[{(000)},
 {(0+-), (--0), (0-+), (++0), (+0+), (-0-)},
 {(---), (-+-), (++-), (--+), (+++), (+-+)}]
sign_vectors.oriented_matroids.lower_faces(covectors)

Compute the lower faces of given covectors.

INPUT:

  • covectors – an iterable of all covectors with same rank r of an oriented matroid.

OUTPUT:

Returns a set of covectors of rank r-1 of the oriented matroid.

ALGORITHM:

This function is based on an algorithm in [FST91]. See also [Fin01].

FST91(1,2)

Fukuda, K., Saito, S., and Tamura, A.: “Combinatorial face enumeration in arrangements and oriented matroids”. In: Discrete Applied Mathematics 31.2 (1991), pp. 141-149. doi: 10.1016/0166-218X(91)90066-6.

See also

face_enumeration() covectors_from_topes()

sign_vectors.oriented_matroids.topes_from_cocircuits(cocircuits)

Use the cocircuits of an oriented matroid to compute the topes.

INPUT:

  • cocircuits – an iterable of cocircuits of an oriented matroid.

OUTPUT:

A set of topes of the oriented matroid.

ALGORITHM:

This function is based on an algorithm in [Fin01].

EXAMPLES:

First, we need cocircuits. For this purpose, we compute the cocircuits corresponding to some matrix:

sage: from sign_vectors.oriented_matroids import *
sage: A = matrix([[2, -1, -1]])
sage: A
[ 2 -1 -1]
sage: ccA = cocircuits_from_matrix(A)
sage: ccA
{(0+-), (--0), (0-+), (++0), (+0+), (-0-)}
sage: topes_from_cocircuits(ccA)
{(---), (++-), (--+), (+++), (-+-), (+-+)}
sign_vectors.oriented_matroids.topes_from_matrix(M, dual: bool = True)

Return the topes of the oriented matroid corresponding to the matrix M.

INPUT:

  • M – a matrix

  • dual – a boolean (default: True)

OUTPUT:

  • If dual is true, returns a set of topes determined by the kernel of the matrix M.

  • If dual is false, returns a set of topes determined by the row space of the matrix M.

EXAMPLES:

We define some matrix and compute the topes of the corresponding oriented matroid:

sage: from sign_vectors.oriented_matroids import *
sage: A = matrix([[2, -1, -1]])
sage: A
[ 2 -1 -1]
sage: topes_from_matrix(A)
{(---), (++-), (--+), (+++), (-+-), (+-+)}

TESTS:

sage: M = zero_matrix(1, 3)
sage: topes_from_matrix(M, dual=False)
{(000)}