Linear combinations and linear independence

$\newenvironment {prompt}{}{} \newcommand {\ungraded }[0]{} \newcommand {\definedTerm }[1]{\textbf {#1}} \newcommand {\dfn }[1]{\textbf {#1}} \newcommand {\wt }[0]{\widetilde } \newcommand {\ov }[0]{\overline } \newcommand {\inj }[0]{\rightarrowtail } \newcommand {\surj }[0]{\twoheadrightarrow } \newcommand {\harpoon }[0]{\overset {\rightharpoonup }} \newcommand {\orderof }[1]{\sim #1} \newcommand {\Z }[0]{\mathbb {Z}} \newcommand {\reals }[0]{\mathbb {R}} \newcommand {\real }[1]{\mathbb {R}^{#1}} \newcommand {\complexes }[0]{\mathbb {C}} \newcommand {\complex }[1]{\mathbb {C}^{#1}} \newcommand {\CC }[0]{\mathbb {C}} \newcommand {\conjugate }[1]{\overline {#1}} \newcommand {\modulus }[1]{\left \lvert #1\right \rvert } \newcommand {\zerovector }[0]{\vect {0}} \newcommand {\zeromatrix }[0]{\mathcal {O}} \newcommand {\innerproduct }[2]{\left \langle #1,\,#2\right \rangle } \newcommand {\norm }[1]{\left \lVert #1\right \rVert } \newcommand {\dimension }[1]{\dim \left (#1\right )} \newcommand {\nullity }[1]{n\left (#1\right )} \newcommand {\rank }[1]{r\left (#1\right )} \newcommand {\ds }[0]{\oplus } \newcommand {\detname }[1]{\det \left (#1\right )} \newcommand {\detbars }[1]{\left \lvert #1\right \rvert } \newcommand {\trace }[1]{t\left (#1\right )} \newcommand {\sr }[1]{#1^{1/2}} \newcommand {\spn }[1]{\left \langle #1\right \rangle } \newcommand {\nsp }[1]{\mathcal {N}\!\left (#1\right )} \newcommand {\csp }[1]{\mathcal {C}\!\left (#1\right )} \newcommand {\rsp }[1]{\mathcal {R}\!\left (#1\right )} \newcommand {\lns }[1]{\mathcal {L}\!\left (#1\right )} \newcommand {\per }[1]{#1^\perp } \newcommand {\augmented }[2]{\left \lbrack \left .#1\,\right \rvert \,#2\right \rbrack } \newcommand {\linearsystem }[2]{\mathcal {LS}\!\left (#1,\,#2\right )} \newcommand {\homosystem }[1]{\linearsystem {#1}{\zerovector }} \newcommand {\rowopswap }[2]{R_{#1}\leftrightarrow R_{#2}} \newcommand {\rowopmult }[2]{#1R_{#2}} \newcommand {\rowopadd }[3]{#1R_{#2}+R_{#3}} \newcommand {\leading }[1]{\fbox {#1}} \newcommand {\rref }[0]{\xrightarrow {\text {RREF}}} \newcommand {\elemswap }[2]{E_{#1,#2}} \newcommand {\elemmult }[2]{E_{#2}\left (#1\right )} \newcommand {\elemadd }[3]{E_{#2,#3}\left (#1\right )} \newcommand {\scalarlist }[2]{{#1}_{1},\,{#1}_{2},\,{#1}_{3},\,\ldots ,\,{#1}_{#2}} \newcommand {\vect }[1]{\mathbf {#1}} \newcommand {\colvector }[1]{\begin {bmatrix}#1\end {bmatrix}} \newcommand {\vectorcomponents }[2]{\colvector {#1_{1}\\#1_{2}\\#1_{3}\\\vdots \\#1_{#2}}} \newcommand {\vectorlist }[2]{\vect {#1}_{1},\,\vect {#1}_{2},\,\vect {#1}_{3},\,\ldots ,\,\vect {#1}_{#2}} \newcommand {\vectorentry }[2]{\left \lbrack #1\right \rbrack _{#2}} \newcommand {\matrixentry }[2]{\left \lbrack #1\right \rbrack _{#2}} \newcommand {\lincombo }[3]{#1_{1}\vect {#2}_{1}+#1_{2}\vect {#2}_{2}+#1_{3}\vect {#2}_{3}+\cdots +#1_{#3}\vect {#2}_{#3}} \newcommand {\matrixcolumns }[2]{\left \lbrack \vect {#1}_{1}|\vect {#1}_{2}|\vect {#1}_{3}|\ldots |\vect {#1}_{#2}\right \rbrack } \newcommand {\transpose }[1]{#1^{t}} \newcommand {\inverse }[1]{#1^{-1}} \newcommand {\submatrix }[3]{#1\left (#2|#3\right )} \newcommand {\adj }[1]{\transpose {\left (\conjugate {#1}\right )}} \newcommand {\adjoint }[1]{#1^\ast } \newcommand {\set }[1]{\left \{#1\right \}} \newcommand {\setparts }[2]{\left \lbrace #1\,\middle |\,#2\right \rbrace } \newcommand {\card }[1]{\left \lvert #1\right \rvert } \newcommand {\setcomplement }[1]{\overline {#1}} \newcommand {\charpoly }[2]{p_{#1}\left (#2\right )} \newcommand {\eigenspace }[2]{\mathcal {E}_{#1}\left (#2\right )} \newcommand {\eigensystem }[3]{\lambda &amp;=#2&amp;\eigenspace {#1}{#2}&amp;=\spn {\set {#3}}} \newcommand {\geneigenspace }[2]{\mathcal {G}_{#1}\left (#2\right )} \newcommand {\algmult }[2]{\alpha _{#1}\left (#2\right )} \newcommand {\geomult }[2]{\gamma _{#1}\left (#2\right )} \newcommand {\indx }[2]{\iota _{#1}\left (#2\right )} \newcommand {\ltdefn }[3]{#1\colon #2\rightarrow #3} \newcommand {\lteval }[2]{#1\left (#2\right )} \newcommand {\ltinverse }[1]{#1^{-1}} \newcommand {\restrict }[2]{{#1}|_{#2}} \newcommand {\preimage }[2]{#1^{-1}\left (#2\right )} \newcommand {\rng }[1]{\mathcal {R}\!\left (#1\right )} \newcommand {\krn }[1]{\mathcal {K}\!\left (#1\right )} \newcommand {\compose }[2]{{#1}\circ {#2}} \newcommand {\vslt }[2]{\mathcal {LT}\left (#1,\,#2\right )} \newcommand {\isomorphic }[0]{\cong } \newcommand {\similar }[2]{\inverse {#2}#1#2} \newcommand {\vectrepname }[1]{\rho _{#1}} \newcommand {\vectrep }[2]{\lteval {\vectrepname {#1}}{#2}} \newcommand {\vectrepinvname }[1]{\ltinverse {\vectrepname {#1}}} \newcommand {\vectrepinv }[2]{\lteval {\ltinverse {\vectrepname {#1}}}{#2}} \newcommand {\matrixrep }[3]{M^{#1}_{#2,#3}} \newcommand {\matrixrepcolumns }[4]{\left \lbrack \left .\vectrep {#2}{\lteval {#1}{\vect {#3}_{1}}}\right |\left .\vectrep {#2}{\lteval {#1}{\vect {#3}_{2}}}\right |\left .\vectrep {#2}{\lteval {#1}{\vect {#3}_{3}}}\right |\ldots \left |\vectrep {#2}{\lteval {#1}{\vect {#3}_{#4}}}\right .\right \rbrack } \newcommand {\cbm }[2]{C_{#1,#2}} \newcommand {\jordan }[2]{J_{#1}\left (#2\right )} \newcommand {\hadamard }[2]{#1\circ #2} \newcommand {\hadamardidentity }[1]{J_{#1}} \newcommand {\hadamardinverse }[1]{\widehat {#1}} \newcommand {\id }[0]{\mathrm {id}} \newcommand {\C }[0]{\mathbb {C}} \newcommand {\R }[0]{\mathbb {R}} \newcommand {\Q }[0]{\mathbb {Q}} \newcommand {\N }[0]{\mathbb {N}} \newcommand {\F }[0]{\mathbb {F}} \newcommand {\bbH }[0]{\mathbb {H}} \newcommand {\SO }[0]{\operatorname {SO}} \newcommand {\Dten }[0]{D_{10}} \newcommand {\calC }[0]{\mathcal {C}} \newcommand {\calD }[0]{\mathcal {D}} \newcommand {\calF }[0]{\mathcal {F}} \newcommand {\calO }[0]{\mathcal {O}} \newcommand {\calP }[0]{\mathcal {P}} \newcommand {\calN }[0]{\mathcal {N}} \newcommand {\calR }[0]{\mathcal {R}} \newcommand {\calS }[0]{\mathcal {S}} \newcommand {\calX }[0]{\mathcal {X}} \newcommand {\rmZ }[0]{\mathrm {Z}} \newcommand {\rmC }[0]{\mathrm {C}} \newcommand {\rmH }[0]{\mathrm {H}} \newcommand {\trans }[0]{\mathrm {T}} \newcommand {\Span }[0]{\operatorname {Span}} \newcommand {\Rep }[0]{\operatorname {Rep}} \newcommand {\Vect }[0]{\operatorname {Vec}} \newcommand {\Obj }[0]{\operatorname {Obj}} \newcommand {\Adj }[0]{\operatorname {Adj}} \newcommand {\Aut }[0]{\operatorname {Aut}} \newcommand {\Hom }[0]{\operatorname {Hom}} \newcommand {\End }[0]{\operatorname {End}} \newcommand {\tr }[0]{\operatorname {tr}} \newcommand {\Stab }[0]{\operatorname {Stab}} \newcommand {\FPdim }[0]{\operatorname {FPdim}} \newcommand {\lcm }[0]{\mathrm {l.c.m}} \newcommand {\proj }[0]{\operatorname {proj}} \newcommand {\Repart }[0]{\operatorname {Re}} \newcommand {\Impart }[0]{\operatorname {Im}} \newcommand {\im }[0]{\operatorname {im}} \newcommand {\rk }[0]{\operatorname {rank}} \newcommand {\diag }[0]{\operatorname {diag}} \newcommand {\Zmod }[1]{\Z /#1 \Z } \newcommand {\Reptwo }[0]{\Rep (\Z /2\Z )} \newcommand {\qaH }[0]{\mathrm {H}_{\mathrm {qa}}} \newcommand {\abH }[0]{\mathrm {H}_{\mathrm {ab}}} \newcommand {\qaZ }[0]{\mathrm {Z}_{\mathrm {qa}}} \newcommand {\qaB }[0]{\mathrm {B}_{\mathrm {qa}}} \newcommand {\1}[0]{\mathbf {1}} \newcommand {\Ctimes }[0]{\mathbb {C}^{\times }} \newcommand {\HyperFirstAtBeginDocument }[0]{\AtBeginDocument }$

A linear combination is a sum of scalar multiples of vectors.

The operation of forming linear combinations of vectors is at the heart of Linear Algebra; it is, arguably, the central construct of the entire subject. And yet, it is relatively straightforward to describe.

Let $(V,+,\cdot )$ be a vector space, and ${\bf v}_1,\dots , {\bf v}_n\in V$ a collection of $n$ vectors in $V$ . Then a linear combination of ${\bf v}_1,\dots ,{\bf v}_n$ is a sum of scalar multiples of these vectors; in other words, a sum of the form $\begin{equation} \alpha_1{\bf v}_1 + \alpha_2{\bf v}_2 +\dots + \alpha_n{\bf v}_n \end{equation}$ for some choice of scalars $\alpha _1,\alpha _2,\dots ,\alpha _n$ . A vector $\bf v$ is a linear combination of ${\bf v}_1,\dots ,{\bf v}_n$ if it can be written in this form.

Suppose ${\bf v}_1 = [1\ 0\ 0]^T, {\bf v}_2 = [0\ 1\ 0]^T\in \mathbb R^3$ (we have written these column vectors as transposed row vectors). Then ${\bf v} = [2\ 5\ 0]^T = 2{\bf v}_1 + 5{\bf v}_2$ , so $\bf v$ is a linear combination of ${\bf v}_1,{\bf v}_2$ . On the other hand, ${\bf w} = [0\ 0\ 1]^T$ is not a linear combination of ${\bf v}_1,{\bf v}_2$ , since the $(3,1)$ -entry of $\bf w$ is non-zero, while any linear combination of ${\bf v}_1,{\bf v}_2$ would have a $(3,1)$ -entry equal to $0$ , regardless of the choice of scalars for coefficients.

In general, given vectors ${\bf v}_1,{\bf v}_2,\dots ,{\bf v}_n$ , it can be quite difficult to determine simply by inspection whether or not some other vector $\bf v$ is or is not a linear combination of the given collection. One of our goals, discussed in detail below, will be to establish some systematic way of answering this question.

A collection of vectors ${\bf v}_1,\dots ,{\bf v}_n$ is linearly independent if $\begin{equation} \alpha_1{\bf v}_1 + \alpha_2{\bf v}_2 +\dots + \alpha_n{\bf v}_n = {\bf z}\qquad \boldsymbol{\Longleftrightarrow}\qquad \alpha_1 = \alpha_2 = \dots = \alpha_n = 0 \end{equation}$ In other words, the only linear combination of the vectors that produces the zero vector is the trivial combination, where each coefficient $\alpha _i = 0$ .

A collection of vectors ${\bf v}_1,\dots ,{\bf v}_n$ is linearly dependent iff it is not linearly independent. More precisely,

A set of vectors ${\bf v}_1,\dots ,{\bf v}_n$ is linearly dependent precisely when there is a set of scalars $\alpha _1,\dots \alpha _n$ which are not all zero with $\alpha _1{\bf v}_1 + \alpha _2{\bf v}_2 +\dots + \alpha _n{\bf v}_n = {\bf z}$

Call the set $\{{\bf v}_1,\dots ,{\bf v}_n\}$ vectorwise independent if no vector in the set can be written as a linear combination of the remaining vectors in the set. The following lemma records the equivalence of these two concepts.

A collection of vectors $\{{\bf v}_1,\dots ,{\bf v}_n\}$ is linearly independent iff it is vectorwise independent.

Proof: Suppose $\alpha _1{\bf v}_1 + \alpha _2{\bf v}_2 +\dots + \alpha _n{\bf v}_n = {\bf z}$ is a linear combination of $\{{\bf v}_1,\dots ,{\bf v}_n\}$ equalling the zero vector. If $\alpha _i\ne 0$ for some $1\le i\le n$ , then this linear relation may be rewritten as ${\bf v}_i = \frac {-\alpha _1}{\alpha _i}{\bf v}_1 + \frac {-\alpha _2}{\alpha _i}{\bf v}_2 +\dots + \frac {-\alpha _{i-1}}{\alpha _i}{\bf v}_{i-1} + \frac {-\alpha _{i+1}}{\alpha _i}{\bf v}_{i+1}+\dots + \frac {-\alpha _n}{\alpha _i}{\bf v}_n$ from which we see that linear dependence implies the set is not vectorwise independent, or (via the contrapositive), (vectorwise independence) $\Rightarrow$ (linear independence). On the other hand, suppose the vectors are vectorwise dependent. Thus there must exist an index $i$ and scalars $\beta _j, j\ne i$ such that ${\bf v}_i = \beta _1{\bf v}_1 + \beta _2{\bf v}_2 +\dots + \beta _{i-1}{\bf v}_{i-1} + \beta _{i+1}{\bf v}_{i+1}+\dots + \beta _n{\bf v}_n$ or, equivalently ${\bf z} = \beta _1{\bf v}_1 + \beta _2{\bf v}_2 +\dots + \beta _{i-1}{\bf v}_{i-1} - {\bf v}_i + \beta _{i+1}{\bf v}_{i+1}+\dots + \beta _n{\bf v}_n$ from which we see that (vectorwise dependence) $\Rightarrow$ (linear dependence) or, again by contraposition, (linear independence) $\Rightarrow$ (vectorwise independence). $\blacksquare$

Following Example 1 above, show that the set of vectors $\{[1\ 0\ 0]^T, [0\ 1\ 0]^T\}$ is linearly independent, and that the set $\{[1\ 0\ 0]^T, [0\ 1\ 0]^T, [2\ 5\ 0]^T\}$ is linearly dependent.

Given a collection of vectors $S = \{{\bf v}_1,\dots {\bf v}_n\}$ , a fundamental question one can ask is whether the collection (or set) $S$ is linearly independent. One of our main goals in the following sections will be to develop numerical methods for answering this question.