Which orthonormal matrix of size $N \times N$ has the maximum sum of elements?

In other words, I want to find $$\max_\mathbf{U} \bf\underline{1}^TU\underline{1}$$ where $\mathbf{U}$ is an $N \times N$ real orthonormal matrix.

Since problems like this often have trivial solutions, I would guess the answer would be: any permutation matrix, whose elements sum to $N$. How do I prove this? I can prove it for $N=2$ matrix, but how do I prove this for an arbitrary $N$?

Solution 1:

Using the Cauchy-Schwarz inequality and the fact that $U$ is orthonormal, we have $$\vec{1}^TU\vec{1} = \left\langle\vec{1}, U\vec{1}\right\rangle \le \|\vec{1}\| \cdot \|U\vec{1}\| = \|\vec{1}\| \cdot \|\vec{1}\| = \|\vec{1}\|^2 = N.$$ As you noted, equality holds when $U$ is a permutation matrix, so $\displaystyle\max_U \vec{1}^TU\vec{1} = N$.