-- Copyright (c) 2010-2015, David Amos. All rights reserved.

{-# LANGUAGE  MultiParamTypeClasses, FlexibleInstances, FlexibleContexts, 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 consist 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 (GroupAlgebra, p) where

import Prelude hiding ( (*>) )

import Math.Core.Field
import Math.Core.Utils hiding (elts)

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 (solveLinearSystem) -- hiding (inverse, (*>) )

import Math.CommutativeAlgebra.Polynomial
import Math.CommutativeAlgebra.GroebnerBasis


type GroupAlgebra k = Vect k (Permutation Int)

instance (Eq k, Num k) => Algebra k (Permutation Int) where
    unit :: k -> Vect k (Permutation Int)
unit x :: k
x = k
x k -> Vect k (Permutation Int) -> Vect k (Permutation Int)
forall k b. (Eq k, Num k) => k -> Vect k b -> Vect k b
*> Permutation Int -> Vect k (Permutation Int)
forall (m :: * -> *) a. Monad m => a -> m a
return 1
    mult :: Vect k (Tensor (Permutation Int) (Permutation Int))
-> Vect k (Permutation Int)
mult = Vect k (Permutation Int) -> Vect k (Permutation Int)
forall k b. (Eq k, Num k, Ord b) => Vect k b -> Vect k b
nf (Vect k (Permutation Int) -> Vect k (Permutation Int))
-> (Vect k (Tensor (Permutation Int) (Permutation Int))
    -> Vect k (Permutation Int))
-> Vect k (Tensor (Permutation Int) (Permutation Int))
-> Vect k (Permutation Int)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Tensor (Permutation Int) (Permutation Int) -> Permutation Int)
-> Vect k (Tensor (Permutation Int) (Permutation Int))
-> Vect k (Permutation Int)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\(g :: Permutation Int
g,h :: Permutation Int
h) -> Permutation Int
gPermutation Int -> Permutation Int -> Permutation Int
forall a. Num a => a -> a -> a
*Permutation Int
h)

{-
instance Mon (Permutation Int) where
    munit = 1
    mmult = (*)

-- Monoid Algebra instance
instance (Eq k, Num k) => Algebra k (Permutation Int) where
    unit x = x *> return munit
    mult = nf . fmap (\(g,h) -> g `mmult` h)
-}

-- Set Coalgebra instance
-- instance SetCoalgebra (Permutation Int) where {}

instance (Eq k, Num k) => Coalgebra k (Permutation Int) where
    -- counit (V ts) = sum [x | (g,x) <- ts] -- trace
    counit :: Vect k (Permutation Int) -> k
counit = Vect k () -> k
forall k. Num k => Vect k () -> k
unwrap (Vect k () -> k)
-> (Vect k (Permutation Int) -> Vect k ())
-> Vect k (Permutation Int)
-> k
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Permutation Int -> Vect k ())
-> Vect k (Permutation Int) -> Vect k ()
forall k b a.
(Eq k, Num k, Ord b) =>
(a -> Vect k b) -> Vect k a -> Vect k b
linear Permutation Int -> Vect k ()
forall p p. Num p => p -> p
counit' where counit' :: p -> p
counit' g :: p
g = 1 -- trace
    comult :: Vect k (Permutation Int)
-> Vect k (Tensor (Permutation Int) (Permutation Int))
comult = (Permutation Int -> Tensor (Permutation Int) (Permutation Int))
-> Vect k (Permutation Int)
-> Vect k (Tensor (Permutation Int) (Permutation Int))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\g :: Permutation Int
g -> (Permutation Int
g,Permutation Int
g))                          -- 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 :: Vect k (Permutation Int) -> Vect k (Permutation Int)
antipode = Vect k (Permutation Int) -> Vect k (Permutation Int)
forall k b. (Eq k, Num k, Ord b) => Vect k b -> Vect k b
nf (Vect k (Permutation Int) -> Vect k (Permutation Int))
-> (Vect k (Permutation Int) -> Vect k (Permutation Int))
-> Vect k (Permutation Int)
-> Vect k (Permutation Int)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Permutation Int -> Permutation Int)
-> Vect k (Permutation Int) -> Vect k (Permutation Int)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Permutation Int -> Permutation Int
forall a. HasInverses a => a -> a
inverse
    -- 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 :: [[Int]] -> GroupAlgebra Q
p = Permutation Int -> GroupAlgebra Q
forall (m :: * -> *) a. Monad m => a -> m a
return (Permutation Int -> GroupAlgebra Q)
-> ([[Int]] -> Permutation Int) -> [[Int]] -> GroupAlgebra Q
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [[Int]] -> Permutation Int
forall a. Ord a => [[a]] -> Permutation a
fromCycles


instance (Eq k, Num k) => Module k (Permutation Int) Int where
    action :: Vect k (Tensor (Permutation Int) Int) -> Vect k Int
action = Vect k Int -> Vect k Int
forall k b. (Eq k, Num k, Ord b) => Vect k b -> Vect k b
nf (Vect k Int -> Vect k Int)
-> (Vect k (Tensor (Permutation Int) Int) -> Vect k Int)
-> Vect k (Tensor (Permutation Int) Int)
-> Vect k Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Tensor (Permutation Int) Int -> Int)
-> Vect k (Tensor (Permutation Int) Int) -> Vect k Int
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\(g :: Permutation Int
g,x :: Int
x) -> Int
x Int -> Permutation Int -> Int
forall a. Ord a => a -> Permutation a -> a
.^ Permutation Int
g)

instance (Eq k, Num k) => Module k (Permutation Int) [Int] where
    action :: Vect k (Tensor (Permutation Int) [Int]) -> Vect k [Int]
action = Vect k [Int] -> Vect k [Int]
forall k b. (Eq k, Num k, Ord b) => Vect k b -> Vect k b
nf (Vect k [Int] -> Vect k [Int])
-> (Vect k (Tensor (Permutation Int) [Int]) -> Vect k [Int])
-> Vect k (Tensor (Permutation Int) [Int])
-> Vect k [Int]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Tensor (Permutation Int) [Int] -> [Int])
-> Vect k (Tensor (Permutation Int) [Int]) -> Vect k [Int]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\(g :: Permutation Int
g,xs :: [Int]
xs) -> [Int]
xs [Int] -> Permutation Int -> [Int]
forall a. Ord a => [a] -> Permutation a -> [a]
-^ Permutation Int
g)

-- use *. instead
-- r *> m = action (r `te` m)

newtype X a = X a deriving (X a -> X a -> Bool
(X a -> X a -> Bool) -> (X a -> X a -> Bool) -> Eq (X a)
forall a. Eq a => X a -> X a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: X a -> X a -> Bool
$c/= :: forall a. Eq a => X a -> X a -> Bool
== :: X a -> X a -> Bool
$c== :: forall a. Eq a => X a -> X a -> Bool
Eq,Eq (X a)
Eq (X a) =>
(X a -> X a -> Ordering)
-> (X a -> X a -> Bool)
-> (X a -> X a -> Bool)
-> (X a -> X a -> Bool)
-> (X a -> X a -> Bool)
-> (X a -> X a -> X a)
-> (X a -> X a -> X a)
-> Ord (X a)
X a -> X a -> Bool
X a -> X a -> Ordering
X a -> X a -> X a
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall a. Ord a => Eq (X a)
forall a. Ord a => X a -> X a -> Bool
forall a. Ord a => X a -> X a -> Ordering
forall a. Ord a => X a -> X a -> X a
min :: X a -> X a -> X a
$cmin :: forall a. Ord a => X a -> X a -> X a
max :: X a -> X a -> X a
$cmax :: forall a. Ord a => X a -> X a -> X a
>= :: X a -> X a -> Bool
$c>= :: forall a. Ord a => X a -> X a -> Bool
> :: X a -> X a -> Bool
$c> :: forall a. Ord a => X a -> X a -> Bool
<= :: X a -> X a -> Bool
$c<= :: forall a. Ord a => X a -> X a -> Bool
< :: X a -> X a -> Bool
$c< :: forall a. Ord a => X a -> X a -> Bool
compare :: X a -> X a -> Ordering
$ccompare :: forall a. Ord a => X a -> X a -> Ordering
$cp1Ord :: forall a. Ord a => Eq (X a)
Ord,Int -> X a -> ShowS
[X a] -> ShowS
X a -> String
(Int -> X a -> ShowS)
-> (X a -> String) -> ([X a] -> ShowS) -> Show (X a)
forall a. Show a => Int -> X a -> ShowS
forall a. Show a => [X a] -> ShowS
forall a. Show a => X a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [X a] -> ShowS
$cshowList :: forall a. Show a => [X a] -> ShowS
show :: X a -> String
$cshow :: forall a. Show a => X a -> String
showsPrec :: Int -> X a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> X a -> ShowS
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 :: Vect Q b -> Either [Vect Q (Glex (X b))] [Vect Q (Glex (X b))]
inv x :: Vect Q b
x@(V ts :: [(b, Q)]
ts) =
    let gs :: [b]
gs = [b] -> [b]
forall a. (Num a, Ord a) => [a] -> [a]
elts ([b] -> [b]) -> [b] -> [b]
forall a b. (a -> b) -> a -> b
$ ((b, Q) -> b) -> [(b, Q)] -> [b]
forall a b. (a -> b) -> [a] -> [b]
map (b, Q) -> b
forall a b. (a, b) -> a
fst ([(b, Q)] -> [b]) -> [(b, Q)] -> [b]
forall a b. (a -> b) -> a -> b
$ Vect Q b -> [(b, Q)]
forall k b. Vect k b -> [(b, k)]
terms Vect Q b
x -- all elements in the group generated by the terms
        cs :: [Vect Q (Glex (X b))]
cs = (b -> Vect Q (Glex (X b))) -> [b] -> [Vect Q (Glex (X b))]
forall a b. (a -> b) -> [a] -> [b]
map (X b -> Vect Q (Glex (X b))
forall v. v -> GlexPoly Q v
glexvar (X b -> Vect Q (Glex (X b)))
-> (b -> X b) -> b -> Vect Q (Glex (X b))
forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> X b
forall a. a -> X a
X) [b]
gs
        x' :: Vect (Vect Q (Glex (X b))) b
x' = [(b, Vect Q (Glex (X b)))] -> Vect (Vect Q (Glex (X b))) b
forall k b. [(b, k)] -> Vect k b
V ([(b, Vect Q (Glex (X b)))] -> Vect (Vect Q (Glex (X b))) b)
-> [(b, Vect Q (Glex (X b)))] -> Vect (Vect Q (Glex (X b))) b
forall a b. (a -> b) -> a -> b
$ ((b, Q) -> (b, Vect Q (Glex (X b))))
-> [(b, Q)] -> [(b, Vect Q (Glex (X b)))]
forall a b. (a -> b) -> [a] -> [b]
map (\(g :: b
g,c :: Q
c) -> (b
g, Q -> Vect Q (Glex (X b))
forall k b. Algebra k b => k -> Vect k b
unit Q
c)) [(b, Q)]
ts
        one :: Vect (Vect Q (Glex (X b))) b
one = Vect (Vect Q (Glex (X b))) b
x' Vect (Vect Q (Glex (X b))) b
-> Vect (Vect Q (Glex (X b))) b -> Vect (Vect Q (Glex (X b))) b
forall a. Num a => a -> a -> a
* ([(b, Vect Q (Glex (X b)))] -> Vect (Vect Q (Glex (X b))) b
forall k b. [(b, k)] -> Vect k b
V ([(b, Vect Q (Glex (X b)))] -> Vect (Vect Q (Glex (X b))) b)
-> [(b, Vect Q (Glex (X b)))] -> Vect (Vect Q (Glex (X b))) b
forall a b. (a -> b) -> a -> b
$ [b] -> [Vect Q (Glex (X b))] -> [(b, Vect Q (Glex (X b)))]
forall a b. [a] -> [b] -> [(a, b)]
zip [b]
gs [Vect Q (Glex (X b))]
cs)
        oneEquations :: [Vect Q (Glex (X b))]
oneEquations = (b -> Vect (Vect Q (Glex (X b))) b -> Vect Q (Glex (X b))
forall k b. (Num k, Eq b) => b -> Vect k b -> k
coeff 1 Vect (Vect Q (Glex (X b))) b
one Vect Q (Glex (X b)) -> Vect Q (Glex (X b)) -> Vect Q (Glex (X b))
forall a. Num a => a -> a -> a
- 1) Vect Q (Glex (X b))
-> [Vect Q (Glex (X b))] -> [Vect Q (Glex (X b))]
forall a. a -> [a] -> [a]
: [b -> Vect (Vect Q (Glex (X b))) b -> Vect Q (Glex (X b))
forall k b. (Num k, Eq b) => b -> Vect k b -> k
coeff b
g Vect (Vect Q (Glex (X b))) b
one Vect Q (Glex (X b)) -> Vect Q (Glex (X b)) -> Vect Q (Glex (X b))
forall a. Num a => a -> a -> a
- 0 | b
g <- [b] -> [b]
forall a. [a] -> [a]
tail [b]
gs]
        zeroEquations :: [Vect Q (Glex (X b))]
zeroEquations = [b -> Vect (Vect Q (Glex (X b))) b -> Vect Q (Glex (X b))
forall k b. (Num k, Eq b) => b -> Vect k b -> k
coeff b
g Vect (Vect Q (Glex (X b))) b
one Vect Q (Glex (X b)) -> Vect Q (Glex (X b)) -> Vect Q (Glex (X b))
forall a. Num a => a -> a -> a
- 0 | b
g <- [b]
gs]
        solution :: [Vect Q (Glex (X b))]
solution = [Vect Q (Glex (X b))] -> [Vect Q (Glex (X b))]
forall k m.
(Fractional k, Ord k, Monomial m, Ord m, Algebra k m) =>
[Vect k m] -> [Vect k m]
gb [Vect Q (Glex (X b))]
oneEquations
    in if [Vect Q (Glex (X b))]
solution [Vect Q (Glex (X b))] -> [Vect Q (Glex (X b))] -> Bool
forall a. Eq a => a -> a -> Bool
== [1]
       then [Vect Q (Glex (X b))]
-> Either [Vect Q (Glex (X b))] [Vect Q (Glex (X b))]
forall a b. a -> Either a b
Left ([Vect Q (Glex (X b))] -> [Vect Q (Glex (X b))]
forall k m.
(Fractional k, Ord k, Monomial m, Ord m, Algebra k m) =>
[Vect k m] -> [Vect k m]
gb [Vect Q (Glex (X b))]
zeroEquations) -- it's a zero divisor
       else [Vect Q (Glex (X b))]
-> Either [Vect Q (Glex (X b))] [Vect Q (Glex (X b))]
forall a b. b -> Either a b
Right [Vect Q (Glex (X b))]
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 using ScopedTypeVariables and var instead of glexvar.
-- However, we should then probably also change the signature of p to p :: Fractional k => [[Int]] -> GroupAlgebra k

-- |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 :: GroupAlgebra Q -> GroupAlgebra Q
inverse x :: GroupAlgebra Q
x@(V ts :: [(Permutation Int, Q)]
ts) =
        let gs :: [Permutation Int]
gs = [Permutation Int] -> [Permutation Int]
forall a. (Num a, Ord a) => [a] -> [a]
elts ([Permutation Int] -> [Permutation Int])
-> [Permutation Int] -> [Permutation Int]
forall a b. (a -> b) -> a -> b
$ ((Permutation Int, Q) -> Permutation Int)
-> [(Permutation Int, Q)] -> [Permutation Int]
forall a b. (a -> b) -> [a] -> [b]
map (Permutation Int, Q) -> Permutation Int
forall a b. (a, b) -> a
fst [(Permutation Int, Q)]
ts -- all elements in the group generated by the terms
            n :: Int
n = [Permutation Int] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [Permutation Int]
gs
            y :: Vect (GlexPoly Q (X Int)) (Permutation Int)
y = [(Permutation Int, GlexPoly Q (X Int))]
-> Vect (GlexPoly Q (X Int)) (Permutation Int)
forall k b. [(b, k)] -> Vect k b
V ([(Permutation Int, GlexPoly Q (X Int))]
 -> Vect (GlexPoly Q (X Int)) (Permutation Int))
-> [(Permutation Int, GlexPoly Q (X Int))]
-> Vect (GlexPoly Q (X Int)) (Permutation Int)
forall a b. (a -> b) -> a -> b
$ [Permutation Int]
-> [GlexPoly Q (X Int)] -> [(Permutation Int, GlexPoly Q (X Int))]
forall a b. [a] -> [b] -> [(a, b)]
zip [Permutation Int]
gs ([GlexPoly Q (X Int)] -> [(Permutation Int, GlexPoly Q (X Int))])
-> [GlexPoly Q (X Int)] -> [(Permutation Int, GlexPoly Q (X Int))]
forall a b. (a -> b) -> a -> b
$ (Int -> GlexPoly Q (X Int)) -> [Int] -> [GlexPoly Q (X Int)]
forall a b. (a -> b) -> [a] -> [b]
map (X Int -> GlexPoly Q (X Int)
forall v. v -> GlexPoly Q v
glexvar (X Int -> GlexPoly Q (X Int))
-> (Int -> X Int) -> Int -> GlexPoly Q (X Int)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> X Int
forall a. a -> X a
X) [1..Int
n] -- x1*1+x2*g2+...+xn*gn
            x' :: Vect (GlexPoly Q (X Int)) (Permutation Int)
x' = [(Permutation Int, GlexPoly Q (X Int))]
-> Vect (GlexPoly Q (X Int)) (Permutation Int)
forall k b. [(b, k)] -> Vect k b
V ([(Permutation Int, GlexPoly Q (X Int))]
 -> Vect (GlexPoly Q (X Int)) (Permutation Int))
-> [(Permutation Int, GlexPoly Q (X Int))]
-> Vect (GlexPoly Q (X Int)) (Permutation Int)
forall a b. (a -> b) -> a -> b
$ ((Permutation Int, Q) -> (Permutation Int, GlexPoly Q (X Int)))
-> [(Permutation Int, Q)]
-> [(Permutation Int, GlexPoly Q (X Int))]
forall a b. (a -> b) -> [a] -> [b]
map (\(g :: Permutation Int
g,c :: Q
c) -> (Permutation Int
g, Q -> GlexPoly Q (X Int)
forall k b. Algebra k b => k -> Vect k b
unit Q
c)) [(Permutation Int, Q)]
ts -- lift the coefficients in x into the polynomial algebra
            one :: Vect (GlexPoly Q (X Int)) (Permutation Int)
one = Vect (GlexPoly Q (X Int)) (Permutation Int)
x' Vect (GlexPoly Q (X Int)) (Permutation Int)
-> Vect (GlexPoly Q (X Int)) (Permutation Int)
-> Vect (GlexPoly Q (X Int)) (Permutation Int)
forall a. Num a => a -> a -> a
* Vect (GlexPoly Q (X Int)) (Permutation Int)
y
            m :: [[Q]]
m = [ [Glex (X Int) -> GlexPoly Q (X Int) -> Q
forall k b. (Num k, Eq b) => b -> Vect k b -> k
coeff (X Int -> Glex (X Int)
forall (m :: * -> *) v. MonomialConstructor m => v -> m v
mvar (Int -> X Int
forall a. a -> X a
X Int
j)) GlexPoly Q (X Int)
c | Int
j <- [1..Int
n]] | Permutation Int
i <- [Permutation Int]
gs, let c :: GlexPoly Q (X Int)
c = Permutation Int
-> Vect (GlexPoly Q (X Int)) (Permutation Int)
-> GlexPoly Q (X Int)
forall k b. (Num k, Eq b) => b -> Vect k b -> k
coeff Permutation Int
i Vect (GlexPoly Q (X Int)) (Permutation Int)
one] -- matrix of the linear system
            b :: [Q]
b = 1 Q -> [Q] -> [Q]
forall a. a -> [a] -> [a]
: Int -> Q -> [Q]
forall a. Int -> a -> [a]
replicate (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-1) 0
        in case [[Q]] -> [Q] -> Maybe [Q]
forall a. (Eq a, Fractional a) => [[a]] -> [a] -> Maybe [a]
solveLinearSystem [[Q]]
m [Q]
b of -- find v such that m v == b - ie find the values of x1, x2, ... xn
            Just v :: [Q]
v -> GroupAlgebra Q -> GroupAlgebra Q
forall k b. (Eq k, Num k, Ord b) => Vect k b -> Vect k b
nf (GroupAlgebra Q -> GroupAlgebra Q)
-> GroupAlgebra Q -> GroupAlgebra Q
forall a b. (a -> b) -> a -> b
$ [(Permutation Int, Q)] -> GroupAlgebra Q
forall k b. [(b, k)] -> Vect k b
V ([(Permutation Int, Q)] -> GroupAlgebra Q)
-> [(Permutation Int, Q)] -> GroupAlgebra Q
forall a b. (a -> b) -> a -> b
$ [Permutation Int] -> [Q] -> [(Permutation Int, Q)]
forall a b. [a] -> [b] -> [(a, b)]
zip [Permutation Int]
gs [Q]
v
            Nothing -> String -> GroupAlgebra Q
forall a. HasCallStack => String -> a
error "GroupAlgebra.inverse: not invertible"

maybeInverse :: Vect Q b -> Maybe (Vect Q b)
maybeInverse x :: Vect Q b
x@(V ts :: [(b, Q)]
ts) =
    let gs :: [b]
gs = [b] -> [b]
forall a. (Num a, Ord a) => [a] -> [a]
elts ([b] -> [b]) -> [b] -> [b]
forall a b. (a -> b) -> a -> b
$ ((b, Q) -> b) -> [(b, Q)] -> [b]
forall a b. (a -> b) -> [a] -> [b]
map (b, Q) -> b
forall a b. (a, b) -> a
fst ([(b, Q)] -> [b]) -> [(b, Q)] -> [b]
forall a b. (a -> b) -> a -> b
$ Vect Q b -> [(b, Q)]
forall k b. Vect k b -> [(b, k)]
terms Vect Q b
x -- all elements in the group generated by the terms
        cs :: [GlexPoly Q (X b)]
cs = (b -> GlexPoly Q (X b)) -> [b] -> [GlexPoly Q (X b)]
forall a b. (a -> b) -> [a] -> [b]
map (X b -> GlexPoly Q (X b)
forall v. v -> GlexPoly Q v
glexvar (X b -> GlexPoly Q (X b)) -> (b -> X b) -> b -> GlexPoly Q (X b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> X b
forall a. a -> X a
X) [b]
gs
        x' :: Vect (GlexPoly Q (X b)) b
x' = [(b, GlexPoly Q (X b))] -> Vect (GlexPoly Q (X b)) b
forall k b. [(b, k)] -> Vect k b
V ([(b, GlexPoly Q (X b))] -> Vect (GlexPoly Q (X b)) b)
-> [(b, GlexPoly Q (X b))] -> Vect (GlexPoly Q (X b)) b
forall a b. (a -> b) -> a -> b
$ ((b, Q) -> (b, GlexPoly Q (X b)))
-> [(b, Q)] -> [(b, GlexPoly Q (X b))]
forall a b. (a -> b) -> [a] -> [b]
map (\(g :: b
g,c :: Q
c) -> (b
g, Q -> GlexPoly Q (X b)
forall k b. Algebra k b => k -> Vect k b
unit Q
c)) [(b, Q)]
ts
        one :: Vect (GlexPoly Q (X b)) b
one = Vect (GlexPoly Q (X b)) b
x' Vect (GlexPoly Q (X b)) b
-> Vect (GlexPoly Q (X b)) b -> Vect (GlexPoly Q (X b)) b
forall a. Num a => a -> a -> a
* ([(b, GlexPoly Q (X b))] -> Vect (GlexPoly Q (X b)) b
forall k b. [(b, k)] -> Vect k b
V ([(b, GlexPoly Q (X b))] -> Vect (GlexPoly Q (X b)) b)
-> [(b, GlexPoly Q (X b))] -> Vect (GlexPoly Q (X b)) b
forall a b. (a -> b) -> a -> b
$ [b] -> [GlexPoly Q (X b)] -> [(b, GlexPoly Q (X b))]
forall a b. [a] -> [b] -> [(a, b)]
zip [b]
gs [GlexPoly Q (X b)]
cs)
        m :: [[Q]]
m = [ [Glex (X b) -> GlexPoly Q (X b) -> Q
forall k b. (Num k, Eq b) => b -> Vect k b -> k
coeff (X b -> Glex (X b)
forall (m :: * -> *) v. MonomialConstructor m => v -> m v
mvar (b -> X b
forall a. a -> X a
X b
j)) GlexPoly Q (X b)
c | b
j <- [b]
gs] | b
i <- [b]
gs, let c :: GlexPoly Q (X b)
c = b -> Vect (GlexPoly Q (X b)) b -> GlexPoly Q (X b)
forall k b. (Num k, Eq b) => b -> Vect k b -> k
coeff b
i Vect (GlexPoly Q (X b)) b
one]
        b :: [Q]
b = 1 Q -> [Q] -> [Q]
forall a. a -> [a] -> [a]
: Int -> Q -> [Q]
forall a. Int -> a -> [a]
replicate ([b] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [b]
gs Int -> Int -> Int
forall a. Num a => a -> a -> a
- 1) 0
    in ([Q] -> Vect Q b) -> Maybe [Q] -> Maybe (Vect Q b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\v :: [Q]
v -> Vect Q b -> Vect Q b
forall k b. (Eq k, Num k, Ord b) => Vect k b -> Vect k b
nf (Vect Q b -> Vect Q b) -> Vect Q b -> Vect Q b
forall a b. (a -> b) -> a -> b
$ [(b, Q)] -> Vect Q b
forall k b. [(b, k)] -> Vect k b
V ([(b, Q)] -> Vect Q b) -> [(b, Q)] -> Vect Q b
forall a b. (a -> b) -> a -> b
$ [b] -> [Q] -> [(b, Q)]
forall a b. [a] -> [b] -> [(a, b)]
zip [b]
gs [Q]
v) ([[Q]] -> [Q] -> Maybe [Q]
forall a. (Eq a, Fractional a) => [[a]] -> [a] -> Maybe [a]
solveLinearSystem [[Q]]
m [Q]
b)
{-
    in case solveLinearSystem m b of
        Just v -> Just $ nf $ V $ zip gs v
        Nothing -> Nothing
-}