-- Copyright (c) 2010-2012, David Amos. All rights reserved. {-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, TypeSynonymInstances #-} -- ScopedTypeVariables -- |A module for doing arithmetic in the group algebra. -- -- Group elements are represented as permutations of the integers, and are entered and displayed -- using a Haskell-friendly version of cycle notation. For example, the permutation (1 2 3)(4 5) -- would be entered as @p [[1,2,3],[4,5]]@, and displayed as [[1,2,3],[4,5]]. -- -- Given a field K and group G, the group algebra KG is the free K-vector space over the elements of G. -- Elements of the group algebra consists of arbitrary K-linear combinations of elements of G. -- For example, @p [[1,2,3]] + 2 * p [[1,2],[3,4]]@ module Math.Algebras.GroupAlgebra where import Math.Core.Field import Math.Core.Utils import Math.Algebras.VectorSpace import Math.Algebras.TensorProduct import Math.Algebras.Structures import Math.Algebra.Group.PermutationGroup hiding (p, action) import qualified Math.Algebra.Group.PermutationGroup as P import Math.Algebra.LinearAlgebra hiding (inverse, (*>) ) import Math.CommutativeAlgebra.Polynomial import Math.CommutativeAlgebra.GroebnerBasis instance Mon (Permutation Int) where munit = 1 mmult = (*) type GroupAlgebra k = Vect k (Permutation Int) -- Monoid Algebra instance instance (Eq k, Num k) => Algebra k (Permutation Int) where unit 0 = zero -- V [] unit x = V [(munit,x)] mult = nf . fmap (\(a,b) -> a `mmult` b) -- Set Coalgebra instance -- instance SetCoalgebra (Permutation Int) where {} instance (Eq k, Num k) => Coalgebra k (Permutation Int) where counit (V ts) = sum [x | (m,x) <- ts] -- trace comult = fmap (\m -> (m,m)) -- diagonal instance (Eq k, Num k) => Bialgebra k (Permutation Int) where {} -- should check that the algebra and coalgebra structures are compatible instance (Eq k, Num k) => HopfAlgebra k (Permutation Int) where antipode (V ts) = nf $ V [(g^-1,x) | (g,x) <- ts] -- |Construct a permutation, as an element of the group algebra, from a list of cycles. -- For example, @p [[1,2],[3,4,5]]@ constructs the permutation (1 2)(3 4 5), which is displayed -- as [[1,2],[3,4,5]]. p :: [[Int]] -> GroupAlgebra Q p cs = return $ P.p cs instance (Eq k, Num k) => Module k (Permutation Int) Int where action = nf . fmap (\(g,x) -> x .^ g) -- use *. instead -- r *> m = action (r `te` m) newtype X a = X a deriving (Eq,Ord,Show) -- Find the inverse of a group algebra element using Groebner basis techniques -- This is overkill, but it was what I had to hand at first inv x@(V ts) = let gs = P.elts $ map fst $ terms x -- all elements in the group generated by the terms cs = map (glexvar . X) gs x' = V $ map (\(g,c) -> (g, unit c)) ts one = x' * (V $ zip gs cs) oneEquations = (coeff 1 one - 1) : [coeff g one - 0 | g <- tail gs] zeroEquations = [coeff g one - 0 | g <- gs] solution = gb oneEquations in if solution == [1] then Left (gb zeroEquations) -- it's a zero divisor else Right solution -- sum [-c *> p g | V [ (Glex (M 1 [(X g, 1)]), 1), (Glex (M 0 []), c) ] <- solution] -- should extract the solution into a group algebra element, but having trouble getting types right -- The following code can be made to work over an arbitrary field by uncommenting the commented code -- However, we should then probably also change the signature of p to p :: Fractional k => [[Int]] -> GroupAlgebra k -- instance Fractional k => HasInverses (GroupAlgebra k) where -- |Note that the inverse of a group algebra element can only be efficiently calculated -- if the group generated by the non-zero terms is very small (eg \<100 elements). instance HasInverses (GroupAlgebra Q) where inverse x@(V ts) = let gs = P.elts $ map fst $ terms x -- all elements in the group generated by the terms -- cs = map (var . X) gs :: [Vect k (Glex (X (Permutation Int)))] cs = map (glexvar . X) gs x' = V $ map (\(g,c) -> (g, unit c)) ts one = x' * (V $ zip gs cs) m = [ [coeff (mvar (X j)) c | j <- gs] | i <- gs, let c = coeff i one] b = 1 : replicate (length gs - 1) 0 in case solveLinearSystem m b of Just v -> nf $ V $ zip gs v Nothing -> error "GroupAlgebra.inverse: not invertible" maybeInverse x@(V ts) = let gs = P.elts $ map fst $ terms x -- all elements in the group generated by the terms cs = map (glexvar . X) gs x' = V $ map (\(g,c) -> (g, unit c)) ts one = x' * (V $ zip gs cs) m = [ [coeff (mvar (X j)) c | j <- gs] | i <- gs, let c = coeff i one] b = 1 : replicate (length gs - 1) 0 in fmap (\v -> nf $ V $ zip gs v) (solveLinearSystem m b) {- in case solveLinearSystem m b of Just v -> Just $ nf $ V $ zip gs v Nothing -> Nothing -}