Opened 7 years ago

Closed 6 years ago

Last modified 6 years ago

#16659 closed enhancement (fixed)

Representation theory of finite dimensional associative algebras

Reported by: virmaux Owned by:
Priority: major Milestone: sage-6.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:

Status badges

Description (last modified by nthiery)

This ticket implements representation theory methods for a finite dimensional associative algebra A:

  • Maximal decomposition of the identity into primitive idempotents if A is semi-simple 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 A-mod and indecomposable projective A-mod, 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 virmaux

  • Branch set to u/virmaux/t/16659

comment:2 Changed 7 years ago by git

  • Commit set to f94621ef0895e8302f6921301379787cc8db3a3e

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

f94621eindentation

comment:3 Changed 7 years ago by git

  • Commit changed from f94621ef0895e8302f6921301379787cc8db3a3e to a203460edf21c556da86af27a940cea8699f1cc6

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

f0bb894_mul_ at the right place
a3b0987Merge branch 't/11111/public/11111-more_support_for_finite_dimensional_modules_and_algebras_with_basis' into t/16659
a203460tests

comment:4 Changed 7 years ago by git

  • Commit changed from a203460edf21c556da86af27a940cea8699f1cc6 to b2bb56644c544afeaa9e833cf9f59ae426aa8898

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

75e4f5a_lift_idempotent for elements of sub-algebras
7caba0dorthogonal idempotents for semisimple algebras
8aa7db9tests
b2bb566beginning of implemantation for general algebras

comment:5 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:6 Changed 7 years ago by git

  • Commit changed from b2bb56644c544afeaa9e833cf9f59ae426aa8898 to f01ecd13d99a669f0f153639223dd31aaf77ad72

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

a156a1eradical for SemisimpleAlgebras
ebb8cb5example
f01ecd1orthogonal idempotents for all finitedimensional algebras with basis

comment:7 Changed 7 years ago by git

  • Commit changed from f01ecd13d99a669f0f153639223dd31aaf77ad72 to 57fbdc00054e7604f933eb89a443fd425f45361a

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

57fbdc0doctest

comment:8 Changed 7 years ago by git

  • Commit changed from 57fbdc00054e7604f933eb89a443fd425f45361a to d107ce1674e167f22872841da47e548ca0a15872

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

aa1a19cexample lift_idempotent
d107ce1Cartan invariant matrix for general finite dimension algebras with basis

comment:9 Changed 7 years ago by git

  • Commit changed from d107ce1674e167f22872841da47e548ca0a15872 to 9486c194cd14207c0135368f3ea1c7102d808f48

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

9486c19projective modules

comment:10 Changed 7 years ago by git

  • Commit changed from 9486c194cd14207c0135368f3ea1c7102d808f48 to 4efa87753fc20a4fee508943e55c45aa83f03ee2

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

4efa877projective decomposition

comment:11 Changed 7 years ago by pbruin

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 git

  • Commit changed from 4efa87753fc20a4fee508943e55c45aa83f03ee2 to 44e86063f7f7131ff621f06fd39ac1a7a328eb2f

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

fe0dfcamerge
44e8606merge conflict

comment:13 Changed 7 years ago by virmaux

pbruin: thanks for the hint, I will definitely check :)

comment:14 Changed 7 years ago by git

  • 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 git

  • 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
d147678Merge branch 'develop=6.4.beta0' into categories/morphism-methods-10668
8054997Merge branch 'categories/morphism-methods-10668' into categories/module-morphisms-8678
09964afMerge branch 'categories/module-morphisms-8678' into t/11111/more_support_for_finite_dimensional_modules_and_algebras_with_basis
195d14eMerge branch 'public/11111-more_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
1332742Merge branch 't/11111' into t/16659
9c4d13d11111: revert subobjects of algebras
d1fc0a911111: the center of a semisimple algebra is semisimple.
c6eebd2merge 11111
7cbeb9a16659: renamed, moved some methods to better places

comment:16 Changed 7 years ago by git

  • Commit changed from 7cbeb9a0b9a5ba10d7933260d20be29c9f0935fb to b6dc4b989f9a749f7e1dc9a58180d04bada88e30

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

737a8f016340: improved warnings about the current limitation of the model
282ac4e16340: fixed typos reported by Darij
1e4418fMerge branch 'develop' into categories/full-subcategories-16340
314ee44Merge branch 'categories/full-subcategories-16340' into categories/module-morphisms-8678
69070248678: trivial doctest update after merge with develop
98521738678: rewrote a few tests introduced by #16296 so that they do not depend on the number of axioms defined in Sage
6136990See discussion on: https://groups.google.com/d/msg/sage-devel/IT_gI_cx0co/QhxdAZeaJzMJ for details.
ce2a56b8678: oops, restored accidently deleted increment
b9afad7Merge branch 'u/nthiery/categories/module-morphisms-8678' of git://trac.sagemath.org/sage into t/16659
b6dc4b9typos

comment:17 Changed 7 years ago by git

  • Commit changed from b6dc4b989f9a749f7e1dc9a58180d04bada88e30 to b8161c83cb1713246fb9df530e3993fb141d2d14

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

0b4b010#8678: fixed on_basis in TriangularModuleMoprhism
e24e19c8678: finalize previous commit; making on_basis and domain optional arguments will be for latter
33463c410668: rebase doctest upon the fact that Monoids.Commutative now exists
dc0d1db8678: removed explicit doctest:xxx: source line number from a doctest
84576908678: trivial doctest update after merge with develop
62a28dd8678: rewrote a few tests introduced by #16296 so that they do not depend on the number of axioms defined in Sage
2b3ee81Merge branch 'develop = 6.4 beta2' into categories/morphism-methods-10668
35664c7Merge branch 'categories/morphism-methods-10668 (including 6.4.beta2)' into categories/module-morphisms-8678
8913c75Merge branch 'categories/module-morphisms-8678', including 6.4 beta2 into t/11111/more_support_for_finite_dimensional_modules_and_algebras_with_basis
b8161c8Merge branch 't/11111' into t/16659

comment:18 Changed 7 years ago by git

  • Commit changed from b8161c83cb1713246fb9df530e3993fb141d2d14 to 60e314ca7b1185ff6eff78f9b8bf74883e059583

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

60e314cundo a stupid error in finite_dimensional_modules_with_basis.matrix

comment:19 Changed 7 years ago by git

  • Commit changed from 60e314ca7b1185ff6eff78f9b8bf74883e059583 to 7a7edd674d50bea30eaf47683c3c00a6edec87c5

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

479fddb16925: revert SymmetricGroups(...).algebra(...) to just do the standard thing
ce71c7416925: updated a few doctests according to the previous commit
814b51fMerge branch 't/16925/revert_symmetricgroup_algebra_change_from__16678' into t/11111/more_support_for_finite_dimensional_modules_and_algebras_with_basis
7a7edd6Merge branch 't/11111' into t/16659

comment:20 Changed 7 years ago by git

  • Commit changed from 7a7edd674d50bea30eaf47683c3c00a6edec87c5 to 4a9ea8b0b7c0d2234512eb98d807a6c986d49fdf

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

4a9ea8b16659: took off randomness, doctest

comment:21 Changed 7 years ago by git

  • Commit changed from 4a9ea8b0b7c0d2234512eb98d807a6c986d49fdf to 496af7b1dd7cb3c2f828fd6eacb171254d24b757

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

496af7b16659: typo + todo

comment:22 Changed 7 years ago by git

  • Commit changed from 496af7b1dd7cb3c2f828fd6eacb171254d24b757 to 0576a8bb652706451039c6f79e194a42281cb488

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

0576a8b16659: Speedup radical_basis

comment:23 Changed 7 years ago by virmaux

  • Cc ncohen added

comment:24 Changed 7 years ago by SimonKing

  • Cc SimonKing added

comment:25 Changed 6 years ago by git

  • Commit changed from 0576a8bb652706451039c6f79e194a42281cb488 to 4dbf8edc7e5f908131573a3766242e68753e100d

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

eca2e12Cartan invariant matrix for general finite dimension algebras with basis
3f42492projective modules
8dce511projective decomposition
f5ad94016659: renamed, moved some methods to better places
8e37421typos
c9d52a8undo a stupid error in finite_dimensional_modules_with_basis.matrix
3d93d3116659: took off randomness, doctest
bab79b216659: typo + todo
c7b81ec16659: Speedup radical_basis
4dbf8edMerge branch 'u/virmaux/t/16659' of git://trac.sagemath.org/sage into t/16659

comment:26 Changed 6 years ago by git

  • Commit changed from 4dbf8edc7e5f908131573a3766242e68753e100d to 434765db324c0e6da9ddab9dd4b02632d12703f9

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

01e2ec5Merge branch 'categories/module-morphisms-8678' into categories/finite_dimensional_modules_and_algebras_with_basis-11111
ac24f9911111: trivial category update in doctest
ab1806211111: axiom-like syntax for Semisimple + minor spacing fixes
515b0f811111: removed span method in favor of submodule; use the latter in annihilator; minor doc/formating improvements
9d715e711111: doc and formating improvements
9081ef811111: is_submodule for submodules with basis
4b3d74cMerge branch 'develop' into categories/finitely-generated-magmas-17160
6de563dMerge branch 'categories/finitely-generated-magmas-17160 + develop=6.6beta5' into categories/module-morphisms-8678
31a0046Merge branch 'categories/module-morphisms-8678 + develop = 6.6 beta5' into categories/finite_dimensional_modules_and_algebras_with_basis-11111
434765dMerge branch 't/11111/public/11111-more_support_for_finite_dimensional_modules_and_algebras_with_basis' into t/16659/t/16659

comment:27 Changed 6 years ago by saliola

finite_dimensional_algebras_with_basis.py

                 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`` A-module 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 6 years ago by saliola

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 6 years ago by saliola

semisimple_algebras.py

  • The orthogonal_idempotents method returns central orthogonal idempotents, so I think that the name of this method should be changed to central_orthogonal_idempotents. For example, in the docstring the example SymmetricGroup(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. semi-simple (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 6 years ago by saliola

  • Reviewers set to Franco Saliola
  • Status changed from new to needs_info

comment:31 Changed 6 years ago by saliola

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 be len(res) < 2 listGen==[] should be listGen == [] map( lambda x: x.lift(), res) should be map(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.
Last edited 6 years ago by saliola (previous) (diff)

comment:32 Changed 6 years ago by virmaux

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 6 years ago by git

  • Commit changed from 434765db324c0e6da9ddab9dd4b02632d12703f9 to 1ffc713eae626876785cf26216f5cbfd37ad7a34

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

1ffc71316659: numerous types and refactoring some names

comment:34 Changed 6 years ago by nthiery

#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 6 years ago by git

  • Commit changed from 1ffc713eae626876785cf26216f5cbfd37ad7a34 to d196cb30e95cf252116237d400c4d29b1d9fbfa9

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

d196cb3trivial fixes and iterator for Monoids().Finite().example()

comment:36 Changed 6 years ago by git

  • Commit changed from d196cb30e95cf252116237d400c4d29b1d9fbfa9 to 49e6c0ce330894fada62dde17c468f2eebc51503

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

011e877Merge branch 'public/combinat/fix_sga-16926' of trac.sagemath.org:sage into t/16926/public/combinat/fix_sga-16926
23cefb916926: trivial doctest updates w.r.t. previous merge.
49307d716926: proofreading with Travis
4c3c9e4I don't think the WeylAlgebra setting is supported enough to be advertised; furthermore the algebra method on nonstandard symmetric groups is fubar
b2069dbuse cythonized left/right_action_products in SGA too
655380dmore optimizations
8fe64bfMerge branch 'public/combinat/fix_sga-16926' of trac.sagemath.org:sage into t/16926/public/combinat/fix_sga-16926
1f9781416926: proofread Darij's latest changes
12aaaf8doctesting the demise of my bug
49e6c0cMerge branch 't/16926/public/combinat/fix_sga-16926' into t/16659/t/16659

comment:37 Changed 6 years ago by git

  • Commit changed from 49e6c0ce330894fada62dde17c468f2eebc51503 to 45190ac0b91b9025b446ab02f60e66a8c94a6304

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

2ae528e16659: Pierce decomposition, some doctest according to #16926
45190ac18002: general sage convention

comment:38 Changed 6 years ago by git

  • Commit changed from 45190ac0b91b9025b446ab02f60e66a8c94a6304 to 77d81f10e0118bd0fcfd23a58b5c3178466a80e4

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

77d81f1Merge branch 'develop' into t/16659/t/16659

comment:39 Changed 6 years ago by git

  • Commit changed from 77d81f10e0118bd0fcfd23a58b5c3178466a80e4 to 8c6759b811a557f51bdf7a568190bef3cf9eaaea

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

8c6759b16659: clean _orthogonal_idempotent

comment:40 Changed 6 years ago by virmaux

Hello,

I pushed many modifications according to Franco's review.

Also, #16926 had been merged so the tests all pass.

Aladin

comment:41 Changed 6 years ago by git

  • Commit changed from 8c6759b811a557f51bdf7a568190bef3cf9eaaea to a12dd254dd3069c67efdc83c3ba0f2836b021269

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

a12dd25Merge branch 'develop' into t/16659/t/16659

comment:42 Changed 6 years ago by git

  • Commit changed from a12dd254dd3069c67efdc83c3ba0f2836b021269 to 478d5f9d534bfc74537ad1c838ce82f6e2059de1

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

478d5f916659: orthogonal_idempotents -> central_orthogonal_idempotents

comment:43 Changed 6 years ago by virmaux

  • Authors set to Aladin Virmaux

comment:44 Changed 6 years ago by git

  • Commit changed from 478d5f9d534bfc74537ad1c838ce82f6e2059de1 to 5f34c9e157bff7bda8fa20c396a6eb6114d84190

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

15ec494typo
5f34c9eMerge branch 'develop' into t/16659/t/16659

comment:45 Changed 6 years ago by nthiery

  • Status changed from needs_info to needs_work
  • Work issues set to merge in develop.

comment:46 Changed 6 years ago by saliola

  • Branch changed from u/virmaux/t/16659 to u/saliola/t/16659

comment:47 Changed 6 years ago by nthiery

  • Branch changed from u/saliola/t/16659 to u/nthiery/t/16659

comment:48 Changed 6 years ago by nthiery

  • Commit changed from 5f34c9e157bff7bda8fa20c396a6eb6114d84190 to 1b531c628e803ae0d841537012cb4255ac1d986a

For the record: all tests passed on sage.math.u-psud.fr.


Last 10 new commits:

5b1c86911111: add doctest: submodule from non-linearly independent generators
cfe399dMerge branch 'public/11111-more_support_for_finite_dimensional_modules_and_algebras_with_basis' of git://trac.sagemath.org/sage into t/11111
a476501Merge branch 'public/11111-more_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
5c6dea211111: proofreading of Franco's proofreading
203631411111: fixed crosslink + missing file in the ref manual
6a3a07d11111: doc for CombinatorialFreeModule._order_cmp
b6d8bff11111: CombinatorialFreeModule.echelon_from -> Modules.WithBasis.ParentMethods.echelon_form; removed duplicate echelonize; delete meaningless and dangerous argument base_ring
25881cc11111: docstring improvement for quotient_module
7fb5d0c11111: final doc improvements
1b531c6Merge branch 't/11111/more_support_for_finite_dimensional_modules_and_algebras_with_basis' into t/16659/t/16659

comment:49 Changed 6 years ago by virmaux

  • Branch changed from u/nthiery/t/16659 to u/virmaux/t/16659

comment:50 Changed 6 years ago by git

  • 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 6 years ago by git

  • Commit changed from bd4ee7dd6447a23fbf7f8e68030aac8fa173b532 to 5cfb178721813a2260a5177a9a731e9119033253

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

5cfb17816659: Lift_idempotent now work, more test with 0-Hecke, TODO: explanation algorithms

comment:52 Changed 6 years ago by git

  • Commit changed from 5cfb178721813a2260a5177a9a731e9119033253 to 8f6a8670d2708b960a9f89490a59c76b9099d451

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

8f6a86716659: cleaning lifting, work for real now

comment:53 Changed 6 years ago by saliola

  • Branch changed from u/virmaux/t/16659 to u/saliola/t/16659

comment:54 Changed 6 years ago by saliola

  • Commit changed from 8f6a8670d2708b960a9f89490a59c76b9099d451 to 7362f035239f8fdbc992888478a9f4b7d102193c

I pushed some changes:

  1. radical_basis: I removed the optional cache_products option since the speed up by Aladin seems not to use this [should be verified by the reviewer]. I also re-wrote the code to make it more readable (I hope it is more readable, at least).
  1. principal_ideal:

(a) I swapped 'left' and 'right', because they were backwards. The principal left ideal generated by a is Aa, not aA. 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.

  1. 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:

7362f0316659: some documentation and tests

comment:55 Changed 6 years ago by saliola

  • 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 quasi-idempotents); 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 6 years ago by virmaux

  • Branch changed from u/saliola/t/16659 to u/virmaux/t/16659

comment:57 Changed 6 years ago by git

  • Commit changed from 7362f035239f8fdbc992888478a9f4b7d102193c to abcb076cf7ae487d9a34b690b415df40886fd93f

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

abcb07616659: renaming thanks to Franco's remarks, refactoring lifing_idempotent, documentation

comment:58 Changed 6 years ago by virmaux

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?
  • 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 6 years ago by git

  • Commit changed from abcb076cf7ae487d9a34b690b415df40886fd93f to 6f3308a8ce70a2141ab76395b1026afd42292d91

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

6f3308a16659: typo doc

comment:60 Changed 6 years ago by git

  • Commit changed from 6f3308a8ce70a2141ab76395b1026afd42292d91 to 4d72964f090830c6fa01e98588395136506f9eed

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

4d7296416659: revert radical_basis, documentation

comment:61 follow-up: Changed 6 years ago by virmaux

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.

Last edited 6 years ago by virmaux (previous) (diff)

comment:62 Changed 6 years ago by git

  • 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 ; follow-up: Changed 6 years ago by saliola

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 re-wrote 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 6 years ago by nthiery

Replying to saliola:

I'm surprised that there is such a big difference. I just took your method and re-wrote 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 6 years ago by nthiery

  • Description modified (diff)
  • Summary changed from Decomposition of finite dimensional associative algebras to Representation theory of finite dimensional associative algebras

New commits:

6f3308a16659: typo doc
4d7296416659: revert radical_basis, documentation
06de518 16659: documentation and typos

comment:66 Changed 6 years ago by nthiery

  • Description modified (diff)

comment:67 Changed 6 years ago by nthiery

  • Branch changed from u/virmaux/t/16659 to public/representation_theory/finite_dimensional_algebras-16659

comment:68 Changed 6 years ago by nthiery

  • Branch changed from public/representation_theory/finite_dimensional_algebras-16659 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 6 years ago by nthiery

  • Branch changed from u/virmaux/t/16659 to public/representation_theory/finite_dimensional_algebras-16659

comment:70 Changed 6 years ago by git

  • Commit changed from 06de5188ee34750760d480c1920afcfc1f40408d to 3a625818273d2f13547e8399c803405c14935a81

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

3fa0c4916659: documentation references
72f40cd16659 : merge
3a6258116659: add test for orthogonal idempotents summing to one

comment:71 Changed 6 years ago by git

  • Commit changed from 3a625818273d2f13547e8399c803405c14935a81 to bf02606324a12c4749f69f8139e9c3bd9d902e7e

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

bf0260616659: is_identity_decomposition_into_orthogonal_idempotents + documentation + implement Monoids.Algebras.algebra_generators from monoid_generators

comment:72 Changed 6 years ago by git

  • Commit changed from bf02606324a12c4749f69f8139e9c3bd9d902e7e to 0c44982418b96b37731814a0e949471b61270084

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

0c4498217696: use is_identity_decomposition_into_orthogonal_idempotents in the examples

comment:73 Changed 6 years ago by git

  • Commit changed from 0c44982418b96b37731814a0e949471b61270084 to cba7c8d1adcad21ace893b5827777348c2e486ef

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

cba7c8d17696: factored out of the examples a basic implementation of the 0-Hecke monoid

comment:74 Changed 6 years ago by git

  • Commit changed from cba7c8d1adcad21ace893b5827777348c2e486ef to 6e81e4b500f7698446fd19de792744a33667eafa

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

6e81e4b16659: proofreading and little additions to the doc; small refactoring of the code

comment:75 Changed 6 years ago by git

  • Commit changed from 6e81e4b500f7698446fd19de792744a33667eafa to 19756de9e9367efc85add11872bbf03d873b948f

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

19756de16659: minor line-split in the doc

comment:76 Changed 6 years ago by git

  • Commit changed from 19756de9e9367efc85add11872bbf03d873b948f to fd8e1ad375037e078905ae220bc9e543d65a67be

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

fd8e1ad16659: refactored _orthogonal_decomposition and updated doctests accordingly

comment:77 Changed 6 years ago by git

  • Commit changed from fd8e1ad375037e078905ae220bc9e543d65a67be to cc327efe6f3a221ae089d68558e5296cc9fc295c

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

cc327ef16659: improved documentation for _orthogonal_decomposition

comment:78 Changed 6 years ago by git

  • Commit changed from cc327efe6f3a221ae089d68558e5296cc9fc295c to e00dfdb8c49ba0105922aeeabab5bcb234bceaf0

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

e00dfdb16659: improved documentation for _orthogonal_decomposition

comment:79 Changed 6 years ago by nthiery

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 6 years ago by git

  • Commit changed from e00dfdb8c49ba0105922aeeabab5bcb234bceaf0 to cce7d3db05f6f10fec8c19a055987c61eee4b771

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

cce7d3d17696: added crosslinks

comment:81 follow-up: Changed 6 years ago by 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.

comment:82 in reply to: ↑ 81 Changed 6 years ago by nthiery

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 6 years ago by virmaux

There is still no commit with it ;)

comment:84 Changed 6 years ago by git

  • Commit changed from cce7d3db05f6f10fec8c19a055987c61eee4b771 to faf83a1380dde69c2dfd7849c1b8b8d24dcbecd6

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

faf83a116659: added missing hecke_monoid.py file

comment:85 Changed 6 years ago by nthiery

Gasp. I somehow managed to do the commit on develop. Luckily enough there are securities preventing from pushing there :-)

comment:86 Changed 6 years ago by nthiery

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

Last edited 6 years ago by nthiery (previous) (diff)

comment:87 follow-up: Changed 6 years ago by virmaux

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

Last edited 6 years ago by virmaux (previous) (diff)

comment:88 in reply to: ↑ 87 ; follow-up: Changed 6 years ago by 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!

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 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 :) ?

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 6 years ago by nthiery

  • Description modified (diff)

comment:90 in reply to: ↑ 88 ; follow-up: Changed 6 years ago by saliola

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 6 years ago by nthiery

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 6 years ago by nthiery

Gasp, I just noticed that I put a wrong ticket number (#17696 instead of #16659) in some of the commit messages.

comment:93 follow-ups: Changed 6 years ago by saliola

Check it out! I'm actually accomplishing this by my self-imposed deadline. It's rare when this happens. :-)

  1. First of all, this looks great! I only have a few comments / questions.
  1. 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 name complete_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 suggest radical instead of rad; the name is long so a few more characters won't be a problem)
  1. 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)
  1. cartan_invariants_matrix: in the documentation it is written that S_i and their adjoints S_i^* are representatives of the right simple modules; did you mean left for the latter?
  1. Tests: All tests passed!

Positive review pending the change of right to left for S_i^*.

comment:94 in reply to: ↑ 93 Changed 6 years ago by saliola

Replying to saliola:

  1. 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 6 years ago by nthiery

Replying to saliola:

Check it out! I'm actually accomplishing this by my self-imposed deadline. It's rare when this happens. :-)

Quite impressed, I am!

:-)

  1. First of all, this looks great! I only have a few comments / questions.

Thanks, and thanks for the review!

  1. 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 of rad; the name is long so a few more characters won't be a problem)

Will do!

  1. 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.

  1. cartan_invariants_matrix: in the documentation it is written that S_i and their adjoints S_i^* are representatives of the right simple modules; did you mean left for the latter?

Oops. Will fix now!

Cheers,

Nicolas

comment:96 Changed 6 years ago by git

  • Commit changed from faf83a1380dde69c2dfd7849c1b8b8d24dcbecd6 to 661c008e33f1384e9875bd500c148943988d580b

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

5f18523Merge branch 'develop' into representation_theory/finite_dimensional_algebras-16659
661c00816659: orthogonal_idempotents_central_mod_rad -> ...mod_radical + small doc fix

comment:97 Changed 6 years ago by nthiery

  • Status changed from needs_review to positive_review

Implemented final fix requested by Franco; positive review on his behalf!


New commits:

5f18523Merge branch 'develop' into representation_theory/finite_dimensional_algebras-16659
661c00816659: orthogonal_idempotents_central_mod_rad -> ...mod_radical + small doc fix

comment:98 follow-up: Changed 6 years ago by vbraun

  • Status changed from positive_review to needs_work
Overfull \hbox (49.85445pt too wide) in paragraph at lines 44441--44442
\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 follow-up: Changed 6 years ago by 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).

comment:100 in reply to: ↑ 99 Changed 6 years ago by nthiery

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 6 years ago by git

  • Commit changed from 661c008e33f1384e9875bd500c148943988d580b to ff577f3fa9cfdd5246c5e57f4427a1888b2654ef

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

ea552de16659: split Algebras.Semisimple.FiniteDimensional.WithBasis in its own file: first step: copying the file
ff577f316659: split Algebras.Semisimple.FiniteDimensional.WithBasis in its own file: actual work

comment:102 Changed 6 years ago by nthiery

  • 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 6 years ago by nthiery

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/sage-patchbot/issues/64

Cheers,

Nicolas

comment:104 Changed 6 years ago by saliola

  • Status changed from needs_review to positive_review

comment:105 Changed 6 years ago by vbraun

  • Branch changed from public/representation_theory/finite_dimensional_algebras-16659 to ff577f3fa9cfdd5246c5e57f4427a1888b2654ef
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:106 Changed 6 years ago by nthiery

  • Commit ff577f3fa9cfdd5246c5e57f4427a1888b2654ef deleted

Thanks Franco and Volker for this final step!

Yeah, this is done! One more big feature of MuPAD-Combinat that is in Sage :-)

Note: See TracTickets for help on using tickets.