Maths Olympiad Prep

Library / /11 of 43

Algebra Difficulty 7.7 National olympiad, round 2 Find the answer

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?

A number or a short expression. Spacing and $ signs are ignored.

Solution

Solution 1. 2n2 n is the maximal number. An example of 2n2 n 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+12 n+1 vectors in the set. Consider the Gram matrix AA with entries aij=eieja_{i j}=e_{i} \cdot e_{j}. Its rank is at most nn, its eigenvalues are real and non-negative. Put B=AI2n+1B=A-I_{2 n+1}, this is the same matrix, but with zeros on the diagonal. The eigenvalues of BB are real, greater or equal to -1, and the multiplicity of -1 is at least n+1n+1. The matrix C=B3C=B^{3} has the following diagonal entries cii=ijkiaijajkakic_{i i}=\sum_{i \neq j \neq k \neq i} a_{i j} a_{j k} a_{k i} The problem statement implies that in every summand of this expression at least one factor is zero. Hence trC=0\operatorname{tr} C=0. Let x1,,xmx_{1}, \ldots, x_{m} be the positive eigenvalues of BB, their number is mnm \leq n as noted above. From trB=trC\operatorname{tr} B=\operatorname{tr} C we deduce (taking into account that the eigenvalues between -1 and 0 satisfy λ3λ\lambda^{3} \geq \lambda ): x1++xmx13++xm3x_{1}+\cdots+x_{m} \geq x_{1}^{3}+\cdots+x_{m}^{3} Applying trC=0\operatorname{tr} C=0 once again and noting that CC has eigenvalue -1 of multiplicity at least n+1n+1, we obtain x13++xm3n+1x_{1}^{3}+\cdots+x_{m}^{3} \geq n+1 It also follows that (x1++xm)3(x13++xm3)(n+1)2\left(x_{1}+\cdots+x_{m}\right)^{3} \geq\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} \geq\left(x_{1}+\cdots+x_{m}\right)^{3} which is a contradiction with mnm \leq 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}\left(P_{i} P_{j} P_{k}\right)=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=trQ=N\sum t_{i}=\operatorname{tr} Q=N. We get ti3=trQ3=N+6i<jtrPiPj=N+3(trQ2N)=3ti22N\sum t_{i}^{3}=\operatorname{tr} Q^{3}=N+6 \sum_{i<j} \operatorname{tr} P_{i} P_{j}=N+3\left(\operatorname{tr} Q^{2}-N\right)=3 \sum t_{i}^{2}-2 N (we used the obvious identities like trPiPjPi=trPi2Pj=trPiPj\operatorname{tr} P_{i} P_{j} P_{i}=\operatorname{tr} P_{i}^{2} P_{j}=\operatorname{tr} P_{i} P_{j} ). But (ti2)2(ti+1)=ti33ti2+40\left(t_{i}-2\right)^{2}\left(t_{i}+1\right)=t_{i}^{3}-3 t_{i}^{2}+4 \geqslant 0, thus 2N=ti33ti24n-2 N=\sum t_{i}^{3}-3 t_{i}^{2} \geqslant-4 n and N2nN \leqslant 2 n.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.