# This algorithm will find a basis for the span of some vectors. How/why does it work?

Say I want to find a basis for $span((1,2,5),(2,4,10),(-3,-5,-13),(2,1,4),(-4,-6,-16))$. Google tells me that to get the answer, I'm supposed to write down the vectors as columns of a matrix:

$$\begin{pmatrix} 1 & 2 & -3 & 2 & -4 \\ 2 & 4 & -5 & 1 & -6 \\ 5 & 10 & -13 & 4 & -16 \\ \end{pmatrix}$$

... then bring said matrix to row echelon form...

$$\begin{pmatrix} 1 & 2 & 0 & -7 & 2 \\ 0 & 0 & 1 & -3 & 2 \\ 0 & 0 & 0 & 0 & 0 \\ \end{pmatrix}$$

... then look at the pivots; in this case the first and third rows contain pivots, therefore the first and third columns of the original matrix are linearly independent while the others are linearly dependent, and therefore those two vectors are a basis of the span.

Okay, that's simple enough to remember and use in the exam but it still feels like magic to me. How does this work? Why do the pivots show which vectors are linearly independent?

• Short answer: Row operations do not change linear relations between columns. Or maybe it's just a shorter way of phrasing your question: "Why do row operations not change linear relations between columns?" Mar 22, 2017 at 18:22
• That's a good way of simplifying the question, yes. I suspect "how are the row spaces of the two matrices related?" is another very closely related question too. Mar 22, 2017 at 20:27
• This method picks out a subset of the vectors that forms a basis, which can be useful, but this is basically a side-effect of computing the null space (kernel) of this matrix. You generally get a more “useful” basis by column reducing the matrix instead. The non-zero columns of the result form a basis. To compare, the row-reduction process gives as a basis $(1,2,5)^T$ and $(-3,-5,-13)^T$, while column-reduction produces $(1,0,1)^T$ and $(0,1,2)^T$ instead. It’s also less sensitive to the order in which you list the vectors.
– amd
Mar 22, 2017 at 23:38

Combine this with the fact that the row rank and column rank (that is, the dimensions of the row and column spaces) of a matrix are equal, and one can see how this method works: In row-reduced echelon form, each pivot column has a $$1$$ in a different row from other pivot columns and zeros elsewhere, so the set of pivot columns are obviously linearly independent. Since elementary row operations don’t affect linear dependency of columns, the corresponding columns of the original matrix are also linearly independent. There are as many pivots as the rank of the matrix, which is equal to the dimension of the column space, so this set of vectors forms a basis for the column space, i.e., a basis for your original set of vectors.