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.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: