Archived

This topic is now archived and is closed to further replies.

Row or column equal 0

This topic is 5014 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

If its a square matrix then the determinant will be equal to zero (within an error value if using floats or doubles).

If its non-square you''ll probably have to look at all the rows (or columns if num columns < num rows ).

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

Share this post


Link to post
Share on other sites
quote:

If its a square matrix then the determinant will be equal to zero



True, but there are matrices with non-zero rows/columns whose determinants are equal to zero. Consider for example:

[1 2]
[2 4]

[edited by - Muzzafarath on March 22, 2004 11:13:23 AM]

Share this post


Link to post
Share on other sites
Thats true but the matrix is still degenerate in that case.
Just loop through the rows or columns until you find a non-zero value. There might be a better algorithm, its more like a string search than specifically matrix and maths.
You could work out the determinant before looking at the values, of course.
What is it for anyway?

Share this post


Link to post
Share on other sites
You could keep a list of rows and columns which can potentially be filled with 0, and read all elements of the matrix, in order, which belong to a potentially-0 column or row. If it''s a 0, then move on, if it''s not then the corresponding row and column aren''t potentially-0 anymore, and move on. Once you reach the end, any potentially-0 row or column is an actual 0 row or column, and the others aren''t.

Variation : read each potentially-0 row until it turns non-potentially-0, same for columns.

Paradigm shifter : a brute-force search on that problem would be O(n²), and you can achieve even less with a better algorithm, computing the determinant of an nxn matrix is O(n!). The determinant method is therefore a bad idea.

Victor Nicollet, INT13 game programmer

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
what I want is to check if the determinant of a matrix is 0 before to do the determinant, that maybe can avoid some calculus, but I don''t know if the check woll eat more time than do the determinant anyway, although a row or col = 0.

Share this post


Link to post
Share on other sites
If the question is to determine if a row or column has only zeroes in it, I would suggest, for each column and each row, adding the absolute values together and if the sum is zero, then all elements are zero.

That''s (r x c)^2 additions.

To determine if the matrix can be manipulated so a column or a row can be zeroised, you need to evaluate the determinant. If it is zero, then a row or a column can be manipulated to make it zero, if one isn''t already so.




Stevie

Don''t follow me, I''m lost.

Share this post


Link to post
Share on other sites
You might be able to do it via this pseudocode:

while (x < n)
{
while (y < n)
{
if (M[x][y] != 0)
{ x++; y=0; }
}
if (y == n)
return ZERO_ROW;
}


similar for columns. Then it'll run at worst 2n2 times if its a matrix like:
0001
0001
0001
0000

Scout



All polynomials are funny - some to a higher degree.
Furthermore, polynomials of degree zero are constantly funny.

[edited by - MrScout on March 22, 2004 4:07:20 PM]

Share this post


Link to post
Share on other sites
I''m afraid, there isn''t much optimizations to be done, if you already know which column that you want to check, and you don''t want to check all of the columns at once. An if test is as fast as it''s going to get.

Why do you need that? I find it hard to imagine a situation where this operation is a bottleneck; it should be quite fast.

Share this post


Link to post
Share on other sites
There is one small optimization that can be done. Try a bitwise or of all the elements of the row/column, and check that against 0. This way you never need to load any of the elements into the floating point coprocessor and you have reduced conditional branching compared to doing a test against each element one at a time.

Share this post


Link to post
Share on other sites
would something like this be faster?

int checkrow(int y)
{
int sum=0;
int x=0;
while((x++ <= n) && (!sum))
if(array[x][y]) sum=1;

if(x>=dimx) return(0);
return(1);
}

OR

int checkrow(int y)
{
int x=0;
while((x++ <= n))
if(array[x][y]) break;

if(x>=dimx) return(0);
return(1);
}

Share this post


Link to post
Share on other sites