math.wiki
Linear algebra › Abstract vector spaces › Span and independence, proved
Sign in

Span and independence, proved

In a space with no coordinates, such as a space of waveforms, which vectors of a list are redundant, and why can an independent list never be longer than a list that spans?

Where you are 5 in Abstract vector spaces

Why this exists

Yuna and Kofi program the sound engine of a synthesizer. A sound is a waveform, a function of time t, and a patch mixes stored waveforms with adjustable gains, so the sounds of a patch form the span of its waveforms. Which stored waveforms are redundant? And if a patch of n waveforms makes every sound of a second patch, can the second hold more than n independent waveforms?

For columns in \mathbb{R}^n, Linear independence and Basis and dimension answered such questions with pivots and homogeneous systems. Waveforms have no pivots. This lesson proves the basic facts about span and independence from the axioms of Vector spaces from axioms alone, so they hold in every vector space over every field.

Definition

Throughout, V is a vector space over a field \mathbb{F}. Only the field laws are used, so everything below holds over any field, such as \mathbb{Q}.

A list of length m \ge 0 in V is an ordered m-tuple (\mathbf{v}_1, \dots, \mathbf{v}_m) of vectors of V; entries may repeat, and the list of length 0 is the empty list (). The written course spoke of sets of vectors in braces; from here on spanning lists, independent lists and bases are lists, because order matters to the dependence lemma and repeats matter to independence. The span keeps its braces.

A linear combination of the list is a vector a_1\mathbf{v}_1 + \dots + a_m\mathbf{v}_m with a_j \in \mathbb{F} (Linear combination). The span \operatorname{span}\{\mathbf{v}_1, \dots, \mathbf{v}_m\} is the set of all of them (Span), and the span of the empty list is \{\mathbf{0}\}. The list spans V if its span is V. V is finite-dimensional if some list spans it, and infinite-dimensional otherwise: \mathcal{P}_m(\mathbb{F}) is spanned by (1, z, \dots, z^m), while \mathcal{P}(\mathbb{F}) is infinite-dimensional by Result 5 of Polynomials and functions as vectors.

The list is linearly independent if a_1\mathbf{v}_1 + \dots + a_m\mathbf{v}_m = \mathbf{0} only when every a_j = 0, and linearly dependent otherwise; a combination equal to \mathbf{0} with some a_j \neq 0 is a dependence relation. The empty list is independent. The proof of Result 6 of Linear independence uses only the axioms, so in every V a list is independent exactly when each vector of its span is a combination of it in only one way.

Intuition

Build a list one entry at a time and watch the span. A new entry either lies in the span of the entries before it, and is redundant, or lies outside and makes the span grow. A list is independent exactly when every entry makes the span grow (Result 3), and the dependence lemma (Result 4) says a dependent list has an entry that did not.

Result 5 is then a trade. Start from a spanning list of \mathbf{w}’s and feed in independent vectors \mathbf{u}_1, \mathbf{u}_2, \dots one at a time. Each new \mathbf{u} makes the list dependent, the lemma names a redundant entry, and it must be a \mathbf{w}. So every \mathbf{u} pushes out one \mathbf{w}, and the \mathbf{w}’s cannot run out first.

Results

Results 1 to 5 need no finiteness of V.

Result 1 (the span is the smallest subspace). For every list (\mathbf{v}_1, \dots, \mathbf{v}_m) in V, \operatorname{span}\{\mathbf{v}_1, \dots, \mathbf{v}_m\} is a subspace of V containing every \mathbf{v}_j, and every subspace of V containing every \mathbf{v}_j contains it.

Result 2 (sublists). Every sublist of an independent list is independent. A list with \mathbf{0} as an entry, or with one vector in two places, is dependent.

Result 3 (growing a list). If (\mathbf{v}_1, \dots, \mathbf{v}_m) is independent and \mathbf{w} \notin \operatorname{span}\{\mathbf{v}_1, \dots, \mathbf{v}_m\}, then (\mathbf{v}_1, \dots, \mathbf{v}_m, \mathbf{w}) is independent. Hence a list is independent if and only if no entry \mathbf{v}_k lies in \operatorname{span}\{\mathbf{v}_1, \dots, \mathbf{v}_{k-1}\}; for k = 1 that span is \{\mathbf{0}\}, so the condition says \mathbf{v}_1 \neq \mathbf{0}.

Result 4 (linear dependence lemma). If (\mathbf{v}_1, \dots, \mathbf{v}_m) is dependent, there is a k with \mathbf{v}_k \in \operatorname{span}\{\mathbf{v}_1, \dots, \mathbf{v}_{k-1}\}. For every such k, removing \mathbf{v}_k from the list does not change its span.

Result 5 (independent lists are no longer than spanning lists). If (\mathbf{u}_1, \dots, \mathbf{u}_m) is independent and every \mathbf{u}_j lies in \operatorname{span}\{\mathbf{w}_1, \dots, \mathbf{w}_n\}, then m \le n. In particular, if a list of length n spans V, every list in V of length more than n is dependent.

Result 6 (subspaces of finite-dimensional spaces). If a list of length n spans V, then every subspace U of V is spanned by an independent list of length at most n. So every subspace of a finite-dimensional space is finite-dimensional.

Result 7 (a test for infinite dimension). V is infinite-dimensional if and only if there is a sequence \mathbf{v}_1, \mathbf{v}_2, \dots in V such that (\mathbf{v}_1, \dots, \mathbf{v}_m) is independent for every m \ge 1.

Why it is true

Result 1. All coefficients 0 give \mathbf{0} (Result 4 of Vector spaces from axioms). For combinations \mathbf{x} = \sum_j a_j\mathbf{v}_j, \mathbf{y} = \sum_j b_j\mathbf{v}_j and a scalar c, the commutative, associative and distributive axioms give

c\mathbf{x} + \mathbf{y} = \sum_{j=1}^{m} (ca_j + b_j)\mathbf{v}_j,

again a combination; with c = 1, or \mathbf{y} = \mathbf{0}, this is closure under addition and multiples, so the subspace test (Result 9 there) applies. Coefficient 1 on \mathbf{v}_k and 0 elsewhere gives \mathbf{v}_k. A subspace containing every \mathbf{v}_j contains each a_j\mathbf{v}_j and then, one term at a time, their sum.

Result 2. A dependence relation on a sublist becomes one on the whole list when the other entries get coefficient 0; the first claim is the contrapositive. The sublist (\mathbf{0}) has the relation 1\mathbf{0} = \mathbf{0}, and (\mathbf{v}, \mathbf{v}) has 1\mathbf{v} + (-1)\mathbf{v} = \mathbf{0}.

Result 3. Suppose a_1\mathbf{v}_1 + \dots + a_m\mathbf{v}_m + b\mathbf{w} = \mathbf{0}. If b \neq 0, dividing by b gives

\mathbf{w} = -\frac{a_1}{b}\mathbf{v}_1 - \dots - \frac{a_m}{b}\mathbf{v}_m,

in the span, which is false. So b = 0, and independence gives every a_j = 0. For the test: if no entry lies in the span of those before it, start from the empty list and apply the first part m times. Conversely, if \mathbf{v}_k = c_1\mathbf{v}_1 + \dots + c_{k-1}\mathbf{v}_{k-1}, then c_1\mathbf{v}_1 + \dots + c_{k-1}\mathbf{v}_{k-1} - \mathbf{v}_k = \mathbf{0} is a dependence relation.

Result 4. Take a dependence relation a_1\mathbf{v}_1 + \dots + a_m\mathbf{v}_m = \mathbf{0} and let k be the largest index with a_k \neq 0. Since a_k has an inverse in \mathbb{F},

\mathbf{v}_k = -\frac{a_1}{a_k}\mathbf{v}_1 - \dots - \frac{a_{k-1}}{a_k}\mathbf{v}_{k-1},

an empty sum \mathbf{0} when k = 1. This is Result 5 of Linear independence, now in any V. Next let \mathbf{v}_k be any entry in the span of the entries before it, and let S be the span of the list without \mathbf{v}_k. By Result 1, S is a subspace containing \mathbf{v}_1, \dots, \mathbf{v}_{k-1}, so it contains \mathbf{v}_k, so every entry of the full list, and by Result 1 again the full span. Conversely, a combination of the shorter list is one of the full list with coefficient 0 on \mathbf{v}_k.

Result 5. Let W = \operatorname{span}\{\mathbf{w}_1, \dots, \mathbf{w}_n\}. We prove by induction on k = 0, 1, \dots, m that k \le n and, after renumbering the \mathbf{w}’s, the list

B_k = (\mathbf{u}_1, \dots, \mathbf{u}_k, \mathbf{w}_{k+1}, \dots, \mathbf{w}_n)

spans W. For k = 0 this is the hypothesis. Suppose it holds for some k < m. Since \mathbf{u}_{k+1} \in W, inserting \mathbf{u}_{k+1} after \mathbf{u}_k in B_k gives a list with one entry a combination of the others, a dependent list. By Result 4 some entry lies in the span of the entries before it. It is not a \mathbf{u}: the entries before \mathbf{u}_j are \mathbf{u}_1, \dots, \mathbf{u}_{j-1}, and (\mathbf{u}_1, \dots, \mathbf{u}_{k+1}) is independent (Result 2), so Result 3 rules this out. So it is some \mathbf{w}_i with i \ge k + 1; in particular a \mathbf{w} is left, and k + 1 \le n. Removing that \mathbf{w}_i keeps the span W by Result 4, and renumbering the rest gives B_{k+1}. At k = m, m \le n.

The system proof of Basis and dimension also works over any field. The exchange proof says more: \mathbf{u}_1, \dots, \mathbf{u}_m together with n - m of the \mathbf{w}’s still span W.

Result 6. If U = \{\mathbf{0}\}, the empty list spans it. Otherwise choose \mathbf{u}_1 \neq \mathbf{0} in U, and while (\mathbf{u}_1, \dots, \mathbf{u}_k) does not span U, choose \mathbf{u}_{k+1} \in U outside its span (which lies in U by Result 1). Each list built is independent by Result 3, so by Result 5 its length is at most n. So the construction stops within n choices, and it stops only when the list spans U.

Result 7. If a list of length n spans V, no list of length n + 1 is independent (Result 5), so no such sequence exists. Conversely, let V be infinite-dimensional. Then V \neq \{\mathbf{0}\}, so some \mathbf{v}_1 \neq \mathbf{0}. An independent (\mathbf{v}_1, \dots, \mathbf{v}_m) does not span V, so some \mathbf{v}_{m+1} lies outside its span, and (\mathbf{v}_1, \dots, \mathbf{v}_{m+1}) is independent by Result 3. Step by step this builds the sequence.

Worked examples

Example 1

Trimming a patch

Yuna’s patch mixes four waveforms, vectors in the space \mathbb{R}^{\mathbb{R}} of real functions of t: (\sin t, \sin 3t, \sin^3 t, \sin t\cos^2 t). Delete redundant waveforms with the dependence lemma until the list is independent, and describe every sound the patch makes.

Solution

The sum formula (Sine and tangent of a sum or difference) with \sin 2t = 2\sin t\cos t and \cos 2t = 1 - 2\sin^2 t gives

\begin{aligned}\sin 3t &= \sin 2t\cos t + \cos 2t\sin t \\ &= 3\sin t - 4\sin^3 t.\end{aligned}

Ask of each entry whether it lies in the span of those before it. \sin t is not the zero function. If \sin 3t = c\sin t for every t, then t = \tfrac{\pi}{2} gives c = -1 but t = \tfrac{\pi}{6} gives 1 = \tfrac{c}{2}; so \sin 3t stays. The identity gives

\sin^3 t = \tfrac{3}{4}\sin t - \tfrac{1}{4}\sin 3t,

so by Result 4 deleting \sin^3 t keeps the span. In the shorter list, using \cos^2 t = 1 - \sin^2 t,

\begin{aligned}\sin t\cos^2 t &= \sin t - \sin^3 t \\ &= \tfrac{1}{4}\sin t + \tfrac{1}{4}\sin 3t,\end{aligned}

so it goes too. What remains, (\sin t, \sin 3t), is independent by Result 3. The patch makes exactly the sounds a\sin t + b\sin 3t, each from one pair of gains (a, b).

Example 2

Exchanging into a spanning list

In \mathcal{P}_2(\mathbb{R}) the list (p_1, p_2) = (1 + z, z - z^2) is independent and (1, z, z^2, 1 + z^2) spans. Carry out the exchange in the proof of Result 5, each time removing the first entry that lies in the span of the entries before it.

Solution

Coefficients are compared by Result 2 of Polynomials and functions as vectors.

Step 1: put p_1 in front, giving (1 + z, 1, z, z^2, 1 + z^2). The entry 1 is not a multiple of 1 + z, but z = (1 + z) - 1. Removing z leaves B_1 = (1 + z, 1, z^2, 1 + z^2), which still spans by Result 4.

Step 2: put p_2 after p_1, giving (1 + z, z - z^2, 1, z^2, 1 + z^2). A multiple of 1 + z has no z^2 term, so z - z^2 stays. If 1 = a(1 + z) + b(z - z^2), the z^2, z and constant terms give b = 0, a + b = 0 and a = 1, which is impossible. But z^2 = (1 + z) - (z - z^2) - 1, so removing z^2 leaves

B_2 = (1 + z, z - z^2, 1, 1 + z^2),

a spanning list. Each p_j pushed out one original entry, and 2 \le 4. B_2 is still dependent, since 1 + z^2 = p_1 - p_2; cutting spanning lists down is the work of Bases and dimension, proved.

Example 3

Spanning by counting

In \mathcal{P}_3(\mathbb{R}) let q_1 = 1 - z^3, q_2 = z + 2z^2, q_3 = 1 + z^2 and q_4 = 2 + 3z + 4z^2 - 2z^3. Show that (q_1, q_2, q_3, q_4) is independent, then that it spans \mathcal{P}_3(\mathbb{R}) without solving a general system. Write z^3 as a combination of it.

Solution

Use the test of Result 3. q_1 \neq 0. A multiple aq_1 has constant term a, while q_2 has 0, so a = 0; but q_2 \neq 0. In aq_1 + bq_2 = q_3 the z terms give b = 0 and the z^2 terms 2b = 1, impossible. In aq_1 + bq_2 + cq_3 = q_4 the z, z^2 and constant terms give b = 3, then c = -2, then a = 4; but then the z^3 terms give -4, not -2. So the list is independent.

Now let p \in \mathcal{P}_3(\mathbb{R}). The list (q_1, q_2, q_3, q_4, p) lies in the span of (1, z, z^2, z^3) and has length 5 > 4, so it is dependent by Result 5. By Result 4 some entry lies in the span of those before it, and no q_k does. So p \in \operatorname{span}\{q_1, q_2, q_3, q_4\}.

For z^3 = aq_1 + bq_2 + cq_3 + dq_4, the coefficients give a + c + 2d = 0, b + 3d = 0, 2b + c + 4d = 0 and -a - 2d = 1. So b = -3d, c = 2d, a = -4d, and 2d = 1:

z^3 = -2q_1 - \tfrac{3}{2}q_2 + q_3 + \tfrac{1}{2}q_4.
Example 4

Independence depends on the field

The real numbers form a vector space over \mathbb{Q}, with rational scalars. Prove that \displaystyle (1, \sqrt{2}, \sqrt{3}) is independent over \mathbb{Q} but dependent over \mathbb{R}.

Solution

We use that \displaystyle \sqrt{2}, \displaystyle \sqrt{3} and \displaystyle \sqrt{6} are irrational. Let a, b, c \in \mathbb{Q} with \displaystyle a + b\sqrt{2} + c\sqrt{3} = 0. Squaring \displaystyle a + b\sqrt{2} = -c\sqrt{3} gives

a^2 + 2b^2 + 2ab\sqrt{2} = 3c^2.

If ab \neq 0, then \displaystyle \sqrt{2} = \frac{3c^2 - a^2 - 2b^2}{2ab} is rational, which is false. If b = 0, then \displaystyle a = -c\sqrt{3}, and c \neq 0 would make \displaystyle \sqrt{3} rational; so c = 0 and a = 0. If a = 0, multiplying \displaystyle b\sqrt{2} = -c\sqrt{3} by \displaystyle \sqrt{2} gives \displaystyle 2b = -c\sqrt{6}, so c = 0, and then b = 0. In every case a = b = c = 0.

Over \mathbb{R}, \displaystyle \sqrt{2} \cdot 1 + (-1) \cdot \sqrt{2} = 0 is a dependence relation. Independence means nothing until the field is named.

Example 5

An infinite-dimensional space of functions

Let V = \{f \in C[0, 1] : f(0) = 0\}. Prove that V is infinite-dimensional, using the functions e^{x} - 1, e^{2x} - 1, e^{3x} - 1, \dots.

Solution

V is a subspace of C[0, 1]: it holds the zero function, and if f(0) = g(0) = 0 then (af + g)(0) = 0. Each e^{jx} - 1 is continuous and is 0 at x = 0, so it lies in V. By Result 7 it is enough to show that (e^{x} - 1, \dots, e^{mx} - 1) is independent for every m \ge 1. Suppose a_1(e^{x} - 1) + \dots + a_m(e^{mx} - 1) = 0 on [0, 1]. Put y = e^{x}, so e^{jx} = y^j, and c = a_1 + \dots + a_m. As e^{x} is increasing, y takes infinitely many values on [0, 1], and at each of them

a_1y + a_2y^2 + \dots + a_my^m - c = 0.

A polynomial vanishing at infinitely many points has every coefficient 0 (Result 2 of Polynomials and functions as vectors), so every a_j = 0. By Result 6, V is then no subspace of a finite-dimensional space, so C[0, 1] and \mathbb{R}^{[0, 1]} are infinite-dimensional too.

Boundaries

Order decides what the lemma removes. Read Example 1’s list backward, (\sin t\cos^2 t, \sin^3 t, \sin 3t, \sin t). The second entry is not a multiple of the first (at t = \tfrac{\pi}{2} the first is 0 and the second is 1), but \sin 3t = 3\sin t\cos^2 t - \sin^3 t and then \sin t = \sin t\cos^2 t + \sin^3 t go, leaving (\sin t\cos^2 t, \sin^3 t): a different independent list with the same span. And the lemma promises one removable entry, not that every entry is removable (Exercise 4).

Results 5 and 6 need a finite spanning list. In an infinite-dimensional space no length bounds the independent lists (Result 7). Even \mathbb{R} over \mathbb{Q} is infinite-dimensional: the \mathbb{Q}-span of n reals is the image of \mathbb{Q}^n, a countable set, while \mathbb{R} is not countable (Countable and uncountable sets).

Where this goes next

A list that is independent and spans is a basis. Bases and dimension, proved uses Result 4 to cut a spanning list down to a basis and Result 3 to extend an independent list to one, and Result 5 shows that all bases of a finite-dimensional space have one length, its dimension.

Exercises

The dependence lemma

  1. In \mathbb{R}^{2 \times 2} take (A_1, A_2, A_3, A_4, A_5) with A_1 = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}, A_2 = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}, A_3 = \begin{bmatrix} 2 & 3 \\ 3 & 2 \end{bmatrix}, A_4 = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix} and A_5 = \begin{bmatrix} 0 & 1 \\ -1 & 0 \end{bmatrix}. Repeatedly remove the first entry that lies in the span of the entries before it, until none does. Which list remains, and why is it independent with the same span?
  2. In the space \mathbb{R}^{(0, \infty)} of real functions of x > 0, trim (\ln x, \ln(x^2), 1, \ln(5x), (\ln x)^2) the same way, then write \ln(7x^2) as a combination of what remains.
  3. In \mathbb{R}^{\infty} let \mathbf{x} = (1, 0, 1, 0, \dots), \mathbf{y} = (0, 1, 0, 1, \dots), \mathbf{w} = (1, 1, 1, 1, \dots), \mathbf{u} = (1, -1, 1, -1, \dots) and \mathbf{s} = (2, 0, 2, 0, \dots). Trim (\mathbf{x}, \mathbf{y}, \mathbf{w}, \mathbf{u}, \mathbf{s}). Is (3, -1, 3, -1, \dots) in its span? Is (1, 2, 3, 4, \dots)?
  4. Show that (1 + z, 2 + 2z, z^2) is dependent in \mathcal{P}_2(\mathbb{R}) but z^2 \notin \operatorname{span}\{1 + z, 2 + 2z\}. Which single entries can be removed without shrinking the span?

Exchange and counting

  1. In \mathcal{P}_2(\mathbb{R}) the list (z^2 - 1, z + 1) is independent and (1, 1 + z, z + z^2, z^2) spans. Carry out the exchange as in Example 2, and give B_1 and B_2.
  2. Without solving any system, explain: (a) why every list of four vectors in \operatorname{span}\{\sin t, \cos t, \sin 2t\} is dependent; (b) why no list of length 3 spans \mathbb{R}^{2 \times 2}; (c) why every list of four vectors in \{p \in \mathcal{P}_3(\mathbb{R}) : p(1) = 0\} is dependent.
  3. In C(\mathbb{R}): (a) find the lemma’s k and a dependence relation for (\cos t, \cos(t + \tfrac{\pi}{3}), \cos(t + \tfrac{2\pi}{3})); (b) find every real d for which (\cos t, \cos(t + d)) is dependent.

Changing the field

  1. Let \mathbf{v} = (1, i) and \mathbf{w} = (i, -1) in \mathbb{C}^2. Is (\mathbf{v}, \mathbf{w}) independent when \mathbb{C}^2 is a vector space over \mathbb{C}? Over \mathbb{R}?
  2. In \mathbb{R} over \mathbb{Q}: (a) find the lemma’s k for \displaystyle (\sqrt{5}, \sqrt{45}, \sqrt{7}); (b) show that \displaystyle (1, \sqrt{7}) is independent, and write \displaystyle 2 + \sqrt{28} as a combination of it.

Proofs

  1. Let (\mathbf{v}_1, \dots, \mathbf{v}_m) be independent in V and \mathbf{w} = c_1\mathbf{v}_1 + \dots + c_m\mathbf{v}_m. Fix k and replace \mathbf{v}_k by \mathbf{w} in the list. Prove that the new list is independent with the same span if c_k \neq 0, and dependent if c_k = 0.
  2. Let (\mathbf{v}_1, \dots, \mathbf{v}_m) span V, where no list of length less than m spans V. Prove that it is independent.
  3. Suppose a list of length n spans V and U_0 \subsetneq U_1 \subsetneq \dots \subsetneq U_k are subspaces of V. Prove that k \le n.
  4. For c \in (0, 1) let f_c(x) = \lvert x - c \rvert on [0, 1]. Prove that (f_{c_1}, \dots, f_{c_m}) is independent in C[0, 1] whenever c_1, \dots, c_m \in (0, 1) are distinct.
  5. Let V be a vector space over \mathbb{C}, so also over \mathbb{R}. Prove that if (\mathbf{v}_1, \dots, \mathbf{v}_m) is independent over \mathbb{C}, then (\mathbf{v}_1, i\mathbf{v}_1, \dots, \mathbf{v}_m, i\mathbf{v}_m) is independent over \mathbb{R}.
  6. Prove that V is finite-dimensional if and only if there is an integer N such that every independent list in V has length at most N.
Answers
  1. (A_1, A_2, A_4, A_5). A_2 is not a multiple of A_1, but A_3 = 2A_1 + 3A_2 goes. Combinations of A_1, A_2 have equal diagonal entries, so A_4 stays; combinations of A_1, A_2, A_4 are symmetric and A_5^{T} = -A_5, so A_5 stays. The list is independent by Result 3 and keeps the span by Result 4.
  2. (\ln x, 1, (\ln x)^2). For x > 0, \ln(x^2) = 2\ln x goes; every multiple of \ln x vanishes at x = 1, so 1 stays; \ln(5x) = \ln 5 \cdot 1 + \ln x goes. If (\ln x)^2 = a\ln x + b for all x > 0, then u^2 - au - b = 0 for every real u, impossible for a nonzero polynomial (Result 1 of Polynomials and functions as vectors). Then \ln(7x^2) = 2\ln x + \ln 7 \cdot 1.
  3. (\mathbf{x}, \mathbf{y}) remains: \mathbf{y} is not a multiple of \mathbf{x}, and then \mathbf{w} = \mathbf{x} + \mathbf{y}, \mathbf{u} = \mathbf{x} - \mathbf{y} and \mathbf{s} = 2\mathbf{x} go in turn. Yes: (3, -1, 3, -1, \dots) = 3\mathbf{x} - \mathbf{y}. Every member (a, b, a, b, \dots) has equal first and third entries, so (1, 2, 3, 4, \dots) is not.
  4. 2(1 + z) - (2 + 2z) = 0, and combinations of 1 + z and 2 + 2z have degree at most 1, so z^2 is not one. Removing 1 + z or 2 + 2z keeps the span, each being a multiple of the other (Result 4 with that entry listed second). Removing z^2 shrinks it.
  5. Step 1, in (z^2 - 1, 1, 1 + z, z + z^2, z^2): 1 is not a multiple of z^2 - 1, combinations of z^2 - 1 and 1 have no z term, but z + z^2 = (z^2 - 1) + (1 + z); so B_1 = (z^2 - 1, 1, 1 + z, z^2). Step 2, in (z^2 - 1, z + 1, 1, 1 + z, z^2): z + 1 stays; a(z^2 - 1) + b(z + 1) = 1 forces a = b = 0 by the z^2 and z terms, so 1 stays; 1 + z equals the second entry. So B_2 = (z^2 - 1, z + 1, 1, z^2).
  6. (a) By Result 5, a space spanned by three vectors has no independent list of four. (b) The four matrices with a single entry 1 are independent, since a combination of them is the matrix of its coefficients; by Result 5 every spanning list has length at least 4. (c) If p = a_0 + a_1z + a_2z^2 + a_3z^3 has p(1) = 0, then a_0 = -a_1 - a_2 - a_3, so p = a_1(z - 1) + a_2(z^2 - 1) + a_3(z^3 - 1). Three vectors span the space, so by Result 5 no list of four in it is independent.
  7. (a) \displaystyle \cos(t + \tfrac{\pi}{3}) = \tfrac{1}{2}\cos t - \tfrac{\sqrt{3}}{2}\sin t is \displaystyle -\tfrac{\sqrt{3}}{2} at t = \tfrac{\pi}{2}, where \cos t is 0, so it stays. And \displaystyle \cos(t + \tfrac{2\pi}{3}) = -\tfrac{1}{2}\cos t - \tfrac{\sqrt{3}}{2}\sin t, which is \cos(t + \tfrac{\pi}{3}) - \cos t. So k = 3 and \cos t - \cos(t + \tfrac{\pi}{3}) + \cos(t + \tfrac{2\pi}{3}) = 0. (b) Exactly the integer multiples of \pi. For those, \sin d = 0 and \cos(t + d) = \cos d\cos t - \sin d\sin t = \pm\cos t. If \sin d \neq 0 and a\cos t + b\cos(t + d) = 0, then t = \tfrac{\pi}{2} gives -b\sin d = 0, so b = 0, and t = 0 gives a = 0.
  8. Over \mathbb{C}, dependent: i\mathbf{v} - \mathbf{w} = \mathbf{0}. Over \mathbb{R}, independent: a\mathbf{v} + b\mathbf{w} has first entry a + bi, which is 0 for real a, b only when a = b = 0.
  9. (a) \displaystyle \sqrt{5} \neq 0 and \displaystyle \sqrt{45} = 3\sqrt{5} with 3 \in \mathbb{Q}, so k = 2. (b) If \displaystyle a + b\sqrt{7} = 0 with b \neq 0, then \displaystyle \sqrt{7} = -\tfrac{a}{b} is rational, which is false; so b = 0, then a = 0. As \displaystyle \sqrt{28} = 2\sqrt{7}, \displaystyle 2 + \sqrt{28} = 2 \cdot 1 + 2 \cdot \sqrt{7}.
  10. Call the new list L'. If c_k = 0, then \mathbf{w} - \sum_{j \neq k} c_j\mathbf{v}_j = \mathbf{0} is a dependence relation on L', with coefficient 1 on \mathbf{w}. Now let c_k \neq 0. Then \mathbf{v}_k = c_k^{-1}\big(\mathbf{w} - \sum_{j \neq k} c_j\mathbf{v}_j\big), so every entry of the old list lies in the span of L', and \mathbf{w} lies in the span of the old list; by Result 1 the two spans are equal. Suppose b\mathbf{w} + \sum_{j \neq k} b_j\mathbf{v}_j = \mathbf{0}. Substituting for \mathbf{w} gives bc_k\mathbf{v}_k + \sum_{j \neq k} (bc_j + b_j)\mathbf{v}_j = \mathbf{0}, so independence gives bc_k = 0 and bc_j + b_j = 0 for j \neq k. As c_k \neq 0, b = 0, and then every b_j = 0.
  11. If it were dependent, Result 4 would remove an entry and keep the span V, giving a spanning list of length m - 1, contrary to the choice of m. (For m = 0, the empty list is independent.)
  12. For j = 1, \dots, k choose \mathbf{u}_j \in U_j outside U_{j-1}. The chain increases, so \mathbf{u}_1, \dots, \mathbf{u}_{j-1} \in U_{j-1}, whose span lies in U_{j-1} by Result 1; so \mathbf{u}_j is not in it (for j = 1 that span is \{\mathbf{0}\} \subseteq U_0). By Result 3 the list (\mathbf{u}_1, \dots, \mathbf{u}_k) is independent, and by Result 5, k \le n.
  13. Each f_c is continuous. Suppose \sum_j a_jf_{c_j} = 0 and fix i. For j \neq i, x - c_j keeps one sign near c_i, so f_{c_j} is \pm(x - c_j) there and is differentiable at c_i. So a_if_{c_i} = -\sum_{j \neq i} a_jf_{c_j} is differentiable at c_i. If a_i \neq 0, so is f_{c_i}; but its one-sided derivatives at c_i are -1 and 1. So every a_i = 0.
  14. Suppose \sum_j (a_j\mathbf{v}_j + b_j(i\mathbf{v}_j)) = \mathbf{0} with real a_j, b_j. Since b_j(i\mathbf{v}_j) = (b_ji)\mathbf{v}_j and scalars distribute, \sum_j (a_j + b_ji)\mathbf{v}_j = \mathbf{0}. Independence over \mathbb{C} gives a_j + b_ji = 0, so a_j = b_j = 0 for every j.
  15. If a list of length n spans V, then N = n works by Result 5. Conversely, if such an N exists but V is infinite-dimensional, Result 7 gives an independent list (\mathbf{v}_1, \dots, \mathbf{v}_{N+1}), longer than N, a contradiction (Proof by contradiction).
math.wiki · CC-BY-SA-4.0