## Deciding linear independence and computing spans and linear dependencies in a vector space

Let $V$ be an $m$-dimensional vector space over a field $F$ having basis $E = \{e_i\}_{i=1}^m$ and let $\{v_j\}_{j=1}^m$ be vectors in $V$. Let $A$ be the $m \times n$ matrix whose $j$th column is the coordinates of $v_j$ expressed in terms of the ordered basis $E$. Let $A^\prime$ be the reduced row echelon form of $A$.

1. Let $B$ be any matrix that is row equivalent to $A$, and let $\{w_j\}_{i=1}^n$ be the elements of $V$ whose coordinates (in terms of the ordered basis $E$) are the columns of $B$. Prove that if $\sum \alpha_i v_i = 0$, then $\sum \alpha_i w_i = 0$.
2. Prove that the vectors whose $E$-coordinates are the pivotal columns of $A^\prime$ are linearly independent, and that the vectors whose $E$-coordinates are given by the nonpivotal columns of $A^\prime$ are linearly dependent on these.
3. Prove that the vectors $\{v_i\}_{i=1}^n$ are linearly independent if and only if $A^\prime$ has $n$ nonzero rows.
4. By part (3), the vectors $\{v_i\}_{i=1}^n$ are linearly dependent if and only if $A^\prime$ has nonpivotal columns. In this case, compute all of the linear dependencies among the $v_i$.
5. Prove that the dimension of the subspace $W$ spanned by $\{v_i\}_{i=1}^n$ is the row rank of $A^\prime$. Prove also that the columns of $A$ corresponding to the pivotal columns of $A^\prime$ form a basis for $W$.

1. Say $A$ and $B$ are row equivalent via the invertible matrix $P$– that is, $PA = B$. Now $P[v_1 | \cdots | v_n] = [Pv_1 | \cdots | PV_n] = [w_1 | \cdots | w_n]$, so that $Pv_i = w_i$ for each $i$. Now if $\sum \alpha_i v_i = 0$, then $P(\sum \alpha_i v_i) = 0$, so that $\sum \alpha_i Pv_i = 0$, and thus $\sum \alpha_i w_i = 0$.
2. Note that the pivotal columns of $A^\prime$ are a subset of $E$, and thus are linearly independent. Moreover, any nonpivotal column has nonzero entries only in those rows containing a pivot; hence each of the nonpivotal columns of $A^\prime$ is linearly dependent on the pivot columns.
3. Suppose the $v_i$ are linearly independent. Then by part (1) the columns of $A^\prime$ are linearly independent. By part (2), all $n$ columns of $A^\prime$ are pivot columns, and so the column rank (hence row rank) of $A^\prime$ is $n$. Using this previous exercise, $A^\prime$ has $n$ nonzero rows.

Conversely, suppose $A^\prime$ has $n$ nonzero rows. Then the row rank (hence column rank) of $A^\prime$ is $n$, so that the columns of $A^\prime$ are linearly independent. By part (1), the columns of $A$ are linearly independent.

4. Using part (1), it suffices to find the linear dependencies among the columns of $A^\prime$. To that end, let $u_i$ be the columns of $A^\prime$ (in order) and suppose $\sum \beta_i u_i = 0$. Letting $B = [\beta_1 | \cdots | \beta_n]^\mathsf{T}$, we have $A^\prime B = 0$. We computed the solutions $B$ of this matrix equation here; in particular, we may choose the $\beta_i$ corresponding to nonpivotal columns of $A^\prime$ arbitrarily, and the $\beta_i$ corresponding to pivotal columns are then determined uniquely. Every such solution $B$ then gives a linear dependence among the columns of $A$.
5. Because the matrix $P$ carrying $A$ to $A^\prime$ is invertible, the span of the $v_i$ is the preimage of the span of the $u_i$, and the preimage of a basis is a basis. In (2) we saw that the pivotal columns of $A^\prime$ are a maximal linearly independent set of columns of $A^\prime$, and thus form a basis of the column space of $A^\prime$. Hence the columns of $A$ corresponding to pivotal columns of $A^\prime$ form a basis of the column space of $A$. In particular, the dimension of this subspace is the row rank (i.e. number of nonzero rows) of $A^\prime$.