A bound for the permanent of a nonnegative matrix

Question

Suppose $A=(a_{ij})$ is a symmetric (0,1)-matrix with 1's along the diagonal, and let $A_{ij}$ be the matrix obtained by removing the $i$-th row and $j$-th column.

Based on substantial numerical experimentation it seems that the bound $$\operatorname{Perm}(A) \geq 2 \operatorname{Perm}(A_{ij})$$ holds for any $(i,j)$, $i \neq j$. I would be interested in any bound of the form $\operatorname{Perm}(A) \geq c \operatorname{Perm}(A_{ij})$ for a constant $c>0$. (The bound $\operatorname{Perm}(A) \geq \operatorname{Perm}(A_{ij})$ is trivial if $a_{ij}=1$, but not so clear if $a_{ij}=0$.)

My numerical experimentation suggests that this is a specific case of a far more general fact:

Conjecture: If $A$ is any matrix with nonnegative entries, $i \neq j$ and $\operatorname{Perm}(A)>0$, then $$\operatorname{Perm}(A)^2 \geq 4 a_{ii}a_{jj} \operatorname{Perm}(A_{ij})\operatorname{Perm}(A_{ji}). $$

It seems that there are various families of matrices $A$ that achieve equality.

Answer 1

Please check the details.

Below I denote $i=1,j=2$.

Expand ${\rm Perm}\,A$ as a polynomial in $a_{11}$ and $a_{22}$ as $a_{11}a_{22}X+a_{11}Y+a_{22}Z+T$. Then $$({\rm Perm}\,A)^2\geqslant 4a_{11}a_{22}(XT+YZ).$$

I claim that $XT+YZ$ is coefficient-wise not less than ${\rm Perm}\, A_{12} {\rm Perm}\, A_{21}$.

For this sake, consider the weighted complete bipartite graph $K_{nn}$, with parts $M=\{m_1,\ldots,m_n\}$ and $W=\{w_1,\ldots,w_n\}$, and weight of the edge $m_iw_j$ equal to $a_{ij}$. Then the permanent of matrix $A$ is the weighted sum of perfect matchings (as usual, the weight of a set of edges is defined as the product of all weights of edges in this set).

The permanent of $A_{12}$ is the weighted sum of matchings between $M\setminus \{m_1\}$ and $W\setminus \{w_2\}$. Call them blue matchings. Analogously, the permanent of $A_{21}$ is the weighted sum of matchings between $M\setminus \{m_2\}$ and $W\setminus \{w_1\}$. They are called red matchings. Thus, $a_{11} a_{22}{\rm Perm}\, A_{12} {\rm Perm}\, A_{21}$ is a weighted sum of such multisets of edges: ($m_1w_1,m_2w_2$, blue matching, red matching). Call it a special multiset. Any special multiset $S$ of edges is a regular multigraph of degree 2, thus it is partitioned onto cycles. Thus, $S$ is partitioned onto two perfect matchings by $2^p$ ways, where $p$ is the number of long cycles (=cycles containing more than 2 vertices.) Denote by $q$ the number of long cycles not containing the edges $m_1w_1,m_2w_2$. I claim that the coefficient of weight of $S$ in $a_{11}a_{22}(XT+YZ)$ is at least $2^q$ (in $a_{11} a_{22}{\rm Perm}\, A_{12} {\rm Perm}\, A_{21}$ it is exactly $2^q$).

Indeed, partition $S$ onto two matchings. Remove the edges $m_1w_1$ and $m_2w_2$ from these matchings. If they are removed from different matchings, this corresponds to $YZ$. If they are removed from the same matching, it corresponds to $XT$.