Zero Matrix has Inverse over Finite Field

[prismika]

The bug is outlined in this post: https://ask.sagemath.org/question/52487/zero-matrix-has-an-inverse-over-finite-field/

In short, the following lines of code should throw an error, but they do not.

M = Matrix([0], ring=GF(4))
M.inverse()

Instead they return the matrix [1].

CC: @malb @slel

Component: linear algebra

Keywords: m4rie

Author: Martin Albrecht

Branch/Commit: ccaf79d

Reviewer: Samuel Lelièvre

Issue created by migration from https://trac.sagemath.org/ticket/30161

[slel]

comment:1

The source code for the __invert__ method, revealed by

sage: M.__invert__??

seems to involve mzed_invert_newton_john from m4rie.

[slel]

Changed keywords from none to m4rie

[malb]

comment:2

Yep, that's a bug in m4rie:

mzed_t *mzed_invert_newton_john(mzed_t *B, const mzed_t *A) {
  assert(A->nrows == A->ncols);
  mzed_t *I = mzed_init(A->finite_field, A->nrows, A->ncols);
  mzed_set_ui(I, 1);
  mzed_t *T = mzed_concat(NULL, A, I);
  mzed_free(I);

  rci_t r = mzed_echelonize_newton_john(T, 1);
  if (r != A->nrows) 
    m4ri_die("mzed_invert_newton_john: input matrix does not have full rank.");
  B = mzed_submatrix(B, T, 0, A->ncols, A->nrows, T->ncols);
  mzed_free(T);
  return B;
}

We first add an identity matrix and then check if the whole thing has full rank, which is nonsense.

[malb]

Branch: u/malb/ticket-30161

[malb]

Commit: ccaf79d

[malb]

New commits:

ccaf79d

check rank before inverting

[slel]

Reviewer: Samuel Lelièvre

[slel]

comment:5

Thanks!

[slel]

Author: Martin Albrecht

[vbraun]

Changed branch from u/malb/ticket-30161 to ccaf79d