Let $A$ be a non-negative (all entries $\geq 0$) square matrix. Is it always true that


$$
 (a\_{11}+a\_{12}+a\_{21}+a\_{22})^2\geq 4a\_0a\_2
$$


where


$a\_{ij}$ is the permanent of a matrix obtained by deleting $i$-th row and $j$-th column from $A$.


$a\_0=\rm{perm}(A)$


$a\_2$ is the permanent of $A$ without the first two rows and columns?



An inequality between permanents of non-negative matrices
Notice that
$$
 (a\_{11}+a\_{22}+a\_{12}+a\_{21})^2\geq (a\_{11}+a\_{22})^2+(a\_{12}+a\_{21})^2\geq 4a\_{11}a\_{22}+4a\_{12}a\_{21}.
$$
Thus, it suffices to show
$$
 a\_{11}a\_{22}+a\_{12}a\_{21}\geq a\_0a\_2.
$$
Expand each permanent and perform multiplication to obtain the sums of products of $2n-2$ entries on both sides.. We will provide an injection from summands on the right to those on the left; this clearly yields the required inequality.


Visualize the $(i,j)$th entry of $A$ as an edge $(r\_i,c\_j)$ of a bipartite graph with parts $R=\{r\_1,\dots,r\_n\}$, $C=\{c\_1,\dots,c\_n\}$. Each summand on the right corresponds to a graph where the degrees of $r\_1,r\_2,c\_1,c\_2$ are $1$, the other degrees are $2$. Its edges are colored in red (corresponding to factors from $a\_0$) and blue (from $a\_2$). 


This graph contains several cycles and two paths, which are either $r\_1\to c\_1$ and $r\_2\to c\_2$, or $r\_1\to c\_2$ and $r\_2\to c\_1$ (the starting and ending edges of each path are red, so it has an odd number of edges). Repainting the path from $r\_1$, we obtain a graph correspoding to a summand from one of the products on the left hand part (in $a\_{1i}a\_{2j}$, we assume that blue edges correspond to the factors from $a\_{2j}$). This is clearly an injection, since the inverse map is provided by the same repainting. So we are done.


