nmod_mat_randrank_profile

The rank profile matrix of an $m \times n$ matrix $A$ of rank $r$ is the unique $m \times n$ matrix $\mathcal{R}_A$ with $r$ entries equal to 1, no two in the same row or column, and zeros elsewhere, such that every leading submatrix of $A$ (first $i$ rows, first $j$ columns) has the same rank as the corresponding leading submatrix of $\mathcal{R}_A$. It determines the row and column rank profiles of all leading submatrices of $A$ [DPS2017].

The matrix is computed as one product $L U$: $L$ is $m \times r$ with column $k$ zero above row mrp_r[k], 1 in that row and random below it, and $U$ is $r \times n$ with row $k$ zero left of column mrp_c[k], uniformly random and nonzero in that column, and random to the right of it. The random entries come from nmod_mat_randtest, so that the factors, and therefore the result, are sparse with some probability. Completing $L$ and $U$ into square unit lower and invertible upper triangular matrices gives $A = L' \mathcal{R} U'$ where $\mathcal{R}$ has the entries 1 at the given positions, and multiplying by such triangular matrices does not change the rank profile matrix. If the modulus is 1, the matrix is zero.

@misc{flint-doc-nmod-mat-nmod-mat-randrank-profile,
  author       = {{The FLINT team}},
  title        = {{nmod\_mat\_randrank\_profile (nmod\_mat.h)}},
  howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
  year         = {2026},
  url          = {https://flintlib.org/doc/nmod_mat/nmod_mat_randrank_profile.html},
  note         = {Generated 2026-11-02}
}