Matrices

Matrix functions

EXAMPLES:

...

TODO:

  • Discrete geometry code should use projection_matrix from here

slabbe.matrices.Minkowski_embedding_without_sqrt2(self, B=None, prec=None)

This method is a modification of the Minkowski_embedding method of NumberField in sage (without sqrt2).

INPUT:

  • self – number field

  • B – vector (default:None), the basis. If None, the default basis is \(\{1,\alpha, ..., \alpha^{n-1}\}\).

  • prec – integer (default:None), the precision. The computations will use RealField(prec) or RDF if prec is None or the field of algebraic numbers QQbar (or it subfield AA of algebraic reals) if prec is infinity.

OUTPUT:

a matrix

See also

function Minkowski_projection_triple() which returns the rows of the same matrix split into three according to the expanding, contracting and neutral eigenspaces.

EXAMPLES:

sage: from slabbe.matrices import Minkowski_embedding_without_sqrt2
sage: F.<alpha> = NumberField(x^3+2)
sage: F.minkowski_embedding()
[ 1.00000000000000 -1.25992104989487  1.58740105196820]
[ 1.41421356237309 0.890898718140339 -1.12246204830937]
[0.000000000000000  1.54308184421705  1.94416129723967]
sage: Minkowski_embedding_without_sqrt2(F)
[  1.00000000000000  -1.25992104989487   1.58740105196820]
[  1.00000000000000  0.629960524947437 -0.793700525984099]
[ 0.000000000000000   1.09112363597172   1.37472963699860]
sage: Minkowski_embedding_without_sqrt2(F, [1, alpha+2, alpha^2-alpha])
[ 1.00000000000000 0.740078950105127  2.84732210186307]
[ 1.00000000000000  2.62996052494744 -1.42366105093154]
[0.000000000000000  1.09112363597172 0.283606001026881]
sage: Minkowski_embedding_without_sqrt2(F) * (alpha + 2).vector().column()
[0.740078950105127]
[ 2.62996052494744]
[ 1.09112363597172]

The input vector may have arbitrary length:

sage: Minkowski_embedding_without_sqrt2(F, [1, alpha, alpha^2, 1-alpha])
[  1.00000000000000  -1.25992104989487   1.58740105196820  2.25992104989487]
[  1.00000000000000  0.629960524947437 -0.793700525984099 0.370039475052563]
[ 0.000000000000000   1.09112363597172   1.37472963699860 -1.09112363597172]

Tribo:

sage: F.<beta> = NumberField(x^3-x^2-x-1)
sage: F.minkowski_embedding()
[  1.00000000000000   1.83928675521416   3.38297576790624]
[  1.41421356237309 -0.593465355971987 -0.270804762516626]
[ 0.000000000000000  0.857424571985895 -0.719625086862932]
sage: Minkowski_embedding_without_sqrt2(F)
[  1.00000000000000   1.83928675521416   3.38297576790624]
[  1.00000000000000 -0.419643377607080 -0.191487883953119]
[ 0.000000000000000  0.606290729207199 -0.508851778832738]

Comprendre le problème de norme:

sage: norme = lambda v:abs(v[0]) * (v[1]^2 + v[2]^2)
sage: F.<beta> = NumberField(x^3-x^2-x-1)
sage: M = Minkowski_embedding_without_sqrt2(F)
sage: norme(M*vector((1,0,0)))
1.00000000000000
sage: norme(M*vector((1,0,-1)))
4.00000000000000
slabbe.matrices.Minkowski_projection_triple(self, B=None, prec=None)

Return the projections to the expanding, contracting and neutral spaces.

It describes the images of the vectors in B as matrix columns.

INPUT:

  • self – number field

  • B – vector (default:None), the basis. If None, the default basis is \(\{1,\alpha, ..., \alpha^{n-1}\}\).

  • prec – integer (default:None), the precision. The computations will use RealField(prec) or RDF if prec is None or the field of algebraic numbers QQbar (or it subfield AA of algebraic reals) if prec is infinity.

OUTPUT:

  • tuple (P, Q, R) of matrices giving the projection to the expanding, contracting and neutral eigenspaces respectively.

EXAMPLES:

sage: from slabbe.matrices import Minkowski_projection_triple
sage: F.<alpha> = NumberField(x^3+2)
sage: Minkowski_projection_triple(F)
(
[  1.00000000000000  -1.25992104989487   1.58740105196820]
[  1.00000000000000  0.629960524947437 -0.793700525984099]
[ 0.000000000000000   1.09112363597172   1.37472963699860], [], []
)
sage: Minkowski_projection_triple(F, [1, alpha+2, alpha^2-alpha])
(
[ 1.00000000000000 0.740078950105127  2.84732210186307]
[ 1.00000000000000  2.62996052494744 -1.42366105093154]
[0.000000000000000  1.09112363597172 0.283606001026881], [], []
)

The input vector may have arbitrary length:

sage: Minkowski_projection_triple(F, [1, alpha, alpha^2, 1-alpha])
(
[  1.00000000000000  -1.25992104989487   1.58740105196820   2.25992104989487]
[  1.00000000000000  0.629960524947437 -0.793700525984099  0.370039475052563]
[ 0.000000000000000   1.09112363597172   1.37472963699860  -1.09112363597172],
[],
[]
)

Tribo:

sage: F.<beta> = NumberField(x^3-x^2-x-1)
sage: Minkowski_projection_triple(F)
(
[1.000000000000000000000000000000 1.839286755214161132551852564671
3.382975767906237494122708536521],
[  1.00000000000000 -0.419643377607080 -0.191487883953119]
[ 0.000000000000000  0.606290729207199 -0.508851778832738], []
)

Tribo, projection in the field of algebraic numbers with prec=oo:

sage: Minkowski_projection_triple(F, prec=oo)
(
[                 1 1.839286755214161? 3.382975767906238?],
<BLANKLINE>
[                   1 -0.4196433776070806? -0.1914878839531188?]
[                   0  0.6062907292071993? -0.5088517788327380?],
<BLANKLINE>
[]
)
sage: F.<alpha> = NumberField(x^3-x-1)
sage: Minkowski_projection_triple(F)
(
[1.000000000000000000000000000000 1.324717957244746025960912521898 1.754877666246692760049518612953],
[  1.00000000000000 -0.662358978622373  0.122561166876654]
[ 0.000000000000000  0.562279512062301 -0.744861766619744], []
)

With neutral eigenvalues. Notice that if the precision is too low, some roots on the unit circle are wrongly considered strictly inside, thus contracting. One must increase the precision in this case:

sage: F.<alpha> = NumberField(x^2-x+1)
sage: Minkowski_projection_triple(F)     # gives wrong result due to low precision
(
    [ 1.00000000000000 0.500000000000000]
[], [0.000000000000000 0.866025403784439], []
)
sage: Minkowski_projection_triple(F, prec=60)
(
        [ 1.0000000000000000 0.50000000000000000]
[], [], [0.00000000000000000 0.86602540378443865]
)
sage: Minkowski_projection_triple(F, prec=oo)
(
        [                   1 0.50000000000000000?]
[], [], [                   0   0.866025403784439?]
)
slabbe.matrices.column_norm_ratio(M, p=1)

Return the maximum of the ratio of the norm of two columns.

INPUT:

  • p - default: 2 - p can be a real number greater than 1, infinity (oo or Infinity), or a symbolic expression.

    • \(p=1\): the taxicab (Manhattan) norm

    • \(p=2\): the usual Euclidean norm (the default)

    • \(p=\infty\): the maximum entry (in absolute value)

EXAMPLES:

sage: from slabbe.matrices import column_norm_ratio
sage: M = matrix(3, range(9))
sage: column_norm_ratio(M)
5/3
slabbe.matrices.conjugate_matrix_Z(M)

Return the conjugate matrix Z as defined in [1].

EXAMPLES:

sage: from slabbe.matrices import conjugate_matrix_Z
sage: M = matrix(2, [11,29,14,-1])
sage: conjugate_matrix_Z(M)       # abs tol 1e-8
[11.674409930010482  27.69820597163912]
[14.349386111618157  -1.67440993001048]
sage: conjugate_matrix_Z(M)^2     # abs tol 1e-8
[533.7440993001048 276.9820597163913]
[143.4938611161816 400.2559006998952]
sage: M = matrix(2, [-11,14,-26,29])
sage: conjugate_matrix_Z(M)     # abs tol 1e-8
[ 7.200000000000004  4.199999999999998]
[ 7.799999999999995 10.800000000000002]
sage: conjugate_matrix_Z(M) * 5     # abs tol 1e-8
[ 36.00000000000002 20.999999999999993]
[ 38.99999999999998 54.000000000000014]
sage: M = matrix(2, [-11,26,-14,29]) / 15
sage: conjugate_matrix_Z(M)     # abs tol 1e-8
[ 0.5999999999999999  0.3999999999999999]
[0.39999999999999986  0.5999999999999999]

REFERENCES:

[1] Labbé, Jean-Philippe, et Sébastien Labbé. « A Perron theorem for matrices with negative entries and applications to Coxeter groups ». arXiv:1511.04975 [math], 16 novembre 2015. http://arxiv.org/abs/1511.04975.

slabbe.matrices.is_nonnegative(M)

EXAMPLES:

sage: from slabbe.matrices import is_nonnegative
sage: m = matrix(4, range(-8,8))
sage: is_nonnegative(m)
False
sage: m = matrix(4, range(16))
sage: is_nonnegative(m)
True
slabbe.matrices.is_pisot(M)

EXAMPLES:

sage: from slabbe.matrices import is_pisot
sage: M = matrix(2,[1,1,0,1])
sage: is_pisot(M)
False
sage: M = matrix(2,[0,1,1,1])
sage: is_pisot(M)
True
slabbe.matrices.is_positive(M)

EXAMPLES:

sage: from slabbe.matrices import is_positive
sage: m = matrix(4, range(16))
sage: is_positive(m)
False
sage: m = matrix(4, range(1,17))
sage: is_positive(m)
True
slabbe.matrices.is_primitive(M)

EXAMPLES:

sage: from slabbe.matrices import is_primitive
sage: m = matrix(2, [0,1,1,1])
sage: is_primitive(m)
True
sage: m = matrix(2, [1,1,0,1])
sage: is_primitive(m)
False
slabbe.matrices.map_coefficients_to_variable_index(M, x)

INPUT:

  • M – matrix

  • x – string, variable

EXAMPLES:

sage: from slabbe.matrices import map_coefficients_to_variable_index
sage: M = matrix(2, range(4))
sage: map_coefficients_to_variable_index(M, 's')
[s_0 s_1]
[s_2 s_3]
sage: latex(_)
\left(\begin{array}{rr}
s_{0} & s_{1} \\
s_{2} & s_{3}
\end{array}\right)
slabbe.matrices.perron_left_eigenvector_in_number_field(M, name='root')

Return the Perron left eigenvector of a primitive matrix

INPUT:

  • M – primitive matrix

  • name - a string (default:'root'), the name of the generator of the Number field associated to the characteristic polynomial with embedding equal to the Perron dominant eigenvalue

OUTPUT:

  • Perron eigenvalue

  • Perron left-eigenvector

EXAMPLES:

sage: from slabbe.matrices import perron_left_eigenvector_in_number_field
sage: m = matrix(2,[1,1,1,0])
sage: perron_left_eigenvector_in_number_field(m)
(root, (1, root - 1))
sage: m = matrix(2,[11,14,26,29])
sage: perron_left_eigenvector_in_number_field(m)
(-2*root + 21, (1, -1/13*root + 5/13))

Using a different name for the generator:

sage: perron_left_eigenvector_in_number_field(m, 'rho')
(-2*rho + 21, (1, -1/13*rho + 5/13))
slabbe.matrices.perron_right_eigenvector(M)

EXAMPLES:

sage: from slabbe.matrices import perron_right_eigenvector
sage: m = matrix(2,[-11,14,-26,29])
sage: perron_right_eigenvector(m)    # abs tol 0.0000001
(15.0, (0.35, 0.65))
slabbe.matrices.perron_right_eigenvector_in_number_field(M, name='root')

Return the Perron right eigenvector of a primitive matrix

INPUT:

  • M – primitive matrix

  • name - a string (default:'root'), the name of the generator of the Number field associated to the characteristic polynomial with embedding equal to the Perron dominant eigenvalue

OUTPUT:

  • Perron eigenvalue

  • Perron right-eigenvector

EXAMPLES:

sage: from slabbe.matrices import perron_right_eigenvector_in_number_field
sage: m = matrix(2,[1,1,1,0])
sage: perron_right_eigenvector_in_number_field(m)
(root, (1, root - 1))
sage: m = matrix(2,[11,14,26,29])
sage: perron_right_eigenvector_in_number_field(m)
(-2*root + 21, (1, -1/7*root + 5/7))

Using a different name for the root:

sage: perron_right_eigenvector_in_number_field(m, 'rho')
(-2*rho + 21, (1, -1/7*rho + 5/7))

Works if the characteristic polynomial is reducible:

sage: M = matrix(3, [0, 1, 1, 1, 0, 1, 1, 0, 0])
sage: M.charpoly().factor()
(x + 1) * (x^2 - x - 1)
sage: perron_right_eigenvector_in_number_field(M)
(root, (1, 1, root - 1))

With negative entries, why not:

sage: m = matrix(2,[-11,14,-26,29])
sage: perron_right_eigenvector_in_number_field(m)
(15, (1, 13/7))
slabbe.matrices.projection_matrix(dim_from=3, dim_to=2)

Return a projection matrix from R^d to R^l.

INPUT:

  • dim_from` -- integer (default: ``3)

  • dim_to` -- integer (default: ``2)

OUTPUT:

matrix

EXAMPLES:

sage: from slabbe.matrices import projection_matrix
sage: projection_matrix(3,2)
[-0.866025403784439  0.866025403784439  0.000000000000000]
[-0.500000000000000 -0.500000000000000   1.00000000000000]
sage: projection_matrix(2,3)
[-0.577350269189626 -0.333333333333333]
[ 0.577350269189626 -0.333333333333333]
[ 0.000000000000000  0.666666666666667]
slabbe.matrices.rauzy_projection(M, beta=None, prec=53)

Returns a projection matrix of the canonical basis using the Minkowski embedding associated to the left eigenvector of the given eigenvalue.

INPUT:

  • beta - a real element of QQbar of degree >= 2 (default: None). The eigenvalue used for the projection. It must be an eigenvalue of M. The one used by default is the maximal eigenvalue of M (usually a Pisot number), but matrices of order larger than 3 letters other interesting choices are sometimes possible.

  • prec - integer (default: 53), the number of bits used in the floating point representations of the coordinates.

OUTPUT:

matrix

EXAMPLES:

Fibonacci:

sage: from slabbe.matrices import rauzy_projection
sage: m = matrix(2,(1,1,1,0))
sage: m
[1 1]
[1 0]
sage: rauzy_projection(m)
[ 1.000000000000000000000000000000 -1.618033988749894848204586834366]
[ 1.000000000000000000000000000000 0.6180339887498948482045868343656]

Tribonacci:

sage: m = matrix(3, [1,1,1, 1,0,0, 0,1,0])
sage: rauzy_projection(m)
[  1.00000000000000  0.839286755214161  0.543689012692076]
[  1.00000000000000  -1.41964337760708 -0.771844506346038]
[ 0.000000000000000  0.606290729207199  -1.11514250803994]
sage: matrix(2,(0,1,0, 0,0,-1))*rauzy_projection(m)
[  1.00000000000000  -1.41964337760708 -0.771844506346038]
[ 0.000000000000000 -0.606290729207199   1.11514250803994]

which corresponds to the Rauzy fractal projection coded by Timo:

sage: s = WordMorphism('1->12,2->13,3->1')
sage: s.rauzy_fractal_projection()
{'1': (1.00000000000000, 0.000000000000000),
 '2': (-1.41964337760708, -0.606290729207199),
 '3': (-0.771844506346038, 1.11514250803994)}

TESTS:

sage: t = WordMorphism('1->12,2->3,3->45,4->5,5->6,6->7,7->8,8->1')
sage: m = matrix(t)
sage: rauzy_projection(m).T
[  1.00000000000000   1.00000000000000  0.000000000000000]
[ 0.324717957244746  -1.66235897862237  0.562279512062301]
[ 0.430159709001947  0.784920145499027  -1.30714127868205]
[ 0.245122333753307   1.87743883312335  0.744861766619744]
[ 0.324717957244746  -1.66235897862237  0.562279512062301]
[ 0.430159709001947  0.784920145499027  -1.30714127868205]
[ 0.569840290998053  0.215079854500973   1.30714127868205]
[ 0.754877666246693 -0.877438833123346 -0.744861766619744]
sage: t.rauzy_fractal_projection()
{'1': (1.00000000000000, 0.000000000000000),
 '2': (-1.66235897862237, -0.562279512062301),
 '3': (0.784920145499027, 1.30714127868205),
 '4': (1.87743883312335, -0.744861766619744),
 '5': (-1.66235897862237, -0.562279512062301),
 '6': (0.784920145499027, 1.30714127868205),
 '7': (0.215079854500973, -1.30714127868205),
 '8': (-0.877438833123346, 0.744861766619744)}
sage: E = t.incidence_matrix().eigenvalues()
sage: x = [x for x in E if -0.8 < x < -0.7][0]
sage: x
-0.7548776662466928?
sage: rauzy_projection(m, beta=x).T
[  1.00000000000000   1.00000000000000  0.000000000000000]
[ -1.75487766624669 -0.122561166876654  0.744861766619744]
[  1.32471795724475 -0.662358978622373  0.562279512062301]
[ -4.07959562349144 -0.460202188254281  0.182582254557443]
[  3.07959562349144 -0.539797811745719 -0.182582254557443]
[ -2.32471795724475 -0.337641021377627 -0.562279512062301]
[  1.75487766624669  0.122561166876654 -0.744861766619744]
[ -1.32471795724475  0.662358978622373 -0.562279512062301]
sage: t.rauzy_fractal_projection(eig=x)
{'1': (1.00000000000000, 0.000000000000000),
 '2': (-0.122561166876654, -0.744861766619744),
 '3': (-0.662358978622373, -0.562279512062301),
 '4': (-0.460202188254281, -0.182582254557443),
 '5': (-0.539797811745719, 0.182582254557443),
 '6': (-0.337641021377627, 0.562279512062301),
 '7': (0.122561166876654, 0.744861766619744),
 '8': (0.662358978622373, 0.562279512062301)}

AUTHORS:

  • Timo Jolivet (2012-06-16) – for substitutions in Sage

  • Sébastien Labbé (2018-03-08) – for matrices, using Minkowski embedding

slabbe.matrices.recurrence_matrix(coeffs)

Return the recurrence matrix of a relation, for example:

INPUT:

  • coeffs – list of integers, for example if R(n) = R(n-1) + 2 R(n-2) + 3R(n-3) + 4R(n-4) + 5R(n-5) then coeff must be [1,2,3,4,5]

EXAMPLES:

sage: from slabbe.matrices import recurrence_matrix
sage: recurrence_matrix([1,2,3,4,5])
[1 2 3 4 5]
[1 0 0 0 0]
[0 1 0 0 0]
[0 0 1 0 0]
[0 0 0 1 0]
slabbe.matrices.spectrum(M)

EXAMPLES:

sage: from slabbe.matrices import spectrum, recurrence_matrix
sage: M = recurrence_matrix([1,2,3,4,5])
sage: spectrum(M)
2.576021761956651?