Skip to main content
2 of 4
Including theorem shared by Mark L. Stone

When Is the Log-Permanent Concave?

Let $PSD_n$ be the set of $n\times n$ semidefinite positive matrices. For any $X\in PSD_n$, define $$f(X)=\log(\det(X)).$$ Then $f$ is a concave function over $PSD_n$. This fact has some significance in convex optimization.

Is there an analogous result for the permanent? In particular, if we define $$g(X)=\log(Perm(X)),$$ can we identify some non-trivial set $M$ of matrices over which $g$ is concave (or convex for that matter)?

(I'm hoping for some set larger than "diagonal matrices".)


EDIT: In the comments below, Mark L. Stone included a reference to a very interesting theorem; here's the relevant part.

Let $H_n$ be the set of $n\times n$ Hermitian matrices. For $X,Y\in H_n$, we say that $X\preccurlyeq Y$ iff $Y-X$ is semidefinite positive. Let $S_n$ be the group of permutations on $n$ objects, and $G$ a subgroup of $S_n$.

We define a function $d:H_n \rightarrow R$ for an irreducible character $\chi$ of $G$ by: $$d(X)=\sum_{\sigma\in G} \chi(\sigma) \prod_{i=1}^{n} X_{\sigma(i),i}$$

(Note that the determinant and the permanent are instances of this function, as are, I think, the immanants.)

Theorem: If $X,Y\in H_n$, $0 \preccurlyeq Y \preccurlyeq X$ and $0\leq \lambda \leq 1$, then $d$ is convex, i.e., $$ d(\lambda X + (1-\lambda)Y) \leq \lambda d(A) + (1-\lambda)d(B) $$

In particular, that holds for the permanent. However, this result doesn't quite answer my original question, in that there is no fixed set $M$ that works-- it requires a relationship between $X$ and $Y$. (Is there some way to lift this result with a matrix exponential to get $M=PSD_n$?)