Linear algebra over all rings (which are not fields)

[sagetrac-nborie]

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

[sagetrac-nborie]

comment:1

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]

comment:4

A fix for this would likely include/fix #15947.

[videlec]

comment:6

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]

comment:7

Do you have a concrete example of something that doesn't work currently?

[sagetrac-nborie]

comment:8

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.

[sagetrac-nborie]

comment:9

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]

comment:10

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

[sagetrac-nborie]

comment:11

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

• MV, VM, cM, Mc, cV, Vc 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.

[jdemeyer]

Changed keywords from matrix, RingElement, ring to matrix, ring