Source code for flatsurf.geometry.finitely_generated_matrix_group

r"""
Class for matrix groups generated by a finite number of elements.

EXAMPLES::

    sage: from flatsurf.geometry.finitely_generated_matrix_group import  FinitelyGenerated2x2MatrixGroup

    sage: m1 = matrix([[1,1],[0,1]])
    sage: m2 = matrix([[1,0],[1,1]])
    sage: G = FinitelyGenerated2x2MatrixGroup([m1,m2])
    sage: G
    Matrix group generated by:
    [1 1]  [1 0]
    [0 1], [1 1]
    sage: it = iter(G)
    sage: [next(it) for _ in range(5)]
    [
    [1 0]  [1 1]  [1 2]  [2 1]  [ 0  1]
    [0 1], [0 1], [0 1], [1 1], [-1  1]
    ]

    sage: G = FinitelyGenerated2x2MatrixGroup([identity_matrix(2)])
"""
# ****************************************************************************
#  This file is part of sage-flatsurf.
#
#       Copyright (C) 2013-2019 Vincent Delecroix
#                     2013-2019 W. Patrick Hooper
#                          2023 Julian Rüth <julian.rueth@fsfe.org>
#
#  sage-flatsurf is free software: you can redistribute it and/or modify
#  it under the terms of the GNU General Public License as published by
#  the Free Software Foundation, either version 2 of the License, or
#  (at your option) any later version.
#
#  sage-flatsurf is distributed in the hope that it will be useful,
#  but WITHOUT ANY WARRANTY; without even the implied warranty of
#  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#  GNU General Public License for more details.
#
#  You should have received a copy of the GNU General Public License
#  along with sage-flatsurf. If not, see <https://www.gnu.org/licenses/>.
# ****************************************************************************

from sage.rings.integer import Integer
from sage.structure.parent import Parent
from sage.groups.group import Group
from sage.structure.sequence import Sequence
from sage.rings.infinity import Infinity
from sage.matrix.constructor import matrix


[docs] def invariant_quadratic_forms(m): r""" Return the space of quadratic forms invariant under m. If the matrix is orientable, there is only one (what about strange eigenvalues?) If the det(m) == -1 and trace(m) == 0, there are 2. EXAMPLES:: sage: from flatsurf.geometry.finitely_generated_matrix_group import invariant_quadratic_forms sage: invariant_quadratic_forms(matrix(2, [0,1,-1,0])) Free module of degree 3 and rank 1 over Integer Ring Echelon basis matrix: [1 1 0] sage: invariant_quadratic_forms(matrix(2, [1,1,0,1])) Free module of degree 3 and rank 1 over Integer Ring Echelon basis matrix: [0 1 0] sage: invariant_quadratic_forms(matrix(2, [2,1,1,1])) Free module of degree 3 and rank 1 over Integer Ring Echelon basis matrix: [ 2 -2 -1] sage: r = matrix(2,[1,-1,1,0]) sage: q = invariant_quadratic_forms(r) sage: q Free module of degree 3 and rank 1 over Integer Ring Echelon basis matrix: [ 2 2 -1] sage: a,c,b = q.gen() sage: m = matrix(2, [a,b,b,c]) sage: r.transpose() * m * r == m True sage: invariant_quadratic_forms(matrix(2, [-1,0,0,1])) Free module of degree 3 and rank 2 over Integer Ring Echelon basis matrix: [1 0 0] [0 1 0] sage: invariant_quadratic_forms(-identity_matrix(2)) Traceback (most recent call last): ... ValueError: m must be non scalar sage: for _ in range(100): ....: r = random_matrix(ZZ, 2, algorithm='unimodular') ....: if r.is_scalar(): continue ....: q = invariant_quadratic_forms(r) ....: a,c,b = q.random_element() ....: m = matrix(2, [a,b,b,c]) ....: assert r.transpose() * m * r == m ....: m[0,0] = -m[0,0] ....: m[0,1] = -m[0,1] ....: q = invariant_quadratic_forms(r) ....: a,c,b = q.random_element() ....: m = matrix(2, [a,b,b,c]) ....: assert r.transpose() * m * r == m """ if m.is_scalar(): raise ValueError("m must be non scalar") s = m.det() if not s.is_unit(): raise ValueError("determinant must be +1 or -1") a, b, c, d = m.list() V = matrix( m.base_ring(), 4, 3, [ a - s * d, 0, (1 + s) * c, s * b, c, (1 - s) * a, b, s * c, (1 - s) * d, 0, d - s * a, (1 + s) * b, ], ).right_kernel() return V
[docs] def contains_definite_form(V): r""" Check whether a given a subspace of the 3 dimensional space (a,b,c) contains a definitive positive quadratic form ax^2 + 2bxy + by^2. TESTS:: sage: from flatsurf.geometry.finitely_generated_matrix_group import contains_definite_form sage: V = ZZ**3 sage: contains_definite_form(V.submodule([(1,1,0)])) True sage: contains_definite_form(V.submodule([(2,1,1)])) True sage: contains_definite_form(V.submodule([(1,1,1)])) False sage: contains_definite_form(V.submodule([(1,0,0),(0,1,0)])) True sage: contains_definite_form(V.submodule([(1,0,0),(0,0,1)])) False sage: contains_definite_form(V.submodule([(-1,0,0),(0,1,3)])) True """ dim = V.dimension() if dim == 0: return False elif dim == 1: a, c, b = V.gen(0) return b**2 < a * c elif dim == 2: a1, c1, b1 = V.gen(0) a2, c2, b2 = V.gen(1) if b1**2 < a1 * c1 or b2**2 < a2 * c2: return True return (2 * b1 * b2 - a2 * c1 - a1 * c2) ** 2 - 4 * (b1**2 - a1 * c1) * ( b2**2 - a2 * c2 ) > 0 elif dim == 3: return True else: raise RuntimeError
[docs] def matrix_multiplicative_order(m): r""" Return the order of the 2x2 matrix ``m``. """ if m.is_one(): return Integer(1) elif m.det() != 1 and m.det() != -1: return Infinity # now we compute the potentially preserved quadratic form # i.e. looking for A such that m^t A m = A m00 = m[0, 0] m01 = m[0, 1] m10 = m[1, 0] m11 = m[1, 1] M = matrix( m.base_ring(), [ [m00**2, m00 * m10, m10**2], [m00 * m01, m00 * m11, m10 * m11], [m01**2, m01 * m11, m11**2], ], ) # might there be several solutions ? (other than scaling)... should not try: from sage.all import identity_matrix v = (M - identity_matrix(3)).solve_right() except ValueError: # no solution return False raise NotImplementedError( "your matrix is conjugate to an orthogonal matrix but the angle might not be rational.. to be terminated." )
# then we conjugate and check if the angles are rational # we need to take a square root of a symmetric matrix... this is not implemented! # A = matrix(m.base_ring(), [[v[0], v[1]], [v[1], v[2]]])
[docs] class FinitelyGenerated2x2MatrixGroup(Group): r""" Finitely generated group of 2x2 matrices with real coefficients .. SEEALSO:: :py:mod:`sage.groups.group` for the general interface of groups like this in SageMath """ def __init__(self, matrices, matrix_space=None, category=None): if matrix_space is None: from sage.matrix.matrix_space import MatrixSpace ring = Sequence(matrices).universe().base_ring() matrix_space = MatrixSpace(ring, 2) self._generators = list(map(matrix_space, matrices)) for m in self._generators: m.set_immutable() self._matrix_space = matrix_space if category is None: from sage.categories.groups import Groups category = Groups() Parent.__init__(self, category=category, facade=matrix_space)
[docs] def is_abelian(self): r""" Check whether this group is abelian. .. TODO:: move this method inside Sage EXAMPLES:: sage: from flatsurf.geometry.finitely_generated_matrix_group import FinitelyGenerated2x2MatrixGroup sage: m1 = matrix([[1,1],[0,1]]) sage: m2 = matrix([[1,0],[1,1]]) sage: G = FinitelyGenerated2x2MatrixGroup([m1,m2]) sage: G.is_abelian() False sage: G = FinitelyGenerated2x2MatrixGroup([m1]) sage: G.is_abelian() True """ for a in self._generators: for b in self._generators: if a * b != b * a: return False return True
def _repr_(self): mat_string = [g.str().split("\n") for g in self._generators] return ( "Matrix group generated by:\n" + " ".join(x[0] for x in mat_string) + "\n" + ", ".join(x[1] for x in mat_string) )
[docs] def is_finite(self): r""" Check whether the group is finite. A group is finite if and only if it is conjugate to a (finite) subgroup of O(2). This is actually also true in higher dimensions. EXAMPLES:: sage: from flatsurf.geometry.finitely_generated_matrix_group import FinitelyGenerated2x2MatrixGroup sage: G = FinitelyGenerated2x2MatrixGroup([identity_matrix(2)]) sage: G.is_finite() True sage: t = matrix(2, [2,1,1,1]) sage: m1 = matrix([[0,1],[-1,0]]) sage: m2 = matrix([[1,-1],[1,0]]) sage: FinitelyGenerated2x2MatrixGroup([m1]).is_finite() True sage: FinitelyGenerated2x2MatrixGroup([t*m1*~t]).is_finite() True sage: FinitelyGenerated2x2MatrixGroup([m2]).is_finite() True sage: FinitelyGenerated2x2MatrixGroup([m1,m2]).is_finite() False sage: FinitelyGenerated2x2MatrixGroup([t*m1*~t,t*m2*~t]).is_finite() False sage: from flatsurf.geometry.polygon import number_field_elements_from_algebraics sage: c5 = QQbar.zeta(5).real() sage: s5 = QQbar.zeta(5).imag() sage: K, (c5,s5) = number_field_elements_from_algebraics([c5,s5]) sage: r = matrix(K, 2, [c5,-s5,s5,c5]) sage: FinitelyGenerated2x2MatrixGroup([m1,r]).is_finite() True sage: FinitelyGenerated2x2MatrixGroup([t*m1*~t,t*r*~t]).is_finite() True sage: FinitelyGenerated2x2MatrixGroup([m2,r]).is_finite() False sage: FinitelyGenerated2x2MatrixGroup([t*m2*~t, t*r*~t]).is_finite() False """ # determinant and trace tests # (the code actually check that each generator is of finite order) for m in self._generators: if ( (m.det() != 1 and m.det() != -1) or m.trace().abs() > 2 or (m.trace().abs() == 2 and (m[0, 1] or m[1, 0])) ): return False gens = [g for g in self._generators if not g.is_scalar()] if len(gens) <= 1: return True # now we try to find a non-trivial invariant quadratic form from sage.modules.free_module import FreeModule V = FreeModule(self._matrix_space.base_ring(), 3) for g in gens: V = V.intersection(invariant_quadratic_forms(g)) if not contains_definite_form(V): return False return True
[docs] def cardinality(self): if self.is_finite(): # THIS IS STUPID!!! return len(list(self)) else: return Infinity
def __iter__(self): yield self.one() s = {self.one()} wait = self._generators[:] while wait: p = wait.pop(0) if p not in s: yield p s.add(p) for g in self._generators: for m in [p * g, p * g.inverse(), g * p, g.inverse() * p]: m.set_immutable() if m not in s: yield m s.add(m) wait.append(m) def __eq__(self, other): return ( isinstance(other, FinitelyGenerated2x2MatrixGroup) and self._generators == other._generators )
[docs] def some_elements(self): from itertools import islice return list(islice(self, 5))
def __ne__(self, other): return not self == other def __reduce__(self): return FinitelyGenerated2x2MatrixGroup, (self._generators, self._matrix_space)
[docs] def one(self): return self._matrix_space.identity_matrix()
def _an_element_(self): r""" Return a typical element of this group, namely a generator. EXAMPLES: sage: from flatsurf.geometry.finitely_generated_matrix_group import FinitelyGenerated2x2MatrixGroup sage: G = FinitelyGenerated2x2MatrixGroup([identity_matrix(2)]) sage: G._an_element_() [1 0] [0 1] sage: G.an_element() [1 0] [0 1] .. SEEALSO:: :meth:`sage.structure.parent.Parent.an_element` which relies on this method and should be called instead """ return self._generators[0]
[docs] def gen(self, i): return self._generators[i]