• ### Announcements

#### Archived

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

# Row or column equal 0

## Recommended Posts

Silly_con    136
Anyone know a good logic test, fast algorithm, to detect if a column or a row in a nxn matrix is equal to 0 ?

##### Share on other sites
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 on other sites
Muzzafarath    146
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 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 on other sites
ToohrVyk    1595
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 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 on other sites
stevie56    145
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.

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

##### Share on other sites
MrScout    120
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 on other sites
Cedric    158
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 on other sites
SiCrane    11839
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 on other sites
healeyx76    136
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);
}