Matrices over Cyclotomic Fields

The underlying matrix for a Matrix_cyclo_dense object is stored as follows: given an n x m matrix over a cyclotomic field of degree d, we store a d x (nm) matrix over QQ, each column of which corresponds to an element of the original matrix. This can be retrieved via the _rational_matrix method. Here is an example illustrating this:

EXAMPLES:

sage: F.<zeta> = CyclotomicField(5)
sage: M = Matrix(F, 2, 3, [zeta, 3, zeta**4+5, (zeta+1)**4, 0, 1])
sage: M
[                        zeta                            3  -zeta^3 - zeta^2 - zeta + 4]
[3*zeta^3 + 5*zeta^2 + 3*zeta                            0                            1]

sage: M._rational_matrix()
[ 0  3  4  0  0  1]
[ 1  0 -1  3  0  0]
[ 0  0 -1  5  0  0]
[ 0  0 -1  3  0  0]

>>> from sage.all import *
>>> F = CyclotomicField(Integer(5), names=('zeta',)); (zeta,) = F._first_ngens(1)
>>> M = Matrix(F, Integer(2), Integer(3), [zeta, Integer(3), zeta**Integer(4)+Integer(5), (zeta+Integer(1))**Integer(4), Integer(0), Integer(1)])
>>> M
[                        zeta                            3  -zeta^3 - zeta^2 - zeta + 4]
[3*zeta^3 + 5*zeta^2 + 3*zeta                            0                            1]

>>> M._rational_matrix()
[ 0  3  4  0  0  1]
[ 1  0 -1  3  0  0]
[ 0  0 -1  5  0  0]
[ 0  0 -1  3  0  0]
AUTHORS:

  • William Stein

  • Craig Citro

class sage.matrix.matrix_cyclo_dense.Matrix_cyclo_dense[source]

Bases: Matrix_dense

Initialize a newly created cyclotomic matrix.

INPUT:

  • parent – a matrix space over a cyclotomic number field

  • entries – see matrix()

  • copy – ignored (for backwards compatibility)

  • coerce – if False, assume without checking that the entries lie in the base ring

EXAMPLES:

This function is called implicitly when you create new cyclotomic dense matrices:

sage: W.<a> = CyclotomicField(100)
sage: A = matrix(2, 3, [1, 1/a, 1-a,a, -2/3*a, a^19])
sage: A
[                        1 -a^39 + a^29 - a^19 + a^9                    -a + 1]
[                        a                    -2/3*a                      a^19]
sage: TestSuite(A).run()

>>> from sage.all import *
>>> W = CyclotomicField(Integer(100), names=('a',)); (a,) = W._first_ngens(1)
>>> A = matrix(Integer(2), Integer(3), [Integer(1), Integer(1)/a, Integer(1)-a,a, -Integer(2)/Integer(3)*a, a**Integer(19)])
>>> A
[                        1 -a^39 + a^29 - a^19 + a^9                    -a + 1]
[                        a                    -2/3*a                      a^19]
>>> TestSuite(A).run()
charpoly(var='x', algorithm='multimodular', proof=None)[source]

Return the characteristic polynomial of self, as a polynomial over the base ring.

INPUT:

  • algorithm – options:

    • 'multimodular' (default): reduce modulo primes, compute charpoly mod p, and lift (very fast)

    • 'pari': use pari (quite slow; comparable to Magma v2.14 though)

    • 'hessenberg': put matrix in Hessenberg form (double dog slow)

  • proof – boolean (default: None); proof flag determined by global linalg proof

OUTPUT: polynomial

EXAMPLES:

sage: K.<z> = CyclotomicField(5)
sage: a = matrix(K, 3, [1,z,1+z^2, z/3,1,2,3,z^2,1-z])
sage: f = a.charpoly(); f
x^3 + (z - 3)*x^2 + (-16/3*z^2 - 2*z)*x - 2/3*z^3 + 16/3*z^2 - 5*z + 5/3
sage: f(a)
[0 0 0]
[0 0 0]
[0 0 0]
sage: a.charpoly(algorithm='pari')
x^3 + (z - 3)*x^2 + (-16/3*z^2 - 2*z)*x - 2/3*z^3 + 16/3*z^2 - 5*z + 5/3
sage: a.charpoly(algorithm='hessenberg')
x^3 + (z - 3)*x^2 + (-16/3*z^2 - 2*z)*x - 2/3*z^3 + 16/3*z^2 - 5*z + 5/3

sage: Matrix(K, 1, [0]).charpoly()
x
sage: Matrix(K, 1, [5]).charpoly(var='y')
y - 5

sage: Matrix(CyclotomicField(13),3).charpoly()
x^3
sage: Matrix(CyclotomicField(13),3).charpoly()[2].parent()
Cyclotomic Field of order 13 and degree 12

>>> from sage.all import *
>>> K = CyclotomicField(Integer(5), names=('z',)); (z,) = K._first_ngens(1)
>>> a = matrix(K, Integer(3), [Integer(1),z,Integer(1)+z**Integer(2), z/Integer(3),Integer(1),Integer(2),Integer(3),z**Integer(2),Integer(1)-z])
>>> f = a.charpoly(); f
x^3 + (z - 3)*x^2 + (-16/3*z^2 - 2*z)*x - 2/3*z^3 + 16/3*z^2 - 5*z + 5/3
>>> f(a)
[0 0 0]
[0 0 0]
[0 0 0]
>>> a.charpoly(algorithm='pari')
x^3 + (z - 3)*x^2 + (-16/3*z^2 - 2*z)*x - 2/3*z^3 + 16/3*z^2 - 5*z + 5/3
>>> a.charpoly(algorithm='hessenberg')
x^3 + (z - 3)*x^2 + (-16/3*z^2 - 2*z)*x - 2/3*z^3 + 16/3*z^2 - 5*z + 5/3

>>> Matrix(K, Integer(1), [Integer(0)]).charpoly()
x
>>> Matrix(K, Integer(1), [Integer(5)]).charpoly(var='y')
y - 5

>>> Matrix(CyclotomicField(Integer(13)),Integer(3)).charpoly()
x^3
>>> Matrix(CyclotomicField(Integer(13)),Integer(3)).charpoly()[Integer(2)].parent()
Cyclotomic Field of order 13 and degree 12
coefficient_bound()[source]

Return an upper bound for the (complex) absolute values of all entries of self with respect to all embeddings.

Use self.height() for a sharper bound.

This is computed using just the Cauchy-Schwarz inequality, i.e., we use the fact that

\left| \sum_i a_i\zeta^i \right| \leq \sum_i |a_i|,

as \(|\zeta| = 1\).

EXAMPLES:

sage: W.<z> = CyclotomicField(5)
sage: A = matrix(W, 2, 2, [1+z, 0, 9*z+7, -3 + 4*z]); A
[  z + 1       0]
[9*z + 7 4*z - 3]
sage: A.coefficient_bound()
16

>>> from sage.all import *
>>> W = CyclotomicField(Integer(5), names=('z',)); (z,) = W._first_ngens(1)
>>> A = matrix(W, Integer(2), Integer(2), [Integer(1)+z, Integer(0), Integer(9)*z+Integer(7), -Integer(3) + Integer(4)*z]); A
[  z + 1       0]
[9*z + 7 4*z - 3]
>>> A.coefficient_bound()
16

The above bound is just \(9 + 7\), coming from the lower left entry. A better bound would be the following:

sage: (A[1,0]).abs()
12.997543663...

>>> from sage.all import *
>>> (A[Integer(1),Integer(0)]).abs()
12.997543663...
denominator()[source]

Return the denominator of the entries of this matrix.

OUTPUT: integer; the smallest integer \(d\) so that d * self has entries in the ring of integers

EXAMPLES:

sage: W.<z> = CyclotomicField(5)
sage: A = matrix(W, 2, 2, [-2/7,2/3*z+z^2,-z,1+z/19]); A
[       -2/7 z^2 + 2/3*z]
[         -z  1/19*z + 1]
sage: d = A.denominator(); d
399

>>> from sage.all import *
>>> W = CyclotomicField(Integer(5), names=('z',)); (z,) = W._first_ngens(1)
>>> A = matrix(W, Integer(2), Integer(2), [-Integer(2)/Integer(7),Integer(2)/Integer(3)*z+z**Integer(2),-z,Integer(1)+z/Integer(19)]); A
[       -2/7 z^2 + 2/3*z]
[         -z  1/19*z + 1]
>>> d = A.denominator(); d
399
echelon_form(algorithm='multimodular', height_guess=None)[source]

Find the echelon form of self, using the specified algorithm.

The result is cached for each algorithm separately.

EXAMPLES:

sage: W.<z> = CyclotomicField(3)
sage: A = matrix(W, 2, 3, [1+z, 2/3, 9*z+7, -3 + 4*z, z, -7*z]); A
[  z + 1     2/3 9*z + 7]
[4*z - 3       z    -7*z]
sage: A.echelon_form()
[                  1                   0  -192/97*z - 361/97]
[                  0                   1 1851/97*z + 1272/97]
sage: A.echelon_form(algorithm='classical')
[                  1                   0  -192/97*z - 361/97]
[                  0                   1 1851/97*z + 1272/97]

>>> from sage.all import *
>>> W = CyclotomicField(Integer(3), names=('z',)); (z,) = W._first_ngens(1)
>>> A = matrix(W, Integer(2), Integer(3), [Integer(1)+z, Integer(2)/Integer(3), Integer(9)*z+Integer(7), -Integer(3) + Integer(4)*z, z, -Integer(7)*z]); A
[  z + 1     2/3 9*z + 7]
[4*z - 3       z    -7*z]
>>> A.echelon_form()
[                  1                   0  -192/97*z - 361/97]
[                  0                   1 1851/97*z + 1272/97]
>>> A.echelon_form(algorithm='classical')
[                  1                   0  -192/97*z - 361/97]
[                  0                   1 1851/97*z + 1272/97]

We verify that the result is cached and that the caches are separate:

sage: A.echelon_form() is A.echelon_form()
True
sage: A.echelon_form() is A.echelon_form(algorithm='classical')
False

>>> from sage.all import *
>>> A.echelon_form() is A.echelon_form()
True
>>> A.echelon_form() is A.echelon_form(algorithm='classical')
False
height()[source]

Return the height of self.

If we let \(a_{ij}\) be the \(i,j\) entry of self, then we define the height of self to be

\(\max_v \max_{i,j} |a_{ij}|_v\),

where \(v\) runs over all complex embeddings of self.base_ring().

EXAMPLES:

sage: W.<z> = CyclotomicField(5)
sage: A = matrix(W, 2, 2, [1+z, 0, 9*z+7, -3 + 4*z]); A
[  z + 1       0]
[9*z + 7 4*z - 3]
sage: A.height()
12.997543663...
sage: (A[1,0]).abs()
12.997543663...

>>> from sage.all import *
>>> W = CyclotomicField(Integer(5), names=('z',)); (z,) = W._first_ngens(1)
>>> A = matrix(W, Integer(2), Integer(2), [Integer(1)+z, Integer(0), Integer(9)*z+Integer(7), -Integer(3) + Integer(4)*z]); A
[  z + 1       0]
[9*z + 7 4*z - 3]
>>> A.height()
12.997543663...
>>> (A[Integer(1),Integer(0)]).abs()
12.997543663...
randomize(density=1, num_bound=2, den_bound=2, distribution=None, nonzero=False, *args, **kwds)[source]

Randomize the entries of self.

Choose rational numbers according to distribution, whose numerators are bounded by num_bound and whose denominators are bounded by den_bound.

EXAMPLES:

sage: A = Matrix(CyclotomicField(5),2,2,range(4)) ; A
[0 1]
[2 3]
sage: A.randomize()
sage: A   # random output
[       1/2*zeta5^2 + zeta5                        1/2]
[        -zeta5^2 + 2*zeta5 -2*zeta5^3 + 2*zeta5^2 + 2]

>>> from sage.all import *
>>> A = Matrix(CyclotomicField(Integer(5)),Integer(2),Integer(2),range(Integer(4))) ; A
[0 1]
[2 3]
>>> A.randomize()
>>> A   # random output
[       1/2*zeta5^2 + zeta5                        1/2]
[        -zeta5^2 + 2*zeta5 -2*zeta5^3 + 2*zeta5^2 + 2]
set_immutable()[source]

Change this matrix so that it is immutable.

EXAMPLES:

sage: W.<z> = CyclotomicField(5)
sage: A = matrix(W, 2, 2, [1,2/3*z+z^2,-z,1+z/2])
sage: A[0,0] = 10
sage: A.set_immutable()
sage: A[0,0] = 20
Traceback (most recent call last):
...
ValueError: matrix is immutable; please change a copy instead (i.e., use copy(M) to change a copy of M).

>>> from sage.all import *
>>> W = CyclotomicField(Integer(5), names=('z',)); (z,) = W._first_ngens(1)
>>> A = matrix(W, Integer(2), Integer(2), [Integer(1),Integer(2)/Integer(3)*z+z**Integer(2),-z,Integer(1)+z/Integer(2)])
>>> A[Integer(0),Integer(0)] = Integer(10)
>>> A.set_immutable()
>>> A[Integer(0),Integer(0)] = Integer(20)
Traceback (most recent call last):
...
ValueError: matrix is immutable; please change a copy instead (i.e., use copy(M) to change a copy of M).

Note that there is no function to set a matrix to be mutable again, since such a function would violate the whole point. Instead make a copy, which is always mutable by default.:

sage: A.set_mutable()
Traceback (most recent call last):
...
AttributeError: 'sage.matrix.matrix_cyclo_dense.Matrix_cyclo_dense' object has no attribute 'set_mutable'...
sage: B = A.__copy__()
sage: B[0,0] = 20
sage: B[0,0]
20

>>> from sage.all import *
>>> A.set_mutable()
Traceback (most recent call last):
...
AttributeError: 'sage.matrix.matrix_cyclo_dense.Matrix_cyclo_dense' object has no attribute 'set_mutable'...
>>> B = A.__copy__()
>>> B[Integer(0),Integer(0)] = Integer(20)
>>> B[Integer(0),Integer(0)]
20
tensor_product(A, subdivide=True)[source]

Return the tensor product of two matrices.

INPUT:

  • A – a matrix

  • subdivide – boolean (default: True); whether or not to return natural subdivisions with the matrix

OUTPUT:

Replace each element of self by a copy of A, but first create a scalar multiple of A by the element it replaces. So if self is an \(m\times n\) matrix and A is a \(p\times q\) matrix, then the tensor product is an \(mp\times nq\) matrix. By default, the matrix will be subdivided into submatrices of size \(p\times q\).

EXAMPLES:

sage: C = CyclotomicField(12)
sage: M = matrix.random(C, 3, 3)
sage: N = matrix.random(C, 50, 50)
sage: M.tensor_product(M) == super(type(M), M).tensor_product(M)
True
sage: N = matrix.random(C, 15, 20)
sage: M.tensor_product(N) == super(type(M), M).tensor_product(N)
True

>>> from sage.all import *
>>> C = CyclotomicField(Integer(12))
>>> M = matrix.random(C, Integer(3), Integer(3))
>>> N = matrix.random(C, Integer(50), Integer(50))
>>> M.tensor_product(M) == super(type(M), M).tensor_product(M)
True
>>> N = matrix.random(C, Integer(15), Integer(20))
>>> M.tensor_product(N) == super(type(M), M).tensor_product(N)
True