uniolympiads Ελληνικά

IMC 2021, Day 2, Problem 8

Let nn be a positive integer. At most how many distinct unit vectors can be selected in Rn\mathbb{R}^n such that from any three of them, at least two are orthogonal?

Original from the official PDFLet n be a positive integer. At most how many distinct unit vectors can be selected in R n such that from any three of them, at least two are orthogonal?

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 Alexander Polyanskii, Moscow Institute of Physics and Technology; based on results of Paul Erdős and Moshe Rosenfeld)

Hint: Play with the Gram matrix of these vectors.

Solution 1. 2n2n is the maximal number.

An example of 2n2n vectors in the set is given by a basis and its opposite vectors. In the rest of the text we prove that it is impossible to have 2n+12n+1 vectors in the set.

Consider the Gram matrix AA with entries aij=ei⋅eja_{ij} = e_i\cdot e_j. Its rank is at most nn, its eigenvalues are real and non-negative. Put B=A−I2n+1B = A - I_{2n+1}, this is the same matrix, but with zeros on the diagonal. The eigenvalues of BB are real, greater or equal to −1-1, and the multiplicity of −1-1 is at least n+1n+1.

The matrix C=B3C = B^3 has the following diagonal entries

cii=∑i≠j≠k≠iaijajkaki.c_{ii} = \sum_{i \ne j \ne k \ne i} a_{ij}a_{jk}a_{ki}.

The problem statement implies that in every summand of this expression at least one factor is zero. Hence tr⁡C=0\operatorname{tr} C = 0. Let x1,…,xmx_1, \ldots, x_m be the positive eigenvalues of BB, their number is m≤nm \le n as noted above. From tr⁡B=tr⁡C\operatorname{tr} B = \operatorname{tr} C we deduce (taking into account that the eigenvalues between −1-1 and 00 satisfy λ3≥λ\lambda^3 \ge \lambda):

x1+⋯+xm≥x13+⋯+xm3x_1 + \cdots + x_m \ge x_1^3 + \cdots + x_m^3

Applying tr⁡C=0\operatorname{tr} C = 0 once again and noting that CC has eigenvalue −1-1 of multiplicity at least n+1n+1, we obtain

x13+⋯+xm3≥n+1.x_1^3 + \cdots + x_m^3 \ge n + 1.

It also follows that

(x1+⋯+xm)3≥(x13+⋯+xm3)(n+1)2.(x_1 + \cdots + x_m)^3 \ge \left(x_1^3 + \cdots + x_m^3\right)(n+1)^2.

By Hölder’s inequality, we obtain

(x13+⋯+xm3)m2≥(x1+⋯+xm)3,\left(x_1^3 + \cdots + x_m^3\right)m^2 \ge (x_1 + \cdots + x_m)^3,
which is a contradiction with m≤nm \le n.

Solution 2. Let PiP_i denote the projection onto ii-th vector, i=1,…,Ni = 1, \ldots, N. Then our relation reads as tr⁡(PiPjPk)=0\operatorname{tr}(P_iP_jP_k) = 0 for distinct i,j,ki, j, k. Consider the operator Q=∑i=1NPiQ = \sum_{i=1}^N P_i, it is non-negative definite, let t1,…,tnt_1, \ldots, t_n be its eigenvalues, ∑ti=tr⁡Q=N\sum t_i = \operatorname{tr} Q = N. We get

∑ti3=tr⁡Q3=N+6∑i<jtr⁡PiPj=N+3(tr⁡Q2−N)=3∑ti2−2N\sum t_i^3 = \operatorname{tr} Q^3 = N + 6\sum_{i<j} \operatorname{tr} P_iP_j = N + 3(\operatorname{tr} Q^2 - N) = 3\sum t_i^2 - 2N
(we used the obvious identities like tr⁡PiPjPi=tr⁡Pi2Pj=tr⁡PiPj\operatorname{tr} P_iP_jP_i = \operatorname{tr} P_i^2P_j = \operatorname{tr} P_iP_j). But (ti−2)2(ti+1)=ti3−3ti2+4⩾0(t_i - 2)^2(t_i + 1) = t_i^3 - 3t_i^2 + 4 \geqslant 0, thus −2N=∑ti3−3ti2⩾−4n-2N = \sum t_i^3 - 3t_i^2 \geqslant -4n and N⩽2nN \leqslant 2n.

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