Chess Picking Problem

Rephrase the chess picking problem in a more formal way.

Problem Statement

Let $M$ be the set of $2n\times 2n$ 0-1 matrices such that

• All matrices have the same number of $1$'s
• Any $n\times n$ submatrix has at least one $1$
• The number of 1's, $k$, is the minimal possible value

Calculate $k$ and $\|M\|$.

Solution

Minimal Number of 1's

Let $A = S_{2n}\times S_{2n}$ act on $M$ by reordering the rows and columns. Clearly, this group action is well-defined. Now consider $\|M/A\|$, the number of different orbits. We can use one $S_{2n}$ to make the diagonal all $1$'s, and still have the ability to reorder the column.

Define a graph $G = (N, M)$, where $N = \\{1,\ldots,n\\}$ and there is an edge from $x$ to $y$ iff $(x,y)$ is $1$ in $M$. We may assume there is a self loop on each node. Removing those $2n$ self loops, we will get a simple graph with $k-2n$ edges. Let the second $S_{2n}$ act as relabeling the nodes, so it suffices to consider unlabeled graphs. Now, the submatrix condition becomes that:

• For any set of $n$ nodes, there exists an edge pointing out.

And $\|M/A\|$ is equal to the number of such simple graphs, up to isomorphism.

Clearly, $n$ edges does not work. But there is a solution with $n+1$ edges: a $n+1$ cycle plus $n-1$ isolated nodes. Thus, $k = 3n+1$.

Number of Orbits

We can prove this is the only graph.

• If there is a cycle of length $c< n+1$, then the rest $2n-c$ elements will have only $n-c+1$ edges. Thus, there exists at least $n-1$ nodes that does not have an outgoing edge. Pick the $c$ nodes from the cycle and $n-c$ nodes with 0 outgoing degree, and we get a cut.
• If there is no cycle at all, e.g. forest, then we can simply sort nodes in the topological order and take the last $n$ ones.

Thus, $\|M/A\| = 1$. A (somehow) surprising result.

Number of Matrices

Since there is only one orbit, $\|M\| = [A: \mathrm{stab}_{A}(x)]$, where $x$ is a solution.

Without loss of generality, let $x$ contain the cycle $1\to 2\to\cdots\to (n+1)$ plus isolated points $(n+2,n+2),\ldots,(2n,2n)$. Consider $|\mathrm{stab}_{A}(x)|$:

• We can reorder the $n+2,\ldots,2n$ rows in any permutation, as long as we do the same to those columns: $(n-1)!$
• For the cycle part, the stablizer set size is equal to automorphisms of an unlabeled cycle: $2(n+1)$
  • It's hard to describe why verbally. But you can have a try: pick any row in the cycle to be the first row, and you'll find there are exactly 2 ways to do the rest.

Thus, the total number is $\|M\| = \frac{(2n)!^2}{2(n-1)!(n+1)}$.

We can also directly count this:

• For the $n-1$ isolated nodes, we can insert them into any columns & rows: ${2n \choose n-1}^2$
  • And then, we can choose the position to place 1 at each row: $(n-1)!$
• For the $n+1$ cycle, we can shuffle the rows as a free circular permutation: $\frac{1}{2}n!$
  • And then each row is different so we can shuffle them: $(n+1)!$

Thus, the total number is $\|M\| = \frac{1}{2}(n-1)!n!(n+1)!{2n \choose n-1}^2$.

PS: Complexity

If the answer is $\|M\|$ modulo $p$, then we have a faster algorithm $O(\sqrt{n}\log n)$ via multipoint evaluation. See the next post.

Reference

• Polynomial Algorithms
• Factorial mod Prime in Rust
• 階乗 mod 素数 - memo. Link is broken. Please use Wayback machine.