elementary_vectors.functions

Computing elementary vectors

Functions

elementary_vectors(M[, dual, ...])	Compute elementary vectors of a subspace determined by a matrix or a list of maximal minors.
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)]

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) → int

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.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 or a list of maximal minors.

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)]

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]