# Incidence algebras in QPA via SAGE

This problem needs a little algebraic background. The input is a connected poset and the output should be the data needed to define the incidence algebra of the poset in QPA (a GAP package). Here the algebraic background: Given a connected poset P, the incidence algebra (over a feld $K$) is isomorphic to the quiver algebra $KQ/I$ (see https://en.wikipedia.org/wiki/Quiver_... for background), where $Q$ is the Hasse quiver of the poset $P$ and $I$ an admissible ideal defined generated by the following relations: $w_1 - w_2$ where $w_1$ and $w_2$ are two paths in the path algebra $KQ$ starting and ending at the same points. The relation more or less mean that we have a commutativity relation at each small "rectangle" (or pentagon etc.) of the Hasse quiver of the algebra. So I is generated by those commutativity relations (of course each "bigger" rectangle then commutes automatically when each smaller rectangle commutes) How the input should look like so that QPA can understand it and define the incidence algebra:

Q:=Quiver(5,[[1,2,"x12"],[2,4,"x24"],[2,3,"x23"],[4,5,"x45"],[3,5,"x35"]]);kQ:=PathAlgebra(Rationals,Q);AssignGeneratorVariables(kQ);rel:=[x24 * x45-x23 * x35];A:=kQ/rel; (*)

(More than one relation would look like this: rel:=[x24 * x45-x23 * x35, x24 * x45-x23 * x35]; so two relations are separeted by a comma , )

In this example the ouput is the incidence algebra of the poset 7 from the list http://math.chapman.edu/~jipsen/tikzs... (with 1 the lowest element).

I failed to program this in GAP but maybe there is an easy way doing this using SAGE? The advantage could also be to use SAGE to generate all posets on n elements (a thing which GAP can not do) and then calculate the above forms (*) of those posets. Then I would use the data to put it in to GAP and obtain the incidence algebras. (GAP can do things which SAGE probably can not do, like calculate the indecomposable modules in case the algebra has finite representation type)

So to make it clear: The problem is only about getting a poset in SAGE into the form in (*) and then I want to copy this form into GAP (more precisly the GAP package QPA) and continue working there with incidence algebra. While the algebras are isomorphic and just in another form , it is essential to work with QPA and view the indicence algebra as a quiver algebra.

Since this a somewhat harder program probably, I offer a twenty Euro prize money for a quick programm that works to give incidence algebras in SAGE. First quick program wins. Payment via paypal or Ama zon gift card. My motivation is to test some theoretical obtained results.

See page 8 of https://folk.ntnu.no/oyvinso/QPA/manu... for the definition of quiver algebras in QPA for more details.

edit: The code should be able to do two things (the first is more or less a special case of the second):

1. Given a specific poset, the code should give the output in the form (*).

2. Given a set of posets (for example all connected posets on 5 points or similar things), the code should put them in the form (*) but if the set contains n elements the output should enumerate them. For example the output should be in the form (in case the set contains the 2 posets as defined below)

L:=[];

Q1:=Quiver(5,[[1,2,"x12"],[2,4,"x24"],[2,3,"x23"],[4,5,"x45"],[3,5,"x35"]]);kQ1:=PathAlgebra(Rationals,Q1);AssignGeneratorVariables(kQ1);rel1:=[x24 * x45-x23 * x35];L[1]:=[Q1,kQ1/rel1];

Q2:=Quiver(4,[[1,2,"x12"],[2,4,"x24"],[1,3,"x13"],[3,4,"x34"]]);kQ2:=PathAlgebra(Rationals,Q2);AssignGeneratorVariables(kQ2);rel2:=[x12 * x24-x13 * x34];L[2]:=[Q2,kQ2/rel2];

so the empty list L gets filled with entries L[1] and L[2] so at the end we have a list L with the two incidence algebras (together with the underlying Hasse quivers Q1 and Q2)L[1] and L[2] in QPA after having copied the SAGE output into QPA.

edit retag close merge delete

Sort by » oldest newest most voted

Do you know about tab-completion in Sage? Once you define a poset p, type p. and then hit the TAB key. It will list all of the possible methods attached to p. One of those options is p.incidence_algebra. Typing p.incidence_algebra? provides the information that it takes one argument, the base ring. So p.incidence_algebra(QQ) may be what you want.

Alternatively to tab-completion, you can search the documentation (for example at http://doc.sagemath.org/html/en/refer...) to get http://doc.sagemath.org/html/en/refer....

Or you can search from within Sage:

sage: search_src('incidence algebra')

more

Thank you, but I do not need the incidence algebra in SAGE but I need it in GAP. So I just want to use SAGE to generate all posets (what GAP cant do) and transform them in the needed form so that GAP understand the input. SAGE is not able to do the things GAP can do to incidence algebras that I need(while SAGE can do alot things which GAP cant do). For example SAGE does not view the incidence algebra as a quiver algebra.

( 2017-09-20 18:01:52 -0500 )edit

Note that sometimes one can work entirely in sage, if there is only one specific step (or jaust a few) to be done in gap:

sage: gap( "Group((1,2,3,4),(1,2));" )
Group( [ (1,2,3,4), (1,2) ] )
sage: gap( "Size( Group((1,2,3,4),(1,2)) );" )
24


There is an interface in sage to gap understanding the most gap objects, translating them into sage objects.

( 2017-09-20 18:27:36 -0500 )edit

I use the GAP package QPA which is pretty new. Dont think things work with SAGE at the moment. Cant even get to QPA in the SAGE cell.

( 2017-09-20 18:29:37 -0500 )edit

Yes, the real work has to be done in gap, and sage is used as a poset generator & string parser. To help us get started please give e.g the poset in sage! Also translate / define the gap path algebra.

If the big hint incidence_algebra shows up, please understand that it's best to confirm/reject if this object is the object of study. It does not help a potential reader (now / in some years) to follow the discussion if there is no bridge in it.

... code:

X = [1..5]
p = Poset( ( X, [[1, 2], [2, 4], [2, 3], [4, 5], [3, 5]] ) )
A = p.incidence_algebra( QQ, prefix='x' )
for k in X:
for n in X:
key = 'x[%s, %s]' % (k,n)
if key in A.gens_dict():
exec( "x%s%s = A.gens_dict() [key]" % (k,n) )

print x24 * x45 - x23 * x35

( 2017-09-20 19:18:06 -0500 )edit

Sorry, your question ended with "works to give incidence algebras in SAGE", and I addressed that. Sage also has quiver algebras, although perhaps not an interface between them and incidence algebras.

( 2017-09-20 20:18:39 -0500 )edit

The code:

X = [1,2,3,4,5]
R = [ [1,2], [2,3], [3,5], [1,4], [4,5] ]
P = Poset( (X,R) )

def str_prod_for_path( path ):
"""given a list / "path", e.g. [1,3,7,9,1991]
return something like x13*x37*x39*x91991 .
(Not our problem here to distinguish between [1,3,7,9,1991] and [1,3,7,91,991].)
(The caller insures len(path) >= 2.)
"""
return "*".join( [ "x%s%s" % ( path[k], path[k+1] ) for k in range(len(path)-1) ] )

def generate_gap_code( poset ):
"""The poset must be a poset of 1, 2, ... , n
where ...
"""
n = len( poset.list() )

covers = poset.cover_relations()
str1_Q = ( 'Q := Quiver( %s, [%s] );'
% ( n,
','.join( [ '[%s,%s,"x%s%s"]' % (j,k,j,k)
for j,k in covers ] )
) )
str2_kQ  = 'kQ := PathAlgebra( Rationals, Q );'
str3_AGV = 'AssignGeneratorVariables( kQ );'

all_chains  = [ ch for ch in poset.chains() if len(ch) >= 2 ]    # you possibly need only == 3
chains      = []    # and we append
for ch in all_chains:
ok = True
for k in range(len(ch)-1):
if [ ch[k], ch[k+1] ] not in covers:
ok = False
break    # the for k loop
if ok:
chains.append( ch )
chains_keys = [ (ch[0], ch[-1]) for ch in chains ]
chains_dic  = dict( [ (key, [ ch
for ch in chains
if  ch[0]==key[0] and ch[-1]==key[-1] ] )
for key in chains_keys
] )
chains_rels = []    # and we append
for key, paths in chains_dic.iteritems():
if len( paths ) <= 1 :    continue
str_prod_for_path0 = str_prod_for_path( paths[0] )
for k in range(1, len(paths)):
str_prod_for_pathk = str_prod_for_path( paths[k] )
chains_rels.append( "%s - %s" % ( str_prod_for_path0 ,
str_prod_for_pathk ) )
str4_rel = 'rels := [ %s ]' % ( ', '.join( chains_rels ) )
str5_A   = 'A := kQ/rels;'

return ( '\n'.join( [ str1_Q  ,
str2_kQ ,
str3_AGV,
str4_rel,
str5_A  ] ) )

print generate_gap_code( P )


produces

Q := Quiver( 5, [[1,2,"x12"],[1,4,"x14"],[2,3,"x23"],[3,5,"x35"],[4,5,"x45"]] );
kQ := PathAlgebra( Rationals, Q );
AssignGeneratorVariables( kQ );
rels := [ x12*x23*x35 - x14*x45 ]
A := kQ/rels;


Comment:

In any comment to the above - if any - please describe first what should be installed in gap to make this or the to-be-final code work. Please give a relevant example with relations that make the difference, so that the lack of specification can be covered by common sense. It does not help to give an example with one relation from a link with an unlabeled picture, that is copied as a second relation. If the really needed posets have only quadratic relations, then specify it! You know what you need, but the question is so general, so that a potential helper gets problems where there aren't any. Is the following poset relevant?

  2
/ \
1   3---6
\   \   \
\   5---8
\ /   /
4---7


Which relations should be extracted from it? It may be, that

    all_chains  = [ ch for ch in poset.chains() if len(ch) >= 2 ]    # you possibly need only == 3


should be simply:

    all_chains  = [ ch for ch in poset.chains() if len(ch) == 3 ]

more

Thank you very much for your answer. I start to read it now. But a small comment on the output: Instead of Q := Quiver( 5, [[1,2,"x12"],[1,4,"x14"],[2,3,"x23"],[3,5,"x35"],[4,5,"x45"]] ); kQ := PathAlgebra( Rationals, Q ); AssignGeneratorVariables( kQ ); [ x12 * x23 * x35 - x14 * x45 ] A := kQ/rel; the output should be Q := Quiver( 5, [[1,2,"x12"],[1,4,"x14"],[2,3,"x23"],[3,5,"x35"],[4,5,"x45"]] ); kQ := PathAlgebra( Rationals, Q ); AssignGeneratorVariables( kQ ); rel:=[ x12 * x23 * x35 - x14 * x45 ]; A := kQ/rel;

So the rel:= was forgotten and the ; after the relations.

( 2017-09-21 12:15:54 -0500 )edit

Thanks, i've changed it... Now there are rels in there.

( 2017-09-21 12:20:58 -0500 )edit

I read your comment. The relations are such that two paths $w_1$ and $w_2$ that start and end at the same points have a relations $w_1 -w_2$. Of course such paths $w_1$ can be the product of an arbitrary large number of arrows (but at least two arrows always). So In your picture, there are 3 commutativity relations: The pentagon 4-1-2-3-5, the rectangle 5-8-6-3 and the rectangle 4-7-8-5. If those commute then of course all larger diagrams also commutative like for example 3-6-5-4-7-8 so it is not necessary to include the commutativty relations from 3-6-5-4-7-8, since they are a consequence of the smaller commutativity relations. You can find the definition of incidence algebras as quiver algebras for example in https://link.springer.com/chapter/10.... on page 3 of the paper.

( 2017-09-21 12:24:55 -0500 )edit

@dan_fulea thanks for the edit. There is still the ; missing behind the rels.

( 2017-09-21 12:29:35 -0500 )edit

As a first step:

sage: p=posets.PentagonPoset()
sage: Q=DiGraph([(x,y,'c'+str(x)+str(y)) for x,y in p.cover_relations()])
sage: Q.path_semigroup().algebra(QQ)
Path algebra of Digraph on 5 vertices over Rational Field


Then you need a general way to pass this path algebra and its elements to gap.

EDIT

Here is a better helper function:

def gap_text(P):
Z = P.relabel()
Z = Z.relabel(lambda s: s+1)
Q = DiGraph([(x,y,'x'+str(x)+str(y)) for x, y in Z.cover_relations()])
SG = Q.path_semigroup()
A = SG.algebra(ZZ)
rels = []
for a, b in Z.relations():
if Q.in_degree(b) > 1 and Q.out_degree(a) > 1:
paths = Q.all_paths(a, b)
if len(paths) > 1:
prod_paths = [A.prod(A(Q.edge_label(pa[i], pa[i+1]))
for i in range(len(pa) - 1))
for pa in paths]
rels += [prod_paths[0] - pi for pi in prod_paths[1:]]
txt0 = 'Q:=Quiver({},{});'.format(Q.num_verts(),[list(e) for e in Q.edges()])
txt1 = 'kQ:=PathAlgebra(Rationals,Q);'
txt2 = 'AssignGeneratorVariables(kQ);'
txt3 = 'rel:={};'.format(rels)
txt4 = 'A:=kQ/rel;'
return (txt0 + txt1 + txt2 + txt3 + txt4).replace("'", '"')


that gives

sage: p=posets.DivisorLattice(6)
sage: gap_text(p)
"Q:=Quiver(4,[(1, 2, 'x12'), (1, 3, 'x13'), (2, 6, 'x26'), (3, 6, 'x36')]);kQ:=PathAlgebra(Rationals,Q);AssignGeneratorVariables(kQ);rel:=[-x13*x36 + x12*x26];A:=kQ/rel;"

more

Thank you, but this wont work I think. The problem is just about putting a poset in SAGE into the form (*) as in the question and then I want to copy the output and work with it in the GAP package QPA.

( 2017-09-21 04:07:38 -0500 )edit

Thank you very much again, but instead of "Q:=Quiver(4,[(1, 2, 'x12'), (1, 3, 'x13'), (2, 6, 'x26'), (3, 6, 'x36')]);kQ:=PathAlgebra(Rationals,Q);AssignGeneratorVariables(kQ);rel:=[-x13 * x36 + x12 * x26];A:=kQ/rel;" the output has to have the form "Q:=Quiver(4,[[1, 2, "x12"], [1, 3, "x13"], [2, 6, "x26"], [3, 6, "x36"]]);kQ:=PathAlgebra(Rationals,Q);AssignGeneratorVariables(kQ);rel:=[-x13 * x36 + x12 * x26];A:=kQ/rel;" The difference is that there are " instead of ' and [ ] instead of ( ) in the definition of Q. But there is also a principal problem: The number of points is 4 so the points should be enumerated from 1 to 4 else QPA is not able to understand it.

( 2017-09-21 11:33:58 -0500 )edit

I have modified my function. There remains the " versus ' issue.

( 2017-09-21 13:15:10 -0500 )edit

@fredericC thanks. In the answer of dan_fulea, he managed to get " in the output. Maybe that helps.

( 2017-09-21 13:29:58 -0500 )edit
1

Just replace ' with " in the output string: return (txt0 + .... + txt4).replace("'", '"').

( 2017-09-21 13:52:17 -0500 )edit

## Stats

Seen: 197 times

Last updated: Sep 21 '17