#16659 closed enhancement (fixed)
Representation theory of finite dimensional associative algebras
Reported by:  virmaux  Owned by:  

Priority:  major  Milestone:  sage6.4 
Component:  algebra  Keywords:  representation theory, days64, sd67 
Cc:  nthiery, ncohen, SimonKing  Merged in:  
Authors:  Aladin Virmaux  Reviewers:  Franco Saliola, Nicolas M. Thiéry 
Report Upstream:  N/A  Work issues:  
Branch:  ff577f3 (Commits, GitHub, GitLab)  Commit:  
Dependencies:  #11111  Stopgaps: 
Description (last modified by )
This ticket implements representation theory methods for a finite dimensional associative algebra A:
 Maximal decomposition of the identity into primitive idempotents if A is semisimple and commutative;
 Maximal decomposition of the identity into a sum of central orthogonal idempotents if A is semi simple;
 Lifting thereof from the semisimple quotient of A;
 Peirce decomposition of A;
 Information on the simple Amod and indecomposable projective Amod, and in particular the Cartan invariant matrix of A.
 projective indecomposable modules (up to multiplicity)
 principal ideals
Also optimizes Algebras.FiniteDimensional.ParentMethods.radical_basis
, and remove now useless cached_product
option since products are always cached.
See #18311 for a follow up.
Change History (106)
comment:1 Changed 7 years ago by
 Branch set to u/virmaux/t/16659
comment:2 Changed 7 years ago by
 Commit set to f94621ef0895e8302f6921301379787cc8db3a3e
comment:3 Changed 7 years ago by
 Commit changed from f94621ef0895e8302f6921301379787cc8db3a3e to a203460edf21c556da86af27a940cea8699f1cc6
comment:4 Changed 7 years ago by
 Commit changed from a203460edf21c556da86af27a940cea8699f1cc6 to b2bb56644c544afeaa9e833cf9f59ae426aa8898
comment:5 Changed 7 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:6 Changed 7 years ago by
 Commit changed from b2bb56644c544afeaa9e833cf9f59ae426aa8898 to f01ecd13d99a669f0f153639223dd31aaf77ad72
comment:7 Changed 7 years ago by
 Commit changed from f01ecd13d99a669f0f153639223dd31aaf77ad72 to 57fbdc00054e7604f933eb89a443fd425f45361a
Branch pushed to git repo; I updated commit sha1. New commits:
57fbdc0  doctest

comment:8 Changed 7 years ago by
 Commit changed from 57fbdc00054e7604f933eb89a443fd425f45361a to d107ce1674e167f22872841da47e548ca0a15872
comment:9 Changed 7 years ago by
 Commit changed from d107ce1674e167f22872841da47e548ca0a15872 to 9486c194cd14207c0135368f3ea1c7102d808f48
Branch pushed to git repo; I updated commit sha1. New commits:
9486c19  projective modules

comment:10 Changed 7 years ago by
 Commit changed from 9486c194cd14207c0135368f3ea1c7102d808f48 to 4efa87753fc20a4fee508943e55c45aa83f03ee2
Branch pushed to git repo; I updated commit sha1. New commits:
4efa877  projective decomposition

comment:11 Changed 7 years ago by
This may be a superfluous comment, but have you taken a look at #12141 (merged 6 months ago) and have you checked that you are not duplicating any of the functionality there? (I'm asking because you seem to work mostly inside sage.categories
and not to interact with sage.algebras
.)
comment:12 Changed 7 years ago by
 Commit changed from 4efa87753fc20a4fee508943e55c45aa83f03ee2 to 44e86063f7f7131ff621f06fd39ac1a7a328eb2f
comment:13 Changed 7 years ago by
pbruin: thanks for the hint, I will definitely check :)
comment:14 Changed 7 years ago by
 Commit changed from 44e86063f7f7131ff621f06fd39ac1a7a328eb2f to 4efa87753fc20a4fee508943e55c45aa83f03ee2
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
comment:15 Changed 7 years ago by
 Commit changed from 4efa87753fc20a4fee508943e55c45aa83f03ee2 to 7cbeb9a0b9a5ba10d7933260d20be29c9f0935fb
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
016cd16  #16340: Revert ReST typo fix in ell_curve_isogeny.py to avoid conflict with other ticket handling it

d147678  Merge branch 'develop=6.4.beta0' into categories/morphismmethods10668

8054997  Merge branch 'categories/morphismmethods10668' into categories/modulemorphisms8678

09964af  Merge branch 'categories/modulemorphisms8678' into t/11111/more_support_for_finite_dimensional_modules_and_algebras_with_basis

195d14e  Merge branch 'public/11111more_support_for_finite_dimensional_modules_and_algebras_with_basis' of trac.sagemath.org:sage into t/11111/more_support_for_finite_dimensional_modules_and_algebras_with_basis

1332742  Merge branch 't/11111' into t/16659

9c4d13d  11111: revert subobjects of algebras

d1fc0a9  11111: the center of a semisimple algebra is semisimple.

c6eebd2  merge 11111

7cbeb9a  16659: renamed, moved some methods to better places

comment:16 Changed 7 years ago by
 Commit changed from 7cbeb9a0b9a5ba10d7933260d20be29c9f0935fb to b6dc4b989f9a749f7e1dc9a58180d04bada88e30
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
737a8f0  16340: improved warnings about the current limitation of the model

282ac4e  16340: fixed typos reported by Darij

1e4418f  Merge branch 'develop' into categories/fullsubcategories16340

314ee44  Merge branch 'categories/fullsubcategories16340' into categories/modulemorphisms8678

6907024  8678: trivial doctest update after merge with develop

9852173  8678: rewrote a few tests introduced by #16296 so that they do not depend on the number of axioms defined in Sage

6136990  See discussion on: https://groups.google.com/d/msg/sagedevel/IT_gI_cx0co/QhxdAZeaJzMJ for details.

ce2a56b  8678: oops, restored accidently deleted increment

b9afad7  Merge branch 'u/nthiery/categories/modulemorphisms8678' of git://trac.sagemath.org/sage into t/16659

b6dc4b9  typos

comment:17 Changed 7 years ago by
 Commit changed from b6dc4b989f9a749f7e1dc9a58180d04bada88e30 to b8161c83cb1713246fb9df530e3993fb141d2d14
Branch pushed to git repo; I updated commit sha1. New commits:
0b4b010  #8678: fixed on_basis in TriangularModuleMoprhism

e24e19c  8678: finalize previous commit; making on_basis and domain optional arguments will be for latter

33463c4  10668: rebase doctest upon the fact that Monoids.Commutative now exists

dc0d1db  8678: removed explicit doctest:xxx: source line number from a doctest

8457690  8678: trivial doctest update after merge with develop

62a28dd  8678: rewrote a few tests introduced by #16296 so that they do not depend on the number of axioms defined in Sage

2b3ee81  Merge branch 'develop = 6.4 beta2' into categories/morphismmethods10668

35664c7  Merge branch 'categories/morphismmethods10668 (including 6.4.beta2)' into categories/modulemorphisms8678

8913c75  Merge branch 'categories/modulemorphisms8678', including 6.4 beta2 into t/11111/more_support_for_finite_dimensional_modules_and_algebras_with_basis

b8161c8  Merge branch 't/11111' into t/16659

comment:18 Changed 7 years ago by
 Commit changed from b8161c83cb1713246fb9df530e3993fb141d2d14 to 60e314ca7b1185ff6eff78f9b8bf74883e059583
Branch pushed to git repo; I updated commit sha1. New commits:
60e314c  undo a stupid error in finite_dimensional_modules_with_basis.matrix

comment:19 Changed 7 years ago by
 Commit changed from 60e314ca7b1185ff6eff78f9b8bf74883e059583 to 7a7edd674d50bea30eaf47683c3c00a6edec87c5
Branch pushed to git repo; I updated commit sha1. New commits:
479fddb  16925: revert SymmetricGroups(...).algebra(...) to just do the standard thing

ce71c74  16925: updated a few doctests according to the previous commit

814b51f  Merge branch 't/16925/revert_symmetricgroup_algebra_change_from__16678' into t/11111/more_support_for_finite_dimensional_modules_and_algebras_with_basis

7a7edd6  Merge branch 't/11111' into t/16659

comment:20 Changed 7 years ago by
 Commit changed from 7a7edd674d50bea30eaf47683c3c00a6edec87c5 to 4a9ea8b0b7c0d2234512eb98d807a6c986d49fdf
Branch pushed to git repo; I updated commit sha1. New commits:
4a9ea8b  16659: took off randomness, doctest

comment:21 Changed 7 years ago by
 Commit changed from 4a9ea8b0b7c0d2234512eb98d807a6c986d49fdf to 496af7b1dd7cb3c2f828fd6eacb171254d24b757
Branch pushed to git repo; I updated commit sha1. New commits:
496af7b  16659: typo + todo

comment:22 Changed 7 years ago by
 Commit changed from 496af7b1dd7cb3c2f828fd6eacb171254d24b757 to 0576a8bb652706451039c6f79e194a42281cb488
Branch pushed to git repo; I updated commit sha1. New commits:
0576a8b  16659: Speedup radical_basis

comment:23 Changed 7 years ago by
 Cc ncohen added
comment:24 Changed 7 years ago by
 Cc SimonKing added
comment:25 Changed 7 years ago by
 Commit changed from 0576a8bb652706451039c6f79e194a42281cb488 to 4dbf8edc7e5f908131573a3766242e68753e100d
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
eca2e12  Cartan invariant matrix for general finite dimension algebras with basis

3f42492  projective modules

8dce511  projective decomposition

f5ad940  16659: renamed, moved some methods to better places

8e37421  typos

c9d52a8  undo a stupid error in finite_dimensional_modules_with_basis.matrix

3d93d31  16659: took off randomness, doctest

bab79b2  16659: typo + todo

c7b81ec  16659: Speedup radical_basis

4dbf8ed  Merge branch 'u/virmaux/t/16659' of git://trac.sagemath.org/sage into t/16659

comment:26 Changed 7 years ago by
 Commit changed from 4dbf8edc7e5f908131573a3766242e68753e100d to 434765db324c0e6da9ddab9dd4b02632d12703f9
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
01e2ec5  Merge branch 'categories/modulemorphisms8678' into categories/finite_dimensional_modules_and_algebras_with_basis11111

ac24f99  11111: trivial category update in doctest

ab18062  11111: axiomlike syntax for Semisimple + minor spacing fixes

515b0f8  11111: removed span method in favor of submodule; use the latter in annihilator; minor doc/formating improvements

9d715e7  11111: doc and formating improvements

9081ef8  11111: is_submodule for submodules with basis

4b3d74c  Merge branch 'develop' into categories/finitelygeneratedmagmas17160

6de563d  Merge branch 'categories/finitelygeneratedmagmas17160 + develop=6.6beta5' into categories/modulemorphisms8678

31a0046  Merge branch 'categories/modulemorphisms8678 + develop = 6.6 beta5' into categories/finite_dimensional_modules_and_algebras_with_basis11111

434765d  Merge branch 't/11111/public/11111more_support_for_finite_dimensional_modules_and_algebras_with_basis' into t/16659/t/16659

comment:27 Changed 7 years ago by
finite_dimensional_algebras_with_basis.py
 the code needs to be cleaned up; for details see http://www.sagemath.org/doc/developer/coding_basics.html#documentationstrings
Product of two elements. INPUT::
 insert an extra line here
 also, change :: to : for INPUT blocks
INPUT::  ``self``, ``right``  two elements
The beginning of descriptions of the inputs is aligned with the I in INPUT.
If B is a SubModuleWithBasis of A, then the multiplication law of B is inherited from the multiplication of A.
The Python and Sage objects should be approperiately wrapped : B
, A
,
:class:`SubModuleWithBasis`
, ...
return p.retract( self.lift() * right.lift())
There should be no space after p.retract(
.
Delete this line:
# x[i,j] = product_on_basis(x,i).coefficient(j)
Delete these lines:
# Old algorithm: + # mat = matrix(self.base_ring(), [ + # [sum(product_on_basis(x,j).coefficient(i) * c + # for i in keys for j,c in product_on_basis(y,i)) for x in keys] + # for y in keys ])
Wrap the A
below in single backticks (for latex output):
Construct the ``side`` Amodule generated by ``a``.
There is some redundancy:
+ sage: A = FiniteDimensionalAlgebrasWithBasis(QQ).example() + sage: A = FiniteDimensionalAlgebrasWithBasis(QQ).example(); A
Add a reference for the algorithm/formula used in _lift_idempotent
.
There are other possibilities one could use here. Is it work implementing
some of these other ones and giving the user a choice between algorithms?
Does Python / Sage prefer !=
to <>
?
to be continued ...
comment:28 Changed 7 years ago by
finite_dimensional_algebras_with_basis.py (part 2)
I think that cartan_invariant_matrix
should be
cartan_invariants_matrix
; update the documentation of this method to read:
Return the matrix of Cartan invariants of ``self``.
In the method cartan_invariant_matrix
, you compute the dimension of the
simple modules, but this is just the cartan invariants for the semisimple
quotient. Perhaps you can use this to clean up the code.
At the very least, I think that the code to compute the dimension of the simple modules should be refactored into a separate method.
``side``sided
should be just ``side``
.
projective_decomposition
> projective_indecomposables
or projective_indecomposable_modules
_cartan_matrix_coef
> _cartan_matrix_coeff
(two fs)
missing documentation string for _cartan_matrix_coeff
Perhaps it is a good idea to define a method called pierce_decomposition
that returns the Pierce decomposition of the algebra; and maybe
pierce_component
? This would simplify _cartan_matrix_coef
.
comment:29 Changed 7 years ago by
semisimple_algebras.py
 The
orthogonal_idempotents
method returns central orthogonal idempotents, so I think that the name of this method should be changed tocentral_orthogonal_idempotents
. For example, in the docstring the exampleSymmetricGroup(3).algebra(QQ)
returns 3 idempotents, but I expected 4.
 Also, this example doesn't work:
sage: A3 = SymmetricGroup(3).algebra(QQ) sage: A3 Symmetric group algebra of order 3 over Rational Field sage: A3.orthogonal_idempotents()  AttributeError Traceback (most recent call last) ... AttributeError: 'list' object has no attribute 'map'
 semisimple vs. semisimple (be consistent)
 in the following, change the names
listGen
,topLevel
to be consistent with Sage coding conventions:+ def _orthogonal_decomposition(self, listGen=None, topLevel=True):
 clean up the documentation of
_orthogonal_decomposition
: the last line ("Return a list...") should be the first line
orthogonal_idempotents
: what is the definition of a "minimal" idempotent?
 should there be a
test_orthogonal_idempotents
method? at the very least, there should be tests to test that the created idempotents are indeed orthogonal, sum to the identity, minimal, ....
comment:30 Changed 7 years ago by
 Reviewers set to Franco Saliola
 Status changed from new to needs_info
comment:31 Changed 7 years ago by
General comments
 There are a few fixes needed to make the code conform to the Sage coding conventions. Things like proper ReST formatting of the documentation, and spaces surrounding operators and comparisons. For example:
len(res)<2
should belen(res) < 2
listGen==[]
should belistGen == []
map( lambda x: x.lift(), res)
should bemap(lambda x: x.lift(), res)
...
 Can you add a description of the algorithm to the documentation string of
_orthogonal_decomposition
? I think it would be helpful to someone reading the code to figure out what it is trying to do.
 Good work! Thanks for implementing this! It will be very useful.
comment:32 Changed 7 years ago by
Hello Franco,
thank you very much for the very precise review. I agree with you on all points.
Unfortunatly the tests with SymmetricGroup.Algebra
don't pass yet, but there is two ways to make them work for now:
 force
SymmetricGroup(n).algebra(field)
to be generic by commenting the good lines in /groups/perm_gps/permgroup_named.py  waiting for #16926 to be in
I am working on it right now and will commit a revision as soon as possible!
Aladin
comment:33 Changed 7 years ago by
 Commit changed from 434765db324c0e6da9ddab9dd4b02632d12703f9 to 1ffc713eae626876785cf26216f5cbfd37ad7a34
Branch pushed to git repo; I updated commit sha1. New commits:
1ffc713  16659: numerous types and refactoring some names

comment:34 Changed 7 years ago by
#16926 is very close from positive review (just waiting for a green light from the patchbot). So feel free to merge it in.
comment:35 Changed 7 years ago by
 Commit changed from 1ffc713eae626876785cf26216f5cbfd37ad7a34 to d196cb30e95cf252116237d400c4d29b1d9fbfa9
Branch pushed to git repo; I updated commit sha1. New commits:
d196cb3  trivial fixes and iterator for Monoids().Finite().example()

comment:36 Changed 7 years ago by
 Commit changed from d196cb30e95cf252116237d400c4d29b1d9fbfa9 to 49e6c0ce330894fada62dde17c468f2eebc51503
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
011e877  Merge branch 'public/combinat/fix_sga16926' of trac.sagemath.org:sage into t/16926/public/combinat/fix_sga16926

23cefb9  16926: trivial doctest updates w.r.t. previous merge.

49307d7  16926: proofreading with Travis

4c3c9e4  I don't think the WeylAlgebra setting is supported enough to be advertised; furthermore the algebra method on nonstandard symmetric groups is fubar

b2069db  use cythonized left/right_action_products in SGA too

655380d  more optimizations

8fe64bf  Merge branch 'public/combinat/fix_sga16926' of trac.sagemath.org:sage into t/16926/public/combinat/fix_sga16926

1f97814  16926: proofread Darij's latest changes

12aaaf8  doctesting the demise of my bug

49e6c0c  Merge branch 't/16926/public/combinat/fix_sga16926' into t/16659/t/16659

comment:37 Changed 7 years ago by
 Commit changed from 49e6c0ce330894fada62dde17c468f2eebc51503 to 45190ac0b91b9025b446ab02f60e66a8c94a6304
comment:38 Changed 7 years ago by
 Commit changed from 45190ac0b91b9025b446ab02f60e66a8c94a6304 to 77d81f10e0118bd0fcfd23a58b5c3178466a80e4
Branch pushed to git repo; I updated commit sha1. New commits:
77d81f1  Merge branch 'develop' into t/16659/t/16659

comment:39 Changed 7 years ago by
 Commit changed from 77d81f10e0118bd0fcfd23a58b5c3178466a80e4 to 8c6759b811a557f51bdf7a568190bef3cf9eaaea
Branch pushed to git repo; I updated commit sha1. New commits:
8c6759b  16659: clean _orthogonal_idempotent

comment:40 Changed 7 years ago by
Hello,
I pushed many modifications according to Franco's review.
Also, #16926 had been merged so the tests all pass.
Aladin
comment:41 Changed 7 years ago by
 Commit changed from 8c6759b811a557f51bdf7a568190bef3cf9eaaea to a12dd254dd3069c67efdc83c3ba0f2836b021269
Branch pushed to git repo; I updated commit sha1. New commits:
a12dd25  Merge branch 'develop' into t/16659/t/16659

comment:42 Changed 7 years ago by
 Commit changed from a12dd254dd3069c67efdc83c3ba0f2836b021269 to 478d5f9d534bfc74537ad1c838ce82f6e2059de1
Branch pushed to git repo; I updated commit sha1. New commits:
478d5f9  16659: orthogonal_idempotents > central_orthogonal_idempotents

comment:43 Changed 7 years ago by
comment:44 Changed 7 years ago by
 Commit changed from 478d5f9d534bfc74537ad1c838ce82f6e2059de1 to 5f34c9e157bff7bda8fa20c396a6eb6114d84190
comment:45 Changed 7 years ago by
 Status changed from needs_info to needs_work
 Work issues set to merge in develop.
comment:46 Changed 7 years ago by
 Branch changed from u/virmaux/t/16659 to u/saliola/t/16659
comment:47 Changed 7 years ago by
 Branch changed from u/saliola/t/16659 to u/nthiery/t/16659
comment:48 Changed 7 years ago by
 Commit changed from 5f34c9e157bff7bda8fa20c396a6eb6114d84190 to 1b531c628e803ae0d841537012cb4255ac1d986a
For the record: all tests passed on sage.math.upsud.fr.
Last 10 new commits:
5b1c869  11111: add doctest: submodule from nonlinearly independent generators

cfe399d  Merge branch 'public/11111more_support_for_finite_dimensional_modules_and_algebras_with_basis' of git://trac.sagemath.org/sage into t/11111

a476501  Merge branch 'public/11111more_support_for_finite_dimensional_modules_and_algebras_with_basis' of trac.sagemath.org:sage into t/11111/more_support_for_finite_dimensional_modules_and_algebras_with_basis

5c6dea2  11111: proofreading of Franco's proofreading

2036314  11111: fixed crosslink + missing file in the ref manual

6a3a07d  11111: doc for CombinatorialFreeModule._order_cmp

b6d8bff  11111: CombinatorialFreeModule.echelon_from > Modules.WithBasis.ParentMethods.echelon_form; removed duplicate echelonize; delete meaningless and dangerous argument base_ring

25881cc  11111: docstring improvement for quotient_module

7fb5d0c  11111: final doc improvements

1b531c6  Merge branch 't/11111/more_support_for_finite_dimensional_modules_and_algebras_with_basis' into t/16659/t/16659

comment:49 Changed 7 years ago by
 Branch changed from u/nthiery/t/16659 to u/virmaux/t/16659
comment:50 Changed 7 years ago by
 Commit changed from 1b531c628e803ae0d841537012cb4255ac1d986a to bd4ee7dd6447a23fbf7f8e68030aac8fa173b532
Branch pushed to git repo; I updated commit sha1. New commits:
bd4ee7d  16659: documentation lift idempotent

comment:51 Changed 7 years ago by
 Commit changed from bd4ee7dd6447a23fbf7f8e68030aac8fa173b532 to 5cfb178721813a2260a5177a9a731e9119033253
Branch pushed to git repo; I updated commit sha1. New commits:
5cfb178  16659: Lift_idempotent now work, more test with 0Hecke, TODO: explanation algorithms

comment:52 Changed 7 years ago by
 Commit changed from 5cfb178721813a2260a5177a9a731e9119033253 to 8f6a8670d2708b960a9f89490a59c76b9099d451
Branch pushed to git repo; I updated commit sha1. New commits:
8f6a867  16659: cleaning lifting, work for real now

comment:53 Changed 7 years ago by
 Branch changed from u/virmaux/t/16659 to u/saliola/t/16659
comment:54 Changed 7 years ago by
 Commit changed from 8f6a8670d2708b960a9f89490a59c76b9099d451 to 7362f035239f8fdbc992888478a9f4b7d102193c
I pushed some changes:
radical_basis
: I removed the optionalcache_products
option since the speed up by Aladin seems not to use this [should be verified by the reviewer]. I also rewrote the code to make it more readable (I hope it is more readable, at least).
principal_ideal
:
(a) I swapped 'left' and 'right', because they were backwards. The principal left ideal generated by
a
isAa
, notaA
. I added doctests to test this.
(b) the implementation only worked for 'triangularizable' algebras (for a suitable definition of triangularizable). I fixed the method to handle the generic case.
central_orthogonal_idempotents
: I added a TESTS section to test that the idempotents constructed in the examples are "idempotents", "orthogonal" and "central". (I didn't run the tests yet though.)
Some of the above changes might break some tests in other parts of the code that rely on it (for example, principal_ideal
).
New commits:
7362f03  16659: some documentation and tests

comment:55 Changed 7 years ago by
 Keywords days64 sd67 added
Here are a few more comments that came up at Sage Days 67.
FiniteDimensionalAlgebrasWithBasis.ParentMethods.central_orthogonal_idempotents
:
 shouldn't this be
orthogonal_idempotents
since they do not belong to the center? Or maybe I don't understand the definition: what is meant by "central"?  there should be a method to also compute the central orthogonal idempotents?
SemisimpleAlgebras.Commutative.ParentMethods._orthogonal_idempotents
:
 these are not idempotents (they are quasiidempotents); the documentation string needs to be updated
Documentation string for Pierce decomposition:
 needs the definition of a Pierce decomposition
e_i A e_j
are *not* submodules or subalgebras in general, but subspaces
Other questions:
 is there a method somewhere to test that a family of idempotents is a minimal family of orthogonal idempotents? if so, then the tests in
orthogonal_idempotents
need to be updated to use it
 is there a method to test whether an idempotent is primitive?
At this point, I'll have little time to work on these over the next couple of weeks, but I will answer questions, if you have any.
comment:56 Changed 7 years ago by
 Branch changed from u/saliola/t/16659 to u/virmaux/t/16659
comment:57 Changed 7 years ago by
 Commit changed from 7362f035239f8fdbc992888478a9f4b7d102193c to abcb076cf7ae487d9a34b690b415df40886fd93f
Branch pushed to git repo; I updated commit sha1. New commits:
abcb076  16659: renaming thanks to Franco's remarks, refactoring lifing_idempotent, documentation

comment:58 Changed 7 years ago by
Hi Franco, thank you for the remarks.
I made some changes after a discussion with Nicolas and Florent:
 Semisimple algebras:
 In the semisimple quotient, the idempotents that we construct are central as they live in the center of the algebra. Unfortunately, lifting those idempotents does not preserve this last property. So I left the name
central_orthogonal_idempotents
for semisimple algebras.  I updated the documentation for
_orthogonal_decomposition
, but maybe we should change the name?
 In the semisimple quotient, the idempotents that we construct are central as they live in the center of the algebra. Unfortunately, lifting those idempotents does not preserve this last property. So I left the name
 Finite dimensional algebras with basis
orthogonal_idempotents
>orthogonal_idempotents_central_mod_rad
because they are obtained by lifting the central_idempotents of the semisimple quotient. As well, we now have a method
lifting_idempotents
instead of a subfunction in the previous method.  Peirce (with the correct spelling) is now splitted in two:
peirce_summand
return a sandwich subspace e_i A e_j and peirce_decomposition return the list of all sandwiches with the orthogonal idempotents lifted from the central ones of the semisimple quotient.
Other questions: The idempotents we get for non semisimple algebra are not primitive. The only primitive idempotents we construct are for commutative semisimple algebras. To test if an idempotent e of A is primitive, we may construct the semisimple quotient of eA and test wether it is a simple module or not. In our finite dimensional case, is it enough to check that all elements of the basis generate the whole module?
comment:59 Changed 7 years ago by
 Commit changed from abcb076cf7ae487d9a34b690b415df40886fd93f to 6f3308a8ce70a2141ab76395b1026afd42292d91
Branch pushed to git repo; I updated commit sha1. New commits:
6f3308a  16659: typo doc

comment:60 Changed 7 years ago by
 Commit changed from 6f3308a8ce70a2141ab76395b1026afd42292d91 to 4d72964f090830c6fa01e98588395136506f9eed
Branch pushed to git repo; I updated commit sha1. New commits:
4d72964  16659: revert radical_basis, documentation

comment:61 followup: ↓ 63 Changed 7 years ago by
I reverted the radical basis. Here is a quick benchmark to show why: Version #11111:
sage: D25 = DihedralGroup(25).algebra(QQ, category=Monoids().Finite()) sage: %time D25.radical() CPU times: user 49.9 s, sys: 84 ms, total: 50 s Wall time: 49.9 s
Version #16659
sage: %time D25.radical() CPU times: user 572 ms, sys: 12 ms, total: 584 ms Wall time: 590 ms
I am currently rewriting a lot of the documentation, I try to finish in the next hours.
comment:62 Changed 7 years ago by
 Commit changed from 4d72964f090830c6fa01e98588395136506f9eed to 06de5188ee34750760d480c1920afcfc1f40408d
Branch pushed to git repo; I updated commit sha1. New commits:
06de518  16659: documentation and typos

comment:63 in reply to: ↑ 61 ; followup: ↓ 64 Changed 7 years ago by
Replying to virmaux:
I reverted the radical basis. Here is a quick benchmark to show why:
That's very convincing!
I'm surprised that there is such a big difference. I just took your method and rewrote it to be easier to read (I wanted to avoid the nested list comprehensions). But speed is more important. :)
comment:64 in reply to: ↑ 63 Changed 7 years ago by
Replying to saliola:
I'm surprised that there is such a big difference. I just took your method and rewrote it to be easier to read (I wanted to avoid the nested list comprehensions). But speed is more important. :)
The main difference is that the reinstated version takes advantage of the sparsity of the products. Of course this makes a bigger difference for a monoid algebra than for an average algebra; so the benchmark is not completely fair. But still, many of our algebras are rather sparse, so that's good.
On another note: I actually tend to find nested list comprehensions more readable than for loops because they highlight the intent. But that's indeed only valid if one does not need to do weird stuff to make it fit into the functional style.
Cheers,
Nicolas
comment:65 Changed 7 years ago by
 Description modified (diff)
 Summary changed from Decomposition of finite dimensional associative algebras to Representation theory of finite dimensional associative algebras
comment:66 Changed 7 years ago by
 Description modified (diff)
comment:67 Changed 7 years ago by
 Branch changed from u/virmaux/t/16659 to public/representation_theory/finite_dimensional_algebras16659
comment:68 Changed 7 years ago by
 Branch changed from public/representation_theory/finite_dimensional_algebras16659 to u/virmaux/t/16659
 Description modified (diff)
 Reviewers changed from Franco Saliola to Franco Saliola, Nicolas M. Thiéry
 Status changed from needs_work to needs_review
 Work issues merge in develop. deleted
comment:69 Changed 7 years ago by
 Branch changed from u/virmaux/t/16659 to public/representation_theory/finite_dimensional_algebras16659
comment:70 Changed 7 years ago by
 Commit changed from 06de5188ee34750760d480c1920afcfc1f40408d to 3a625818273d2f13547e8399c803405c14935a81
comment:71 Changed 7 years ago by
 Commit changed from 3a625818273d2f13547e8399c803405c14935a81 to bf02606324a12c4749f69f8139e9c3bd9d902e7e
Branch pushed to git repo; I updated commit sha1. New commits:
bf02606  16659: is_identity_decomposition_into_orthogonal_idempotents + documentation + implement Monoids.Algebras.algebra_generators from monoid_generators

comment:72 Changed 7 years ago by
 Commit changed from bf02606324a12c4749f69f8139e9c3bd9d902e7e to 0c44982418b96b37731814a0e949471b61270084
Branch pushed to git repo; I updated commit sha1. New commits:
0c44982  17696: use is_identity_decomposition_into_orthogonal_idempotents in the examples

comment:73 Changed 7 years ago by
 Commit changed from 0c44982418b96b37731814a0e949471b61270084 to cba7c8d1adcad21ace893b5827777348c2e486ef
Branch pushed to git repo; I updated commit sha1. New commits:
cba7c8d  17696: factored out of the examples a basic implementation of the 0Hecke monoid

comment:74 Changed 7 years ago by
 Commit changed from cba7c8d1adcad21ace893b5827777348c2e486ef to 6e81e4b500f7698446fd19de792744a33667eafa
Branch pushed to git repo; I updated commit sha1. New commits:
6e81e4b  16659: proofreading and little additions to the doc; small refactoring of the code

comment:75 Changed 7 years ago by
 Commit changed from 6e81e4b500f7698446fd19de792744a33667eafa to 19756de9e9367efc85add11872bbf03d873b948f
Branch pushed to git repo; I updated commit sha1. New commits:
19756de  16659: minor linesplit in the doc

comment:76 Changed 7 years ago by
 Commit changed from 19756de9e9367efc85add11872bbf03d873b948f to fd8e1ad375037e078905ae220bc9e543d65a67be
Branch pushed to git repo; I updated commit sha1. New commits:
fd8e1ad  16659: refactored _orthogonal_decomposition and updated doctests accordingly

comment:77 Changed 7 years ago by
 Commit changed from fd8e1ad375037e078905ae220bc9e543d65a67be to cc327efe6f3a221ae089d68558e5296cc9fc295c
Branch pushed to git repo; I updated commit sha1. New commits:
cc327ef  16659: improved documentation for _orthogonal_decomposition

comment:78 Changed 7 years ago by
 Commit changed from cc327efe6f3a221ae089d68558e5296cc9fc295c to e00dfdb8c49ba0105922aeeabab5bcb234bceaf0
Branch pushed to git repo; I updated commit sha1. New commits:
e00dfdb  16659: improved documentation for _orthogonal_decomposition

comment:79 Changed 7 years ago by
Hi Aladin, Franco, Florent,
I am done going through this ticket, and am happy with its state. Please proofread my changes, and if you are ok with them, I guess this is good to go!
Great job Aladin by the way.
comment:80 Changed 7 years ago by
 Commit changed from e00dfdb8c49ba0105922aeeabab5bcb234bceaf0 to cce7d3db05f6f10fec8c19a055987c61eee4b771
Branch pushed to git repo; I updated commit sha1. New commits:
cce7d3d  17696: added crosslinks

comment:81 followup: ↓ 82 Changed 7 years ago by
Hi Nicolas, thank you very much for these last commits. I agree with the documentation and the refactorisation you made, but I think you forgot to add sage.monoids.hecke_monoid.
comment:82 in reply to: ↑ 81 Changed 7 years ago by
Replying to virmaux:
Hi Nicolas, thank you very much for these last commits. I agree with the documentation and the refactorisation you made, but I think you forgot to add sage.monoids.hecke_monoid.
Oops, fixed! Thanks for the notice!
comment:83 Changed 7 years ago by
There is still no commit with it ;)
comment:84 Changed 7 years ago by
 Commit changed from cce7d3db05f6f10fec8c19a055987c61eee4b771 to faf83a1380dde69c2dfd7849c1b8b8d24dcbecd6
Branch pushed to git repo; I updated commit sha1. New commits:
faf83a1  16659: added missing hecke_monoid.py file

comment:85 Changed 7 years ago by
Gasp. I somehow managed to do the commit on develop. Luckily enough there are securities preventing from pushing there :)
comment:86 Changed 7 years ago by
Aladin, do you think this is good to go, or would you like Franco or Florent to have a last round of checks?
By the way, and just to wet your appetite, I have been working on a
follow up ticket which improves the algorithmic complexity (n^4
to
n^3
for the radical) and further optimizes the code.
Without:
sage: A = HeckeMonoid(SymmetricGroup(5)).algebra(QQ) sage: %time len(A.radical_basis()) CPU times: user 4.25 s, sys: 45.1 ms, total: 4.3 s Wall time: 4.26 s 104 sage: %time A.cartan_invariants_matrix() CPU times: user 45.2 s, sys: 267 ms, total: 45.4 s Wall time: 45.5 s
With:
sage: A = HeckeMonoid(SymmetricGroup(5)).algebra(QQ) sage: %time len(A.radical_basis()) CPU times: user 418 ms, sys: 29.5 ms, total: 447 ms Wall time: 422 ms 104 sage: %time A.cartan_invariants_matrix_by_characters() CPU times: user 9.39 s, sys: 208 ms, total: 9.6 s Wall time: 9.53 s
(in the above, I am *not* using that this is a monoid algebra, though of course the sparsity helps).
Cheers,
Nicolas
comment:87 followup: ↓ 88 Changed 7 years ago by
Hello,
well the code looks fine to me but I definitely think we need an outisde view on it, for example from Franco or Florent.
This optimization on the radical is very exciting :) But maybe it deserves a new ticket ?
Also it would be nice to add examples from the Descent Algebra (NCSF), but the current implementation does not contain a method algebra_generator. It is possible to hack the following way:
sage: D4 = DescentAlgebra(QQ, 4).B() sage: D4.algebra_generators = D4.basis sage: D4.cartan_invariants_matrix() [1 0 0 0 0] [0 1 0 0 0] [0 1 1 0 0] [0 0 0 1 0] [0 1 1 0 1]
I am not sure how to make it proper, should we check in the center
that algebra_generator
returns something useful ? Or should we add this method in descent_algebra.py
for every implemented basis, or should we define in the category to return the basis as default ? Or should we just make a new ticket :) ?
Aladin
comment:88 in reply to: ↑ 87 ; followup: ↓ 90 Changed 7 years ago by
Replying to virmaux:
well the code looks fine to me but I definitely think we need an outisde view on it, for example from Franco or Florent.
Ok!
This optimization on the radical is very exciting :) But maybe it deserves a new ticket ?
It definitely is for a follow up ticket. Especially since I had to do some optimizations on ModulesWithBasis? and friends which deserve a ticket by themselves.
Also it would be nice to add examples from the Descent Algebra (NCSF), but the current implementation does not contain a method algebra_generator. It is possible to hack the following way:
sage: D4 = DescentAlgebra(QQ, 4).B() sage: D4.algebra_generators = D4.basis sage: D4.cartan_invariants_matrix() [1 0 0 0 0] [0 1 0 0 0] [0 1 1 0 0] [0 0 0 1 0] [0 1 1 0 1]I am not sure how to make it proper, should we check in the
center
thatalgebra_generator
returns something useful ? Or should we add this method indescent_algebra.py
for every implemented basis, or should we define in the category to return the basis as default ? Or should we just make a new ticket :) ?
For a finite dimensional algebra with basis, it sounds quite
reasonable to use basis
as default implementation for
algebra_generators
. I believe we can leave that to the follow up
ticket.
Cheers,
Nicolas
comment:89 Changed 7 years ago by
 Description modified (diff)
comment:90 in reply to: ↑ 88 ; followup: ↓ 91 Changed 7 years ago by
Replying to nthiery:
Replying to virmaux:
well the code looks fine to me but I definitely think we need an outisde view on it, for example from Franco or Florent.
Ok!
I would love to take a look at the code and play around with it a bit more. I can do it by Friday, if you don't mind waiting until then.
Franco
comment:91 in reply to: ↑ 90 Changed 7 years ago by
Replying to saliola:
I would love to take a look at the code and play around with it a bit more. I can do it by Friday, if you don't mind waiting until then.
Sure thing! Thanks in advance.
comment:92 Changed 7 years ago by
comment:93 followups: ↓ 94 ↓ 95 Changed 7 years ago by
Check it out! I'm actually accomplishing this by my selfimposed deadline. It's rare when this happens. :)
 First of all, this looks great! I only have a few comments / questions.
orthogonal_idempotents_central_mod_rad
: Isn't this the same thing as a complete set of primitive orthogonal idempotent? If so then I suggest the namecomplete_set_of_primitive_orthogonal_idempotents
. I think this is the standard name in the literature. Maybe I'm missing something? (If we stick with the original name, then I suggestradical
instead ofrad
; the name is long so a few more characters won't be a problem)
idempotent_lift
: there are other possible lifts one could use here. Is it worth implementing some of these others and giving the user a choice? (doesn't have to be done on this ticket; just something I'd like to hear about)
cartan_invariants_matrix
: in the documentation it is written thatS_i
and their adjointsS_i^*
are representatives of the right simple modules; did you mean left for the latter?
 Tests: All tests passed!
Positive review pending the change of right
to left
for S_i^*
.
comment:94 in reply to: ↑ 93 Changed 7 years ago by
Replying to saliola:
idempotent_lift
: there are other possible lifts one could use here. Is it worth implementing some of these others and giving the user a choice? (doesn't have to be done on this ticket; just something I'd like to hear about)
For instance, it seems that one can iterate the formula 3 * a^2  2 * a^3
to lift the idempotents. See Lemma 1.7.3 (Idempotent Refinement) of Benson's 'Representations and Cohomology I (search for refinement).
comment:95 in reply to: ↑ 93 Changed 7 years ago by
Replying to saliola:
Check it out! I'm actually accomplishing this by my selfimposed deadline. It's rare when this happens. :)
Quite impressed, I am!
:)
 First of all, this looks great! I only have a few comments / questions.
Thanks, and thanks for the review!
orthogonal_idempotents_central_mod_rad
: Isn't this the same thing as a complete set of primitive orthogonal idempotent?
Nope; in the case of a full nxn matrix algebra (which is semisimple,
so mod rad or not are the same), we get a single idempotent: the
identity; to get primitive idempotents, we would need to refine this
trivial decomposition into n
orthogonal idempotents.
In general, for each simple module of dim k, we get a single idempotent e such that eAe is the k x k block matrix corresponding to the simple module.
We haven't found a good name for those idempotents in the literature; suggestions welcome!
(If we stick with the original name, then I suggest
radical
instead ofrad
; the name is long so a few more characters won't be a problem)
Will do!
idempotent_lift
: there are other possible lifts one could use here. Is it worth implementing some of these others and giving the user a choice? (doesn't have to be done on this ticket; just something I'd like to hear about)
If we have a use case for it, that is if the various lifting have each some specific merit, then why not. For a latter ticket indeed.
cartan_invariants_matrix
: in the documentation it is written thatS_i
and their adjointsS_i^*
are representatives of the right simple modules; did you mean left for the latter?
Oops. Will fix now!
Cheers,
Nicolas
comment:96 Changed 7 years ago by
 Commit changed from faf83a1380dde69c2dfd7849c1b8b8d24dcbecd6 to 661c008e33f1384e9875bd500c148943988d580b
comment:97 Changed 7 years ago by
 Status changed from needs_review to positive_review
comment:98 followup: ↓ 103 Changed 7 years ago by
 Status changed from positive_review to needs_work
Overfull \hbox (49.85445pt too wide) in paragraph at lines 4444144442 \T1/ptm/m/n/10 Bases: \T1/pcr/m/n/10 sage.categories.category_with_axiom.Catego ryWithAxiom_over_base_ring ! LaTeX Error: Too deeply nested. See the LaTeX manual or LaTeX Companion for explanation. Type H <return> for immediate help. ... l.44470 \begin{itemize} ? > ! Emergency stop. ... l.44470 \begin{itemize} ! ==> Fatal error occurred, no output PDF file produced! Transcript written on categories.log.
comment:99 followup: ↓ 100 Changed 7 years ago by
Easiest way to fix this is probably to just pull out SemisimpleAlgebras.FiniteDimensional.WithBasis
into a separate class (it seems big enough to warrant this anyways IMO).
comment:100 in reply to: ↑ 99 Changed 7 years ago by
Good morning Travis,
Replying to tscrim:
Easiest way to fix this is probably to just pull out
SemisimpleAlgebras.FiniteDimensional.WithBasis
into a separate class (it seems big enough to warrant this anyways IMO).
Perfect, that's exactly what I was working on :)
Great minds ...
comment:101 Changed 7 years ago by
 Commit changed from 661c008e33f1384e9875bd500c148943988d580b to ff577f3fa9cfdd5246c5e57f4427a1888b2654ef
comment:102 Changed 7 years ago by
 Status changed from needs_work to needs_review
Done!
All long tests pass in sage/categories, and the pdf doc compiles. I haven't made any change besides moving the code, and adding the usual file/class docstrings, lazy imports, and addition to the ref manual. If someone can briefly double check those, I believe this can be set back to positive review.
comment:103 in reply to: ↑ 98 Changed 7 years ago by
Replying to vbraun:
! LaTeX Error: Too deeply nested.
Thanks Volker for the report, and sorry for not having compiled the pdf doc!
To reduce the risk of this happening again, I have posted a feature request for the patchbot to build and report on the pdf doc:
https://github.com/robertwb/sagepatchbot/issues/64
Cheers,
Nicolas
comment:104 Changed 7 years ago by
 Status changed from needs_review to positive_review
comment:105 Changed 7 years ago by
 Branch changed from public/representation_theory/finite_dimensional_algebras16659 to ff577f3fa9cfdd5246c5e57f4427a1888b2654ef
 Resolution set to fixed
 Status changed from positive_review to closed
comment:106 Changed 7 years ago by
 Commit ff577f3fa9cfdd5246c5e57f4427a1888b2654ef deleted
Thanks Franco and Volker for this final step!
Yeah, this is done! One more big feature of MuPADCombinat that is in Sage :)
Branch pushed to git repo; I updated commit sha1. New commits:
indentation