IMC 2013 · Day 2 · P8

If $v_1, \dots, v_d$ are linearly dependent then we can simply take a unit vector $u$ perpendicular to $\operatorname{span}(v_1, \dots, v_d)$. So assume that $v_1, \dots, v_d$ are linearly independent. Let $w_1, \dots, w_d$ be the dual basis of $(v_1, \dots, v_d)$, i.e. $$w_i \cdot v_j = \delta_{ij} = \begin{cases} 1 & \text{if } i = j \\ 0 & \text{if } i \ne j \end{cases} \quad \text{for } 1 \le i, j \le d.$$ From $w_i \cdot v_i = 1$ we have $|w_i| \ge 1$.

For every sequence $\varepsilon = (\varepsilon_1, \dots, \varepsilon_d) \in \{+1, -1\}^d$ of signs define $u_\varepsilon = \sum_{i=1}^{d} \varepsilon_i w_i$. Then we have $$|u_\varepsilon \cdot v_k| = \left| \sum_{i=1}^{d} \varepsilon_i (w_i \cdot v_k) \right| = \left| \sum_{i=1}^{d} \varepsilon_i \delta_{ik} \right| = |\varepsilon_k| = 1 \quad \text{for } k = 1, \dots, d.$$ Now estimate the average of $|u_\varepsilon|^2$. $$\begin{align*} \frac{1}{2^d} \sum_{\varepsilon \in \{+1,-1\}^n} |u_\varepsilon|^2$$

&= \frac{1}{2^d} \sum_{\varepsilon \in \{+1,-1\}^n} \left( \sum_{i=1}^{d} \varepsilon_i w_i \right) \cdot \left( \sum_{j=1}^{d} \varepsilon_j w_j \right) = \\ &= \sum_{i=1}^{d} \sum_{j=1}^{d} (w_i \cdot w_j) \left( \frac{1}{2^d} \sum_{\varepsilon \in \{+1,-1\}^n} \varepsilon_i \varepsilon_j \right) = \sum_{i=1}^{d} \sum_{j=1}^{d} (w_i \cdot w_j) \delta_{ij} = \sum_{i=1}^{d} |w_i|^2 \ge d. \end{align*} It follows that there is a $\varepsilon$ such that $|u_\varepsilon|^2 \ge d$. For that $\varepsilon$ the vector $u = \frac{u_\varepsilon}{|u_\varepsilon|}$ satisfies the conditions.