patternMinor
Number of $n \times n$ binary matrices whose rows and columns sum to at most $m$
Viewed 0 times
rowssumnumberwhosecolumnsbinarymatricesandtimesmost
Problem
How many matrices satisfy the following constraints?
Is there a formula or an efficient algorithm to solve this problem?
- $n$ rows
- $n$ columns
- Cell values are either $0$ or $1$
- Sum of any row is at most $m$
- sum of any column is at most $m$
Is there a formula or an efficient algorithm to solve this problem?
Solution
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.
$$\{ \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.
Context
StackExchange Computer Science Q#66265, answer score: 4
Revisions (0)
No revisions yet.