View source for Linear Dependence of Vectors

==Linear Independence and Dependence==
<blockquote style="background: white; border: 1px solid black; padding: 1em;"> 
:'''Definition:''' A set of vectors <math>V = \{ \mathbf{x_1}, \mathbf{x_2}, ..., \mathbf{x_n} \}</math> and the scalars <math>k_1, k_2, ..., k_n</math> has a solution for the vector equation <math>k_1\mathbf{x_1} + k_2\mathbf{x_2} + ... + k_n\mathbf{x_n} = 0</math>, namely when <math>k_1 = k_2 = ... = k_n = 0</math>. If this is the only solution to the vector equation, then the set <math>V</math> is said to be '''Linearly Independent'''. If there exists other solutions where not all <math>k_i = 0</math>, then <math>V</math> is said to be '''Linearly Dependent'''.
</blockquote>

We will now look at some examples of vector sets which are either linearly independent or linearly dependent.
<blockquote style="background: white; border: 1px solid black; padding: 1em;"> 
:'''Note:''' Another way to write that a set of vectors <math>\{v_1, v_2, ..., v_n \}</math> is linearly independent is by saying that <math>\mathrm{span} (v_1, v_2, ..., v_n) = \bigoplus_{i=1}^{n} \mathbb{F}v_i</math>, which says that any vector that is a linear combination of the set of vectors <math>v_1, v_2, ..., v_n</math> is a unique linear combination.
</blockquote>

===Example 1===
'''Determine whether or not the vector set <math>V = \{ (1, 2), (-5, -3) \}</math> is linearly independent or linearly dependent.'''
	
We first must see if there exists only one set of scalars <math>c_1 = c_2 = 0</math> (the trivial solution) as a solution to the vector equation <math>c_1(1, 2) + c_2(-5, -3) = 0</math> or if there exists more solutions.
	
From this vector equation we get the following system of linear equations:
<div style="text-align: center;"><math>\begin{align} c_1 - 5c_2 = 0 \\ 2c_1 -3c_2 = 0 \end{align}</math></div>
	
When we reduce this system to RREF, we get that:
<div style="text-align: center;"><math>\begin{align} c_1 + 0c_2 = 0 \\ 0c_1 + c_2 = 0 \end{align}</math></div>
	
Therefore our only set of scalars <math>c_1, c_2</math> are both equal to zero. Therefore, the vector set <math>V</math> is linearly independent.

===Example 2===
'''Determine whether the vector set <math>V = \{ (3, 6), (4, 8) \}</math> is a linearly independent or a linearly dependent set.'''

Once again, for <math>V</math> to be a linearly independent set then the vector equation <math>c_1(3, 6) + c_2(4, 8) = 0</math> must containing only one set of scalars <math>c_1 = c_2 = 0</math>. From our vector equation be obtain the following system of linear equations:
<div style="text-align: center;"><math>\begin{align} 3c_1 + 4c_2 = 0 \\ 6c_1 + 8c_2 = 0 \end{align}</math></div>

When we solve this system of equations we obtain that:
<div style="text-align: center;"><math>\begin{align} c_1 + \frac{4}{3}c_2 = 0 \\ 0c_1 + 0c_2 = 0 \end{align}</math></div>

Suppose that <math>c_2 = s</math> so that <math>c_1 = - \frac{4}{3} s</math>. We see that for any <math>s \in \mathbb{R}</math>, the scalars <math>c_1</math> and <math>c_2</math> satisfy the vector equation and thus there are infinitely many scalars sets. Therefore <math>V</math> is a linearly ''dependent'' set.

===Example 3===
'''Show that if <math>A</math> is an <math>n \times n</math> invertible matrix, then the column vectors of <math>A</math> denoted <math>C_1</math>, <math>C_2</math>, &#8230;, <math>C_n</math> are linearly independent.'''

Suppose that <math>A</math> is an invertible matrix and suppose that we have the linear system <math>Ax = 0</math>. We note that the only solution to this linear system is the trivial solution, namely <math>x = 0</math>. This system corresponds to the following vector equations though:
<div style="text-align: center;"><math> x_1C_1 + x_2C_2 + ... + x_nC_n = 0 </math></div>

And since <math>x = (x_1, x_2, ..., x_n) = (0, 0, ..., 0)</math>, we see that this vector equation only have the scalars <math>x_1 = x_2 = ... = x_n = 0</math>, so the column vectors of <math>A</math> are linearly independent.

===Example 4===
'''Consider the set of vectors <math>\{1, 1-x, 1-x^2 \}</math> from the vector space <math>\wp_2 (\mathbb{F})</math>. Determine if this set of vectors is linearly independent or linearly dependent.'''

When we expand the vector equation <math>a(1) + b(1 -x) + c(1 - x^2) = 0</math> as follows, notice:
<div style="text-align: center;"><math>\begin{align} a(1) + b(1 -x) + c(1 - x^2) = 0 \\ a + b - bx + c - cx^2 = 0 \\ (a + b + c) + (-b)x + (-c)x^2 = 0 \end{align}</math></div>

We can clearly see that this equation holds only if <math>a = b = c = 0</math>. We can also verify this with the following matrix:
<div style="text-align: center;"><math>\begin{align} A = \begin{bmatrix} 1 & 1 & 1\\ 0 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix} \end{align}</math></div>

Since this is an upper triangular matrix, its determinant is the product of the entries down the main diagonal and so <math>\mathrm{det} (A) = 1 \cdot (-1) \cdot (-1) = 1</math> which implies <math>A</math> is invertible, and so the homogenous system <math>\begin{bmatrix}1 & 1 & 1\\ 0 & -1 & 0\\ 0 & 0 & -1\end{bmatrix} \begin{bmatrix}a\\ b\\ c \end{bmatrix} = \begin{bmatrix}0\\ 0\\ 0 \end{bmatrix}</math> has only the trivial solution <math>a = b = c = 0</math>.

===Example 5===
'''Show that the set of vectors <math>\{ m, m - x, m - x^2 \}</math> from <math>\wp_2 (\mathbb{F})</math> is a linearly independent set for all nonzero <math>m</math>.'''
	
We should note that this example is a more general version of example 4. First, let's expand the vector equation <math>a_1m + a_2(m - x) + a_3(m - x^2) = 0</math> as follows:
<div style="text-align: center;"><math>\begin{align} a_1m + a_2(m - x) + a_3(m - x^2) = 0 \\ a_1m + a_2m - a_2x + a_3m - a_3x^2 = 0 \\ (a_1 + a_2 + a_3)m + (-a_2)x + (-a_3)x^2 = 0 \end{align}</math></div>
	
Once again, this vector equation is only true if <math>a_1 = a_2 = a_3 = 0</math>. The same matrix from example 4 can be used to provide a more extensive argument.

==Linear Dependence Lemma==
We will now look at a very important lemma known as the linear dependence lemma.

<blockquote style="background: white; border: 1px solid black; padding: 1em;"> 
:'''Lemma (Linear Dependence Lemma):''' Let <math>\{ v_1, v_2, ..., v_m \}</math> be a set of linearly dependent vectors in the vector space <math>V</math> and <math>v_1 \neq 0</math>. Then there exists <math>j \in \{ 2, 3, ..., m \}</math> such that:<br />
:'''a)''' <math>v_j \in \mathrm{span} \{ v_1, ..., v_{j-1} \}</math>.<br />
:'''b)''' <math>\mathrm{span} \{ v_1, ..., v_{j-1}, v_{j+1}, ..., v_m \} = \mathrm{span} \{ v_1, ..., v_m \}</math>.</td>
</blockquote>

The linear dependence lemma tells us that given a linear dependent set of vectors where the first vector is nonzero, then there exists a vector in the set <math>\{ v_1, v_2, ..., v_m \}</math> such that <math>v_j</math> can be written as a linear combination of <math>\{ v_1, v_2, ..., v_{j-1}</math> (that is <math>v_j \in \mathrm{span} \{ v_1, v_2, ..., v_{j-1} \}</math>), and that the set of linear combinations of the set of vectors <math>\{ v_1, ..., v_{j-1}, v_{j+1}, ..., v_m \}</math> is the same set as the combination of the set of vectors <math>\{ v_1, v_2, ..., v_m \}</math>.

*'''Proof:''' Let <math>\{ v_1, v_2, ..., v_m \}</math> be a set of vectors that are linearly dependent where <math>v_1 \neq 0</math>, and let <math>a_1, a_2, ..., a_m \in \mathbb{F}</math>. Since this set of vectors is not linearly independent, then:

<div style="text-align: center;"><math> a_1v_1 + a_2v_2 + ... + a_mv_m = 0 </math></div>

*Where not all <math>a_i</math> are zero (otherwise the set of vectors would be linearly independent). Now since <math>v_1 \neq 0</math>, it follows that not all <math>a_2, a_3, ..., a_m \in \mathbb{F}</math> are equal to zero, and so there exists an <math>a_j \in \mathbb{F}</math> such that <math>a_j \neq 0</math> where <math>j</math> is the largest index such that <math>a_j \neq 0</math>, in other words, <math>a_{j+1} = 0</math>, <math>a_{j+2} = 0</math>, etc&#8230;, and so so:

<div style="text-align: center;"><math>\begin{align} \quad a_jv_j = -a_1v_1 - a_2v_2 - ... - a_{j-1}v_{j-1} - \underbrace{a_{j+1}v_{j+1}}_{=0} + ... + \underbrace{a_{m}v_{m}}_{=0} \\ \quad a_jv_j = -a_1v_1 - a_2v_2 - ... - a_{j-1}v_{j-1} \\ \quad v_j = -\frac{a_1}{a_j}v_1 -\frac{a_2}{a_j}v_2 - ... - \frac{a_{j-1}}{a_j}v_{j-1} \end{align}</math></div>

*Therefore <math>v_j</math> can be written as a linear combination of the set of vectors <math>\{ v_1, v_2, ..., v_{j-1} \}</math> so <math>v_j \in \mathrm{span} \{ v_1, v_2, ..., v_{j-1} \}</math> which proves '''A'''.


*Now let <math>u \in \mathrm{span} \{ v_1, v_2, ..., v_m \}</math>, and so <math>u</math> can be written as a linear combination of the vectors in this set, and so there exists <math>b_1, b_2, ..., b_m \in \mathbb{F}</math> such that:

<div style="text-align: center;"><math> u = b_1v_1 + b_2v_2 + ... + b_mv_m </math></div>

*Now we substitute that <math>\quad v_j = -\frac{a_1}{a_j}v_1 -\frac{a_2}{a_j}v_2 - ... - \frac{a_{j-1}}{a_j}v_{j-1}</math> and so:

<div style="text-align: center;"><math>\begin{align} \quad u = b_1v_1 + b_2v_2 + ... + b_{j-1}v_{j-1} + b_jv_j + b_{j+1}v_{j+1} + ... + b_mv_m \\ \quad u = b_1v_1 + b_2v_2 + ... + b_{j-1}v_{j-1} + b_j[-\frac{a_1}{a_j}v_1 -\frac{a_2}{a_j}v_2 - ... - \frac{a_{j-1}}{a_j}v_{j-1}] + b_{j+1}v_{j+1} + ... + b_mv_m \\ \quad u = (b_1 - a_1b_j)v_1 + (b_2 - a_2b_j)v_2 + ... + (b_{j-1} - a_{j-1}b_j)v_{j-1} + (b_{j+1} - a_{j+1}b_j)v_{j+1} + ... + (b_m - a_mb_j)v_m \end{align}</math></div>

*Therefore <math>u</math> can be written as a linear combination of the vectors <math>\{ v_1, ..., v_{j-1}, v_{j+1}, ..., v_m</math> and so <math>u \in \mathrm{span} \{ v_1, ..., v_{j-1}, v_{j+1}, ..., v_m \}</math>. Therefore <math>\mathrm{span} \{ v_1, v_2, ..., v_m \} = \mathrm{span} \{ v_1, ..., v_{j-1}, v_{j+1}, ..., v_m \}</math>. <math>\blacksquare</math>

== Licensing == 
Content obtained and/or adapted from:
* [http://mathonline.wikidot.com/linear-independence-and-dependence Linear Independence and Dependence, mathonline.wikidot.com] under a CC BY-SA license
* [http://mathonline.wikidot.com/linear-dependence-lemma Linear Dependence Lemma, mathonline.wikidot.com] under a CC BY-SA license