#31995 closed defect (fixed)

Submodules of a MatrixSpace

Reported by: Matthias Köppe Owned by:
Priority: major Milestone: sage-9.4
Component: linear algebra Keywords:
Cc: Travis Scrimshaw, David Roe Merged in:
Authors: Matthias Koeppe, Travis Scrimshaw Reviewers: Travis Scrimshaw, Matthias Koeppe
Report Upstream: N/A Work issues:
Branch: 2061f10 (Commits, GitHub, GitLab) Commit: 2061f10a00a5bfdc53d4473a6a7faa6a16783558
Dependencies: Stopgaps:

Status badges

Description

MatrixSpace does not implement the category ModulesWithBasis correctly.

sage: M = MatrixSpace(QQ, 2)
sage: M.submodule([M.matrix([[1, 2], [3, 4]])])
AttributeError: 'tuple' object has no attribute 'support'

Change History (17)

comment:1 Changed 16 months ago by Matthias Köppe

Branch: u/mkoeppe/submodules_of_a_matrixspace

comment:2 Changed 16 months ago by Matthias Köppe

Commit: 54915a614fba1f361e7d8e47b87785844a8c165b

Here's a first fix (follow-up from #19448, I think)


New commits:

54915a6FiniteDimensionalModulesWithBasis: Fix use of _compute_support_order

comment:3 Changed 16 months ago by Matthias Köppe

This gets a bit farther and now leads to:

TypeError: <class 'sage.sets.family.TrivialFamily_with_category'> is not hashable and does not implement _cache_key()

comment:4 Changed 16 months ago by Travis Scrimshaw

TrivialFamily is hashable and even has a doctest:

sage: from sage.sets.family import TrivialFamily
sage: f = TrivialFamily((3,4,7))
sage: hash(f) == hash(f)

The problem comes from the fact that matrices by default are mutable and not hashable. If you look a little higher up in the error, you get:

TypeError: mutable matrices are unhashable

This comes from the fact that echelon_form creates mutable matrices:

sage: mat = M.matrix([[1, 2], [3, 4]])
sage: mat.set_immutable()
sage: M.echelon_form([mat])[0]
[1 2]
[3 4]
sage: _.is_mutable()
True

If we skip this step, then it creates the submodule:

sage: M.submodule([mat], already_echelonized=True)
Free module generated by {0} over Rational Field
Last edited 16 months ago by Travis Scrimshaw (previous) (diff)

comment:5 Changed 16 months ago by Travis Scrimshaw

Authors: Matthias Koeppe, Travis Scrimshaw
Branch: u/mkoeppe/submodules_of_a_matrixspacepublic/linear_algebra/matrix_space_submodules-31995
Commit: 54915a614fba1f361e7d8e47b87785844a8c165bc60bc37dcf38ffa99f96ab8670cb1aedf8f95d2f
Reviewers: Travis Scrimshaw, Matthias Koeppe
Status: newneeds_review

The best way around this IMO is a special case of submodule in MatrixSpace that just makes the result of echelon_form into a set of immutable matrices. This now works for me.


New commits:

c60bc37Make matrices immutable during the construction of submodule().

comment:6 Changed 16 months ago by Matthias Köppe

Status: needs_reviewpositive_review

This seems to work well, thanks very much!

(The way that the submodule prints itself, using the indices, is a bit strange, but that can be improved on another ticket.)

comment:7 Changed 15 months ago by Matthias Köppe

Status: positive_reviewneeds_work

The example from #30334 (duplicate of this ticket) still fails, with a new error:

sage: M = MatrixSpace(QQ, 3, 3)
sage: M in ModulesWithBasis(QQ)
True
sage: A = M([[0, 0, 1], [0, 0, 0], [0, 0, 0]])
sage: A
[0 0 1]
[0 0 0]
[0 0 0]
sage: M.submodule([A])
TypeError: entries must be a list of length 9

comment:8 Changed 15 months ago by git

Commit: c60bc37dcf38ffa99f96ab8670cb1aedf8f95d2fe270655ec552abb098a27cb61f3d78ddd2a1886a

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

e270655Fixing issue when the support is smaller than the dimension.

comment:9 Changed 15 months ago by Travis Scrimshaw

Status: needs_workneeds_review

This fixes that issue, which came from the category FiniteDimensionalModulesWithBasis expecting order to have full support. However, I think we don't want this because we want to support more sparse matrices (or, more general, any ordering passed from the user) for taking submodules, and having a get_order() would force a conversion to a dense implementation.

Last edited 15 months ago by Samuel Lelièvre (previous) (diff)

comment:10 Changed 15 months ago by Matthias Köppe

Status: needs_reviewpositive_review

Yes, I agree with this solution. Thanks!

comment:11 Changed 15 months ago by Travis Scrimshaw

Thank you.

comment:12 Changed 15 months ago by Volker Braun

Status: positive_reviewneeds_work
sage -t --long --warn-long 42.0 --random-seed=0 src/sage/matrix/matrix_space.py
**********************************************************************
File "src/sage/matrix/matrix_space.py", line 1622, in sage.matrix.matrix_space.MatrixSpace.?
Failed example:
    Xp = M.submodule([A, B], order=[(0,1), (1,1), (0,0)])
Exception raised:
    Traceback (most recent call last):
      File "sage/misc/cachefunc.pyx", line 996, in sage.misc.cachefunc.CachedFunction.__call__ (build/cythonized/sage/misc/cachefunc.c:5974)
        return self.cache[k]
      File "sage/misc/weak_dict.pyx", line 702, in sage.misc.weak_dict.WeakValueDictionary.__getitem__ (build/cythonized/sage/misc/weak_dict.c:3712)
        cdef PyObject* wr = PyDict_GetItemWithError(self, k)
    TypeError: unhashable type: 'list'

    During handling of the above exception, another exception occurred:

    Traceback (most recent call last):
      File "sage/misc/cachefunc.pyx", line 543, in sage.misc.cachefunc.dict_key (build/cythonized/sage/misc/cachefunc.c:3091)
        hash(o)
    TypeError: unhashable type: 'list'

    During handling of the above exception, another exception occurred:

    Traceback (most recent call last):
      File "sage/misc/cachefunc.pyx", line 583, in sage.misc.cachefunc.cache_key (build/cythonized/sage/misc/cachefunc.c:3295)
        hash(o)
    TypeError: unhashable type: 'list'

    During handling of the above exception, another exception occurred:

    Traceback (most recent call last):
      File "sage/misc/cachefunc.pyx", line 583, in sage.misc.cachefunc.cache_key (build/cythonized/sage/misc/cachefunc.c:3295)
        hash(o)
    TypeError: unhashable type: 'list'

    During handling of the above exception, another exception occurred:

    Traceback (most recent call last):
      File "sage/misc/cachefunc.pyx", line 583, in sage.misc.cachefunc.cache_key (build/cythonized/sage/misc/cachefunc.c:3295)
        hash(o)
    TypeError: unhashable type: 'list'

    During handling of the above exception, another exception occurred:

    Traceback (most recent call last):
      File "sage/misc/cachefunc.pyx", line 596, in sage.misc.cachefunc.cache_key_unhashable (build/cythonized/sage/misc/cachefunc.c:3699)
        k = o._cache_key()
    AttributeError: 'list' object has no attribute '_cache_key'

    During handling of the above exception, another exception occurred:

    Traceback (most recent call last):
      File "/home/release/Sage/local/lib64/python3.9/site-packages/sage/doctest/forker.py", line 718, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/release/Sage/local/lib64/python3.9/site-packages/sage/doctest/forker.py", line 1137, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.matrix.matrix_space.MatrixSpace.?[9]>", line 1, in <module>
        Xp = M.submodule([A, B], order=[(Integer(0),Integer(1)), (Integer(1),Integer(1)), (Integer(0),Integer(0))])
      File "/home/release/Sage/local/lib64/python3.9/site-packages/sage/matrix/matrix_space.py", line 1647, in submodule
        return SubmoduleWithBasis(gens, ambient=self,
      File "sage/misc/classcall_metaclass.pyx", line 322, in sage.misc.classcall_metaclass.ClasscallMetaclass.__call__ (build/cythonized/sage/misc/classcall_metaclass.c:1761)
        return cls.classcall(cls, *args, **kwds)
      File "/home/release/Sage/local/lib64/python3.9/site-packages/sage/modules/with_basis/subquotient.py", line 218, in __classcall_private__
        return super(SubmoduleWithBasis, cls).__classcall__(cls,
      File "sage/misc/cachefunc.pyx", line 998, in sage.misc.cachefunc.CachedFunction.__call__ (build/cythonized/sage/misc/cachefunc.c:6013)
        k = dict_key(k)
      File "sage/misc/cachefunc.pyx", line 545, in sage.misc.cachefunc.dict_key (build/cythonized/sage/misc/cachefunc.c:3129)
        o = (unhashable_key, cache_key_unhashable(o))
      File "sage/misc/cachefunc.pyx", line 594, in sage.misc.cachefunc.cache_key_unhashable (build/cythonized/sage/misc/cachefunc.c:3660)
        return tuple(cache_key(item) for item in o)
      File "sage/misc/cachefunc.pyx", line 594, in genexpr (build/cythonized/sage/misc/cachefunc.c:3551)
        return tuple(cache_key(item) for item in o)
      File "sage/misc/cachefunc.pyx", line 585, in sage.misc.cachefunc.cache_key (build/cythonized/sage/misc/cachefunc.c:3333)
        o = cache_key_unhashable(o)
      File "sage/misc/cachefunc.pyx", line 594, in sage.misc.cachefunc.cache_key_unhashable (build/cythonized/sage/misc/cachefunc.c:3660)
        return tuple(cache_key(item) for item in o)
      File "sage/misc/cachefunc.pyx", line 594, in genexpr (build/cythonized/sage/misc/cachefunc.c:3551)
        return tuple(cache_key(item) for item in o)
      File "sage/misc/cachefunc.pyx", line 585, in sage.misc.cachefunc.cache_key (build/cythonized/sage/misc/cachefunc.c:3333)
        o = cache_key_unhashable(o)
      File "sage/misc/cachefunc.pyx", line 594, in sage.misc.cachefunc.cache_key_unhashable (build/cythonized/sage/misc/cachefunc.c:3660)
        return tuple(cache_key(item) for item in o)
      File "sage/misc/cachefunc.pyx", line 594, in genexpr (build/cythonized/sage/misc/cachefunc.c:3551)
        return tuple(cache_key(item) for item in o)
      File "sage/misc/cachefunc.pyx", line 585, in sage.misc.cachefunc.cache_key (build/cythonized/sage/misc/cachefunc.c:3333)
        o = cache_key_unhashable(o)
      File "sage/misc/cachefunc.pyx", line 598, in sage.misc.cachefunc.cache_key_unhashable (build/cythonized/sage/misc/cachefunc.c:3783)
        raise TypeError("unhashable type: {!r}".format(type(o).__name__))
    TypeError: unhashable type: 'list'
**********************************************************************

comment:13 Changed 15 months ago by git

Commit: e270655ec552abb098a27cb61f3d78ddd2a1886a2061f10a00a5bfdc53d4473a6a7faa6a16783558

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

d9fed04Merge branch 'public/linear_algebra/matrix_space_submodules-31995' of git://trac.sagemath.org/sage into public/linear_algebra/matrix_space_submodules-31995
2061f10Fixing bad doctests.

comment:14 Changed 15 months ago by Travis Scrimshaw

Status: needs_workneeds_review

I could have sworn I tested this...sorry about that. Fixed the bad doctests.

comment:15 Changed 15 months ago by Matthias Köppe

Status: needs_reviewpositive_review

comment:16 Changed 15 months ago by Travis Scrimshaw

Thank you.

comment:17 Changed 15 months ago by Volker Braun

Branch: public/linear_algebra/matrix_space_submodules-319952061f10a00a5bfdc53d4473a6a7faa6a16783558
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.