# Prove without induction: Eigenvectors with distinct eigenvalues are linearly independent

Prove that if $$\{b_n\}$$ are eigenvectors with distinct eigenvalues $$\{\lambda_n\}$$, then $$\{b_n\}$$ are linearly independent.

Note: Proofs for this are available on this site and elsewhere. My question is to verify my proof below, which, at least to me, is simpler.

Lemma: If $$B$$ is a finite set of linear independent vectors, there is at most one linear combination of $$B$$ equal to a given vector $$v$$.

Proof: Consider a finite set $$\{b_n\}$$ of linearly independent vectors. Assume $$\sum_n c_nb_n = v$$ and $$\sum_n c'_nb_n = v$$, with at least one $$c_n \neq c'_n$$. Then $$\sum_n (c_n - c'_n)b_n = v - v = 0$$, which is impossible since $$\{b_n\}$$ is linearly independent.

Main Proof: Let $$\{b_n\}$$ be linearly independent eigenvectors of matrix $$A$$ with distinct eigenvalues $$\{\lambda_n\}$$. Let $$d$$ be a distinct eigenvector of $$A$$ with eigenvalue $$\delta \notin \{\lambda_n\}$$. We claim that $$d$$ is linearly independent of $$\{b_n\}$$.

Assume $$d$$ is not linearly independent of $$\{b_n\}$$. Then there exists $$\{c_n\}$$ such that $$\sum_n c_nb_n = d$$. Consequently, $$Ad = \sum_n \lambda_n c_n b_n$$. But $$Ad = \delta d = \sum_n \delta c_n b_n$$. This would give two different linear combinations of $$\{b_n\}$$ that yield $$Ad$$, violating the lemma. Hence, $$d$$ must be linearly independent of $$\{b_n\}$$.

Questions: Is this proof correct, rigorous, and well written? How can it be improved?

As far as I can tell, this proof does not use induction. Is that correct?

## Update

Thank you the responders. I believe I need to add the following step, which indeed uses induction. Can you please verify that with this step, the proof is correct?

Let $$B_0$$ be the empty set, and for all $$n \in \mathbb N$$, let $$B_n = B_{n-1} \cup \{b_n\}$$. If $$B_n$$ is a set (possibly empty) of linearly independent eigenvectors with distinct eigenvalues, $$B_{n+1}$$ must also be, as proven above. $$B_0$$ is such a set, and so therefore $$B_n$$ is such for all $$n$$. This completes the proof.

• Are you sure this isn't a proof without induction? That sure looks like an inductive step. Mar 17 at 19:37
• @eyeballfrog - Yes, I'd say they had done the inductive step, and left out the base case, and the words "the proof is by induction". I also think that the subtle distinction between "one vector is lin indep from a set of vectors" and "a lin indep set of vectors" makes it harder to see in this case. Mar 17 at 20:05
• Thanks! Can you please review the fix. Mar 17 at 20:12
• You are missing at least one step: from $\sum \lambda_n c_nb_n = \sum \delta c_nb_n$, you should conclude that $\lambda_n c_n=\delta c_n$ for all $n$. From the fact that $d$ is an eigenvector, and therefore not equal to zero, you know that at least on $c_i$ is nonzero. Then $\lambda_i c_i = \delta c_i$, and now you can cancel the $c_i$ to conclude that $\lambda_i=\delta$, contradicting the assumption that $\delta$ was distinct from all $\lambda_i$. Mar 17 at 20:31
• There is a theorem (proven by induction) that says that if $b_1,\ldots,b_n$ is a list of vectors, then it is linearly dependent if and only if there exists a $j$, $1\leq j\leq n$, such that $b_1,\ldots,b_{j-1}$ is linearly independent, and $b_j\in\mathrm{span}(b_1,\ldots,b_{j-1})$ You can then start with a list $b_1,\ldots,b_n$ of eigenvectors of pairwise distinct eigenvalues; if they are linearly independent, you are done. If not, then $n\gt 1$, and there pick $b_j$ as above and do your argument (with the added step). But this uses induction hidden in the minimality of $j$. Mar 17 at 20:34