Opened 8 years ago
Last modified 4 years ago
#15160 new defect
Linear algebra over all rings (which are not fields)
Reported by: | nborie | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-8.2 |
Component: | linear algebra | Keywords: | matrix, ring |
Cc: | sage-combinat | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
Basic arithmetic works for matrices over exotic rings, but many linear algebra algorithms do not, such as computing rank, inverse (when the matrix is invertible), ...
Attachments (1)
Change History (14)
Changed 8 years ago by
comment:1 Changed 8 years ago by
comment:2 Changed 8 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:3 Changed 7 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:4 Changed 7 years ago by
A fix for this would likely include/fix #15947.
comment:5 Changed 7 years ago by
- Milestone changed from sage-6.3 to sage-6.4
comment:6 Changed 4 years ago by
Actually, to define the R
-algebra (MatrixSpace(R,m,n), +, *)
one only needs a semi-ring R
... would be useful when R is the max-plus semiring! But in this more general situation, many feature of linear algebra do not make sense (e.g. rank, determinant, etc).
comment:7 Changed 4 years ago by
Do you have a concrete example of something that doesn't work currently?
comment:8 Changed 4 years ago by
Hello, sorry for my version of Sage but I think nothing has move for enabling matrices and linear algebra in general for general rings (these using the category framework and not using the class RingElement?).
The mercurial patch attached on this ticket did break the multiplication between matrix and vector. This is not the right way to fix that. I don't know how to fix that, this go far beyond my knowledge with the category framework, coercions, actions...
On cocalc and my (old) version of Sage (sorry one more time), I still have things that the following tests... For that reason, I did locally implement an horrible hack to invert matrix with unitary determinant.
nborie@caradoc:~$ sage ┌────────────────────────────────────────────────────────────────────┐ │ SageMath version 7.6, Release Date: 2017-03-25 │ │ Type "notebook()" for the browser-based notebook interface. │ │ Type "help()" for help. │ └────────────────────────────────────────────────────────────────────┘ sage: SF = SymmetricFunctions(QQ).schur() sage: SF.one() s[] sage: ~SF.one() s[] sage: M = Matrix([[SF.one()]]) sage: M.determinant() s[] sage: ~M.determinant() s[] sage: M.inverse() --------------------------------------------------------------------------- AttributeError Traceback (most recent call last) ... AttributeError: 'SymmetricFunctionAlgebra_schur_with_category' object has no attribute 'fraction_field'
sage: S = SteenrodAlgebra(2) sage: S mod 2 Steenrod algebra, milnor basis sage: S.one() 1 sage: ~S.one() 1 sage: M = Matrix([[S.one()]]) sage: M.is_invertible() True sage: M.inverse() --------------------------------------------------------------------------- AttributeError Traceback (most recent call last) ... AttributeError: 'SteenrodAlgebra_mod_two_with_category' object has no attribute 'fraction_field'
sage: A = SymmetricGroup(4).algebra(QQ) sage: M = Matrix([[A.one()]]) sage: M.is_invertible() True sage: M.inverse() --------------------------------------------------------------------------- AttributeError Traceback (most recent call last) ... AttributeError: 'SymmetricGroupAlgebra_n_with_category' object has no attribute 'is_field'
sage: NonCommutativeSymmetricFunctions(QQ) Non-Commutative Symmetric Functions over the Rational Field sage: NCSF = NonCommutativeSymmetricFunctions(QQ) sage: M = Matrix([[NCSF.one()]]) sage: M.is_invertible() True sage: M.inverse() --------------------------------------------------------------------------- AttributeError Traceback (most recent call last) ... AttributeError: 'NonCommutativeSymmetricFunctions.Complete_with_category' object has no attribute 'is_field'
You could try these short examples on the current Sage version. Same error appear with the following :
sage: MatrixSpace(SF, 4) Full MatrixSpace of 4 by 4 dense matrices over Symmetric Functions over Rational Field in the Schur basis sage: M = MatrixSpace(SF, 4) sage: M.identity_matrix() [s[] 0 0 0] [ 0 s[] 0 0] [ 0 0 s[] 0] [ 0 0 0 s[]] sage: ~M.identity_matrix() --------------------------------------------------------------------------- AttributeError Traceback (most recent call last) ... AttributeError: 'SymmetricFunctionAlgebra_schur_with_category' object has no attribute 'fraction_field'
All these kind of tests can be read in the very old bugged patch.
Hope this could help.
comment:9 Changed 4 years ago by
Sorry for my English btw. Same problem with FreeAlgebra?
sage: F = FreeAlgebra(QQ, ['a','b','c']) sage: M = Matrix([[F.one()]]) sage: M*M == M True sage: M.inverse() --------------------------------------------------------------------------- AttributeError Traceback (most recent call last) ... AttributeError: 'FreeAlgebra_generic_with_category' object has no attribute 'fraction_field'
Since I did not contribute to Sage these last... two years (perhaps). I am not aware of the list of algebraic construction for which this bug pop. I am really afraid the list can be very large.
I did work on basis changes of the coinvariant of the symmetric group (Schubert polynomials, Harmonic polynomials, Descents Monomials, Monomials under staircase, Higher Specht Polynomials). This topic is closed to representation theory of the symmetric group (linear algebra on some strange ring). All my basis changes (binomial(5, 2) different) are matrices with unital determinant that Sage can't inverse. Oh, In fact Sage can do that for sure (all good algorithms are inside for that...), but I really don't know how to fix it. I did try but I did not succeed...
I will compile an up to date version of Sage this night to check the bug is still here...
comment:10 Changed 4 years ago by
nborie: I understand your last comments, but my impression was that the ticket was talking also about much more elementary stuff than inverting matrices.
For example, one of the "goals" stated is "Try to modify MatrixSpace
and Matrix
such that all basic operation can be done with special rings". It would be good to have an example of something that doesn't work for this "goal".
comment:11 Changed 4 years ago by
Ok, I know have a 8.1 and things seems now better...
I did check on my small set of exotic rings (they don't all come from the combinat crew, Steenrod come from number theorists I guess...)
It seems to me that very basic stuff work fine : for M a matrix and V a vector and c a ring coefficient
- M*V, V*M, c*M, M*c, c*V, V*c all works fine (I did not manage to build a vector for Non Commutative Symmetric Functions but this probably don't come from matrix code...)
- .charpoly() also works fine
- .commutator() always works
- Some Tracebacks for adjoint, echelonize, inverse, rank and kernel...
I did run that (I create a vector with the first column of the identity matrix, I did not use the vector( ...data... ) function)
def test_ring(R): o = R.one() z = R.zero() try: Id2 = Matrix([[o, z], [z, o]]) except: print(R, "Error creating a matrix") return None try: V = Id2.column(0) except: print(R, "Error creating a vector") return None c = R.an_element() try: if(V*c != c*V): print(R, "Bug in mul on coef*vector") except: print(R, "Error in mul on coef*vector") try: if(Id2*c != c*Id2): print(R, "Bug in mul on coef*matrix") except: print(R, "Error in mul on coef*matrix") try: if(Id2*V != V*Id2): print(R, "Bug in mul on matrix*vector") except: print(R, "Error in mul on matrix*vector") try: P = Id2.charpoly() except: print(R, "Error in computation of charpoly") try: P = Id2.adjoint() except: print(R, "Error in computation of adjoint") try: P = Id2.commutator(Id2) except: print(R, "Error in computation of commutator") try: P = Id2.echelonize() except: print(R, "Error in computation of echelonize") try: P = Id2.inverse() except: print(R, "Error in computation of inverse") try: P = Id2.rank() except: print(R, "Error in computation of rank") try: P = Id2.kernel() except: print(R, "Error in computation of kernel")
and I did get:
(Symmetric Functions over Rational Field, 'Error in computation of adjoint') (Symmetric Functions over Rational Field, 'Error in computation of echelonize') (Symmetric Functions over Rational Field, 'Error in computation of inverse') (Symmetric Functions over Rational Field, 'Error in computation of rank') (Symmetric Functions over Rational Field, 'Error in computation of kernel') (mod 2 Steenrod algebra, milnor basis, 'Error in computation of adjoint') (mod 2 Steenrod algebra, milnor basis, 'Error in computation of echelonize') (mod 2 Steenrod algebra, milnor basis, 'Error in computation of inverse') (mod 2 Steenrod algebra, milnor basis, 'Error in computation of rank') (mod 2 Steenrod algebra, milnor basis, 'Error in computation of kernel') (Free Algebra on 2 generators (a, b) over Rational Field, 'Error in computation of echelonize') (Free Algebra on 2 generators (a, b) over Rational Field, 'Error in computation of inverse') (Free Algebra on 2 generators (a, b) over Rational Field, 'Error in computation of rank') (Free Algebra on 2 generators (a, b) over Rational Field, 'Error in computation of kernel') (Symmetric group algebra of order 2 over Rational Field, 'Error in computation of echelonize') (Symmetric group algebra of order 2 over Rational Field, 'Error in computation of inverse') (Symmetric group algebra of order 2 over Rational Field, 'Error in computation of rank') (Symmetric group algebra of order 2 over Rational Field, 'Error in computation of kernel') (Non-Commutative Symmetric Functions over the Rational Field, 'Error creating a vector') (Quaternion Algebra (1, 1) with base ring Rational Field, 'Error in computation of echelonize') (Quaternion Algebra (1, 1) with base ring Rational Field, 'Error in computation of inverse') (Quaternion Algebra (1, 1) with base ring Rational Field, 'Error in computation of rank') (Quaternion Algebra (1, 1) with base ring Rational Field, 'Error in computation of kernel')
So It seems to me that error appears when using any algo using a division in coefficient ring... So this ticket should just enable the possibility of doing silently divisions by unital elements of the coefficient ring without searching for fraction_field, is_field or whatever. This remains me the method divide_knowing_divisible_by
of sage integers. If you have a multiple, you don't want as answer a rational.
After, the problem stays very technical since, for speed issues, we don't want to overload all divisions. Can it be done softly ? Is Implementing a new method inverse_knowing_invertible
or inverse_no_division
(just inverse the det) something sufficient ? I don't know enough about matrix code to give a good opinion. I just remember that my very old patch did allows to invert matrices with unital determinant but it did break everything everywhere (My old path did break the scalar multiplication of Sage FreeModule? for example)...
Feel free to reformulate/update/correct the ticket description. My English is pretty horrible and I don't use often the right words.
comment:12 Changed 4 years ago by
- Description modified (diff)
- Summary changed from Matrix and MatrixSpace over ALL rings (not using RingElement...) to Linear algebra over all rings (which are not fields)
comment:13 Changed 4 years ago by
- Keywords RingElement removed
- Milestone changed from sage-6.4 to sage-8.2
- Priority changed from critical to major
This ticket follow the conversation on Sage-combinat-devel :
https://groups.google.com/forum/#!topic/sage-combinat-devel/CJRnG1ppBe0