sign_vectors.oriented_matroids

Oriented matroids

Classes

OrientedMatroid(matrix)

An oriented matroid.
class sign_vectors.oriented_matroids.OrientedMatroid(matrix)

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

category(self)

File: sage/structure/sage_object.pyx (starting at line 484)

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.

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 elements of this oriented matroid.

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.

The covectors are all elements of this oriented matroid.

See also

property dimension: int

The dimension of this oriented matroid.

dual() → sign_vectors.oriented_matroids._OrientedMatroid

Return the dual oriented matroid.

The dual is determined from the chirotope.

dump(self, filename, compress=True)

File: sage/structure/sage_object.pyx (starting at line 445)

Same as self.save(filename, compress)

dumps(self, compress=True)

File: sage/structure/sage_object.pyx (starting at line 451)

Dump self to a string s, which can later be reconstituted as self using loads(s).

There is an optional boolean argument compress which defaults to True.

EXAMPLES:

sage: from sage.misc.persist import comp
sage: O = SageObject()
sage: p_comp = O.dumps()
sage: p_uncomp = O.dumps(compress=False)
sage: comp.decompress(p_comp) == p_uncomp
True
sage: import pickletools
sage: pickletools.dis(p_uncomp)
    0: \x80 PROTO      2
    2: c    GLOBAL     'sage.structure.sage_object SageObject'
   41: q    BINPUT     ...
   43: )    EMPTY_TUPLE
   44: \x81 NEWOBJ
   45: q    BINPUT     ...
   47: .    STOP
highest protocol among opcodes = 2
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 covector 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.

parent(self)

File: sage/structure/sage_object.pyx (starting at line 518)

Return the type of self to support the coercion framework.

EXAMPLES:

sage: t = log(sqrt(2) - 1) + log(sqrt(2) + 1); t
log(sqrt(2) + 1) + log(sqrt(2) - 1)
sage: u = t.maxima_methods()
sage: u.parent()
<class 'sage.symbolic.maxima_wrapper.MaximaWrapper'>
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.

rename(self, x=None)

File: sage/structure/sage_object.pyx (starting at line 68)

Change self so it prints as x, where x is a string.

Note

This is only supported for Python classes that derive from SageObject.

EXAMPLES:

sage: x = PolynomialRing(QQ, 'x', sparse=True).gen()
sage: g = x^3 + x - 5
sage: g
x^3 + x - 5
sage: g.rename('a polynomial')
sage: g
a polynomial
sage: g + x
x^3 + 2*x - 5
sage: h = g^100
sage: str(h)[:20]
'x^300 + 100*x^298 - '
sage: h.rename('x^300 + ...')
sage: h
x^300 + ...

Real numbers are not Python classes, so rename is not supported:

sage: a = 3.14
sage: type(a)
<... 'sage.rings.real_mpfr.RealLiteral'>
sage: a.rename('pi')
Traceback (most recent call last):
...
NotImplementedError: object does not support renaming: 3.14000000000000

Note

The reason C-extension types are not supported by default is if they were then every single one would have to carry around an extra attribute, which would be slower and waste a lot of memory.

To support them for a specific class, add a cdef public __custom_name attribute.

reset_name(self)

File: sage/structure/sage_object.pyx (starting at line 125)

Remove the custom name of an object.

EXAMPLES:

sage: P.<x> = QQ[]
sage: P
Univariate Polynomial Ring in x over Rational Field
sage: P.rename('A polynomial ring')
sage: P
A polynomial ring
sage: P.reset_name()
sage: P
Univariate Polynomial Ring in x over Rational Field
save(self, filename=None, compress=True)

File: sage/structure/sage_object.pyx (starting at line 420)

Save self to the given filename.

EXAMPLES:

sage: f = x^3 + 5
sage: f.save(os.path.join(SAGE_TMP, 'file'))
sage: load(os.path.join(SAGE_TMP, 'file.sobj'))
x^3 + 5
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.

See also

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

Compute the vectors of the oriented matroid.

The vectors are the elements generated by the circuits. They are the covectors of the dual oriented matroid.

See also