uniolympiads Ελληνικά

IMC 2014, Day 2, Problem 2

Let A=(aij)i,j=1nA = (a_{ij})_{i,j=1}^{n} be a symmetric n×nn \times n matrix with real entries, and let λ1,λ2,…,λn\lambda_1, \lambda_2, \dots, \lambda_n denote its eigenvalues. Show that

∑1≤i<j≤naiiajj≥∑1≤i<j≤nλiλj,\sum_{1 \le i < j \le n} a_{ii}a_{jj} \ge \sum_{1 \le i < j \le n} \lambda_i\lambda_j,

and determine all matrices for which equality holds.

Original from the official PDFLet A = (a ij ) ni,j=1 be a symmetri n × n matrix with real entries, and let λ 1 , λ 2 , . . . , λ n denote its eigenvalues. Show that Problem 2. X a ii a jj ≥ 1≤i<j≤n X λ i λ j , 1≤i<j≤n and determine all matri es for whi h 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 Martin Niepel, Comenius University, Bratislava)

Solution. Eigenvalues of a real symmetric matrix are real, hence the inequality makes sense. Similarly, for Hermitian matrices diagonal entries as well as eigenvalues have to be real.

Since the trace of a matrix is the sum of its eigenvalues, for AA we have

∑i=1naii=∑i=1nλi,\sum_{i=1}^n a_{ii} = \sum_{i=1}^n \lambda_i,
and consequently
∑i=1naii2+2∑i<jaiiajj=∑i=1nλi2+2∑i<jλiλj.\sum_{i=1}^n a_{ii}^2 + 2\sum_{i<j} a_{ii}a_{jj} = \sum_{i=1}^n \lambda_i^2 + 2\sum_{i<j}\lambda_i\lambda_j.
Therefore our inequality is equivalent to
∑i=1naii2≤∑i=1nλi2.\sum_{i=1}^n a_{ii}^2 \le \sum_{i=1}^n \lambda_i^2.
Matrix A2A^2, which is equal to ATAA^TA (or A∗AA^*A in Hermitian case), has eigenvalues λ12,λ22,…,λn2\lambda_1^2, \lambda_2^2, \ldots, \lambda_n^2. On the other hand, the trace of ATAA^TA gives the square of the Frobenius norm of AA, so we have
∑i=1naii2≤∑i,j=1n∣aij∣2=tr(ATA)=tr(A2)=∑i=1nλi2.\sum_{i=1}^n a_{ii}^2 \le \sum_{i,j=1}^n |a_{ij}|^2 = \mathrm{tr}(A^TA) = \mathrm{tr}(A^2) = \sum_{i=1}^n \lambda_i^2.
The inequality follows, and it is clear that the equality holds for diagonal matrices only.

Remark. Same statement is true for Hermitian matrices.

Transcribed from the official solutions, pages 1–2. 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?