Linear Dependence, Bases, and Dimension

Arun Ram
Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia
aram@unimelb.edu.au

Last update: 13 August 2013

Linear Dependence, Bases, and Dimension

Let $R$ be a ring and let $M$ be an $R\text{-module.}$ Let $S$ be a subset of $M\text{.}$

• The submodule generated by $S$ is the smallest submodule of $M$ containing $S\text{;}$ i.e. $\text{span}\left(S\right)$ is a submodule of $M$ such that

  (a)	$S\subseteq \text{span}\left(S\right),$
  (b)	If $N$ is a submodule of $M$ such that $S\subseteq N$ then $\text{span}\left(S\right)\subseteq N\text{.}$

• A module $M$ is finitely generated if there is a finite subset $S$ of $M$ such that $\text{span}\left(S\right)=M\text{.}$
• A vector space $V$ is finite dimensional if there is a finite subset $S$ of $V$ such that $\text{span}\left(S\right)=V\text{.}$
• A linear combination of elements of $S$ is an element $v\in M$ of the form $$v=\sum _{s\in S}{r}_{s}s,$$ where $r_s\in R$ are such that $r_s=0$ for all but a finite number of $s\in S\text{.}$
• The set $S$ is linearly independent if it satisfies the condition, $$\text{If}\sum _{s\in S}{r}_{s}s=0,\text{then}{r}_s=0,\text{for all}\hspace{0.17em}s\in S\text{.}$$
• The set $S$ is linearly dependent if it is not linearly independent.
• A basis of $M$ is a set $B\subseteq M$ such that

  a)	$\text{span}\left(B\right)=V,$ and
  b)	$B$ is linearly independent.

• A free module is an $R\text{-module}$ $M$ that has a basis.

HW: Show that $\text{span}\left(S\right)$ is the set of linear combinations of elements in $S\text{.}$

HW: Let $R$ be a commutative ring. Give an example of a finitely generated $R\text{-module}$ $M$ that does not have a basis.

Let $V$ be a vector space over a field $𝔽\text{.}$ Then $V$ has a basis.

Example. Let $R$ be the ring of infinite matrices with rows and columns indexed by ${\mathbb{Z}}_{>0},$ entries in $ℂ,$ and only a finite number of nonzero entries in each row,

$$R=\left\{\left(\begin{array}{cccc}{a}_{11}& a_{12}& a_{13}& \cdots \\ a_{21}& a_{22}& a_{23}& \cdots \\ a_{31}& a_{32}& \ddots \\ ⋮& & & \ddots \end{array}\right)\hspace{0.17em}\right|\hspace{0.17em}{a}_{ij}\in ℂ\},\text{and let}M=R$$

be the regular $R\text{-module.}$ Let

$$b_0=\left(\begin{array}{ccccc}1& 0& 0& 0& \cdots \\ 0& 1& 0& 0& \cdots \\ 0& 0& 1& 0& \cdots \\ 0& 0& 0& 1& \cdots \\ ⋮& & \ddots \end{array}\right),b_1=\left(\begin{array}{cccccc}1& 0& 0& 0& 0& \cdots \\ 0& 0& 1& 0& 0& \cdots \\ 0& 0& 0& 0& 1& \cdots \\ 0& 0& 0& 0& 0& \cdots \\ ⋮& & & & ⋮& \ddots \end{array}\right),b_2=\left(\begin{array}{ccccccc}0& 1& 0& 0& 0& 0& \cdots \\ 0& 0& 0& 1& 0& 0& \cdots \\ 0& 0& 0& 0& 0& 1& \cdots \\ 0& 0& 0& 0& 0& 0& \cdots \\ ⋮& 0& & & & ⋮& \ddots \end{array}\right)\text{.}$$

Then

$$B_1=\left\{b_0\right\}\text{and}{B}_2=\{b_1,b_2\}$$

are both bases of $M\text{.}$

(a)	Let $R$ be a ring and let $M$ be a free with an infinite basis. Any two bases of $M$ have the same number of elements.
(b)	Let $V$ be a vector space over a field $𝔽\text{.}$ Any two bases of $V$ have the same number of elements.
(c)	Let $R$ be a commutative ring and let $M$ be a free $R\text{-module.}$ Any two bases of $M$ have the same number of elements.

Let $R$ be a commutative ring and let $M$ be a free $R\text{-module.}$ Let $V$ be a vector space over a field $F\text{.}$

• The rank of $M$ is the number of elements in a basis of $M\text{.}$
• The dimension of $V$ is the number of elements in a basis of $V\text{.}$

Let $B$ be a set and let $R$ be a ring.

• The free module on the set $B$ is the $R\text{-module}$ $$R^B=\left\{\sum _{b\in B}{r}_{b}b\hspace{0.17em}\right|\hspace{0.17em}{r}_b\in R,\hspace{0.17em}\text{and all but a finite number of the}\hspace{0.17em}{r}_b\hspace{0.17em}\text{are equal to}\hspace{0.17em}0\},$$ with addition given by $$\left(\sum _{b\in B}{r}_{b}b\right)+\left(\sum _{b\in B}{s}_{b}b\right)=\sum _{b\in B}(r_b+s_b)b,$$ and $R\text{-action}$ given by $$r\sum _{b\in B}{r}_{b}b=\sum _{b\in B}\left(r{r}_b\right)b\text{.}$$

HW: Let $B$ be a set. Show that $R^B$ is a free $R\text{-module}$ with basis $B\text{.}$

Let $M$ be an $R\text{-module}$ and let $B$ be a subset of $M\text{.}$

(a)	There is an $R\text{-module}$ homomorphism $\varphi :R^B\to M$ such that $\varphi \left(b\right)=b\text{.}$
(b)	$M$ is generated by $B$ if and only if $M$ is a quotient of $R^B\text{.}$
(c)	$M$ is a free module with basis $B$ if and only if $M\cong R^B\text{.}$

Let $B$ and $C$ be sets. Let $R$ be a ring.

• A $C\times B$ matrix with entries in $R$ is a collection $F=\left(F_{cb}\right)$ of elements $F_{cb}\in R$ indexed by the elements of $C\times B$ and such that for each $b\in B$ all but a finite number of the $F_{cb}$ are $0\text{.}$
• $M_{C\times B}\left(R\right)=\{C\times B\hspace{0.17em}\text{matrices with entries in}\hspace{0.17em}R\}\text{.}$
• The sum of two matrices $F_1,F_2\in M_{C\times B}\left(R\right)$ is the matrix $F_1+F_2$ given by $${(F_1+F_2)}_{cb}={\left(F_1\right)}_{cb}+{\left(F_2\right)}_{cb},\text{for all}\hspace{0.17em}b\in B,c\in C\text{.}$$
• The product of matrices $F_1\in M_{D\times C}\left(R\right)$ and $F_2\in M_{C\times B}\left(R\right)$ is the matrix $F_1{F}_2\in M_{D\times B}\left(R\right)$ given by $${\left(F_1{F}_2\right)}_{db}=\sum _{c\in C}{\left(F_1\right)}_{dc}{\left(F_2\right)}_{cb},\text{for all}\hspace{0.17em}b\in B\hspace{0.17em}\text{and}\hspace{0.17em}d\in D\text{.}$$

Let $M$ and $N$ be free $R\text{-modules}$ with bases $B$ and $C,$ respectively. Let $f:M\to N$ be a homomorphism.

• The matrix of $f:M\to N$ with respect to $B$ and $C$ is the matrix ${}^{\circ }f\in M_{C\times B}\left(R^{\text{op}}\right)$ given by $${\left({}^{\circ }f\right)}_{cb}={\left(f_{cb}\right)}^{\text{op}}\text{where}\hspace{0.17em}{f}_{cb}\in R\hspace{0.17em}\text{are given by}f\left(b\right)=\sum _{c\in C}{f}_{cb}c,$$ for all $b\in B\text{.}$

Let $M$ and $N$ be free $R\text{-modules}$ with bases $B$ and $C,$ respectively.

(a)	The function $$\begin{array}{ccc}{\text{Hom}}_R(M,N)& ⟶& M_{C\times B}\left(R^{\text{op}}\right)\\ f& ⟼& {}^{\circ }f\end{array}$$ is an isomorphism of abelian groups.
(b)	The function $$\begin{array}{ccc}{\text{End}}_R\left(M\right)& ⟶& M_{B\times B}\left(R^{\text{op}}\right)\\ f& ⟼& {}^{\circ }f\end{array}$$ is a ring isomorphism.

HW: Discuss the difficulties in trying to make the map in Proposition ??? (a) into an $R\text{-modules}$ homomorphism, or into an $R^{\text{op}}\text{-module}$ isomorphism.

Let $M$ be a free module and let $B_o$ and $B_n$ be bases of $M\text{.}$

• The change of basis matrix is the matrix $T_{o\to n}$ given by $$b\in \sum _{c\in B_n}{\left(T_{o\to n}\right)}_{cb}c,\text{for all}\hspace{0.17em}b\in B_o\text{.}$$

Let $M$ be a free module with bases $B_o$ and $B_n$ and let $N$ be a free module with bases $C_o$ and $C_n\text{.}$ Then

$${{}^{\circ }f}_n=T_{o\to n}\left({{}^{\circ }f}_o\right)T_{n\to o}$$

Let $V$ be a vector space. Let $L,S$ be subsets of $V$ such that $L\subseteq S\subseteq$ such that $L$ is linearly independent and $\text{span}\left(S\right)=V\text{.}$ Then there exists a basis $B$ of $V$ such that $L\subseteq B\subseteq S\text{.}$

		Proof.
	Let $𝒞$ be the set of linearly independent subsets $L\subseteq C\subseteq S,$ partially ordered by inclusion. Let $B$ be a maximal element of $𝒞\text{.}$ To show: $B$ is a basis of $V\text{.}$ To show: (a) $\text{span}\left(B\right)=V\text{.}$ (b) $B$ is linearly independent. (a) Suppose that $\text{span}\left(B\right)\ne V\text{.}$ Let $s\in S$ such that $s\notin \text{span}\left(B\right)\text{.}$ Then $L\subseteq (B\cup \left\{s\right\})\subseteq S,$ and if there is a linear combination $${\xi }_{s}s+\sum _{b\in B}{\xi }_{b}b=0,\text{with}\hspace{0.17em}{\xi }_s\ne 0,\text{then}s={\xi }_s^{-1}\left(\sum _{b\in B}{\xi }_{b}b\right)\in \text{span}\left(B\right)\text{.}$$ Since $s\notin \text{span}\left(B\right),$ ${\xi }_s=0,$ but then since $B$ is linearly independent ${\xi }_b=0$ for all $b\in B\text{.}$ So $B\cup \left\{s\right\}$ is linearly independent. This is a contradiction to the maximality of $B\text{.}$ So $\text{span}\left(B\right)=V\text{.}$ (b) $B$ is linearly independent by definition. $\square$

Let $R$ be a ring and let $M$ be a free $R\text{-module.}$ If $M$ has an infinite basis, or $R$ is a field, or $R$ is a commutative ring, then any two bases of $M$ have the same number of elements.

		Proof.
	(a) Let $B$ be an infinite basis of $M\text{.}$ Let $C$ be a basis of $M\text{.}$ Define $r_{cb}\in R$ for $c\in C,$ $b\in B,$ by $$b=\sum _{c\in C}{r}_{cb}c\text{and let}{S}_b=\{c\in C\hspace{0.17em}|\hspace{0.17em}{r}_{cb}\ne 0\},$$ for each $b\in B\text{.}$ Then each $S_b$ is a finite subset of $C$ and $C\subseteq {\bigcup }_{b\in B}{S}_b$ since $C$ is a minimal spanning set. So $\text{Card}\left(C\right)\le {\aleph }_0\text{Card}\left(B\right)=\text{Card}\left(B\right)\text{.}$ The same argument shows that $\text{Card}\left(B\right)\le {\aleph }_0\text{Card}\left(C\right)\text{.}$ So $\text{Card}\left(B\right)=\text{Card}\left(C\right)\text{.}$ (b) By part (a) we may assume that $V$ has a finite basis $B\text{.}$ Let $C$ be another basis of $B\text{.}$ Let $b\in B\text{.}$ Then there is an element $c\in C$ such that $c\notin \text{span}(B-\left\{b\right\})\text{.}$ Then $B_1=(B-\left\{b\right\})\cup \left\{c\right\}$ is a basis with the same cardinality as $B\text{.}$ By repeating this process, we can create a basis $B\prime$ of $V$ which contains all the elements of $C$ and which has the same cardinality as $C\text{.}$ Thus $\text{Card}\left(B\right)\ge \text{Card}\left(C\right)\text{.}$ A similar argument with $C$ in place of $B$ give that $\text{Card}\left(B\right)\le \text{Card}\left(C\right)\text{.}$ (c) The case when $\text{Card}\left(B\right)$ is infinite is covered by part (a). We will show that if $B$ is a basis of $M$ then $\bar{B}=\{b+𝔪M\hspace{0.17em}|\hspace{0.17em}b\in B\}$ is a basis of $M/𝔪M$ as a vector space over $R/𝔪\text{.}$ Then the result will follow from part (b). Let $$\sum _i{\bar{r}}_i{\bar{b}}_i=0$$ where ${\bar{r}}_i\in R/𝔪$ and ${\bar{b}}_i\in M/𝔪M\text{.}$ Then $$0=\sum _i{\bar{r}}_i{\bar{b}}_i=\sum _i(r_i+𝔪)(b_i+𝔪M)=\left(\sum _i{r}_i{b}_i\right)+𝔪M\text{.}$$ So ${\sum }_i{r}_i{b}_i\in 𝔪M\text{.}$ So there are elements ${\ell }_j\in 𝔪,$ $m_j\in M$ and elements $c_{j_k}\in R$ such that $$\sum _i{r}_i{b}_i={\ell }_1{m}_1+\cdots {\ell }_s{m}_s=\sum _j{\ell }_j\sum _k{c}_{j_k}{b}_k=\sum _{j,k}{\ell }_j{m}_{j_k}{b}_k\text{.}$$ Since $B$ is linearly independent $$r_k=\sum _j{\ell }_j{c}_{j_k}\in 𝔪,\text{for each}\hspace{0.17em}k\text{.}$$ So ${\bar{r}}_k=0$ for each $k\text{.}$ So $\bar{B}$ is linearly independent. $\square$

Let $M$ and $N$ be free $R\text{-modules}$ with bases $B$ and $C,$ respectively.

(a)	The function $$\begin{array}{ccc}{\text{Hom}}_R(M,N)& ⟶& M_{B\times C}\left(R^{\text{op}}\right)\\ f& ⟼& {}^{\circ }f\end{array}$$ is a bijection.
(b)	The function $$\begin{array}{ccc}{\text{End}}_R\left(M\right)& ⟶& M_{B\times B}\left(R^{\text{op}}\right)\\ f& ⟼& {}^{\circ }f\end{array}$$ is a ring isomorphism.

		Proof.
	(b) In fact we shall show that if $M,$ $N$ and $P$ are free modules with bases $B,$ $C$ and $D$ respectively and if $f_1\in {\text{Hom}}_R(M,N)$ and $f_2\in {\text{Hom}}_R(N,P)$ then ${}^{\circ }\left(f_1{f}_2\right)={{}^{\circ }f}_1{{}^{\circ }f}_2\text{.}$ $$f_1\left(f_2\left(b\right)\right)=\sum _{c\in C}{\left(f_2\right)}_{cb}c{f}_1\left(c\right)=\sum _{c\in C}\sum _{d\in D}{\left(f_2\right)}_{cb}{\left(f_1\right)}_{dc}d=\sum _{d\in D}\left(\sum _{c\in C}{\left(f_2\right)}_{cb}{\left(f_1\right)}_{dc}\right)d\text{.}$$ So $${\left({}^{\circ }\left(f_1{f}_2\right)\right)}_{db}={\left(\sum _{c\in C}{\left(f_2\right)}_{cb}{\left(f_1\right)}_{dc}\right)}^{\text{op}}=\sum _{c\in C}{\left(f_1\right)}_{dc}^{\text{op}}{\left(f_2\right)}_{cb}^{\text{op}}=\sum _{c\in C}{\left({{}^{\circ }f}_1\right)}_{dc}{\left({{}^{\circ }f}_2\right)}_{cb}={\left({{}^{\circ }f}_1{{}^{\circ }f}_2\right)}_{db}$$ $\square$

HW: Discuss the difficulties in trying to make the map in Proposition ??? (a) into an $R\text{-modules}$ homomorphism, or into an $R^{\text{op}}\text{-module}$ isomorphism.

Let $M$ be a free module and let $B=\left\{b_i\right\}$ and $B\prime =\left\{b_j^{\prime }\right\}$ be bases of $M\text{.}$

• The change of basis matrix $P(B\prime ,B)$ is the matrix given by $$b_i=\sum _{j}P{(B,B\prime )}_{ij}{b}_j^{\prime },\text{for all}\hspace{0.17em}{b}_i\in B\text{.}$$

HW: Let $M$ be an $R\text{-module}$ and let $S\subseteq M$ be a subset of $M\text{.}$ Show that $\text{span}\left(S\right)$ exists and is unique by showing that $\text{span}\left(S\right)$ is the intersection of all of the submodules that contain $S\text{.}$

HW: Let M be an $R\text{-module.}$ Show that

$$\text{span}\left(S\right)=\left\{\sum _{m\in S}{r}_{m}m\hspace{0.17em}\right|\hspace{0.17em}{r}_m=0\hspace{0.17em}\text{for all but a finite number of}\hspace{0.17em}m\in S\}\text{.}$$

HW: Let $M$ be an $R\text{-module.}$ Show that a subset $S\subseteq M$ is linearly independent if and only if $S$ satisfies the following property:
If $r_m\in R$ such that $r_m=0$ for all but a finite number of $m\in M$ and ${\sum }_{m\in S}{r}_{m}m=0$ then $r_m=0$ for all $m\in M\text{.}$

HW: Let $V$ be a vector space over a field $F\text{.}$ Show that if $v\in V$ and $\{v_1,v_2,\cdots ,v_n\}$ is a basis of $V$ then there exist unique $c_i\in F$ such that $v=c_1{v}_1+c_2{v}_2+\cdots +c_n{v}_n\text{.}$

HW: Give an example of a finitely generated module over a commutative ring that does not have a basis.

HW: Give an example of a ring $R$ and a finitely generated module over $R$ that has two different finite bases with different numbers of elements.

page history