Matrix rank certification

Abstract

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 x column vector and row-vector x 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 probablistic of the Las Vegas type; the correctness of the result is guaranteed.