Rank of square binary matrix - algorithm?

>>I don't want to access each matrix element individually.

In my opinion you should XOR every column or row and then count if there 1 in the column or row if so rank++, skip to next column or row

however in my opinion when XORing you should access each element of row or column

Regards,

Rank=m; //m is number of your rows

for(i=0;i<NumberofRows<i++)
{
    Row[i]=Row[i] XOR Row[i+1]
   for(j=0;j<NumberofColumns;j++)
  {
    if element(j)==1 continue; //element is an individual in the row
   else rank--;
  }
}

Regards,

 

btw,

element(j) is in Row[0]

I changed the code a little bit

for(i=1;i<NumberofRows<i++)
{
    Row[0]=Row[0] XOR Row[i]
   for(j=0;j<NumberofColumns;j++)
  {
    if element(j)==1 continue; //element is an individual in the row
   else rank--;
  }
}

Regards,

I checked with m>5 the code seem to give errors

Sorry for that

Hi MacroLand,

In your mind's eye, try to run a 3x3 identity matrix through your algorithm.
The rank will be 2.
Good attempt, though.

The code in Infinity08's post is practically gaussian elimination, which Takasaki said was out of bounds.  But I don't understand how one could test the rank of a matrix without using some form of gaussian elimination.

>>  But I don't understand how one could test the rank of a matrix without using some form of gaussian elimination.
Well, you could brute-force it (check every combination of rows), but that doesn't seem like a very efficient way :)

Infinity8:

Thank you for digging up that great thread.  However, everyone there is focused on architecture implementation, sign-edness, shifting etc.  I'm not limited to 32 bits or sign because I have access to big number packages, like my favorite NTL.

Also, Rank32(...) might crash (go OOB) if the array length is less than 32.  To avoid these problems, I requested psuedocode.

   

>>  I'm not limited to 32 bits or sign because I have access to big number packages, like my favorite NTL.
In that case, you can use the same algorithm with some unlimited-length unsigned integer value. I assume that you can use your big number package for that.

>> Also, Rank32(...) might crash (go OOB) if the array length is less than 32.
Well, the code is only an example of how you could do it - not how you should do it.

btw, you can easily treat matrices smaller than 32x32 with this method by putting the rest of the matrix to 0.

Hi Takasaki,

>>try to run a 3x3 identity matrix through your algorithm.

1 0 0
0 1 0
0 0 1

My idea was to take row 1 XOR with Row 2 and XOR with Row 3

if result was 0 0 0 then rank=rank-1

the result would be 1 1 1 so rank would not change which would be equal to rank=m=3

idea also worked with

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

result was 0 0 0 so rank would be m -1

but failed with

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

where rank is 3 but algorithm found it to be 4. Even with scanning row i to row j where j=i+1

Regards

Everyone:

These algorithms are still based on Gauss, and maybe that is the only way.

Then, the first order of business in a decent algorithm is to rapidly determine if the binary matrix has full-rank or if it is deficient.  If it is deficient, then one of these algorithms can be run.

Is there a rapid method to determine full-rank status first (again, no Gauss, no LU, no pivoting, etc)?
Especially, I do not want to calculate the determinant, or to check the diagonal entries in an L (or U) matrix.

Also, searching for identical rows/cols is a little weak... a global algorithm should account for that automatically. Again, psuedocode please.

Thanks!
-Tak

>> Is there a rapid method to determine full-rank status first
Not faster than just finding the rank.

Of course there are special situations like identical rows, but you can't base an algorithm on special cases :)

A good algorithm will always look like Gauss in some way - it's not for nothing that it's the most used way to determine the rank of a matrix :)

There are some simple checks you can do to determine some trivial cases when the rank is not full.  

If any row is all zeros, there is an empty row and the rank is not full.

OR together all the rows.  If any of the first n bits are zero, there is an empty column and the rank is not full.

No comment has been added to this question in more than 21 days, so it is now classified as abandoned.

I will leave the following recommendation for this question in the Cleanup Zone:
  Split: Infinity08 {http:#18586058} & BigRat {http:#18608373} & NovaDenizen {http:#18609641}

Any objections should be posted here in the next 4 days. After that time, the question will be closed.

Sean Durkin
Experts Exchange Cleanup Volunteer

Forced accept.

Computer101
EE Admin