# Finding the basis of $\mathbb{R}^n$ given a set of non-spanning, linearly independent vectors

Let $$S = \{ v_1, \dotsc, v_k \}$$ be a set of non-spanning, linearly independent vectors in $$\mathbb{R}^n$$. From my lecture in LA, the instructor said that we can form a basis with $$S$$ given that we solve for the row-echelon form of $$[v_1 \dotsc v_k \ e_1 \dotsc e_n]$$ (where $$\{ e_1, \dotsc, e_n \}$$ is the natural basis of $$\mathbb{R}^n$$), and the vector whose column in the $$\text{ref}([v_1 \dotsc v_k \ e_1 \dotsc e_n])$$ has a leading one, then its a member of the desired basis.

For example, to find the basis in $$\mathbb{R}^2$$ which includes the vector in $$S = \left\{ \begin{bmatrix} 1 \\ 5 \end{bmatrix} \right\}$$ (which is, by default, a linearly independent vector), we solve for the ref of S adjoint the natural basis of $$\mathbb{R}^2$$:

$$\begin{bmatrix} 1 & 0 & 1 \\ 5 & 1 & 0 \end{bmatrix} \sim \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & -5 \end{bmatrix} \ .$$

Since the first and second column of the ref had the leading one, then the first and second column of the initial matrix can form a basis which includes the vector $$[1 \ 5]^T$$, i.e. $$\left\{ \begin{bmatrix} 1 \\ 5 \end{bmatrix}, \begin{bmatrix} 0 \\ 1 \end{bmatrix} \right\}$$ is a basis of $$\mathbb{R}^2$$

Why is that?

This is because row operation does not change linear dependence relations between the columns. This is a consequence of the fact that row operations do not change the solution set of a system of linear equations.

You can actually get away with solving this problem and reducing a smaller matrix at the cost of having to reverse the row operations. You would do as follows:

1. Bring the matrix $$[v_1 \quad \cdots \quad v_k ]$$ to reduced row echelon form, keeping track of your operations. For each row missing a pivot, you add a column providing the missing pivot, until you have an invertible matrix $$[v_1 \quad \cdots \quad v_k \, u_{k+1} \quad \cdots \quad u_{n}]$$.

2. You reverse the row operations you did in step 1 on the matrix augmented with extra columns and the columns of the resultant matrix form a basis of $$\mathbb{R}^n$$ containing the original linearly independent, non-spanning set.

This question relates to the row-space and column-space of a matrix.

Theorem 2: Let $$B$$ be any matrix that is row equivalent to a matrix $$A$$, then row-space$$(A)=$$row-space$$(B)$$

Proof: This is mainly because row-equivalent matrices $$A\cong B$$ are attained by elementary row-operations, which implies that the rows of $$B$$ are linear combinations of the rows of $$A$$, and row$$(B)\subseteq$$row$$(A)$$. The reverse inclusion is had by noting that the same row operations used to get from $$A$$ to $$B$$ can be used in reverse from $$B$$ to get to $$A$$, thus the rows of $$A$$ are linear combinations of the rows of $$B$$, row$$(A)\subseteq$$row$$(B)$$.

Now comes the question of finding a basis for the row-space of a matrix $$A$$, well since row$$(A)=$$row$$($$rref$$(A))$$, we can look at the reduced row echelon form of $$A$$ to find a basis for row$$(A)$$.

It turns out that the if $$R$$ is a matrix in row echelon form, then a basis for row$$(R)$$ consists of the nonzero rows of $$R$$.

For example if

$$A=\begin{pmatrix} 1&1&3&1&6 \\ 2&-1&0&1&-1 \\-3&2&1&-2&1 \\ 4&1&6&1&3 \end{pmatrix}$$

then $$R=rref(A)=\begin{pmatrix}1&0&1&0&-1\\0&1&2&0&3\\0&0&0&1&4\\0&0&0&0&0 \end{pmatrix}$$

and a basis for row$$(A)$$ is $$\left\{\begin{bmatrix}1&0&1&0&-1\end{bmatrix}, \begin{bmatrix}0&1&2&0&3\end{bmatrix}, \begin{bmatrix}0&0&0&1&4\end{bmatrix} \right\}$$

What about the column-space of $$A$$? Recall that $$A\vec{x}$$ is a linear combination of the columns of $$A$$:

$$A_{3\times 3}\vec{x}=\begin{pmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\\a_{31}&a_{32}&a_{33}\end{pmatrix}\begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix}=x_1\begin{pmatrix} a_{11}\\a_{21}\\a_{31}\end{pmatrix}+x_2\begin{pmatrix}a_{12}\\a_{22}\\a_{32}\end{pmatrix}+ x_3\begin{pmatrix}a_{13}\\a_{23}\\a_{33}\end{pmatrix}$$

Since elementary row operations do not affect the nontrivial solution set of the dependence relation $$A\vec{x}=\vec{0}$$, the columns of $$A$$ have the same dependence relationships as the columns of $$R=$$ref$$(A)$$.

Given our matrix $$R$$ it is obvious that $$\vec{r_3}=\vec{r_1}+2\vec{r_2}$$ and $$\vec{r_5}=-\vec{r_1}+3\vec{r_2}+4\vec{r_4}$$ where $$\vec{r_1},...,\vec{r_5}$$ are the column vectors of $$R$$, you can also note that these same relationships hold amongst the column vectors of $$A$$.

For example: $$\begin{pmatrix}3\\0\\1\\6\end{pmatrix}=\begin{pmatrix}1\\2\\-3\\4\end{pmatrix}+2\cdot\begin{pmatrix}1\\-1\\2\\1\end{pmatrix}$$.

Thus the column vectors of $$A$$ that have a nontrivial dependence relation correspond to the non-leading-one column vectors of $$R$$. Therefore the linearly independent column vectors of $$A$$ correspond to the leading-one column vectors of $$R$$.

In your case you are given that $$\{v_1,...,v_k\}$$ is linearly independent, then $$\{v_1,...,v_k,e_1,...,e_n\}$$ has $$k+n$$ vectors but $$\mathbb{R}^n$$ has dimension $$n$$, thus there has to be a nontrivial dependence relationship amongst some of the vectors as we’re forming a basis for $$\mathbb{R}^n$$. In the RREF of your matrix you would have the first $$k$$ column vectors be leading-ones because the first $$k$$ vectors are linearly independent, the remaining columns would either display a nontrivial dependence relation, or not. Those that do are not necessary in the basis, therefore the basis would consist of all the vectors that correspond to the leading ones in the RREF of $$[v_1\;\;\;\;\;v_k\;e_1\;\;\;\;\;e_n]$$. Don’t believe me? The Fundamental Theorem of Invertible Matrices can help in this case. Note that if you eliminated all the columns of $$A$$ that didn’t correspond to leading-ones in the RREF of $$A$$, then you would have an $$n\times n$$ matrix $$A’$$ whose RREF is $$I_n$$, and therefore the column vectors of the new matrix $$A’$$ are linearly independent. Also note that your professor assures that you have $$n$$ leadings ones by placing all desired vectors he wants in the basis as the first $$k$$ columns and then adding a basis for $$\mathbb{R}^n$$ to the matrix, if the vectors $$e_1,...,e_n$$ would of been placed first then we would of gotten $$n$$ leading ones for the first $$n$$ columns(by definition of the standard basis) and would of been done before even starting.

Note that in your example $$\vec{r_3}=\begin{pmatrix}1\\0\end{pmatrix}=\vec{r_1}-5\vec{r_2}=\begin{pmatrix} 1\\5\end{pmatrix}-5\begin{pmatrix}0\\1\end{pmatrix}$$ thus every linear combination of $$\vec{r_1},\vec{r_2},\vec{r_3}$$ is really just a linear combination of $$\vec{r_1},\vec{r_2}$$, and $$\vec{r_1},\vec{r_2}$$ are not multiples of one another and thus must be linearly independent.

Most of this explanation was taken from Linear Algebra: A Modern Introduction by David Poole between pages(approximately) 180-200.