Analogue of PSD matrices for permanents?

Question

Let's begin with a few observations. Suppose we consider the set of $N\times N$ matrices and consider the matrices with positive determinant. There are several connected components in this set; let $S$ be the component that contains the identity matrix. Observe that $S$ corresponds to the set of positive definite matrices. This fact (and the convexity of $S$) is important for interior-point techniques in semi-definite programming.

Suppose we replace "determinant" with "permanent". What happens? In other words, suppose we consider matrices with positive permanent. Let $C$ be the connected component that contains the identity matrix. The closure $\overline{C}$ is a pointed cone.

1. Is $C$ convex?
2. Does $C$ or $\overline{C}$ have a name, or can anyone point me to literature discussing its properties?

Answer 1

The set $C$ is not convex, nor is its intersection with the symmetric matrices. To see this note that by linearly interpolating between each of the matrices below we maintain positive permanent and symmetry: \[ I = \begin{bmatrix} 1 & 0 & 0 \\\ 0 & 1 & 0 \\\ 0 & 0 & 1\end{bmatrix} \rightarrow \begin{bmatrix} 1 & 0 & 0 \\\ 0 & 1 & 1 \\\ 0 & 1 & 1\end{bmatrix} \rightarrow \begin{bmatrix} 1 & 0 & 0 \\\ 0 & -1 & 1 \\\ 0 & 1 & -1\end{bmatrix} \rightarrow \begin{bmatrix} 1 & 0 & 0 \\\ 0 & -1 & 0 \\\ 0 & 0 & -1\end{bmatrix}. \]

Therefore the matrix on the right is in $C$. Similar reasoning shows that all of \[ \begin{bmatrix} 1 & 0 & 0 \\\ 0 & -1 & 0 \\\ 0 & 0 & -1\end{bmatrix}, \begin{bmatrix} -1 & 0 & 0 \\\ 0 & 1 & 0 \\\ 0 & 0 & -1\end{bmatrix}, \begin{bmatrix} -1 & 0 & 0 \\\ 0 & -1 & 0 \\\ 0 & 0 & 1\end{bmatrix} \] are in $C$. But their average \[ \begin{bmatrix} -1/3 & 0 & 0 \\\ 0 & -1/3 & 0 \\\ 0 & 0 & -1/3\end{bmatrix} \] has negative permanent.

---

Edit: Another way to see this is to note that the permanent of an upper or lower triangular matrix is the product of the diagonal entries. Therefore all matrices on the line segment between the identity and any other triangular matrix with positive diagonal have positive permanent. Thus the convex hull of $C$ contains all matrices with positive diagonal. Some such matrices have negative permanent, so $C$ is not convex. The same argument applies with determinant in place of permanent when we don't restrict to symmetric matrices.

Answer 2

The set of $n \times n$ matrices with positive permanent is connected. Given such a matrix $A$, consider the expansion of $P(A)$ in minors along the first row: say $P(A) = \sum_{j=1}^n a_{1j} P(A_{1j})$. We can choose one $j$ for which $a_{1j} P(A_{1j}) > 0$, first reduce gradually to 0 all $a_{1k}$ for which $a_{ik} P(A_{1k}) < 0$, then reduce gradually to $0$ all other $a_{1k}$ for $k \ne j$, ending with a matrix with only one nonzero element in the first row. Continuing in this way for each of the other rows, we obtain a matrix whose only nonzero elements are $a_{i,\sigma(i)}$ for a permutation $\sigma$ of $\{1,\ldots,n\}$. Note that the number of negative elements $a_{i,\sigma(i)}$ will be negative. Now for any $i \ne j$ where $a_{i,\sigma(i)} a_{j,\sigma(j)} > 0$, by changing only the elements $a_{i,\sigma(i)}$, $a_{i,\sigma(j)}$, $a_{j,\sigma(i)}$ and $a_{j,\sigma(j)}$ (taking these four elements to be $ \pmatrix{(1-t) a_{i,\sigma(i)} & t\cr t & (1-t) a_{j,\sigma(j)}\cr}$ for $0 \le t \le 1$) we can multiply the permutation by the transposition $(i,j)$, and incidentally make the elements $a_{i,\sigma(j)} = a_{j,\sigma(i)}=1$. Using an appropriate sequence of transpositions, we eventually get the identity matrix.