Applied Linear Algebra - Packet 06

Packet 06

Vectors II: Independence

Independence

A collection of vectors $\{{𝐯}_1,{𝐯}_2,\dots ,{𝐯}_k\}$ is called independent when the only solution to the equation

$$x_1{𝐯}_1+x_2{𝐯}_2+\cdots +x_k{𝐯}_k=0$$

is given by setting $x_i=0$ for every $i$.

Question 06-01

Independence vs. dependency equations

Prove the statement:

The collection $𝒱$ is dependent (i.e. not independent) if and only if at least one of the vectors can be written as a linear combination of the others, i.e. one of them is in the span of the others.

Example

Dependent columns implies non-invertible

If a square matrix $A$ has column vectors ${𝐚}_i$ which form a dependent set, then the square matrix is not invertible.

Proof: Let $x_i$ be numbers giving the dependency relation. These numbers can be combined into a vector $𝐱=(x_1,\dots ,x_n)$. Then:

$$\begin{array}{cc}A𝐱& =A(x_1{𝐞}_1+\cdots +x_n{𝐞}_n)\\ & =A(x_1{𝐞}_1)+\cdots +A(x_n{𝐞}_n)\\ & =x_1(A{𝐞}_1)+\cdots +x_n(A{𝐞}_n)\\ & =x_1{𝐚}_1+\cdots +x_n{𝐚}_n\\ & =0.\end{array}$$

However, since the $x_i$ are not all zero, we know $𝐱\ne 0$, and therefore $A$ sends something nonzero to zero, which means it cannot be invertible. (Otherwise, what would be the preimage of zero?)

Independence and dimension Recall that the dimension of a subspace is equal to the smallest number of vectors needed to span the subspace.

If a set of vectors has the smallest number that spans whatever they span, then this set is independent. (If there is any dependency relation, then a smaller set will have the same span: just eliminate the dependent vector.)

Conversely, if some vectors are independent, then they are automatically the smallest number that spans their span:

Theorem: Independent vectors span their span minimally

Let $V=⟨{𝐯}_1,\dots ,{𝐯}_k⟩\subset {ℝ}^n$ be the subspace spanned by the set of vectors $\{{𝐯}_1,\dots ,{𝐯}_k\}$, and suppose the set $\{{𝐯}_1,\dots ,{𝐯}_k\}$ is independent. Then any set of vectors spanning $V$ must have at least $k$ elements.

Proof

We use Steinitz Exchange but with ${𝐯}_i$ in place of ${𝐞}_i$. Suppose $V=⟨{𝐮}_1,\dots ,{𝐮}_r⟩$ for $r$ other vectors ${𝐮}_j$. Our goal is to show that $r\ge k$.

First, since ${𝐯}_1\in V$, we know there is a linear combination

$${𝐯}_1=a_1{𝐮}_1+\cdots +a_r{𝐮}_r$$

with at least one coefficient $a_{i^{\star }}\ne 0$. Solve for ${𝐮}_{i^{\star }}$ in terms of the others in this equation to obtain the fact that $V=⟨{𝐯}_1,{𝐮}_2^{\prime },\dots ,{𝐮}_r^{\prime }⟩$, where we introduce the labels ${𝐮}_j^{\prime }$ with $j=2,\dots ,r$ for whichever vectors are left from $\{{𝐮}_1,\dots ,{𝐮}_r\}$ after removing ${𝐮}_{i^{\star }}$.

By iterating this process, we obtain

$$⟨{𝐯}_1,{𝐯}_2,\dots ,{𝐯}_k,{𝐮}_{k+1}^{(k-1)},\dots ,{𝐮}_{r-k}^{(k-1)}⟩,$$

and this is only possible if $r\ge k$.

(Notation: here ${𝐮}_j^{(p)}$ stands for ${𝐮}_j^{\prime \prime }{}^{\dots }{}^{\prime }$ with $p$ ticks, just as for higher derivatives.)

We are able to iterate the process because the vectors ${𝐯}_i$ are independent: at each stage, the next ${𝐯}_{i+1}$ can be written as a linear combination of the previous ${𝐯}_j$ ($j<i$) and some other ${𝐮}_j$. But the coefficient on at least one of the ${𝐮}_j$ must be nonzero, otherwise we have written ${𝐯}_i$ in terms of ${𝐯}_j$ alone, and that is impossible by independence.

Exercise 06-01

Understanding independence

Explain in more detail why we can iterate the process because the ${𝐯}_j$ are independent. Specifically compare the reason it works here with the reason it worked for the ${𝐞}_j$ in the Steinitz Exchange at the end of Packet 05.

Question 06-02

Completing the logic

Explain in more detail the statement: “and this is only possible if $r\ge k$.” Why is this statement true? What would happen if $r<k$?

Example

Independence

Problem: Is the following set of vectors dependent or independent?

$$\left(\begin{array}{c}3\\ -1\\ 2\end{array}\right),\left(\begin{array}{c}0\\ 2\\ -1\end{array}\right),\left(\begin{array}{c}2\\ -4\\ 3\end{array}\right),\left(\begin{array}{c}0\\ 1\\ 1\end{array}\right)$$

Solution: It must be a dependent set. These vectors live in ${ℝ}^3$, which is spanned by ${𝐞}_1,{𝐞}_2,{𝐞}_3$. If these vectors were independent, then we could use Steinitz Exchange to write ${ℝ}^3=⟨{𝐞}_1,{𝐞}_2,{𝐞}_3⟩$ as the span of just three of them. Since the fourth is also in ${ℝ}^3$, it could then be written as a combination of the other three, contradicting independence.

Basis

A basis for $V\subset {ℝ}^n$ is a set of independent vectors which span the entire subspace $V$.

For example, the standard basis $\{{𝐞}_1,\dots ,{𝐞}_n\}$ is a basis for the whole space ${ℝ}^n$.

The criterion of independence is a function of the relationships between the vectors in the set. The criterion of spanning also depends upon what other vectors there may be in the subspace.

(Independence is an intrinsic concept, whereas spanning the subspace is an extrinsic concept. These are not precise mathematical terms.)

Any set of vectors spans a certain subspace, namely the span itself. Therefore any independent set of vectors is a basis for its own span.

Because an independent set of vectors is always the minimal number needed to span its span (the theorem above), and a basis for a given space is an independent set of vectors spanning the subspace, every basis for a given subspace has the same number of vectors. (Since every basis has the minimal number needed to span the given subspace.) This number as the dimension of the subspace.

The most important way to think about and use the concept of basis is this: Given a basis $\{{𝐯}_1,{𝐯}_2,\dots ,{𝐯}_k\}$ for a subspace $V\subset {ℝ}^n$, every vector $𝐰$ in $V$ can be obtained uniquely as a linear combination of basis vectors:

$$𝐰=x_1{𝐯}_1+\cdots +x_k{𝐯}_k.$$

(Here ‘unique’ means that the coefficients $x_i$ are uniquely determined by $𝐰$.)

From this way of thinking about a basis, we see that the dimension $k$ is the number of quantities $x_i$ that are needed to describe everything in the space without redundancy.

Example

3 vectors spanning 3D space must be independent

In Problem 05-02, we saw that the span

$$⟨\left(\begin{array}{c}1\\ 1\\ 1\end{array}\right),\left(\begin{array}{c}1\\ 1\\ 0\end{array}\right),\left(\begin{array}{c}0\\ 2\\ 2\end{array}\right)⟩$$

is a 3-dimensional subspace of ${ℝ}^3$. (In fact it is ${ℝ}^3$, since the Steinitz Exchange will put all three ${𝐞}_i$ in the same span as this.) Therefore we know the vectors are independent, because there are three vectors spanning a 3D space.

Orthonormal systems, orthonormal bases A collection of vectors $\{{𝐯}_1,{𝐯}_2,\dots ,{𝐯}_k\}$ is called an orthonormal system when they are:

• unit vectors, meaning $|{𝐯}_i|=1$ for all $i$
• pairwise orthogonal, meaning ${𝐯}_i\cdot {𝐯}_j=0$ when $i\ne j$

If the collection is also a basis, then it is called an orthonormal basis.

Vector components in a given basis The typical application of a basis is to write other vectors as its linear combinations. Since a basis spans the whole space, every other vector in the space can be written using some set of coefficients. Since a basis is linearly independent, there is a unique set of coefficients that will generate a given vector.

For example, if $ℬ=\{{𝐛}_1,\dots ,{𝐛}_k\}$ is a basis of a subspace $V\subset {ℝ}^n$, which incidentally therefore has dimension $k$, then we can write any $𝐯\in V$ by:

$$𝐯=x_1{𝐛}_1+x_2{𝐛}_2+\cdots +x_k{𝐛}_k.$$

Using such linear combinations to express vectors $𝐯$, we find a unique association between a vector $𝐯$ and the quantities $x_1,\dots ,x_k$ which express that vector in terms of the ${𝐛}_i$. We can group those quantities into a list $(x_1,\dots ,x_k)$. The terms are called the components of $𝐯$ in the basis $ℬ$.

The ordinary component entries of a vector are actually just the components of the vector in the standard basis. (Think about this!)

Problems due Monday 26 Feb 2024 by 12:00pm

Problem 06-01

Unique coefficients on independent vectors

Suppose the vectors $\{{𝐯}_1,\dots ,{𝐯}_k\}$ are independent. Show that the coefficients on these vectors are unique, in any linear combination. This means, for example, that if we know

$$x_1{𝐯}_1+\cdots +x_k{𝐯}_k=𝐰=y_1{𝐯}_1+\cdots +y_k{𝐯}_k,$$

then in fact we have $x_i=y_i$ for all $i$. In other words, there is at most one way to write a vector as a linear combination of some independent vectors.

Problem 06-02

Neutralizing a matrix row

Suppose that the row vectors of a matrix $M$ are dependent. Explain precisely how (in terms of a given dependency relation) you can transform $M$ into a matrix having a row of all zeros by performing some combination of row-scale and row-add operations to the rows of $M$.

Problem 06-03

Column dependence and multiple solutions

Suppose that the columns of a matrix $A$ are dependent. Consider equations of the form $A𝐱=𝐛$ for $𝐱$ a variable vector, and $𝐛$ a given constant vector. Show that if there is a solution $𝐱$ to this equation, then there must be more than one solution $𝐱$. (Because of the dependency of the columns of $A$.)

(Hint: because the columns of $A$ are dependent, (explain how) you can find a specific vector ${𝐱}^{\prime }\ne 0$ with the property that $A{𝐱}^{\prime }=0$. Combine ${𝐱}^{\prime }$ with a given solution to the equation to produce a second solution. Can you always get an infinite set of solutions?)

Problem 06-04

Checking independence

Is the following set of vectors linearly independent?

$$\{\left(\begin{array}{c}1\\ 2\\ 3\end{array}\right),\left(\begin{array}{c}4\\ 5\\ 6\end{array}\right),\left(\begin{array}{c}2\\ 1\\ 0\end{array}\right)\}$$

If it’s dependent, find a dependency relation.

(You are encouraged to do this problem without Steinitz Exchange and dimensional reasoning: simply solve a system of equations instead.)

Problem 06-05

Vector operations according to components in another basis

Show that the list of components of a vector in some basis $ℬ$ are added and scaled componentwise.

This means: given two vectors, if you express them in the basis $ℬ$, and add the components in this basis, you will get the same result as if you first added the two vectors (according to the definition of adding components within ${ℝ}^n$) and then expressed the result in the basis $ℬ$. And similarly for scaling.