How do I define a block of a $(0,1)$-matrix as one that has no proper sub-blocks?

48 Views Asked by At

I'm struggling to come up with a definition of a "block" in a $(0,1)$-matrix $M$ such that we can decompose $M$ into blocks, but the blocks themselves don't further decompose. This is what I've got so far:

Given any $r \times s$ $(0,1)$-matrix $M$, we define a block of $M$ to be a submatrix $H$ in which: (a) every row and every column of $H$ contains a $1$, (b) in $M$, there are no $1$'s in the rows of $H$ outside of $H$, (c) in $M$, there are no $1$'s in the columns of $H$ outside of $H$, and (d) no proper submatrix of $H$ satisfies (a)-(c).

I want to define blocks in such a way that there are no proper sub-blocks in blocks. But I feel item (d) is difficult to parse. I can't just say "there's no proper sub-blocks" because this is a circular definition.

Q: Could the community suggest a better way of phrasing this definition?

My conundrum reminds me of this comic:

But *I* know what I mean!

1

There are 1 best solutions below

1
On BEST ANSWER

I would suggest breaking this up into two definitions... maybe call one of them a "block", and another a "simple block". That is:

Given any $r \times s$ $(0,1)$-matrix $M$, we define a block of $M$ to be a submatrix $H$ in which: (a) every row and every column of $H$ contains a $1$, (b) in $M$, there are no $1$'s in the rows of $H$ outside of $H$, (c) in $M$, there are no $1$'s in the columns of $H$ outside of $H$.

A sub-block of a block $H$ is a block $J$ of the submatrix $H$. If $J \neq H$, then $J$ is a proper sub-block.

We say that $H$ is a simple block if it has no proper sub-block.

How's that? Alternatively, call the first one a "pre-block", and the second a "block" (cf. pre-sheaf vs. sheaf).