Maximum permanent on a unitary orbit

← Minc’s list

Minc’s list · Problem 1

Maximum permanent on a unitary orbit

Open

Posed by
Marcus and Minc
First posed
1965

Statement

Posed by M. Marcus and H. Minc in their 1965 survey of permanents; it is Problem 1 in Minc’s catalogue.

Problem 1. Find the maximum value of \(\operatorname{per}(U^*AU)\) if \(A\) is a fixed \(n\times n\) positive semidefinite Hermitian matrix, \(n\ge3\), and \(U\) runs over all \(n\times n\) unitary matrices.

The matrices \(U^*AU\) are exactly the Hermitian matrices with the same eigenvalues \(\lambda_1,\dots,\lambda_n\ge0\) as \(A\), so the maximum depends only on the spectrum. The problem asks for the value; describing the maximizing matrices is a separate question.

Prior progress

  • Marcus and Minc (1964) proved the upper bound \(\operatorname{per}(U^*AU)\le\frac1n\sum_i\lambda_i^n\).
  • Grone, Johnson, de Sá and Wolkowicz (1986) showed that a maximizer \(B\) must commute with its permanental adjoint, the matrix with entries \(\operatorname{per}B(j\mid i)\), and solved the case \(n=2\).
  • Drew and Johnson (1989) solved the case \(n=3\) for real symmetric matrices, with a maximizer that can be chosen symmetric about both diagonals. In a companion note they disproved Mehta’s conjecture that the maximum always occurs at constant diagonal. Hu (1994, 1996) completed the complex Hermitian case \(n=3\) for every spectrum.

Our progress so far

  • Maximizers are degenerate, in every order. If the eigenvalues are distinct and \(B=V\operatorname{diag}(\lambda)V^*\) is a maximizer, or even a local maximum, then the doubly stochastic matrix \(\bigl(\lvert V_{i\alpha}\rvert^2\bigr)\) is singular.
  • The classical bound is never attained. For \(n\ge3\) and positive distinct eigenvalues, \(\operatorname{per}(U^*AU)<\frac1n\sum_i\lambda_i^n\) for every \(U\). The maximum is at least \(h_n(\lambda)/\binom{2n-1}{n}\), where \(h_n\) is the complete homogeneous symmetric polynomial.
  • Order four. Every maximizer satisfies the algebraic equation \(\det\bigl[(B^k)_{ii}\bigr]_{1\le i\le4,\ 0\le k\le3}=0\). We proved the explicit lower bound \[ \max_U\operatorname{per}(U^*AU)\ \ge\ \frac{3\sum_i\lambda_i^4+2\sum_{i<j}\lambda_i^2\lambda_j^2+8\lambda_1\lambda_2\lambda_3\lambda_4}{32}, \] which is not always the maximum. We also classified several families of critical points as local maxima or saddles. The value for \(n=4\) remains open.

References

  1. M. Marcus and H. Minc, Inequalities for general matrix functions, Bull. Amer. Math. Soc. 70 (1964), 308–313. doi:10.1090/S0002-9904-1964-11136-8
  2. M. Marcus and H. Minc, Permanents, Amer. Math. Monthly 72 (1965), 577–591. doi:10.1080/00029890.1965.11970575
  3. R. Grone, C. R. Johnson, E. M. de Sá and H. Wolkowicz, A note on maximizing the permanent of a positive definite Hermitian matrix, given the eigenvalues, Linear and Multilinear Algebra 19 (1986), 389–393. doi:10.1080/03081088608817733
  4. J. H. Drew and C. R. Johnson, The maximum permanent of a 3-by-3 positive semidefinite matrix, given the eigenvalues, Linear and Multilinear Algebra 25 (1989), 243–251. doi:10.1080/03081088908817947
  5. J. H. Drew and C. R. Johnson, Counterexample to a conjecture of Mehta regarding permanental maximization, Linear and Multilinear Algebra 25 (1989), 253–254. doi:10.1080/03081088908817948
  6. S.-A. Hu, Maximum permanent and Hermitian matrices, Linear Algebra Appl. 235 (1996), 93–105. doi:10.1016/0024-3795(94)00121-9