Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Computing rank of a matrix over a finite field

  1. Mar 21, 2006 #1

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    How would one go about computing the rank of a matrix over a finite field? Obviously row reduction could be used... is there a better way?
     
  2. jcsd
  3. Mar 21, 2006 #2

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    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.
     
  4. Mar 21, 2006 #3

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Both!

    I'm under the impression that the singular value decomposition is generally superior to gaussian elimination when working over the reals or complexes. (but the algorithm I've seen simply won't work over a finite field)

    And, I suspect that there ought to be a good way to do it over a finite field.
     
  5. Mar 22, 2006 #4

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    why doesn't it work? i.e. what is it?
     
  6. Mar 22, 2006 #5

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    The algorithm I saw involved finding a subprocedure called "House" -- something relating to something called a Householder matrix.

    The algorithm for house involved dividing by something positive -- when I naively tried to apply it to a finite field, it required a division by zero.

    I think the house algorithm is, given a vector x, supposed to return b and v such that [itex](I - \beta \nu \nu^T) x = ||x|| e_1[/itex]. The algorithm blew up on the computation of b... I tried assuming it had v right, and found that such a beta cannot exist.

    Furthermore, I don't really have a norm on a vector space over a finite field -- many of the interesting vectors have a zero inner product with themselves! So, I strongly suspect that in such cases, even if house could be properly tweaked, I don't know if it would give interesting results at all!
     
  7. May 6, 2007 #6
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Computing rank of a matrix over a finite field
Loading...