Different algebraic systems are used in linear algebra. The most important are commutative rings with identity and fields.
Definition. A ring is a set R with two binary operations addition (denoted +) and multiplication (denoted ). These operations satisfy the following axioms:
1. Addition is associative: If , then
2. There is an identity for addition, denoted 0. It satisfies
3. Every every of R has an additive inverse. That is, if , there is an element which satisfies
4. Addition is commutative: If , then
5. Multiplication is associative: If , then
6. Multiplication distributes over addition: If , hen
It's common to drop the " " in " " and just write " ". I'll do this except where the " " is needed for clarity.
You'll study general rings in an abstract algebra course. The rings that occur in linear algebra satisfy some additional axioms.
Definition. A ring R is commutative if the multiplication is commutative. That is, for all ,
A ring R is a ring with identity if there is an identity for multiplication. That is, there is an element such that
A commutative ring which has an identity element is called a commutative ring with identity.
In a ring with identity, you usually also assume that . (Nothing stated so far requires this, so you have to take it as an axiom.) In fact, you can show that if in a ring R, then R consists of 0 alone --- which means that it's not a very interesting ring!
Example. Here are some number systems you're familiar with:
The integers .
The rational numbers .
The real numbers .
The complex numbers .
Each of these is a commutative ring with identity. In fact, all of them except are fields. I'll discuss fields below.
Example. ( The integers mod n) For this collection of examples, n will denote an integer. Actually, n can be any integer if I modify the discussion a little, but to keep things simple, I'll take .
The integers mod n is the set
n is called the modulus.
For example,
becomes a commutative ring with identity under the operations of addition mod n and multiplication mod n. I'm going to describe these operations in a functional way, which is sufficient for a linear algebra course. You'll see a rigorous treatment of in abstract algebra.
(a) To add x and y mod n, add them as integers to get . Then divide by n and take the remainder --- call it r. Then .
(b) To multiply x and y mod n, multiply them as integers to get . Then divide by n and take the remainder --- call it r. Then .
This is actually much easier to do than it is to describe! Here's an example. Suppose , so the ring is .
Hence, in .
Hence, in .
Notice that when you take the remainder after dividing by 6, you'll always wind up with a number in .
Other arithmetic operations work as you'd expect. For example,
Hence, in .
Negative numbers in are additive inverses. Thus, in , because . To deal with negative numbers in general, add a positive multiple of 6 to get a number in the set . For example,
Hence, in .
The reason you can add 18 (or any multiple of 6) is that 18 divided by 6 leaves a remainder of 0. In other words, " " in , so adding 18 is like adding 0.
Example. ( Addition and multiplication mod 5) Construct addition and multiplication tables for .
Notice in the multiplication table that
This means that , , and . In particular, to divide by 2 you multiply by 3: in , the elements 2 and 3 are reciprocals.
Commutative rings with identity come up in discussing determinants, but the algebraic system of greatest importance in linear algebra is the field.
Definition. Let R be a ring with identity, and let . The multiplicative inverse of x is an element which satisifies
Definition. A field F is a commutative ring with identity in which and every nonzero element has a multiplicative inverse.
By convention, you don't write " " for " " unless the ring happens to be , , or .
If an element x has a multiplicative inverse, you can divide by x by multiplying by . Thus, in a field, you can divide by any nonzero element. (You'll learn in abstract algebra why it doesn't make sense to divide by 0.)
Example. The rationals , the reals , and the complex numbers are fields. Many of the examples will use these number systems.
The ring of integers is not a field. For example, 2 is a nonzero integer, but it does not have a multiplicative inverse which is an integer. ( is not an integer --- it's a rational number.)
, , and are all infinite fields --- that is, they all have infinitely many elements. For applications, it's important to consider finite fields as well. Before I give some examples, I need some definitions.
Definition. Let R be a commutative ring with identity. The characteristic of R is the smallest positive integer n such that . Notation: .
If there is no positive integer n such that , then .
In fact, if , then for all .
, , , and are all rings of characteristic 0. On the other hand, .
Definition. An integer is prime if its only positive divisors are 1 and n.
The first few prime numbers are
An integer which is not prime is composite. The first few composite numbers are
The following important results are proved in abstract algebra courses.
Theorem. The characteristic of a field is either 0 or a prime number.
Theorem. If p is prime and n is a positive integer, there is a field of characteristic p having elements. This field is unique up to ring isomorphism, and is denoted (the Galois field of order ).
The only unfamiliar thing in the last result is the phrase "ring isomorphism". This is another concept whose precise definition you'll see in abstract algebra. The statement means, roughly, that any two fields with elements are "the same", in that you can get one from the other by just renaming or reordering the elements.
Since the characteristic of is n, the first theorem implies the following result:
Corollary. is a field if and only if n is prime.
Example. ( Fields of prime characteristic) , , and are fields, since 2, 3, and 61 are prime.
On the other hand, is not a field, since 6 isn't prime (because ). is a commutative ring with identity.
For simplicity, the fields of prime characteristic that I use in this course will almost always be finite. But what would an infinite field of prime characteristic look like?
As an example, start with . Form the field of rational functions . Thus, elements of have the form where and are polynomials with coefficients in . Here are some examples of elements of :
You can find multiplicative inverses of nonzero elements by taking reciprocals; for instance,
I won't go through and check all the axioms, but in fact, is a field. Moreover, since in , it's a field of characteristic 2. It has an infinite number of elements; for example, it contains
Example. ( A field with 4 elements) Here are the addition and multiplication tables for , the Galois field of order 4.
You can check by examining the multiplication table that multiplication is commutative, that 1 is the multiplicative identity, and that the nonzero elements (1, a, and b) all have multiplicative inverses.
Example. Find the multiplicative inverses of the nonzero elements of .
Since 5 is prime, is a field. This means that every nonzero element has a multiplicative inverse.
Example. Find in .
In , I have , so . You could do this by trial and error, since isn't that big:
Alternatively, you might reason this way: I want x so that . Now an integer equals 1 mod 13 if it is a multiple of 13 plus 1 (because mod 13 multiples of 13 equal 0). So I take multiples of 13 and add 1, stopping when I get a number divisible by 8:
Then , so .
Even this approach is too tedious to use with large numbers. The systematic way to find inverses is to use the Extended Euclidean Algorithm.
Example. (a) Show that 2 doesn't have a multiplicative inverse in .
(b) Show that 14 doesn't have a multiplicative inverse in .
(a) Try all possibilities:
Note that 4 isn't prime, and is not a field. This example shows it directly: 2 is nonzero, but 2 does not have a multiplicative inverse.
(b) I could do this by trial and error, but it would be tedious because 18 is a bit large. Instead, I'll show that there is no multiplicative inverse using proof by contradiction.
Suppose for . Then
(Note that in .) The last line above is a contradiction, so 14 does not have a multiplicative inverse in .
In general, the elements in which have multiplicative inverses are the elements which are relatively prime to n.
Example. Find the roots of in .
Make a table:
The roots are , , and .
You would normally not expect a quadratic to have 4 roots! This shows that algebraic facts you may know for real numbers may not hold in arbitrary rings (note that is not a field).
There are systematic ways for finding inverses of elements in --- for example, by using the Extended Euclidean Algorithm. I'll stick to simple cases where trial and error is sufficient.
Linear algebra deals with structures based on fields, and you've now seen most of the fields that will come up in the examples. To keep things simple, most of the example involving finite fields will use for p prime, rather than the more general Galois fields, or infinite fields of characteristic p.
Copyright 2016 by Bruce Ikenaga