Commits

Volker Braun  committed 3c2d0c7

split new matrix groups patch into pieces

  • Participants
  • Parent commits 828d928

Comments (0)

Files changed (6)

 trac_14188_vb.patch
 trac_14188_docfix.patch
+trac_14175_plot_options.patch
 trac_13249_vb.patch
 trac_13249_volume.patch
 trac_12553_ppl_count_points.patch
 trac_13826_star_imports_race.patch
 trac_14187_lazy_import_test.patch
 trac_14187_lazy_everywhere.patch
+trac_14014_libgap_cyclotomic_matrix.patch
+trac_14014_deletions.patch
 trac_14014_parents_for_matrix_groups.patch
+trac_14014_parents_group_dependents.patch
 trac_14015_affine_group.patch
 trac_12892_orbit_closure_morphism.patch
 trac_12892_toric_morphism_fibers.patch

File trac_14014_deletions.patch

+# HG changeset patch
+# Parent f683248fbbb54bbcb9a3262e13d282edc41f0dde
+
+Deletions for files that are renamed
+
+diff --git a/sage/groups/matrix_gps/general_linear.py b/sage/groups/matrix_gps/general_linear.py
+deleted file mode 100644
+--- a/sage/groups/matrix_gps/general_linear.py
++++ /dev/null
+@@ -1,239 +0,0 @@
+-r"""
+-General Linear Groups
+-
+-EXAMPLES::
+-
+-    sage: GL(4,QQ)
+-    General Linear Group of degree 4 over Rational Field
+-    sage: GL(1,ZZ)
+-    General Linear Group of degree 1 over Integer Ring
+-    sage: GL(100,RR)
+-    General Linear Group of degree 100 over Real Field with 53 bits of precision
+-    sage: GL(3,GF(49,'a'))
+-    General Linear Group of degree 3 over Finite Field in a of size 7^2
+-
+-AUTHORS:
+-
+-- David Joyner (2006-01)
+-
+-- William Stein (2006-01)
+-
+-- David Joyner (2006-05): added _latex_, __str__, examples
+-
+-- William Stein (2006-12-09): rewrite
+-"""
+-
+-##TODO: Rework this and \code{special_linear} into MatrixGroup class for any
+-##field, wrapping all of GAP's matrix group commands in chapter 41
+-##Matrix Groups of the GAP reference manual.
+-
+-
+-#*****************************************************************************
+-#       Copyright (C) 2005 William Stein <wstein@gmail.com>
+-#
+-#  Distributed under the terms of the GNU General Public License (GPL)
+-#
+-#    This code 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.
+-#
+-#  The full text of the GPL is available at:
+-#
+-#                  http://www.gnu.org/licenses/
+-#*****************************************************************************
+-
+-from sage.structure.unique_representation import UniqueRepresentation
+-from sage.rings.all import is_FiniteField, Integer, FiniteField
+-from matrix_group import MatrixGroup_gap, MatrixGroup_gap_finite_field
+-
+-def GL(n, R, var='a'):
+-    """
+-    Return the general linear group of degree `n` over the ring
+-    `R`.
+-
+-    .. note::
+-        This group is also available via ``groups.matrix.GL()``.
+-
+-    EXAMPLES::
+-
+-        sage: G = GL(6,GF(5))
+-        sage: G.order()
+-        11064475422000000000000000
+-        sage: G.base_ring()
+-        Finite Field of size 5
+-        sage: G.category()
+-        Category of finite groups
+-        sage: TestSuite(G).run()
+-
+-        sage: G = GL(6, QQ)
+-        sage: G.category()
+-        Category of groups
+-        sage: TestSuite(G).run()
+-
+-    Here is the Cayley graph of (relatively small) finite General Linear Group::
+-
+-        sage: g = GL(2,3)
+-        sage: d = g.cayley_graph(); d
+-        Digraph on 48 vertices
+-        sage: d.show(color_by_label=True, vertex_size=0.03, vertex_labels=False)
+-        sage: d.show3d(color_by_label=True)
+-
+-    ::
+-
+-        sage: F = GF(3); MS = MatrixSpace(F,2,2)
+-        sage: gens = [MS([[0,1],[1,0]]),MS([[1,1],[0,1]])]
+-        sage: G = MatrixGroup(gens)
+-        sage: G.order()
+-        48
+-        sage: G.cardinality()
+-        48
+-        sage: H = GL(2,F)
+-        sage: H.order()
+-        48
+-        sage: H == G           # Do we really want this equality?
+-        False
+-        sage: H.as_matrix_group() == G
+-        True
+-        sage: H.gens()
+-        [
+-        [2 0]
+-        [0 1],
+-        [2 1]
+-        [2 0]
+-        ]
+-
+-    TESTS::
+-
+-        sage: groups.matrix.GL(2, 3)
+-        General Linear Group of degree 2 over Finite Field of size 3
+-    """
+-    if isinstance(R, (int, long, Integer)):
+-        R = FiniteField(R, var)
+-    if is_FiniteField(R):
+-        return GeneralLinearGroup_finite_field(n, R)
+-    return GeneralLinearGroup_generic(n, R)
+-
+-class GeneralLinearGroup_generic(UniqueRepresentation, MatrixGroup_gap):
+-    """
+-    TESTS::
+-
+-        sage: G6 = GL(6, QQ)
+-        sage: G6 == G6
+-        True
+-        sage: G6 != G6  # check that #8695 is fixed.
+-        False
+-    """
+-    def _gap_init_(self):
+-        """
+-        EXAMPLES::
+-        
+-            sage: G = GL(6,GF(5))
+-            sage: G._gap_init_()
+-            'GL(6, GF(5))'
+-        """
+-        return "GL(%s, %s)"%(self.degree(), self.base_ring()._gap_init_())
+-
+-    def _latex_(self):
+-        """
+-        EXAMPLES::
+-        
+-            sage: G = GL(6,GF(5))
+-            sage: latex(G)
+-            \text{GL}_{6}(\Bold{F}_{5})
+-        """
+-        return "\\text{GL}_{%s}(%s)"%(self.degree(), self.base_ring()._latex_())
+-    
+-    def _repr_(self):
+-        """
+-        String representation of this linear group.
+-        
+-        EXAMPLES::
+-        
+-            sage: GL(6,GF(5))
+-            General Linear Group of degree 6 over Finite Field of size 5
+-        """
+-        return "General Linear Group of degree %s over %s"%(self.degree(), self.base_ring())
+-
+-    def __call__(self, x):
+-        """
+-        Construct a new element in this group, i.e. try to coerce x into
+-        self if at all possible.
+-        
+-        EXAMPLES: This indicates that the issue from trac #1834 is
+-        resolved::
+-        
+-            sage: G = GL(3, ZZ)
+-            sage: x = [[1,0,1], [0,1,0], [0,0,1]]
+-            sage: G(x)
+-            [1 0 1]
+-            [0 1 0]
+-            [0 0 1]
+-        """
+-        if isinstance(x, self.element_class) and x.parent() is self:
+-            return x
+-        try:
+-            m = self.matrix_space()(x)
+-        except TypeError:
+-            raise TypeError, "Cannot coerce %s to a %s-by-%s matrix over %s"%(x,self.degree(),self.degree(),self.base_ring())
+-        if m.is_invertible():
+-            return self.element_class(m, self)
+-        else:
+-            raise TypeError, "%s is not an invertible matrix"%(x)
+-        
+-    def __contains__(self, x):
+-        """
+-        Return True if x is an element of self, False otherwise.
+-        
+-        EXAMPLES::
+-        
+-            sage: G = GL(2, GF(101))
+-            sage: x = [[0,1], [1,0]]
+-            sage: x in G
+-            True
+-        
+-        ::
+-        
+-            sage: G = GL(3, ZZ)
+-            sage: x = [[1,0,1], [0,2,0], [0,0,1]]
+-            sage: x in G
+-            False
+-        """
+-        try:
+-            x = self(x)
+-        except TypeError:
+-            return False
+-        return True
+-
+-class GeneralLinearGroup_finite_field(GeneralLinearGroup_generic, MatrixGroup_gap_finite_field):
+-
+-    def random_element(self):
+-        """
+-        Return a random element of this group.
+-        
+-        EXAMPLES::
+-        
+-            sage: G = GL(4, GF(3))
+-            sage: G.random_element()  # random
+-            [2 1 1 1]
+-            [1 0 2 1]
+-            [0 1 1 0]
+-            [1 0 0 1]
+-            sage: G.random_element() in G
+-            True
+-
+-        ALGORITHM:
+-
+-        The random matrix is generated by rejection sampling: 
+-        1. Generate a random matrix
+-        2. Check if is is invertible, if so return it
+-        3. Go back to step 1
+-
+-        The expected number of iterations of this procedure is of
+-        order `1 + 1/q` where `q` is the size of the field. In all
+-        cases, the expected number of iterations is less than 4.
+-        """
+-        M = self.matrix_space().random_element()
+-        while not M.is_invertible():
+-            M.randomize()
+-        return self(M)
+diff --git a/sage/groups/matrix_gps/matrix_group_element.py b/sage/groups/matrix_gps/matrix_group_element.py
+deleted file mode 100644
+--- a/sage/groups/matrix_gps/matrix_group_element.py
++++ /dev/null
+@@ -1,478 +0,0 @@
+-"""
+-Matrix Group Elements
+-
+-AUTHORS:
+-
+-- David Joyner (2006-05): initial version David Joyner
+-
+-- David Joyner (2006-05): various modifications to address William
+-  Stein's TODO's.
+-
+-- William Stein (2006-12-09): many revisions.
+-
+-EXAMPLES::
+-
+-    sage: F = GF(3); MS = MatrixSpace(F,2,2)
+-    sage: gens = [MS([[1,0],[0,1]]),MS([[1,1],[0,1]])]
+-    sage: G = MatrixGroup(gens); G
+-    Matrix group over Finite Field of size 3 with 2 generators: 
+-     [[[1, 0], [0, 1]], [[1, 1], [0, 1]]]    
+-    sage: g = G([[1,1],[0,1]])
+-    sage: h = G([[1,2],[0,1]])
+-    sage: g*h
+-    [1 0]
+-    [0 1]    
+-
+-You cannot add two matrices, since this is not a group operation.
+-You can coerce matrices back to the matrix space and add them
+-there::
+-
+-    sage: g + h
+-    Traceback (most recent call last):
+-    ...
+-    TypeError: unsupported operand type(s) for +: 'MatrixGroup_gens_finite_field_with_category.element_class' and 'MatrixGroup_gens_finite_field_with_category.element_class'
+-
+-::
+-
+-    sage: g.matrix() + h.matrix()
+-    [2 0]
+-    [0 2]
+-
+-::
+-
+-    sage: 2*g
+-    Traceback (most recent call last):
+-    ...
+-    TypeError: unsupported operand parent(s) for '*': 'Integer Ring' and 'Matrix group over Finite Field of size 3 with 2 generators: 
+-     [[[1, 0], [0, 1]], [[1, 1], [0, 1]]]'
+-    sage: 2*g.matrix()
+-    [2 2]
+-    [0 2]
+-"""
+-
+-#*****************************************************************************
+-#       Copyright (C) 2006 David Joyner and William Stein <wstein@gmail.com>
+-#
+-#  Distributed under the terms of the GNU General Public License (GPL)
+-#
+-#                  http://www.gnu.org/licenses/
+-#*****************************************************************************
+-
+-from sage.rings.all import Integer, Infinity
+-from sage.interfaces.gap import gap
+-import sage.structure.element as element
+-from sage.matrix.matrix import Matrix
+-from sage.structure.factorization import Factorization
+-from sage.structure.sage_object import have_same_parent
+-
+-def is_MatrixGroupElement(x):
+-    return isinstance(x, MatrixGroupElement)
+-
+-class MatrixGroupElement(element.MultiplicativeGroupElement):
+-    """
+-    An element of a matrix group.
+-    
+-    EXAMPLES::
+-    
+-        sage: F = GF(3); MS = MatrixSpace(F,2,2)
+-               sage: gens = [MS([[1,0],[0,1]]),MS([[1,1],[0,1]])]
+-        sage: G = MatrixGroup(gens)
+-        sage: g = G.random_element()
+-        sage: type(g)
+-        <class 'sage.groups.matrix_gps.matrix_group_element.MatrixGroup_gens_finite_field_with_category.element_class'>
+-    """
+-    def __init__(self, g, parent, check = True):
+-        r"""
+-        Create element of a matrix group.
+-        
+-        INPUT:
+-        
+-        
+-        -  ``g`` - a Matrix
+-        
+-        -  ``parent`` - defines parent group (g must be in
+-           parent or a TypeError is raised).
+-        
+-        -  ``check`` - bool (default: True), if true does some
+-           type checking.
+-        
+-        
+-        TESTS::
+-        
+-            sage: F = GF(3); MS = MatrixSpace(F,2,2)
+-            sage: gens = [MS([[1,0],[0,1]]),MS([[1,1],[0,1]])]
+-            sage: G = MatrixGroup(gens)
+-            sage: g = G.random_element()
+-            sage: TestSuite(g).run()
+-        """
+-        if check:
+-            if not isinstance(g, Matrix):
+-                raise TypeError, "g must be a matrix"
+-            if not (g.parent() is parent):
+-                g = parent.matrix_space()(g)
+-        element.Element.__init__(self, parent)
+-        self.__mat = g
+-
+-    def matrix(self):
+-        """
+-        Obtain the usual matrix (as an element of a matrix space)
+-        associated to this matrix group element.
+-        
+-        One reason to compute the associated matrix is that matrices
+-        support a huge range of functionality.
+-        
+-        EXAMPLES::
+-        
+-            sage: k = GF(7); G = MatrixGroup([matrix(k,2,[1,1,0,1]), matrix(k,2,[1,0,0,2])])
+-            sage: g = G.0
+-            sage: g.matrix()
+-            [1 1]
+-            [0 1]
+-            sage: parent(g.matrix())
+-            Full MatrixSpace of 2 by 2 dense matrices over Finite Field of size 7
+-        
+-        Matrices have extra functionality that matrix group elements do not
+-        have.
+-        
+-        ::
+-        
+-            sage: g.matrix().charpoly('t')
+-            t^2 + 5*t + 1
+-        """
+-        return self.__mat.__copy__()
+-
+-    def _gap_init_(self):
+-        """
+-        Return a string representation of a Gap object corresponding to
+-        this matrix group element.
+-        
+-        EXAMPLES::
+-        
+-            sage: k = GF(7); G = MatrixGroup([matrix(k,2,[1,1,0,1]), matrix(k,2,[1,0,0,2])]); g = G.1
+-            sage: g._gap_init_() # The variable $sage27 belongs to gap(k) and is somehow random
+-            '[[Z(7)^0,0*Z(7)],[0*Z(7),Z(7)^2]]*One($sage27)'
+-            sage: gap(g._gap_init_())
+-            [ [ Z(7)^0, 0*Z(7) ], [ 0*Z(7), Z(7)^2 ] ]
+-        
+-        It may be better to use gap(the matrix), since the result is
+-        cached.
+-        
+-        ::
+-        
+-            sage: gap(G.1)
+-            [ [ Z(7)^0, 0*Z(7) ], [ 0*Z(7), Z(7)^2 ] ]
+-            sage: gap(G.1).IsMatrix()
+-            true
+-        """
+-        return self.__mat._gap_init_()
+-
+-    def _gap_latex_(self):
+-        r"""
+-        Return the GAP latex version of this matrix.
+-        
+-        AUTHORS:
+-
+-        - S. Kohl: Wrote the GAP function.
+-        
+-        EXAMPLES::
+-        
+-            sage: F = GF(3); MS = MatrixSpace(F,2,2)
+-            sage: gens = [MS([[1,0],[0,1]]),MS([[1,1],[0,1]])]
+-            sage: G = MatrixGroup(gens)
+-            sage: g = G([[1, 1], [0, 1]])
+-            sage: print g._gap_latex_()
+-            \left(\begin{array}{rr}%
+-            Z(3)^{0}&Z(3)^{0}\\%
+-            0*Z(3)&Z(3)^{0}\\%
+-            \end{array}\right)%
+-        
+-        Type view(g._latex_()) to see the object in an xdvi window
+-        (assuming you have latex and xdvi installed).
+-        """
+-        s1 = self.__mat._gap_init_()
+-        s2 = gap.eval("LaTeX("+s1+")")
+-        return eval(s2)
+-
+-    def _repr_(self):
+-        """
+-        Return string representation of this matrix.
+-        
+-        EXAMPLES::
+-        
+-            sage: F = GF(3); MS = MatrixSpace(F,2,2)
+-            sage: gens = [MS([[1,0],[0,1]]),MS([[1,1],[0,1]])]
+-            sage: G = MatrixGroup(gens)
+-            sage: g = G([[1, 1], [0, 1]])
+-            sage: g                        # indirect doctest
+-            [1 1]
+-            [0 1]
+-        """
+-        return str(self.__mat)
+-    
+-    def _latex_(self):
+-        r"""
+-        EXAMPLES::
+-        
+-            sage: F = GF(3); MS = MatrixSpace(F,2,2)
+-            sage: gens = [MS([[1,0],[0,1]]),MS([[1,1],[0,1]])]
+-            sage: G = MatrixGroup(gens)
+-            sage: g = G([[1, 1], [0, 1]])
+-            sage: print g._latex_()
+-            \left(\begin{array}{rr}
+-            1 & 1 \\
+-            0 & 1
+-            \end{array}\right)
+-        
+-        Type ``view(g._latex_())`` to see the object in an
+-        xdvi window (assuming you have latex and xdvi installed).
+-        """
+-        return self.__mat._latex_()
+-
+-    def _mul_(self,other):
+-        """
+-        Return the product of self and other, which must have identical
+-        parents.
+-        
+-        EXAMPLES::
+-        
+-            sage: F = GF(3); MS = MatrixSpace(F,2)
+-            sage: gens = [MS([1,0, 0,1]), MS([1,1, 0,1])]
+-            sage: G = MatrixGroup(gens)
+-            sage: g = G([1,1, 0,1])
+-            sage: h = G([1,1, 0,1])
+-            sage: g*h         # indirect doctest
+-            [1 2]
+-            [0 1]
+-        """
+-        parent = self.parent()
+-        return parent.element_class(self.__mat * other.__mat, parent, check=False)
+-    
+-    def _act_on_(self, x, self_on_left):
+-        """
+-        EXAMPLES::
+-        
+-            sage: G = GL(4,7)
+-            sage: G.0 * vector([1,2,3,4])
+-            (3, 2, 3, 4)
+-            sage: v = vector(GF(7), [3,2,1,-1])
+-            sage: g = G.1
+-            sage: v * g == v * g.matrix()   # indirect doctest
+-            True
+-        """
+-        if not is_MatrixGroupElement(x) and x not in self.parent().base_ring():
+-            try:
+-                if self_on_left:
+-                    return self.matrix() * x
+-                else:
+-                    return x * self.matrix()
+-            except TypeError:
+-                return None
+-
+-    def __invert__(self):
+-        parent = self.parent()
+-        return parent.element_class(~self.__mat, parent, check=False)
+-
+-    def __cmp__(self, other):
+-        """
+-        EXAMPLES::
+-        
+-            sage: F = GF(3); MS = MatrixSpace(F,2)
+-            sage: gens = [MS([1,0, 0,1]), MS([1,1, 0,1])]
+-            sage: G = MatrixGroup(gens)
+-            sage: g = G([1,1, 0,1])
+-            sage: h = G([1,1, 0,1])
+-            sage: g == h
+-            True
+-        """
+-        return cmp(self.__mat, other.__mat)
+-
+-    def __eq__(self, other):
+-        """
+-        EXAMPLES::
+-
+-            sage: F = GF(3); MS = MatrixSpace(F,2)
+-            sage: gens = [MS([1,0, 0,1]), MS([1,1, 0,1])]
+-            sage: G = MatrixGroup(gens)
+-            sage: H = MatrixGroup(gens)
+-            sage: g = G([1,1, 0,1])
+-            sage: h = H([1,1, 0,1])
+-            sage: g == h
+-            True
+-        """
+-        return have_same_parent(self, other) and self.__mat == other.__mat
+-
+-    def __ne__(self, other):
+-        """
+-        EXAMPLES::
+-
+-            sage: F = GF(3); MS = MatrixSpace(F,2)
+-            sage: gens = [MS([1,0, 0,1]), MS([1,1, 0,1])]
+-            sage: G = MatrixGroup(gens)
+-            sage: H = MatrixGroup(gens)
+-            sage: g = G([1,1, 0,1])
+-            sage: h = H([1,1, 0,1])
+-            sage: g != h
+-            False
+-        """
+-        return not self.__eq__(other)
+-
+-    def order(self):
+-        """
+-        Return the order of this group element, which is the smallest
+-        positive integer `n` such that `g^n = 1`, or
+-        +Infinity if no such integer exists.
+-        
+-        EXAMPLES::
+-        
+-            sage: k = GF(7); G = MatrixGroup([matrix(k,2,[1,1,0,1]), matrix(k,2,[1,0,0,2])])
+-            sage: G
+-            Matrix group over Finite Field of size 7 with 2 generators: 
+-             [[[1, 1], [0, 1]], [[1, 0], [0, 2]]]
+-            sage: G.order()
+-            21        
+-        
+-        See trac #1170
+-        
+-        ::
+-        
+-            sage: gl=GL(2,ZZ); gl  
+-            General Linear Group of degree 2 over Integer Ring
+-            sage: g=gl.gens()[2]; g
+-            [1 1]
+-            [0 1]
+-            sage: g.order()        
+-            +Infinity
+-        """
+-        try:
+-            return self.__order
+-        except AttributeError:
+-            try:
+-                self.__order = Integer(self._gap_().Order())
+-            except TypeError:
+-                self.__order = Infinity
+-            return self.__order
+-
+-    def word_problem(self, gens=None):
+-        r"""
+-        Write this group element in terms of the elements of the list
+-        ``gens``, or the standard generators of the parent of self if
+-        ``gens`` is None.
+-        
+-        INPUT:
+-
+-        - ``gens`` - a list of elements that can be coerced into the parent of
+-          self, or None.
+-
+-        ALGORITHM: Use GAP, which has optimized algorithms for solving the
+-        word problem (the GAP functions EpimorphismFromFreeGroup and
+-        PreImagesRepresentative).
+-        
+-        EXAMPLE::
+-        
+-            sage: G = GL(2,5); G
+-            General Linear Group of degree 2 over Finite Field of size 5
+-            sage: G.gens()
+-            [
+-            [2 0]
+-            [0 1],
+-            [4 1]
+-            [4 0]
+-            ]
+-            sage: G(1).word_problem([G.1, G.0])
+-            1
+-        
+-        Next we construct a more complicated element of the group from the
+-        generators::
+-        
+-            sage: s,t = G.0, G.1
+-            sage: a = (s * t * s); b = a.word_problem(); b
+-            ([2 0]
+-            [0 1]) *
+-            ([4 1]
+-            [4 0]) *
+-            ([2 0]
+-            [0 1])
+-            sage: b.prod() == a
+-            True
+-
+-        We solve the word problem using some different generators::
+-
+-            sage: s = G([2,0,0,1]); t = G([1,1,0,1]); u = G([0,-1,1,0])
+-            sage: a.word_problem([s,t,u])
+-            ([2 0]
+-            [0 1])^-1 *
+-            ([1 1]
+-            [0 1])^-1 *
+-            ([0 4]
+-            [1 0]) *
+-            ([2 0]
+-            [0 1])^-1
+-
+-        We try some elements that don't actually generate the group::
+-
+-            sage: a.word_problem([t,u])
+-            Traceback (most recent call last):
+-            ...
+-            ValueError: Could not solve word problem
+-
+-        AUTHORS:
+-
+-        - David Joyner and William Stein
+-        - David Loeffler (2010): fixed some bugs
+-        """
+-        G = self.parent()
+-        gg = gap(G)
+-        if not gens:
+-            gens = gg.GeneratorsOfGroup()
+-        else:
+-            gens = gap([G(x) for x in gens])
+-        H = gens.Group()
+-        hom = H.EpimorphismFromFreeGroup()
+-        in_terms_of_gens = str(hom.PreImagesRepresentative(self))
+-        if 'identity' in in_terms_of_gens:
+-            return Factorization([])
+-        elif in_terms_of_gens == 'fail':
+-            raise ValueError, "Could not solve word problem"
+-        v = list(H.GeneratorsOfGroup())
+-        F = G.field_of_definition()
+-        w = [G(x._matrix_(F)) for x in v]
+-        factors = [Factorization([(x,1)]) for x in w]
+-        d = dict([('x%s'%(i+1),factors[i]) for i in range(len(factors))])
+-
+-        from sage.misc.sage_eval import sage_eval
+-        F = sage_eval(str(in_terms_of_gens), d)
+-        F._set_cr(True)
+-        return F
+-
+-    def list(self):
+-        """
+-        Return list representation of this matrix.
+-        
+-        EXAMPLES::
+-        
+-            sage: F = GF(3); MS = MatrixSpace(F,2,2)
+-            sage: gens = [MS([[1,0],[0,1]]),MS([[1,1],[0,1]])]
+-            sage: G = MatrixGroup(gens)
+-            sage: g = G.0
+-            sage: g.list()   
+-            [[1, 0], [0, 1]]
+-        """
+-        rws = (self.__mat).rows()
+-        lrws = [list(x) for x in rws]
+-        return lrws
+-
+-    def conjugacy_class(self):
+-        r"""
+-        Return the conjugacy class of ``self``.
+-
+-        EXAMPLES::
+-
+-            sage: G = SL(2, GF(2))
+-            sage: g = G.gens()[0]
+-            sage: g.conjugacy_class()
+-            Conjugacy class of [1 1]
+-            [0 1] in Special Linear Group of degree 2 over Finite Field of size 2
+-        """
+-        from sage.groups.conjugacy_classes import ConjugacyClassGAP
+-        return ConjugacyClassGAP(self.parent(), self)
+-
+diff --git a/sage/groups/matrix_gps/matrix_group_morphism.py b/sage/groups/matrix_gps/matrix_group_morphism.py
+deleted file mode 100644
+--- a/sage/groups/matrix_gps/matrix_group_morphism.py
++++ /dev/null
+@@ -1,255 +0,0 @@
+-"""
+-Homomorphisms Between Matrix Groups
+-
+-AUTHORS:
+-
+-- David Joyner and William Stein (2006-03): initial version
+-
+-- David Joyner (2006-05): examples
+-
+-- Simon King (2011-01): cleaning and improving code
+-"""
+-
+-#*****************************************************************************
+-#       Copyright (C) 2006 David Joyner and William Stein <wstein@gmail.com>
+-#
+-#  Distributed under the terms of the GNU General Public License (GPL)
+-#  as published by the Free Software Foundation; either version 2 of
+-#  the License, or (at your option) any later version.
+-#                  http://www.gnu.org/licenses/
+-#*****************************************************************************
+-
+-from sage.interfaces.gap import gap
+-from sage.categories.morphism import *
+-from sage.misc.latex import latex
+-
+-class MatrixGroupMap(Morphism):
+-    """
+-    A set-theoretic map between matrix groups.
+-    """
+-    def __init__(self, parent):
+-        Morphism.__init__(self, parent)
+-
+-    def _repr_type(self):
+-        return "MatrixGroup"
+-
+-class MatrixGroupMorphism(MatrixGroupMap):
+-    pass
+-
+-class MatrixGroupMorphism_im_gens(MatrixGroupMorphism):
+-    """
+-    Some python code for wrapping GAP's GroupHomomorphismByImages
+-    function but only for matrix groups. Can be expensive if G is
+-    large.
+-    
+-    EXAMPLES::
+-    
+-        sage: F = GF(5); MS = MatrixSpace(F,2,2)
+-        sage: G = MatrixGroup([MS([1,1,0,1])])
+-        sage: H = MatrixGroup([MS([1,0,1,1])])
+-        sage: phi = G.hom(H.gens())
+-        sage: phi
+-        Homomorphism : Matrix group over Finite Field of size 5 with 1 generators: 
+-         [[[1, 1], [0, 1]]] --> Matrix group over Finite Field of size 5 with 1 generators: 
+-         [[[1, 0], [1, 1]]]
+-        sage: phi(MS([1,1,0,1]))
+-        [1 0]
+-        [1 1]
+-        sage: F = GF(7); MS = MatrixSpace(F,2,2)
+-        sage: F.multiplicative_generator()
+-        3
+-        sage: G = MatrixGroup([MS([3,0,0,1])])
+-        sage: a = G.gens()[0]^2
+-        sage: phi = G.hom([a])
+-    """
+-    def __init__(self, homset, imgsH, check=True):
+-        MatrixGroupMorphism.__init__(self, homset)   # sets the parent
+-        G = homset.domain()
+-        H = homset.codomain()
+-        gaplist_gens = [gap(x) for x in G.gens()]
+-        gaplist_imgs = [gap(x) for x in imgsH]
+-        genss = '[%s]'%(','.join(str(v) for v in gaplist_gens))
+-        imgss = '[%s]'%(','.join(str(v) for v in gaplist_imgs))
+-        args = '%s, %s, %s, %s'%(G._gap_init_(), H._gap_init_(), genss, imgss)
+-        self._gap_str = 'GroupHomomorphismByImages(%s)'%args
+-        phi0 = gap(self)
+-        if gap.eval("IsGroupHomomorphism(%s)"%phi0.name())!="true":
+-            raise ValueError,"The map "+str(gensG)+"-->"+str(imgsH)+" isn't a homomorphism."
+-
+-    def _repr_(self):
+-        """
+-        EXAMPLES::
+-        
+-            sage: F = GF(5); MS = MatrixSpace(F,2,2)
+-            sage: G = MatrixGroup([MS([1,1,0,1])])
+-            sage: H = MatrixGroup([MS([1,0,1,1])])
+-            sage: phi = G.hom(H.gens())
+-            sage: phi
+-            Homomorphism : Matrix group over Finite Field of size 5 with 1 generators: 
+-             [[[1, 1], [0, 1]]] --> Matrix group over Finite Field of size 5 with 1 generators: 
+-             [[[1, 0], [1, 1]]]            
+-            sage: phi(MS([1,1,0,1]))
+-            [1 0]
+-            [1 1]
+-        """
+-        return "Homomorphism : %s --> %s"%(self.domain(),self.codomain())
+-    
+-    def _latex_(self):
+-        r"""
+-        EXAMPLES::
+-        
+-            sage: F = GF(5); MS = MatrixSpace(F,2,2)
+-            sage: G = MatrixGroup([MS([1,1,0,1])])
+-            sage: phi = G.hom(G.gens())
+-            sage: print latex(phi)
+-            \left\langle \left(\begin{array}{rr}
+-            1 & 1 \\
+-            0 & 1
+-            \end{array}\right) \right\rangle \rightarrow{} \left\langle \left(\begin{array}{rr}
+-            1 & 1 \\
+-            0 & 1
+-            \end{array}\right) \right\rangle
+-        """
+-        return "%s \\rightarrow{} %s"%(latex(self.domain()), latex(self.codomain()))
+-
+-    def _gap_init_(self):
+-        return self._gap_str
+-
+-    def kernel(self):
+-        """
+-        Return the kernel of ``self``, i.e., a matrix group.
+-
+-        EXAMPLES::
+-        
+-            sage: F = GF(7); MS = MatrixSpace(F,2,2)
+-            sage: F.multiplicative_generator()
+-            3
+-            sage: G = MatrixGroup([MS([3,0,0,1])])
+-            sage: a = G.gens()[0]^2
+-            sage: phi = G.hom([a])
+-            sage: phi.kernel()
+-            Matrix group over Finite Field of size 7 with 1 generators: 
+-             [[[6, 0], [0, 1]]]
+-
+-        """
+-        gap_ker = gap(self).Kernel()
+-        from sage.all import MatrixGroup
+-        F = self.domain().base_ring()
+-        return MatrixGroup([x._matrix_(F) for x in gap_ker.GeneratorsOfGroup()])
+-
+-    def pushforward(self, J, *args,**kwds):
+-        """
+-        The image of an element or a subgroup.
+-
+-        INPUT:
+-
+-        ``J`` -- a subgroup or an element of the domain of ``self``.
+-
+-        OUTPUT:
+-
+-        The image of ``J`` under ``self``
+-        
+-        NOTE:
+-
+-        ``pushforward`` is the method that is used when a map is called on
+-        anything that is not an element of its domain. For historical reasons,
+-        we keep the alias ``image()`` for this method.
+-
+-        EXAMPLES::
+-        
+-            sage: F = GF(7); MS = MatrixSpace(F,2,2)
+-            sage: F.multiplicative_generator()
+-            3
+-            sage: G = MatrixGroup([MS([3,0,0,1])])
+-            sage: a = G.gens()[0]^2
+-            sage: phi = G.hom([a])
+-            sage: phi.image(G.gens()[0]) # indirect doctest
+-            [2 0]
+-            [0 1]
+-            sage: H = MatrixGroup([MS(a.list())])
+-            sage: H
+-            Matrix group over Finite Field of size 7 with 1 generators:
+-             [[[2, 0], [0, 1]]]
+-
+-        The following tests against trac ticket #10659::
+-
+-            sage: phi(H)   # indirect doctestest
+-            Matrix group over Finite Field of size 7 with 1 generators: 
+-             [[[4, 0], [0, 1]]]
+-        """
+-        phi = gap(self)
+-        F = self.codomain().base_ring()
+-        from sage.all import MatrixGroup
+-        gapJ = gap(J)
+-        if gap.eval("IsGroup(%s)"%gapJ.name()) == "true":
+-            return MatrixGroup([x._matrix_(F) for x in phi.Image(gapJ).GeneratorsOfGroup()])
+-        return phi.Image(gapJ)._matrix_(F)
+-
+-    image = pushforward
+-
+-    def _call_( self, g ):
+-        """
+-        Some python code for wrapping GAP's Images function for a matrix
+-        group G. Returns an error if g is not in G.
+-        
+-        EXAMPLES::
+-        
+-            sage: F = GF(5); MS = MatrixSpace(F,2,2)
+-            sage: g = MS([1,1,0,1])
+-            sage: G = MatrixGroup([g])
+-            sage: phi = G.hom(G.gens())
+-            sage: phi(G.0)
+-            [1 1]
+-            [0 1]
+-            sage: phi(G(g^2))
+-            [1 2]
+-            [0 1]
+-        
+-        ::
+-        
+-            sage: F = GF(5); MS = MatrixSpace(F,2,2)
+-            sage: gens = [MS([1,2,  -1,1]),MS([1,1,  0,1])]
+-            sage: G = MatrixGroup(gens)
+-            sage: phi = G.hom(G.gens())
+-            sage: phi(G.0)
+-            [1 2]
+-            [4 1]
+-            sage: phi(G.1)
+-            [1 1]
+-            [0 1]
+-
+-        TEST:
+-
+-        The following tests that the call method was successfully
+-        improved in trac ticket #10659::
+-
+-            sage: O = WeylGroup(['D',6])
+-            sage: r = prod(O.gens())
+-            sage: r_ = r^-1
+-            sage: f = O.hom([r*x*r_ for x in O.gens()])  # long time (19s on sage.math, 2011)
+-            sage: [f(x) for x in O.gens()]  # long time
+-            [
+-            [1 0 0 0 0 0]  [1 0 0 0 0 0]  [1 0 0 0 0 0]  [ 0  0  0  0 -1  0]
+-            [0 0 1 0 0 0]  [0 1 0 0 0 0]  [0 1 0 0 0 0]  [ 0  1  0  0  0  0]
+-            [0 1 0 0 0 0]  [0 0 0 1 0 0]  [0 0 1 0 0 0]  [ 0  0  1  0  0  0]
+-            [0 0 0 1 0 0]  [0 0 1 0 0 0]  [0 0 0 0 1 0]  [ 0  0  0  1  0  0]
+-            [0 0 0 0 1 0]  [0 0 0 0 1 0]  [0 0 0 1 0 0]  [-1  0  0  0  0  0]
+-            [0 0 0 0 0 1], [0 0 0 0 0 1], [0 0 0 0 0 1], [ 0  0  0  0  0  1],
+-            <BLANKLINE>
+-            [0 0 0 0 0 1]  [ 0  0  0  0  0 -1]
+-            [0 1 0 0 0 0]  [ 0  1  0  0  0  0]
+-            [0 0 1 0 0 0]  [ 0  0  1  0  0  0]
+-            [0 0 0 1 0 0]  [ 0  0  0  1  0  0]
+-            [0 0 0 0 1 0]  [ 0  0  0  0  1  0]
+-            [1 0 0 0 0 0], [-1  0  0  0  0  0]
+-            ]
+-            sage: f(O)  # long time
+-            Matrix group over Rational Field with 6 generators: 
+-             [[[1, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0], [0, 1, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 0, 1]], [[1, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0], [0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 0, 1]], [[1, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 1, 0], [0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 0, 1]], [[0, 0, 0, 0, -1, 0], [0, 1, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0], [-1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1]], [[0, 0, 0, 0, 0, 1], [0, 1, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 1, 0], [1, 0, 0, 0, 0, 0]], [[0, 0, 0, 0, 0, -1], [0, 1, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 1, 0], [-1, 0, 0, 0, 0, 0]]]
+-
+-        """
+-        phi = gap(self)
+-        G = self.domain()
+-        F = G.base_ring()
+-        h = gap(g)
+-        return phi.Image(h)._matrix_(F)
+diff --git a/sage/groups/matrix_gps/matrix_groups_catalog.py b/sage/groups/matrix_gps/matrix_groups_catalog.py
+deleted file mode 100644
+--- a/sage/groups/matrix_gps/matrix_groups_catalog.py
++++ /dev/null
+@@ -1,21 +0,0 @@
+-r"""
+-Type ``groups.matrix.<tab>`` to access examples
+-of groups implemented as permutation groups.
+-"""
+-
+-# groups imported here will be available
+-# via  groups.matrix.<tab>
+-#
+-# Do not use this file for code
+-#
+-# If you import a new group, then add an
+-# entry to the list in the module-level
+-# docstring of groups/groups_catalog.py
+-
+-from general_linear import GL
+-from special_linear import SL
+-from symplectic import Sp
+-from unitary import SU, GU
+-from orthogonal import SO, GO
+-from sage.groups.misc_gps.misc_groups import QuaternionMatrixGroupGF3 as QuaternionGF3
+-

File trac_14014_libgap_cyclotomic_matrix.patch

+# HG changeset patch
+# Parent 9c0aba4e14d3c00f957d6bb2f66cd4acd85f1186
+
+Cyclotomic numbers and matrix support for LibGAP, bugfixes.
+
+diff --git a/sage/groups/free_group.py b/sage/groups/free_group.py
+--- a/sage/groups/free_group.py
++++ b/sage/groups/free_group.py
+@@ -167,6 +167,46 @@
+             x = AbstractWordTietzeWord(l, parent._gap_gens())
+         ElementLibGAP.__init__(self, x, parent)
+ 
++    def _latex_(self):
++        """
++        Return a LaTeX representation
++
++        OUTPUT:
++
++        String. A valid LaTeX math command sequence.
++
++        EXAMPLES::
++
++            sage: F.<a,b,c> = FreeGroup()
++            sage: f = F([1, 2, 2, -3, -1]) * c^15 * a^(-23)
++            sage: f._latex_()
++            'a\\cdot b^{2}\\cdot c^{-1}\\cdot a^{-1}\\cdot c^{15}\\cdot a^{-23}'
++
++            sage: F = FreeGroup(3)
++            sage: f = F([1, 2, 2, -3, -1]) * F.gen(2)^11 * F.gen(0)^(-12)
++            sage: f._latex_()
++            'x_{0}\\cdot x_{1}^{2}\\cdot x_{2}^{-1}\\cdot x_{0}^{-1}\\cdot x_{2}^{11}\\cdot x_{0}^{-12}'
++
++            sage: F.<a,b,c> = FreeGroup()
++            sage: G = F /  (F([1, 2, 1, -3, 2, -1]), F([2, -1]))
++            sage: f = G([1, 2, 2, -3, -1]) * G.gen(2)^15 * G.gen(0)^(-23)
++            sage: f._latex_()
++            'a\\cdot b^{2}\\cdot c^{-1}\\cdot a^{-1}\\cdot c^{15}\\cdot a^{-23}'
++
++            sage: F = FreeGroup(4)
++            sage: G = F.quotient((F([1, 2, 4, -3, 2, -1]), F([2, -1])))
++            sage: f = G([1, 2, 2, -3, -1]) * G.gen(3)^11 * G.gen(0)^(-12)
++            sage: f._latex_()
++            'x_{0}\\cdot x_{1}^{2}\\cdot x_{2}^{-1}\\cdot x_{0}^{-1}\\cdot x_{3}^{11}\\cdot x_{0}^{-12}'
++        """
++        import re
++        s = self._repr_()
++        s = re.sub('([a-z]|[A-Z])([0-9]+)', '\g<1>_{\g<2>}', s)
++        s = re.sub('(\^)(-)([0-9]+)', '\g<1>{\g<2>\g<3>}', s)
++        s = re.sub('(\^)([0-9]+)', '\g<1>{\g<2>}', s)
++        s = s.replace('*', '\cdot ')
++        return s
++
+     def __reduce__(self):
+         """
+         Implement pickling.
+diff --git a/sage/groups/libgap_group.py b/sage/groups/libgap_group.py
+new file mode 100644
+--- /dev/null
++++ b/sage/groups/libgap_group.py
+@@ -0,0 +1,67 @@
++"""
++Generic LibGAP-based Group
++
++This is useful if you need to use a GAP group implementation in Sage
++that does not have a dedicated Sage interface.
++
++If you want to implement your own group class, you should not derive
++from this but directly from
++:class:`~sage.groups.libgap_wrapper.ParentLibGAP`.
++
++EXAMPLES::
++
++    sage: F.<a,b> = FreeGroup()
++    sage: G_gap = libgap.Group([ (a*b^2).gap() ])
++    sage: from sage.groups.libgap_group import GroupLibGAP
++    sage: G = GroupLibGAP(G_gap);  G
++    Group([ a*b^2 ])
++    sage: type(G)
++    <class 'sage.groups.libgap_group.GroupLibGAP_with_category'>
++    sage: G.gens() 
++    (a*b^2,)
++"""
++
++##############################################################################
++#       Copyright (C) 2013 Volker Braun <vbraun.name@gmail.com>
++#
++#  Distributed under the terms of the GNU General Public License (GPL)
++#
++#  The full text of the GPL is available at:
++#
++#                  http://www.gnu.org/licenses/
++##############################################################################
++
++
++from sage.groups.group import Group
++from sage.groups.libgap_wrapper import ParentLibGAP, ElementLibGAP
++
++class GroupLibGAP(Group, ParentLibGAP):
++    
++    Element = ElementLibGAP
++
++    def __init__(self, *args, **kwds):
++        """
++        Group interface for LibGAP-based groups.
++
++        INPUT:
++
++        Same as :class:`~sage.groups.libgap_wrapper.ParentLibGAP`.
++
++        TESTS::
++
++            sage: F.<a,b> = FreeGroup()
++            sage: G_gap = libgap.Group([ (a*b^2).gap() ])
++            sage: from sage.groups.libgap_group import GroupLibGAP
++            sage: G = GroupLibGAP(G_gap);  G
++            Group([ a*b^2 ])
++            sage: g = G.gen(0);  g
++            a*b^2
++            sage: TestSuite(G).run(skip=['_test_pickling', '_test_elements'])
++            sage: TestSuite(g).run(skip=['_test_pickling'])
++        """
++        ParentLibGAP.__init__(self, *args, **kwds)
++        Group.__init__(self)
++
++
++
++
+diff --git a/sage/groups/libgap_mixin.py b/sage/groups/libgap_mixin.py
+new file mode 100644
+--- /dev/null
++++ b/sage/groups/libgap_mixin.py
+@@ -0,0 +1,555 @@
++"""
++Mix-in Class for libGAP-based Groups
++
++This class adds access to GAP functionality to groups such that parent
++and element have a ``gap()`` method that returns a libGAP object for
++the parent/element.
++
++If your group implementation uses libgap, then you should add
++:class:`GroupMixinLibGAP` as the first class that you are deriving
++from. This ensures that it properly overrides any default methods that
++just raise ``NotImplemented``.
++"""
++
++from sage.libs.all import libgap
++from sage.misc.cachefunc import cached_method
++
++
++class GroupElementMixinLibGAP(object):
++
++    @cached_method
++    def order(self):
++        """
++        Return the order of this group element, which is the smallest
++        positive integer `n` such that `g^n = 1`, or
++        +Infinity if no such integer exists.
++        
++        EXAMPLES::
++        
++            sage: k = GF(7); 
++            sage: G = MatrixGroup([matrix(k,2,[1,1,0,1]), matrix(k,2,[1,0,0,2])]); G
++            Matrix group over Finite Field of size 7 with 2 generators (
++            [1 1]  [1 0]
++            [0 1], [0 2]
++            )
++            sage: G.order()
++            21    
++            sage: G.gen(0).order(), G.gen(1).order()
++            (7, 3)
++
++            sage: k = QQ; 
++            sage: G = MatrixGroup([matrix(k,2,[1,1,0,1]), matrix(k,2,[1,0,0,2])]); G
++            Matrix group over Rational Field with 2 generators (
++            [1 1]  [1 0]
++            [0 1], [0 2]
++            )
++            sage: G.order()
++            +Infinity
++            sage: G.gen(0).order(), G.gen(1).order()
++            (+Infinity, +Infinity)
++      
++            sage: gl = GL(2, ZZ);  gl
++            General Linear Group of degree 2 over Integer Ring
++            sage: g = gl.gen(2);  g
++            [1 1]
++            [0 1]
++            sage: g.order()        
++            +Infinity
++        """
++        order = self.gap().Order()
++        if order.IsInt():
++            return order.sage()
++        else:
++            assert order.IsInfinity()
++            from sage.rings.all import Infinity
++            return Infinity
++
++    def word_problem(self, gens=None):
++        r"""
++        Solve the word problem.
++
++        This method writes the group element as a product of the
++        elements of the list ``gens``, or the standard generators of
++        the parent of self if ``gens`` is None.
++        
++        INPUT:
++
++        - ``gens`` -- a list/tuple/iterable of elements (or objects
++          that can be converted to group elements), or ``None``
++          (default). By default, the generators of the parent group
++          are used.
++
++        OUTPUT:
++
++        A factorization object that contains information about the
++        order of factors and the exponents. A ``ValueError`` is raised
++        if the group element cannot be written as a word in ``gens``.
++
++        ALGORITHM: 
++
++        Use GAP, which has optimized algorithms for solving the word
++        problem (the GAP functions ``EpimorphismFromFreeGroup`` and
++        ``PreImagesRepresentative``).
++        
++        EXAMPLE::
++        
++            sage: G = GL(2,5); G
++            General Linear Group of degree 2 over Finite Field of size 5
++            sage: G.gens()
++            (
++            [2 0]  [4 1]
++            [0 1], [4 0]
++            )
++            sage: G(1).word_problem([G.gen(0)])
++            1
++            sage: type(_)
++            <class 'sage.structure.factorization.Factorization'>
++
++            sage: g = G([0,4,1,4])
++            sage: g.word_problem()
++            ([4 1]
++             [4 0])^-1
++
++        Next we construct a more complicated element of the group from the
++        generators::
++        
++            sage: s,t = G.0, G.1
++            sage: a = (s * t * s); b = a.word_problem(); b
++            ([2 0]
++             [0 1]) *
++            ([4 1]
++             [4 0]) *
++            ([2 0]
++             [0 1])
++            sage: flatten(b)
++            [
++            [2 0]     [4 1]     [2 0]   
++            [0 1], 1, [4 0], 1, [0 1], 1
++            ]
++            sage: b.prod() == a
++            True
++
++        We solve the word problem using some different generators::
++
++            sage: s = G([2,0,0,1]); t = G([1,1,0,1]); u = G([0,-1,1,0])
++            sage: a.word_problem([s,t,u])
++            ([2 0]
++             [0 1])^-1 *
++            ([1 1]
++             [0 1])^-1 *
++            ([0 4]
++             [1 0]) *
++            ([2 0]
++             [0 1])^-1
++
++        We try some elements that don't actually generate the group::
++
++            sage: a.word_problem([t,u])
++            Traceback (most recent call last):
++            ...
++            ValueError: word problem has no solution
++
++        AUTHORS:
++
++        - David Joyner and William Stein
++        - David Loeffler (2010): fixed some bugs
++        - Volker Braun (2013): LibGAP
++        """
++        from sage.libs.gap.libgap import libgap
++        G = self.parent()
++        if gens:
++            gen = lambda i:gens[i]
++            H = libgap.Group([G(x).gap() for x in gens])
++        else:
++            gen = G.gen
++            H = G.gap()
++        hom = H.EpimorphismFromFreeGroup()
++        preimg = hom.PreImagesRepresentative(self.gap())
++
++        if preimg.is_bool():
++            assert preimg == libgap.eval('fail')
++            raise ValueError('word problem has no solution')
++            
++        result = []
++        n = preimg.NumberSyllables().sage()
++        exponent_syllable  = libgap.eval('ExponentSyllable')
++        generator_syllable = libgap.eval('GeneratorSyllable')
++        for i in range(n):
++            exponent  = exponent_syllable(preimg, i+1).sage()
++            generator = gen(generator_syllable(preimg, i+1).sage() - 1)
++            result.append( (generator, exponent) )
++        from sage.structure.factorization import Factorization
++        result = Factorization(result)
++        result._set_cr(True)
++        return result
++
++
++class GroupMixinLibGAP(object):
++    
++    @cached_method
++    def is_abelian(self):
++        r"""
++        Test whether the group is Abelian.
++
++        OUTPUT: 
++        
++        Boolean. ``True`` if this group is an Abelian group.
++        
++        EXAMPLES::
++        
++            sage: SL(1, 17).is_abelian()
++            True
++            sage: SL(2, 17).is_abelian()
++            False
++        """
++        return self.gap().IsAbelian().sage()
++
++    @cached_method
++    def is_finite(self):
++        """
++        Test whether the matrix group is finite.
++
++        OUTPUT:
++
++        Boolean.
++        
++        EXAMPLES::
++        
++            sage: G = GL(2,GF(3))
++            sage: G.is_finite()
++            True
++            sage: SL(2,ZZ).is_finite()
++            False
++        """
++        return self.gap().IsFinite().sage()
++
++    def cardinality(self):
++        """
++        Implements :meth:`EnumeratedSets.ParentMethods.cardinality`.
++
++        EXAMPLES::
++        
++            sage: G = Sp(4,GF(3))
++            sage: G.cardinality()
++            51840
++
++            sage: G = SL(4,GF(3))
++            sage: G.cardinality()
++            12130560
++
++            sage: F = GF(5); MS = MatrixSpace(F,2,2)
++            sage: gens = [MS([[1,2],[-1,1]]),MS([[1,1],[0,1]])]
++            sage: G = MatrixGroup(gens)
++            sage: G.cardinality()
++            480
++
++            sage: G = MatrixGroup([matrix(ZZ,2,[1,1,0,1])])
++            sage: G.cardinality()
++            +Infinity
++
++            sage: G = Sp(4,GF(3))
++            sage: G.cardinality()
++            51840
++
++            sage: G = SL(4,GF(3))
++            sage: G.cardinality()
++            12130560
++
++            sage: F = GF(5); MS = MatrixSpace(F,2,2)
++            sage: gens = [MS([[1,2],[-1,1]]),MS([[1,1],[0,1]])]
++            sage: G = MatrixGroup(gens)
++            sage: G.cardinality()
++            480
++
++            sage: G = MatrixGroup([matrix(ZZ,2,[1,1,0,1])])
++            sage: G.cardinality()
++            +Infinity
++        """
++        if self.is_finite():
++            return self.gap().Size().sage()
++        from sage.rings.infinity import Infinity
++        return Infinity
++    
++    order = cardinality
++
++    @cached_method
++    def conjugacy_class_representatives(self):
++        """
++        Return a set of representatives for each of the conjugacy classes
++        of the group.
++        
++        EXAMPLES::
++        
++            sage: G = SU(3,GF(2))
++            sage: len(G.conjugacy_class_representatives())
++            16
++
++            sage: G = GL(2,GF(3))
++            sage: G.conjugacy_class_representatives()
++            (
++            [1 0]  [0 2]  [2 0]  [0 2]  [0 2]  [0 1]  [0 1]  [2 0]
++            [0 1], [1 1], [0 2], [1 2], [1 0], [1 2], [1 1], [0 1]
++            )
++
++            sage: len(GU(2,GF(5)).conjugacy_class_representatives())
++            36
++        """
++        G = self.gap()
++        reps = [ cc.Representative() for cc in G.ConjugacyClasses() ]
++        return tuple(self(g) for g in reps)
++
++    @cached_method    
++    def conjugacy_classes(self):
++        r"""
++        Return a list with all the conjugacy classes of ``self``.
++        
++        EXAMPLES::
++
++            sage: G = SL(2, GF(2))
++            sage: G.conjugacy_classes()
++            (Conjugacy class of [1 0]
++             [0 1] in Special Linear Group of degree 2 over Finite Field of size 2, 
++             Conjugacy class of [0 1]
++             [1 0] in Special Linear Group of degree 2 over Finite Field of size 2, 
++             Conjugacy class of [0 1]
++             [1 1] in Special Linear Group of degree 2 over Finite Field of size 2)
++        """
++        from sage.groups.conjugacy_classes import ConjugacyClassGAP
++        G = self.gap()
++        reps = [ cc.Representative() for cc in G.ConjugacyClasses() ]
++        return tuple(ConjugacyClassGAP(self, self(g)) for g in reps)
++    
++    def class_function(self, values):
++        """
++        Return the class function with given values.
++
++        INPUT:
++
++        - ``values`` -- list/tuple/iterable of numbers. The values of the
++          class function on the conjugacy classes, in that order.
++          
++        EXAMPLES::
++
++            sage: G = GL(2,GF(3))
++            sage: chi = G.class_function(range(8))
++            sage: list(chi)
++            [0, 1, 2, 3, 4, 5, 6, 7]
++        """
++        from sage.groups.class_function import ClassFunction_libgap
++        return ClassFunction_libgap(self, values)
++
++    @cached_method
++    def center(self):
++        """
++        Return the center of this linear group as a subgroup.
++        
++        OUTPUT:
++
++        The center as a subgroup.
++
++        EXAMPLES::
++        
++            sage: G = SU(3,GF(2))
++            sage: G.center()
++            Matrix group over Finite Field in a of size 2^2 with 1 generators (
++            [a 0 0]
++            [0 a 0]
++            [0 0 a]
++            )
++            sage: GL(2,GF(3)).center()
++            Matrix group over Finite Field of size 3 with 1 generators (
++            [2 0]
++            [0 2]
++            )
++            sage: GL(3,GF(3)).center()
++            Matrix group over Finite Field of size 3 with 1 generators (
++            [2 0 0]
++            [0 2 0]
++            [0 0 2]
++            )
++            sage: GU(3,GF(2)).center()
++            Matrix group over Finite Field in a of size 2^2 with 1 generators (
++            [a + 1     0     0]
++            [    0 a + 1     0]
++            [    0     0 a + 1]
++            )
++
++            sage: A = Matrix(FiniteField(5), [[2,0,0], [0,3,0], [0,0,1]])
++            sage: B = Matrix(FiniteField(5), [[1,0,0], [0,1,0], [0,1,1]])
++            sage: MatrixGroup([A,B]).center()
++            Matrix group over Finite Field of size 5 with 1 generators (
++            [1 0 0]
++            [0 1 0]
++            [0 0 1]
++            )
++        """
++        G = self.gap()
++        center = list(G.Center().GeneratorsOfGroup())
++        if len(center) == 0:
++            center = [G.One()]
++        return self.subgroup(center)
++
++    @cached_method
++    def irreducible_characters(self):
++        """
++        Returns the irreducible characters of the group.
++
++        OUTPUT:
++
++        A tuple containing all irreducible characters.
++
++        EXAMPLES::
++        
++            sage: G = GL(2,2)
++            sage: G.irreducible_characters()
++            (Character of General Linear Group of degree 2 over Finite Field of size 2,
++             Character of General Linear Group of degree 2 over Finite Field of size 2,
++             Character of General Linear Group of degree 2 over Finite Field of size 2)
++        """
++        Irr = self.gap().Irr()
++        L = []
++        from sage.groups.class_function import ClassFunction_libgap
++        for irr in Irr:
++            L.append(ClassFunction_libgap(self, irr))
++        return tuple(L)
++
++    def random_element(self):
++        """
++        Return a random element of this group.
++
++        OUTPUT:
++
++        A group element.
++        
++        EXAMPLES::
++        
++            sage: G = Sp(4,GF(3))
++            sage: G.random_element()  # random
++            [2 1 1 1]
++            [1 0 2 1]
++            [0 1 1 0]
++            [1 0 0 1]
++            sage: G.random_element() in G
++            True
++
++            sage: F = GF(5); MS = MatrixSpace(F,2,2)
++            sage: gens = [MS([[1,2],[-1,1]]),MS([[1,1],[0,1]])]
++            sage: G = MatrixGroup(gens)
++            sage: G.random_element()  # random
++            [1 3]
++            [0 3]
++            sage: G.random_element() in G
++            True
++        """
++        return self(self.gap().Random())
++
++    def list(self):
++        """
++        List all elements of this group.
++        
++        OUTPUT:
++
++        A tuple containing all group elements in a random but fixed
++        order.
++        
++        EXAMPLES::
++        
++            sage: F = GF(3)
++            sage: gens = [matrix(F,2, [1,0, -1,1]), matrix(F, 2, [1,1,0,1])]
++            sage: G = MatrixGroup(gens)
++            sage: G.cardinality()
++            24
++            sage: v = G.list()
++            sage: len(v)
++            24
++            sage: v[:5]
++            (
++            [0 1]  [0 1]  [0 1]  [0 2]  [0 2]
++            [2 0], [2 1], [2 2], [1 0], [1 1]
++            )
++            sage: all(g in G for g in G.list())
++            True
++
++        An example over a ring (see trac 5241)::
++
++            sage: M1 = matrix(ZZ,2,[[-1,0],[0,1]]) 
++            sage: M2 = matrix(ZZ,2,[[1,0],[0,-1]]) 
++            sage: M3 = matrix(ZZ,2,[[-1,0],[0,-1]]) 
++            sage: MG = MatrixGroup([M1, M2, M3]) 
++            sage: MG.list() 
++            (
++            [-1  0]  [-1  0]  [ 1  0]  [1 0]
++            [ 0 -1], [ 0  1], [ 0 -1], [0 1]
++            )
++            sage: MG.list()[1] 
++            [-1  0] 
++            [ 0  1] 
++            sage: MG.list()[1].parent() 
++            Matrix group over Integer Ring with 3 generators (
++            [-1  0]  [ 1  0]  [-1  0]
++            [ 0  1], [ 0 -1], [ 0 -1]
++            )
++
++        An example over a field (see trac 10515)::
++        
++            sage: gens = [matrix(QQ,2,[1,0,0,1])]
++            sage: MatrixGroup(gens).list()
++            (
++            [1 0]
++            [0 1]
++            )
++
++        Another example over a ring (see trac 9437)::
++
++            sage: len(SL(2, Zmod(4)).list())
++            48
++
++        An error is raised if the group is not finite::
++        
++            sage: GL(2,ZZ).list()
++            Traceback (most recent call last):
++            ...
++            ValueError: group must be finite
++        """
++        if not self.is_finite():
++            raise ValueError('group must be finite')
++        elements = self.gap().Elements()
++        return tuple(self(x) for x in elements)
++
++    def is_isomorphic(self, H):
++        """
++        Test whether ``self`` and ``H`` are isomorphic groups.
++
++        INPUT:
++
++        - ``H`` -- a group.
++
++        OUTPUT:
++
++        Boolean.
++
++        EXAMPLES::
++
++            sage: m1 = matrix(GF(3), [[1,1],[0,1]])
++            sage: m2 = matrix(GF(3), [[1,2],[0,1]])
++            sage: F = MatrixGroup(m1)
++            sage: G = MatrixGroup(m1, m2)
++            sage: H = MatrixGroup(m2)
++            sage: F.is_isomorphic(G)
++            True
++            sage: G.is_isomorphic(H)
++            True
++            sage: F.is_isomorphic(H)
++            True
++            sage: F==G, G==H, F==H
++            (False, False, False)
++        """
++        iso = self.gap().IsomorphismGroups(H.gap())
++        if iso.is_bool():   # fail means not isomorphic
++            try:
++                iso.sage()
++                assert False
++            except ValueError:
++                pass
++            return False
++        return True
+diff --git a/sage/groups/libgap_wrapper.pyx b/sage/groups/libgap_wrapper.pyx
+--- a/sage/groups/libgap_wrapper.pyx
++++ b/sage/groups/libgap_wrapper.pyx
+@@ -59,23 +59,38 @@
+ #                  http://www.gnu.org/licenses/
+ ##############################################################################
+ 
+-from sage.libs.gap.libgap import libgap
+ from sage.libs.gap.element cimport GapElement
+ from sage.rings.integer import Integer
+ from sage.rings.integer_ring import IntegerRing
+ from sage.misc.cachefunc import cached_method
++from sage.structure.sage_object import SageObject
+ from sage.structure.element cimport Element
+ 
+ 
+-class ParentLibGAP(object):
++class ParentLibGAP(SageObject):
+     """
+     A class for parents to keep track of the GAP parent.
+ 
++    This is not a complete group in Sage, this class is only a base
++    class that you can use to implement your own groups with
++    LibGAP. See :mod:`~sage.groups.libgap_group` for a minimal example
++    of a group that is actually usable.
++
++    Your implementation definitely needs to supply 
++
++    * ``__reduce__()``: serialize the LibGAP group. Since GAP does not
++      support Python pickles natively, you need to figure out yourself
++      how you can recreate the group from a pickle.
++    
+     INPUT:
+ 
+     - ``libgap_parent`` -- the libgap element that is the parent in
+       GAP.
+ 
++    - ``ambient`` -- A derived class of :class:`ParentLibGAP` or
++      ``None`` (default). The ambient class if ``libgap_parent`` has
++      been defined as a subgroup.
++
+     EXAMPLES::
+ 
+         sage: from sage.groups.libgap_wrapper import ElementLibGAP, ParentLibGAP
+@@ -92,7 +107,7 @@
+         <pc group of size 3 with 1 generators>
+     """
+ 
+-    def __init__(self, libgap_parent):
++    def __init__(self, libgap_parent, ambient=None):
+         """
+         The Python constructor.
+ 
+@@ -103,6 +118,95 @@
+         """
+         assert isinstance(libgap_parent, GapElement)
+         self._libgap = libgap_parent
++        self._ambient = ambient
++
++    def ambient(self):
++        """
++        Return the ambient group of a subgroup.
++
++        OUTPUT:
++
++        A group containing ``self``. If ``self`` has not been defined
++        as a subgroup, we just return ``self``.
++
++        EXAMPLES::
++
++            sage: G = FreeGroup(3)
++            sage: G.ambient() is G
++            True
++        """
++        if self._ambient is None:
++            return self
++        else:
++            return self._ambient
++
++    def is_subgroup(self):
++        """
++        Return whether the group was defined as a subgroup of a bigger
++        group.
++
++        You can access the contaning group with :meth:`ambient`.
++
++        OUTPUT:
++
++        Boolean.
++
++        EXAMPLES::
++
++            sage: G = FreeGroup(3)
++            sage: G.is_subgroup()
++            False
++        """
++        return self._ambient is not None
++
++    def _subgroup_constructor(self, libgap_subgroup):
++        """
++        Return the class of a subgroup.
++        
++        You should override this with a derived class. Its constructor
++        must accept the same arguments as :meth:`__init__`.
++
++        OUTPUT:
++
++        A new instance of a group (derived class of
++        :class:`ParentLibGAP`).
++
++        TESTS::
++
++            sage: F.<a,b> = FreeGroup()
++            sage: G = F.subgroup([a^2*b]);  G
++            Group([ a^2*b ])
++            sage: F._subgroup_constructor(G.gap())._repr_()
++            'Group([ a^2*b ])'
++        """
++        from sage.groups.libgap_group import GroupLibGAP
++        return GroupLibGAP(libgap_subgroup, ambient=self)
++
++    def subgroup(self, generators):
++        """
++        Return the subgroup generated.
++        
++        INPUT:
++
++        - ``generators`` -- a list/tuple/iterable of group elements.
++
++        OUTPUT:
++
++        The subgroup generated by ``generators``.
++
++        EXAMPLES::
++
++            sage: F.<a,b> = FreeGroup()
++            sage: G = F.subgroup([a^2*b]);  G
++            Group([ a^2*b ])
++            sage: G.gens()
++            (a^2*b,)
++        """
++        generators = [ g if isinstance(g, GapElement) else g.gap()
++                       for g in generators ]
++        G = self.gap()
++        H = G.Subgroup(generators)
++        return self._subgroup_constructor(H)
+ 
+     def gap(self):
+         """
+@@ -190,9 +294,10 @@
+ 
+         TESTS::
+ 
++            sage: from sage.groups.libgap_wrapper import ElementLibGAP, ParentLibGAP
+             sage: G.<a,b> =FreeGroup()
+-            sage: G     # indirect doctest
+-            Free Group on generators {a, b}
++            sage: ParentLibGAP._repr_(G)
++            '<free group on the generators [ a, b ]>'
+         """
+         return self._libgap._repr_()
+ 
+@@ -325,10 +430,15 @@
+             sage: TestSuite(g).run()
+         """
+         MultiplicativeGroupElement.__init__(self, parent)
+-        assert isinstance(libgap_element, GapElement)
+         assert isinstance(parent, ParentLibGAP)
+-        self._libgap = libgap_element
+-
++        if isinstance(libgap_element, GapElement):
++            self._libgap = libgap_element
++        else:
++            if libgap_element == 1:
++                self._libgap = self.parent().gap().Identity()
++            else:
++                raise TypeError('need a libgap group element or "1" in constructor')
++                
+     cpdef GapElement gap(self):
+         """
+         Returns a LibGAP representation of the element
+@@ -413,35 +523,17 @@
+ 
+         EXAMPLES::
+ 
+-            sage: F.<a,b,c> = FreeGroup()
+-            sage: f = F([1, 2, 2, -3, -1]) * c^15 * a^(-23)
+-            sage: f._latex_()
+-            'a\\cdot b^{2}\\cdot c^{-1}\\cdot a^{-1}\\cdot c^{15}\\cdot a^{-23}'
+-
+-            sage: F = FreeGroup(3)
+-            sage: f = F([1, 2, 2, -3, -1]) * F.gen(2)^11 * F.gen(0)^(-12)
+-            sage: f._latex_()
+-            'x_{0}\\cdot x_{1}^{2}\\cdot x_{2}^{-1}\\cdot x_{0}^{-1}\\cdot x_{2}^{11}\\cdot x_{0}^{-12}'
+-
+-            sage: F.<a,b,c> = FreeGroup()
+-            sage: G = F /  (F([1, 2, 1, -3, 2, -1]), F([2, -1]))
+-            sage: f = G([1, 2, 2, -3, -1]) * G.gen(2)^15 * G.gen(0)^(-23)
+-            sage: f._latex_()
+-            'a\\cdot b^{2}\\cdot c^{-1}\\cdot a^{-1}\\cdot c^{15}\\cdot a^{-23}'
+-
+-            sage: F = FreeGroup(4)
+-            sage: G = F.quotient((F([1, 2, 4, -3, 2, -1]), F([2, -1])))
+-            sage: f = G([1, 2, 2, -3, -1]) * G.gen(3)^11 * G.gen(0)^(-12)
+-            sage: f._latex_()
+-            'x_{0}\\cdot x_{1}^{2}\\cdot x_{2}^{-1}\\cdot x_{0}^{-1}\\cdot x_{3}^{11}\\cdot x_{0}^{-12}'
++            sage: from sage.groups.libgap_group import GroupLibGAP
++            sage: G = GroupLibGAP(libgap.FreeGroup('a', 'b'))
++            sage: g = G.gen(0) * G.gen(1)
++            sage: g._latex_()
++            "ab%\n"
+         """
+-        import re
+-        s = self._repr_()
+-        s = re.sub('([a-z]|[A-Z])([0-9]+)', '\g<1>_{\g<2>}', s)
+-        s = re.sub('(\^)(-)([0-9]+)', '\g<1>{\g<2>\g<3>}', s)
+-        s = re.sub('(\^)([0-9]+)', '\g<1>{\g<2>}', s)
+-        s = s.replace('*', '\cdot ')
+-        return s
++        try:
++            return self.gap().LaTeX()
++        except ValueError:
++            from sage.misc.latex import latex
++            return latex(self._repr_())
+ 
+     cpdef MonoidElement _mul_(left, MonoidElement right):
+         """
+@@ -488,6 +580,13 @@
+         Boilerplate for Cython elements
+ 
+         See :mod:`~sage.structure.element` for details.
++
++        EXAMPLES::
++
++            sage: G.<a,b> = FreeGroup('a, b')
++            sage: G_gap = G.gap()
++            sage: G_gap == G_gap    # indirect doctest
++            True
+         """
+         return (<Element>left)._richcmp(right, op)
+ 
+@@ -496,6 +595,12 @@
+         Boilerplate for Cython elements
+ 
+         See :mod:`~sage.structure.element` for details.
++
++        EXAMPLES::
++
++            sage: G.<a,b> = FreeGroup('a, b')
++            sage: cmp(G.gap(), G.gap())   # indirect doctest
++            0
+         """
+         return (<Element>left)._cmp(right)
+ 
+@@ -564,4 +669,3 @@
+ 
+     inverse = __invert__
+ 
+-
+diff --git a/sage/libs/gap/element.pxd b/sage/libs/gap/element.pxd
+--- a/sage/libs/gap/element.pxd
++++ b/sage/libs/gap/element.pxd
+@@ -35,11 +35,14 @@
+ 
+     # comparison
+     cdef bint _compare_by_id
+-    cdef int _cmp_c_impl(self, Element other) except -2
++    cdef _richcmp_c_impl(self, Element other, int op)
++    cdef bint _compare_equal(self, Element other) except -2
++    cdef bint _compare_less(self, Element other) except -2
+     cpdef _set_compare_by_id(self)
+     cpdef _assert_compare_by_id(self)
+ 
+     cdef _initialize(self, parent, libGAP_Obj obj)
++    cpdef _type_number(self)
+     cpdef ModuleElement _add_(self, ModuleElement right)
+     cpdef ModuleElement _sub_(self, ModuleElement right)
+     cpdef RingElement _mul_(self, RingElement right)
+@@ -53,6 +56,18 @@
+ cdef class GapElement_Rational(GapElement):
+     pass
+ 
++cdef class GapElement_IntegerMod(GapElement):
++    cpdef GapElement_Integer lift(self)
++
++cdef class GapElement_FiniteField(GapElement):
++    cpdef GapElement_Integer lift(self)
++
++cdef class GapElement_Cyclotomic(GapElement):
++    pass
++
++cdef class GapElement_Ring(GapElement):
++    pass
++
+ cdef class GapElement_String(GapElement):
+     pass
+ 
+diff --git a/sage/libs/gap/element.pyx b/sage/libs/gap/element.pyx
+--- a/sage/libs/gap/element.pyx
++++ b/sage/libs/gap/element.pyx
+@@ -15,12 +15,34 @@
+ #                   http://www.gnu.org/licenses/
+ ###############################################################################
+ 
++include "../../ext/python_object.pxi"
++
+ from sage.structure.sage_object cimport SageObject
+ from sage.structure.parent import Parent
+ from sage.rings.all import ZZ
+ 
+-
+-
++decode_type_number = {
++    libGAP_T_INT: 'T_INT (integer)',
++    libGAP_T_INTPOS: 'T_INTPOS (positive integer)',
++    libGAP_T_INTNEG: 'T_INTNEG (negative integer)',
++    libGAP_T_RAT: 'T_RAT (rational number)',
++    libGAP_T_CYC: 'T_CYC (