Let $J$ be the $n$ by $n$ matrix of all 1's. Let $f(n)$ be the least number $m$ of unitary matrices $U_1,\dots,U_m$ so that $J = U_1 + \cdots + U_m$. What can you say about the growth of the function $f(n)$?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Hint: $J$ has an eigenvector for eigenvalue $n$. What can you say about $\|Uv\|$ for a unitary matrix $U$ and vector $v$?
Robert Israel has given a hint for finding a lower bound on $f(n)$. To see that the lower bound is sharp, you can write $J$ as a sum of permutation matrices.