4 Linear algebra 4 Linear algebra 4.2 Vector spaces

4.1 Fields

This part of the module is about generalizing what we know about matrices and vectors.

When we talk about vectors, or matrices, there’s an important thing we have to decide: where do the entries come from? For example, we might work with matrices with real numbers as entries, or with complex numbers as entries. We never really discussed this in the first part of the module, because it doesn’t make any difference to the theory we developed. So it’s natural to ask which other kinds of numbers we could use as entries in our vectors and matrices and still have everything work OK.

The answer is that the entries must come from what is called a field. Roughly speaking, a field is a set with multiplication and addition operations that obey the usual rules of algebra, and where you can divide by any non-zero element. Examples are $\mathbb{R}$ , the set of all real numbers, $\mathbb{C}$ , the set of all complex numbers, $\mathbb{Q}$ , the set of all rational numbers. Non-examples are $\mathbb{Z}$ : you can’t divide by 2 in $\mathbb{Z}$ , and $M_{2\times 2}(\mathbb{R})$ , the set of all $2\times 2$ real matrices, again because we know there are non-zero $2\times 2$ matrices which aren’t invertible.

The usual way to define a field is to write down a list of axioms. Everything that satisfies the axioms is a field. If you do want to know the field axioms, here they are: you can read them here.

The next section is about an important family of fields we have not seen yet.

4.1.1 Finite fields of prime order

Let $p$ be a prime number. Then $\mathbb{F}_{p}$ , the finite field of order $p$ , is the set $\{0,1,2,\ldots,p-1\}$ with addition and multiplication exactly the same as for ordinary whole numbers, except that we regard all multiples of $p$ as equal to 0.

This is easier to understand in an example. Let’s work in $\mathbb{F}_{5}$ . Then

•

$3+4=7=2$ because $5=0$ in $\mathbb{F}_{5}$ . Similarly,
•

$3+2=0$ ,
•

$4\times 3=12=2$ .

We can deal with subtractions and negative numbers too:

•

$3-4=-1=-1+5=4$
•

$4\times(-3)=-12=-12+15=3$ .

4.1.2 Addition and multiplication tables

There’s an easy way to summarize all the possible additions and multiplications in $\mathbb{F}_{5}$ : draw tables with rows and columns labelled by $0,1,2,3,4$ , and in row $i$ and column $j$ put the result of $i+j$ or $i\times j$ .

+	0	1	2	3	4
0	0	1	2	3	4
1	1	2	3	4	0
2	2	3	4	0	1
3	3	4	0	1	2
4	4	0	1	2	3

Table 4.1: Addition table for

\mathbb{F}_{5}

$\times$	1	2	3	4
0	0	0	0	0
1	1	2	3	4
2	2	4	1	3
3	3	1	4	2
4	4	3	2	1

Table 4.2: Multiplication table for

\mathbb{F}_{5}

Here are the addition and multiplication tables for $\mathbb{F}_{3}$ .

+	0	1	2
0	0	1	2
1	1	2	0
2	2	0	1

Table 4.3: Addition table for

\mathbb{F}_{3}

$\times$	1	2
0	0	0
1	1	2
2	2	1

Table 4.4: Multiplication table for

\mathbb{F}_{3}

4.1.3 Multiplicative inverses

In a field, you have to be able to divide by non-zero elements. Being able to divide by $x$ is equivalent to the existence of an element $1/x$ or $x^{-1}$ , called a multiplicative inverse to $x$ (because $y/x$ is just $y\times 1/x$ ). So to check that we can divide, we need to check that for each nonzero $x$ there is another element which you can multiply $x$ by to get 1. We will do this for the examples of $\mathbb{F}_{3}$ and $\mathbb{F}_{5}$ .

In $\mathbb{F}_{3}$ , you can see from the table that

•

$1\times 1=1$ , so $1^{-1}=1$
•

$2\times 2=1$ , so $2^{-1}=2$

and so every non-zero element of $\mathbb{F}_{3}$ has a multiplicative inverse.

In $\mathbb{F}_{5}$ , you can see from the table that

•

$1\times 1=1$ , so $1^{-1}=1$
•

$2\times 3=1$ , so $2^{-1}=3$ and $3^{-1}=2$
•

$4\times 4=1$ , so $4^{-1}=4$ .

and so every non-zero element of $\mathbb{F}_{5}$ has a multiplicative inverse.

We’re going to give a proof that every element of $\mathbb{F}_{p}$ has a multiplicative inverse and give a method for finding these multiplicative inverses.

First, here is a reminder about division with remainder. There is a fundamental fact about the natural numbers: if you have any two positive whole numbers $x$ and $y$ , you can try to divide $x$ by $y$ . When you do that you get a quotient $q$ and a remainder $r$ , which is a nonnegative integer less than $y$ :

\displaystyle x

\displaystyle=qy+r

\displaystyle 0\leqslant r<y

It’s easy to convince yourself of the truth of this by imagining starting at zero on the number line and taking steps of size $y$ to the right, stopping when the next step would take you past $x$ . Call the number of steps taken at the point you stop $q$ . You’ve stopped at the number $q y$ , and the distance from this point to $x$ , which is the remainder $r=x-qy$ , must be less than $y$ since otherwise you could take another full step without passing $x$ .

Theorem 4.1.1.

Let $p$ be prime and $0<a<p$ be a whole number. Then there are whole numbers $s$ and $t$ such that $as+pt=1$ .

Proof.

Let $g$ be the smallest positive number that can be written as an integer multiple of $p$ plus an integer multiple of $a$ , so $g=as+pt$ for some integers $s$ and $t$ . Note that $g<p$ since $p-a$ is a positive number that can be written this way. Divide $p$ by $g$ to get quotient $q$ and remainder $r$ , so $p=qg+r$ where $0\leqslant r<g$ . Then

	$\displaystyle r$	$\displaystyle=p-qg$
		$\displaystyle=p-q(as+pt)$
		$\displaystyle=(1-qt)p-qsa.$

Since $0\leqslant r<g$ and $g$ is the smallest positive number that can be written as a multiple of $p$ plus a multiple of $a$ we must have $r=0$ , that is, $g$ divides the prime number $p$ . Since $g<p$ we have $g=1$ . ∎

We can even calculate numbers $s$ and $t$ satisfying $as+pt=1$ quickly. To do this divide $p$ by $a$ , getting a quotient $q_{2}$ and a remainder $r_{2}$

p=q_{2}a+r_{2}\;\;0\leqslant r_{2}<a

(we start with a subscript 2 here because we will think of $p$ as $r_{0}$ and $a$ as $r_{1}$ ). If $r_{2}=0$ , stop. Otherwise divide $a$ by $r_{2}$ getting a quotient $q_{3}$ and remainder $r_{3}$

a=q_{3}r_{2}+r_{3}\;\;0\leqslant r_{3}<r_{2}

If $r_{3}=0$ , stop. Otherwise divide $r_{2}$ by $r_{3}$ getting a quotient $q_{4}$ and remainder $r_{4}$ :

r_{2}=q_{4}r_{3}+r_{4}\;\;0\leqslant r_{4}<r_{3}

If $r_{4}=0$ , stop. Otherwise divide $r_{3}$ by $r_{4}$ getting quotient $q_{5}$ and remainder $r_{5}$ :

r_{3}=q_{5}r_{4}+r_{5}\;\;0\leqslant r_{5}<r_{4}

and so on. The sequence $r_{2},r_{3},\ldots$ satisfies

a>r_{2}>r_{3}>r_{4}>r_{5}>\cdots\geqslant 0

You can’t have a decreasing sequence of positive integers that goes on forever, so there is some $m$ such that $r_{m}=0$ . The last few divisions were

$\displaystyle r_{m-5}$	$\displaystyle=q_{m-3}r_{m-4}+r_{m-3}$	(4.1)
$\displaystyle r_{m-4}$	$\displaystyle=q_{m-2}r_{m-3}+r_{m-2}$	(4.2)
$\displaystyle r_{m-3}$	$\displaystyle=q_{m-1}r_{m-2}+r_{m-1}$	(4.3)
$\displaystyle r_{m-2}$	$\displaystyle=q_{m}r_{m-1}+0$	(4.4)

We claim that $r_{m-1}=1$ . For $r_{m-1}$ divides $r_{m-2}$ , because of the last equation. In (4.3) the terms on the right hand side are multiples of $r_{m-1}$ , so the left hand side $r_{m-3}$ is a multiple of $r_{m-1}$ as well. Repeating the same argument we end up with $r_{m-1}$ dividing all the left-hand-sides, in particular, $r_{m-1}$ divides the prime number $p$ . Since $r_{m-1}<a<p$ we have $r_{m-1}=1$ . So (4.3) is really

r_{m-3}=q_{m-1}r_{m-2}+1

or equivalently

r_{m-3}-q_{m-1}r_{m-2}=1.

(4.5)

Now we can express $r_{m-3}$ in terms of $r$ s with a smaller subscript with equation (4.1), and we can express $r_{m-2}$ in terms of $r$ s with a smaller subscript using (4.2). When we substitute this in (4.5), we get $1=$ some multiple of $r_{m-3}$ plus some multiple of $r_{m-4}$ . And we can keep doing that over and over again until we eventually get $1=$ a multiple of $r_{1}$ plus a multiple of $r_{0}$ , that is, $as+pt$ for some whole numbers $s$ and $t$ .

It helps to see an example. Take $p=13$ and $a=5$ . We have

	$\displaystyle 13$	$\displaystyle=2\times 5+3$
	$\displaystyle 5$	$\displaystyle=1\times 3+2$
	$\displaystyle 3$	$\displaystyle=1\times 2+1$
	$\displaystyle 2$	$\displaystyle=2\times 1+0$

and so

	$\displaystyle 1$	$\displaystyle=3-1\times 2$
		$\displaystyle=(13-2\times 5)-1\times(5-1\times 3)$
		$\displaystyle=(13-2\times 5)-1\times(5-1\times(13-2\times 5))$
		$\displaystyle=2\times 13-5\times 5$

This helps us find multiplicative inverses in $\mathbb{F}_{p}$ because if $as+pt=1$ then in $\mathbb{F}_{p}$ we have, since multiples of $p$ are equal to zero, $as=1$ and $s$ is the multiplicative inverse of $a$ . In our example, $p=13,a=5,s=-5,t=2$ , so the multiplicative inverse of $5$ in $\mathbb{F}_{13}$ is $-5$ which is the same as $8$ .