Theorem: Let $A$ be an $n \times n$ matrix. If $\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_k$ are eigenvectors corresponding to distinct eigenvalues $\lambda_1, \lambda_2, \ldots, \lambda_k$, then $\{\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_k\}$ is linearly independent.

Proof: We use proof by induction on $k$.

Base case ($k = 1$): A single eigenvector $\mathbf{v}_1$ is nonzero by definition, hence linearly independent.

Inductive step: Assume the result holds for $k-1$ eigenvectors. We prove it for $k$ eigenvectors.

Suppose for contradiction that $\{\mathbf{v}_1, \ldots, \mathbf{v}_k\}$ is linearly dependent. Then there exist scalars $c_1, \ldots, c_k$, not all zero, such that: $c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + \cdots + c_k\mathbf{v}_k = \mathbf{0} \quad \text{...(1)}$

Since not all $c_i$ are zero, we can assume without loss of generality that $c_k \neq 0$ (by reordering if necessary).

Step 1: Apply matrix $A$ to equation (1): $A(c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + \cdots + c_k\mathbf{v}_k) = A(\mathbf{0}) = \mathbf{0}$

By linearity: $c_1A\mathbf{v}_1 + c_2A\mathbf{v}_2 + \cdots + c_kA\mathbf{v}_k = \mathbf{0}$

Since $A\mathbf{v}_i = \lambda_i\mathbf{v}_i$ for each $i$: $c_1\lambda_1\mathbf{v}_1 + c_2\lambda_2\mathbf{v}_2 + \cdots + c_k\lambda_k\mathbf{v}_k = \mathbf{0} \quad \text{...(2)}$

Step 2: Multiply equation (1) by $\lambda_k$: $c_1\lambda_k\mathbf{v}_1 + c_2\lambda_k\mathbf{v}_2 + \cdots + c_k\lambda_k\mathbf{v}_k = \mathbf{0} \quad \text{...(3)}$

Step 3: Subtract equation (3) from equation (2): $c_1(\lambda_1 - \lambda_k)\mathbf{v}_1 + c_2(\lambda_2 - \lambda_k)\mathbf{v}_2 + \cdots + c_{k-1}(\lambda_{k-1} - \lambda_k)\mathbf{v}_{k-1} = \mathbf{0}$

Note that the term involving $\mathbf{v}_k$ cancels: $c_k(\lambda_k - \lambda_k)\mathbf{v}_k = \mathbf{0}$.

Step 4: Apply the inductive hypothesis. By assumption, $\{\mathbf{v}_1, \ldots, \mathbf{v}_{k-1}\}$ is linearly independent (since these correspond to distinct eigenvalues $\lambda_1, \ldots, \lambda_{k-1}$).

Therefore, all coefficients in the above equation must be zero: $c_i(\lambda_i - \lambda_k) = 0 \quad \text{for } i = 1, 2, \ldots, k-1$

Step 5: Reach a contradiction. Since the eigenvalues are distinct, $\lambda_i \neq \lambda_k$ for $i < k$, so $\lambda_i - \lambda_k \neq 0$ for all $i = 1, \ldots, k-1$.

Therefore: $c_1 = c_2 = \cdots = c_{k-1} = 0$

Substituting back into equation (1): $c_k\mathbf{v}_k = \mathbf{0}$

Since $\mathbf{v}_k$ is an eigenvector, $\mathbf{v}_k \neq \mathbf{0}$. Therefore $c_k = 0$.

But this contradicts our assumption that not all $c_i$ are zero.

Conclusion: The assumption that $\{\mathbf{v}_1, \ldots, \mathbf{v}_k\}$ is linearly dependent leads to a contradiction. Therefore, the eigenvectors are linearly independent. ∎