Let $M$ be a matrix with entries equal to 0, 1 or 2, such that all of the row and column sums are equal to $c$.

The Van der Waerden bound gives (roughly) the following bound on the permanent of $M$: $ per(M) \ge \left( \frac{c}{e} \right)^n $.

I am interested in the number of permutation matrices supported by $M$, rather than the permanent. Call this number $per'(M)$. For 0,1 matrices, the two numbers are equal. How about 0,1,2 matrices? Clearly, in this case $per'(M) \ge 2^{-n} per(M)$.

Is it possible to give a better lower bound on $per'(M)$, in terms of the number of 1 and 2 entries in $M$?

For my purposes, $c$ may be assumed to be $\gamma n$ for some $0 \le \gamma \le 1$.

The motivation for the question is as follows: Define a "double Latin square" to be an n by n matrix where each entry is composed of two different symbols from $\{ 1, ... ,n \}$, and each symbol appears in each row and column exactly twice.

Let $L_n$ denote the number of ordinary Latin squares of order $n$. There is a simple lower bound of $L_n^2$ on the number of double Latin squares. Let $n$ be an even number, and let $A$ and $B$ be any two order $n$ Latin squares. We construct a double Latin square $C$ by identifying pairs of symbols in $A$ and $B$, so that $A$ holds the values $\{1, ... ,n/2 \}$ and $B$ contains $\{n/2+1, ... n\}$, and then placing the revised matrices $A$ and $B$ on top of each other.

I'd like to get a lower bound that beats $L_n^2$.

To this end I have the following construction in mind (following a construction for Latin squares): Choose each row at random from the set of the rows that are legal given the preceding rows.

Suppose that $n-k$ rows have already been chosen. Let $M$ be the n by n matrix defined by letting $M_{i,j}$ equal the number of $i$ symbols yet to be chosen for the $j$'th column. Then the sum of every row and column of $M$ is $2k$, and the next row must be a pair of disjoint permutation matrices supported by $M$. Hopefully, their number is about $per'(M)^2$.

Update: The above construction has a flaw. It isn't immediately clear how to choose a pair of disjoint permutation matrices supported by $M$. Brendan McKay pointed this out and suggested the following improvement: build the double Latin square two rows at a time.

$M$ describes a $2k$ regular bipartite multigraph with maximum multiplicity 2. Choose 4 (not necessarily disjoint) 1-factors of $M$. Their union is a (not necessarily simple) 4-factor of $M$, and as the following lemma says, such a 4-factor is always the union of two simple 2-factors, giving us our 2 rows.

Lemma: A 4-regular bipartite multigraph $G$ with maximum multiplicity 2 is the union of 2 simple 2-factors.

Proof sketch: Let $F$ denote the first 2-factor. First, choose 1 edge for $F$ from each double edge of $G$. Then let $G'$ be the subgraph defined by taking only the edges of $G$ with multiplicity 1. Construct a flow network by connecting one side of $G'$ to a source node $s$, and the other to a sink node $t$. The edge capacities are 1 for edges of $G'$, and for edges from a vertex to $s$ or $t$ the capacity is the number of additional edges that need to be chosen for that vertex so that $F$ is a 2-factor.

Define $N$ to be $2n$ minus the number of double edges in $G$ (That is, the number of edges that need to be added to $F$). A flow of size $N$ in the flow network corresponds to a legal completion of $F$ to a 2-factor. It is easy to show that such a flow exists using the min-cut max-flow theorem (just verify that every cut has capacity $\geq N$ ).

`$\{x,x\}$`

for the last entry in that column. So there is no uniform positive lower bound on the number of extensions. This prompts me to ask: what is the maximum $k$ such that there exists a $n-k$ rectangle that cannot be extended? – Brendan McKay Sep 15 '11 at 10:38