Open 0f5ae6f6-e03a-45d9-b571-4ce01615e676 opened 10 years ago
0f5ae6f6-e03a-45d9-b571-4ce01615e676
commented
10 years ago Attachment: fix_inversion_for_matrix_with_unital_det-nb.patch.gz
This ticket follow the conversation on Sage-combinat-devel :
https://groups.google.com/forum/#!topic/sage-combinat-devel/CJRnG1ppBe0
tscrim
commented
10 years ago A fix for this would likely include/fix #15947.
videlec
commented
6 years ago 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).
jdemeyer
commented
6 years ago Do you have a concrete example of something that doesn't work currently?
0f5ae6f6-e03a-45d9-b571-4ce01615e676
commented
6 years ago 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.
0f5ae6f6-e03a-45d9-b571-4ce01615e676
commented
6 years ago 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...
jdemeyer
commented
6 years ago 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".
0f5ae6f6-e03a-45d9-b571-4ce01615e676
commented
6 years ago 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
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.
jdemeyer
commented
6 years ago Description changed:
---
+++
@@ -1,6 +1 @@
-Currently MatrixSpace and Matrix can be used properly only on ring whose element inherint from RingElement. Since the new category framework and CombinatorialFreeModule, a huge collection of ring from combinat can't be used as matrix coefficient. For example, the scalar multiplication doesn't work (and from that, nothing work...(charpoly, invertion, adjoint, ...)).
-
-The Goal of this ticket is currently :
-- Try to modify MatrixSpace and Matrix such that all basic operation can be done with special rings
-- Insivibility of modifications concerning usuals ring (especially for speed issues...)
-- Invert matrix with unital determinant for ALL rings
+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), ...Changed keywords from matrix, RingElement, ring to matrix, ring
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), ...
CC: @sagetrac-sage-combinat
Component: linear algebra
Keywords: matrix, ring
Issue created by migration from https://trac.sagemath.org/ticket/15160