Add representations of quivers and quiver algebras to sage

[sagetrac-JStarx]

This will add classes dealing with quivers, quiver algebras, representations of quivers, elements of these representations, homomorphisms between these representations, and spaces of homomorphisms between these representations.

There's a lot here that is really easily computable. We can compute socles, quotients, radicals, duals, and more for any finite dimensional representation. We can compute projective covers of modules so Auslander-Rieten translations have been implemented and there's certainly potential for future enhancements dealing with homology and cohomology. There's only so much I can say here but everything is fully documented and should be self explanatory.

Two shortcomings are that quivers need to be acyclic (to keep things finite dimensional) and this code does not handle quivers with relations. As far as quivers with relations go there are comments in the code detailing what should be done to implement that. It's well within the reach of Sage, I just don't have the time to do it at the moment.

About the commits

The second commit is supposed to split the code into chewable bits (so that maintenance and cythonization will become easier), introduces a parent structure for the paths of a quiver (namely: a free small category), makes paths inherit from Element (but not from UniqueRepresentation!) and fixes some tests. The third commit uses Sage's infrastructure for morphisms and homsets of representations, and it reduces the pollution of the global namespace.

Depends on #12412
Depends on #12413
Depends on #14806
Depends on #15491
Depends on #15623
Depends on #15810

CC: @jhpalmieri @williamstein @stumpc5 @saliola @simon-king-jena @sagetrac-gmoose05 @sagetrac-drupel @mguaypaq @nthiery @avirmaux @nathanncohen

Component: algebra

Keywords: algebra, quiver, module, days49

Author: Jim Stark, Simon King, Mathieu Guay-Paquet, Aladin Virmaux

Branch: f3402ef

Reviewer: Simon King, Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/12630

[stumpc5]

comment:2

I just had a quick look at the patch, it seems to be very complete - thanks!

We are currently slowly getting a large project into sage dealing with (the combinatorics of) cluster algebras and quivers, see #10298. In particular, we also have a class quiver (#10538). I think both classes should be merged as they both deal with acyclic quivers. To be more precice, we deal with skew-symmetrizable matrices and the corresponding labeled quivers, while you seem to focus on the simply-laced version.

I can definitely to the review for this patch, and I propose to sit down (virtually together) and merge both concepts. This means make one being dependent of the other.

I also want to remark that Franco Saliola has as well quite some code on quiver representations that we might want to merge (if it is not subsumed). We also have currently a project of implementing the knitting algorithm for quivers without cycles which is currently based on Franco's implementation.

[stumpc5]

Changed dependencies from 12412, 12413 to #12412, #12413

[saliola]

comment:4

JStarx, are you coming to Sage Days 38? One of the themes is this sort of thing.

• Wiki page for Sage Days 38
• Official webpage (for registration and funding requests)

[sagetrac-JStarx]

comment:5

Correct me if I'm wrong, but my understanding is that a simply-laced quiver is a quiver whose underlying undirected graph is Dynkin type A, D, or E. If this is what you meant then no, this patch doesn't focus on simply-laced quivers. Any finite acyclic quiver is allowed, it could have multiple edges, be disconnected, it doesn't need to be Dynkin or even affine Dynkin.

Also it's important that the quivers in my patch have unique representation in Sage because they are part of the defining data of a parent, whereas the point of the combinat quivers is that they can be mutated. So I'm not sure combining the two classes makes sense. I would be very interested in what Simon has to say about this (and in general about my patch) from an algebra/representation theory perspective, as I'm pretty new to Sage development.

Franco: I hadn't really considered the possibility till now. But with funding I would definitely be able to come. I'll go ahead and apply.

[stumpc5]

comment:6

Replying to @sagetrac-JStarx:

Correct me if I'm wrong, but my understanding is that a simply-laced quiver is a quiver whose underlying undirected graph is Dynkin type A, D, or E. If this is what you meant then no, this patch doesn't focus on simply-laced quivers. Any finite acyclic quiver is allowed, it could have multiple edges, be disconnected, it doesn't need to be Dynkin or even affine Dynkin.

Starting with any quiver, you can construct a skew-symmetric matrix (m_{i,j}) with m_{i,j} is the number of edges from i to j minus the number of edges from j to i (one is always supposed to be 0). That's what I meant with simply-laced. One can also think of quivers (like in type B) coming from a skew-symmetrizable matrix (i.e., M such that DM is skew-symmetric for a positive diagonal matrix D), where the edges are labeled (m_{i,j},m_{j,i}). Our "combinatorial quiver" can be construced for any skew-symmetrizable matrix (not in any way restriced to finite or affine types).

Also it's important that the quivers in my patch have unique representation in Sage because they are part of the defining data of a parent, whereas the point of the combinat quivers is that they can be mutated. So I'm not sure combining the two classes makes sense.

This might be right. We could also think of two classes "Quiver" and "CombinatorialQuiver" (as your construction is really the one Gabriel named quiver), and then having maps between them. Can you think of any interaction between the two concepts (like mutating in sinks and sources corresponds in finite types to picking a particular Coxeter element, which corresponds to picking a particular Auslander-Reiten quiver -- we are also currently preparing a paper where we give an alternative combinatorial view on Auslander-Reiten translates in finite types -- any further ideas, maybe beyond finite types)?

Best, Christian

[sagetrac-JStarx]

comment:7

Unfortunately I'm no expert on Auslander-Reiten theory, but I think the idea of two separate classes with an easy way of converting makes sense. I also think the conversions should be very easy to do, as both classes can already take a DiGraph as input.

I think the easiest way to work this would be to go ahead and get both patches into Sage independently. After that happens it would only take a minor tweak to make the constructors accept Quivers of the other type as input.

[simon-king-jena]

comment:8

Replying to @sagetrac-JStarx:

Unfortunately I'm no expert on Auslander-Reiten theory, but I think the idea of two separate classes with an easy way of converting makes sense. I also think the conversions should be very easy to do, as both classes can already take a DiGraph as input.

I think the easiest way to work this would be to go ahead and get both patches into Sage independently. After that happens it would only take a minor tweak to make the constructors accept Quivers of the other type as input.

That approach makes sense to me. By the way: For my own work (computing ext algebras of basic algebras), I'd need finite dimensional quotients of quiver algebras with cycles. So, for now, I think I have to rely on my own implementation.

[saliola]

comment:9

Replying to @sagetrac-JStarx:

Franco: I hadn't really considered the possibility till now. But with funding I would definitely be able to come. I'll go ahead and apply.

I'm glad that you are considering it. I think you'd make a great fit. Christian is coming as well.

Maybe we can convince Simon to come also?

[loefflerd]

Reviewer: PatchBot

[loefflerd]

Work Issues: doctest failure

[loefflerd]

comment:10

A doctest fails on 5.0.beta7:

sage -t  -force_lib devel/sage-12630/sage/modules/quiver_module.py
**********************************************************************
File "/storage/masiao/sage-5.0.beta7-patchbot/devel/sage-12630/sage/modules/quiver_module.py", line 2235:
    sage: y
Expected:
    b + a
Got:
    a + b
**********************************************************************

It looks pretty harmless, but please check it out anyway.

[sagetrac-JStarx]

comment:11

I added comparisons to the QuiverPath class and CombinatorialFreeModuleElement should use should now use those comparisons to determine the order that monomials are printed in. I think previously the order was based on the id of the elements which explains why the patchbot could be getting different output then I was.

[sagetrac-JStarx]

Changed work issues from doctest failure to none

[sagetrac-JStarx]

Changed author from JStarx to Jim Stark

[sagetrac-JStarx]

Changed reviewer from PatchBot to none

[fchapoton]

comment:12

There is one error in the tests, that has to be corrected, see the bot report.

Please also remove all trailing whitespaces (there seems to be many..)

[tscrim]

comment:255

I've made my pass through it. The first half of the commits are adding the files to the doc and doing doc formatting (and 80 width lines). I've made three changes:

1. There was a bug in the all_paths() method would consider a single edge from 1 -> 2 with label 'abc' as 3 edges. Fixed.
2. For a path algebra A, the A[1] worked. So list(A) would not error out (in fact, it would run for forever). I added an __iter__() so that it would iterate over the non-zero graded components.
3. I made alias for S as simple for a more natural name. Similarly injective and projective for I and P respectively.

If you're happy with my changes, then I believe we can set this to a positive review.

[tscrim]

Changed reviewer from Simon King to Simon King, Travis Scrimshaw

[simon-king-jena]

comment:256

Replying to @tscrim:

I've made my pass through it.

Thank you very much!

The first half of the commits are adding the files to the doc and doing doc formatting (and 80 width lines).

Wait, did I really forget to include the new modules in the reference manual?? Strange.

If you're happy with my changes, then I believe we can set this to a positive review.

I'll have a look. Do all tests pass? Shall I re-test it?

[simon-king-jena]

comment:257

Replying to @sagetrac-git:

Branch pushed to git repo; I updated commit sha1. New commits:

81b351c

Merge branch 'public/combinat/quivers' of trac.sagemath.org:sage into public/combinat/quivers

What does this one do? What kind of merge was done there? Can I assume that this is nothing more but moving the existing code into another branch?

[simon-king-jena]

comment:258

Replying to @sagetrac-git:

16fa7c8	Added files to documentation.

Is this how modules are added to the docs nowadays (:doc:`Quviers <quivers/index>`)? I didn't know that.

[simon-king-jena]

comment:259

Could you elaborate on src/doc/en/reference/quivers/conf.py? Again, this is something I don't know from when I have worked on the docs last time. I.e.: Can you please give me a pointer to a place in the developers guide or another piece of documentation, explaining how to add to the docs?

[simon-king-jena]

comment:260

I get this error when building the doc ('make doc-clean' followed by 'make').

OSError: [quivers  ] /home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/quivers/representation.py:docstring of sage.quivers.representation:13: ERROR: Unknown target name: "e".

[simon-king-jena]

comment:261

Aha!! I think it complains about this:

- each edge of the quiver is labelled with a nonempty string.  The label cannot
  begin with 'e_' or contain '*' and distinct edges must have distinct labels.

Perhaps the 'e_' should be enclosed in double backticks?

[simon-king-jena]

comment:262

I agree with your changes, modulo the problem mentioned in the previous comment. Provided that the documentation builds and the tests pass, I'll post a fix for the 'e_' problem and set it to positive review.

[sagetrac-git]

Changed commit from b628ce3 to f3402ef

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

f3402ef

Make documentation of quivers/representation.py build

[simon-king-jena]

comment:264

Documentation does build, hence, I pushed the (presumably final) commit and will now wait for the test results.

---

New commits:

f3402ef

Make documentation of quivers/representation.py build

[simon-king-jena]

comment:265

All tests pass! Hence, I suppose I can turn this into "positive review".

Thank you very much, to all contributors!

[nthiery]

comment:266

Yeah! Congratulations Simon!

[tscrim]

comment:267

Thanks Simon. The first commit was me merging the branch into my own (based off the current develop). As for the conf.py, I just copied what was done in other folders (and at some point I realized it was needed, but I don't remember when). And all tests pass for me.

[vbraun]

Changed branch from public/combinat/quivers to f3402ef

[nthiery]

Changed commit from f3402ef to none

[nthiery]

comment:270

Hi!

With #15801 and this ticket, I am getting the following error:

        sage: Q = DiGraph({1:{3:['a']}, 2:{3:['b']}}).path_semigroup()
        sage: spaces = {1: QQ^2, 2: QQ^3, 3: QQ^2}
        sage: maps = {(1, 3, 'a'): (QQ^2).Hom(QQ^2).identity(), (2, 3, 'b'): [[1, 0], [0, 0], [0, 0]]}
        sage: M = Q.representation(QQ, spaces, maps)
	sage: TestSuite(M).run()
	Failure in _test_category:
	...
	The following tests failed: _test_category

And indeed:

sage: M in M.category()
False

This is due to the following (apparent?) inconsistency:

sage: M.category().base_ring()
Path algebra of Multi-digraph on 3 vertices over Rational Field
sage: M.base_ring()
Rational Field

Question: which one do we want to change?

Cheers,
Nicolas

[simon-king-jena]

comment:271

We have

sage: M = QQ['t']^3
sage: M.base()
Univariate Polynomial Ring in t over Rational Field
sage: M.base_ring()
Univariate Polynomial Ring in t over Rational Field

So, for consistency, I think we want that the base ring is the path algebra.

But, please fix this in #15801 and not here, as this ticket is closed already.

[nthiery]

comment:272

Replying to @simon-king-jena:

So, for consistency, I think we want that the base ring is the path algebra.

Ok.

But, please fix this in #15801 and not here, as this ticket is closed already.

I agree the fix belongs to a followup ticket, and I am fine putting it
in #15801. Would you have a chance to handle it though? I had a quick
try, and am not sure of the repercussions: in particular, to avoid
ambiguities, should the current _base_ring attribute and the
associated base_ring method be renamed to something like
base_ring_of_representation?

I fixed the docbuilding issues in #10963/#15801, and the latter is
fair game for you if you feel like it.

Cheers,
Nicolas

[darijgr]

comment:273

Personally, I disagree (noncommutative base rings scare me, even as a noncommutative algebraist), but this is a tough question. For me, the base ring is the ring everything in sight is linear over (including noncanonical splittings and other auxiliary constructs). Whether QQ or QQ['t'] is the base ring of QQ['t']^3 should really be up to the user to decide, not up to Sage; it depends on what one is doing. It being an attribute is a structural weakness of Sage that will bite us if we start doing serious algebra.

[nthiery]

comment:274

Thinking twice about my first feelings ... For a quiver
representation, I would also tend to have base_ring return QQ above,
and the rep be accordingly in Modules(QQ). So far, in Sage,
Modules(R) is about which ring R we do the linear algebra with, compute
bases, etc. Later on we will have a proper hierarchy of categories for
representations (well, I have some stuff in the Sage-Combinat queue),
and then it will be time to put the quiver representations in the
appropriate category of this hierarchy.

The case of QQ[x]^3 is a bit different, since we really do the
linear algebra over QQ[x].

No strong opinion though ...