5
$\begingroup$

How many matrices satisfy the following constraints?

  1. $n$ rows
  2. $n$ columns
  3. Cell values are either $0$ or $1$
  4. Sum of any row is at most $m$
  5. sum of any column is at most $m$

Is there a formula or an efficient algorithm to solve this problem?

$\endgroup$
3
  • $\begingroup$ I can solve the cases $m=0$ and $m=1$. $\endgroup$ Nov 21 '16 at 7:45
  • 1
    $\begingroup$ This is the same as the number of digraphs where the in-degree and out-degree are bounded by $m$. $\endgroup$ Nov 21 '16 at 7:46
  • 1
    $\begingroup$ This has some connection to Latin Squares. In particular, we can take an $n\times n$ Latin Square, set the numbers from 1 to $m$ to be 1, and the numbers from $m+1$ to $n$ to be 0. Good news is that this gives a lower bound on your problem. Two problems: 1. the number of Latin squares of size $n$ is an open problem (known bounds are thought to be fairly weak), and 2. it's not clear to me how tight this bound is. In particular, while every Latin square is a solution to your problem, I'm not sure when a solution to this problem can be turned into a Latin Square. $\endgroup$
    – SamM
    Nov 21 '16 at 10:12
4
$\begingroup$

Given $1 \leq m \leq n$, we want to determine the cardinality of the following set

$$\{ \mathrm X \in \{0,1\}^{n \times n} \mid \mathrm X 1_n \leq m 1_n \,\land\, \mathrm 1_n^{\top} \mathrm X \leq m \mathrm 1_n^{\top} \}$$

Vectorizing, $\tilde{\mathrm x} := \mbox{vec} (\mathrm X)$, we obtain

$$\bigg\{ \tilde{\mathrm x} \in \{0,1\}^{n^2} : \begin{bmatrix} 1_n^{\top} \otimes \mathrm I_n\\ \mathrm I_n \otimes \mathrm 1_n^{\top}\end{bmatrix} \tilde{\mathrm x} \leq m \begin{bmatrix} \mathrm 1_n\\ \mathrm 1_n\end{bmatrix} \bigg\}$$

or,

$$\bigg\{ \tilde{\mathrm x} \in [0,1]^{n^2} : \begin{bmatrix} 1_n^{\top} \otimes \mathrm I_n\\ \mathrm I_n \otimes \mathrm 1_n^{\top}\end{bmatrix} \tilde{\mathrm x} \leq m \begin{bmatrix} \mathrm 1_n\\ \mathrm 1_n\end{bmatrix} \bigg\} \cap \mathbb Z^{n^2}$$

Thus, we want to count the number of integer points inside a convex polytope, or, in other words, to count the number of solutions a given integer program (IP) has. Take a look at De Loera's survey [0] and the references therein.


[0] Jesús De Loera, The Many Aspects of Counting Lattice Points in Polytopes, 2005.

$\endgroup$

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.