Computing rank of a matrix over a finite field

why is a finite field special? is there a better way than row reduction over Q?

or is the question whether finite fields allow some special method?

i don't know of any. except maybe to use macaulay, a computer program.

 

why doesn't it work? i.e. what is it?

 

Parallel algorithm for rank computation

There is an efficient parallel algorithm (in which you allow many processors but far less time allowed for each of them) which performs significantly better than the row reduction, gaussian elimination etc. The result is due to Ketan Mulmuley and was published in 1986.
http://portal.acm.org/citation.cfm?id=12164

It is known that the determinant can be computed in parallel. In fact, the similar methods can be extended to the coefficients of the characteristic polynomial of the matrix. Determinant is zero means that characteristic polynomial has its constant term as zero. Now can one generalize this to rank ? Namely is the rank of an nxn matrix, exactly n-k where k is the highest power of x which divides the characterestic polynomial ? Not really, in general one can easily construct counter examples for this.

Mulmuley constructs one family of matrices(M) for which the above generalization is actually true. Then he shows that every matrix A can be transformed to a matrix B in M, where the rank of the matrix A is easily recoverable from the rank of B. That gives the parallel algorithm.

Quite simple and elegant.