FiniteDimensionalAlgebra.is_unitary is not sufficient

[darijgr]

Here is the semigroup algebra (over QQ) of the semigroup with two elements whose product is given by x*y == y:

sage: A = FiniteDimensionalAlgebra(QQ, [Matrix([[1,0],[1,0]]), Matrix([[0,1],[0,1]])])
sage: for x in A.basis():
    for y in A.basis():
        print x*y == y
....:         
True
True
True
True

Sage claims that it is unitary:

sage: A.is_unitary()
True

based on the following wrong concept:

        .. NOTE::

            If a finite-dimensional algebra over a field admits a left identity,
            then this is the unique left identity, and it is also a
            right identity.

On a slightly related note, the table method on FiniteDimensionalAlgebra returns mutable matrices, and mutating them corrupts the algebra.

CC: @sagetrac-sage-combinat @tscrim @nthiery

Component: algebra

Keywords: finite-dimensional algebra

Author: Peter Bruin

Branch/Commit: 366feae

Reviewer: Darij Grinberg, Travis Scrimshaw

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

[darijgr]

Commit: 376152e

[darijgr]

Work Issues: check that it works (my sage is still compiling); test for speed regressions

[darijgr]

Branch: public/ticket/19473

[darijgr]

Author: Darij Grinberg

[darijgr]

New commits:

ef3c7fc	is_unitary method fixed
376152e	mutability of table fixed

[pjbruin]

comment:2

The wrong claim "If a finite-dimensional algebra over a field admits a left identity, then this is the unique left identity, and it is also a right identity" is my fault (introduced in trac_12141_finite_algebras.patch​ at #12141). I have no idea what I was thinking...

About the mutability: can't we just make the matrices in the table immutable using the set_immutable() method?

[darijgr]

comment:3

Maybe (I don't see a downside to this, but I know little of matrices in Sage...). But we'd have to make the list immutable too.

[pjbruin]

comment:4

Replying to @darijgr:

Maybe (I don't see a downside to this, but I know little of matrices in Sage...).

As far as I know there is no downside, but I'm not an expert either.

But we'd have to make the list immutable too.

Instead of a list, we could return a tuple (or an immutable sequence).

[tscrim]

comment:5

I would get rid of the copy attribute, instead make this a UniqueRepresentation (or perhaps a UniqueFactory so we can better control the cache key), and make the table a tuple of immutable matrices that gets set by the __classcall_private__.

We also need to fix the category, which is wrong for non-associative, non-unital cases.

[darijgr]

comment:6

OK, feel free to rollback my 2nd commit, which as I see just now is broken anyway. I'm all for immutability, though I am not sure if we want UniqueRepresentation (didn't we agree at some point that it is a pain in the ass?).

[tscrim]

comment:7

Some things with UniqueRepresentation are annoying, but overall that isn't so big here IMO. Here's my proposal with UniqueRepresentation and also changing the default category to be MagmaticAlgebras. I would like to check during construction if the algebra is associative/unital/commutative but this is too expensive. Also refining the category after the fact can lead to subtle bugs, mainly the elements don't know the could have more methods from the refined category. So I'm leaving it to the user to pass the correct category (but I left the assume_associative).

---

New commits:

6fa53aa

Adding UniqueRepresentation behavior.

[tscrim]

Changed commit from 376152e to 6fa53aa

[tscrim]

Changed branch from public/ticket/19473 to public/algebra/finite_dim_algebra_fixes-19473

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

Changed author from Darij Grinberg to Darij Grinberg, Travis Scrimshaw

[tscrim]

comment:8

BTW, the previous branch had doctest failures noted on the patchbot.

[tscrim]

Changed work issues from check that it works (my sage is still compiling); test for speed regressions to none

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

0cfe036

Adding UniqueRepresentation behavior.

[sagetrac-git]

Changed commit from 6fa53aa to 0cfe036

[darijgr]

comment:10

Actually my fix for the unitality assumed associativity. I need to fix it again to work in the magmatic case...

[darijgr]

comment:11

OK, now I am lost. FiniteDimensionalAlgebra inherits from Algebra, which in turn inherits from Ring. The test suite of Ring has associativity, which makes me suspect that rings are supposed to be associative. But the design of FiniteDimensionalAlgebra makes it clear that associativity is optional, and the docstrings contain examples of non-associative algebras (which still pass their test suites since some_element returns just a 1-element list). So should they be associative or not?

[darijgr]

Work Issues: clear up associativity requirement; if necessary, change superclass and is_unitary method

[tscrim]

comment:12

From what I see, there are no additional tests in Ring. Instead these come from the category of Rings, which is not in the supercategories. However I think we are okay because the class doesn't necessarily assume the parent is associative and unital.

[pjbruin]

comment:13

Replying to @tscrim:

I would get rid of the copy attribute, instead make this a UniqueRepresentation (or perhaps a UniqueFactory so we can better control the cache key), and make the table a tuple of immutable matrices that gets set by the __classcall_private__.

How does introducing UniqueRepresentation help in solving this ticket? Wouldn't it be better to do that on a separate ticket?

We also need to fix the category, which is wrong for non-associative, non-unital cases.

I agree. It is unfortunate that refining the category after initialisation is possibly problematic.

[pjbruin]

comment:14

Here is Johan Bosman's implementation of is_unitary() from #12141 before my wrong rewrite (and after some editing and simplification):

@cached_method
def is_unitary(self):
    """
    Return True if ``self`` is unitary.

    EXAMPLES::

        sage: B = FiniteDimensionalAlgebra(QQ, [Matrix([[1,0],[0,1]]), Matrix([[0,1],[-1,0]])])
        sage: B.is_unitary()
        True
        sage: C = FiniteDimensionalAlgebra(QQ, [Matrix([[0,0],[0,0]]), Matrix([[0,0],[0,0]])])
        sage: C.is_unitary()
        False
    """
    n = self._degree
    k = self.base_ring()
    if n == 0:
        self._one = vector(k, [])
        return True
    B1 = reduce(lambda x, y: x.augment(y),
                self._table, Matrix(k, n, 0))
    B2 = reduce(lambda x, y: x.augment(y),
                self.left_table(), Matrix(k, n, 0))
    # This is the vector obtained by concatenating the rows of the
    # n times n identity matrix:
    v = vector(k, (n - 1) * ([1] + n * [0]) + [1])
    try:
        sol1 = B1.solve_left(v)
        sol2 = B2.solve_left(v)
    except ValueError:
        return False
    if sol1 == sol2:
        self._one = sol1
        return True
    else:
        return False

If this is correct, we can just re-use it.

[tscrim]

comment:15

Replying to @pjbruin:

Replying to @tscrim:

I would get rid of the copy attribute, instead make this a UniqueRepresentation (or perhaps a UniqueFactory so we can better control the cache key), and make the table a tuple of immutable matrices that gets set by the __classcall_private__.

How does introducing UniqueRepresentation help in solving this ticket? Wouldn't it be better to do that on a separate ticket?

We can separate off the table issues into a separate ticket, that is okay with me. Want me to do that?

We also need to fix the category, which is wrong for non-associative, non-unital cases.

I agree. It is unfortunate that refining the category after initialisation is possibly problematic.

The other option would be to add boolean parameters that do checks in the initialization (which would require some minor refactoring if we wanted to go the UniqueRepresentaion route and would mean we do that on this ticket).

[pjbruin]

comment:16

Replying to @tscrim:

Replying to @pjbruin:

Replying to @tscrim:

I would get rid of the copy attribute, instead make this a UniqueRepresentation (or perhaps a UniqueFactory so we can better control the cache key), and make the table a tuple of immutable matrices that gets set by the __classcall_private__.

How does introducing UniqueRepresentation help in solving this ticket? Wouldn't it be better to do that on a separate ticket?

We can separate off the table issues into a separate ticket, that is okay with me. Want me to do that?

We also need to fix the category, which is wrong for non-associative, non-unital cases.

I agree. It is unfortunate that refining the category after initialisation is possibly problematic.

The other option would be to add boolean parameters that do checks in the initialization (which would require some minor refactoring if we wanted to go the UniqueRepresentaion route and would mean we do that on this ticket).

It seems to me that there are four mostly independent issues:

1. the wrong is_unitary() method;
2. the fact that the multiplication table is mutable;
3. determining the correct category;
4. implementing unique representation.
   We could possibly fix issue 2 on this ticket (assuming it just takes a few lines), but also doing 3 and 4 on this ticket would be way too much in my opinion. I would prefer just solving issue 1 on this ticket and opening separate tickets (possibly with dependencies) for issues 2, 3 and 4.

[tscrim]

comment:17

Replying to @pjbruin:

It seems to me that there are four mostly independent issues:

1. the wrong is_unitary() method;
2. the fact that the multiplication table is mutable;
3. determining the correct category;
4. implementing unique representation.
   We could possibly fix issue 2 on this ticket (assuming it just takes a few lines), but also doing 3 and 4 on this ticket would be way too much in my opinion. I would prefer just solving issue 1 on this ticket and opening separate tickets (possibly with dependencies) for issues 2, 3 and 4.

Then let us just fix 1 here and use the changes on the current branch as a followup ticket.

[darijgr]

comment:18

+1 for splitting 1&2 | 3&4. This is particularly helpful to me, as I am fairly sure I can review 1&2, but probably not 3&4 these days.

Johan Bosman's approach looks correct (mathematically -- haven't checked the programming). It isn't even necessary to check that the two identities are equal, since their existence already yields their equality.

[pjbruin]

comment:19

Replying to @darijgr:

Johan Bosman's approach looks correct (mathematically -- haven't checked the programming). It isn't even necessary to check that the two identities are equal, since their existence already yields their equality.

Indeed, I have now also convinced myself of this. This means that we can replace

    if sol1 == sol2:
        self._one = sol1
        return True
    else:
        return False

by

    assert sol1 == sol2
    return True

(note that at this point the fact that sol1 and sol2 have been computed implies that left and right identity elements exist).

[darijgr]

comment:20

One more thing. The definition

v = vector(k, (n - 1) * ([1] + n * [0]) + [1])

of v is one step back from the currently present definition

v = vector(Matrix.identity(k, n).list())

because it is far better for the entries of v to be defined as the zero/one elements of R rather than the ints 0 and 1. There are, after all, rings whose zero/one elements are distinct from 0 and 1. (So far we probably don't have fields like that, but it could be imaginable. More importantly, coercions like R(0) take time, particularly when they are cast on each entry of the vector separately.

[tscrim]

Changed author from Darij Grinberg, Travis Scrimshaw to Peter Bruin

[tscrim]

comment:21

Okay, here is 1. The rest will be handled on #19507.

---

New commits:

9dd11b2

Fixing is_unitary for FiniteDimensionalAlgebra.

[tscrim]

Changed work issues from clear up associativity requirement; if necessary, change superclass and is_unitary method to none

[tscrim]

Changed branch from public/algebra/finite_dim_algebra_fixes-19473 to public/algebras/unitary_fd_algerba-19473

[tscrim]

Changed reviewer from Travis Scrimshaw to Darij Grinberg, Travis Scrimshaw

[tscrim]

Changed commit from 0cfe036 to 9dd11b2

[sagetrac-git]

Changed commit from 9dd11b2 to 366feae

[sagetrac-git]

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

366feae

non-associative doctests

[darijgr]

comment:23

LGTM, but I've added some doctests to make sure this doesn't regress. Positive review, if you agree.

[vbraun]

Changed branch from public/algebras/unitary_fd_algerba-19473 to 366feae