# MATLAB Puzzler: Removing columns and rows from binary matrices 35

Posted by **Doug Hull**,

```
a=[
0 1 1 0 0
0 0 1 0 1
0 0 1 0 0
0 0 1 0 1
0 0 1 0 1]
```

The above is a good test matrix, but you can generate more random ones with this:
`a = full(round(sprand(5,5,0.8)))`

I was surprised that Jiro and I took very different paths to solving this problem. Post your solutions in the comments area along with how long it took you to solve.

**[NOTE] After a week, a wrap-up was posted for this Puzzler. [click here]**

## 35 CommentsOldest to Newest

**1**of 35

**2**of 35

```
a = [
0 1 0 1 0
0 1 0 0 0
1 1 0 0 0
0 1 0 0 1
0 0 0 1 1]
```

The above solution reports columns [3 2] to be removed, but it is actually [1 3] to be removed.
The keeping track of the indices is tricky.
Doug **3**of 35

**4**of 35

**5**of 35

```
a =[
0 0 0 0 0
1 0 0 1 0
0 1 0 0 0
1 0 0 0 1
1 0 0 0 0];
```

The solution you submitted misses this (all rows are eliminated).
Doug **6**of 35

**7**of 35

**8**of 35

**9**of 35

```
a =[
1 1 0 0 0
1 0 0 0 0
0 0 0 0 0
1 0 1 0 0
1 0 0 0 0];
```

I can see that for the next puzzler, I am going to need to make a test harness to send out with the problem. I have already produced next week's puzzler, but I can do it for the future ones.
Thanks for playing around.
Doug **10**of 35

**11**of 35

**12**of 35

**13**of 35

```
a = [
0 0 0 0 1
0 0 0 0 0
1 0 0 0 1
1 0 1 0 0
0 0 0 0 0];
```

You did the right thing by running the elimination a second time, but it is possible that you need to run once for each column. A while loop is the right thing to do here.
Replacing the rows with NaN is a good idea so that you can keep the matrix the same size throughout, that means you do not have to keep track of tricky index math when the matrix is shrinking.
The way you eliminate the NaN at the end works, but it is more difficult to understand than other methods because the reshape operation is a little non-intuitive. Look at my elimination strategy for a different implementation.
Thanks for letting me critique the code and for playing along.
Doug **14**of 35

**15**of 35

```
a = [
0 1 0 1 0
0 1 0 0 0
1 1 0 0 0
0 1 0 0 1
0 0 0 1 1]
```

fails. Your code produces:
```
r =
0 0 1 0 0
```

The correct answer is below:
Remove these columns: 1 3
```
a =
1 0 0
1 0 1
0 1 1
```

Note that by eliminating the third column and row, the first column then becomes all zeros.
I am not sure I understand how your code would work since this needs to be an iterative solution.
Thanks for playing!
Doug **16**of 35

**17**of 35

```
zerocols=find(any(a)==0);
```

can be replaced with
```
zerocols = find( all(~a) )
```

It just seems more intuitive to parse mentally, at least to me.
Removing the correct rows and columns was done in my code like this:
```
a(newEmptyCols,:) = [];
a(:,newEmptyCols) = [];
```

Where newEmptyCols was a list of columns to be eliminated.
This avoids the reshape.
Thanks for playing!
Doug **18**of 35

**19**of 35

```
a = full(round(sprand(5,5,0.8)))
```

Has anyone else had problems with the second video? I have tested it and it is working.
Thanks,
Doug **20**of 35

**21**of 35

```
a =
0 0 0 0 0
0 0 0 0 1
1 0 1 0 1
0 0 1 1 1
0 0 0 0 0
```

Sorry, but your code fails on the above input!
Doug **22**of 35

**23**of 35

**24**of 35

idx = 1; szA = size(a, 2); remCols = 1:szA; while ~isempty(a) && any(~sum(a)) id(idx) = find(sum(a)==0, 1, 'first'); remCols(id(idx)) = []; a(id(idx),:) = []; a(:,id(idx)) = []; end disp(['Remove these columns: ', num2str(setdiff(1:szA, remCols))]); a"remCols" keeps track of the remaining columns. And at the end, I take the set difference between all columns and the remaining, and they are the columns that I deleted. But then after spending about another 15 minutes, I realized that I actually didn't need to keep "id". And I also realized that I can do the row and column deletion in one line. So this is a more streamlined code that I ended up with:

szA = size(a, 2); remCols = 1:szA; while ~isempty(a) && any(~sum(a)) id = find(sum(a)==0, 1, 'first'); remCols(id) = []; a = a(setdiff(1:size(a,2),id), setdiff(1:size(a,2),id)); end disp(['Remove these columns: ', num2str(setdiff(1:szA, remCols))]); a

*I hope you all enjoyed doing this puzzler. Thanks, Doug, for doing this. We should definitely do more of these.*

**NOTE:**Everyone, you can now use the <pre></pre> tag to display your code using fixed-width font in your comments. There's also a "preview" button above that you can use to preview your comment. (Javascript is required for this feature)

**25**of 35

```
a=a([1:i-1 i+1:length(a)],[1:i-1 i+1:length(a)])
```

This really highlights the indexing capability of MATLAB, where you can specify vector indices to extract a submatrix of a matrix.
Steve talks about this in one of his blog posts:
https://blogs.mathworks.com/steve/2008/02/08/linear-indexing/ **26**of 35

k = 1 ; while (a column in A exists with 1 nonzero) do let A(i,j) be the single nonzero in a column j where nnz(a(:,j)) == 1 remove column j and row i from the matrix A row i becomes the kth row of U column j becomes the kth column of L k = k + 1 endThen repeat, but looking for rows with one entry instead. You can see the effect of this with [L,U,P,Q] = lu(A) for, say the west0479 matrix: load west0479 [L,U,P,Q]=lu(west0479) ; spy(L+U) If you look closely, you can see that the first 25 rows of U have lots of nonzeros in them, but the first 25 columns of L have just one nonzero in them. The first loop (above) iterated 25 times. If A were a morally or psychologically triangular matrix, then this process would eliminate all of A, leaving L equal to the identity matrix, and U a permuted version of A. Then the next 108 rows of U have just one entry each but the same columns of L have lots of nonzeros. The the rest of the matrix is factorized using a sparse LU factorization. So ... how would you do this binary thing efficiently for a huge sparse binary matrix? Note that x=A(i,:) is very slow for a sparse A, but x=A(:,j) is fast (if you want x=A(i,:) for lots of rows i, then do B=A' ; x=B(:,i) instead). How's that for an extension to your puzzler?

**27**of 35

function res = puzzler(a) sub = 1:size(a, 1); rem = zeros(1, 0); zer = 0; while ~isempty(zer) zer=find(sum(a(sub, sub), 1)==0); rem = [rem sub(zer)]; sub(zer)=[]; end disp(sprintf('Removed: %s', mat2str(rem))); res = a(sub,sub);(this works "in place" without disturbing the contents of a)

**28**of 35

**29**of 35

while ~isequal(any(A),any(A,2)') A(~any(A),:)=0; end disp(['Removed columns: ',num2str(find(~any(A)))]); disp(A(any(A),any(A)));

**30**of 35

```
A = [
0 1 0 0 0
0 0 0 0 0
0 0 0 0 0
1 0 0 1 0
0 0 0 0 1]
```

What I notice with your code is that it works, but after five minutes, I still do not really understand why. It is very clever, more clever than me!
My goal in writing code is to make people understand it as easily as the computer does. More often than not, the person that will need to understand it is me in a few weeks once I have forgotten all about it. Here is my solution:
```
a = full(round(sprand(5,5,0.8)))
oldEmptyCols = [];
newEmptyCols = all(~a);
%
while ~isequal(oldEmptyCols, newEmptyCols)
a(newEmptyCols,:) = 0;
oldEmptyCols = newEmptyCols;
newEmptyCols = all(~a);
end
% display results
disp ('---------------')
disp(['Remove these columns: ' num2str(find(newEmptyCols))])
find(newEmptyCols)
%
a(newEmptyCols,:) = [];
a(:,newEmptyCols) = []
```

Notice that with a good variable naming scheme and use of functions that are pronounceable, this code is very readable, even without comments.
For example, I picked:
`~isequal(oldEmptyCols, newEmptyCols)`

instead of
`~(oldEmptyCols == newEmptyCols)`

Little things like this make the code easier to understand when you need to deal with it again later.
Doug **31**of 35

while ~isequal(any(A) & any(A,2)', any(A')) A(~any(A),:)=0; end disp(['Removed columns: ',num2str(find(~any(A)))]); disp(A(any(A),any(A)));The first code is based on the fact that a diagonl mtrix left-multiply a matrix equivalent to multiply the matrix row by row with the corresponding elements in the diagonal vector. Hence, any(A) get a vector with 1 where the coulmn is not full zero, 0 otherwise. Using this vector to form a diagonl mtrix to left multiply A will set rows of A either all zero (multiply by 0 where corresponding column is all zero) or no change (multiply 1 where corresponding column is not full zero). This is exactly your puzzle required. In the code, double is used to convert logical variable produced by any(A) to double so that the multiplication can be performed. Hope this makes the code understandable.

**32**of 35

**33**of 35

**34**of 35

**35**of 35

colsRemoved=[]; %While you are larger than 2x2 and you most recently found a zero column while (length(colsRemoved) < length(a)-2) && (k~= length(a)) for k=1:length(a)%for however large the matrix is if ( max(a(:,k)) <1 && ( max(a(:,k)~=-1 )) ); %if the column is zero a(k,:)=-1; %change the value of the row to -1 a(:,k)=-1 %change the value of the column to -1 colsRemoved(end+1)=k; break; end end end %Now go through and remove all the -1's. while find(a==-1) for k=1:length(a) if max(a(:,k)==-1) a(k,:)=[]; a(:,k)=[]; break end end end a disp(['Removed column numbers: ' num2str(colsRemoved)])

## Recent Comments