I have encountered a fairly structured $M\times N$ matrix $A$:

  • $A$ has only $1$s and $0$s
  • The sum along any row of $A$ equals $R$
  • The sum along any column of $A$ equals $C$.
  • $\frac{M}{R}=\frac{N}{C}=K$, and $K$ is an integer.

Is there a name for the matrices that satisfy these properties? What does the set of these matrices look like?

Additional info, although possibly unhelpful:

The matrix is actually a scaled discrete joint-probability distribution for finite RVs $(X,Y)$. I am interested in forming a $K$-partition of the $Y$-dimension of this matrix. Given we know what set of the partition $Y$ is in, we know the range of rows $X$ must be in. I'm trying to find the $K$-partition that minimizes the average amount of rows.

For example, one such matrix is a block-diagonal matrix with $K$ blocks of size $R\times C$, each block full of 1s. We partition the columns so that each set encapsulates the columns associated with a block. Then if we know that $Y$ is in the $i$th set, then $X$ has to be in the rows that the $i$'th block occupies. So then we know $X$ to within $R$ values.

  • $\begingroup$ This is an incidence matrix, however, you still have to specify the conditions that there are $A$ ones in each row and $B$ ones in each column. $\endgroup$ – Element118 Oct 27 '15 at 7:54
  • $\begingroup$ It is also the matrix that describes a bipartite graph where each vertex from one group has $R$ connections, and each vertex from the other has $C$ connections, along with that condition that involves $K$ which specifies the size of the graph. $\endgroup$ – enthdegree Oct 28 '15 at 10:13

This matrix represents a $(R,C)$-regular bipartite graph of dimension $(KR,KC)$, letting each row and column represent a vertex, and letting a '1' denote a connection between the row/column vertex.

It is also one of the set of solutions to a specific Nonogram puzzle.

Thought process continued in: Clustering large biregular graphs


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.