I came across the following while doing some related proof; It seems easy to prove. $\quad$
We are in ${\mathbb{M}}_n(\mathbb{C})$, $n>1$:

$1$) Given a unitary $n\times n$ matrix $U$, there is some permutation of the columns such that the modulus of each entry on the diagonal of the resulting matrix is $\le \dfrac{\sqrt{2}}{2}$, $\quad$

And more difficult:

$2$) There are no $n\times n$ unitary matrices $U$ of diagonal $D$ with all entries satisfying $|d_{i,i}|>\dfrac{1}{\sqrt{n-1}}$ for all $i$, unless $U$ is a direct sum of unitaries $U_k$, (up to a permutation congruence) $U_k\in {\mathbb{M}}_k$, $k<n$. I am searching for a proof or related facts.

Edit: for $2$ and $n=4$, we can take $\begin{pmatrix}a&b&c&d\\-b&a&-d&c\\-c&d&a&-b\\-d&-c&b&a\end{pmatrix}$. The only thing is that it may(not) hold for $n=3$.

  • 1
    $\begingroup$ How does 1 fit with the identity matrix being unitary? $\endgroup$
    – kneidell
    Nov 17, 2019 at 11:54
  • 1
    $\begingroup$ Actually, same goes for 2, unless I'm completely misunderstanding your question... $\endgroup$
    – kneidell
    Nov 17, 2019 at 11:56
  • 2
    $\begingroup$ There no problem for (1) with identity matrix. But I don't see how to interpret (2) "up to permutation". Please clarify. $\endgroup$
    – YCor
    Nov 17, 2019 at 12:28
  • 3
    $\begingroup$ (2) is false even with the correction. Just perturb the identity matrix slightly. $\endgroup$ Nov 17, 2019 at 14:38
  • 1
    $\begingroup$ Consider $\begin{pmatrix}\frac{\cos(\theta)}{\sqrt{2}}&\frac{\sin(\theta)}{\sqrt{2}}&-\frac{\sqrt{2}}{2}\\ \sin(\theta)&\cos(\theta)&0\\ \frac{\cos(\theta)}{\sqrt{2}}&\frac{\sin(\theta)}{\sqrt{2}}&\frac{\sqrt{2}}{2}\end{pmatrix}$ for small $\theta > 0$... $\endgroup$ Nov 17, 2019 at 21:23

1 Answer 1


Consider a unitary matrix $U = (u_{i,j})$. We will show that there is some permutation $\pi:[n] \to [n]$ such that $|u_{i,\pi(i)}| \leq \sqrt{2}/\sqrt{n+1}$ for all $i$, which is sufficient to prove the first stated conjecture when $n \geq 3$, and when $n=2$ we can use the expression of $U$ as: $$\left(\begin{array}{cc} \sin(\theta) & \cos(\theta)\\ \cos(\theta) & -\sin(\theta) \end{array}\right)$$ to obtain the desired bound, since $\min(\sin(\theta),\cos(\theta)) \leq \sqrt{2}/2$ for any $\theta$. Note that the process of permuting columns doesn't preserve the trace of the matrix, but it does preserve the property of being unitary!

Given $\pi$, consider the associated quantity $I(\pi) = \sum_{i=1}^n |u_{i,\pi(i)}|^2$. Since there are only finitely many permutations, there is some permutation $\pi_*$ minimizing this value. In particular, letting $v_{i,j} = u_{i,\pi_*(j)}$, the resulting matrix $V= (v_{i,j})$ after applying the permutation of the columns must satisfy $$|v_{i,j}|^2 + |v_{j,i}|^2 \geq |v_{i,i}|^2 + |v_{j,j}|^2$$ for all indices $i,j$, since otherwise we could exchange rows $i$ and $j$ and obtain a smaller value of $I(\pi)$.

Consider summing the above inequality over $j$. On the left hand side we get the squared norm of a row and a column of $V$, which both must be $1$. Thus we get: $$2 \geq n|v_{i,i}|^2 + I(\pi_*).$$ Since $I(\pi_*) \geq |v_{i,i}|^2$, this gives the claimed bound.

Summing the latter inequality over $i$, we moreover deduce that: $$2n \geq 2nI(\pi_*),$$ whence we conclude that $I(\pi_*) \leq 1$. Thus in particular, we cannot have $|v_{i,i}| > 1/\sqrt{n}$ for every $i$, which resolves one possible interpretation of the second part of the OP's question.

It is worth noting that it might be possible to strengthen these bounds for large enough $n$ by considering a more interesting permutation than a transposition in the original inequality, but it is tight for $n=2$ by the above and for $n=3$ since there is no way to avoid having a $\sqrt{2}/2$ on the diagonal of a matrix whose columns are a permutation of: $$\left(\begin{array}{ccc} 0 & \sqrt{2}/2 & \sqrt{2}/2\\ 0 & \sqrt{2}/2 & -\sqrt{2}/2\\ 1 & 0 & 0 \end{array}\right)$$

  • $\begingroup$ I like this answer a lot. However, your conclusion $n |v_{i,i}|^2\le1$ would only be justified if you had $I(\pi_*)\ge1$, whereas you actually have $I(\pi_*)\le1$. Anyhow, you have proved a slightly weaker conclusion, $n |v_{i,i}|^2\le2$, which will imply the OP's conjecture 1) for $n\ge4$; the cases $n=2,3$ should be easy. Also, your proof applies to the more general setting with a general doubly stochastic matrix $(p_{ij})$ in place of the unistochastic matrix $(|u_{ij}|^2)$; see en.wikipedia.org/wiki/Unistochastic_matrix . $\endgroup$ Nov 17, 2019 at 17:16
  • $\begingroup$ Oops yep, good point. I'll edit appropriately. $\endgroup$ Nov 17, 2019 at 17:18
  • 1
    $\begingroup$ The feel of this proof reminded me of the Gershgorin Theorems bounding the spectrum of a matrix in terms of sums of column entries compared with diagonal entries. It's not directly relevant, but may be of interest. $\endgroup$ Nov 17, 2019 at 18:05
  • $\begingroup$ Concerning conjecture 2), Sam Zbarsky's comment shows it is false. $\endgroup$ Nov 17, 2019 at 19:06
  • $\begingroup$ @‍SamZbarsky's comment referenced by @IosifPinelis. $\endgroup$
    – LSpice
    Nov 18, 2019 at 16:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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