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

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 only $11$ distinct functions if $n=3$, among $13$ pairs.

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
up vote 17 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 LAA)

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 '15 at 6:30
1  
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 '15 at 14:00
2  
This is fascinating. I found it interesting that matrices with rank as low as 2 were found as counterexamples. I know that this would not be possible for Lieb's conjecture as I proved Lieb for all $n \times n$ matrices of rank 2 during my PhD research in 1998 (although I never published the work as I left academia after my PhD). – Keith May 9 at 10:21
1  
@Suvrit. Sadly I do not have the TeX file any more. I have a hard copy and it is also available at the library of Imperial College London. The proof generalized a result by Tom Pate (Article: Immanant Inequalities, Induced Characters, and Rank Two Partitions Thomas H. Pate Full-text · Article · Feb 1994 · Journal of the London Mathematical Society). Through the generalization and establishing a link between the rank of a partition in character theory of the Symmetric Group and the rank of a Hermitian Positive Semidefinite matrix, it was possible to show (continued) – Keith May 10 at 10:21
1  
that the Permanent was the maximal Immanant for all Hermitian Positive Semidefinite matrices of rank at most 2. The second part of the thesis focused on Totally Positive Matrices and set out a computational structure (obtained via the Bruhat partial order on the Symmetric Group) to test matrix inequalities on this class of matrices. As a corollary I was able to show that the J-matrices were test matrices for all matrix function inequalities on $n x n$ totally positive matrices for $n \leq 5$. – Keith May 10 at 10:21

Your Answer

 
discard

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.