sign_vectors.oriented_matroids

Oriented matroids

Classes

OrientedMatroid(*args, **kwargs)

Class representing an oriented matroid.
class sign_vectors.oriented_matroids.OrientedMatroid(*args, **kwargs)

Class representing an oriented matroid.

This class provides methods to work with oriented matroids, including computing their faces, cocircuits, topes, and chirotope.

EXAMPLES:

There are several ways to initialize an oriented matroid. First, we define an oriented matroid from a matrix:

sage: from sign_vectors import *
sage: M = matrix([[1, 1, 0, 0], [0, 1, 1, -1]])
sage: om = OrientedMatroid(M)
sage: om
Oriented matroid of dimension 1 with elements of size 4.
sage: om.ground_set
{0, 1, 2, 3}
sage: om.rank
2

We compute the chirotope:

sage: om.chirotope()
[+, +, -, +, -, 0]
sage: om.chirotope_as_string()
'++-+-0'

Next, we count the number of faces:

sage: om.num_faces()
13
sage: om.f_vector()
[1, 6, 6]

We compute the faces explicitly:

sage: om.cocircuits()
{(-0+-), (0++-), (--00), (++00), (0--+), (+0-+)}
sage: om.topes()
{(---+), (+--+), (--+-), (-++-), (++-+), (+++-)}
sage: om.faces()
[{(0000)},
 {(-0+-), (0++-), (--00), (++00), (0--+), (+0-+)},
 {(---+), (+--+), (--+-), (-++-), (++-+), (+++-)}]

To compute the faces of a given dimension, we call:

sage: om.faces(0)
{(-0+-), (0++-), (--00), (++00), (0--+), (+0-+)}

We compute the face lattice which we can also plot:

sage: om.face_lattice()
Finite lattice containing 14 elements
sage: om.plot() # not tested
Graphics object consisting of 39 graphics primitives

The dual oriented matroid is represented by the circuits and vectors:

sage: om.circuits()
{(00++), (-+0+), (00--), (+-0-), (-+-0), (+-+0)}
sage: om.vectors()
{(0000),
 (-+-+),
 (00++),
 (-+0+),
 (-+++),
 (00--),
 (+---),
 (-+--),
 (+-0-),
 (+-+0),
 (+-+-),
 (+-++),
 (-+-0)}

We can directly compute the dual oriented matroid:

sage: om_dual = om.dual()
sage: om_dual
Oriented matroid of dimension 1 with elements of size 4.
sage: om_dual.faces()
[{(0000)},
 {(00++), (-+0+), (00--), (+-0-), (-+-0), (+-+0)},
 {(-+-+), (-+++), (+---), (-+--), (+-+-), (+-++)}]

Now, we consider an oriented matroid given by its circuits:

sage: om = OrientedMatroid.from_circuits({"0+-000", "+00-00", "0-+000", "-00+00"})
sage: om
Oriented matroid of dimension 3 with elements of size 6.
sage: om.chirotope()
[0, 0, 0, 0, 0, +, 0, 0, +, 0, 0, 0, 0, -, -]
sage: om.f_vector()
[1, 8, 24, 32, 16]
an_element() → sign_vectors.sign_vectors.SignVector

Compute a random element of the oriented matroid.

See also

chirotope() → list[sign_vectors.chirotopes.Sign]

Compute all chirotope entries of the oriented matroid.

See also

EXAMPLES:

sage: from sign_vectors import *
sage: M = matrix([[1, 2, 0, 0], [0, 1, 2, 3]])
sage: om = OrientedMatroid(M)
sage: om.chirotope()
[+, +, +, +, +, 0]
sage: om.chirotope_as_string()
'+++++0'
chirotope_as_string() → str

Represent the chirotope as a string.

chirotope_entry(indices: list[int]) → sign_vectors.chirotopes.Sign

Compute the chirotope for the given indices.

INPUT:

  • indices – a list of indices.

See also

EXAMPLES:

sage: from sign_vectors import *
sage: M = matrix([[1, 2, 0, 0], [0, 1, 2, 3]])
sage: om = OrientedMatroid(M)
sage: om.chirotope_entry([1, 2])
+
sage: om.chirotope_entry([2, 3])
0
circuit(indices: list[int]) → sign_vectors.sign_vectors.SignVector

Compute a circuit for the given indices.

INPUT:

  • indices – a list of indices.

OUTPUT:

  • The circuit as a sign vector of this oriented matroid.

See also

EXAMPLES:

sage: from sign_vectors import *
sage: M = matrix([[1, 2, 0, 0], [0, 1, 2, 3]])
sage: om = OrientedMatroid(M)
sage: om.circuit([0, 1, 2])
(+-+0)
sage: om.circuit([1, 2, 3])
(00-+)
circuits() → set[sign_vectors.sign_vectors.SignVector]

Compute the circuits of the oriented matroid.

OUTPUT:

  • A set of circuits as sign vectors of this oriented matroid.

Note

The circuits are the support-minimal sign vectors corresponding to the kernel.

See also

EXAMPLES:

sage: from sign_vectors import *
sage: M = matrix([[1, 2, 0, 0], [0, 1, 2, 3]])
sage: om = OrientedMatroid(M)
sage: om.circuits()
{(00-+), (+-0+), (-+0-), (00+-), (-+-0), (+-+0)}
cocircuit(indices: list[int]) → sign_vectors.sign_vectors.SignVector

Compute a cocircuit for the given indices.

INPUT:

  • indices – a list of indices.

OUTPUT:

  • The cocircuit as a sign vector of this oriented matroid.

See also

EXAMPLES:

sage: from sign_vectors import *
sage: M = matrix([[1, 2, 0, 0], [0, 1, 2, 3]])
sage: om = OrientedMatroid(M)
sage: om.cocircuit([0])
(0---)
sage: om.cocircuit([3])
(++00)
cocircuits() → set[sign_vectors.sign_vectors.SignVector]

Compute the cocircuits of the oriented matroid.

The cocircuits are the support-minimal sign vectors corresponding to the row space.

OUTPUT:

  • A set of cocircuits as sign vectors of this oriented matroid.

Note

The result is cached.

See also

EXAMPLES:

sage: from sign_vectors import *
sage: M = matrix([[1, 2, 0, 0], [0, 1, 2, 3]])
sage: om = OrientedMatroid(M)
sage: om.cocircuits()
{(+0--), (-0++), (--00), (++00), (0+++), (0---)}
covectors() → set[sign_vectors.sign_vectors.SignVector]

Compute the covectors of the oriented matroid.

Note

The covectors are all sign vectors corresponding to the row space.

See also

property dimension: int

The dimension of this oriented matroid.

dual() → sign_vectors.oriented_matroids.OrientedMatroid

Return the dual oriented matroid.

Note

The dual is determined from the chirotope.

elements() → set[sign_vectors.sign_vectors.SignVector]

Compute the covectors of the oriented matroid.

See also

f_vector() → list[int]

Compute the f-vector of the oriented matroid.

The f-vector (face vector) is a list where the i-th entry is the number of faces of dimension i.

See also

face_lattice() → sage.combinat.posets.lattices.LatticePoset

Return the face lattice of the oriented matroid.

OUTPUT:

  • A lattice representing the face lattice.

TESTS:

sage: from sign_vectors import *
sage: M = matrix([[1, 1, 1]])
sage: om = OrientedMatroid(M)
sage: om.face_lattice()
Finite lattice containing 4 elements

sage: M = matrix(0, 3)
sage: om = OrientedMatroid(M)
sage: om.face_lattice()
Finite lattice containing 2 elements

sage: M = matrix([[1, 0], [0, 1]])
sage: om = OrientedMatroid(M)
sage: om.face_lattice()
Finite lattice containing 10 elements
faces(dimension: Optional[int] = None) → set[sign_vectors.sign_vectors.SignVector] | list[set[sign_vectors.sign_vectors.SignVector]]

Compute the faces of the same level of the oriented matroid.

OUTPUT: If dimension is not specified, return all faces separated by dimension.

Note

The result is cached.

See also

static from_chirotope(entries: list[int] | str, rank: int, ground_set_size: int) → sign_vectors.oriented_matroids.OrientedMatroid

Create an oriented matroid from a chirotope.

INPUT:

  • entries – a list of integers or a string of +, -, 0.

OUTPUT:

EXAMPLES:

sage: from sign_vectors import *
sage: om = OrientedMatroid.from_chirotope([1, 2, -3, 4, -6, 0], 2, 4)
sage: om
Oriented matroid of dimension 1 with elements of size 4.
sage: om.faces()
[{(0000)},
 {(-0+-), (0++-), (--00), (++00), (0--+), (+0-+)},
 {(---+), (+--+), (--+-), (-++-), (++-+), (+++-)}]
sage: om.dual()
Oriented matroid of dimension 1 with elements of size 4.

The chirotope can also be specified as a string:

sage: OrientedMatroid.from_chirotope("00--0+++++", 2, 5)
Oriented matroid of dimension 1 with elements of size 5.
static from_chirotope_class(chirotope: sign_vectors.chirotopes.Chirotope) → sign_vectors.oriented_matroids.OrientedMatroid

Create an oriented matroid from a chirotope instance.

INPUT:

static from_circuits(circuits: set[sign_vectors.sign_vectors.SignVector | str], rank: Optional[int] = None, ground_set_size: Optional[int] = None) → sign_vectors.oriented_matroids.OrientedMatroid

Create an oriented matroid from circuits.

INPUT:

  • circuits – a set (or list) of sign vectors or strings representing the circuits.

  • rank – the rank of the oriented matroid (optional).

  • ground_set_size – the size of the ground set (optional).

EXAMPLES:

sage: from sign_vectors import *
sage: om = OrientedMatroid.from_circuits({"0+0", "+00"})
sage: om
Oriented matroid of dimension 0 with elements of size 3.
sage: om.chirotope()
[0, 0, +]
sage: om.faces()
[{(000)}, {(00+), (00-)}]

TESTS:

sage: om = OrientedMatroid.from_circuits([], ground_set_size=4)
sage: om
Oriented matroid of dimension 3 with elements of size 4.
static from_cocircuits(cocircuits: set[sign_vectors.sign_vectors.SignVector | str], rank: Optional[int] = None, ground_set_size: Optional[int] = None) → sign_vectors.oriented_matroids.OrientedMatroid

Create an oriented matroid from cocircuits.

INPUT:

  • cocircuits – a set (or list) of sign vectors or strings representing the cocircuits.

  • rank – the rank of the oriented matroid (optional).

  • ground_set_size – the size of the ground set (optional).

EXAMPLES:

sage: from sign_vectors import *
sage: om = OrientedMatroid.from_cocircuits({"0+", "+0"})
sage: om
Oriented matroid of dimension 1 with elements of size 2.
sage: om.faces()
[{(00)}, {(+0), (0-), (0+), (-0)}, {(--), (+-), (-+), (++)}]

Specify rank to speed up computations:

sage: om = OrientedMatroid.from_cocircuits({"0+", "+0"}, rank=2)
sage: om
Oriented matroid of dimension 1 with elements of size 2.
sage: om.faces()
[{(00)}, {(+0), (0-), (0+), (-0)}, {(--), (+-), (-+), (++)}]

You can also use sign vector objects as input:

sage: om = OrientedMatroid.from_cocircuits({sign_vector("0+"), sign_vector("+0")})
sage: om
Oriented matroid of dimension 1 with elements of size 2.
sage: om.faces()
[{(00)}, {(+0), (0-), (0+), (-0)}, {(--), (+-), (-+), (++)}]

TESTS:

sage: om = OrientedMatroid.from_cocircuits(["0++", "+00"])
sage: om
Oriented matroid of dimension 1 with elements of size 3.
sage: sorted(om.faces(0), key=lambda X: hash(X))
[(0++), (+00), (-00), (0--)]
sage: om.faces(1)
{(---), (+--), (+++), (-++)}

sage: om = OrientedMatroid.from_cocircuits([], ground_set_size=3)
sage: om
Oriented matroid of dimension -1 with elements of size 3.
sage: om.faces()
[{(000)}]
sage: om.circuits()
{(-00), (00+), (00-), (0+0), (0-0), (+00)}
sage: om.chirotope()
[+]
sage: om.dual()
Oriented matroid of dimension 2 with elements of size 3.
sage: om.dual().cocircuits()
{(-00), (00+), (00-), (0+0), (0-0), (+00)}
static from_topes(topes: list[sign_vectors.sign_vectors.SignVector | str] | set[sign_vectors.sign_vectors.SignVector | str]) → sign_vectors.oriented_matroids.OrientedMatroid

Create an oriented matroid from a tope set.

INPUT:

  • topes – a list or set of sign vectors or strings representing the topes.

EXAMPLES:

sage: from sign_vectors import *
sage: om = OrientedMatroid.from_topes({"+++"})
sage: om
Oriented matroid of dimension 0 with elements of size 3.
sage: om.faces()
[{(000)}, {(---), (+++)}]
sage: om.chirotope()
[+, +, +]

sage: om = OrientedMatroid.from_topes([[-1, 1, -1, 1], [-1, -1, -1, 1], [-1, 1, -1, -1], [-1, -1, 1, 1]])
sage: om
Oriented matroid of dimension 1 with elements of size 4.
sage: om.faces()
[{(0000)},
 {(++0-), (+0+-), (--0+), (0-++), (0+--), (-+-0), (-0-+), (+-+0)},
 {(-+-+), (---+), (-+--), (--++), (+-+-), (++--), (+-++), (+++-)}]

TESTS:

sage: om = OrientedMatroid.from_topes(["000"])
sage: om
Oriented matroid of dimension -1 with elements of size 3.
sage: OrientedMatroid.from_topes([])
Traceback (most recent call last):
...
ValueError: Tope set must not be empty.
property ground_set: set[int]

The ground set of this oriented matroid.

property ground_set_size: int

The size of the ground set of this oriented matroid.

loops() → set[int]

Compute the loops of this oriented matroid.

A loop is a component where every face is zero.

Note

The result is cached.

num_faces() → int

Return the total number of faces (covectors) of the oriented matroid.

See also

parallel_classes() → list[set[int]]

Compute the parallel classes of this oriented matroid.

plot(vertex_size: int = 600, figsize: Optional[int] = None, aspect_ratio=None) → None

Plot the big face lattice of the oriented matroid.

INPUT:

  • vertex_size – the size of the vertices in the plot.

  • figsize – the size of the figure.

  • aspect_ratio – the aspect ratio of the plot.

Note

Only works well for small length and dimension.

property rank: int

The rank of this oriented matroid.

set_face_connections(value: bool = True) → None

Keep track of connections between faces.

If this is set to true, the object will keep track of connections between faces while computing. This improves performance for plotting but slightly slows down other computations.

topes() → set[sign_vectors.sign_vectors.SignVector]

Compute the topes of the oriented matroid.

The topes are the support-maximal sign vectors corresponding to the row space.

See also

vectors() → set[sign_vectors.sign_vectors.SignVector]

Compute the vectors of the oriented matroid.

Note

The vectors are all sign vectors corresponding to the kernel.

See also