elementary_vectors.functions

Computing elementary vectors

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

Functions

circuits(matrix[, prevent_multiples, generator])

Compute the circuits 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.

division_free_kernel_matrix(matrix)

Division-free right kernel matrix based on elementary vectors.

Classes

ElementaryVectors(matrix)

A class used to compute elementary vectors.

Exceptions

MultipleException

Raised when a multiple of a previously computed elementary vector is detected.
class elementary_vectors.functions.ElementaryVectors(matrix: sage.matrix.constructor.matrix)

A class used to compute elementary vectors.

Whenever a maximal minor is computed, it is stored in a dictionary for efficient reuse. Supports elementary vectors in the kernel and row space.

EXAMPLES:

sage: from elementary_vectors import *
sage: M = matrix([[1, 2, 4, 1, -1], [0, 1, 2, 3, 4]])
sage: evs = ElementaryVectors(M)
sage: evs.elements()
[(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: evs.elements(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: evs.elements(kernel=False)
[(0, -1, -2, -3, -4), (1, 0, 0, -5, -9), (3, 5, 10, 0, -7), (4, 9, 18, 7, 0)]
sage: evs.elements(kernel=False, 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)]

sage: evs.minor([0, 2])
2
sage: evs.element([0, 2, 3])
(10, 0, -3, 2, 0)
sage: evs.element([0])
(0, -1, -2, -3, -4)
sage: evs.element([0, 2, 3], kernel=True)
(10, 0, -3, 2, 0)
sage: evs.element([0], kernel=False)
(0, -1, -2, -3, -4)
sage: evs.random_element() # random
(0, 0, 7, -18, 10)
sage: evs.random_element(kernel=False) # random
(3, 5, 10, 0, -7)

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: evs = ElementaryVectors(M)
sage: evs.elements()
[(0, -2, 1, 0), (0, 0, 0, 1)]
compute_minors() → None

Compute all maximal minors of the matrix.

degenerate_elements(kernel: bool = True) → Iterator[sage.modules.free_module_element.vector]

Generator of elementary vectors with smaller-than-usual support.

EXAMPLES:

sage: from elementary_vectors import *
sage: M = matrix([[1, 0, 1, 0], [0, 0, 1, 1]])
sage: evs = ElementaryVectors(M)
sage: list(evs.degenerate_elements())
[(0, -1, 0, 0)]
sage: list(evs.degenerate_elements(kernel=False))
[(0, 0, -1, -1), (1, 0, 0, -1), (1, 0, 1, 0)]

sage: M = matrix([[1, 1, 1, 0], [0, 1, 1, 1]])
sage: evs = ElementaryVectors(M)
sage: list(evs.degenerate_elements())
[(0, -1, 1, 0)]
sage: list(evs.degenerate_elements(kernel=False))
[(1, 0, 0, -1)]

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: evs = ElementaryVectors(M)
sage: list(evs.degenerate_elements())
[(-1, -1, 0, 0, 0, 0)]
element(indices: List[int], kernel: Optional[bool] = None, prevent_multiple: bool = False) → sage.modules.free_module_element.vector

Compute the elementary vector corresponding to a list of indices.

INPUT:

  • indices – a list of rank - 1 (for elements in the row space)

    or rank + 1 (for elements in the kernel) integers

  • kernel – a boolean

  • prevent_multiple – a boolean

If kernel is true, return an elementary vector in the kernel and otherwise in the row space. If not specified, this is determined from the number of 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: evs = ElementaryVectors(M)

Elementary vectors in the kernel require 3 indices:

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

For the row space, we need 1 element:

sage: evs.element([0])
(0, -1, -2, 0)

TESTS:

sage: evs.element([1, 2])
Traceback (most recent call last):
...
ValueError: The number of indices should be 1 or 3 but got 2.

evs._element_kernel([1, 2, 3])
(0, 0, 0, 0)
evs._element_row_space([3])
(0, 0, 0, 0)
elements(kernel: bool = True, prevent_multiples: bool = True) → List[sage.modules.free_module_element.vector]

Return a list of elementary vectors

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: evs = ElementaryVectors(M)
sage: evs.elements(M)
[(4, -2, 1, 0), (6, -3, 0, 1), (0, 0, -3, 2)]
sage: evs.elements(prevent_multiples=False)
[(4, -2, 1, 0), (6, -3, 0, 1), (0, 0, -3, 2), (0, 0, -6, 4)]

By default, the elementary vectors in the kernel are computed. To consider the row space, pass kernel=False:

sage: evs.elements(kernel=False)
[(0, -1, -2, -3), (1, 0, -4, -6), (2, 4, 0, 0)]

Variables are also supported:

sage: var('a, b')
(a, b)
sage: M = matrix([[1, 2, a, 0], [0, 1, 2, b]])
sage: M
[1 2 a 0]
[0 1 2 b]
sage: evs = ElementaryVectors(M)
sage: evs.elements(M)
[(-a + 4, -2, 1, 0), (2*b, -b, 0, 1), (a*b, 0, -b, 2), (0, a*b, -2*b, -a + 4)]

Matrices over the polynomial ring work, too:

sage: R = PolynomialRing(ZZ, "x")
sage: x = R.gen()
sage: M = matrix([[1, 2, x, 0], [0, 1, 2, x]])
sage: M
[1 2 x 0]
[0 1 2 x]
sage: evs = ElementaryVectors(M)
sage: evs.elements()
[(-x + 4, -2, 1, 0), (2*x, -x, 0, 1), (x^2, 0, -x, 2), (0, x^2, -2*x, -x + 4)]
sage: R = PolynomialRing(ZZ, "x, y")
sage: x, y = R.gens()
sage: M = matrix([[x, y, 0, 0], [0, 1, 2, 3]])
sage: M
[x y 0 0]
[0 1 2 3]
sage: evs = ElementaryVectors(M)
sage: evs.elements()
[(2*y, -2*x, x, 0), (3*y, -3*x, 0, x), (0, 0, -3*x, 2*x)]

TESTS:

sage: evs = ElementaryVectors(matrix(0, 4))
sage: evs.elements()
[(1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0), (0, 0, 0, 1)]
sage: evs = ElementaryVectors(matrix([[1, 0, 0], [0, 0, 0]]))
sage: evs.elements()
[(0, -1, 0), (0, 0, -1)]
generator(kernel: bool = True, prevent_multiples: bool = True, reverse: bool = False) → Iterator[sage.modules.free_module_element.vector]

Return a generator of elementary vectors

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

Compute a minor given by (sorted) indices.

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: evs = ElementaryVectors(M)
sage: evs._minors
{}
sage: evs.minor([0, 1])
1
sage: evs._minors
{(0, 1): 1}
sage: evs.minor([2, 4])
18
sage: evs._minors
{(0, 1): 1, (2, 4): 18}
sage: evs.minor([0, 1, 2])
Traceback (most recent call last):
...
ValueError: Indices (0, 1, 2) should have size 2 and not 3.
random_element(kernel: bool = True) → Optional[sage.modules.free_module_element.vector]

Return a random elementary vector

Note

If no elementary vector 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.circuits(matrix, prevent_multiples: bool = True, generator: bool = False) → Union[List[sage.modules.free_module_element.vector], Iterator[sage.modules.free_module_element.vector]]

Compute the circuits of a matrix.

INPUT:

  • matrix – a matrix

  • prevent_multiples – a boolean (default: True)

  • generator – a boolean (default: False)

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

  • If generator is True, the output will be a generator object instead of a list.

See also

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: circuits(M)
[(4, -2, 1, 0), (6, -3, 0, 1), (0, 0, -3, 2)]
elementary_vectors.functions.cocircuits(matrix: sage.matrix.constructor.matrix, prevent_multiples: bool = True, generator: bool = False) → Union[List[sage.modules.free_module_element.vector], Iterator[sage.modules.free_module_element.vector]]

Compute the cocircuits of a matrix.

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

OUTPUT: Return the cocircuits of this matrix. These are the nonzero support-minimal elements in the row space.

  • If generator is True, the output will be a generator object instead of a list.

See also

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: cocircuits(M)
[(0, -1, -2, -3), (1, 0, -4, -6), (2, 4, 0, 0)]
elementary_vectors.functions.degenerate_circuits(matrix: sage.matrix.constructor.matrix) → list[sage.modules.free_module_element.vector]

Compute degenerate circuits of a matrix.

OUTPUT: Return a list of degenerate circuits of the matrix. These are the nonzero support-minimal elements in the kernel with support smaller than rank + 1.

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: degenerate_circuits(M)
[(0, -1, 0, 0)]
sage: M = matrix([[1, 1, 1, 0], [0, 1, 1, 1]])
sage: M
[1 1 1 0]
[0 1 1 1]
sage: degenerate_circuits(M)
[(0, -1, 1, 0)]
elementary_vectors.functions.degenerate_cocircuits(matrix: sage.matrix.constructor.matrix) → list[sage.modules.free_module_element.vector]

Compute degenerate cocircuits of a matrix.

OUTPUT: Return a list of degenerate cocircuits of the matrix. These are the nonzero support-minimal elements in the row space with support smaller than rank - 1.

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: degenerate_cocircuits(M)
[(0, 0, -1, -1), (1, 0, 0, -1), (1, 0, 1, 0)]
sage: M = matrix([[1, 1, 1, 0], [0, 1, 1, 1]])
sage: M
[1 1 1 0]
[0 1 1 1]
sage: degenerate_cocircuits(M)
[(1, 0, 0, -1)]
elementary_vectors.functions.division_free_kernel_matrix(matrix: sage.matrix.constructor.matrix) → sage.matrix.constructor.matrix

Division-free right kernel matrix based on elementary vectors.

OUTPUT: A right kernel matrix. It 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: division_free_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: division_free_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: division_free_kernel_matrix(M)
[    1     0     0     1     1]
[    0     1     0     0     1]
[    0     0     1     1 a + 1]

TESTS:

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

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