7
$\begingroup$

I am wondering if the following generalization of van der Waerden's conjecture is true.

Suppose A is an n x n non-negative matrix with all column sums equal to 1, and the sum of row i equal to $T_i$. Then $per(A) \geq T_1\ldots T_n \frac{n!}{n^n}$. This obviously implies van der Waerden's conjecture. I can check it by hand for 2x2 matrices, and I did not have the patience to try larger examples (so it may be false for some easy example). I couldn't modify Gurvits's proof to work either.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
13
$\begingroup$

The conjecture is false. Here is a counterexample.

\begin{equation*} A = \begin{bmatrix} \tfrac18 & \tfrac4{15} & \tfrac1{10}\\ \tfrac18 & \tfrac4{15} & \tfrac1{10}\\ \tfrac68 & \tfrac7{15} & \tfrac8{10} \end{bmatrix}. \end{equation*}

For this matrix, $\text{per}(A)=\frac{21}{200}=0.105$. The row sums $T_1,\ldots,T_3=\left\{\frac{59}{120},\frac{59}{120},\frac{121}{60}\right\}$, so that $T_1T_2T_3 n!/n^n = \frac{421201}{3888000} \approx 0.108334...$, which is greater than $\frac{21}{200} = 0.105$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Even simpler: the permanent is $76/8^3$ and the proposed lower bound is $(700/9)/8^3$ or $77.7/8^3$ for $$\begin{equation*} A = \begin{bmatrix} 1 & 1 & 3\\ 1 & 1 & 3\\ 6 & 6 & 2\\ \end{bmatrix}/8. \end{equation*}$$ $\endgroup$
    – user44143
    Commented Oct 11, 2019 at 13:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .