Saturday, May 20, 2006

Fields and Rings

In today's blog, I will talk about the assumptions behind the idea of a field. I use the concept of a field in the proof for the Division Algorithm for Polynomials.

Definition 1: Ring

A ring R is a nonempty set with two binary operations: addition (a + b) and multiplication (ab).

It has the following properties:

1. Commutative Rule for Addition: a + b = b + a

2. Associative Rule for Addition: (a + b) + c = a + (b + c)

3. Additive Identity: there exists a value 0 ∈ R such that a + 0 = a for all a ∈ R

4. Additive Inverse: for all elements a ∈ R, there exists a value -a ∈ R such that a + -a = 0.

5. Associative Rule for Multiplication: a(bc) = (ab)c

6. Distributive Rule: a(b + c) = ab + ac and (b + c)a = ba + ca

Definition 2: Commutative Ring

A ring that has the following additional property:

7. Commutative Rule for Multiplication: ab = ba

Definition 3: Field

A field is a commutative ring R with unity in which every nonzero element is a unit.

It has all the properties of a commutative ring plus:

8. Multiplicative Identity (unity): there exists a value 1 ∈ R such that such that a * 1 = a for all a ∈ R

9. Multiplicative Inverse (every nonzero element is a unit): for all nonzero elements a ∈ R, there exists an inverse a-1 ∈ R such that a*a-1 = 1.

Examples:

1. The set of integers Z is a commutative ring with unity 1. [See here for more information on the integers]

2. The set Zn is a commutative ring with unity 1. [See here for more information on modular arithmetic]

3. The set of 2x2 matrices with integer entries is a noncommutative ring with unity. [See here for more information on 2x2 matrices]

4. If p is prime, then the set Zp is a field. [See here for more information on modular arithmetic]

5. The set of rational numbers Q is a field.

6. The set of real numbers R is a field.

7. The set of complex numbers is a field. [See here for more information on complex numbers]

8. The set of Gaussian Integers is a ring. [See here for more information on Gaussian Integers]

9. The set of Eisenstein Integers is a ring. [See here for more information on Eisenstein Integers]

References

Division Algorithm for Polynomials

In today's blog, I will go over a result that I use in the proof for the Fundamental Theorem of Algebra.

Today's proof is taken from Joseph A. Gallian's Contemporary Abstract Algebra.

Theorem: Division Algorithm for Polynomials

Let F be a field, f(x), g(x) ∈ F[x] with g(x) ≠ 0.

Then there exists unique polynomials q(x), r(x) in F[x] such that f(x) = g(x)q(x) + r(x) and r(x)=0 or deg r(x) is less than deg g(x).

Proof:

(1) Let f(x) = g(x)q(x) + r(x) with g(x) ≠ 0

(2) If f(x) = 0 or deg f(x) is less than g(x), then q(x)=0, r(x)=f(x)

(3) So, we can assume that f(x) ≠ 0 and deg f(x) ≥ deg g(x)

(4) Let f(x) = anxn + ... + a0

(5) Let g(x) = bmxm + ... + b0

(6) Let f1(x) = f(x) - anbm-1xn-mg(x)

(7) We note that deg f1(x) is less than deg f(x) since:

f(x) - anbm-1xn-mg(x) =

= anxn + ... + a0 - anbm-1xn-m(bmxm + ... + b0) =

= ann - anxn + an-1xn-1 + ... + a0 - anbm-1bm-1xn-1 - ... - anbm-1b0xn-m =

= an-1xn-1 + ... + a0 - anbm-1bm-1xn-1 - ... - anbm-1b0xn-m

So that f1(x) has a degree of n-1 while f(x) has a degree of n.

(8) Now, we are ready to prove this theorem by induction.

(9) The assumption is true for deg f(x) = 0

deg f(x) is 0 → f(x)=C where C is a constant.

If deg g(x) is 0, then g(x) = D where D is a nonzero constant and q(x) = C/D and r(x)=0.

If deg g(x) is greater than 0, then q(x)=0 and r(x)=C.

(10) We can now assume that the assumption holds for all polynomials up to degree n-1.

(9) We see that:

f(x) = anbm-1xn-mg(x) + f1(x)

where the degree of f1(x) is n-1 [See step #7]

(10) But by the induction hypothesis (step #10), we can assume that there exists q1(x) and r1(x) where r1(x) has a degree lower than g(x).

(11) Therefore, we have:

anbm-1xn-mg(x) + f1(x) = anbm-1xn-mg(x) + q1(x)g(x) + r1(x) =

= [anbm-1xn-m + q1(x)]g(x) + r1(x)

(12) Which proves that degree r(x) is less than degree g(x) by principle of induction.

(13) Now, we still need to prove uniqueness of q(x),r(x)

(14) Suppose that:

f(x) = g(x)q(x) + r(x) = g(x)q'(x) + r'(x) where r(x),r'(x)=0 or deg r(x),r'(x) is less than deg g(x)

(15) Now, if we substract both equations, we get:

0 = g(x)[q(x) - q'(x)] + [r(x) - r'(x)]

which is the same as:

r'(x) - r(x) = g(x)[q(x) - q'(x)]

(16) Now since r'(x) and r(x) have degree less than g(x), the only way that this can be true is if r'(x) - r(x) = 0

(17) But then r'(x) = r(x) and q(x) = q'(x)

QED

References

Properties of cos θ + i sin θ

In today's blog, I will go over some basic trigonometric properties that I use in my proof for the Fundamental Theorem of Algebra.

Lemma 1: [(cos α + i sin α) ]a = cos (a*α) + i sin (a*α)

Proof:

(1) From Euler's Formula, we know that:

e = cos α + i sin (α)

(2) So, we see that:

(e)a = ei*a*α

(3) Finally,

ei(a*α) = cos (a*α) + i sin (a*α)

QED

Lemma 2: (cos α + i sin α)(cos β + i sin β) = cos(α + β) + i sin(α + β)

Proof:

(1) Again, using Euler's Formula, we have:

e = cos α + i sin α

e = cos β + i sin β

(2) So multiplying these two values together gives us [see here if a review of exponents are needed]:

(e)(e) = eiα + iβ = ei(α + β)

(3) Finally,

ei(α + β) = cos(α + β) + i sin(α + β)

QED

Argand Diagram

An Argand Diagram is a way of visualizing complex numbers. It involves graphing a complex number to the Cartesian coordinates.

There are two ways to represent a complex number:

x + iy

r (cos φ + i sin φ)

Both of these ways are equivalent since:

Here is the Argand Diagram:

One important point to remember is that in the r (cos φ + i sin φ) form, all values can be positive since r is an absolute magnitude and φ is a value between 0 and using radians (or in degrees, between 0 and 360).

References