§18 Vector Spaces

§18.1 Spanning Sets, Linear Independence, and Bases

Definition 18.1 Fix

x_{1},\ldots,x_{n}\in M.

(1) If the map

X:R^{n}\to M

is surjective, then we say that the set spans $M$ .

(2) If the map

X:R^{n}\to M

is injective, then we say that the set is linearly independent in $M$ .

(3) If $X$ is both injective and surjective, then we say that the set is a basis of $M$ .

You will recognize these terms from linear algebra. Expressed in terms of equations, these definitions are exactly what you would expect.

Proposition 18.1 Let $M$ be a left $R$ -module, and let

x_{1},\ldots,x_{n}\in M

be an ordered set.

(1) If for every

y\in M

there exist

a_{1},\ldots,a_{n}\in R

such that

y=a_{1}x_{1}+\cdots+a_{n}x_{n},

then the set spans $M$ .

(2) If the equation

0=a_{1}x_{1}+\cdots+a_{n}x_{n}

has the unique solution

(a_{1},\ldots,a_{n})=(0,\ldots,0),

then the set is linearly independent.

(3) If for every

y\in M,

the equation

y=a_{1}x_{1}+\ldots+a_{n}x_{n}

has a unique solution

(a_{1},\ldots,a_{n}),

then the set is a basis.

Proof: The first statement is simply the definition of surjectivity.

The second follows because a homomorphism is injective if and only if its kernel is trivial, and

(0,\ldots,0)\in R^{n}

is the additive identity of $R^n$ .

The final statement is the definition of a bijection.

~\tag*{$\square$}

Definition 18.2 A module is called finitely generated if there exists some integer

n\in\mathbb{Z}_{\geqslant0}

and a surjective $R$ -module homomorphism

R^{n}\to M.

This is analogous to the case of groups.

A group $G$ is finitely generated if and only if there exist finitely many elements $g_i$ such that every other element can be expressed as a product of the $g_i$ and their inverses.

Similarly, a module $M$ is finitely generated if there exist finitely many $x_i$ such that every element of $M$ can be obtained as a linear combination of the $x_i$ .

Example 18.1 Not every $R$ -module admits a basis.

This is different from the situation for vector spaces.

For example, let

R=\mathbb{Z}

and

M=\mathbb{Z}/n\mathbb{Z}.

Then for any

x\in M,

the equation

ax=0

has many solutions: $a$ may be

n,2n,\ldots.

Key Point: Not every finitely generated $R$ -module admits a basis.

§18.2 Vector Spaces and Subspaces

Definition 18.3 A commutative ring is called a field if

R-\{0\}

forms a group under multiplication.

Definition 18.4 Let $F$ be a field. A module over $F$ is called a vector space over $F$ .

Definition 18.5 Let $V$ be a vector space. A submodule of $V$ is called a linear subspace of $V$ .

§18.3 A Spanning Set Is at Least as Large as an Independent Set

The following is one of the most important differences between fields and general rings.

Theorem 18.2 Let $F$ be a field and let $M$ be a vector space over $F$ .

v_{1},\ldots,v_{n}

span $M$ , and

w_{1},\ldots,w_{m}

are linearly independent, then

n\geqslant m.

Proof: Let

y_{1},\ldots,y_{m}

be linearly independent, and let

v_{1},\ldots,v_{n}

span.

If necessary, reorder the $v_i$ so that

y_{1} = a_{1}v_{1} +\ldots+ a_{n}v_{n}

with

a_{1}\neq0.

Then

y_{1},v_{2},\ldots,v_{n}

also span $M$ , because we can express $v_1$ as a linear combination of $y_1$ and the other $v_i$ simply by dividing the equation above by $a_1\neq0$ and rearranging.

Let

M_{1}\subset M

be the submodule generated by $y_1$ , i.e. the image of

R\to M

defined by

1\mapsto y_1,

and consider the quotient module

M/M_1.

One can prove that this is an $R$ -module, hence a vector space.

Then

\overline{y_2},\ldots,\overline{y_m}

remain linearly independent, because a linear combination of them is zero if and only if

a_1y_1 = a_2y_2+\ldots+a_my_m

for some

a_1\in F,

and such an equation can hold only when all the $a_i$ are zero, since the $y_i$ are assumed to be linearly independent.

Notice that

\overline{y_1}=0, \qquad \overline{v_2},\ldots,\overline{v_n}

still span.

Therefore,

\overline{v_2},\ldots,\overline{v_n}

span

M/M_1.

Thus we have $n-1$ vectors spanning $M/M_1$ and $m-1$ linearly independent vectors in it.

Repeating this argument, if a vector space has $m$ linearly independent elements and is spanned by $n$ elements, then in a quotient vector space we obtain

m-k

linearly independent elements and

n-k

spanning elements.

Which of these numbers reaches $0$ first?

n-k=0

first, then we are in a quotient vector space spanned by $0$ elements, i.e. the zero vector space.

Therefore,

m-k=0,

because there are no linearly independent vectors in the zero vector space.

In this case,

m=n.

m-k

reaches zero before $n-k$ , then

m\leqslant n.

~\tag*{$\square$}

§18.4 Dimension

Corollary 18.3 If $M$ is a finitely generated vector space, then any two bases of $M$ contain the same number of elements.

Proof: If

\{v_i\}

and

\{w_i\}

are both spanning and linearly independent, then

n\geqslant m

and

m\geqslant n.

Therefore,

m=n.

~\tag*{$\square$}

Definition 18.6 Let $V$ be a finitely generated $F$ -module, i.e. a finitely generated vector space.

Such a $V$ is called a finite-dimensional vector space, and the dimension of $V$ is defined by

\dim_F V

to be the number of elements in any basis of $V$ .

Remark This is one of the most important facts in linear algebra: we have a notion of dimension.

It took humanity thousands of years to understand what an $n$ -dimensional space is, so do not take this concept lightly!

Example 18.2 The $0$ -dimensional vector space is the module given by the trivial Abelian group

M=\{0\}.

Corollary 18.4 If $M$ is a finitely generated vector space, then any linearly independent set

w_{1},\ldots,w_{m}

can be extended to a basis.

That is, we can find

w_{m+1},\ldots,w_{n}

such that

w_{1},\ldots,w_{n}

is both linearly independent and spanning.

Proof: Since $M$ is finitely generated, there exists some $N$ such that we have a surjection

F^N\to M.

Therefore, the size of any linearly independent set of vectors must be

\leqslant N.

X_m:F^m\to M

is the map determined by

w_1,\ldots,w_m

and $X_m$ is not surjective, choose an element

w_{m+1}

not lying in

\mathrm{im}(X_m).

Notice that the resulting set

w_1,\ldots,w_{m+1}

is still linearly independent.

Indeed, if

a_1w_1+\ldots+a_{m+1}w_{m+1} = 0,

then

a_1w_1+\ldots+a_mw_m = -a_{m+1}w_{m+1}.

a_{m+1}=0,

then the linear independence of the $w_i$ implies that all $a_i=0$ .

On the other hand, if

a_{m+1}\neq0,

then dividing gives the contradiction

\frac{a_1}{-a_{m+1}}w_1 +\ldots+ \frac{a_m}{-a_{m+1}}w_m = w_{m+1}.

The left-hand side lies in the image of $X_m$ , while $w_{m+1}$ was chosen not to lie in it.

Therefore, we obtain an injective homomorphism

X_{m+1}:F^{m+1}\to M.

If $X_{m+1}$ is not surjective, repeat the argument.

By the theorem, $X_{m+k}$ must become surjective for some

m+k\leqslant N.

Let $k$ be the first integer for which $X_{m+k}$ is surjective.

By the argument above, it is still injective.

Therefore, the generators

w_1,\ldots,w_{m+k}

determine a basis.

~\tag*{$\square$}

§18.5 Some Corollaries

What are we going to do with this?

You have already studied matrices with real entries.

You performed many operations on them: multiplication, addition, and determining when they are invertible.

I claim that almost everything you do with real matrices can also be done with matrices over any field.

Corollary 18.5 Every finitely generated module over a field $F$ is isomorphic to

F^n

for some $n$ .

Proof: Starting with the linearly independent set containing $0$ elements, extend it to a basis.

A basis defines an isomorphism from

F^n

to your module.

~\tag*{$\square$}

Remark If $R$ is not a field, this statement fails for $R$ -modules.

After all, every finite Abelian group is a $\mathbb{Z}$ -module, but every free $\mathbb{Z}$ -module is either the zero module or infinite.

Corollary 18.6 If

V^{\prime}\subset V

is a subspace, then

\dim V^{\prime} = \dim V \quad\Leftrightarrow\quad V=V^{\prime}.

Proof: One direction is obvious.

For the other direction, let

y_1,\ldots,y_n

be a basis of $V^{\prime}$ .

Since these vectors are linearly independent, one of the previous corollaries allows us to extend them to a basis of $V$ .

But by the definition of dimension, this basis must have exactly $n$ elements.

In other words, the $y_i$ already form a basis of $V$ .

~\tag*{$\square$}

Corollary 18.7 Let

V^{\prime}\subset V

be a subspace.

Then

\dim V^{\prime} + \dim V/V^{\prime} = \dim V.

Proof: Let

v_1,\ldots,v_{\dim V^{\prime}}

be a basis of $V^{\prime}$ .

Let

\overline{u_1}, \ldots, \overline{u_{\dim V/V^{\prime}}}

be a basis of

V/V^{\prime}.

Choose representatives $u_i$ for the $\overline{u_i}$ .

Then the set

v_1,\ldots,v_{\dim V^{\prime}}, u_1,\ldots,u_{\dim V/V^{\prime}}

is a basis of $V$ .

It clearly spans, because for every

a\in V,

the class

\overline{a}

is a linear combination of the $\overline{u_i}$ .

Therefore, $a$ lies in the $V^{\prime}$ -orbit of some such linear combination.

It is also linearly independent.

Indeed, if

0 = a_1v_1 +\cdots+ a_{\dim V^{\prime}}v_{\dim V^{\prime}} + b_1u_1 +\cdots+ b_{\dim V/V^{\prime}}u_{\dim V/V^{\prime}},

then

\overline{0} = a_1\overline{v_1} +\cdots+ a_{\dim V^{\prime}}\overline{v_{\dim V^{\prime}}} + b_1\overline{u_1} +\cdots+ b_{\dim V/V^{\prime}}\overline{u_{\dim V/V^{\prime}}}.

Since

\overline{v_i}=0,

the terms involving the $a_i$ vanish.

Thus we obtain an equation saying that a linear combination of the $\overline{u_i}$ is zero.

Since the $\overline{u_i}$ are linearly independent, every $b_i$ must be zero.

The original equation then becomes

0 = \sum a_iv_i.

Since the $v_i$ are linearly independent, all $a_i$ must also be zero.

~\tag*{$\square$}

Corollary 18.8 (Rank-Nullity Theorem)

Let

f:V\to W

be a map of $F$ -modules, and assume that $V$ is finitely generated.

Then

\dim\ker f + \dim\mathrm{im}f = \dim V.

Proof: By the fundamental theorem of homomorphisms, we know that there is a group isomorphism

V/\ker f \cong \mathrm{im}f.

But this homomorphism is also an $F$ -module map, as can be verified directly.

Therefore,

\mathrm{im}f \cong V/\ker f.

~\tag*{$\square$}

Corollary 18.9 (Criterion for Isomorphisms)

Let

f:V\to W

be a linear map between finite-dimensional vector spaces.

Then $f$ is an isomorphism if and only if $f$ is injective and

\dim V = \dim W.

Proof: By the Rank-Nullity Theorem, the dimension of the image of $f$ equals the dimension of $V$ because $f$ is injective.

~\tag*{$\square$}

§18.6 Summary

The main lesson from everything above is the power of the concept of dimension.

Whether your field is something familiar like $\mathbb{R}$ or something more unfamiliar like $\mathbb{Z}/p\mathbb{Z}$ ; whether your linear map is a familiar matrix or something like evaluation of polynomial functions, we have a powerful method for studying linear maps.

§18.7 Determinants

Another powerful tool from linear algebra is the concept of the determinant.

The determinant requires only notions of multiplication by $-1$ , i.e. taking additive inverses, multiplication of matrix entries, and addition.

Therefore, we should be able to define the determinant of a matrix whose entries lie in any ring $R$ .

It turns out that if the ring $R$ is not commutative, some formulas may fail because the order of multiplication matters.

Therefore, we restrict ourselves to commutative rings.

Definition 18.7 Let $R$ be a commutative ring.

A $k\times k$ matrix is a collection of elements

A_{ij}\in R

where

i\in1,\ldots,k, \qquad j\in1,\ldots,k.

We denote the matrix by

A=(A_{ij}).

Example 18.3 A $3\times3$ matrix over $R$ may be written in the usual way:

\begin{pmatrix} A_{11} & A_{12} & A_{13} \\ A_{21} & A_{22} & A_{23} \\ A_{31} & A_{32} & A_{33} \end{pmatrix}.

Definition 18.8 The ring of $k\times k$ matrices over $R$ , denoted

M_{k\times k}(R),

has addition defined by

(A_{ij})+(B_{ij}) = (A_{ij}+B_{ij}),

and multiplication defined by

(A_{ij})(B_{ij}) = \left( \sum_{l=1}^{k} A_{il}B_{lj} \right).

Thus addition is performed entrywise, while the $(i,j)$ entry of the product is the pairing of the $i$ th row of $A$ with the $j$ th column of $B$ .

Definition 18.9 (Cofactor Matrix)

Let $A$ be a $k\times k$ matrix.

The cofactor matrix associated with the $(i,j)$ entry of $A$ is the matrix obtained by deleting the $i$ th row and the $j$ th column of $A$ .

When $A$ is understood, we write

C_{i,j}

for the $(k-1)\times(k-1)$ matrix obtained from the cofactor associated with the $(i,j)$ entry of $A$ .

Definition 18.10 The determinant of a $1\times1$ matrix over $R$ is its unique entry

A_{11}.

Recursively, let $A$ be a $k\times k$ matrix.

The determinant of $A$ is defined by the sum

\det A = A_{11}\det C_{1,1} - A_{21}\det C_{2,1} + \cdots + (-1)^{1+k} A_{k1}\det C_{k,1}.

Using summation notation,

\det A := \sum_{i=1}^{k} (-1)^{i+1} A_{i1} \det C_{i,1}.

This defines a function

\det: M_{k\times k}(R) \to R.

Example 18.4 If $A$ is a $2\times2$ matrix, then

\det(A) = A_{11}A_{22} - A_{12}A_{21}.

We will not prove the following theorem, but the proofs you know over the real numbers work equally well in this general setting.

Theorem 18.10 Let $A$ and $B$ be $k\times k$ matrices.

Then

\det(A)\det(B) = \det(AB),

and

\det(A^{\mathrm{T}}) = \det(A).

Theorem 18.11 Let

\mathrm{adj}(A)

be the $k\times k$ matrix whose $(i,j)$ entry is

(-1)^{i+j} \det C_{j,i}.

Then

A\cdot(\mathrm{adj}A) = (\mathrm{adj}A)\cdot A = \det A\cdot I,

where

\det A\cdot I

is the diagonal matrix whose diagonal entries are the element

\det A\in R.

Remark If you have not seen the final statement of this theorem before, here is a brief sketch of the proof.

The $(i,j)$ entry of the first product is

\sum_{l=1}^{k} A_{il}(\mathrm{adj}A)_{lj} = \sum_{l=1}^{k} A_{il} (-1)^{j+l} \det C_{j,l}.

For example, the $(1,1)$ entry is exactly the definition of the determinant of $A$ .

Using the fact that exchanging two rows only changes the sign of the determinant, one can prove that every diagonal entry is equal to $\det A$ .

For the off-diagonal entries, observe that the sum above becomes the determinant of a matrix having two identical rows, and is therefore zero.

Corollary 18.12 Let

A\in M_{k\times k}(R).

Then $A$ is invertible if and only if

\det A\in R

has a multiplicative inverse.

Proof: Let

B = \det A^{-1} \mathrm{adj}A.

Then

BA = \det A^{-1} \mathrm{adj}A\cdot A = \det A^{-1} \det A\cdot I = I.

Similarly, one can prove

BA=I.

~\tag*{$\square$}

Example 18.5 If $A$ is a matrix with integer entries, then it has an inverse with integer entries if and only if

\det A=\pm1.

Example 18.6 Let $A$ be a matrix over

\mathbb{Z}/n\mathbb{Z}.

Then $A$ is invertible if and only if its determinant is relatively prime to $n$ .

Contents

§18 Vector Spaces

§18.1 Spanning Sets, Linear Independence, and Bases

§18.2 Vector Spaces and Subspaces

§18.3 A Spanning Set Is at Least as Large as an Independent Set

§18.4 Dimension

§18.5 Some Corollaries

§18.6 Summary

§18.7 Determinants