ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sun, 03 Nov 2013 00:14:05 +0100Group algebra/matrix space homomorphismhttps://ask.sagemath.org/question/10684/group-algebramatrix-space-homomorphism/I would like to know if it is possible to define a homomorphism (of algebras) between a group algebra over the rationals and a matrix space over the rationals.
I have
sage: S3 = SymmetricGroup(3)
sage: QG = GroupAlgebra(S3, QQ)
sage: QG.gens()
Finite family {(1,2,3): (1,2,3), (1,2): (1,2)}
sage: M_3 = MatrixSpace(QQ, 2)
sage: ma = M_3([[0,-1],[1,-1]])
sage: mb = M_3([[1,-1],[0,-1]])
Now I would like to map each generator of QG to a matrix. In this case I would like to map (1,2,3) to ma and (1,2) to mb and use that to define a homomorphism. But everything I tried didn't work.
Edit:
I've encountered another issue, though I can work around it. So this is only for information. The elements of `G.gens()` don't coincide with the reduced words of length 1.
sage: S3 = SymmetricGroup(3)
sage: S3.gens()
[(1,2,3), (1,2)]
sage: {g: g.reduced_word() for g in S3}
{(): [],
(2,3): [2],
(1,2): [1],
(1,2,3): [2, 1],
(1,3,2): [1, 2],
(1,3): [1, 2, 1]}
Sat, 02 Nov 2013 05:49:02 +0100https://ask.sagemath.org/question/10684/group-algebramatrix-space-homomorphism/Comment by vdelecroix for <p>I would like to know if it is possible to define a homomorphism (of algebras) between a group algebra over the rationals and a matrix space over the rationals.</p>
<p>I have </p>
<pre><code>sage: S3 = SymmetricGroup(3)
sage: QG = GroupAlgebra(S3, QQ)
sage: QG.gens()
Finite family {(1,2,3): (1,2,3), (1,2): (1,2)}
sage: M_3 = MatrixSpace(QQ, 2)
sage: ma = M_3([[0,-1],[1,-1]])
sage: mb = M_3([[1,-1],[0,-1]])
</code></pre>
<p>Now I would like to map each generator of QG to a matrix. In this case I would like to map (1,2,3) to ma and (1,2) to mb and use that to define a homomorphism. But everything I tried didn't work.</p>
<p>Edit: <br/>
I've encountered another issue, though I can work around it. So this is only for information. The elements of <code>G.gens()</code> don't coincide with the reduced words of length 1.</p>
<pre><code>sage: S3 = SymmetricGroup(3)
sage: S3.gens()
[(1,2,3), (1,2)]
sage: {g: g.reduced_word() for g in S3}
{(): [],
(2,3): [2],
(1,2): [1],
(1,2,3): [2, 1],
(1,3,2): [1, 2],
(1,3): [1, 2, 1]}
</code></pre>
https://ask.sagemath.org/question/10684/group-algebramatrix-space-homomorphism/?comment=16811#post-id-16811about your edit: I would not characterize it as a bug. This is well documented, the reduced_word method returns a word over the simple reflections (1,2), (2,3), (3,4), ...Sun, 03 Nov 2013 00:14:05 +0100https://ask.sagemath.org/question/10684/group-algebramatrix-space-homomorphism/?comment=16811#post-id-16811Comment by vuur for <p>I would like to know if it is possible to define a homomorphism (of algebras) between a group algebra over the rationals and a matrix space over the rationals.</p>
<p>I have </p>
<pre><code>sage: S3 = SymmetricGroup(3)
sage: QG = GroupAlgebra(S3, QQ)
sage: QG.gens()
Finite family {(1,2,3): (1,2,3), (1,2): (1,2)}
sage: M_3 = MatrixSpace(QQ, 2)
sage: ma = M_3([[0,-1],[1,-1]])
sage: mb = M_3([[1,-1],[0,-1]])
</code></pre>
<p>Now I would like to map each generator of QG to a matrix. In this case I would like to map (1,2,3) to ma and (1,2) to mb and use that to define a homomorphism. But everything I tried didn't work.</p>
<p>Edit: <br/>
I've encountered another issue, though I can work around it. So this is only for information. The elements of <code>G.gens()</code> don't coincide with the reduced words of length 1.</p>
<pre><code>sage: S3 = SymmetricGroup(3)
sage: S3.gens()
[(1,2,3), (1,2)]
sage: {g: g.reduced_word() for g in S3}
{(): [],
(2,3): [2],
(1,2): [1],
(1,2,3): [2, 1],
(1,3,2): [1, 2],
(1,3): [1, 2, 1]}
</code></pre>
https://ask.sagemath.org/question/10684/group-algebramatrix-space-homomorphism/?comment=16815#post-id-16815yes, I used M_3 instead of matrix, I posted the wrong code here, sorry for thatSat, 02 Nov 2013 12:49:39 +0100https://ask.sagemath.org/question/10684/group-algebramatrix-space-homomorphism/?comment=16815#post-id-16815Comment by vdelecroix for <p>I would like to know if it is possible to define a homomorphism (of algebras) between a group algebra over the rationals and a matrix space over the rationals.</p>
<p>I have </p>
<pre><code>sage: S3 = SymmetricGroup(3)
sage: QG = GroupAlgebra(S3, QQ)
sage: QG.gens()
Finite family {(1,2,3): (1,2,3), (1,2): (1,2)}
sage: M_3 = MatrixSpace(QQ, 2)
sage: ma = M_3([[0,-1],[1,-1]])
sage: mb = M_3([[1,-1],[0,-1]])
</code></pre>
<p>Now I would like to map each generator of QG to a matrix. In this case I would like to map (1,2,3) to ma and (1,2) to mb and use that to define a homomorphism. But everything I tried didn't work.</p>
<p>Edit: <br/>
I've encountered another issue, though I can work around it. So this is only for information. The elements of <code>G.gens()</code> don't coincide with the reduced words of length 1.</p>
<pre><code>sage: S3 = SymmetricGroup(3)
sage: S3.gens()
[(1,2,3), (1,2)]
sage: {g: g.reduced_word() for g in S3}
{(): [],
(2,3): [2],
(1,2): [1],
(1,2,3): [2, 1],
(1,3,2): [1, 2],
(1,3): [1, 2, 1]}
</code></pre>
https://ask.sagemath.org/question/10684/group-algebramatrix-space-homomorphism/?comment=16816#post-id-16816It even seems impossible to get a group morphism from S3 to MatrixGroup([ma,mb])... which looks like another bug!Sat, 02 Nov 2013 10:26:33 +0100https://ask.sagemath.org/question/10684/group-algebramatrix-space-homomorphism/?comment=16816#post-id-16816Comment by vdelecroix for <p>I would like to know if it is possible to define a homomorphism (of algebras) between a group algebra over the rationals and a matrix space over the rationals.</p>
<p>I have </p>
<pre><code>sage: S3 = SymmetricGroup(3)
sage: QG = GroupAlgebra(S3, QQ)
sage: QG.gens()
Finite family {(1,2,3): (1,2,3), (1,2): (1,2)}
sage: M_3 = MatrixSpace(QQ, 2)
sage: ma = M_3([[0,-1],[1,-1]])
sage: mb = M_3([[1,-1],[0,-1]])
</code></pre>
<p>Now I would like to map each generator of QG to a matrix. In this case I would like to map (1,2,3) to ma and (1,2) to mb and use that to define a homomorphism. But everything I tried didn't work.</p>
<p>Edit: <br/>
I've encountered another issue, though I can work around it. So this is only for information. The elements of <code>G.gens()</code> don't coincide with the reduced words of length 1.</p>
<pre><code>sage: S3 = SymmetricGroup(3)
sage: S3.gens()
[(1,2,3), (1,2)]
sage: {g: g.reduced_word() for g in S3}
{(): [],
(2,3): [2],
(1,2): [1],
(1,2,3): [2, 1],
(1,3,2): [1, 2],
(1,3): [1, 2, 1]}
</code></pre>
https://ask.sagemath.org/question/10684/group-algebramatrix-space-homomorphism/?comment=16817#post-id-16817Looks like a bug... I modified ma = matrix(...) to ma = M_3(...) and similarly for mb.Sat, 02 Nov 2013 10:23:50 +0100https://ask.sagemath.org/question/10684/group-algebramatrix-space-homomorphism/?comment=16817#post-id-16817Answer by nborie for <p>I would like to know if it is possible to define a homomorphism (of algebras) between a group algebra over the rationals and a matrix space over the rationals.</p>
<p>I have </p>
<pre><code>sage: S3 = SymmetricGroup(3)
sage: QG = GroupAlgebra(S3, QQ)
sage: QG.gens()
Finite family {(1,2,3): (1,2,3), (1,2): (1,2)}
sage: M_3 = MatrixSpace(QQ, 2)
sage: ma = M_3([[0,-1],[1,-1]])
sage: mb = M_3([[1,-1],[0,-1]])
</code></pre>
<p>Now I would like to map each generator of QG to a matrix. In this case I would like to map (1,2,3) to ma and (1,2) to mb and use that to define a homomorphism. But everything I tried didn't work.</p>
<p>Edit: <br/>
I've encountered another issue, though I can work around it. So this is only for information. The elements of <code>G.gens()</code> don't coincide with the reduced words of length 1.</p>
<pre><code>sage: S3 = SymmetricGroup(3)
sage: S3.gens()
[(1,2,3), (1,2)]
sage: {g: g.reduced_word() for g in S3}
{(): [],
(2,3): [2],
(1,2): [1],
(1,2,3): [2, 1],
(1,3,2): [1, 2],
(1,3): [1, 2, 1]}
</code></pre>
https://ask.sagemath.org/question/10684/group-algebramatrix-space-homomorphism/?answer=15639#post-id-15639Hi,
it seems to me that R.module_morphism for R a parent inheriting from CombinatorialFreeModule does not support a definition on_gens (probably some code by Robert Bradshaw do that but I do not remember where it is in Sage...). So the only current way to define your morphism imply to do some math to get a definition on_basis instead on_gens.
For example, this work but is ugly :
sage: S3 = SymmetricGroup(3)
sage: QG = GroupAlgebra(S3, QQ)
sage: QG.gens()
Finite family {(1,2,3): (1,2,3), (1,2): (1,2)}
sage: M_3 = MatrixSpace(QQ, 2)
sage: ma = M_3([[0,-1],[1,-1]])
sage: mb = M_3([[1,-1],[0,-1]])
sage: def img_of_perm(p, gens_mat):
w = p.reduced_word()
R = gens_mat[0].parent()
return R.prod([gens_mat[i-1] for i in w])
....:
sage: f = QG.module_morphism(on_basis=lambda x: img_of_perm(x, [ma,mb]),
codomain=ma.parent(), category=Algebras(QQ))
sage: f(QG.an_element())
[ 2 -5]
[ 2 -3]
Another bug : if you replace category=Algebras(QQ) by category=AlgebrasWithBasis(QQ), you get the error :
TypeError: Full MatrixSpace of 2 by 2 dense matrices over Rational Field is not in Category of algebras with basis over Rational Field
In a perfect world, the category should be at least FiniteDimensionnalAlgebraWithBasis(QQ) (because the parents should lies in it if I don't say something false)
The other way is trying to find stuff from Robert to define maps between parents on generators... I am not sure but I think it won't work either because it assume that elements of the two parents are not based on RingElement (old category stuff) and your group algebra is a CombinatorialFreeModule in data structure.
anyway, generally, define an algebra homomorphism between a group algebra and a matrix space implies there exist an algorithm to decompose each element of the domain in a polynomial over the algebra generators (I am not very sure it is a prerequisite but I think so...). For the symmetric group, we know how to do that with reduced word but a lot of combinatorial free module in Sage have a method algebra_generators() but do not know how to decompose an element along these algebra generators...
GAP do probably that very well but I also never tried (GAP knows how to decompose a group element along group generators...).
I hope that help a little...
Cheers,
Nicolas B.Sat, 02 Nov 2013 11:19:05 +0100https://ask.sagemath.org/question/10684/group-algebramatrix-space-homomorphism/?answer=15639#post-id-15639Comment by vuur for <p>Hi, </p>
<p>it seems to me that R.module_morphism for R a parent inheriting from CombinatorialFreeModule does not support a definition on_gens (probably some code by Robert Bradshaw do that but I do not remember where it is in Sage...). So the only current way to define your morphism imply to do some math to get a definition on_basis instead on_gens.</p>
<p>For example, this work but is ugly :</p>
<pre><code>sage: S3 = SymmetricGroup(3)
sage: QG = GroupAlgebra(S3, QQ)
sage: QG.gens()
Finite family {(1,2,3): (1,2,3), (1,2): (1,2)}
sage: M_3 = MatrixSpace(QQ, 2)
sage: ma = M_3([[0,-1],[1,-1]])
sage: mb = M_3([[1,-1],[0,-1]])
sage: def img_of_perm(p, gens_mat):
w = p.reduced_word()
R = gens_mat[0].parent()
return R.prod([gens_mat[i-1] for i in w])
....:
sage: f = QG.module_morphism(on_basis=lambda x: img_of_perm(x, [ma,mb]),
codomain=ma.parent(), category=Algebras(QQ))
sage: f(QG.an_element())
[ 2 -5]
[ 2 -3]
</code></pre>
<p>Another bug : if you replace category=Algebras(QQ) by category=AlgebrasWithBasis(QQ), you get the error :
TypeError: Full MatrixSpace of 2 by 2 dense matrices over Rational Field is not in Category of algebras with basis over Rational Field</p>
<p>In a perfect world, the category should be at least FiniteDimensionnalAlgebraWithBasis(QQ) (because the parents should lies in it if I don't say something false)</p>
<p>The other way is trying to find stuff from Robert to define maps between parents on generators... I am not sure but I think it won't work either because it assume that elements of the two parents are not based on RingElement (old category stuff) and your group algebra is a CombinatorialFreeModule in data structure.</p>
<p>anyway, generally, define an algebra homomorphism between a group algebra and a matrix space implies there exist an algorithm to decompose each element of the domain in a polynomial over the algebra generators (I am not very sure it is a prerequisite but I think so...). For the symmetric group, we know how to do that with reduced word but a lot of combinatorial free module in Sage have a method algebra_generators() but do not know how to decompose an element along these algebra generators...</p>
<p>GAP do probably that very well but I also never tried (GAP knows how to decompose a group element along group generators...).</p>
<p>I hope that help a little...</p>
<p>Cheers,</p>
<p>Nicolas B.</p>
https://ask.sagemath.org/question/10684/group-algebramatrix-space-homomorphism/?comment=16814#post-id-16814I donĀ“t mind using (or calculating) the basis instead of gens, Thanks for answering. It helps alot :-)Sat, 02 Nov 2013 12:58:08 +0100https://ask.sagemath.org/question/10684/group-algebramatrix-space-homomorphism/?comment=16814#post-id-16814Answer by vdelecroix for <p>I would like to know if it is possible to define a homomorphism (of algebras) between a group algebra over the rationals and a matrix space over the rationals.</p>
<p>I have </p>
<pre><code>sage: S3 = SymmetricGroup(3)
sage: QG = GroupAlgebra(S3, QQ)
sage: QG.gens()
Finite family {(1,2,3): (1,2,3), (1,2): (1,2)}
sage: M_3 = MatrixSpace(QQ, 2)
sage: ma = M_3([[0,-1],[1,-1]])
sage: mb = M_3([[1,-1],[0,-1]])
</code></pre>
<p>Now I would like to map each generator of QG to a matrix. In this case I would like to map (1,2,3) to ma and (1,2) to mb and use that to define a homomorphism. But everything I tried didn't work.</p>
<p>Edit: <br/>
I've encountered another issue, though I can work around it. So this is only for information. The elements of <code>G.gens()</code> don't coincide with the reduced words of length 1.</p>
<pre><code>sage: S3 = SymmetricGroup(3)
sage: S3.gens()
[(1,2,3), (1,2)]
sage: {g: g.reduced_word() for g in S3}
{(): [],
(2,3): [2],
(1,2): [1],
(1,2,3): [2, 1],
(1,3,2): [1, 2],
(1,3): [1, 2, 1]}
</code></pre>
https://ask.sagemath.org/question/10684/group-algebramatrix-space-homomorphism/?answer=15641#post-id-15641Hi,
I reproduce here the answer I got from Travis Scrimshaw on the mailing list sage-combinat devel.
**First method**
sage: S3 = SymmetricGroup(3)
sage: SGA = GroupAlgebra(S3, QQ)
sage: MS = MatrixSpace(QQ,2)
sage: mtx = [MS([[0,-1],[1,-1]]), MS([[1,-1],[0,-1]])]
sage: f = lambda x: MS.prod(mtx[i-1] for i in x.reduced_word())
sage: phi = SGA.module_morphism(f, codomain=MS)
Where the -1 is needed because of indexing. Now you can check:
sage: elt = SGA.gen(0) + SGA.gen(1); elt
(1,2) + (1,2,3)
sage: phi(elt)
[-1 -1]
[ 0 0]
**Second method**
An alternative method is to build a group morphism and then build the associate algebra morphism. There is a subtle issue as there is currently no method to express an element of a finite group in terms of generators. In particular, a morphism can not be built by providing only the image of the generators.
sage: MG = MatrixGroup(mtx) # take some time because it launches GAP
sage: H = Hom(S3, MG)
sage: psi = H(lambda x: MG.prod(MG.gen(i-1) for i in x.reduced_word()))
sage: kappa = SGA.module_morphism(lambda x: MS(psi(x)), codomain=MS)
You can again check
sage: elt = SGA.gen(0) + SGA.gen(1); elt
(1,2) + (1,2,3)
sage: kappa(elt)
[-1 -1]
[ 0 0]
**Alternative to the second method**
The following shows how in general, given a finite group, one may express a given element in terms of generators using the Cayley graph:
sage: G = S3.cayley_graph(generators=S3.gens())
sage: path = G.shortest_path(S3.one(), prod(S3.gens())); path
[(), (1,2,3), (2,3)]
sage: labels = [G.edge_label(path[i], path[i+1]) for i in range(len(path)-1)]; labels
[(1,2,3), (1,2)]
sage: map(lambda x: list(S3.gens()).index(x), labels)
[0, 1]
Sat, 02 Nov 2013 12:57:17 +0100https://ask.sagemath.org/question/10684/group-algebramatrix-space-homomorphism/?answer=15641#post-id-15641Comment by vuur for <p>Hi,</p>
<p>I reproduce here the answer I got from Travis Scrimshaw on the mailing list sage-combinat devel.</p>
<p><strong>First method</strong></p>
<pre><code>sage: S3 = SymmetricGroup(3)
sage: SGA = GroupAlgebra(S3, QQ)
sage: MS = MatrixSpace(QQ,2)
sage: mtx = [MS([[0,-1],[1,-1]]), MS([[1,-1],[0,-1]])]
sage: f = lambda x: MS.prod(mtx[i-1] for i in x.reduced_word())
sage: phi = SGA.module_morphism(f, codomain=MS)
</code></pre>
<p>Where the -1 is needed because of indexing. Now you can check:</p>
<pre><code>sage: elt = SGA.gen(0) + SGA.gen(1); elt
(1,2) + (1,2,3)
sage: phi(elt)
[-1 -1]
[ 0 0]
</code></pre>
<p><strong>Second method</strong>
An alternative method is to build a group morphism and then build the associate algebra morphism. There is a subtle issue as there is currently no method to express an element of a finite group in terms of generators. In particular, a morphism can not be built by providing only the image of the generators.</p>
<pre><code>sage: MG = MatrixGroup(mtx) # take some time because it launches GAP
sage: H = Hom(S3, MG)
sage: psi = H(lambda x: MG.prod(MG.gen(i-1) for i in x.reduced_word()))
sage: kappa = SGA.module_morphism(lambda x: MS(psi(x)), codomain=MS)
</code></pre>
<p>You can again check</p>
<pre><code>sage: elt = SGA.gen(0) + SGA.gen(1); elt
(1,2) + (1,2,3)
sage: kappa(elt)
[-1 -1]
[ 0 0]
</code></pre>
<p><strong>Alternative to the second method</strong>
The following shows how in general, given a finite group, one may express a given element in terms of generators using the Cayley graph:</p>
<pre><code>sage: G = S3.cayley_graph(generators=S3.gens())
sage: path = G.shortest_path(S3.one(), prod(S3.gens())); path
[(), (1,2,3), (2,3)]
sage: labels = [G.edge_label(path[i], path[i+1]) for i in range(len(path)-1)]; labels
[(1,2,3), (1,2)]
sage: map(lambda x: list(S3.gens()).index(x), labels)
[0, 1]
</code></pre>
https://ask.sagemath.org/question/10684/group-algebramatrix-space-homomorphism/?comment=16813#post-id-16813Thanks for answering. I will try out what works best for me. Sat, 02 Nov 2013 13:05:41 +0100https://ask.sagemath.org/question/10684/group-algebramatrix-space-homomorphism/?comment=16813#post-id-16813