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$ ).

  • $\begingroup$ You might get a better approximation if you knew the number of nonzero entries in each row and column. Do you have any other information on the matrix you are willing to use for such a formula? Gerhard "Ask Me About System Design" Paseman, 2011.09.14 $\endgroup$ – Gerhard Paseman Sep 14 '11 at 15:32
  • 1
    $\begingroup$ Zur wrote that the row and columns sums are all equal to $c$, which is a fairly strong restriction. I'll ask: is $c$ bounded? It can make quite a difference whether the matrix is sparse or dense. Also, are you interested in random matrices? Probably the asymptotic expected value of $per'(M)$ can be computed for bounded or slowly increasing $c$. $\endgroup$ – Brendan McKay Sep 14 '11 at 15:47
  • 2
    $\begingroup$ Interesting problem. A fundamental difficulty will be that, unlike for ordinary Latin squares, you might not be able to complete $n-k$ rows to $n-k+1$ rows at all. This is easiest to see for $k=1$, since some column might have $n-1$ symbols twice each already, leaving only the illegal pair $\{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? $\endgroup$ – Brendan McKay Sep 15 '11 at 10:38
  • $\begingroup$ That is a difficulty. I'm hoping that it will turn out that the maximum k you allude to is small (o(n) would be enough). In that case, perhaps we can use the construction for n-k-1 rows and then say "And now there exists a way to complete the square". I can show that if we are able to complete n-2 rows, then we can always complete the final 2 rows (based on a flow network argument). Therefore I hope that the maximal k is 1, although I haven't been able to prove this yet. $\endgroup$ – Zur Luria Sep 16 '11 at 8:30
  • 1
    $\begingroup$ $M$ describes a $2k$-regular bipartite multigraph $G$ with maximum multiplicity 2, and you want to partition it into $k$ simple 2-factors. This is not always possible for $k=1$, but I understand you as saying you have proved it for $k=2$. For larger $k$ you can find a 4-factor (not necessarily simple) by combining 4 1-factors of a 1-factorization. Then use your lemma to extract a simple 2-factor $F$ from this 4-factor and continue with $G-F$ recursively. So $k=1$ is the only case which might not be factorable. $\endgroup$ – Brendan McKay Sep 16 '11 at 13:09

Your Answer

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

Browse other questions tagged or ask your own question.