Permanent of a Square of a Doubly Stochastic Matrix – Analysis

co.combinatoricspermanentpr.probabilitystochastic-matrices

Let $A = (a_{i,j})$ be a double stochastic matrix with positive entries. That is, all entries are positive real numbers, and each row and column sums to one. A permanent of a matrix $A = (a_{i,j})$ is defined as
$$
\text{perm}(A) = \sum_{\pi \in S_n}\prod_{i=1}^{n}a_{i,\pi(i)}.
$$

Is it true that $\text{perm}(A^2) \leq \text{perm}(A)$ with the equality achieved only by $P_n = (1/n)$?

More generally, is it true that $\text{per}(A^n) \leq \text{per}(A^m)$ for $n > m$ with the equality achieved only by $P_n = (1/n)$?

Van der Waerden's conjecture states that the minimum permanent among doubly stochastic matrices is achieved precisely by the matrix $P_n = (1/n)$. Since $P_n$ is the only doubly stochastic matrix with positive entries and $P_n^2 = P_n$, the conjecture above implies Van der Waerden's conjecture for matrices with positive entries, so I don't assume it's easy to prove it if it's true.

I wrote a simple code (well, I mostly got it from here) in Wolfram Mathematica to test the conjecture on random doubly stochastic matrices but couldn't find any counterexamples.

n := 5
While[Min[
   dsm := FixedPoint[
     Standardize[Transpose[Standardize[#, 0 &, Total]], 0 &, Total] &,
      RandomReal[1, {n, n}], 
     SameTest -> (Norm[#1 - Transpose[#2], "Frobenius"] < 
         1.*^-12 &)]] < 0.1]

Do[
 mat = dsm;
 If[Permanent[mat] < Permanent[mat.mat],
  Print[mat]];
 , {i, 1, 10000}]

The intuition behind the conjecture is from the two-sided Markov chains. Since $A$ is doubly stochastic, one can run two Markov chains on both sides. The permanent can be interpreted as some statistics on collisions between particles that start at certain positions. Since the Markov chain, after many steps, "wash out" original biases, the number of collisions should get smaller and achieve the minimum on the limit, which is $P_n = (1/n)$ for a doubly stochastic matrix.

Update: Relevant partial result: Sinkhorn, Richard. "Doubly stochastic matrices whose squares decrease the permanent." Linear and Multilinear Algebra 4, no. 2 (1976): 153-158.

Update: Joseph Van Name showed in the answer that the conjecture is wrong: the following doubly stochastic matrix is a counterexample.

\begin{pmatrix}
15/32 & 1/64 & 1/2 & 1/64 \\
1/64 & 1/64 & 15/32 & 1/2 \\
1/2 & 15/32 & 1/64 & 1/64 \\
1/64 & 1/2 & 1/64 & 15/32
\end{pmatrix}

Best Answer

No. This is not true.

For example, set

$$A=\frac{1}{2}\begin{bmatrix} 1&0&1&0\\ 0&0&1&1\\ 1&1&0&0\\ 0&1&0&1 \end{bmatrix}.$$

Then $\text{Per}(A)=1/8$ and $\text{Per}(A^2)=9/64.$

Since the collection of all matrices $B$ where $\text{per}(B^2)>\text{per}(B)$ is open, there is some $\epsilon$ where if $\|B-A\|<\epsilon$, then $\text{per}(B^2)>\text{per}(B)$. In this case, one can select a doubly stochastic $B$ with strictly positive entries with $\|B-A\|<\epsilon$ and therefore $\text{per}(B^2)>\text{per}(B)$.

It looks like the class of arithmetic means of two permutation matrices is the best source of examples of doubly stochastic matrices $A$ with $\text{Per}(A^2)>\text{Per}(A).$

More generally, if $P$ is a permutation matrix, and $A=\frac{P+P^{*}}{2}$, then in the computer experiments that I have ran, we usually have $\text{Per}(A^2)>\text{Per}(A).$

Testing a conjecture on convex sets

We observe that the permutation matrices are the extreme points among all doubly stochastic matrices. Recall that the Krein-Milman theorem states that every compact convex subset of a Hausdorff locally convex topological vector space is in the convex closure of its extreme points. Furthermore, recall that Caratheodory's theorem states that if $C\subseteq\mathbb{R}^{n}$ is the convex closure of a set $A$, then every point in $C$ is a convex combination of at most $n+1$ many points of $A$. By combining these two theorems together, we conclude that for every compact convex subset $C$ of $\mathbb{R}^n$, every element in $C$ is in the convex closure of at most $n+1$ many extreme points in $C$.

In general, if $U$ is a totally bounded convex subset of a real affine space $V$ with $\dim(V)=n$, and one is trying to find an element in $U$ that satisfies a property using a computer search, one should test elements near the extreme points of $\overline{U}$. If this does not work, then whenever $1\leq d\leq n+1$, one should test points near convex combinations of $d+1$ many extreme points.

For this kind of problem, it also appears that it is a good idea to run all these tests to see if there is a symmetric counterexample. If this still did not work, then I would use a gradient descent to minimize $\text{per}(B)-\text{per}(B^2).$

Related Question