| |||||||||||||
IMC2021: Day 2, Problem 8Problem 8. Let \(\displaystyle n\) be a positive integer. At most how many distinct unit vectors can be selected in \(\displaystyle \RR^n\) such that from any three of them, at least two are orthogonal? Alexander Polyanskii, Moscow Institute of Physics and Technology; Solution 1. \(\displaystyle 2n\) is the maximal number. An example of \(\displaystyle 2n\) 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 \(\displaystyle 2n+1\) vectors in the set. Consider the Gram matrix \(\displaystyle A\) with entries \(\displaystyle a_{ij} = e_i\cdot e_j\). Its rank is at most \(\displaystyle n\), its eigenvalues are real and non-negative. Put \(\displaystyle B = A - I_{2n+1}\), this is the same matrix, but with zeros on the diagonal. The eigenvalues of \(\displaystyle B\) are real, greater or equal to \(\displaystyle -1\), and the multiplicity of \(\displaystyle -1\) is at least \(\displaystyle n+1\). The matrix \(\displaystyle C=B^3\) has the following diagonal entries \(\displaystyle c_{ii} = \sum_{i\neq j\neq k\neq 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 \(\displaystyle \mathop{\rm tr} C = 0\). Let \(\displaystyle x_1,\ldots, x_m\) be the positive eigenvalues of \(\displaystyle B\), their number is \(\displaystyle m\le n\) as noted above. From \(\displaystyle \mathop{\rm tr}B = \mathop{\rm tr}C\) we deduce (taking into account that the eigenvalues between \(\displaystyle -1\) and \(\displaystyle 0\) satisfy \(\displaystyle \lambda^3\ge \lambda\)): \(\displaystyle x_1+\dots+x_m \ge x_1^3+\dots+x_m^3 \) Applying \(\displaystyle \mathop{\rm tr}C = 0\) once again and noting that \(\displaystyle C\) has eigenvalue \(\displaystyle -1\) of multiplicity at least \(\displaystyle n+1\), we obtain \(\displaystyle x_1^3+\dots+x_m^3\ge n+1. \) It also follows that \(\displaystyle \left( x_1+\dots+x_m \right)^3 \ge \left( x_1^3+\dots+x_m^3 \right) (n+1)^2. \) By Hölder's inequality, we obtain \(\displaystyle \left( x_1^3+\dots+x_m^3 \right) m^2 \ge \left( x_1+\dots+x_m \right)^3, \) which is a contradiction with \(\displaystyle m\le n\). Solution 2. Let \(\displaystyle P_i\) denote the projection onto \(\displaystyle i\)-th vector, \(\displaystyle i=1,\ldots,N\). Then our relation reads as \(\displaystyle {\rm tr}\,(P_iP_jP_k)=0\) for distinct \(\displaystyle i,j,k\). Consider the operator \(\displaystyle Q=\sum_{i=1}^N P_i\), it is non-negative definite, let \(\displaystyle t_1,\ldots,t_n\) be its eigenvalues, \(\displaystyle \sum t_i={\rm tr}\, Q=N\). We get \(\displaystyle \sum t_i^3={\rm tr}\, Q^3=N+6\sum_{i<j} {\rm tr}\, P_iP_j =N+3({\rm tr}\, Q^2-N)=3\sum t_i^2-2N \) (we used the obvious identities like \(\displaystyle {\rm tr} P_iP_jP_i= {\rm tr}\, P_i^2P_j={\rm tr}\, P_iP_j\)). But \(\displaystyle (t_i-2)^2(t_i+1)=t_i^3-3t_i^2+4\geqslant 0\), thus \(\displaystyle -2N=\sum t_i^3-3t_i^2\geqslant -4n\) and \(\displaystyle N\leqslant 2n\). Solution 3. (from the work of a student) Let \(\displaystyle G\) be the Gram matrix of the given set. As in solution 1 it has at most \(\displaystyle n\) nonzero eigenvalues \(\displaystyle \lambda_1, \dots, \lambda_n\). By Jensen's inequality we have the following
On the other hand, \(\displaystyle \tr(G^2)\) is the sum of squares of all entries of \(\displaystyle G\). Fix an index \(\displaystyle i\), then \(\displaystyle \sum_j G_{ij}^2 = 1 + \sum_{v_j \not\perp v_i} \langle v_j, v_i \rangle^2 \le 2, \) by Bessel's inequality (the set of vector not perpendicular to a given \(\displaystyle v_i\) is an orthonormal set). Hence the sum of squared entries of \(\displaystyle G\) is at most \(\displaystyle 2N\). Together with (1) we get that \(\displaystyle N \le 2n\) as needed. | |||||||||||||
© IMC |