Linear Combinations and Spans

The finite sum of an indexed family. Linear combinations are formed by adding finitely many scalar multiples of vectors. To make this precise, we first define the sum of a finite indexed family in the general setting of a commutative monoid.

Definition 1.4.1. Let $$(M,+,0_M)$$ be a commutative monoid, and let $\{x_i\}_{i\in I}$ be a family of elements of $$M$$ indexed by a finite set $$I$.$ The sum of this family is defined recursively by

\[\begin{aligned} \sum_{i\in\varnothing}x_i &=0_M,\\ \sum_{i\in I}x_i &=x_j+\sum_{ i\in I\setminus\{j\}}x_i \quad \text{if } j\in I. \end{aligned}\]

The sum of a family indexed by the empty set is called the empty sum. When $$I=\{1,\ldots,n\}$,$ we also write the sum as $$\sum_{i=1}^{n}x_i$.$

Proposition 1.4.2. Let $$(M,+,0_M)$$ be a commutative monoid, and let $\{x_i\}_{i\in I}$ be a family in $$M$$ indexed by a finite set $$I$.$ Then the recursive rules in Definition 1.4.1 determine a unique element of $$M$.$ In particular, the resulting sum is independent of the choices of indices made during the recursion.

Proof. We proceed by strong induction on $$n=|I|$.$ If $$n=0$,$ then $$I=\varnothing$,$ and the recursive rules uniquely determine the sum to be $$0_M$.$ Now let $$n\ge 1$,$ and suppose that the recursive rules determine a unique element of $$M$$ for every family indexed by a set of cardinality less than $$n$.$ Let $$|I|=n$.$ For any $$j\in I$,$ the induction hypothesis and closedness under addition guarantees that

\[x_j+\sum_{i\in I\setminus\{j\}}x_i\]

is a well-defined element of $$M$.$ It remains to show that this element is independent of the choice of $$j$.$ Let $$j,k\in I$.$ If $$j=k$,$ there is nothing to prove. Otherwise, define $$R=I\setminus\{j,k\}$.$ Since $$R$,$ $$I\setminus\{j\}$,$ and $I\setminus\{k\}$ all have cardinality less than $$n$,$ their sums are uniquely determined by the induction hypothesis. Hence, by Definition 1.4.1 and associativity and commutativity of addition,

\[\begin{align} x_j+\sum_{i\in I\setminus\{j\}}x_i &=x_j+\lowparen{x_k+\sum_{i\in R}x_i}\\ &=x_k+\lowparen{x_j+\sum_{i\in R}x_i}\\ &=x_k+\sum_{i\in I\setminus\{k\}}x_i.\tag*{$\square$} \end{align}\]

Proposition 1.4.3. Let $$(M,+,0_M)$$ be a commutative monoid, and let $$I$$ be a finite set. If $$I=A\mathbin{\dot{\cup}} B$,$ then for every indexed family $\{x_i\}_{i\in I}$ in $$M$,$

\[\sum_{i\in I}x_i = \sum_{i\in A}x_i + \sum_{i\in B}x_i.\]

Proof. We proceed by induction on $$n=|B|$.$ If $$n=0$,$ then $B=\varnothing$ and $$I=A$.$ By Definition 1.4.1, we have

\[\begin{aligned} \sum_{i\in I}x_i &=\sum_{i\in A}x_i\\ &=\sum_{i\in A}x_i+0_M\\ &=\sum_{i\in A}x_i+\sum_{i\in B}x_i. \end{aligned}\]

Now suppose that the statement holds for $$n=k$.$ Let $$I=A\mathbin{\dot{\cup}} B$,$ and $$n=k+1$.$ Choose $$b\in B$,$ and define $$B'=B\setminus\{b\}$.$ Since $I\setminus\{b\}=A\mathbin{\dot{\cup}} B'$ and $$|B'|=k$,$ the induction hypothesis gives

\[\sum_{i\in I\setminus\{b\}}x_i = \sum_{i\in A}x_i+\sum_{i\in B'}x_i.\]

Therefore, by Definition 1.4.1, the induction hypothesis, and the associativity and commutativity of addition in $$M$,$

\[\begin{align} \sum_{i\in I}x_i &=x_b+\sum_{i\in I\setminus\{b\}}x_i\\ &=x_b+\lowparen{\sum_{i\in A}x_i+\sum_{i\in B'}x_i}\\ &=\sum_{i\in A}x_i+\lowparen{x_b+\sum_{i\in B'}x_i}\\ &=\sum_{i\in A}x_i+\sum_{i\in B}x_i.\tag*{$\square$} \end{align}\]

Proposition 1.4.3 shows that a finite sum can be decomposed into two sums over disjoint subsets of its index set. To generalize this to any finite number of groups, we may use a function to assign each index to a group: The fibers of the function determine a decomposition of the index set. The next theorem shows that summing within each group and then summing the resulting partial sums gives the original sum, independently of how the indices are grouped. It is a general principle underlying several fundamental properties of finite sums.

Theorem 1.4.4. Let $$(M,+,0_M)$$ be a commutative monoid, let $$I$$ and $$J$$ be finite sets, and let $f\colon I\to J$ be a function. Then, for every family $\{x_i\}_{i\in I}$ in $$M$,$

\[\sum_{i\in I}x_i = \sum_{j\in J} \lowparen{\sum_{i\in f^{-1}(j)}x_i} .\]

Proof. We proceed by induction on $$n=|J|$.$ If $$n=0$,$ then $$I=J=\varnothing$,$ so both sides equal $$0_M$.$ Now suppose that the statement holds for $$n=k$.$ Let $$|J|=k+1$$ and choose $$j'\in J$.$ Define $I'=I\setminus f^{-1}(\{j'\})$ and $$J'=J\setminus\{j'\}$,$ and let $g\colon I'\to J'$ be the restriction of $$f$$ to $$I'$.$ Then, by Proposition 1.4.3,

\[\sum_{i\in I}x_i = \sum_{i\in f^{-1}(j')}x_i + \sum_{i\in I'}x_i.\]

Since $$|J'|=k$,$ by the induction hypothesis and Definition 1.4.1,

\[\begin{align} \sum_{i\in I}x_i &= \sum_{i\in f^{-1}(j')}x_i + \sum_{j\in J'}\lowparen{\sum_{i\in g^{-1}(\{j\})}x_i}\\ &= \sum_{j\in J} \lowparen{\sum_{i\in f^{-1}(j)}x_i}.\tag*{$\square$} \end{align}\]

Reindexing replaces the indices of a family through a bijection without changing the terms being summed. Since a bijective grouping function has singleton fibers, reindexing is a special case of grouping. Thus, the invariance of finite sums under reindexing follows directly from Theorem 1.4.4.

Corollary 1.4.5. Let $$(M,+,0_M)$$ be a commutative monoid, let $$I$$ and $$J$$ be finite sets, and let $\varphi\colon J\to I$ be a bijection. Then, for every family $\{x_i\}_{i\in I}$ in $$M$,$

\[\sum_{i\in I}x_i = \sum_{j\in J}x_{\varphi(j)}.\]

Proof. Let $$f=\varphi^{-1}\colon I\to J$.$ By Theorem 1.4.4, we have

\[\sum_{i\in I}x_i = \sum_{j\in J}\lowparen{\sum_{i\in f^{-1}(j)}x_i}.\]

Since $\varphi$ is bijective, the fiber of $$f$$ over $$j$$ is the singleton $$\{\varphi(j)\}$.$ Hence

\[\begin{align} \sum_{i\in \{\varphi(j)\}}x_i &= x_{\varphi(j)} + 0_M\\ &= x_{\varphi(j)}, \end{align}\]

so we obtain the desired equality. $\square$

The following corollary is a concrete example showing that the results obtained by using distinct grouping functions are always the same.

Corollary 1.4.6. Let $$(M,+,0_M)$$ be a commutative monoid, and let $$n$$ be a nonnegative integer. Define $$K=\{(i,j):0\le i\le j\le n\}$.$ Then, for every family $\{x_{ij}\}_{(i,j)\in K}$ in $$M$,$

\[\sum_{i=0}^{n}\sum_{j=i}^{n}x_{ij} = \sum_{j=0}^{n}\sum_{i=0}^{j}x_{ij}.\]

Proof. Let $I = \{0,\ldots, n\}$ and define

\[f\colon K\to I, \qquad (i,j)\mapsto i.\]

By Theorem 1.4.4,

\[\sum_{k\in K}x_k = \sum_{i=0}^n \lowparen{\sum_{k\in f^{-1}(i)}x_k}.\]

Let $J_i = \{i,\ldots,n\}$ and define

\[\varphi_i\colon J_i \to f^{-1}(i),\qquad j\mapsto (i,j).\]

Since $\varphi_i$ is bijective, by Corollary 1.4.5,

\[\sum_{k\in K}x_k = \sum_{i=0}^{n}\sum_{j=i}^{n}x_{ij}.\]

Similarly, we have

\[\sum_{k\in K}x_k = \sum_{j=0}^{n}\sum_{i=0}^{j}x_{ij}.\]

Therefore,

\[\sum_{i=0}^{n}\sum_{j=i}^{n}x_{ij} = \sum_{j=0}^{n}\sum_{i=0}^{j}x_{ij}. \tag*{$\square$}\]

We now return to vector spaces and examine how finite summation interacts with vector addition and scalar multiplication. These properties will be useful in studying linear combinations.

Proposition 1.4.7. Let $$V$$ be a vector space over a field $$F$,$ and let $$I$$ be a finite set. Then the following hold:

For any families $\{u_i\}_{i\in I}$ and $\{v_i\}_{i\in I}$ in $$V$,$
\[\sum_{i\in I}(u_i+v_i) = \sum_{i\in I}u_i + \sum_{i\in I}v_i.\]
For any family $\{v_i\}_{i\in I}$ in $$V$$ and any scalar $$a\in F$,$
\[\sum_{i\in I}av_i = a\sum_{i\in I}v_i.\]
For any family $\{a_i\}_{i\in I}$ in $$F$$ and any vector $$v\in V$,$
\[\sum_{i\in I}a_iv = \lowparen{\sum_{i\in I}a_i}v.\]

Proof. (1) We proceed by induction on $$n=|I|$.$ If $$n=0$,$ then both sides equal $$0_V$.$ Now suppose that the statement holds for $$n=k$.$ Let $$|I|=k+1$,$ and choose $$i'\in I$.$ Put $$I'=I\setminus\{i'\}$.$ By Definition 1.4.1, the induction hypothesis, and associativity and commutativity of addition,

\[\begin{align} \sum_{i\in I}(u_i+v_i) &= (u_{i'} + v_{i'}) + \sum_{i\in I'} (u_i+v_i)\\ &= (u_{i'} + v_{i'}) + \lowparen{\sum_{i\in I'}u_i + \sum_{i\in I'}v_i}\\ &=\lowparen{u_{i'} + \sum_{i\in I'}u_i} + \lowparen{v_{i'} + \sum_{i\in I'}v_i}\\ &=\sum_{i\in I}u_i + \sum_{i\in I}v_i. \end{align}\]

(2) We proceed by induction on $$n=|I|$.$ If $$n=0$,$ both sides equal $$0_V$,$ since $$a0_V=0_V$.$ Now suppose that the statement holds for $$n=k$.$ Let $$|I|=k+1$,$ and choose $$i'\in I$.$ By Definition 1.4.1, distributivity of scalar multiplication over addition, and the induction hypothesis,

\[\begin{align} a\sum_{i\in I}v_i &=a\lowparen{v_{i'}+\sum_{i\in I\setminus\{i'\}}v_i}\\ &=av_{i'}+a\sum_{i\in I\setminus\{i'\}}v_i\\ &=av_{i'}+\sum_{i\in I\setminus\{i'\}}av_i\\ &=\sum_{i\in I}av_i. \end{align}\]

(3) We proceed by induction on $$n=|I|$.$ If $$n=0$,$ both sides equal $$0_V$,$ since $$0v=0_V$.$ Now suppose that the statement holds for $$n=k$.$ Let $$|I|=k+1$,$ and choose $$i'\in I$.$ By Definition 1.4.1, distributivity with respect to scalar addition, and the induction hypothesis,

\[\begin{align} \lowparen{\sum_{i\in I}a_i}v &=\lowparen{a_{i'}+\sum_{i\in I\setminus\{i'\}}a_i}v\\ &=a_{i'}v+\lowparen{\sum_{i\in I\setminus\{i'\}}a_i}v\\ &=a_{i'}v+\sum_{i\in I\setminus\{i'\}}a_iv\\ &=\sum_{i\in I}a_iv.\tag*{$\square$} \end{align}\]

Definitions of linear combinations and spans. Moving on to our main topic, we now define linear combinations and spans using finite sums.

Definition 1.4.8. Let $$V$$ be a vector space over $$F$.$ Given a finite set $$I$$ and indexed families $\{u_i\}_{i\in I}$ in $$V$$ and $\{a_i\}_{i\in I}$ in $$F$,$ the sum

\[\sum_{i\in I}a_iu_i\]

is called a linear combination of $$\{u_i\}_{i\in I}$.$ The scalars $$a_i$$ are called the coefficients of the linear combination. For a subset $$S\subseteq V$,$ a vector $v\in V$ is called a linear combination of vectors in $$S$$ if there exist a finite set $$I$$ and indexed families $\{s_i\}_{i\in I}$ in $$S$$ and $\{a_i\}_{i\in I}$ in $$F$$ such that

\[v=\sum_{i\in I}a_is_i.\]

Definition 1.4.9. Let $$V$$ be a vector space over $$F$,$ and let $$S\subseteq V$.$ The span of $$S$$ is the set

\[\operatorname{span}(S) = \left\lbrace v\in V : v\text{ is a linear combination of vectors in } S \right\rbrace.\]

If $$W$$ is a subspace of $$V$$ and $$\operatorname{span} (S) = W$,$ then the set $$S$$ is called a generating set for $$W$.$

Example 1.4.10. For a single vector $$v\in V$,$

\[\operatorname{span}\{v\}=\{av:a\in F\}.\]

If $$v=0_V$,$ this is the zero subspace. In real vector space $$\mathbb R^k$,$ the span of a nonzero vector is the line through the origin in the direction of that vector.

Example 1.4.11. The matrices

\[\begin{pmatrix} 1 & 0\\ 0& 0\end{pmatrix},\quad \begin{pmatrix} 0 & 1\\ 0& 0\end{pmatrix}, \quad \begin{pmatrix} 0 & 0\\ 1& 0\end{pmatrix}, \quad \text{and} \quad \begin{pmatrix} 0 & 0\\ 0& 1\end{pmatrix}\]

generate $\operatorname{Mat}_{2\times 2}(\mathbb R)$ since for any $2\times 2$ matrix the following holds:

\[\begin{pmatrix} a_{11} & a_{12}\\ a_{21}& a_{22}\end{pmatrix} = a_{11} \begin{pmatrix} 1 & 0\\ 0& 0\end{pmatrix} + a_{12}\begin{pmatrix} 0 & 1\\ 0& 0\end{pmatrix} + a_{21}\begin{pmatrix} 0 & 0\\ 1& 0\end{pmatrix} + a_{22}\begin{pmatrix} 0 & 0\\ 0& 1\end{pmatrix}.\]

On the other hand, consider the matrices

\[A=\begin{pmatrix}1&0\\0&1\end{pmatrix},\quad B=\begin{pmatrix}1&1\\0&1\end{pmatrix}, \quad \text{and} \quad C=\begin{pmatrix}1&0\\1&1\end{pmatrix}.\]

Their linear combinations have the form

\[\alpha A+\beta B+\gamma C =\begin{pmatrix} \alpha+\beta+\gamma&\beta\\ \gamma&\alpha+\beta+\gamma \end{pmatrix}.\]

The two diagonal entries are always equal, so these matrices do not generate $$\operatorname{Mat}_{2\times 2}(\mathbb R)$.$ It follows that

\[\operatorname{span}\{A,B,C\} =\left\{ \begin{pmatrix}t&u\\v&t\end{pmatrix} :t,u,v\in\mathbb R \right\}.\]

Thus the same subspace can be described by a condition on its elements or by a set of vectors that generates it. The condition identifies which vectors belong to the subspace; the generating set identifies the vectors from which the elements of the subspace can be built.

Example 1.4.12. Let $$n$$ be a nonnegative integer. The polynomial subspace $$F_n[x]$$ from Example 1.3.4 has $\{1,x,\ldots,x^n\}$ as a generating set:

\[F_n[x]=\operatorname{span}\{1,x,\ldots,x^n\}.\]

By definition, a vector $$v$$ belongs to $\operatorname{span}(S)$ if and only if it can be expressed as a linear combination of vectors in $$S$.$ However, the same vector in $$S$$ may occur at several indices, and the corresponding coefficients can be combined without changing the sum. This suggests an essentially concise characterization of span membership: the existence of a representation of $$v$$ in terms of $$S$.$ We formalize this idea through finitely supported functions.

Definition 1.4.13. Let $$S$$ be a subset of a vector space $$V$$ over a field $$F$,$ and let $$v\in V$.$ A representation of $$v$$ in terms of $$S$$ is a function $a\colon S\to F$ with finite support such that

\[v=\sum_{s\in\operatorname{supp}(a)}a(s)s,\qquad \operatorname{supp}(a)=\{s\in S:a(s)\neq 0\}.\]

Proposition 1.4.14. Let $$S$$ be a subset of a vector space $$V$$ over a field $$F$,$ and let $$v\in V$.$ Then, $v\in \operatorname{span}(S)$ if and only if $$v$$ has a representation in terms of $$S$.$

Proof. If $$v\in \operatorname{span}(S)$,$ Definition 1.4.8 gives a finite set $$I$$ and indexed families $\{s_i\}_{i\in I}$ in $$S$$ and $\{a_i\}_{i\in I}$ in $$F$$ such that

\[v=\sum_{i\in I}a_is_i.\]

Put $J=\{s_i:i\in I\}$ and define $a\colon S\to F$ by

\[a(s)=\sum_{\substack{i\in I\\s_i=s}}a_i.\]

If $$s\notin J$,$ the defining sum is empty, so $$a(s)=0$.$ Hence $\operatorname{supp}(a)\subseteq J$ is finite. By Theorem 1.4.4 applied to $$i\mapsto s_i$,$ Proposition 1.4.7(3), and Proposition 1.4.3,

\[\begin{aligned} v&=\sum_{i\in I}a_is_i\\ &=\sum_{s\in J}\sum_{\substack{i\in I\\s_i=s}}a_is\\ &=\sum_{s\in J}a(s)s\\ &=\sum_{s\in\operatorname{supp}(a)}a(s)s. \end{aligned}\]

Thus $$a$$ is a representation of $$v$$ in terms of $$S$.$ The converse is trivial. $\square$