Re: matrix rank

["Robert G. Brown" <rgb at phy dot duke dot edu>]

On Tue, 23 Nov 2004, Brian Gough wrote:

> Robert G. Brown writes:
>  > I'm getting shot down by antispam software every time I post, so I'll
>  > make this up out of several short messages.  First, for list
>  > statisticians -- I need to evaluate the rank of an MxN (possibly square)
>  > integer matrix.  Is the best routine for this purpose one of the SVD
>  > routines or something else?  I could write one, but I'm trying to use
>  > GSL code where I can as it is likely better than a simple pivoted
>  > elimination (and I don't have to write it:-)
> 
> For practical work the SVD with a suitable cutoff is likely the best
> choice.

I didn't fully understand the problem when I asked -- it is actually a
BINARY rank that I need on the field [0,1] (that is, the rank of a
bitwise matrix like:

 0 1 1 0
 0 1 0 0
 1 1 0 1
 1 1 0 0

The rank is still found with a form of pivoted elimination, but the code
involves lots of bitwise manipulations and masks (although SVD might or
QRPC might well still work, they would be relatively inefficient).

I'm just having a go at writing this myself; although the required bit
manipulations are giving me a mild headache they are relatively
straightforward.

I believe binary rank is used in cryptography and signal processing,
although I'm not certain.  As always, if you are interested in adding
binary rank to the GSL let me know and I'll contribute the code (once
I've validated it).

   rgb

Robert G. Brown	                       http://www.phy.duke.edu/~rgb/
Duke University Dept. of Physics, Box 90305
Durham, N.C. 27708-0305
Phone: 1-919-660-2567  Fax: 919-660-2525     email:rgb@phy.duke.edu