uniolympiads English

IMC 2026, Ημέρα 2, Θέμα 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.

Πρωτότυπο από το επίσημο 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.

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

(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.

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 3–5. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;