6
$\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
$\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$ – Bill Bradley May 9 '20 at 2:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.