Opened 6 years ago

Closed 6 years ago

#19473 closed defect (fixed)

FiniteDimensionalAlgebra.is_unitary is not sufficient

Reported by: darij Owned by:
Priority: major Milestone: sage-6.10
Component: algebra Keywords: finite-dimensional algebra, linear algebra
Cc: sage-combinat, tscrim, nthiery Merged in:
Authors: Peter Bruin Reviewers: Darij Grinberg, Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 366feae (Commits, GitHub, GitLab) Commit: 366feaedc2e28d1fc8d03380970883f644abd5de
Dependencies: Stopgaps:

Status badges

Description

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.

Change History (25)

comment:1 Changed 6 years ago by darij

  • Authors set to Darij Grinberg
  • Branch set to public/ticket/19473
  • Commit set to 376152ea6bd6616b9b47b184b5e4c508c4850f86
  • Status changed from new to needs_review
  • Work issues set to check that it works (my sage is still compiling); test for speed regressions

New commits:

ef3c7fcis_unitary method fixed
376152emutability of table fixed

comment:2 Changed 6 years ago by pbruin

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?

comment:3 follow-up: Changed 6 years ago by darij

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.

comment:4 in reply to: ↑ 3 Changed 6 years ago by pbruin

Replying to darij:

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

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

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

comment:6 Changed 6 years ago by darij

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

comment:7 Changed 6 years ago by tscrim

  • Branch changed from public/ticket/19473 to public/algebra/finite_dim_algebra_fixes-19473
  • Commit changed from 376152ea6bd6616b9b47b184b5e4c508c4850f86 to 6fa53aad0a3faf6304a8dea0f5cc92f7009f41f7

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:

6fa53aaAdding UniqueRepresentation behavior.

comment:8 Changed 6 years ago by tscrim

  • Authors changed from Darij Grinberg to Darij Grinberg, Travis Scrimshaw
  • Reviewers set to Travis Scrimshaw
  • Work issues check that it works (my sage is still compiling); test for speed regressions deleted

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

comment:9 Changed 6 years ago by git

  • Commit changed from 6fa53aad0a3faf6304a8dea0f5cc92f7009f41f7 to 0cfe0366fc527d2f692c835be3d40f60aa61c471

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

0cfe036Adding UniqueRepresentation behavior.

comment:10 Changed 6 years ago by darij

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

comment:11 Changed 6 years ago by darij

  • Work issues set to clear up associativity requirement; if necessary, change superclass and is_unitary method

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?

comment:12 Changed 6 years ago by tscrim

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.

comment:13 in reply to: ↑ 5 ; follow-up: Changed 6 years ago by pbruin

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.

comment:14 Changed 6 years ago by pbruin

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.

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

comment:15 in reply to: ↑ 13 ; follow-up: Changed 6 years ago by tscrim

Replying to pbruin:

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

comment:16 in reply to: ↑ 15 ; follow-up: Changed 6 years ago by pbruin

Replying to tscrim:

Replying to pbruin:

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.

comment:17 in reply to: ↑ 16 Changed 6 years ago by tscrim

Replying to pbruin:

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.

comment:18 follow-up: Changed 6 years ago by darij

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

comment:19 in reply to: ↑ 18 Changed 6 years ago by pbruin

Replying to darij:

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

comment:20 Changed 6 years ago by darij

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.

comment:21 Changed 6 years ago by tscrim

  • Authors changed from Darij Grinberg, Travis Scrimshaw to Peter Bruin
  • Branch changed from public/algebra/finite_dim_algebra_fixes-19473 to public/algebras/unitary_fd_algerba-19473
  • Commit changed from 0cfe0366fc527d2f692c835be3d40f60aa61c471 to 9dd11b272861e5e7c50c04d44364452d71359b8d
  • Reviewers changed from Travis Scrimshaw to Darij Grinberg, Travis Scrimshaw
  • Work issues clear up associativity requirement; if necessary, change superclass and is_unitary method deleted

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


New commits:

9dd11b2Fixing is_unitary for FiniteDimensionalAlgebra.

comment:22 Changed 6 years ago by git

  • Commit changed from 9dd11b272861e5e7c50c04d44364452d71359b8d to 366feaedc2e28d1fc8d03380970883f644abd5de

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

366feaenon-associative doctests

comment:23 Changed 6 years ago by darij

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

comment:24 Changed 6 years ago by tscrim

  • Status changed from needs_review to positive_review

comment:25 Changed 6 years ago by vbraun

  • Branch changed from public/algebras/unitary_fd_algerba-19473 to 366feaedc2e28d1fc8d03380970883f644abd5de
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.