# Unitary condition

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. I am searching for a proof or related facts.
Thanks.

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$$.

• How does 1 fit with the identity matrix being unitary? Nov 17, 2019 at 11:54
• Actually, same goes for 2, unless I'm completely misunderstanding your question... Nov 17, 2019 at 11:56
• There no problem for (1) with identity matrix. But I don't see how to interpret (2) "up to permutation". Please clarify.
– YCor
Nov 17, 2019 at 12:28
• (2) is false even with the correction. Just perturb the identity matrix slightly. Nov 17, 2019 at 14:38
• 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$... Nov 17, 2019 at 21:23

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)$$

• 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 . Nov 17, 2019 at 17:16
• Oops yep, good point. I'll edit appropriately. Nov 17, 2019 at 17:18
• 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. Nov 17, 2019 at 18:05
• Concerning conjecture 2), Sam Zbarsky's comment shows it is false. Nov 17, 2019 at 19:06
• @‍SamZbarsky's comment referenced by @IosifPinelis. Nov 18, 2019 at 16:26