elementary_vectors.functions

Computing elementary vectors

Functions

circuits(M)

Compute the circuits of a matrix.

cocircuits(M)

Compute the cocircuits of a matrix.

elementary_vectors(M[, dual, ...])

Compute elementary vectors of a subspace determined by a matrix.

kernel_matrix_using_elementary_vectors(M)

Division-free right kernel matrix based on elementary vectors.

Classes

ElementaryVectors(M)

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(M: 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.functions import ElementaryVectors
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(dual=False)
[(0, -1, -2, -3, -4), (1, 0, 0, -5, -9), (3, 5, 10, 0, -7), (4, 9, 18, 7, 0)]
sage: evs.elements(dual=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], dual=True)
(10, 0, -3, 2, 0)
sage: evs.element([0], dual=False)
(0, -1, -2, -3, -4)
sage: evs.random_element() # random
(0, 0, 7, -18, 10)
sage: evs.random_element(dual=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(dual: bool = True) → Generator[sage.modules.free_module_element.vector, None, None]

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(dual=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(dual=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], dual: 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

  • dual – a boolean

  • prevent_multiple – a boolean

If dual 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(dual: bool = True, prevent_multiples: bool = True) → List[sage.modules.free_module_element.vector]

Return a list of elementary vectors

generator(dual: bool = True, prevent_multiples: bool = True, reverse: bool = False) → Generator[sage.modules.free_module_element.vector, None, None]

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.functions import ElementaryVectors
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(dual: 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(M: sage.matrix.constructor.matrix) → List[sage.modules.free_module_element.vector]

Compute the circuits of a matrix. INPUT:

  • M – a matrix

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

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(M: sage.matrix.constructor.matrix) → List[sage.modules.free_module_element.vector]

Compute the cocircuits of a matrix.

INPUT:

  • M – a matrix

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

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.elementary_vectors(M: sage.matrix.constructor.matrix, dual: bool = True, prevent_multiples: bool = True, generator: bool = False) → Union[List[sage.modules.free_module_element.vector], Generator[sage.modules.free_module_element.vector, None, None]]

Compute elementary vectors of a subspace determined by a matrix.

INPUT:

  • M – a matrix

  • dual – a boolean (default: True)

  • prevent_multiples – a boolean (default: True)

  • generator – a boolean (default: False)

OUTPUT: Return a list of elementary vectors in the kernel of a matrix given by the matrix M. To compute the elementary vectors in the row space, pass False for dual.

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

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: elementary_vectors(M)
[(4, -2, 1, 0), (6, -3, 0, 1), (0, 0, -3, 2)]
sage: elementary_vectors(M, 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 dual=False:

sage: elementary_vectors(M, dual=False)
[(0, -1, -2, -3), (1, 0, -4, -6), (2, 4, 0, 0)]

We can also compute elementary vectors over a finite field:

sage: B = matrix(GF(7), [[1, 2, 3, 4, 0], [0, 5, 2, 3, 3]])
sage: B
[1 2 3 4 0]
[0 5 2 3 3]
sage: elementary_vectors(B)
[(3, 5, 5, 0, 0),
 (0, 4, 0, 5, 0),
 (6, 4, 0, 0, 5),
 (1, 0, 4, 2, 0),
 (2, 0, 4, 0, 2),
 (5, 0, 0, 4, 3),
 (0, 2, 1, 0, 3),
 (0, 0, 5, 5, 1)]

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: elementary_vectors(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: elementary_vectors(M)
[(-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: elementary_vectors(M)
[(2*y, -2*x, x, 0), (3*y, -3*x, 0, x), (0, 0, -3*x, 2*x)]

TESTS:

sage: elementary_vectors(random_matrix(QQ, 0, 4))
[(1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0), (0, 0, 0, 1)]
sage: elementary_vectors(matrix([[1, 0, 0], [0, 0, 0]]))
[(0, -1, 0), (0, 0, -1)]
elementary_vectors.functions.kernel_matrix_using_elementary_vectors(M: sage.matrix.constructor.matrix) → sage.matrix.constructor.matrix

Division-free right kernel matrix based on elementary vectors.

INPUT:

  • M – a matrix

OUTPUT: A right kernel matrix of M. It also works for symbolic matrices.

Note

Raises a ValueError if M 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: kernel_matrix_using_elementary_vectors(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: kernel_matrix_using_elementary_vectors(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: kernel_matrix_using_elementary_vectors(M)
[    1     0     0     1     1]
[    0     1     0     0     1]
[    0     0     1     1 a + 1]

TESTS:

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

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