FLINT3.7.0-dev
/

fmpz_mat_rref_upper_certify_lu_mod_p

Synopsis#include <flint/fmpz_mat.h>
int fmpz_mat_rref_upper_certify_lu_mod_p(fmpz_mat_t E, fmpz_t den, const fmpz_mat_t A, slong rank, const slong * P, const slong * pivs)source

Given the echelon structure of the m×nm \times n matrix AA modulo a prime, as computed by nmod_mat_lu_with_pivots (the rank rr modulo pp, the row permutation P and the array pivs of the rr pivot columns followed by the other columns), tries to compute and certify the first rr rows of the reduced row echelon form of AA over Q\mathbb{Q}. Returns 1 on success, with (EE, den) holding these rows, and 0 if the prime was unlucky.

EE must be an r×nr \times n zero matrix not aliased with AA. The function solves BE2=den⋅CB E_2 = \mathit{den} \cdot C exactly, where BB and CC are the pivot rows of AA restricted to the pivot and the other columns, checks that (E,den)(E, \mathit{den}) is in reduced row echelon form, and checks that the other rows of AA are annihilated by the nullspace basis that EE defines. Both checks are exact, so a result of 1 is a proof. With probability close to 1 for a random prime, the rank modulo pp equals the rank of AA and the function succeeds; otherwise it returns 0 and EE and den are unspecified.

Cite this page

The FLINT team, “fmpz_mat_rref_upper_certify_lu_mod_p (fmpz_mat.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/fmpz_mat/fmpz_mat_rref_upper_certify_lu_mod_p.html (generated 2026-11-02).