Return to Answer

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 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}| \geq 1/\sqrt{n}$ for every $i$, which gives the second part of the OP's question.

It is worth noting that it might be possible to strengthen these bounds by considering a more interesting permutation than a transposition in the original inequality.

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

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 $\max(2\sin(\theta),2\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 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}| \geq 1/\sqrt{n}$ for every $i$, which gives the second part of the OP's question.

It is worth noting that it might be possible to strengthen these bounds by considering a more interesting permutation than a transposition in the original inequality.

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 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}| \geq 1/\sqrt{n}$ for every $i$, which gives the second part of the OP's question.

It is worth noting that it might be possible to strengthen these bounds by considering a more interesting permutation than a transposition in the original inequality.

Consider a unitary matrix $U = (u_{i,j})$. We will show the slightly stronger statement that there is some permutation $\pi:[n] \to [n]$ such that $|u_{i,\pi(i)}| \leq 1/\sqrt{n}$ for all $i$. 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_*).$$ Summing over $i$, we moreover deduce that: $$2n \geq 2nI(\pi_*),$$ whence we conclude that $I(\pi_*) \leq 1$ and hence from the previous inequality $n |v_{i,i}|^2 \leq 1$. Rearranging gives the desired result.

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 $\max(2\sin(\theta),2\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 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}| \geq 1/\sqrt{n}$ for every $i$, which gives the second part of the OP's question.

It is worth noting that it might be possible to strengthen these bounds by considering a more interesting permutation than a transposition in the original inequality.