Opened 6 years ago

Closed 6 years ago

# FiniteDimensionalAlgebra.is_unitary is not sufficient

Reported by: Owned by: darij major sage-6.10 algebra finite-dimensional algebra, linear algebra sage-combinat, tscrim, nthiery Peter Bruin Darij Grinberg, Travis Scrimshaw N/A 366feae 366feaedc2e28d1fc8d03380970883f644abd5de

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

### 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:

 ​ef3c7fc `is_unitary method fixed` ​376152e `mutability 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: ↓ 4 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: ↓ 13 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:

 ​6fa53aa `Adding 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:

 ​0cfe036 `Adding 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: ↓ 15 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: ↓ 16 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: ↓ 17 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: ↓ 19 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:

 ​9dd11b2 `Fixing 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:

 ​366feae `non-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.