It's been a little while since my last post. That's partly because I've been busy writing new code. I've put up a new release,
HaskellForMaths 0.3.3, which contains three new modules:
- Math.Combinatorics.Digraph
- Math.Combinatorics.Poset
- Math.Combinatorics.IncidenceAlgebra
I'll go through their contents at some point, but this time I want to talk about the tensor algebra.
So recall that previously we defined the
free vector space over a type,
tensor products,
algebras and
coalgebras in Haskell code.
In HaskellForMaths, we always work with the free vector space over a type: that means, we take some type b as a basis, and form k-linear combinations of elements of b. This construction is represented by the type Vect k b.
Given two vector spaces A = Vect k a, B = Vect k b, we can form their tensor product A⊗B = Vect k (Tensor a b). So Tensor is a type constructor on basis types, which takes basis types a, b for vector spaces A, B, and returns a basis type for the tensor product A⊗B.
We also defined a type constructor DSum, which returns a basis type for the direct sum A⊕B.
Now, we saw that tensor product is a monoid (at the type level, up to isomorphism):
- it is associative: (A⊗B)⊗C is isomorphic to A⊗(B⊗C)
- it has a unit: the field k itself is an identity for tensor product, in the sense that k⊗A is isomorphic to A, is isomorphic to A⊗k
Given some specific vector space V, we can consider the tensor powers of V:
k, V, V⊗V, V⊗V⊗V, ...
(We can omit brackets in V⊗V⊗V because tensor product is associative.)
And indeed we can form their direct sum:
T(V) = k ⊕ V ⊕ V⊗V ⊕ V⊗V⊗V ⊕ ...
(where an element of T(V) is understood to be a
finite sum of elements of the tensor powers.)
This is a vector space, since tensor products and direct sums are vector spaces. If V has a basis e1,e2,e3,..., then a typical element of T(V) might be something like 3 + 5e2 + 2e1⊗e3⊗e1.
Now the interesting thing is that T(V) can be given the structure of an algebra, as follows:
- for the unit, we use the injection of k into the first direct summand
- for the mult, we use tensor product
For example, we would have
e2 * (2 + 3e1 + e4⊗e2) = 2e2 + 3e2⊗e1 + e2⊗e4⊗e2
With this algebra structure, T(V) is called the tensor algebra.
So how should we represent the tensor algebra in HaskellForMaths? Suppose that V is the free vector space Vect k a over some basis type a. (Recall also that the field k itself can be represented as the free vector space Vect k () over the unit type.) Can we use the DSum and Tensor type constructors to build the tensor algebra? Something like:
Vect k (DSum () (DSum a (DSum (Tensor a a) (DSum ...))))
Hmm, that's not going to work - we can't build the whole of what we want that way. (Unless some type system wizard knows otherwise?) So instead of representing the direct sum and tensor product at the type level, we're going to have to do it at the value level. Here's the definition:
data TensorAlgebra a = TA Int [a] deriving (Eq,Ord)
Given the free vector space V = Vect k a over basis type a, then TensorAlgebra a is the basis type for the tensor algebra over a, so that Vect k (TensorAlgebra a) is the tensor algebra T(V). The Int in TA Int [a] tells us which direct summand we're in (ie which tensor power), and the [a] tells us the tensor multiplicands. So for example, e2⊗e1⊗e4 would be represented as TA 3 [e2,e1,e4]. Then Vect k (TensorAlgebra a) consists of k-linear combinations of these basis elements, so it is the vector space T(V) that we are after.
Here's a Show instance:
instance Show a => Show (TensorAlgebra a) where
show (TA _ []) = "1"
show (TA _ xs) = filter (/= '"') $ concat $ L.intersperse "*" $ map show xs
It will be helpful to have a vector space basis to work with, so here's one that we used previously:
newtype EBasis = E Int deriving (Eq,Ord)
instance Show EBasis where show (E i) = "e" ++ show i
Then, for example, our Show instance gives us:
> :l Math.Algebras.TensorAlgebra
> return (TA 0 []) <+> return (TA 2 [E 1, E 3])
1+e1*e3
(Recall that the free vector space is a monad, hence our use of return to put a basis element into the vector space.)
So note that in the show output, the "*" is meant to represent tensor product, so this is really 1+e1⊗e3. You can actually get Haskell to output the tensor product symbol - just replace "*" by "\x2297" in the definition of show - however I found that it didn't look too good in the Mac OS X terminal, and I wasn't sure it would work on all OSes.
Ok, how about an Algebra instance? Well, TensorAlgebra a is basically just a slightly frilly version of [a], so it's a monoid, and we can use the monoid algebra construction:
instance Mon (TensorAlgebra a) where
munit = TA 0 []
mmult (TA i xs) (TA j ys) = TA (i+j) (xs++ys)
instance (Num k, Ord a) => Algebra k (TensorAlgebra a) where
unit x = x *> return munit
mult = nf . fmap (\(a,b) -> a `mmult` b)
So now we can do arithmetic in the tensor algebra:
> let e_ i = return (TA 1 [E i]) :: Vect Q (TensorAlgebra EBasis)
> let e1 = e_ 1; e2 = e_ 2; e3 = e_ 3; e4 = e_ 4
> (e1+e2) * (1+e3*e4)
e1+e2+e1*e3*e4+e2*e3*e4
We've got into the habit of using QuickCheck to check algebraic properties. Let's just check that the tensor algebra, as we've defined it, is an algebra:
instance Arbitrary b => Arbitrary (TensorAlgebra b) where
arbitrary = do xs <- listOf arbitrary :: Gen [b] -- ScopedTypeVariables
let d = length xs
return (TA d xs)
prop_Algebra_TensorAlgebra (k,x,y,z) = prop_Algebra (k,x,y,z)
where types = (k,x,y,z) :: ( Q, Vect Q (TensorAlgebra EBasis), Vect Q (TensorAlgebra EBasis), Vect Q (TensorAlgebra EBasis) )
> quickCheck prop_Algebra_TensorAlgebra
+++ OK, passed 100 tests.
Ok, so what's so special about the tensor algebra? Well, it has a rather nice universal property:
Suppose A = Vect k a, B = Vect k b are vector spaces, and we have a linear map f : A -> B. Suppose that B is also an algebra. Then we can "lift" f to an algebra morphism f' : T(A) -> B, such that the following diagram commutes.
In other words, f' agrees with f on the copy of A within T(A): f = f' . i
Ah, but hold on, I didn't say what an algebra morphism is. Well, it's just the usual: a function which "commutes" with the algebra structure. Specifically, it's a linear map (so that it commutes with the vector space structure), which makes the following diagrams commute:
So how does this universal property work then? Here's the code:
injectTA :: Num k => Vect k a -> Vect k (TensorAlgebra a)
injectTA = fmap (\a -> TA 1 [a])
liftTA :: (Num k, Ord b, Show b, Algebra k b) =>
(Vect k a -> Vect k b) -> Vect k (TensorAlgebra a) -> Vect k b
liftTA f = linear (\(TA _ xs) -> product [f (return x) | x <- xs])
In other words, any tensor product u⊗v⊗... is sent to f(u)*f(v)*...
Let's look at an example. Recall that the quaternion algebra H has the basis {1,i,j,k}, with i^2 = j^2 = k^2 = ijk = -1.
> let f = linear (\(E n) -> case n of 1 -> 1+i; 2 -> 1-i; 3 -> j+k; 4 -> j-k; _ -> zerov)
> let f' = liftTA f
> e1*e2
e1*e2
> f' (e1*e2)
2
Recall that we usually define a linear map by linear extension from its action on a basis - that's what the "linear" is doing in the definition of f. It's fairly clear what f' is doing: it's basically just variable substitution. That is, we can consider the basis elements ei as variables, and the tensor algebra as the algebra of non-commutative polynomials in the ei. Then the linear map f assigns a substitution to each basis element, and f' just substitutes and multiplies out in the target algebra. In this case, we have:
e1⊗e2 -> (1+i)*(1-i) = 1-i^2 = 2
We can use QuickCheck to verify that liftTA f is indeed the algebra morphism required by the universal property. Here's a QuickCheck property for an algebra morphism. (We don't bother to check that f is a linear map, since it's almost always clear from the definition. If in doubt, we can test that separately.)
prop_AlgebraMorphism f (k,x,y) =
(f . unit) k == unit k &&
(f . mult) (x `te` y) == (mult . (f `tf` f)) (x `te` y)
This is just a transcription of the diagrams into code.
In order to test the universal property, we have to check that liftTA f is an algebra morphism, and that it agrees with f on (the copy of) V (in T(V)):
prop_TensorAlgebra_UniversalProperty (fmatrix,(k,x,y),z) =
prop_AlgebraMorphism f' (k,x,y) &&
(f' . injectTA) z == f z
where f = linfun fmatrix
f' = liftTA f
types = (fmatrix,(k,x,y),z) :: (LinFun Q EBasis HBasis,
(Q,Vect Q (TensorAlgebra EBasis), Vect Q (TensorAlgebra EBasis)),
Vect Q EBasis)
So the key to this code is the parameter fmatrix, which is an arbitrary (sparse) matrix from Q^n to H, the quaternions, from which we build an arbitrary linear function. Note that the universal property of course implies that we can choose any algebra as the target for f - I just chose the quaternions because they're familiar.
> quickCheck prop_TensorAlgebra_UniversalProperty
+++ OK, passed 100 tests.
With this construction, tensor algebra is in fact a functor from
k-Vect to
k-Alg. The action on objects is V -> T(V), Vect k a -> Vect k (TensorAlgebra a). But a functor also acts on the arrows of the source category.
How do we get an action on arrows? Well, we can use the universal property to construct one. If we have an arrow f: A -> B, then (injectTA . f) is an arrow A -> T(B). Then we use the universal property to lift to an arrow f': T(A) -> T(B).
Here's the code:
fmapTA :: (Num k, Ord b, Show b) =>
(Vect k a -> Vect k b) -> Vect k (TensorAlgebra a) -> Vect k (TensorAlgebra b)
fmapTA f = liftTA (injectTA . f)
For example:
newtype ABasis = A Int deriving (Eq,Ord,Show)
newtype BBasis = B Int deriving (Eq,Ord,Show)
> let f = linear (\(A i) -> case i of 1 -> return (B 1) <+> return (B 2);
2 -> return (B 3) <+> return (B 4);
_ -> zerov :: Vect Q BBasis)
> let f' = fmapTA f
> return (TA 2 [A 1, A 2]) :: Vect Q (TensorAlgebra ABasis)
A 1*A 2
> f' it
B 1*B 3+B 1*B 4+B 2*B 3+B 2*B 4
So this is variable substitution again. In this case, as f is just a linear map between vector spaces, we can think of it as something like a change of basis of the underlying space. Then f' shows us how the (non-commutative) polynomials defined over the space transform under the change of basis.
Let's just verify that this is a functor. We have to show:
- That fmapTA f is an algebra morphism (ie it is an arrow in
k-Alg)
- That fmapTA commutes with the category structure, ie fmapTA id = id, and fmapTA (g . f) = fmapTA g . fmapTA f.
Here's a QuickCheck property:
prop_Functor_Vect_TensorAlgebra (f,g,k,x,y) =
prop_AlgebraMorphism (fmapTA f') (k,x,y) &&
(fmapTA id) x == id x &&
fmapTA (g' . f') x == (fmapTA g' . fmapTA f') x
where f' = linfun f
g' = linfun g
types = (f,g,k,x,y) :: (LinFun Q ABasis BBasis, LinFun Q BBasis CBasis,
Q, Vect Q (TensorAlgebra ABasis), Vect Q (TensorAlgebra ABasis) )
> quickCheck prop_Functor_Vect_TensorAlgebra
+++ OK, passed 100 tests.
So can we declare a Functor instance? Well no, actually. Haskell only allows us to declare type constructors as Functor instances, whereas what we would want to do is declare the type function (\Vect k a -> Vect k (TensorAlgebra a)) as a Functor, which isn't allowed.
Ok, so we have a functor T:
k-Vect ->
k-Alg, the tensor algebra functor. We also have a forgetful functor going the other way,
k-Alg ->
k-Vect, which consists in taking an algebra, and simply forgetting that it is an algebra, and seeing only the vector space structure. (As it does at least remember the vector space structure, perhaps we should call this a semi-forgetful, or merely absent-minded functor.)
The cognoscenti will no doubt have seen what is coming next: we have an adjunction, and hence a monad.
How so? Well, it's obvious from its type signature that injectTA is return. For (>>=) / bind, we can define the following:
bindTA :: (Num k, Ord b, Show b) =>
Vect k (TensorAlgebra a) -> (Vect k a -> Vect k (TensorAlgebra b)) -> Vect k (TensorAlgebra b)
bindTA = flip liftTA
Note that in addition to flipping the arguments, bindTA also imposes a more restrictive signature than liftTA: the target algebra is constrained to be a tensor algebra.
> let f = linear (\(A i) -> case i of 1 -> return (TA 2 [B 1, B 2]);
2 -> return (TA 1 [B 3]) + return (TA 1 [B 4]);
_ -> zerov :: Vect Q (TensorAlgebra BBasis))
> return (TA 2 [A 1, A 2]) `bindTA` f
B 1*B 2*B 3+B 1*B 2*B 4
So the effect of bind is to feed a non-commutative polynomial through a variable substitution.
Monads are meant to satisfy the following
monad laws:
- "Left identity": return a >>= f == f a
- "Right identity": m >>= return == m
- "Associativity": (m >>= f) >>= g == m >>= (\x -> f x >>= g)
As usual, we write a QuickCheck property:
prop_Monad_Vect_TensorAlgebra (fmatrix,gmatrix,a,ta)=
injectTA a `bindTA` f == f a && -- left identity
ta `bindTA` injectTA == ta && -- right identity
(ta `bindTA` f) `bindTA` g == ta `bindTA` (\a -> f a `bindTA` g) -- associativity
where f = linfun fmatrix
g = linfun gmatrix
types = (fmatrix,gmatrix,a,ta) :: (LinFun Q ABasis (TensorAlgebra BBasis),
LinFun Q BBasis (TensorAlgebra CBasis),
Vect Q ABasis, Vect Q (TensorAlgebra ABasis) )
> quickCheck prop_Monad_Vect_TensorAlgebra
+++ OK, passed 100 tests.
Once again, we can't actually declare a Monad instance, because our type function (\Vect k a -> Vect k (TensorAlgebra a)) is not a type constructor.
So, we have a functor, and indeed a monad, T:
k-Vect ->
k-Alg. Now recall that the free vector space construction (\a -> Vect k a) was itself a functor, indeed a monad, from
Set ->
k-Vect. What happens if we compose these two functors? Why then of course we get a functor, and a monad, from
Set ->
k-Alg. In Haskell terms, this is a functor a -> Vect k (TensorAlgebra a).
What does this functor look like? Well, relative to a, Vect k (TensorAlgebra a) is the
free algebra on a, consisting of all expressions in which the elements of k and the elements of a are combined using (commutative) addition and (non-commutative) multiplication. In other words, the elements of a can be thought of as variable symbols, and Vect k (TensorAlgebra a) as the algebra of non-commutative polynomials in these variables.
Here's the code:
injectTA' :: Num k => a -> Vect k (TensorAlgebra a)
injectTA' = injectTA . return
liftTA' :: (Num k, Ord b, Show b, Algebra k b) =>
(a -> Vect k b) -> Vect k (TensorAlgebra a) -> Vect k b
liftTA' = liftTA . linear
fmapTA' :: (Num k, Ord b, Show b) =>
(a -> b) -> Vect k (TensorAlgebra a) -> Vect k (TensorAlgebra b)
fmapTA' = fmapTA . fmap
bindTA' :: (Num k, Ord b, Show b) =>
Vect k (TensorAlgebra a) -> (a -> Vect k (TensorAlgebra b)) -> Vect k (TensorAlgebra b)
bindTA' = flip liftTA'
The only one of these which might require a little explanation is liftTA'. This works by applying a universal property twice, as shown by the diagram below: first, the universal property of free vector spaces is used to lift a function a -> Vect k (TensorAlgebra b) to a function Vect k a -> Vect k (TensorAlgebra b); then the universal property of the tensor algebra is used to lift that to a function Vect k (TensorAlgebra a) -> Vect k (TensorAlgebra b).
Here's an example, which shows that in the free algebra as in the tensor algebra, bind corresponds to variable substitution:
> let [t,x,y,z] = map injectTA' ["t","x","y","z"] :: [Vect Q (TensorAlgebra String)]
> let f "x" = 1-t^2; f "y" = 2*t; f "z" = 1+t^2
> (x^2+y^2-z^2) `bindTA'` f
0
