elementary_vectors.functions

Computing elementary vectors

Functions

circuits(matrix)

Compute the circuits of a matrix.

cocircuits(matrix)

Compute the cocircuits of a matrix.

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

Compute elementary vectors of a subspace determined by a matrix.

kernel_matrix_using_elementary_vectors(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.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)]
category(self)

File: sage/structure/sage_object.pyx (starting at line 484)

compute_minors() → None

Compute all maximal minors of the matrix.

degenerate_elements(dual: 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(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)]
dump(self, filename, compress=True)

File: sage/structure/sage_object.pyx (starting at line 445)

Same as self.save(filename, compress)

dumps(self, compress=True)

File: sage/structure/sage_object.pyx (starting at line 451)

Dump self to a string s, which can later be reconstituted as self using loads(s).

There is an optional boolean argument compress which defaults to True.

EXAMPLES:

sage: from sage.misc.persist import comp
sage: O = SageObject()
sage: p_comp = O.dumps()
sage: p_uncomp = O.dumps(compress=False)
sage: comp.decompress(p_comp) == p_uncomp
True
sage: import pickletools
sage: pickletools.dis(p_uncomp)
    0: \x80 PROTO      2
    2: c    GLOBAL     'sage.structure.sage_object SageObject'
   41: q    BINPUT     ...
   43: )    EMPTY_TUPLE
   44: \x81 NEWOBJ
   45: q    BINPUT     ...
   47: .    STOP
highest protocol among opcodes = 2
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) → 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.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.
parent(self)

File: sage/structure/sage_object.pyx (starting at line 518)

Return the type of self to support the coercion framework.

EXAMPLES:

sage: t = log(sqrt(2) - 1) + log(sqrt(2) + 1); t
log(sqrt(2) + 1) + log(sqrt(2) - 1)
sage: u = t.maxima_methods()
sage: u.parent()
<class 'sage.symbolic.maxima_wrapper.MaximaWrapper'>
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.

rename(self, x=None)

File: sage/structure/sage_object.pyx (starting at line 68)

Change self so it prints as x, where x is a string.

Note

This is only supported for Python classes that derive from SageObject.

EXAMPLES:

sage: x = PolynomialRing(QQ, 'x', sparse=True).gen()
sage: g = x^3 + x - 5
sage: g
x^3 + x - 5
sage: g.rename('a polynomial')
sage: g
a polynomial
sage: g + x
x^3 + 2*x - 5
sage: h = g^100
sage: str(h)[:20]
'x^300 + 100*x^298 - '
sage: h.rename('x^300 + ...')
sage: h
x^300 + ...

Real numbers are not Python classes, so rename is not supported:

sage: a = 3.14
sage: type(a)
<... 'sage.rings.real_mpfr.RealLiteral'>
sage: a.rename('pi')
Traceback (most recent call last):
...
NotImplementedError: object does not support renaming: 3.14000000000000

Note

The reason C-extension types are not supported by default is if they were then every single one would have to carry around an extra attribute, which would be slower and waste a lot of memory.

To support them for a specific class, add a cdef public __custom_name attribute.

reset_name(self)

File: sage/structure/sage_object.pyx (starting at line 125)

Remove the custom name of an object.

EXAMPLES:

sage: P.<x> = QQ[]
sage: P
Univariate Polynomial Ring in x over Rational Field
sage: P.rename('A polynomial ring')
sage: P
A polynomial ring
sage: P.reset_name()
sage: P
Univariate Polynomial Ring in x over Rational Field
save(self, filename=None, compress=True)

File: sage/structure/sage_object.pyx (starting at line 420)

Save self to the given filename.

EXAMPLES:

sage: f = x^3 + 5
sage: f.save(os.path.join(SAGE_TMP, 'file'))
sage: load(os.path.join(SAGE_TMP, 'file.sobj'))
x^3 + 5
exception elementary_vectors.functions.MultipleException

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

with_traceback()

Exception.with_traceback(tb) – set self.__traceback__ to tb and return self.

elementary_vectors.functions.circuits(matrix: sage.matrix.constructor.matrix) → List[sage.modules.free_module_element.vector]

Compute the circuits of a matrix.

OUTPUT: Return a list of circuits of the matrix. 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(matrix: sage.matrix.constructor.matrix) → List[sage.modules.free_module_element.vector]

Compute the cocircuits of a matrix.

OUTPUT: Return a list of cocircuits of the matrix. 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(matrix, dual: bool = True, prevent_multiples: bool = True, generator: bool = False) → Union[List[sage.modules.free_module_element.vector], Iterator[sage.modules.free_module_element.vector]]

Compute elementary vectors of a subspace determined by a matrix.

INPUT:

  • matrix – 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 given matrix. 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(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: 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]