Bases and Dependence

Here are some general facts that we will use.




  1. Homogeneous equations with more unknowns than equations always have a non-trivial (not all zero) solution.

    The reason is that the matix of coefficients will have more columns (unknowns or variables) than rows (equations). There can be only one leading or pivot variable per row, so there must be at least one variable which is not a pivot variable --- i.e. there must be a free variable. Since this variable can be set to anything, there is a solution which is not all zeros.

  2. If the first $k$ columns of a matrix are linearly independent, then its row-reduced echelon form (rref) looks like:

    MATH

    To see this, let $\QTR{bf}{V}$ be the matrix of just the first $k$ columns (so it is $n\times k$), and let $\QTR{bf}{R}$ be its row-reduced form. Then the equations MATH and MATH have the same solutions (because row-ops are reversible). Since the columns of $\QTR{bf}{V}$ are independent, there is only one solution: $\QTR{bf}{C=0}$. But a row-reduced matrix with only one solution must have every variable a pivot variable; i.e. there must be exactly $k$ pivots, one in each row. Thus, each of the first $k$ rows must be a pivot row, and so the "top" part of $\QTR{bf}{R}$ must be the $k\times k$ identity. Since every column of $\QTR{bf}{R}$ is a pivot column, all the remaining "bottom" rows must be zero. Returning to the original matrix, this gives the left-hand side of the diagram above. Since we know nothing about the other column, that might be anything.

  3. Suppose that MATH are independent vectors (written as columns), and suppose $\QTR{bf}{w}\in $ SpanMATH. Then the augmented matrix MATH row reduces to a matrix that looks like MATH

    Here's why. Since $\QTR{bf}{w}\in $ SpanMATH, there is a solution to the $k$ equations in $k$ unknowns: MATH. The row-reduced matrix gives these solutions. From part 2 above, we know the first $k$ columns must look like the $k\times k$ identity with zeros rows below. If there were any non-zero number $r$ in the lower right column we would get the contradiction MATH.




We now state our main result.

Theorem Suppose MATH are linearly independent and MATH lie in Span(MATH); then $w_{1}$, ...$,w_{k+1}$ are linearly dependent.



Proof

Let $\QTR{bf}{A}$ be the matrix whose columns are the $2k+1$ vectors MATH:MATHWe row-reduce $\QTR{bf}{A}$ to get the row-reduced matrix $\QTR{bf}{R}$, and we claim that $\QTR{bf}{R}$ looks like:

MATHThis follows directly from part 3 above, applied to each of the vectors MATH, since each is in SpanMATH. Now we note the key fact: the matrix $\QTR{bf}{J}$ in the upper right corner has $k+1$ columns (one for each of the $\QTR{bf}{w}_{i}$) and only $k$ rows. By part 1 above, we can find a (column) vector $\QTR{bf}{C}$ with entries MATH such that MATH, and $\QTR{bf}{C}$ is not all zeros. ($\QTR{bf}{C}$ gives a non-trivial dependence among the columns of $\QTR{bf}{J}$.)

We now form a $k+(k+1)$ component column vector MATH from $\QTR{bf}{C}$ by adding $k$ 0's to the beginning of $\QTR{bf}{C}$.

MATHWe first note that MATH. This is because the first $k$ entries of MATH are all zeros, so they multiply the first $k$ column vectors of $\QTR{bf}{R}$ into $\QTR{bf}{0}$. The entries $c_{1}$ through $c_{k+1}$ combine the upper, or "$\QTR{bf}{J}$" part, of the last $k+1$ columns of $\QTR{bf}{R}$ into $\QTR{bf}{0}$, and the remaining --- lower --- part of the columns is already zero; thus, MATH. However, as already noted above, a matrix $\QTR{bf}{A}$ and the matrix obtained from any row operations, say $\QTR{bf}{R}$, always have the same solutions. So we conclude that MATH as well. This gives a non-trivial dependence among the columns of $\QTR{bf}{A}$. But the first $k$ entries of MATH are zero, so this non-trivial dependence doesn't involve the first $k$ columns of $\QTR{bf}{A}$, which are the vectors MATH. Thus MATH gives us a non-trivial dependence relation among the last $k+1$ column vectors of $\QTR{bf}{A}$, which are the vectors MATH. This completes the proof.



Corollary Suppose MATH are linearly independent and MATH are also linearly independent and lie in Span(MATH); then $n\leq k$.



Proof

If $n>k$ then the Theorem says that the $w$'s would be dependent.



Corollary Any two bases for a vector space have the same number of elements.



Proof

If MATH and MATH are both bases, then each set of vectors is linearly independent and lies in the span of the other. By the previous corollary, $k\leq n$ and $n\leq k$; thus $k=n$.