Module 6: Theory, Part I

Next, let's look at an important idea: rank

• Suppose we have the following vectors $${\bf v}_1 \eql \vecfour{1}{-1}{0}{0} \;\;\;\;\;\;\;\;\; {\bf v}_2 \eql \vecfour{1}{0}{1}{0} \;\;\;\;\;\;\;\;\; {\bf v}_3 \eql \vecfour{1}{1}{2}{0} \;\;\;\;\;\;\;\;\; {\bf v}_4 \eql \vecfour{0}{1}{1}{0} \;\;\;\;\;\;\;\;\; {\bf v}_5 \eql \vecfour{3}{-1}{2}{0}$$

• Consider ${\bf v}_2$ and ${\bf v}_4$. Then, it's easy to see that
  • ${\bf v}_2$ and ${\bf v}_4$ are independent.
  • ${\bf v}_1 = {\bf v}_2 - {\bf v}_4$
  • ${\bf v}_3 = {\bf v}_2 + {\bf v}_4$
  • ${\bf v}_5 = 3{\bf v}_2 - {\bf v}_4$
  This suggests that we need at least two of these vectors to express the others.

• Similarly, it's easy to show that
  • ${\bf v}_1$ and ${\bf v}_2$ are independent.
  • ${\bf v}_3 = -{\bf v}_1 + 2{\bf v}_2$
  • ${\bf v}_4 = -{\bf v}_1 + {\bf v}_2$
  • ${\bf v}_5 = {\bf v}_1 + 2{\bf v}_2$

  In-Class Exercise 7: Show that the above is true given what was shown earlier for ${\bf v}_2$ and ${\bf v}_4$.

• More such tedious calculations with these vectors reveal that the largest independent subset possible from the vectors above is of size 2.
  • No subset of size 1 is enough to express the others.
  • Any subset of size 3 or larger will have dependence.

• Now, any subset of a linearly independent collection is linearly independent.

  In-Class Exercise 8: Prove the following: if the vectors ${\bf v}_1, {\bf v}_2, \ldots, {\bf v}_n$ are independent, then so is any subset of these vectors.

• Thus, for any general collection of vectors, what we need to do is identify the largest subset that's independent.

• In some ways this characterizes the amount of independence present in a collection.

• Definition: The rank of a collection of vectors is the size of the largest subset of independent vectors.

And now for two remarkable results:

• Suppose that ${\bf v}_1, {\bf v}_2, \ldots, {\bf v}_n$ is a collection of vectors and ${\bf A}$ is a matrix that has these vectors as columns.

• Proposition 6.3:. If columns $i_1,i_2, \ldots, i_k$ are the pivot columns of $RREF({\bf A})$, then ${\bf v}_{i_1}, {\bf v}_{i_2}, \ldots, {\bf v}_{i_k}$ are independent vectors amongst the set.

• Proposition 6.4: The rank of the collection ${\bf v}_1, {\bf v}_2, \ldots, {\bf v}_n$ is the number of pivot columns of $RREF({\bf A})$.

• The statements are a bit complicated, with double subscripts, so let's understand what they're saying through an example:
  • Consider the vectors $${\bf v}_1 \eql \vecfour{1}{-1}{0}{0} \;\;\;\;\;\;\;\;\; {\bf v}_2 \eql \vecfour{1}{0}{1}{0} \;\;\;\;\;\;\;\;\; {\bf v}_3 \eql \vecfour{1}{1}{2}{0} \;\;\;\;\;\;\;\;\; {\bf v}_4 \eql \vecfour{0}{1}{1}{0} \;\;\;\;\;\;\;\;\; {\bf v}_5 \eql \vecfour{3}{-1}{2}{0}$$
  • Let's put them in a matrix as columns: $$\mat{1 & 1 & 1 & 0 & 3\\ -1 & 0 & 1 & 1 & -1\\ 0 & 1 & 2 & 1 & 2\\ 0 & 0 & 0 & 0 & 0}$$
  • The RREF turns out to be: $$\mat{{\bf 1} & 0 & -1 & -1 & 1\\ 0 & {\bf 1} & 2 & 1 & 2\\ 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0}$$
  • Then, ${\bf v}_1, {\bf v}_2$ are a linearly independent subset, from Proposition 6.3.
  • Note: ${\bf v}_1, {\bf v}_2$ are not columns of the RREF: they are columns of ${\bf A}$.
  • Proposition 6.4 says that no other linearly independent subset is larger.
  • That is, the rank of the set is 2.

• We will prove 6.3 in two parts:
  • Part I: any vector corresponding to a non-pivot column can be expressed in terms of the vectors corresponding to the pivot columns, i.e., ${\bf v}_{i_1}, {\bf v}_{i_2}, \ldots, {\bf v}_{i_k}$
  • Part II: ${\bf v}_{i_1}, {\bf v}_{i_2}, \ldots, {\bf v}_{i_k}$ are linearly independent.

• Proposition 6.3:. If columns $i_1,i_2, \ldots, i_k$ are the pivot columns of $RREF({\bf A})$, where ${\bf A}$ is formed with vectors ${\bf v}_1, {\bf v}_2, \ldots, {\bf v}_n$ as a columns, then ${\bf v}_{i_1}, {\bf v}_{i_2}, \ldots, {\bf v}_{i_k}$ are independent vectors amongst the set.

• Proof of Part I: Suppose each vector has $m$ dimensions. Now consider the solution to ${\bf Ax}={\bf 0}$, where ${\bf A}$ has $m$ rows and $n$ columns. First, let's look at the case when ${\bf Ax}={\bf 0}$ has ${\bf x}={\bf 0}$ as the only solution:
  • In this case, all the columns are pivot columns.
  • And therefore ${\bf x}={\bf 0}$ is the only solution to $x_1{\bf v}_1 + x_2{\bf v}_2 + \ldots + x_n{\bf v}_n = {\bf 0}$, because this is just a restatement of ${\bf Ax}={\bf 0}$.
  • This means all of ${\bf v}_1, {\bf v}_2, \ldots, {\bf v}_n$ are independent, and the proposition is true.
  Now suppose ${\bf Ax}={\bf 0}$ has a solution ${\bf x}\neq {\bf 0}$:
  • In this case, the pivot columns $i_1,i_2, \ldots, i_k$ correspond to basic variables.
  • Now let $x_j$ be any free variable in the (non-zero) solution of ${\bf Ax}={\bf 0}$.
  • We'll write the solution as: $$x_1{\bf v}_1 + x_2{\bf v}_2 + \ldots + x_n{\bf v}_n = {\bf 0}$$ and express $$x_j{\bf v}_j = -x_1{\bf v}_1 - x_2{\bf v}_2 - \ldots - x_{j-1}{\bf v}_{j-1} - x_{j+1}{\bf v}_{j+1} - \ldots - x_n{\bf v}_n$$
  • Set $x_j=1$ and all the other free variables to $0$.
  • This results in $${\bf v}_j = -x_{i_1}{\bf v}_{i_1} - x_{i_2}{\bf v}_{i_2} - \ldots - x_{i_k}{\bf v}_{i_k}$$
  • That is, ${\bf v}_j$ is expressed as a linear combination of ${\bf v}_{i_1}, {\bf v}_{i_2}, \ldots, {\bf v}_{i_k}$.
  • In this way, any vector corresponding to a non-pivot column can be expressed in terms of ${\bf v}_{i_1}, {\bf v}_{i_2}, \ldots, {\bf v}_{i_k}$.

• Before proving Part II, let's see why it's needed at all:
  • We know that the pivot columns of the RREF are independent
          $\rhd$ You proved this earlier in Proposition 6.1.
  • But this doesn't mean that the original columns corresponding to these in ${\bf A}$ are independent.
  • Also, just because we expressed the other vectors in terms of these doesn't mean they (the columns of ${\bf A}$ corresponding to pivots) are independent.
  • That is, there could be dependence between them.

• The proof of Part II is a bit subtle.

• Let's first illustrate the idea through an example:
  • Suppose we have $n=5$ vectors, and that the first three columns while the next two are non-pivot columns.
  • Now consider ${\bf Ax} = {\bf 0}$. That is, $$x_1{\bf v}_1 + x_2{\bf v}_2 + x_3{\bf v}_3 + x_4{\bf v}_4 + x_5{\bf v}_5 = {\bf 0}$$
  • We're interested in the case ${\bf x}\neq{\bf 0}$ (because the case ${\bf x}={\bf 0}$ is covered above).
  • The first three in ${\bf x}=(x_1,x_2,x_3,x_4,x_5)$ are basic variables, whereas $x_4,x_5$ are free variables.
  • Suppose now that we set $x_4=x_5=0$. Does this imply that $x_1=x_2=x_3=0$? If it did, then it means that the solution to $$x_1{\bf v}_1 + x_2{\bf v}_2 + x_3{\bf v}_3 \eql {\bf 0}$$ is $x_1=x_2=x_3=0$, meaning they are independent. How do we argue that it it implies that $x_1=x_2=x_3=0$? Here's where the insight comes in.
  • Suppose we found a solution where $x_1\neq 0$. Then, ${\bf Ax}={\bf 0}$ has a nonzero solution with $x_4=x_5=0$.
  • Which means $RREF({\bf A}){\bf x}={\bf 0}$ has the same solution (with $x_1\neq 0$), which contradicts the fact that the RREF's pivot columns are independent.

• The last step in reasoning above was a bit complicated so let's illustrate that with our running example:
  • Suppose with free variables set to 0, there is a non-zero solution with $x_1 \neq 0$, then it would look like this: $$\mat{1 & 1 & 1 & 0 & 3\\ -1 & 0 & 1 & 1 & -1\\ 0 & 1 & 2 & 1 & 2\\ 0 & 0 & 0 & 0 & 0} \mat{x_1\neq 0\\ x_2 \\ x_3=0\\ x_4=0\\ x_5=0} \eql \mat{0\\ 0\\ 0\\ 0\\ 0}$$
  • But this would imply the same solution for the RREF (because the free variables are set to 0): $$\mat{{\bf 1} & 0 & -1 & -1 & 1\\ 0 & {\bf 1} & 2 & 1 & 2\\ 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0} \mat{x_1\neq 0\\ x_2 \\ x_3=0\\ x_4=0\\ x_5=0} \eql \mat{0\\ 0\\ 0\\ 0\\ 0}$$ But this is not possible, since the RREF's pivot columns are independent.

• Proof of Part II: Let's formalize the above argument (in steps):
  • Let $j_1, j_2, \ldots, j_{n-k}$ be the indices of the non-pivot columns. Thus, $x_{j_1},x_{j_2},x_{j_{n-k}}$ are free variables.
  • The indices $i_1, i_2, \ldots, i_k$ are the pivot columns and so $x_{i_1},x_{i_2},x_{i_k}$ are basic variables.
  • Let ${\bf x}$ be a vector where the free variables are set to zero and then consider ${\bf Ax}={\bf 0}$.
  • If there's a non-zero solution, this means there's some variable $x_{i_p}\neq 0$ amongst the basic variables.
  • Now for the key insight: this same solution must work for the equations $RREF({\bf A}){\bf x}={\bf 0}$ since row reductions do not change the set of solutions.
  • Thus, we will have found a linear combination of the RREF columns with one nonzero coefficient that equals the zero vector (remembering that the coefficients of the non-pivot columns are already zero by construction). But this is a contradiction since the RREF's pivot columns are independent.

• Phew!

• What about Proposition 6.4?
  • We can see that because ${\bf v}_{i_1}, {\bf v}_{i_2}, \ldots, {\bf v}_{i_k}$ are linearly independent, the rank of the collection ${\bf v}_{1}, {\bf v}_{2}, \ldots, {\bf v}_{n}$ is at least $k$.
  • But could it be larger than $k$?
  • That is, what if there is some subset other than ${\bf v}_{i_1}, {\bf v}_{i_2}, \ldots, {\bf v}_{i_k}$ that's independent and larger than $k$?
  • To make this more concrete: suppose the first three vectors correspond to the pivot columns, could it be that the next four vectors are independent amongst themselves even though each of those depend on the first three?

• Unfortunately, as it turns out, the proof is not that simple and will have to await a more dramatic result.