  In this paper, we give novel certificates for triangular equivalence and rank
profiles. These certificates enable somebody to verify the row or column rank
profiles or the whole rank profile matrix faster than recomputing them, with a
negligible overall overhead. We first provide quadratic time and space
non-interactive certificates saving the logarithmic factors of previously known
ones. Then we propose interactive certificates for the same problems whose
Monte Carlo verification complexity requires a small constant number of
matrix-vector multiplications, a linear space, and a linear number of extra
field operations , with a linear number of interactions. As an application we
also give an interactive protocol, certifying the determinant or the signature
of dense matrices, faster for the Prover than the best previously known one.
Finally we give linear space and constant round certificates for the row or
column rank profiles.
