## Linear Algebra and Its Applications, Exercise 2.3.5

Exercise 2.3.5. If we test vectors by independence by putting them into the rows of a matrix (rather than the columns), how can we determine whether or not the rows are independent using the elimination process? Determine the independence of the vectors in exercise 2.3.1 using this method.

Answer: My goal in this post is to (as much as possible) answer the question using the material introduced in section 2.3 and prior sections of the book. The material in section 2.4, in particular regarding the relationship of the row space to the column space, can simplify the answer, or at least make it more rigorous.

Assume that we have a set of $m$ vectors, each of which has $n$ elements; the vectors are therefore contained in the vector space $\mathbf{R}^n$. We create an $m$ by $n$ matrix  with the rows being the vectors in question.

The first thing to note is that if $m > n$ then the row vectors must be linearly dependent, since we cannot have more than $n$ linearly independent vectors in $\mathbf{R}^n$ (see page 88).

The next thing to note is that if any of the rows of the matrix is initially zero then again the row vectors must be linearly dependent, since we can multiply that row by a nonzero weight and all other rows by zero to produce a nontrivial linear combination of the rows that is equal to the zero vector.

If the number of rows $m \le n$ and none of the initial rows is zero then we proceed to perform Gaussian elimination on the matrix. We can assume that we do not need to do row exchanges during elimination, since exchanging rows does not affect whether or not the row vectors are linearly independent, and if row exchanges are indeed required then they can be done prior to elimination, i.e., by multiplying by a permutation matrix.

Suppose at some point in the elimination process a row of all zero values is produced. Since the multipliers in Gaussian elimination are nonzero, the zero row is a linear combination of the original row vectors in which at least one of the weights is nonzero. (For example, if the first entry in the original row vector were nonzero then the first row would be included in the linear combination with weight equal to the negative of the multiplier used to produce a zero in the first position of the row.) Again we have a nontrivial linear combination of rows equaling the zero vector, and thus the rows are linearly dependent.

On the other hand, suppose elimination completes and produces an echelon matrix with no zero rows, i.e., every row has a pivot. The row vectors in this matrix are then linearly independent, as we can see by looking at the pivots:

Start with the pivot in the the first row of the echelon matrix. Since this value is a pivot there are zeros below it, and since this is the first row the pivot is the only nonzero value in this column for any of the rows. Any linear combination of the row vectors that equals zero must therefore multiply the first row by zero. Similarly the pivot in the second row has zeros below it, and since the first row was multiplied by zero it is now the only nonzero value that can contribute to the linear combination. For a linear combination of the rows to equal zero we must therefore also multiply the second row by zero.

Since every row of the echelon matrix has a pivot, looking at each row in turn we can see that for a linear combination of the rows to equal zero we must multiply each row of the echelon matrix by zero. This implies that the rows of the echelon matrix are linearly independent.

What about the rows of the original matrix? If the rows of the echelon matrix are independent were the original rows independent as well? The answer is yes, as can be seen by looking at the spaces spanned by the rows in each case:

The initial set of row vectors spans a vector space; since each row vector has $n$ elements this vector space is a subspace of $\mathbf{R}^n$ or (in some cases) is $\mathbf{R}^n$ itself. If the initial set of row vectors is linearly independent then they are a basis for the space; otherwise (i.e., if the initial set of row vectors in linearly dependent) the basis for the space is a smaller set, with some of the row vectors being linear combinations of the others, and hence not part of the basis.

Performing Gaussian elimination on the matrix takes the initial set of row vectors and at each step replaces one row with a linear combination of that row and another row. More specifically, a given elimination step takes a row vector $r_i$ and replaces it with a new row vector $r'_i = r_i - l_{ij}r_j$ where $j < i$ and $l_{ij}$ is the multiplier used for that step.

Although each elimination step produces a new set of row vectors (since one row is replaced with a new one as described above) that new set spans the exact same space as the original row. To see this, suppose $v$ is a vector in the space spanned by $r_1$ through $r_m$ so that $v$ can be expressed as a linear combination of the row vectors:

$v = c_1r_1 + \cdots + c_jr_j + \cdots + c_ir_i + \cdots + c_nr_n$

Now suppose we replace $r_i$ with a new row vector $r'_i = r_i - l_{ij}r_j$ in a given elimination step. We can then form the linear combination

$c_1r_1 + \cdots + (c_j + c_il_{ij})r_j + \cdots + c_ir'_i + \cdots + c_nr_n$

$= c_1r_1 + \cdots + c_jr_j + c_il_{ij}r_j + \cdots + c_i(r_i - l_{ij}r_j) + \cdots + c_nr_n$

$= c_1r_1 + \cdots + c_jr_j + c_il_{ij}r_j + \cdots + c_ir_i - c_il_{ij}r_j) + \cdots + c_nr_n$

$= c_1r_1 + \cdots + c_jr_j + \cdots + c_ir_i + \cdots + c_nr_n = v$

Since $v$ can be expressed as a linear combination of the vectors $r_1, \dotsc, r'_i, \dotsc, r_n$ any vector in the space spanned by $r_1, \dotsc, r_i, \dotsc, r_n$ is also in the space spanned by $r_1, \dotsc, r'_i, \dotsc, r_n$.

Now consider a vector $v'$ in the space spanned by $r_1, \dotsc, r'_i, \dotsc, r_n$ so that we have

$v' = c'_1r_1 + \cdots + c'_jr_j + \cdots + c'_ir'_i + \cdots + c'_nr_n$

In reversing the elimination step we replace $r'_i$ with $r_i = r'_i + l_{ij}r_j$. We can then form the linear combination

$v' = c'_1r_1 + \cdots + (c'_j - c'_il_{ij})r_j + \cdots + c'_ir_i + \cdots + c'_nr_n$

$= c'_1r_1 + \cdots + c'_jr_j - c'_il_{ij}r_j + \cdots + c'_i(r'_i + l_{ij}r_j) + \cdots + c'_nr_n$

$= c'_1r_1 + \cdots + c'_jr_j - c'_il_{ij}r_j + \cdots + c'_ir'_i + c'_il_{ij}r_j + \cdots + c'_nr_n$

$= c'_1r_1 + \cdots + c'_jr_j + \cdots + c'_ir'_i + \cdots + c'_nr_n = v'$

Since $v'$ can be expressed as a linear combination of the vectors $r_1, \dotsc, r_i, \dotsc, r_n$  any vector in the space spanned by $r_1, \dotsc, r'_i, \dotsc, r_n$ is also in the space spanned by $r_1, \dotsc, r_i, \dotsc, r_n$.

Combined with the previous result we thus conclude that each elimination step does not change the space spanned by the row vectors. The space spanned by the initial set of row vectors is thus exactly the same as the space spanned by the row vectors of the echelon matrix produced by elimination.

If the $m$ rows of the echelon matrix are linearly independent (as discussed above) then they form a basis for the space they span. But the initial row vectors span the exact same space, and there are $m$ such vectors. If that set of vectors were linearly dependent then we could find a larger set of $p$ vectors (with $p > m$) that would be a basis for the space. But since any basis must have the same number of vectors, and the set of $m$ rows of the echelon matrix is a basis, we must have $p = m$, a contradiction.

We conclude that if the set of $m$ rows of the echelon matrix is a basis for the space it spans then the initial set of row vectors is also a basis for the same space and is thus linearly independent.

We now apply the above discussion to the vectors of exercise 2.3.1:

$v_1 = \begin{bmatrix} 1 \\ 1 \\ 0 \\ 0 \end{bmatrix} \qquad v_2 = \begin{bmatrix} 1 \\ 0 \\ 1 \\ 0 \end{bmatrix} \qquad v_3 = \begin{bmatrix} 0 \\ 0 \\ 1 \\ 1 \end{bmatrix} \qquad v_4 = \begin{bmatrix} 0 \\ 1 \\ 0 \\ 1 \end{bmatrix}$

We form a matrix containing as rows the vectors above, and then perform Gaussian elimination on this matrix:

$\begin{bmatrix} 1&1&0&0 \\ 1&0&1&0 \\ 0&0&1&1 \\ 0&1&0&1 \end{bmatrix} \Rightarrow \begin{bmatrix} 1&1&0&0 \\ 0&-1&1&0 \\ 0&0&1&1 \\ 0&1&0&1 \end{bmatrix}$

$\Rightarrow \begin{bmatrix} 1&1&0&0 \\ 0&-1&1&0 \\ 0&0&1&1 \\ 0&0&1&1 \end{bmatrix} \Rightarrow \begin{bmatrix} 1&1&0&0 \\ 0&-1&1&0 \\ 0&0&1&1 \\ 0&0&0&0 \end{bmatrix}$

Since the echelon matrix produced by elimination has a row of zeros its row vectors are linearly dependent, and thus the initial set of row vectors is linearly dependent as well.

NOTE: This continues a series of posts containing worked out exercises from the (out of print) book Linear Algebra and Its Applications, Third Edition by Gilbert Strang.

If you find these posts useful I encourage you to also check out the more current Linear Algebra and Its Applications, Fourth Edition, Dr Strang’s introductory textbook Introduction to Linear Algebra, Fourth Edition and the accompanying free online course, and Dr Strang’s other books.

This entry was posted in linear algebra. Bookmark the permalink.