uniolympiads Ελληνικά

IMC 2026, Day 2, Problem 8

Let n≥5n \ge 5, and suppose that A=(aij)A = (a_{ij}) is a real symmetric n×nn \times n matrix such that

aii=0andaij∈{−1,1} for i≠j.a_{ii} = 0 \quad \text{and} \quad a_{ij} \in \{-1, 1\} \text{ for } i \ne j.

Assume that the scalar products of any two distinct rows of AA have the same value. Let λ1,…,λn\lambda_1, \dots, \lambda_n be the eigenvalues of AA. Prove that

∑i=1n∣λi∣≥2n−2\sum_{i=1}^{n} |\lambda_i| \ge 2n - 2

and determine all matrices for which equality holds.

Original from the official PDFLet n ≥ 5, and suppose that A = (aij) is a real symmetric n × n matrix such that aii = 0 and aij ∈ {−1,1} for i ≠ j. Assume that the scalar products of any two distinct rows of A have the same value. Let λ1,...,λn be the eigenvalues of A. Prove that ∑ |λi| ≥ 2n − 2 and determine all matrices for which equality holds.

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

(proposed by Slobodan Filipovski, University of Primorska, Koper)

Solution. Let cc be the common scalar product of any two distinct rows, and let JJ be the all-ones matrix. Since every row has squared norm n−1n-1 and every two distinct rows have scalar product cc, we have

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

The eigenvalues of the right-hand side are

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

Since AA is real symmetric, the matrix A2A^2 is positive semidefinite. Hence all eigenvalues of A2A^2 are nonnegative. Thus c≥−1c \ge -1. Also, for i≠ji \ne j,

c=∑k=1naikajk=∑k≠i,jaikajk≤n−2,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 11. Therefore
−1≤c≤n−2.-1 \le c \le n-2.
Since the eigenvalues of A2A^2 are λ12,…,λn2\lambda_1^2, \ldots, \lambda_n^2, we obtain
∑i=1n∣λi∣=(n−1)(c+1)+(n−1)n−1−c.(2)\sum_{i=1}^{n} |\lambda_i| = \sqrt{(n-1)(c+1)} + (n-1)\sqrt{n-1-c}. \tag{2}

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

(n−1)nand2n−2,(n-1)\sqrt{n} \quad \text{and} \quad 2n-2,
respectively. Since n≥5n \ge 5, we have (n−1)n>2n−2(n-1)\sqrt{n} > 2n-2, and hence
∑i=1n∣λi∣≥2n−2.\sum_{i=1}^{n} |\lambda_i| \ge 2n-2.

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

A2=I+(n−2)J.(3)A^2 = I + (n-2)J. \tag{3}
It follows that AA commutes with JJ. Hence A1=r1A\mathbf{1} = r\mathbf{1} for some real number rr, where 1\mathbf{1} is the all-ones vector. Applying (3) to 1\mathbf{1} gives
r21=A21=(n−1)21,r^2\mathbf{1} = A^2\mathbf{1} = (n-1)^2\mathbf{1},
so r=±(n−1)r = \pm(n-1). Since every row contains exactly n−1n-1 entries equal to ±1\pm 1, its sum can equal ±(n−1)\pm(n-1) only if all off-diagonal entries in that row are equal. Hence every row consists entirely of 11’s or entirely of −1-1’s. By symmetry, all rows have the same sign, and therefore
A=J−IorA=I−J.A = J - I \quad \text{or} \quad A = I - J.

Conversely, these two matrices have spectra

{n−1,−1,…,−1}and{−(n−1),1,…,1},\{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 2n−22n-2.

Transcribed from the official solutions, pages 3–5. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?