Univariate polynomial matrix, bug in minimal kernel basis for input zero matrix

[vneiger]

Is there an existing issue for this?

• I have searched the existing issues for a bug report that matches the one I want to file, without success.

Did you read the documentation and troubleshoot guide?

• I have read the documentation and troubleshoot guide

Environment

- **OS**: Ubuntu 22.04
- **Sage Version**: 10.0.beta3

Steps To Reproduce

Run these few lines:

m = 2; n = 1; field = GF(97)
pring.<x> = field[]
F = Matrix(pring,m,n)
K = F.minimal_kernel_basis()

The parameters in the first line do not matter for the bug: any other field, and any other matrix dimensions will lead to the same (faulty) behaviour.

Expected Behavior

According to the documentation, this should compute an ordered weak Popov basis K for the left kernel of F, which is here the m x n zero matrix. Here the kernel is generated by the m x m identity matrix (or any m x m unimodular matrix). So in this case, this means K should be a lower triangular m x m matrix with constant entries (i.e. elements of the base field) and diagonal entries nonzero.

Actual Behavior

Fails with

[..] in sage.matrix.matrix_polynomial_dense.Matrix_polynomial_dense.minimal_kernel_basis()
   3973             # compute approximant basis and retrieve kernel rows
-> 3974             P = self.minimal_approximant_basis(orders,shifts,True,normal_form)
[..]

in sage.matrix.matrix_polynomial_dense.Matrix_polynomial_dense.minimal_approximant_basis()
   3575     if o < 1:
-> 3576         raise ValueError("order should consist of positive integers")
[..]
ValueError: order should consist of positive integers

Additional Information

The method minimal_kernel_basis computes some "approximation order" which depends on the degree of the input matrix, and then calls minimal_approximant_basis. Here since the matrix is zero the computed order is nonpositive, which is not acceptable input for the approximant basis method.

Decision to take: either deal with this kernel computation as a particular case (e.g. setting the approximation order to be 1); or modify the approximant basis method to return the identity matrix when the input order is 0. The latter seems preferable but this must be thought of more in depth.

More generally, it should be checked whether there is any risk of creating negative approximation orders with the current code of minimal_kernel_basis, in particular when shifts are involved.

[vneiger]

PS: just asked membership to triage, not able yet to add other labels (c: linear algebra, p: minor). I can handle this issue easily, will do in the coming weeks if not solved already by someone else.

[vneiger]

Additional situations to fix:

• Working row-wise (left kernel), when the input matrix is constant and has some zero column, then the constructed orders may also have zero entries (depending on the input shift). Easy to fix since zero columns do not impact the left kernel. Similar situation when working column-wise, with constant input matrix containing a zero row.
• This method fails when the row or column dimension is zero, but for consistency with left_kernel this should return an empty kernel.