Takasaki

asked on

What is the most rapid algorithmic way you can think of to find the rank of a square, binary matrix?

-no Gauss (e.g. pivoting)

-no Smith

-no SVD

Preferably with XOR row and col operations only.

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

I guess I'm looking for linear independence tests for each col/row and counting those that are as such.

Psuedocodes only, please (C++ notation preferred).

Thanks!

-Tak

-no Gauss (e.g. pivoting)

-no Smith

-no SVD

Preferably with XOR row and col operations only.

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

I guess I'm looking for linear independence tests for each col/row and counting those that are as such.

Psuedocodes only, please (C++ notation preferred).

Thanks!

-Tak

Last Comment

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,

for(i=0;i<NumberofRows<i++

{

Row[i]=Row[i] XOR Row[i+1]

for(j=0;j<NumberofColumns;

{

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,

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;

{

if element(j)==1 continue; //element is an individual in the row

else rank--;

}

}

Regards,

View this solution by signing up for a free trial.

Members can start a 7-Day free trial and enjoy unlimited access to the platform.

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

Sorry for that

Sorry for that

ASKER

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.

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 :)

Well, you could brute-force it (check every combination of rows), but that doesn't seem like a very efficient way :)

ASKER

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.

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.

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

>>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

ASKER

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

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 :)

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.

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.

View this solution by signing up for a free trial.

Members can start a 7-Day free trial and enjoy unlimited access to the platform.

View this solution by signing up for a free trial.

Members can start a 7-Day free trial and enjoy unlimited access to the platform.

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

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

Computer101

EE Admin

C++

C++ is an intermediate-level general-purpose programming language, not to be confused with C or C#. It was developed as a set of extensions to the C programming language to improve type-safety and add support for automatic resource management, object-orientation, generic programming, and exception handling, among other features.

58K

Questions

--

Followers

--

Top Experts

Get a personalized solution from industry experts

TRUSTED BY

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,