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. (Cocircuits are minimal nonzero elements of an oriented matroid with respect to the conformal relation.):

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)}

Topes¶

Next, we compute the topes using the cocircuits. (Topes are the covectors that are maximal with respect to the conformal relation):

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

There are some further commands to work with oriented matroids:

sage: covectors_from_matrix(A)
{(000),
 (+-+),
 (---),
 (-+-),
 (0-+),
 (+0+),
 (--0),
 (-0-),
 (+++),
 (0+-),
 (++-),
 (--+),
 (++0)}
sage: topes_from_matrix(A)
{(+-+), (---), (-+-), (+++), (--+), (++-)}
sage: covectors_from_topes(tA)
{(000),
 (+-+),
 (---),
 (-+-),
 (0-+),
 (+0+),
 (--0),
 (-0-),
 (++-),
 (+++),
 (0+-),
 (--+),
 (++0)}
sage: cocircuits_from_topes(tA)
{(0-+), (+0+), (--0), (-0-), (0+-), (++0)}

Face enumeration¶

Next, we compute all covectors separated by their rank:

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

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

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

Functions

`cocircuits_from_matrix`(M[, kernel])	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[, kernel, ...])	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[, kernel])	Return the topes of the oriented matroid corresponding to the matrix `M`.

Classes

Cocircuits(M)

Class used to compute cocircuits and circuits.

class sign_vectors.oriented_matroids.Cocircuits(M)¶

Class used to compute cocircuits and circuits.

element(indices: list, kernel: bool = True) → sign_vectors.sign_vectors.SignVector¶: Compute the elementary vector corresponding to a list of indices.

Note

Raises a ValueError if the indices correspond to the zero vector.

element_prevent_multiple(indices: list, kernel: bool = True) → sign_vectors.sign_vectors.SignVector¶: Compute the elementary vector corresponding to a list of indices.

Note

If this results in a multiple of a previous element, a ValueError is raised.

elements(kernel: bool = True, prevent_multiples: bool = True) → set¶: Return a list of elementary vectors

generator(kernel: bool = True, prevent_multiples: bool = True, reverse: bool = False) → collections.abc.Generator¶: Return a generator of elementary vectors

minor(indices, kernel: bool = True)¶

Compute a minor given by indices

The minor is cached for efficient reuse.

TESTS:

sage: from elementary_vectors.functions import ElementaryVectors
sage: M = matrix([[1, 2, 3, 4, 5], [0, 1, 2, 2, 3]])
sage: evs = ElementaryVectors(M)
sage: evs.minors
{}
sage: evs.minor([0, 1])
1
sage: evs.minors
{(0, 1): 1}
sage: evs.minor([2, 4])
-1
sage: evs.minors
{(0, 1): 1, (2, 4): -1}

sign_vectors.oriented_matroids.cocircuits_from_matrix(M, kernel: bool = True)¶

Compute a set of cocircuits determined by the matrix M.

INPUT:

M – a matrix with real arguments.
kernel – a boolean (default: True)

OUTPUT:

If kernel is true, returns a set of cocircuits determined by the kernel of the matrix M.
If kernel 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, kernel=False)
{(-000), (0+0+), (00+-), (00-+), (0-0-), (0--0), (+000), (0++0)}

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, kernel: 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.
kernel – 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 kernel is true, the returned covectors will be determined by the kernel of the matrix M.
If kernel 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)},
 {(+-+), (---), (-+-), (--+), (++-), (+++)}]
sage: covectors_from_matrix(A, algorithm="fe", separate=True)
[{(000)},
 {(0-+), (+0+), (--0), (-0-), (0+-), (++0)},
 {(+-+), (---), (-+-), (--+), (++-), (+++)}]

TESTS:

sage: covectors_from_matrix(zero_matrix(1, 4), kernel=False, separate=False)
{(0000)}
sage: covectors_from_matrix(zero_matrix(1, 4), kernel=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].

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.

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, kernel: bool = True)¶

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

INPUT:

M – a matrix
kernel – a boolean (default: True)

OUTPUT:

If kernel is true, returns a set of topes determined by the kernel of the matrix M.
If kernel 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, kernel=False)
{(000)}

sign_vectors.oriented_matroids¶

Oriented matroids¶

Cocircuits¶

Covectors¶

Topes¶

Face enumeration¶

Table of Contents

Previous topic

Next topic

This Page