# Monthly Archives: May 2014

## Independence of Eigenvectors and the Well Ordering Principle

In linear algebra, we frequently use the fact that a set of eigenvectors with pairwise distinct eigenvalues is linearly independent. Hoffman and Kunze prove this fact (see the proof of the second lemma on page 186) by using some elementary facts about polynomials. Here we prove the linear independence of eigenvectors using the well-ordering principle:

Well-ordering principle Suppose $$S$$ is a non-empty subset of the natural numbers, $$S \subseteq \mathbf{N}$$. Then $$S$$ has a minimal element.

The well-ordering principle is equivalent to mathematical induction, and is thus a fundamental property of the natural numbers. Like induction, the well-ordering principle is frequently used to prove properties which hold for every natural number. The following is a common strategy for applying the well-ordering principle to prove that every natural number satisfies some property $$P$$:

1. Suppose $$S$$ is the set of natural numbers that do not possess property $$P$$.
2. By the well-ordering principle, if $$S$$ is not empty it must contain a smallest element, $$x_0$$.
3. Construct some $$x < x_0$$ which does not satisfy $$P$$, hence is also contained in $$S$$.
4. The existence of $$x$$ contradicts the minimality of $$x_0$$, implying that $$S$$ has no minimal element.
5. Therefore, $$S$$ must be empty (by the well-ordering principle), hence $$P$$ holds for every natural number.

This proof technique differs from mathematical induction in that the argument uses contraposition (modus tollens) rather than direct proof (modus ponens).

We are now ready to apply the technique described above to prove the main result.

Theorem Let $$V$$ be a vector space over $$\mathbf{F}$$ and $$T : V \to V$$ a linear operator. Suppose $$v_1, v_2, \ldots, v_m$$ are eigenvectors with corresponding eigenvalues $$\lambda_1, \lambda_2, \ldots, \lambda_m$$ where $$\lambda_i \neq \lambda_j$$ for all $$i \neq j$$. Then the set
$S = \{v_1, v_2, \ldots, v_m\}$
is linearly independent.

Proof Suppose to the contrary that $$S$$ is linearly dependent. That is, there exist $$a_1, a_2, \ldots, a_m \in \mathbf{F}$$, not all zero, such that
$\sum_{i = 1}^m a_i v_i = 0.$
Let $$k$$ be the smallest natural number such that there exist $$k$$ indices $$I = \{i_1, i_2, \ldots, i_k\}$$ and coefficients $$a_{i_1}, a_{i_2}, \ldots, a_{i_k} \neq 0$$ satisfying
$\sum_{j = 1}^k a_{i_j} v_{i_j} = 0.$
Such a minimal $$k$$ exists by the well-ordering principle. Since the $$v_i$$ correspond to distinct eigenvalues, we have
$(T – \lambda_i I) v_i = 0$
while
$(T – \lambda_i I) v_j \neq 0 \text{ for } i \neq j.$
Therefore,
$(T – \lambda_{i_1} I) \sum_{j = 1}^k a_{i_j} v_{i_j} = \sum_{j = 2}^k b_{i_j} v_{i_j} = 0$
where $$b_{i_j} = a_{i_j}(\lambda_{i_1} – \lambda_{i_j})$$. In particular, $$I’ = \{i_2, i_3, \ldots, i_k\}$$ is a set of $$k-1$$ nonzero coefficients whose corresponding linear combination of the $$v_i$$s is zero. This contradicts the minimality of $$k$$. Therefore, no nontrivial linear combination of the vectors in $$S$$ can be zero, so $$S$$ is linearly independent.∎