Linear Dependence and Linear Independence

Some vectors of a generating set may be unnecessary to form the same span: removing one of them may leave the span unchanged. In this sense, a generating set may contain redundant vectors.

Example 1.6.1. Let $$x=(1,0)$$ and $$y=(0,1)$$ be vectors in real vector space $$\mathbb R^2$,$ and consider $$S=\{ x, y, x+ y\}$.$ Then we have

\[\operatorname{span}\{ x, y, x+ y\}=\operatorname{span}\{ x, y\}=\mathbb R^2.\]

Thus, removing $${x}+{y}$$ from $$S$$ does not change the subspace generated by $$S$.$ The vector $${x}+{y}$$ is therefore redundant.

This observation motivates the following definition, which distinguishes generating sets containing such redundancy from those that do not.

Definition 1.6.2. Let $$V$$ be a vector space over a field $$F$,$ and let $$S\subseteq V$.$ We say that $$S$$ is linearly dependent if there exists $v\in S$ such that

\[\operatorname{span}(S\setminus\{v\})=\operatorname{span}(S).\]

Otherwise, the set $$S$$ is said to be linearly independent.

The same phenomenon can be described in terms of individual vectors: a vector of $$S$$ can be removed without changing the span precisely when it can be generated by the remaining vectors.

Proposition 1.6.3. Let $$V$$ be a vector space, and let $$S\subseteq V$.$ The set $$S$$ is linearly dependent if and only if

\[v\in\operatorname{span}(S\setminus\{v\})\]

for some $$v\in S$.$

Proof. Since $$S\setminus\{v\}\subseteq S$,$ monotonicity gives

\[\operatorname{span}(S\setminus\{v\})\subseteq\operatorname{span}(S).\]

By Theorem 1.5.4, the reverse inclusion holds if and only if

\[S\subseteq\operatorname{span}(S\setminus\{v\}).\]

Since $S\setminus\{v\}$ is already contained in its span, this is equivalent to $$v\in\operatorname{span}(S\setminus\{v\})$.$ $\square$

This characterization immediately yields a basic property of linear dependence: linear dependence is monotone with respect to set inclusion.

Proposition 1.6.4. Let $$V$$ be a vector space, and let $$S\subseteq T\subseteq V$.$

If $$S$$ is linearly dependent, then $$T$$ is linearly dependent.
If $$T$$ is linearly independent, then $$S$$ is linearly independent.

Proof. Suppose that $$S$$ is linearly dependent. By Proposition 1.6.3, there exists $v\in S$ such that $$v\in\operatorname{span}(S\setminus\{v\})$.$ Since $$S\setminus\{v\}\subseteq T\setminus\{v\}$,$ monotonicity gives

\[v\in\operatorname{span}(S\setminus\{v\}) \subseteq\operatorname{span}(T\setminus\{v\}).\]

Hence $$T$$ is linearly dependent by Proposition 1.6.3. Taking the contrapositive of (1) yields (2). $\square$

Proposition 1.6.4(2) shows that linear independence is preserved when vectors are removed. Extending a linearly independent set, however, requires more care: adding a vector may introduce redundancy. The following theorem provides a precise criterion for when a linearly independent set can be extended by a new vector. This criterion will later help us understand the relationship between maximal linear independence and spanning.

Theorem 1.6.5. Let $$S$$ be a linearly independent subset of a vector space $$V$,$ and let $$v\in V\setminus S$.$ Then, $S\cup \{v\}$ is linearly independent if and only if $$v\notin \operatorname{span}(S)$.$

Proof. We show that $S\cup\{v\}$ is linearly dependent if and only if $$v\in\operatorname{span}(S)$.$ Suppose that $S\cup\{v\}$ is linearly dependent. By Proposition 1.6.3, there exists $u\in S\cup\{v\}$ such that

\[u\in\operatorname{span}((S\cup\{v\})\setminus\{u\}).\]

If $$u=v$,$ then $$v\in\operatorname{span}(S)$.$ If $$u\in S$,$ then

\[u\in\operatorname{span}((S\setminus\{u\})\cup\{v\}).\]

Since $$S$$ is linearly independent, Proposition 1.6.3 gives

\[u\notin\operatorname{span}(S\setminus\{u\}).\]

Thus, by the Theorem 1.5.13(1),

\[v\in\operatorname{span}((S\setminus\{u\})\cup\{u\}) =\operatorname{span}(S).\]

Conversely, suppose that $$v\in\operatorname{span}(S)$.$ Then

\[\operatorname{span}(S\cup\{v\})=\operatorname{span}(S).\]

Since $$S=(S\cup\{v\})\setminus\{v\}$,$ it follows from Definition 1.6.2 that $S\cup\{v\}$ is linearly dependent. Taking negations yields the desired equivalence. $\square$

In the language of linear algebra, the redundancy of a subset of a vector space can be expressed without referring to one particular element. For example, the redundancy of the set $$S$$ in Example 1.6.1 can be expressed as follows:

\[\sum_{ s\in S}a_ s s=0.\]

That is, a redundant generator gives rise to a nontrivial representation of the zero vector in terms of $$S$.$ This gives an algebraic formulation of linear dependence.

Theorem 1.6.6. A subset $$S$$ of a vector space $$V$$ over a field $$F$$ is linearly dependent if and only if $$0_V$$ has a representation in terms of $$S$$ with nonempty support.

Proof. Suppose that $$S$$ is linearly dependent. Then there exists $v\in S$ such that $$v\in \operatorname{span}(S\setminus\{v\})$.$ By Proposition 1.4.14, there exists a finite supported function $a\colon S\setminus\{v\}\to F$ such that

\[v = \sum_{t\in\operatorname{supp}(a)}a(t)t.\]

Define a function $b\colon S\to F$ by

\[b(s) = \begin{cases} a(s) & \text{if } s\in \operatorname{supp}(a),\\ -1 & \text{if } s=v,\\ 0 & \text{otherwise}. \end{cases}\]

Then $\operatorname{supp}(b)=\operatorname{supp}(a)\cup \{v\}$ is finite and

\[\begin{align} \sum_{s\in\operatorname{supp}(b)}b(s)s &= b(v)v + \sum_{s\in\operatorname{supp}(a)}b(s)s\\ &= -\lowparen{\sum_{t\in\operatorname{supp}(a)}a(t)t} + \sum_{s\in\operatorname{supp}(a)}a(s)s\\ &=0_V. \end{align}\]

Hence $$b$$ is a representation of $$0_V$$ in terms of $$S$,$ and $$v\in \operatorname{supp}(b)$.$ We now prove the converse. Let $a\colon S\to F$ be a representation of $$0_V$$ with nonempty support. Put $I=\operatorname{supp}(a)$ and choose $$s\in I$.$ By Definition 1.4.1, we have

\[a(s)s + \sum_{t\in I\setminus\{s\}}a(t)t = 0_V.\]

Since $$a(s)\ne 0$,$

\[\begin{align} s &= (-a(s))^{-1}\sum_{t\in I\setminus\{s\}}a(t)t \\ &= \sum_{t\in I\setminus\{s\}}(-a(s)^{-1}a(t))t. \end{align}\]

Therefore $$s\in \operatorname{span}(I\setminus\{s\})$,$ so $$I$$ is linearly dependent by Proposition 1.6.3. It follows from Proposition 1.6.4(1) that $$S$$ is linearly dependent. $\square$

The notion of linear independence also can be formulated in the language of linear algebra, as the following corollary shows.

Corollary 1.6.7. A subset $$S$$ of a vector space $$V$$ over a field $$F$$ is linearly independent if and only if every $v\in V$ has at most one representation in terms of $$S$.$

Proof. Suppose that $$S$$ is linearly independent, and let $a,b\colon S\to F$ be representations of the same vector $$v\in V$.$ Put $K=\operatorname{supp}(a)\cup\operatorname{supp}(b)$ and define $d\colon S\to F$ by $$d(s)=a(s)-b(s)$.$ Then $\operatorname{supp}(d)\subseteq K$ is finite. By Proposition 1.4.3,

\[\begin{aligned} \sum_{s\in\operatorname{supp}(d)}d(s)s &=\sum_{s\in K}(a(s)-b(s))s\\ &=\sum_{s\in\operatorname{supp}(a)}a(s)s-\sum_{s\in\operatorname{supp}(b)}b(s)s\\ &=v-v=0_V. \end{aligned}\]

Thus $$d$$ is a representation of $$0_V$$ in terms of $$S$.$ Since $$S$$ is linearly independent, Theorem 1.6.6 implies that $$\operatorname{supp}(d)=\varnothing$.$ Hence $$a=b$.$ Conversely, suppose that every vector has at most one representation in terms of $$S$.$ The zero function $S\to F$ is a representation of $$0_V$,$ so it is the only such representation. Theorem 1.6.6 therefore implies that $$S$$ is linearly independent. $\square$

Proposition 1.6.8. Let $$V$$ be a vector space over a field $$F$,$ and let $$S$$ be a subset of $$V$.$

The set $$S$$ is linearly dependent if $$0_V\in S$.$
The empty set is linearly independent.
The set $$S$$ is linearly independent if it consists of a single nonzero vector.

Proof. (1) Suppose that $0_V\in S$ and define $a\colon S\to F$ by

\[a(t) = \begin{cases} 1 & \text{if } t=0_V,\\ 0 & \text{if } t\ne0_V. \end{cases}\]

Then $\operatorname{supp}(a)=\{0_V\}$ and

\[\sum_{t\in\operatorname{supp}(a)}a(t)t=1\cdot0_V=0_V.\]

Since $$0_V\in \operatorname{supp}(a)$,$ $$S$$ is linearly dependent by Theorem 1.6.6. (2) If $v\in V$ has a representation in terms of $$\varnothing$,$ then it is the empty function. Hence, by Corollary 1.6.7, $\varnothing$ is linearly independent. (3) Suppose that $S=\{v\}$ with $$v\ne0_V$,$ and let $a\colon S\to F$ be a representation of $$0_V$.$ If $$\operatorname{supp}(a)\ne \varnothing$,$ then $$a(v)\ne 0$.$ Hence we have

\[\sum_{s\in \operatorname{supp}(a)}a(s)s = \sum_{s\in \{v\}}a(s)s = a(v)v\ne 0_V,\]

which contradicts the fact that $$a$$ is a representation of $$0_V$.$ Thus $$\operatorname{supp}(a)=\varnothing$,$ so $$S$$ is linearly independent by Theorem 1.6.6. $\square$

Example 1.6.9. Let $$n$$ be a nonnegative integer and define

\[p_k(x)=\sum_{i=k}^{n}x^i \qquad (0\le k\le n).\]

Then the set $S = \{ p_k(x) : 0\le k\le n\}$ is linearly independent in $$F_n[x]$.$ Indeed, by Proposition 1.4.7(2) and Corollary 1.4.6,

\[\begin{aligned} \sum_{k=0}^{n}a_kp_k(x) &=\sum_{k=0}^{n}a_k\left(\sum_{i=k}^{n}x^i\right)\\ &=\sum_{k=0}^{n}\sum_{i=k}^{n}a_kx^i\\ &=\sum_{i=0}^{n}\sum_{k=0}^{i}a_kx^i\\ &=\sum_{i=0}^{n}\left(\sum_{k=0}^{i}a_k\right)x^i \end{aligned}\]

for any scalars $$a_0,\dots,a_n\in F$.$ Therefore, if $a\colon S\to F$ is a representation of the zero polynomial, then $$\operatorname{supp}(a)=\varnothing$.$ By Theorem 1.6.6, $$S$$ is linearly independent.

Exercises

1. Let $$u$$ and $$v$$ be distinct vectors in a vector space $$V$.$ Show that $\{u,v\}$ is linearly independent if and only if $u\notin \operatorname{span}\{v\}$ and $$v\notin \operatorname{span}\{u\}$.$

Proof. By Proposition 1.6.3, $\{u,v\}$ is linearly independent if and only if there are no redundant vectors in $$\{u,v\}$,$ equivalently, if and only if $u\notin \operatorname{span}\{v\}$ and $$v\notin \operatorname{span}\{u\}$.$

2. The characteristic of a field $$F$,$ denoted by $$\operatorname{ch}(F)$,$ is defined to be the least positive integer $$n$$ such that

\[\underbrace{1+1+\cdots + 1}_{n\text{ times}}=0\]

if such an $$n$$ exists; otherwise, the characteristic is defined to be $$0$.$ Let $$V$$ be a vector space over a field $$F$$ with $$\operatorname{ch}(F)\ne 2$.$

Let $u,v\in V$ be distinct. Prove that $\{u,v\}$ is linearly independent if and only if $\{u+v,u-v\}$ is linearly independent.
Let $u,v,w\in V$ be distinct. Prove that $\{u,v,w\}$ is linearly independent if and only if $\{u+v,u+w,v+w\}$ is linearly independent.

3. Prove that a subset $$S$$ of a vector space $$V$$ is linearly independent if and only if every finite subset of $$S$$ is linearly independent.

Proof. If $$S$$ is linearly independent, then every subset of $$S$$ is linearly independent by Proposition 1.6.4(2). We now prove the converse. Since $\operatorname{span}$ is finitary, for any $$v\in V$,$ if $v\notin \operatorname{span}(S_0\setminus\{v\})$ for all finite subset $$S_0\subseteq S$,$ then $$v\notin \operatorname{span}(S\setminus\{v\})$.$ By Proposition 1.6.3, $$S$$ is linearly independent. $\square$

4. Prove that if $\{A_1,\ldots,A_n\}\subseteq \operatorname{Mat}_{n\times n}(F)$ is linearly independent, then $\{A_1^{\!\top},\ldots,A_n^{\!\top}\}$ is linearly independent.

5. Let $S=\{v_1,\ldots,v_n\}$ be a finite subset of a vector space $$V$.$ Prove that $$S$$ is linearly independent if and only if $v_1\ne 0_V$ and $v_{k+1}\notin \operatorname{span}\{v_1,\ldots, v_k\}$ for all $$k=1,\ldots,n-1$.$

6. Let $$S$$ and $$T$$ be disjoint linearly independent subsets of a vector space $$V$.$ Prove that $S\cup T$ is linearly independent if and only if $$\operatorname{span}(S)\cap \operatorname{span}(T) = \{0_V\}$.$