grouping non-zero entries in a matrix according to a rule

Question

I have a matrix say, $a = \left[\matrix{ 0 & 1 & 0& 0& 0& 1& 0\\ 0& 0 &0 &0 &0 &1& 1\\ 1& 0 &0 &0 &0 &0 &0\\ 0 &1 &0 &0 &0 &0& 0\\ 0 &0 &1 &0 &1& 0& 0\\ 0& 0& 0 &1 &0 &0 &1}\right]$

I need to enumerate the non-zero elements into groups according to the following: - if two elements share a row or a column they are in the same group, and if say (1,2) & (1,6) in group1, then group1 will also include (2,6) & (2,7) & (6,7) & (4,2), I have been stuck with this fr a while, any help is deeply appreciated.

Answer 1

"if two elements share a row or a column they are in the same group" How?

"and if say (1,2) & (1,6) in group1, then group1 will also include (2,6) & (2,7) & (6,7) & (4,2)" Why not (6,4)?

Use MATLAB:

  % use the function [e1, e2] = find(a)
  e = find(a(i, :)~=0); % i = 1:size(a, 1), e is a vector of size the
  % number of ones in row i. e=[i1, i2, ..., ip]
  % Put in the 1st group the element a(i, e(i1:ip)).
  Group{k}={a(i, e(i1:ip))}; % k=1:...

  for i=1:size(a, 1)
     e{i} = find(a(i, 1)~=0);
  ...

Answer 2

As det has pointed out, although you got most of the entries needed in Group 1, you missed $(6, 4)$, being in the same row as $(6, 7)$. After verifying that there are no more that need to go in Group 1, go on to making Group 2. Hint: There are only three entries left to place into groups, namely $(3, 1)$, $(5, 3)$, and $(5, 5)$.

Answer 3

Thanks guys,

the solution ended up making use of graph adjacency matrix, and disconnected graphs, credit goes to Matt J. on mathworks central:

[I,J]=find(a); C=bsxfun(@eq,I,I.') | bsxfun(@eq,J,J.');

The matrix C is a graph connectivity map which you can then use to segment into groups using this FEX file,

http://www.mathworks.com/matlabcentral/fileexchange/33877-find-graph-conected-components