elementary_vectors.functions¶

Elementary vectors (circuits and cocircuits)¶

Elementary vectors are support minimal vectors of a subspace. They are also called circuits.

Functions

`circuit_generator`(matrix[, ...])	Generator of circuits of a matrix.
`circuit_kernel_matrix`(matrix)	Right kernel matrix based on circuits.
`circuits`(matrix[, prevent_multiples])	Compute the circuits of a matrix.
`cocircuit_generator`(matrix[, ...])	Generator of cocircuits of a matrix.
`cocircuits`(matrix[, prevent_multiples])	Compute the cocircuits of a matrix.
`degenerate_circuits`(matrix)	Compute degenerate circuits of a matrix.
`degenerate_cocircuits`(matrix)	Compute degenerate cocircuits of a matrix.

Classes

CircuitEnumerator(matrix)

A class used to compute elementary vectors (circuits and cocircuits).

Exceptions

MultipleException

Raised when a multiple of a previously computed elementary vector is detected.

class elementary_vectors.functions.CircuitEnumerator(matrix: matrix)¶

A class used to compute elementary vectors (circuits and cocircuits).

If you want to compute circuits and cocircuits of the same matrix, use this class instead of the functions circuits() and cocircuits() since they share computed maximal minors. Also use this class if you want to compute individual circuits or cocircuits.

Note

Whenever a maximal minor is computed, it is stored in a dictionary for efficient reuse.
If the provided matrix is not full rank, it is replaced by a full-rank one.

EXAMPLES:

sage: from elementary_vectors import *
sage: M = matrix([[1, 2, 4, 1, -1], [0, 1, 2, 3, 4]])
sage: ce = CircuitEnumerator(M)
sage: ce
Circuit enumerator of 2x5 matrix
sage: ce.circuits()
[(0, -2, 1, 0, 0),
 (5, -3, 0, 1, 0),
 (9, -4, 0, 0, 1),
 (10, 0, -3, 2, 0),
 (18, 0, -4, 0, 2),
 (7, 0, 0, -4, 3),
 (0, 7, 0, -9, 5),
 (0, 0, 7, -18, 10)]
sage: ce.circuits(prevent_multiples=False)
[(0, -2, 1, 0, 0),
 (5, -3, 0, 1, 0),
 (9, -4, 0, 0, 1),
 (10, 0, -3, 2, 0),
 (18, 0, -4, 0, 2),
 (7, 0, 0, -4, 3),
 (0, 10, -5, 0, 0),
 (0, 18, -9, 0, 0),
 (0, 7, 0, -9, 5),
 (0, 0, 7, -18, 10)]
sage: ce.cocircuits()
[(0, -1, -2, -3, -4), (1, 0, 0, -5, -9), (3, 5, 10, 0, -7), (4, 9, 18, 7, 0)]
sage: ce.cocircuits(prevent_multiples=False)
[(0, -1, -2, -3, -4),
 (1, 0, 0, -5, -9),
 (2, 0, 0, -10, -18),
 (3, 5, 10, 0, -7),
 (4, 9, 18, 7, 0)]

We compute individual elements:

sage: ce.minor([0, 2])
2
sage: ce.circuit([0, 2, 3])
(10, 0, -3, 2, 0)
sage: ce.cocircuit([0])
(0, -1, -2, -3, -4)
sage: ce.random_circuit() # random
(0, 0, 7, -18, 10)
sage: ce.random_cocircuit() # random
(3, 5, 10, 0, -7)

Now, we consider an example that involves many zero minors:

sage: M = matrix([[1, 2, 4, 0], [0, 1, 2, 0]])
sage: M.minors(2)
[1, 2, 0, 0, 0, 0]
sage: ce = CircuitEnumerator(M)
sage: ce.circuits()
[(0, -2, 1, 0), (0, 0, 0, 1)]

circuit(indices: List[int], prevent_multiple: bool = False) → vector¶

Compute the circuit corresponding to a list of indices.

INPUT:

indices – a list of rank + 1 integers
prevent_multiple – a boolean

Return the circuit corresponding to the given indices.

If prevent_multiple is true, a ValueError is raised if a multiple of this element has been computed before.

Note

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

EXAMPLES:

sage: from elementary_vectors import *
sage: M = matrix([[1, 2, 4, 0], [0, 1, 2, 0]])
sage: ce = CircuitEnumerator(M)

In this example, circuits require 3 indices:

sage: ce.circuit([0, 1, 2])
(0, -2, 1, 0)
sage: ce.circuit([1, 2, 3])
Traceback (most recent call last):
...
ValueError: The indices [1, 2, 3] correspond to the zero vector.

circuit_generator(prevent_multiples: bool = True, reverse: bool = False) → Iterator[vector]¶: Return a generator of circuits

circuits(prevent_multiples: bool = True) → List[vector]¶

Return a list of circuits

EXAMPLES:

sage: from elementary_vectors import *
sage: M = matrix([[1, 2, 0, 0], [0, 1, 2, 3]])
sage: M
[1 2 0 0]
[0 1 2 3]
sage: ce = CircuitEnumerator(M)
sage: ce.circuits()
[(4, -2, 1, 0), (6, -3, 0, 1), (0, 0, -3, 2)]

TESTS:

sage: ce = CircuitEnumerator(matrix(0, 4))
sage: ce.circuits()
[(1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0), (0, 0, 0, 1)]
sage: ce = CircuitEnumerator(matrix([[1, 0, 0], [0, 0, 0]]))
sage: ce.circuits()
[(0, -1, 0), (0, 0, -1)]

cocircuit(indices: List[int], prevent_multiple: bool = False) → vector¶

Compute the cocircuit corresponding to a list of indices.

INPUT:

indices – a list of rank - 1 integers
prevent_multiple – a boolean

Return the cocircuit corresponding to the given indices.

If prevent_multiple is true, a ValueError is raised if a multiple of this element has been computed before.

Note

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

EXAMPLES:

sage: from elementary_vectors import *
sage: M = matrix([[1, 2, 4, 0], [0, 1, 2, 0]])
sage: ce = CircuitEnumerator(M)

In this example, cocircuits require 1 index:

sage: ce.cocircuit([0])
(0, -1, -2, 0)
sage: ce.cocircuit([3])
Traceback (most recent call last):
...
ValueError: The indices [3] correspond to the zero vector.

cocircuit_generator(prevent_multiples: bool = True, reverse: bool = False) → Iterator[vector]¶: Return a generator of cocircuits

cocircuits(prevent_multiples: bool = True) → List[vector]¶

Return a list of cocircuits

EXAMPLES:

sage: from elementary_vectors import *
sage: M = matrix([[1, 2, 0, 0], [0, 1, 2, 3]])
sage: M
[1 2 0 0]
[0 1 2 3]
sage: ce = CircuitEnumerator(M)
sage: ce.cocircuits()
[(0, -1, -2, -3), (1, 0, -4, -6), (2, 4, 0, 0)]

compute_minors() → None¶: Compute all maximal minors of the matrix.

degenerate_circuits() → List[vector]¶

Return a list of degenerate circuits

EXAMPLES:

sage: from elementary_vectors import *
sage: M = matrix([[1, 0, 1, 0], [0, 0, 1, 1]])
sage: ce = CircuitEnumerator(M)
sage: ce.degenerate_circuits()
[(0, -1, 0, 0)]

sage: M = matrix([[1, 1, 1, 0], [0, 1, 1, 1]])
sage: ce = CircuitEnumerator(M)
sage: ce.degenerate_circuits()
[(0, -1, 1, 0)]

We consider an example with 4 zero minors. There are six multiples that involve 2 of them each:

sage: M = matrix([[1, -1, 0, 0, 1, 1], [0, 0, 1, 0, 1, 2], [0, 0, 0, 1, 1, 3]])
sage: M
[ 1 -1  0  0  1  1]
[ 0  0  1  0  1  2]
[ 0  0  0  1  1  3]
sage: ce = CircuitEnumerator(M)
sage: ce.degenerate_circuits()
[(-1, -1, 0, 0, 0, 0)]

degenerate_cocircuits() → List[vector]¶

Return a list of degenerate cocircuits

EXAMPLES:

sage: from elementary_vectors import *
sage: M = matrix([[1, 0, 1, 0], [0, 0, 1, 1]])
sage: M
[1 0 1 0]
[0 0 1 1]
sage: ce = CircuitEnumerator(M)
sage: ce.degenerate_cocircuits()
[(0, 0, -1, -1), (1, 0, 0, -1), (1, 0, 1, 0)]

minor(indices: List[int], mark_if_zero: bool = False)¶

Compute a minor given by (sorted) indices.

Note

The minor is cached for efficient reuse.

TESTS:

sage: from elementary_vectors import *
sage: M = matrix([[1, 2, 4, 1, -1], [0, 1, 2, 3, 4]])
sage: ce = CircuitEnumerator(M)
sage: ce._minors
{}
sage: ce.minor([0, 1])
1
sage: ce._minors
{(0, 1): 1}
sage: ce.minor([2, 4])
18
sage: ce._minors
{(0, 1): 1, (2, 4): 18}
sage: ce.minor([0, 1, 2])
Traceback (most recent call last):
...
ValueError: Indices (0, 1, 2) should have size 2 and not 3.

random_circuit() → vector | None¶: Return a random circuit

Note

If no circuit exists or the zero vector has been generated, None is returned.

random_cocircuit() → vector | None¶: Return a random cocircuit

Note

If no cocircuit exists or the zero vector has been generated, None is returned.

exception elementary_vectors.functions.MultipleException¶: Raised when a multiple of a previously computed elementary vector is detected.

elementary_vectors.functions.circuit_generator(matrix: matrix, prevent_multiples: bool = True, reverse: bool = False) → Iterator[vector]¶

Generator of circuits of a matrix.

INPUT: - matrix – a matrix - prevent_multiples – a boolean (default: True) - reverse – a boolean (default: False)

OUTPUT: A generator of the circuits of this matrix. These are the nonzero support-minimal elements in the kernel.

EXAMPLES:

sage: from elementary_vectors.functions import circuit_generator
sage: M = matrix([[1, 2, 0, 0], [0, 1, 2, 3]])
sage: M
[1 2 0 0]
[0 1 2 3]
sage: list(circuit_generator(M))
[(4, -2, 1, 0), (6, -3, 0, 1), (0, 0, -3, 2)]
sage: list(circuit_generator(M, reverse=True))
[(0, 0, -6, 4), (6, -3, 0, 1), (4, -2, 1, 0)]

elementary_vectors.functions.circuit_kernel_matrix(matrix: matrix) → matrix¶

Right kernel matrix based on circuits.

OUTPUT: A right kernel matrix. Each row is a circuit of the input matrix. Therefore, the output matrix is division-free. Also works for symbolic matrices.

Note

Raises a ValueError if the matrix has no constant nonzero maximal minor.

EXAMPLES:

sage: from elementary_vectors import *
sage: M = matrix([[1, 0, 1, -1, 0], [0, 1, 1, 1, -1]])
sage: M
[ 1  0  1 -1  0]
[ 0  1  1  1 -1]
sage: circuit_kernel_matrix(M)
[1 0 0 1 1]
[0 1 0 0 1]
[0 0 1 1 2]
sage: M = matrix([[1, 1, -1, -1, 0], [2, 1, -1, 0, 1], [1, 1, 1, 1, 1]])
sage: M
[ 1  1 -1 -1  0]
[ 2  1 -1  0  1]
[ 1  1  1  1  1]
sage: circuit_kernel_matrix(M)
[-1  0  0 -1  2]
[ 0 -1  1 -2  2]
sage: var('a')
a
sage: M = matrix([[1, 0, 1, -1, 0], [0, 1, a, 1, -1]])
sage: M
[ 1  0  1 -1  0]
[ 0  1  a  1 -1]
sage: circuit_kernel_matrix(M)
[    1     0     0     1     1]
[    0     1     0     0     1]
[    0     0     1     1 a + 1]

TESTS:

sage: circuit_kernel_matrix(identity_matrix(3, 3))
[]
sage: _.dimensions()
(0, 3)
sage: circuit_kernel_matrix(matrix(0, 3))
[1 0 0]
[0 1 0]
[0 0 1]

sage: M = matrix([[0, 1], [0, 1]])
sage: circuit_kernel_matrix(M)
[1 0]

elementary_vectors.functions.circuits(matrix, prevent_multiples: bool = True) → List[vector]¶

Compute the circuits of a matrix.

INPUT:

matrix – a matrix
prevent_multiples – a boolean (default: True)

OUTPUT: Return the circuits of this matrix. These are the nonzero support-minimal elements in the kernel.