Finite-dimensional algebras with basis: add __invert__ method

[darijgr]

Let's try to invert an element of a
finite-dimensional algebra over a field:

sage: QS3 = SymmetricGroupAlgebra(QQ, 3)
sage: qs = lambda p: QS3(Permutation(p))
sage: a = 3 * qs([1, 2, 3]) + qs([1, 3, 2]) + qs([2, 1, 3]))
sage: b = ~a; b

At the moment, this is not implemented.
The branch attached provides a naive implementation.

It does overshadow the __invert__ method on
AlgebrasWithBasis, which however is unable to
invert anything but a scalar multiple of the unity
(and that only in the case when the unity is a
basis element). In theory, this could be a problem,
but I don't expect it to be.

I hope it doesn't overshadow any more efficient
__invert__ methods on other classes of algebras
via diamond inheritance. Anyone who knows the hierarchy?

CC: @tscrim @fchapoton @mkoeppe @jhpalmieri

Component: algebra

Keywords: algebras, algebras with bases, inverses

Author: Darij Grinberg

Branch/Commit: 836a681

Reviewer: Travis Scrimshaw

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

[tscrim]

comment:4

This is good to add. I think we should have a shortcut for scalars of the identity when 1 is a basis element (via one_basis()).

Since from-category methods are low in the MRO, there shouldn't be any danger of overshadowing more specific implementations.

How could this fail to find an inverse when one did exist? I imagine there has to be some condition on the ground ring.

We probably should also force the coefficients into the base ring (which will fail when it has say 1/2 when over Z as it should). I would add a coerce=False (to keep the current optimized behavior in the code elsewhere) to from_vector that passes that off to _from_dict.

For pushing to trac, perhaps check that your public key on trac? Perhaps something got changed on your computer too?

[darijgr]

comment:5

Replying to @tscrim:

This is good to add. I think we should have a shortcut for scalars of the identity when 1 is a basis element (via one_basis()).

Thanks. Should we just check for the case when both self and alg.one() have length 1 (I assume we can use len() to get the number of nonzero coefficients, right?) and divide the coefficients?

Since from-category methods are low in the MRO, there shouldn't be any danger of overshadowing more specific implementations.

I hope so, but I'm worried that some categories themselves might be specific (e.g., what if we have some kind of, say, "division rings" category that has its own implementation of inverses?).

How could this fail to find an inverse when one did exist? I imagine there has to be some condition on the ground ring.

That would happen if the ground ring doesn't know enough linear algebra to support solve_right. I'm not sure what a good example would be.

We probably should also force the coefficients into the base ring (which will fail when it has say 1/2 when over Z as it should). I would add a coerce=False (to keep the current optimized behavior in the code elsewhere) to from_vector that passes that off to _from_dict.

Yeah, that sounds reasonable.

For pushing to trac, perhaps check that your public key on trac? Perhaps something got changed on your computer too?

My key is on trac, but yes, something changed on my computer (recent reinstall), and something seems to have changed on the server as well (the change from git:// to https://). I'd be happy to discuss this over zoom.

[tscrim]

Commit: 8f19cb7

[tscrim]

Branch: public/algebra/generic_invert-33250

[tscrim]

comment:7

Here is a trac pushed version of the branch. I made some additional changes, including what I mentioned in comment:4. I also took the opportunity to make sure all implementations of from_vector() have the same signature.

---

New commits:

8f19cb7

Implementing general inverse for fin-dim algebra w basis. Extending and standardizing from_vector().

[tscrim]

Author: Darij Grinberg

[tscrim]

Reviewer: Travis Scrimshaw

[sagetrac-git]

Changed commit from 8f19cb7 to 836a681

[sagetrac-git]

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

836a681

Fixes for one_basis() of DescentAlgebra and other misc changes

[darijgr]

comment:9

LGTM! If doctests pass, this should be merged.

(To clarify, Travis has reviewed my part of this ticket and I have now reviewed his.)

[vbraun]

Changed branch from public/algebra/generic_invert-33250 to 836a681