If you find any mistakes, please make a comment! Thank you.

## Solution to Linear Algebra Done Wrong Exercise 1.2.5

Let a system of vectors ${\bf v}_1$, ${\bf v}_2$, $\cdots$, ${\bf v}_r$ be linearly independent but not generating. Show that it is possible to find a vector ${\bf v}_{r+1}$ such that the system ${\bf v}_1$, ${\bf v}_2$, $\cdots$, ${\bf v}_r$, ${\bf v}_{r+1}$ is linearly independent. Hint: Take for ${\bf v}_{r+1}$ any vector that cannot be represented as a linear combination $\sum_{k=1}\alpha_k{\bf v}_{k}$ and show that the system ${\bf v}_1$, ${\bf v}_2$, $\cdots$, ${\bf v}_r$, ${\bf v}_{r+1}$ is linearly independent.

Solution: Since the system of vectors ${\bf v}_1$, ${\bf v}_2$, $\cdots$, ${\bf v}_r$ is not generating, there must exist a vector ${\bf v}_{r+1}$ that cannot be represented as a linear combination $\sum_{k=1}\alpha_k{\bf v}_{k}$. We are going to show that the system ${\bf v}_1$, ${\bf v}_2$, $\cdots$, ${\bf v}_r$, ${\bf v}_{r+1}$ is linearly independent.

Suppose the system ${\bf v}_1$, ${\bf v}_2$, $\cdots$, ${\bf v}_r$, ${\bf v}_{r+1}$ is linearly dependent,  we argue it by contradiction. Then there exist scalars $a_1,\cdots,a_{r+1}$ (not all zero) such that $$\label{1.2.5.1}a_1{\bf v}_1+\cdots+a_{r+1}{\bf v}_{r+1}={\bf 0}.$$If $a_{r+1}=0$, then we have $a_1{\bf v}_1+\cdots+a_{r}{\bf v}_{r}={\bf 0}.$Because the system  of vectors ${\bf v}_1$, ${\bf v}_2$, $\cdots$, ${\bf v}_r$ is linearly independent, we must have $$a_1=\cdots=a_{r}=0.$$This contradicts that not all of $a_1,\cdots,a_{r+1}$ are zero. Therefore, we have $a_{r+1}\ne 0$.

From \eqref{1.2.5.1}, we then have$a_{r+1}{\bf v}_{r+1}=-a_1{\bf v}_1-\cdots-a_{r}{\bf v}_{r}.$Dividing both sides by $a_{r+1}$ (we proved that $a_{r+1}\ne 0$), we obtain${\bf v}_{r+1}=-\frac{a_1}{a_{r+1}}{\bf v}_1-\cdots-\frac{a_r}{a_{r+1}}{\bf v}_{r},$which implies that ${\bf v}_{r+1}$ is a linear combination $\sum_{k=1}\alpha_k{\bf v}_{k}$ (namely $\alpha_k=-a_k/a_{r+1}$). This contradicts the choice of ${\bf v}_{r+1}$. Hence the system ${\bf v}_1$, ${\bf v}_2$, $\cdots$, ${\bf v}_r$, ${\bf v}_{r+1}$ is linearly independent.