elementary_vectors.functions

Computing elementary vectors

Functions

elementary_vectors(M[, kernel, generator])

Compute elementary vectors of a subspace determined by a matrix or a list of maximal minors.

kernel_matrix_using_elementary_vectors(M)

Division-free computation of the right kernel based on elementary vectors.

Classes

ElementaryVectors(M)

A class used to compute elementary vectors.

class elementary_vectors.functions.ElementaryVectors(M)

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

TESTS:

This used to return a multiple:

sage: M = matrix([
....:     [-1, 1, -2, -1, -2, -1, -4, -4],
....:     [-1, 71, -12, 0, 6, 0, 0, 1],
....:     [0, 0, 1, 0, -2, 0, -1, 6],
....:     [1, 0, 1, 0, -5, 0, 1, 1],
....:     [-1, -1, 0, 1, -1, 1, 15, -1]
....: ])
sage: evs = ElementaryVectors(M)
sage: len(evs.elements())
14
element(indices: list, kernel: bool = True)

Compute the elementary vector corresponding to a list of indices.

Note

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

element_prevent_multiple(indices: list, kernel: bool = True)

Compute the elementary vector corresponding to a list of indices.

Note

If this results in a multiple of a previous element, a ValueError is raised.

element_prevent_multiple_dual(indices: list)

Compute the elementary vector corresponding to a list of indices.

Note

If this results in a multiple of a previous element, a ValueError is raised.

elements(kernel: bool = True, prevent_multiples: bool = True) list

Return a list of elementary vectors

generator(kernel: bool = True, prevent_multiples: bool = True, reverse: bool = False) collections.abc.Generator

Return a generator of elementary vectors

minor(indices)

Compute a minor given by indices

The minor is cached for efficient reuse.

TESTS:

sage: from elementary_vectors.functions import ElementaryVectors
sage: M = matrix([[1, 2, 3, 4, 5], [0, 1, 2, 2, 3]])
sage: evs = ElementaryVectors(M)
sage: evs.minors
{}
sage: evs.minor([0, 1])
1
sage: evs.minors
{(0, 1): 1}
sage: evs.minor([2, 4])
-1
sage: evs.minors
{(0, 1): 1, (2, 4): -1}
random_element(kernel: bool = True)

Return a random elementary vector

Note

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

set_combinations(combinations=None) None

Set or reset combinations.

set_combinations_dual(combinations=None) None

Set or reset combinations.

elementary_vectors.functions.elementary_vectors(M, kernel: bool = True, generator: bool = False)

Compute elementary vectors of a subspace determined by a matrix or a list of maximal minors.

INPUT:

  • M – a matrix

  • kernel – 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 kernel.

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

EXAMPLES:

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

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

sage: elementary_vectors(M, kernel=False)
[(0, -2, -4, 0, 0), (0, 2, 0, 4, 0), (-4, 0, 0, 0, -4), (0, 0, -2, 2, 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('c')
c
sage: C = matrix([[c, 0, 0, 2, 1, 1], [0, 1, 0, 1, 2, 1], [0, 0, 1, 1, 1, 2]])
sage: C
[c 0 0 2 1 1]
[0 1 0 1 2 1]
[0 0 1 1 1 2]
sage: elementary_vectors(C)
[(2, c, c, -c, 0, 0),
 (1, 2*c, c, 0, -c, 0),
 (1, c, 2*c, 0, 0, -c),
 (-1, c, 0, c, -c, 0),
 (-3, -c, 0, 2*c, 0, -c),
 (-1, -3*c, 0, 0, 2*c, -c),
 (3, 0, c, -2*c, c, 0),
 (1, 0, -c, -c, 0, c),
 (-1, 0, -3*c, 0, -c, 2*c),
 (4, 0, 0, -3*c, c, c),
 (0, 3, 1, 1, -2, 0),
 (0, 1, 3, 1, 0, -2),
 (0, -1, 1, 0, 1, -1),
 (0, 4, 0, 1, -3, 1),
 (0, 0, 4, 1, 1, -3)]

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)

Division-free computation of the right kernel based on elementary vectors.

INPUT:

  • M – a matrix

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

Note

A ValueError is returned 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]