## A geometric lemma

The following lemma is a curious result that I’ve now found useful both in Lie algebras (in the classification of root systems) and coding theory (to prove the Plotkin bounds).

Lemma. Suppose that $u_1, \ldots, u_m$ are non-zero vectors in a real inner product space such that $\left< u_i, u_j \right> \le 0$ for all distinct $i$ and $j$. Then

1. if $\sum_i \alpha_i u_i = 0$ where the minimal possible number of $\alpha_i \in \mathbf{R}$ are non-zero then all the non-zero $\alpha_i$ have the same sign; and
2. $u_1, \ldots, u_m$ are linearly independent if and only if there exists a vector $v$ such that $\left< v, u_i \right> > 0$ for all $i$.

Proof. Suppose that there is a non-trivial linear dependency between the $u_i$. Separating the coefficients according to their sign, we get a relation

$\sum_{i \in I} \alpha_i u_i = \sum_{j \in J} \beta_j u_j$

where $I$ and $J$ are disjoint subsets of $\{1,\ldots,m\}$ and the $\alpha_i$ and $\beta_j$ are strictly positive. Let $w$ be the common value of both sides of the above equation. Then

$0 \le \left< w, w \right> = \sum_{i \in I} \sum_{j \in J} \alpha_i \beta_j \left< u_i, u_j \right> \le 0$

so $w = 0$. This proves the first part of the lemma.

Moreover if a vector $v$ exists satisfying the hypothesis of the second part then

$\left< v, w\right> = \sum_{i \in I} \alpha_i \left< u_i, v \right> > 0.$

which proves the ‘if’ direction of the second part.

For the ‘only if’ direction we need to find a $v$ making a small angle with all of the $u_i$. If we try to construct such a $v$ as a linear combination of the $u_i$, we quickly lose all control over the various inner products. What works much better is to work with vectors known to be perpendicular to most of the $u_i$. Let $U$ be the subspace spanned by the $u_i$, and choose for each $j$, a non-zero vector $v_j \in U$ perpendicular to all the $u_i$ for $i \not= j$. (This is possible because the span of these vectors has codimension at least one in $U$.) Note that $\left< v_j, u_j \right> \not=0$, since otherwise $\left< v_j, U \right> = 0$. Therefore, if $v = \sum_{j=1}^n \lambda_j v_j$ we have

$\left< v, u_j \right> = \lambda_j \left< v_j, u_j \right>$

and by taking $\lambda_j \in \{+1, -1\}$ so that $\lambda_j$ has the opposite sign to $\left< v_j, u_j \right>$ we get a suitable $v$.

Advertisements