6
$\begingroup$

I am looking for some result useful in deriving following (conjecture?):

Let $A$ be an $n\times n$ matrix with $0-1$ entries. Suppose, that exactly $k\leqslant n$ entries are equal to $0$. Then $\mathrm{Per} A \leqslant n!\left(1-\frac{k}{2n}\right)$

Unfortunately, trying to derive this inequality from other estimates fails in general. For example, the inequality given in

Adam G. Weyhaupt, A note on some upper bounds for permanents of (0,1)-matrices, Journal of Interdisciplinary Mathematics 12 no 1 (2009) pp 123–128, doi:10.1080/09720502.2009.10700615 (pdf)

failed with $k=4$.

Improve this question
$\endgroup$
3
  • $\begingroup$ I should have naively guessed the upper bound $n!(1-k/n)$. Can you explain why the factor $1-\frac{k}{2n}$ is relevant? $\endgroup$
    – Denis Serre
    Commented May 7, 2011 at 20:35
  • $\begingroup$ The identity matrix $2\times 2$ with $k=2$ gives the equality $\mathrm{Per} I = 1 = 2!\left(1-\frac{2}{2\cdot 2}\right)$. $\endgroup$
    – Maciej Skorski
    Commented May 7, 2011 at 21:11
  • $\begingroup$ of course! I went to fast. $\endgroup$
    – Denis Serre
    Commented May 8, 2011 at 6:49

2 Answers 2

Reset to default
13
$\begingroup$

In fact, the maximum is achieved when no two of the 0's are in the same row or column, giving the maximum value $$ S=\sum_{i=0}^k (-1)^i {k\choose i}(n-i)!. $$ Proof. Suppose that there are two 0's in the same row, say the first. Then some row, say the second, has all 1's. Expand the permanent by the first two rows. One of the $2\times 2$ submatrices is $\pmatrix{0&0\cr1&1\cr}$. Changing this to $\pmatrix{1&0\cr0&1\cr}$ does not decrease any of the $2\times 2$ submatrices from the first two rows, so the permanent of the entire matrix does not decrease. We can iterate this procedure (possibly using columns instead of rows) until no two 0's are in the same row and column, so the proof follows.

We now need to show that $S$ is at most $n!\left( 1 -\frac{k}{2n}\right)$. This is trivial for $k=1$, so assume $k>1$. By the Bonferroni inequalities (http://en.wikipedia.org/wiki/Boole's_inequality), $S$ is bounded by the first three terms, i.e., $$ S\leq n!-k(n-1)!+{k\choose 2}(n-2)! = n!\left(1-\frac kn+\frac{{k\choose 2}}{n(n-1)}\right). $$ Since $k\leq n$ we have $$ \frac{{k\choose 2}}{n(n-1)}\leq \frac{k}{2n}, $$ and the result follows.

Improve this answer
$\endgroup$
1
  • $\begingroup$ \pmatrix{0&0\cr1&1\cr} gives $\pmatrix{0&0\cr1&1\cr}$ when you put a dollar sign at each end of it. $\endgroup$
    – Gerry Myerson
    Commented May 8, 2011 at 0:29
1
$\begingroup$

Thanks for help. By the way, I have checked, that solutions of more general extremal problems, using exactly the same ideas (changing a row or column that contains more than one zero) one can found in the paper Maximum permanents of matrices of zeros and ones

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.