International Mathematics Competition
for University Students
2026

IMC2026: Day 2, Problem 8

Problem 8. Let \(\displaystyle n\geq 5\), and suppose that \(\displaystyle A = (a_{ij})\) is a real symmetric \(\displaystyle n\times n\) matrix such that

\(\displaystyle a_{ii} = 0 \quad\text{and}\quad a_{ij}\in\{-1,1\} \text{ for }i\neq j . \)

Assume that the scalar products of any two distinct rows of \(\displaystyle A\) have the same value. Let \(\displaystyle \lambda_1,\ldots,\lambda_n\) be the eigenvalues of \(\displaystyle A\). Prove that

\(\displaystyle \sum_{i=1}^n\lvert\lambda_i\rvert \geq 2n-2 \)

and determine all matrices for which equality holds.

Slobodan Filipovski, University of Primorska, Koper

Solution. Let \(\displaystyle c\) be the common scalar product of any two distinct rows, and let \(\displaystyle J\) be the all-ones matrix. Since every row has squared norm \(\displaystyle n-1\) and every two distinct rows have scalar product \(\displaystyle c\), we have

\(\displaystyle A^2=(n-1-c)I+cJ. \tag{1} \)

emacs p9

The eigenvalues of the right-hand side are

\(\displaystyle (n-1)(c+1) \quad\text{and}\quad n-1-c \quad\text{(with multiplicity \(\displaystyle n-1\))}. \)

Since \(\displaystyle A\) is real symmetric, the matrix \(\displaystyle A^{2}\) is positive semidefinite. Hence all eigenvalues of \(\displaystyle A^{2}\) are nonnegative. Thus \(\displaystyle c\ge -1\). Also, for \(\displaystyle i\ne j\),

\(\displaystyle c=\sum_{k=1}^n a_{ik}a_{jk}=\sum_{k\ne i,j}a_{ik}a_{jk}\le n-2, \)

since the two omitted terms are zero and each remaining term is at most \(\displaystyle 1\). Therefore

\(\displaystyle -1\le c\le n-2. \)

Since the eigenvalues of \(\displaystyle A^2\) are \(\displaystyle \lambda_1^2,\ldots,\lambda_n^2\), we obtain

\(\displaystyle \sum_{i=1}^{n}|\lambda_i| = \sqrt{(n-1)(c+1)}+(n-1)\sqrt{n-1-c}. \tag{2} \)

emacs p9

The right-hand side of (2) is a concave function of \(\displaystyle c\) on the interval \(\displaystyle [-1,n-2]\). Its minimum is therefore attained at an endpoint. At the two endpoints its values are

\(\displaystyle (n-1)\sqrt n \quad\text{and}\quad 2n-2, \)

respectively. Since \(\displaystyle n\ge5\), we have \(\displaystyle (n-1)\sqrt n>2n-2\), and hence

\(\displaystyle \sum_{i=1}^{n}|\lambda_i|\ge2n-2. \)

Equality can occur only for \(\displaystyle c=n-2\). By (1),

\(\displaystyle A^2=I+(n-2)J. \tag{3} \)

emacs p9 It follows that \(\displaystyle A\) commutes with \(\displaystyle J\). Hence \(\displaystyle A\mathbf 1=r\mathbf 1\) for some real number \(\displaystyle r\), where \(\displaystyle \mathbf 1\) is the all-ones vector. Applying (3) to \(\displaystyle \mathbf 1\) gives

\(\displaystyle r^2\mathbf 1=A^2\mathbf 1=(n-1)^2\mathbf 1, \)

so \(\displaystyle r=\pm(n-1)\). Since every row contains exactly \(\displaystyle n-1\) entries equal to \(\displaystyle \pm1\), its sum can equal \(\displaystyle \pm(n-1)\) only if all off-diagonal entries in that row are equal. Hence every row consists entirely of \(\displaystyle 1\)'s or entirely of \(\displaystyle -1\)'s. By symmetry, all rows have the same sign, and therefore

\(\displaystyle A=J-I \quad\text{or}\quad A=I-J. \)

Conversely, these two matrices have spectra

\(\displaystyle \{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 \(\displaystyle 2n-2\).