Maximal spectral norm of balanced $\pm 1$ matrix

Question

Suppose that we have a square matrix $A = [a_{ij}] \in {\Bbb R}^{n \times n}$ whose entries are $\pm 1$ and whose columns are balanced, i.e., $\sum_{i=1}^n a_{ij}=0$. How large can the spectral norm of $A$ be at most?

Answer 1

It's just $n$. As $\text{Tr}(A^tA)=n^2$, we have the maximal eigenvalue of $\text{Tr}(A^tA)$ is at most $n^2$ whose square-root is at most $n$.

The upper bound $n$ can be achieved: consider the matrix $A$ with identical column vectors $v$, and let $w=(1, 1, \cdots, 1)^t$, then we have $\|w\|=\|v\|$ and $\|Aw\| = \|nv\|$, so $\frac{\|Aw\|}{\|w\|}=n, \|A\|\ge n$

Also, the maximal eigenvalue $n$ of $A^tA$ is achieved iff $A^tA$ has eigenvalue $0$ of multiplicity $(n-1)$, or equivalently $\text{Tr}(A^tA)=\text{Tr}(A)=1$. Hence $A$ achives maximum spectral norm $n$ iff all columns are linearly dependent (identical up to a sign based on the condition).

Note that when $n$ is odd, no such matrix exists.