def gap_handle(x):
    """
    Return a low-level libgap handle to the corresponding GAP object.

    EXAMPLES::

        sage: from mygap import mygap
        sage: from mmt import gap_handle
        sage: h = libgap.GF(3)
        sage: F = mygap(h)
        sage: gap_handle(F) is h
        True
        sage: l = gap_handle([1,2,F])
        sage: l
        [ 1, 2, GF(3) ]
        sage: l[0] == 1
        True
        sage: l[2] == h
        True

    .. TODO::

        Maybe we just want, for x a glorified hand, libgap(x) to
        return the corresponding low level handle
    """
    from mygap import GAPObject
    if isinstance(x, (list, tuple)):
        return libgap([gap_handle(y) for y in x])
    elif isinstance(x, GAPObject):
        return x.gap()
    else:
        return libgap(x)

    def __init__(self, n):
        """
        Initialize ``self``.

        EXAMPLES::

            sage: G = groups.matrix.BinaryDihedral(4)
            sage: TestSuite(G).run()
        """
        self._n = n

        if n % 2 == 0:
            R = CyclotomicField(2*n)
            zeta = R.gen()
            i = R.gen()**(n//2)
        else:
            R = CyclotomicField(4*n)
            zeta = R.gen()**2
            i = R.gen()**n

        MS = MatrixSpace(R, 2)
        zero = R.zero()
        gens = [ MS([zeta, zero, zero, ~zeta]), MS([zero, i, i, zero]) ]

        from sage.libs.gap.libgap import libgap
        gap_gens = [libgap(matrix_gen) for matrix_gen in gens]
        gap_group = libgap.Group(gap_gens)

        FinitelyGeneratedMatrixGroup_gap.__init__(self, ZZ(2), R, gap_group, category=Groups().Finite())

    def induct(self, G):
        r"""
        Return the induced character.

        INPUT:

        - ``G`` -- A supergroup of the underlying group of ``self``.

        OUTPUT:

        A :class:`ClassFunction` of ``G`` defined by
        induction. Induction is the adjoint functor to restriction,
        see :meth:`restrict`.

        EXAMPLES::

            sage: G = SymmetricGroup(5)
            sage: H = G.subgroup([(1,2,3), (1,2), (4,5)])
            sage: xi = H.trivial_character(); xi
            Character of Subgroup of (Symmetric group of order 5! as a permutation group) generated by [(4,5), (1,2), (1,2,3)]
            sage: xi.induct(G)
            Character of Symmetric group of order 5! as a permutation group
            sage: xi.induct(G).values()
            [10, 4, 2, 1, 1, 0, 0]
        """
        try:
            gapG = G.gap()
        except AttributeError:
            from sage.libs.gap.libgap import libgap
            gapG = libgap(G)
        ind = self._gap_classfunction.InducedClassFunction(gapG)
        return ClassFunction(G, ind)

    def _cc_mats(self):
        r"""
        The projection given by the conjugacy class.

        This is cached to speed up the computation of the projection matrices.
        See :meth:`~flatsurf.misc.group_representation.conjugacy_class_matrix`
        for more informations.

        TESTS::

            sage: from surface_dynamics.all import *
            sage: p = iet.GeneralizedPermutation('a b b','c c a')
            sage: c = p.cover(['(1,2,3)','(1,3,2)','()'])
            sage: c._cc_mats()
            (
            [1 0 0]  [0 1 0]  [0 0 1]
            [0 1 0]  [0 0 1]  [1 0 0]
            [0 0 1], [1 0 0], [0 1 0]
            )
        """
        from surface_dynamics.misc.group_representation import conjugacy_class_matrix
        G = self.automorphism_group()
        mats = []
        for cl in libgap(G).ConjugacyClasses():
            m = conjugacy_class_matrix(cl, self._degree_cover)
            m.set_immutable()
            mats.append(m)
        return tuple(mats)

    def __init__(self, free_group, relations):
        """
        The Python constructor

        TESTS::

            sage: G = FreeGroup('a, b')
            sage: H = G / (G([1]), G([2])^3)
            sage: H
            Finitely presented group < a, b | a, b^3 >

            sage: F = FreeGroup('a, b')
            sage: J = F / (F([1]), F([2, 2, 2]))
            sage: J is H
            True

            sage: TestSuite(H).run()
            sage: TestSuite(J).run()
        """
        from sage.groups.free_group import is_FreeGroup
        assert is_FreeGroup(free_group)
        assert isinstance(relations, tuple)
        self._free_group = free_group
        self._relations = relations
        self._assign_names(free_group.variable_names())
        parent_gap = free_group.gap() / libgap([ rel.gap() for rel in relations])
        ParentLibGAP.__init__(self, parent_gap)
        Group.__init__(self)

def to_libgap(x):
    """
    Helper to convert ``x`` to a LibGAP matrix or matrix group
    element.

    Deprecated; use the ``x.gap()`` method or ``libgap(x)`` instead.

    EXAMPLES::

        sage: from sage.groups.matrix_gps.morphism import to_libgap
        sage: to_libgap(GL(2,3).gen(0))
        doctest:...: DeprecationWarning: this function is deprecated.
         Use x.gap() or libgap(x) instead.
        See https://trac.sagemath.org/25444 for details.
        [ [ Z(3), 0*Z(3) ], [ 0*Z(3), Z(3)^0 ] ]
        sage: to_libgap(matrix(QQ, [[1,2],[3,4]]))
        [ [ 1, 2 ], [ 3, 4 ] ]
    """
    from sage.misc.superseded import deprecation
    deprecation(25444, "this function is deprecated."
                " Use x.gap() or libgap(x) instead.")
    try:
        return x.gap()
    except AttributeError:
        from sage.libs.gap.libgap import libgap
        return libgap(x)

    def restrict(self, H):
        r"""
        Return the restricted character.

        INPUT:

        - ``H`` -- a subgroup of the underlying group of ``self``.

        OUTPUT:

        A :class:`ClassFunction` of ``H`` defined by restriction.

        EXAMPLES::

            sage: G = SymmetricGroup(5)
            sage: chi = ClassFunction(G, [3, -3, -1, 0, 0, -1, 3]); chi
            Character of Symmetric group of order 5! as a permutation group
            sage: H = G.subgroup([(1,2,3), (1,2), (4,5)])
            sage: chi.restrict(H)
            Character of Subgroup of (Symmetric group of order 5! as a permutation group) generated by [(4,5), (1,2), (1,2,3)]
            sage: chi.restrict(H).values()
            [3, -3, -3, -1, 0, 0]
        """
        try:
            gapH = H.gap()
        except AttributeError:
            from sage.libs.gap.libgap import libgap
            gapH = libgap(H)
        rest = self._gap_classfunction.RestrictedClassFunction(gapH)
        return ClassFunction(H, rest)

    def __init__(self, n=1, R=0):
        """
        Initialize ``self``.

        EXAMPLES::

            sage: H = groups.matrix.Heisenberg(n=2, R=5)
            sage: TestSuite(H).run()  # long time
            sage: H = groups.matrix.Heisenberg(n=2, R=4)
            sage: TestSuite(H).run()  # long time
            sage: H = groups.matrix.Heisenberg(n=3)
            sage: TestSuite(H).run(max_runs=30, skip="_test_elements")  # long time
            sage: H = groups.matrix.Heisenberg(n=2, R=GF(4))
            sage: TestSuite(H).run()  # long time
        """
        def elementary_matrix(i, j, val, MS):
            elm = copy(MS.one())
            elm[i,j] = val
            elm.set_immutable()
            return elm

        self._n = n
        self._ring = R
        # We need the generators of the ring as a commutative additive group
        if self._ring is ZZ:
            ring_gens = [self._ring.one()]
        else:
            if self._ring.cardinality() == self._ring.characteristic():
                ring_gens = [self._ring.one()]
            else:
                # This is overkill, but is the only way to ensure
                #   we get all of the elements
                ring_gens = list(self._ring)

        dim = ZZ(n + 2)
        MS = MatrixSpace(self._ring, dim)
        gens_x = [elementary_matrix(0, j, gen, MS)
                  for j in range(1, dim-1) for gen in ring_gens]
        gens_y = [elementary_matrix(i, dim-1, gen, MS)
                  for i in range(1, dim-1) for gen in ring_gens]
        gen_z = [elementary_matrix(0, dim-1, gen, MS) for gen in ring_gens]
        gens = gens_x + gens_y + gen_z

        from sage.libs.gap.libgap import libgap
        gap_gens = [libgap(single_gen) for single_gen in gens]
        gap_group = libgap.Group(gap_gens)

        cat = Groups().FinitelyGenerated()
        if self._ring in Rings().Finite():
            cat = cat.Finite()

        FinitelyGeneratedMatrixGroup_gap.__init__(self, ZZ(dim), self._ring,
                                                  gap_group, category=cat)

    def _test_structure_coeffs(self, **options):
        """
        Check the structure coefficients against the GAP implementation.

        EXAMPLES::

            sage: L = LieAlgebra(ZZ, cartan_type=['G',2])
            sage: L._test_structure_coeffs()
        """
        tester = self._tester(**options)
        ct = self.cartan_type()

        # Setup the GAP objects
        from sage.libs.gap.libgap import libgap
        L = libgap.SimpleLieAlgebra(ct.letter, ct.n, libgap(self.base_ring()))
        pos_B, neg_B, h_B = libgap.ChevalleyBasis(L)
        gap_p_roots = libgap.PositiveRoots(libgap.RootSystem(L)).sage()
        #E, F, H = libgap.CanonicalGenerators(L)

        # Setup the conversion between the Sage roots and GAP roots.
        #   The GAP roots are given in terms of the weight lattice.
        p_roots = list(ct.root_system().root_lattice().positive_roots_by_height())
        WL = ct.root_system().weight_lattice()
        La = WL.fundamental_weights()
        convert = {WL(root): root for root in p_roots}
        index = {convert[sum(c*La[j+1] for j,c in enumerate(rt))]: i
                 for i, rt in enumerate(gap_p_roots)}

        # Run the check
        basis = self.basis()
        roots = frozenset(p_roots)
        for i,x in enumerate(p_roots):
            for y in p_roots[i+1:]:
                if x + y in roots:
                    c = basis[x].bracket(basis[y]).leading_coefficient()
                    a, b = (x + y).extraspecial_pair()
                    if (x, y) == (a, b): # If it already is an extra special pair
                        tester.assertEqual(pos_B[index[x]] * pos_B[index[y]],
                                           c * pos_B[index[x+y]],
                                           "extra special pair differ for [{}, {}]".format(x, y))
                    else:
                        tester.assertEqual(pos_B[index[x]] * pos_B[index[y]],
                                           c * pos_B[index[x+y]],
                                           "incorrect structure coefficient for [{}, {}]".format(x, y))
                if x - y in roots: # This must be a negative root if it is a root
                    c = basis[x].bracket(basis[-y]).leading_coefficient()
                    tester.assertEqual(pos_B[index[x]] * neg_B[index[y]],
                                       c * neg_B[index[x-y]],
                                       "incorrect structure coefficient for [{}, {}]".format(x, y))

            def __truediv__(self, relators):
                r"""
                Return the quotient group of self by list of relations or relators

                TODO:

                - also accept list of relations as couples of elements,
                  like semigroup quotients do.

                EXAMPLES:

                We define `ZZ^2` as a quotient of the free group
                on two generators::

                    sage: from mygap import mygap
                    sage: F = mygap.FreeGroup("a", "b")
                    sage: a, b = F.group_generators()
                    sage: G = F / [ a * b * a^-1 * b^-1 ]
                    sage: G
                    <fp group of size infinity on the generators [ a, b ]>
                    sage: a, b = G.group_generators()
                    sage: a * b * a^-1 * b^-1
                    a*b*a^-1*b^-1

                Here, equality testing works well::

                    sage: a * b * a^-1 * b^-1 == G.one()
                    True

                We define a Baumslag-Solitar group::

                    sage: a, b = F.group_generators()
                    sage: G = F / [ a * b * a^-1 * b^-2 ]
                    sage: G
                    <fp group of size infinity on the generators [ a, b ]>
                    sage: a, b = G.group_generators()
                    sage: a * b * a^-1 * b^-2
                    a*b*a^-1*b^-2

                Here, equality testing starts an infinite loop where GAP is trying
                to make the rewriting system confluent (a better implementation
                would alternate between making the rewriting system more confluent
                and trying to answer the equality question -- this is a known
                limitation of GAP's implementation of the Knuth-Bendix procedure)::

                    sage: a * b * a^-1 * b^-2 == G.one() # not tested
                """
                return self._wrap( self.gap() / libgap([x.gap() for x in relators]) )

def to_libgap(x):
    """
    Helper to convert ``x`` to a LibGAP matrix or matrix group
    element.

    EXAMPLES::

        sage: from sage.groups.matrix_gps.morphism import to_libgap
        sage: to_libgap(GL(2,3).gen(0))
        [ [ Z(3), 0*Z(3) ], [ 0*Z(3), Z(3)^0 ] ]
        sage: to_libgap(matrix(QQ, [[1,2],[3,4]]))
        [ [ 1, 2 ], [ 3, 4 ] ]
    """
    try:
        return x.gap()
    except AttributeError:
        from sage.libs.gap.libgap import libgap
        return libgap(x)

    def norm_of_galois_extension(self):
        r"""
        Returns the norm as a Galois extension of `\QQ`, which is
        given by the product of all galois_conjugates.

        EXAMPLES::

            sage: E(3).norm_of_galois_extension()
            1
            sage: E(6).norm_of_galois_extension()
            1
            sage: (E(2) + E(3)).norm_of_galois_extension()
            3
            sage: parent(_)
            Integer Ring
        """
        obj = self._obj
        k = obj.Conductor().sage()
        return libgap.Product(libgap([obj.GaloisCyc(i) for i in range(k) if k.gcd(i) == 1])).sage()

    def __init__(self, parent, M, check=True, convert=True):
        r"""
        Element of a matrix group over a generic ring.

        The group elements are implemented as Sage matrices.

        INPUT:

        - ``M`` -- a matrix.

        - ``parent`` -- the parent.

        - ``check`` -- bool (default: ``True``). If true does some
          type checking.

        - ``convert`` -- bool (default: ``True``). If true convert
          ``M`` to the right matrix space.

        TESTS::

            sage: MS = MatrixSpace(GF(3),2,2)
            sage: G = MatrixGroup(MS([[1,0],[0,1]]), MS([[1,1],[0,1]]))
            sage: G.gen(0)
            [1 0]
            [0 1]
            sage: g = G.random_element()
            sage: TestSuite(g).run()
        """
        if isinstance(M, GapElement):
            ElementLibGAP.__init__(self, parent, M)
            return
        if convert:
            M = parent.matrix_space()(M)
        from sage.libs.gap.libgap import libgap

        M_gap = libgap(M)
        if check:
            if not is_Matrix(M):
                raise TypeError("M must be a matrix")
            if M.parent() is not parent.matrix_space():
                raise TypeError("M must be a in the matrix space of the group")
            parent._check_matrix(M, M_gap)
        ElementLibGAP.__init__(self, parent, M_gap)

    def __init__(self, degree, base_ring,
                 gens, invariant_bilinear_form,
                 category=None, check=True,
                 invariant_submodule=None,
                 invariant_quotient_module=None):
        r"""
        Create this orthogonal group from the input.

        TESTS::

            sage: from sage.groups.matrix_gps.isometries import GroupOfIsometries
            sage: bil = Matrix(ZZ,2,[3,2,2,3])
            sage: gens = [-Matrix(ZZ,2,[0,1,1,0])]
            sage: cat = Groups().Finite()
            sage: O = GroupOfIsometries(2, ZZ, gens, bil, category=cat)
            sage: TestSuite(O).run()
        """
        from copy import copy
        G = copy(invariant_bilinear_form)
        G.set_immutable()
        self._invariant_bilinear_form = G
        self._invariant_submodule = invariant_submodule
        self._invariant_quotient_module = invariant_quotient_module
        if check:
            I = invariant_submodule
            Q = invariant_quotient_module
            for f in gens:
                self._check_matrix(f)
                if (not I is None) and I*f != I:
                    raise ValueError("the submodule is not preserved")
                if not Q is None and (Q.W() != Q.W()*f or Q.V()*f != Q.V()):
                    raise ValueError("the quotient module is not preserved")
        if len(gens) == 0:    # handle the trivial group
            gens = [G.parent().identity_matrix()]
        from sage.libs.gap.libgap import libgap
        gap_gens = [libgap(matrix_gen) for matrix_gen in gens]
        gap_group = libgap.Group(gap_gens)
        FinitelyGeneratedMatrixGroup_gap.__init__(self,
                                                  degree,
                                                  base_ring,
                                                  gap_group,
                                                  category=category)

def real_characters(G):
    r"""
    Return a pair ``(table of characters, character degrees)`` for the
    group ``G``.

    OUPUT:

    - table of characters - a list of characters. Each character is represented
      as the list of its values on conjugacy classes. The order of conjugacy
      classes is the same as the one returned by GAP.

    - degrees - the list of degrees of the characters

    EXAMPLES::

        sage: from surface_dynamics.misc.group_representation import real_characters
        sage: T, deg = real_characters(AlternatingGroup(5))
        sage: T
        [(1, 1, 1, 1, 1),
         (3, -1, 0, -E(5) - E(5)^4, -E(5)^2 - E(5)^3),
         (3, -1, 0, -E(5)^2 - E(5)^3, -E(5) - E(5)^4),
         (4, 0, 1, -1, -1),
         (5, 1, -1, 0, 0)]
        sage: set(parent(x) for chi in T for x in chi)
        {Universal Cyclotomic Field}
        sage: deg
        [1, 3, 3, 4, 5]

        sage: T, deg = real_characters(CyclicPermutationGroup(6))
        sage: T
        [(1, 1, 1, 1, 1, 1),
         (1, -1, 1, -1, 1, -1),
         (2, -1, -1, 2, -1, -1),
         (2, 1, -1, -2, -1, 1)]
        sage: deg
        [1, 1, 1, 1]
    """
    from sage.rings.universal_cyclotomic_field import UniversalCyclotomicField

    G = libgap(G)
    UCF = UniversalCyclotomicField()
    n = G.ConjugacyClasses().Length()
    Tgap = G.CharacterTable().Irr()
    degrees = [chi.Degree().sage() for chi in Tgap]
    Tgap = [tuple(UCF(chi[j]) for j in xrange(n)) for chi in Tgap]

    real_T = []
    real_degrees = []
    seen = set()
    for i,chi in enumerate(Tgap):
        if chi in seen:
            continue

        real_degrees.append(degrees[i])
        if all(x.is_real() for x in chi):
            real_T.append(chi)
            seen.add(chi)
        else:
            seen.add(chi)
            chi_bar = tuple(z.conjugate() for z in chi)
            seen.add(chi_bar)
            real_T.append(tuple(chi[j] + chi[j].conjugate() for j in xrange(n)))

    return (real_T, real_degrees)

 def __call__(self, *args):
     return GAP(libgap(*args))

    def _element_constructor_(self, elt):
        r"""
        TESTS::

            sage: UCF = UniversalCyclotomicField()
            sage: UCF(3)
            3
            sage: UCF(3/2)
            3/2

            sage: C = CyclotomicField(13)
            sage: UCF(C.gen())
            E(13)
            sage: UCF(C.gen() - 3*C.gen()**2 + 5*C.gen()**5)
            E(13) - 3*E(13)^2 + 5*E(13)^5

            sage: C = CyclotomicField(12)
            sage: zeta12 = C.gen()
            sage: a = UCF(zeta12 - 3* zeta12**2)
            sage: a
            -E(12)^7 + 3*E(12)^8
            sage: C(_) == a
            True

            sage: UCF('[[0, 1], [0, 2]]')
            Traceback (most recent call last):
            ...
            TypeError: [ [ 0, 1 ], [ 0, 2 ] ] of type <type
            'sage.libs.gap.element.GapElement_List'> not valid to initialize an
            element of the universal cyclotomic field

        .. TODO::

            Implement conversion from QQbar (and as a consequence from the
            symbolic ring)
        """
        elt = py_scalar_to_element(elt)

        if isinstance(elt, (Integer, Rational)):
            return self.element_class(self, libgap(elt))
        elif isinstance(elt, (GapElement_Integer, GapElement_Rational, GapElement_Cyclotomic)):
            return self.element_class(self, elt)
        elif not elt:
            return self.zero()

        obj = None
        if isinstance(elt, gap.GapElement):
            obj = libgap(elt)
        elif isinstance(elt, gap3.GAP3Element):
            obj = libgap.eval(str(elt))
        elif isinstance(elt, str):
            obj = libgap.eval(elt)
        if obj is not None:
            if not isinstance(obj, (GapElement_Integer, GapElement_Rational, GapElement_Cyclotomic)):
                raise TypeError("{} of type {} not valid to initialize an element of the universal cyclotomic field".format(obj, type(obj)))
            return self.element_class(self, obj)

        # late import to avoid slowing down the above conversions
        from sage.rings.number_field.number_field_element import NumberFieldElement
        from sage.rings.number_field.number_field import NumberField_cyclotomic, CyclotomicField
        P = parent(elt)
        if isinstance(elt, NumberFieldElement) and isinstance(P, NumberField_cyclotomic):
            n = P.gen().multiplicative_order()
            elt = CyclotomicField(n)(elt)
            coeffs = elt._coefficients()
            return sum(c * self.gen(n,i) for i,c in enumerate(elt._coefficients()))
        else:
            raise TypeError("{} of type {} not valid to initialize an element of the universal cyclotomic field".format(elt, type(elt)))

def MatrixGroup(*gens, **kwds):
    r"""
    Return the matrix group with given generators.

    INPUT:

    - ``*gens`` -- matrices, or a single list/tuple/iterable of
      matrices, or a matrix group.

    - ``check`` -- boolean keyword argument (optional, default:
      ``True``). Whether to check that each matrix is invertible.

    EXAMPLES::

        sage: F = GF(5)
        sage: gens = [matrix(F,2,[1,2, -1, 1]), matrix(F,2, [1,1, 0,1])]
        sage: G = MatrixGroup(gens); G
        Matrix group over Finite Field of size 5 with 2 generators (
        [1 2]  [1 1]
        [4 1], [0 1]
        )

    In the second example, the generators are a matrix over
    `\ZZ`, a matrix over a finite field, and the integer
    `2`. Sage determines that they both canonically map to
    matrices over the finite field, so creates that matrix group
    there::

        sage: gens = [matrix(2,[1,2, -1, 1]), matrix(GF(7), 2, [1,1, 0,1]), 2]
        sage: G = MatrixGroup(gens); G
        Matrix group over Finite Field of size 7 with 3 generators (
        [1 2]  [1 1]  [2 0]
        [6 1], [0 1], [0 2]
        )

    Each generator must be invertible::

        sage: G = MatrixGroup([matrix(ZZ,2,[1,2,3,4])])
        Traceback (most recent call last):
        ...
        ValueError: each generator must be an invertible matrix

        sage: F = GF(5); MS = MatrixSpace(F,2,2)
        sage: MatrixGroup([MS.0])
        Traceback (most recent call last):
        ...
        ValueError: each generator must be an invertible matrix
        sage: MatrixGroup([MS.0], check=False)  # works formally but is mathematical nonsense
        Matrix group over Finite Field of size 5 with 1 generators (
        [1 0]
        [0 0]
        )

    Some groups are not supported, or do not have much functionality
    implemented::

        sage: G = SL(0, QQ)
        Traceback (most recent call last):
        ...
        ValueError: the degree must be at least 1

        sage: SL2C = SL(2, CC);  SL2C
        Special Linear Group of degree 2 over Complex Field with 53 bits of precision
        sage: SL2C.gens()
        Traceback (most recent call last):
        ...
        AttributeError: 'LinearMatrixGroup_generic_with_category' object has no attribute 'gens'
    """
    if isinstance(gens[-1], dict):   # hack for unpickling
        kwds.update(gens[-1])
        gens = gens[:-1]
    check = kwds.get('check', True)
    if len(gens) == 1:
        if isinstance(gens[0], (list, tuple)):
            gens = list(gens[0])
        else:
            try:
                gens = [g.matrix() for g in gens[0]]
            except AttributeError:
                pass
    if len(gens) == 0:
        raise ValueError('need at least one generator')
    gens = normalize_square_matrices(gens)
    if check and any(not g.is_invertible() for g in gens):
        raise ValueError('each generator must be an invertible matrix')
    MS = gens.universe()
    base_ring = MS.base_ring()
    degree = ZZ(MS.ncols())   # == MS.nrows()
    from sage.libs.gap.libgap import libgap
    try:
        gap_gens = [libgap(matrix_gen) for matrix_gen in gens]
        gap_group = libgap.Group(gap_gens)
        return FinitelyGeneratedMatrixGroup_gap(degree, base_ring, gap_group)
    except (TypeError, ValueError):
        return FinitelyGeneratedMatrixGroup_generic(degree, base_ring, gens)

def isotypic_projection_matrix(G, d, chi, deg, conj_mats=None):
    r"""
    Return an isotypic projection matrix

    INPUT:

    - ``G`` -- a permutation group

    - ``d`` -- (integer) the domain of the group is `\{1, 2, \ldots, d\}`

    - ``chi`` -- (tuple) real or complex character

    - ``deg`` -- (integer) degree of the character

    Recall the formula for the projection as given in Theorem 8 in [Ser]_. If
    `G` is a permutation group, then
    
    .. MATH::
    
        \pi_\chi = \sum_{g \in G} \overline_{\chi(g)} g

    REFERENCES::

    .. [Ser] J.-P. Serre, "Représentation des groupes finis."

    EXAMPLES::

        sage: from surface_dynamics.misc.group_representation import real_characters, isotypic_projection_matrix
        sage: G = AlternatingGroup(5)
        sage: T,deg = real_characters(G)
        sage: isotypic_projection_matrix(G, 5, T[0], deg[0])
        [1/5 1/5 1/5 1/5 1/5]
        [1/5 1/5 1/5 1/5 1/5]
        [1/5 1/5 1/5 1/5 1/5]
        [1/5 1/5 1/5 1/5 1/5]
        [1/5 1/5 1/5 1/5 1/5]
        sage: isotypic_projection_matrix(G, 5, T[1], deg[1])
        [0 0 0 0 0]
        [0 0 0 0 0]
        [0 0 0 0 0]
        [0 0 0 0 0]
        [0 0 0 0 0]
        sage: isotypic_projection_matrix(G, 5, T[2], deg[2])
        [0 0 0 0 0]
        [0 0 0 0 0]
        [0 0 0 0 0]
        [0 0 0 0 0]
        [0 0 0 0 0]
        sage: isotypic_projection_matrix(G, 5, T[3], deg[3])
        [ 4/5 -1/5 -1/5 -1/5 -1/5]
        [-1/5  4/5 -1/5 -1/5 -1/5]
        [-1/5 -1/5  4/5 -1/5 -1/5]
        [-1/5 -1/5 -1/5  4/5 -1/5]
        [-1/5 -1/5 -1/5 -1/5  4/5]
        sage: isotypic_projection_matrix(G, 5, T[4], deg[4])
        [0 0 0 0 0]
        [0 0 0 0 0]
        [0 0 0 0 0]
        [0 0 0 0 0]
        [0 0 0 0 0]

        sage: sum(isotypic_projection_matrix(G, 5, T[i], deg[i]) for i in range(5)).is_one()
        True
    """
    from sage.matrix.special import zero_matrix
    res = zero_matrix(d)

    Ggap = libgap(G)

    for t,cl in enumerate(Ggap.ConjugacyClasses()):
        if conj_mats is None:
            m = conjugacy_class_matrix(cl, d)
        else:
            m = conj_mats[t]
        res += chi[t] * conjugacy_class_matrix(cl,d)

    return deg / G.cardinality() * res