Return to Answer

Mehtaab Sawhney answered and then deleted his answer to point out that this problem is solved in Lemma 11 of Cycles of a given length in tournaments! The largest operator norm is always achieved by the matrix which is $1$'s above the diagonal and $-1$'s below it. (As well as by the many other matrices which are conjugate to this one by signed permutation matrices.)

Another poster answered and then deleted his answer to point out that this problem is solved in Lemma 11 of Cycles of a given length in tournaments! (On reflection, I have removed this poster's name since they choose to self-delete, but I hope they will identify themselves and claim the credit; this is useful!) The largest operator norm is always achieved by the matrix which is $1$'s above the diagonal and $-1$'s below it. (As well as by the many other matrices which are conjugate to this one by signed permutation matrices.)

$\def\Tr{\mathrm{Tr}}\def\Mat{\mathrm{Mat}}$I've been thinking about this problem a bunch, and I think the correct bound is $$ \sum_{i,j} |A_{ij}| \leq \left( \cot \frac{\pi}{2n} \right)|A|_{(1)}. $$ As $n \to \infty$, we have $\cot \tfrac{\pi}{2n} \sim \tfrac{2n}{\pi}$, so this matches the $\pi$ bound that fedja proved for $k=2$. Unfortunately, I can't prove much, but here are ideas that might help someone else.

$\def\Tr{\mathrm{Tr}}\def\Mat{\mathrm{Mat}}$I've been thinking about this problem a bunch, and I think the correct bound is $$ \sum_{i,j} |A_{ij}| \leq \left( \cot \frac{\pi}{2n} \right)|A|_{(1)}. $$ As $n \to \infty$, we have $\cot \tfrac{\pi}{2n} \sim \tfrac{2n}{\pi}$, so this matches the $\pi$ bound that fedja proved for $k=2$. In particular, I will prove that this bound is correct for skew-symmetric $A$; almost all the work is not due to me but to a paper of Grzesik, Kral, Lovasz and Volec which was pointed out in a deleted answer by another user.

I have checked for $n \leq 7$, and the largest operator norm is always achieved by the matrix which is $1$'s above the diagonal and $-1$'s below it. (As well as by the many other matrices which are conjugate to this one by signed permutation matrices.) This matrix can be explicitly diagonalized: The eigenvectors are of the form $(1, \zeta, \zeta^2, \ldots, \zeta^{n-1})$ where $\zeta = \exp(\pi i (2j+1)/(2n))$. The corresponding eigenvalues are $i \cot \tfrac{(2j+1) \pi}{2n}$. In particular, the largest singular value is $\cot \tfrac{\pi}{2n}$, thus explaining my guess.

Mehtaab Sawhney answered and then deleted his answer to point out that this problem is solved in Lemma 11 of Cycles of a given length in tournaments! The largest operator norm is always achieved by the matrix which is $1$'s above the diagonal and $-1$'s below it. (As well as by the many other matrices which are conjugate to this one by signed permutation matrices.) 

This matrix can be explicitly diagonalized: The eigenvectors are of the form $(1, \zeta, \zeta^2, \ldots, \zeta^{n-1})$ where $\zeta = \exp(\pi i (2j+1)/(2n))$. The corresponding eigenvalues are $i \cot \tfrac{(2j+1) \pi}{2n}$. In particular, the largest singular value is $\cot \tfrac{\pi}{2n}$, thus explaining my guess.