[GAP Forum] Constructing bilinear maps for matrix multiplication

[Max Horn]

Hi again,

here is a reply to part 1 of Sandeep's question:

Am 17.11.2011 um 10:57 schrieb Sandeep Murthy:

> Hello,
> 
> 1. I'm trying to construct bilinear maps f_m(K) for m x m matrix
> multiplication over a field K, for small values of m, like 2, 3, 4.
> 
> I'm particularly interested in f_Q(3), and f_Q(4), where Q
> is the field of rationals.  If T := Mat_Q(3) denotes the 3 x 3 matrix
> Q-algebra, with standard basis, it should be possible to 
> do this explicitly on GAP by constructing the direct sum 
> S := Mat_Q(3) \otimes Mat_Q(3), a Q-algebra of dimension 18

Actually, it is a 9^2=81 dimensional algebra. The direct sum is 2*9=18 dimensional, but for a bilinear form you indeed want to study the tensor product.


> with standard basis, and then computing f_Q(3) as the
> map f: S --> T by using AlgebraHomomorphismByImages( source, target, gens, imgs ).
> However, I'm getting a "exceeded the permitted memory" error.

You discovered a bug in GAP itself, which we need to fix. Luckily, though, you can avoid it, at least in this case. Instead of many words, let me show you one possible way:

# Compute algebra and generators
T:=FullMatrixAlgebra(Rationals, 3);;
gensT:=GeneratorsOfAlgebra(T);;

# Compute S = T \otimes T by computing generators
gensS:=ListX(gensT, gensT, KroneckerProduct);;
S:=AlgebraWithOneByGenerators(Rationals, gensS);

# Compute hom from S to T on a basis of S
basisT:=BasisVectors(Basis(T));;
basisS:=ListX(basisT, basisT, KroneckerProduct);;
imgs:=ListX(basisT, basisT, \*);;
hom:=AlgebraHomomorphismByImages(S,T,Basis(S,basisS),imgs);;


Note that the KroneckerProduct of two matrices is just their tensor product (w.r.t. to the "standard" bases). So we can use that to construct the tensor product algebra.

The crucial part is my use of the Basis() command. This is important because the code underlying AlgebraHomomorphismByImages will do something different if you don't define the morphism on a basis. Indeed, if the image of each element in a basis is given, this makes it easy to evaluate a homomorphism. The same is not true if one defines the homomorphism only a generating set (or even if one defines it on a set of vectors that form a basis, but which one has not marked as a basis). So in this case, GAP first tries to extend the definition of the homomorphism to a basis; and it is this case which has a bug. For example:

  hom:=AlgebraHomomorphismByImages(S,T,gensS,ListX(gensT, gensT, \*));;

leads to an endless loop (until memory overflows). This bug will be fixed in the next GAP release.


Best wishes,
Max