An inequality between permanents of non-negative matrices 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?
 A: 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.
