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.



A bound for the permanent of a nonnegative matrix
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$.


