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]
AUTHORS:
  • William Stein
  • Craig Citro
class sage.matrix.matrix_cyclo_dense.Matrix_cyclo_dense

Bases: sage.matrix.matrix_dense.Matrix_dense

Initialize a newly created cyclotomic matrix.

INPUT:

  • parent – a matrix space over a cyclotomic field
  • entries – a list of entries or scalar
  • coerce – boolean; if true entries are coerced to base ring
  • copy – boolean; ignored due to underlying data structure

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

TESTS:

sage: matrix(W, 2, 1, a)
Traceback (most recent call last):
...
TypeError: nonzero scalar matrix must be square

We call __init__ explicitly below:

sage: from sage.matrix.matrix_cyclo_dense import Matrix_cyclo_dense
sage: A = Matrix_cyclo_dense.__new__(Matrix_cyclo_dense, MatrixSpace(CyclotomicField(3),2), [0,1,2,3], True, True)
sage: A.__init__(MatrixSpace(CyclotomicField(3),2), [0,1,2,3], True, True)
sage: A
[0 1]
[2 3]
charpoly(var='x', algorithm='multimodular', proof=None)

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

INPUT:

  • algorithm

    • ‘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 – bool (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

TESTS:

sage: Matrix(CyclotomicField(10),0).charpoly()
1
coefficient_bound()

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

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...
denominator()

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
echelon_form(algorithm='multimodular', height_guess=None)

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]

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

TESTS:

sage: W.<z> = CyclotomicField(13)
sage: A = Matrix(W, 2,3, [10^30*(1-z)^13, 1, 2, 3, 4, z])
sage: B = Matrix(W, 2,3, [(1-z)^13, 1, 2, 3, 4, z])
sage: A.echelon_form() == A.echelon_form('classical')  # long time (4s on sage.math, 2011)
True
sage: B.echelon_form() == B.echelon_form('classical')
True

A degenerate case with the degree 1 cyclotomic field:

sage: A = matrix(CyclotomicField(1),2,3,[1,2,3,4,5,6]);
sage: A.echelon_form()
[ 1  0 -1]
[ 0  1  2]

A case that checks the bug in trac ticket #3500:

sage: cf4 = CyclotomicField(4) ; z4 = cf4.0
sage: A = Matrix(cf4, 1, 2, [-z4, 1])
sage: A.echelon_form()
[    1 zeta4]

Verify that the matrix on trac ticket #10281 works:

 sage: K.<rho> = CyclotomicField(106)
sage: coeffs = [(18603/107*rho^51 - 11583/107*rho^50 - 19907/107*rho^49 - 13588/107*rho^48 - 8722/107*rho^47 + 2857/107*rho^46 - 19279/107*rho^45 - 16666/107*rho^44 - 11327/107*rho^43 + 3802/107*rho^42 + 18998/107*rho^41 - 10798/107*rho^40 + 16210/107*rho^39 - 13768/107*rho^38 + 15063/107*rho^37 - 14433/107*rho^36 - 19434/107*rho^35 - 12606/107*rho^34 + 3786/107*rho^33 - 17996/107*rho^32 + 12341/107*rho^31 - 15656/107*rho^30 - 19092/107*rho^29 + 8382/107*rho^28 - 18147/107*rho^27 + 14024/107*rho^26 + 18751/107*rho^25 - 8301/107*rho^24 - 20112/107*rho^23 - 14483/107*rho^22 + 4715/107*rho^21 + 20065/107*rho^20 + 15293/107*rho^19 + 10072/107*rho^18 + 4775/107*rho^17 - 953/107*rho^16 - 19782/107*rho^15 - 16020/107*rho^14 + 5633/107*rho^13 - 17618/107*rho^12 - 18187/107*rho^11 + 7492/107*rho^10 + 19165/107*rho^9 - 9988/107*rho^8 - 20042/107*rho^7 + 10109/107*rho^6 - 17677/107*rho^5 - 17723/107*rho^4 - 12489/107*rho^3 - 6321/107*rho^2 - 4082/107*rho - 1378/107, 1, 4*rho + 1), (0, 1, rho + 4)]
 sage: m = matrix(2, coeffs)
 sage: a = m.echelon_form(algorithm='classical')
 sage: b = m.echelon_form(algorithm='multimodular')  # long time (5s on sage.math, 2012)
 sage: a == b  # long time (depends on previous)
 True
height()

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...
randomize(density=1, num_bound=2, den_bound=2, distribution=None, nonzero=False, *args, **kwds)

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

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

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
tensor_product(A, subdivide=True)

Return the tensor product of two matrices.

INPUT:

  • A – a matrix
  • subdivide – (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

TESTS:

sage: Mp = matrix.random(C, 2,3)
sage: Np = matrix.random(C, 4,5)
sage: subdiv = super(type(Mp),Mp).tensor_product(Np).subdivisions()
sage: Mp.tensor_product(Np).subdivisions() == subdiv
True