IMC 2026 · Day 2 · P8

Let $c$ be the common scalar product of any two distinct rows, and let $J$ be the all-ones matrix. Since every row has squared norm $n-1$ and every two distinct rows have scalar product $c$, we have $$\begin{equation} A^{2} = (n - 1 - c) I + c J. \tag{1} \end{equation}$$

The eigenvalues of the right-hand side are $$(n-1)(c+1) \quad \text{and} \quad n - 1 - c \quad \text{(with multiplicity } n-1 \text{)}.$$

Since $A$ is real symmetric, the matrix $A^{2}$ is positive semidefinite. Hence all eigenvalues of $A^{2}$ are nonnegative. Thus $c \geq -1$. Also, for $i \neq j$, $$c = \sum_{k=1}^{n} a_{i k} a_{j k} = \sum_{k \neq i, j} a_{i k} a_{j k} \leq n - 2,$$ since the two omitted terms are zero and each remaining term is at most 1. Therefore $$-1 \leq c \leq n - 2.$$ Since the eigenvalues of $A^{2}$ are $\lambda_{1}^{2}, \ldots, \lambda_{n}^{2}$, we obtain $$\begin{equation} \sum_{i=1}^{n} \left| \lambda_{i} \right| = \sqrt{(n-1)(c+1)} + (n-1) \sqrt{n - 1 - c}. \tag{2} \end{equation}$$

The right-hand side of (2) is a concave function of $c$ on the interval $[-1, n-2]$. Its minimum is therefore attained at an endpoint. At the two endpoints its values are $$(n-1) \sqrt{n} \quad \text{and} \quad 2 n - 2,$$ respectively. Since $n \geq 5$, we have $(n-1) \sqrt{n} > 2 n - 2$, and hence $$\sum_{i=1}^{n} \left| \lambda_{i} \right| \geq 2 n - 2.$$

Equality can occur only for $c = n - 2$. By (1), $$\begin{equation} A^{2} = I + (n-2) J. \tag{3} \end{equation}$$ It follows that $A$ commutes with $J$. Hence $A \mathbf{1} = r \mathbf{1}$ for some real number $r$, where $\mathbf{1}$ is the all-ones vector. Applying (3) to $\mathbf{1}$ gives $$r^{2} \mathbf{1} = A^{2} \mathbf{1} = (n-1)^{2} \mathbf{1},$$ so $r = \pm (n-1)$. Since every row contains exactly $n-1$ entries equal to $\pm 1$, its sum can equal $\pm (n-1)$ only if all off-diagonal entries in that row are equal. Hence every row consists entirely of 1's or entirely of $-1$'s. By symmetry, all rows have the same sign, and therefore $$A = J - I \quad \text{or} \quad A = I - J.$$

Conversely, these two matrices have spectra $$\{ n-1, -1, \ldots, -1 \} \quad \text{and} \quad \{ -(n-1), 1, \ldots, 1 \},$$ respectively, and in both cases the sum of the absolute values of the eigenvalues is $2 n - 2$.