ELA, Volume 11, pp. 16-23, February 2004, abstract.
Matrix Rank Certification
B. David Saunders, Arne Storjohann, and Gilles Villard
Randomized algorithms are given for computing the rank
of a matrix over a field of characteristic zero with
conjugation operator. The matrix is treated as a black
box. Only the capability to compute matrix by column-vector
and row-vector by matrix products is used. The methods
are exact, sometimes called seminumeric. They are appropriate
for example for matrices with integer or rational entries.
The rank algorithms are probabilistic of the Las Vegas type;
the correctness of the result is guaranteed.