Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let me recall a result due to I. Schur, which I learnt from F. Goldberg's answer to my MO question Hadamard-like inequalites for positive definite symmetric matrices. If $H$ is a subgroup of $\frak S_n$ and $\chi$ is an irreducible complex character over $H$, define $$d_\chi(S)=\frac1{\chi(e)}\sum_{g\in H}\chi(g)\prod_{i=1}^ns_{ig(i)}.$$ Then for every $S\in SPD_n$, we have $$\det(S)\le d_\chi(S).$$ Notice that if $H=\frak S_n$ and $\chi$ is the signature, then $d_\chi$ is the determinant. Thus $\det$ is the smallest element among the $d_\chi$'s. If instead $\chi={\bf1}$, then $d_\chi$ is the permanent. If $H=(e)$, Schur's inequality is just the Hadamard inequality $$\det S\le\prod_is_{ii}.$$

Given $n$, there are many distinct $d_\chi$'s, even though several choices of the pair $(H,\chi)$ yield the same function. For instance, there are $11$ distinct functions if $n=3$.

My question is whether the permanent is the largest element among the $d_\chi$'s. In other words, is it true that for every $S\in SPD_n$, we have $$d_\chi(S)\le{\rm per}(S)\quad ?$$

I checked the truth of this assertion if $n=2$, $n=3$, and also in quite a complicated case of $n=4$, where $H={\frak A}_4$ and $\chi\ne{\bf1}$ is a linear character.

share|cite|improve this question

1 Answer 1

up vote 13 down vote accepted

This question is better known as the permanental dominance conjecture and is still an open problem.

According to Zhan's survey, it has been confirmed for every irreducible character of $S_n$ for $n \le 13$. Another reference cited for this conjecture is this survey on open problems about permanents by Cheon and Wanless.

EDIT (added 12/10/2015): Incidentally, the closely related Soules's conjecture whose proof would yield the above permanental dominance (and which states that the largest eigenvalues of the Schur-product matrix of a given Hermitian semidefinite matrix $A$ equals the permanent of $A$), has been very recently shown to be false: check out this explicit counterexample!. (If the first link does not work, try this link on Dropbox)

share|cite|improve this answer
Many thanks for the additional references ! But the second one (the counterexample) is on a restricted site. Do you have a copy of it ? – Denis Serre Oct 13 at 6:30
I added the links; the countex is very simple: use $v=(4-2i,2+3i,-4+4i,-3-4i,1)$ and $w=(2+4i,3i,2+4i,3i,-5+7i)$. Then set $A=vv^*+ww^*$. With this choice $\lambda_{\max}(\Pi(A))-\text{per}(A) \approx 1.37\times 10^7$, here $\Pi(A)$ denotes the Schur-product matrix. – Suvrit Oct 13 at 12:59
Many thanks for the reference ! – Denis Serre Oct 13 at 13:23
Just to make sure : the counterexample invalidates the Permanent on top (POT) conjecture by Soules, but it leaves open the permanent dominance conjecture. By the way, what is quantitatively important in the counterexample is the relative excess $(\lambda_\max-{\rm per})/{\rm per}$, which is about $2$ percent here. – Denis Serre Oct 13 at 13:36
Yes, precisely. The POT (which I refer to as "Soules' conjecture" above) is falsified, but the permanental dominance asked in your question is still open (and I would be surprised if it were false!). The key insight (embarrassingly simple in hindsight) of the linked counterexample was to use complex matrices. I wrote a Matlab script to generate counterexamples, and it yields several more rank-2 $5\times5$ matrices as counterexamples. Though the relative errors I observed are typically around 1 to 1.5 percent.. – Suvrit Oct 13 at 14:00

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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