International Mathematics Competition
for University Students
2021

IMC2021: Day 2, Problem 8

Problem 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;
based on results of Paul Erdős and Moshe Rosenfeld

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

\(\displaystyle \tr(G^2) = \sum_i \lambda_i^2 \ge \frac{(\sum_i \lambda_i)^2}{n} = \frac{\tr(G)^2}{n} = \frac{N^2}{n}. \)

\(\displaystyle (1) \)

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.