Set rows and column to zero

Question

I am building an algorithm in Matlab that takes an n by m matrix A of real numbers and sets the entries to zero in each of its columns and rows exactly when the original A has at least one zero entry in them.

The exercise explicitly asks me to ensure that the algorithm uses an additional storage of n+m variables (I don't really know what this means, so an explanation would be so much appreciated) and I need to present a brief complexity analysis of this implementation of the algorithm such that it completes in f(n,m) steps whenever A is a n by m matrix.

I've browsed on the web to find if someone already solved the problem and I've run into some Python code that I tried to adapt in Matlab. The problem is that whenever the given matrix has a single zero, all the elements are set to zero.

A = [ 0 2 1; 4 1 6; 3 7 1; 1 3 1; 4 1 1];
m=size(A,1);
n=size(A,2);
row=false;
column=false;



for i = 1:m
        if A(i,:) == 0
            row=true;
            break
        end
end

for j = 1:n
        if A(:,j) == 0
            column=true;
            break
        end
end

for i = 1:m
    for j = 1:n
        if A(i,j) == 0
            A(i,:)=0;
            A(:,j)=0;
        end
    end
end

for i= 1:m
    if A(i,:) == 0
        for j=1:n
            A(i,j)=0;
        end
    end
end

for j=1:n
    if A(:,j) == 0
        for i=1:m
            A(i,j) = 0;
        end
    end
end

if row == true
    for i=1:m
        A(i,:)=0;
    end
end

if column == true
    for j=1:n
        A(:,j)=0;
    end
end

Answer 1

Ok beaker, thanks to your hints I've finally written working code! Here it is:

[m, n] = size(A);
rowsWithZero = false(1,m);
colsWithZero = false(1,n);

for ii=1:m
    for jj=1:n
        if A(ii,jj) == 0
            rowsWithZero(ii) = true;
            colsWithZero(jj) = true;
        end
    end
end

for ii = 1:numel(rowsWithZero)
        if rowsWithZero(ii) == true
            A(ii,:)=0;
        end
end

for jj = 1:numel(colsWithZero)
        if colsWithZero(jj) == true
            A(:,jj)=0;
        end
end

Now I'll update a little bit later in order to discuss algorithm complexity. Moreover, I came up with some code that is more "Matlab oriented" that solves the problem with fewer lines:

[r,c] = find(A==0);

for i = 1:numel(r)
    A(r(i),:)=0;
end

for j = 1:numel(c)
    A(:,c(j))=0;
end

But in this second case we don't really know in how many steps the function find completes the search and it's a little bit difficult to do a proper complexity analysis.

But I think that the algorithm that uses logical indexing should complete in, at worst, m*n + m+ n steps.

Please correct me if there's anything wrong! Thanks a lot to everybody who wants to help and participate!

Answer 2

I'll give you a chance to work out an answer for yourself, but here's an outline of the program you need:

• Find out which rows already have at least one 0 in them

  • This will be stored in a vector with m elements

• Find out which columns already have at least one 0 in them

  • This will be stored in a vector with n elements

• Now, zero out the rows and columns identified above

  • You don't want to zero out the rows before you identify which columns already have zeros, because if you do, all of them will have zeros! (Assuming there is at least one zero in the matrix.)

The two vectors with m and n elements is where you get the m+n additional space.

Note: The strange wording "additional storage of n+m variables" could just mean "O(n+m) additional space" (which would be quite normal), or it could mean that your calculations can use as much space as they want as long as you store the results in variables that take up no more than O(n+m) space (which would be a bit weird). Some clarification on this point would help.

---

How to find which rows/columns contain at least one zero:

Here's the most straightforward way to do it using a double loop. I'll add more discussion on this as soon as I get a bit more time.

[m, n] = size(A);
rowsWithZero=false(1,m);
colsWithZero=false(1,n);

for ii=1:m
   for jj=1:n
      if A(ii,jj) == 0
         %// Row ii, Col jj has a zero... mark it in the vectors
         rowsWithZero(ii) = true;
         colsWithZero(jj) = true;
      end
   end
end

Using for loops to access matrix elements isn't the most "Matlab" way of doing things, but I'll address that a bit later. For now, note that I've used false and true to build the vectors. This should be a clue that the next step should use logical indexing.