#3158 triangularize gives incorrect result on a matrix containing %i

[Robert Dodier]

From: http://stackoverflow.com/questions/37150735/finding-the-nullity-and-nullspace-in-maxima

(%i1) load (linearalgebra) $
0 errors, 0 warnings
(%i2) trace (triangularize) $
(%i3) M : matrix([0, 1, 1, 0], [-1, 0, 0, 1], [0, 0, 0, 1], [0, 0, -1, 0]) $
(%i4) A : M + %i * ident(4);
                             [ %i   1    1   0  ]
                             [                  ]
                             [ - 1  %i   0   1  ]
(%o4)                        [                  ]
                             [  0   0   %i   1  ]
                             [                  ]
                             [  0   0   - 1  %i ]
(%i5) nullspace (A);
                       [ %i  - 1  0    0   1  0  0  0 ]
                       [                              ]
                       [ 1   %i   0    0   0  1  0  0 ]
1 Enter triangularize [[                              ]]
                       [ 1    0   %i  - 1  0  0  1  0 ]
                       [                              ]
                       [ 0    1   1   %i   0  0  0  1 ]
                      [ %i  - 1  0  0   1     0   0  0 ]
                      [                                ]
                      [ 0    0   0  0  - 1   %i   0  0 ]
1 Exit  triangularize [                                ]
                      [ 0    0   0  0  - %i  - 1  0  0 ]
                      [                                ]
                      [ 0    0   0  0  2 %i   2   0  0 ]
                            [ - 1 ]  [ - %i ]  [ 2 %i ]
                            [     ]  [      ]  [      ]
                            [ %i  ]  [ - 1  ]  [  2   ]
(%o5)                  span([     ], [      ], [      ])
                            [  0  ]  [  0   ]  [  0   ]
                            [     ]  [      ]  [      ]
                            [  0  ]  [  0   ]  [  0   ]

The correct result for nullspace is span(matrix([%i],[1],[0],[0])). The correct result for triangularize should be a rank-3 matrix.

Tracing totaldisrep shows that some MRAT expressions in the result are zero. It appears that these occur because %i is replaced by a gensym (via RATREP*), and, I speculate, TFGELI (Gaussian elimination) doesn't notice that some expressions containing the gensym are zero.

I find that replacing triangularize by ptriangularize (in share/linearalgebra) enables nullspace to get the correct result.

I find that echelon seems to succeed (returning a rank-3 matrix) where triangularize fails:

(%i10) echelon(matrix([%i,-1,0,0,1,0,0,0],[1,%i,0,0,0,1,0,0],
                                            [1,0,%i,-1,0,0,1,0],[0,1,1,%i,0,0,0,1]));
                   [ 1  %i   0    0    - %i   0     0    0 ]
                   [                                       ]
                   [ 0  1   - 1  - %i  - 1    0     %i   0 ]
                   [                                       ]
(%o10)             [                    1            %i  1 ]
                   [ 0  0    1    %i    -     0    - --  - ]
                   [                    2            2   2 ]
                   [                                       ]
                   [ 0  0    0    0     1    - %i   0    0 ]

Since echelon calls TFGELI too, I don't know why the result is different. Maybe it only works correctly in special cases. Or maybe I'm wrong about the role of MRAT expressions and the problem is due to some bug specific to triangularize.

[Robert Dodier]

I see that echelon enables the algebraic flag, while triangularize does not. I find that algebraic:true before calling nullspace or triangularize enables it to return the correct result. This suggests a bug fix is to copy the logic concerning algebraic from echelon to triangularize.

[Robert Dodier]

Fixed by commit [c9375b3] which copies the logic for binding algebraic from echelon to triangularize. Closing this report.