Opened 3 months ago

Closed 3 months ago

#30161 closed defect (fixed)

Zero Matrix has Inverse over Finite Field

Reported by: gh-prismika Owned by:
Priority: major Milestone: sage-9.2
Component: linear algebra Keywords: m4rie
Cc: malb, slelievre Merged in:
Authors: Martin Albrecht Reviewers: Samuel Lelièvre
Report Upstream: N/A Work issues:
Branch: ccaf79d (Commits) Commit: ccaf79dcb9dd7f34d26b7334c52eb32e619b0811
Dependencies: Stopgaps:

Description

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

Change History (6)

comment:1 Changed 3 months ago by slelievre

  • Cc malb slelievre added
  • Keywords m4rie added

The source code for the __invert__ method, revealed by

sage: M.__invert__??

seems to involve mzed_invert_newton_john from m4rie.

comment:2 Changed 3 months ago by malb

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.

comment:3 Changed 3 months ago by malb

  • Branch set to u/malb/ticket-30161

comment:4 Changed 3 months ago by malb

  • Commit set to ccaf79dcb9dd7f34d26b7334c52eb32e619b0811
  • Status changed from new to needs_review

New commits:

ccaf79dcheck rank before inverting

comment:5 Changed 3 months ago by slelievre

  • Authors set to Martin Albrecht
  • Reviewers set to Samuel Lelièvre
  • Status changed from needs_review to positive_review

Thanks!

comment:6 Changed 3 months ago by vbraun

  • Branch changed from u/malb/ticket-30161 to ccaf79dcb9dd7f34d26b7334c52eb32e619b0811
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.