7
$\begingroup$

Let $\operatorname{PSD}_n$ be the cone of $n\times n$ semidefinite positive matrices. For any $X\in \operatorname{PSD}_n$, define $$f(X)=\log(\det(X)).$$ Then $f$ is a concave function on $\operatorname{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(\operatorname{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(X) + (1-\lambda)d(Y) $$

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=\operatorname{PSD}_n$?)

$\endgroup$
2

1 Answer 1

2
$\begingroup$

Just a suggestion, not a complete answer.

Consider the set of matrices with positive elements. The permanent (or whenever the "character" of the immanent) is a posynomial (polynomial with positive coefficients). Making a change of variables for each element as $x=e^y$ and taking log of the permanent, one gets it in the form of a log-sum-exp function. This function is convex in $y$.

Hope this helps.

$\endgroup$
1
  • $\begingroup$ Oh, good point! It's interesting that the analogous result for the determinant is false. $\endgroup$ Commented May 9, 2020 at 2:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .