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 fieldB
– vector (default:None
), the basis. IfNone
, the default basis is \(\{1,\alpha, ..., \alpha^{n-1}\}\).prec
– integer (default:None
), the precision. The computations will useRealField(prec)
orRDF
ifprec
isNone
or the field of algebraic numbersQQbar
(or it subfieldAA
of algebraic reals) ifprec
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 fieldB
– vector (default:None
), the basis. IfNone
, the default basis is \(\{1,\alpha, ..., \alpha^{n-1}\}\).prec
– integer (default:None
), the precision. The computations will useRealField(prec)
orRDF
ifprec
isNone
or the field of algebraic numbersQQbar
(or it subfieldAA
of algebraic reals) ifprec
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
orInfinity
), 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
– matrixx
– 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 matrixname
- 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 matrixname
- 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 ofQQbar
of degree >= 2 (default:None
). The eigenvalue used for the projection. It must be an eigenvalue ofM
. The one used by default is the maximal eigenvalue ofM
(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?