Ask Your Question

Incidence algebras in QPA via SAGE

asked 2017-09-20 16:49:28 -0500

maresage gravatar image

updated 2017-09-21 13:03:38 -0500

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 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 (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 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)


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 flag offensive close merge delete

3 answers

Sort by » oldest newest most voted

answered 2017-09-20 17:56:48 -0500

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 to get

Or you can search from within Sage:

sage: search_src('incidence algebra')
edit flag offensive delete link 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.

maresage gravatar imagemaresage ( 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)) );" )

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

dan_fulea gravatar imagedan_fulea ( 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.

maresage gravatar imagemaresage ( 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
dan_fulea gravatar imagedan_fulea ( 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.

John Palmieri gravatar imageJohn Palmieri ( 2017-09-20 20:18:39 -0500 )edit

answered 2017-09-21 12:10:01 -0500

dan_fulea gravatar image

updated 2017-09-21 12:19:29 -0500

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 ,
                          str5_A  ] ) )

print generate_gap_code( P )


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;


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?

 / \
1   3---6
 \   \   \
  \   5---8
   \ /   /

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 ]
edit flag offensive delete link 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.

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

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

dan_fulea gravatar imagedan_fulea ( 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 on page 3 of the paper.

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

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

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

answered 2017-09-21 02:18:00 -0500

FrédéricC gravatar image

updated 2017-09-21 15:22:20 -0500

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.


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 = [[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;"
edit flag offensive delete link 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.

maresage gravatar imagemaresage ( 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.

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

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

FrédéricC gravatar imageFrédéricC ( 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.

maresage gravatar imagemaresage ( 2017-09-21 13:29:58 -0500 )edit

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

John Palmieri gravatar imageJohn Palmieri ( 2017-09-21 13:52:17 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2017-09-20 16:49:28 -0500

Seen: 130 times

Last updated: Sep 21