How to identify blocks in a diagonal block matrix?

I have the following type of block diagonal matrix whose non-overlapping "blocks" I would like to indentify. These blocks may vary in size and may contain zeros.

M = [
    1	1	1	0	0	0	0	0	0	0	0	0
    1	1	1	0	0	0	0	0	0	0	0	0
    1	1	1	0	0	0	0	0	0	0	0	0
    0	0	0	1	1	1	0	0	0	0	0	0
    0	0	0	1	1	1	0	0	0	0	0	0
    0	0	0	1	1	1	0	0	0	0	0	0
    0	0	0	0	0	0	1	0	0	0	0	0
    0	0	0	0	0	0	0	1	0	1	0	0
    0	0	0	0	0	0	0	0	1	1	1	1
    0	0	0	0	0	0	0	1	1	1	0	1
    0	0	0	0	0	0	0	0	1	0	1	1
    0	0	0	0	0	0	0	0	1	1	1	1]

For this specific example, there are 4 distinct blocks whose indices are:

1, 2, 3 (3x3 block)

4, 5, 6 (3x3 block)

7 (1x1 block)

8, 9, 10, 11, 12 (4x4 block)

[Paul]

What's the rule for identifying a distinct block? For example, why isn't 7 - 12 considered a single 5 x 5 block?

[Ludovic Tenorio]

The reason the element at indices (7,7) is its own block (and not part of the block on the lower right like you suggested), is because it's the only value over that row/colum (i.e. if you sum over either the 7th column or row, you get a value of one). I realize my definitition of block is a little arbitrary here, hopefully this clarifies things.

Answer 1

[Stephen23]

This is not very pretty, but it gets the job done. Note for simplicity it only handles square matrices and assumes square, non-overlapping blocks of data. Extending this approach to non-square matrices and blocks might be possible.

M = [1,1,1,0,0,0,0,0,0,0,0,0; 1,1,1,0,0,0,0,0,0,0,0,0; 1,1,1,0,0,0,0,0,0,0,0,0; 0,0,0,1,1,1,0,0,0,0,0,0; 0,0,0,1,1,1,0,0,0,0,0,0; 0,0,0,1,1,1,0,0,0,0,0,0; 0,0,0,0,0,0,1,0,0,0,0,0; 0,0,0,0,0,0,0,1,0,1,0,0; 0,0,0,0,0,0,0,0,1,1,1,1; 0,0,0,0,0,0,0,1,1,1,0,1; 0,0,0,0,0,0,0,0,1,0,1,1; 0,0,0,0,0,0,0,0,1,1,1,1];
char(M+'0') % just for compact display of the entire matrix

ans = 12×12 char array
    '111000000000'
    '111000000000'
    '111000000000'
    '000111000000'
    '000111000000'
    '000111000000'
    '000000100000'
    '000000010100'
    '000000001111'
    '000000011101'
    '000000001011'
    '000000001111'

assert(isequal(diff(size(M)),0),'matrix must be square')
C = {};
B = 1; % block begin
E = B; % block end
R = size(M,1);
while B<R
    while E<R && any(any(M(E+1:R,B:E)|M(B:E,E+1:R).'))
        E = E+1;
    end
    C{end+1} = M(B:E,B:E); %#ok<SAGROW>
    E = E+1;
    B = E;
end

Checking:

C

C = 1×4 cell array
    {3×3 double}    {3×3 double}    {[1]}    {5×5 double}

C{:}

ans = 3×3

1 1 1 1 1 1 1 1 1

ans = 3×3

1 1 1 1 1 1 1 1 1

ans = 1

ans = 5×5

1 0 1 0 0 0 1 1 1 1 1 1 1 0 1 0 1 0 1 1 0 1 1 1 1

[Ludovic Tenorio]

That works, thank you!