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 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]