# A bound for the permanent of a nonnegative matrix

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.

• If $\rm{Perm} \, A=0$, the conjecture holds by rather simple reasons. Jun 13, 2022 at 7:09
• Isn't this a duplicate of mathoverflow.net/questions/278492 ? Jan 9 at 9:49

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$$.

• @MaxAlekseyev hm, $(a+b+c+d)^2\geqslant (a+b)^2+(c+d)^2\geqslant 4(ab+cd)$, is not it? Jun 21, 2022 at 11:31