Symbolic Computing

LT20, 4:00-6:00pm
Wed, 12 March 2003

Some more examples

Here is an example of a group.   Consider permutation of three objects.  Let call it 1, 2, 3.    A permutation is one-to-one and onto mapping of the set 1, 2, 3.    We'll use the notation P = (1,2,3 -> i,j,k) for a general permutation.   There are altogether 3! = 6 possible permutations for three objects.  There are

p1 = (1,2,3 ->1,2,3)   (no permutation)
p2 = (1,2,3 -> 2,3,1)  (cyclic)
p3 = (1,2,3 -> 3,1,2)
p4 = (1,2,3 -> 3,2,1)
p5 = (1,2,3 -> 2,1,3)
p6 = (1,2,3 -> 1,3,2)

We define ∘ to be a map that is the composite of the two.
Thus  p2 ∘ p3  is to apply map p3 first, then p2.   
p3 = (1,2,3 -> 3,1,2),  p2 = (1,2,3 -> 2,3,1)
thus p2 ∘ p3 = (1,2,3 -> 1,2,3) = p1
This is because 1 is mapped to 3 by p3, and then 3 is mapped to 1 by p2.  So p2 ∘ p3 map 1 to 1.  
   by p3                     by p2              by p3 ∘ p2 = p1
1   ->   3                  1  -> 2             1 -> 3  -> 1
2   ->   1                  2  -> 3             2 -> 1  -> 2
3   ->   2                  3  -> 1             3 -> 2  -> 3

The set {p1, p2, p3, p4, p5, p6} with the multiplication defined above form a group.   This group is known as (Subscript[S, 3]), the permutation group of 3 objects.  The concept can be generalized to permutation of n objects, (Subscript[S, n]).   In (Subscript[S, 3]), p1 is the identity, the inverse of p2 is p3.    Permutation is one of the fundamental concepts in group theory.   Each row or column of a group multiplication table is a permutation of the elements.

Work out the multiplication table of (Subscript[S, 3]).

An example of a ring

((Subscript[Z, 4]);  +, *), the set of integers modulo 4, i.e., the numbers 0, 1, 2, 3.   With modulo 4, 4 is considered equivalent to 0, 5 is considered equivalent to 1.   Any integer n is considered equivalent to  n mod 4.     There are two operations defined, addition +, and multiplication, all modulo 4.   The + and * tables are shown below:

+  |  0    1    2    3                              *  |   0    1     2     3
_____________                            ________________
0  |  0    1    2    3                             0   |   0    0     0     0
1  |  1    2    3    0                             1   |   0    1     2     3
2  |  2    3    0    1                             2   |   0    2     0     2
3  |  3    0    1    2                             3   |   0    3     2     1

Addition form a group, 0 is the additive identity.   The additive inverse (-a)  of a for  0, 1, 2, 3, respectively, is  0, 3, 2, 1.   For multiplication, it is obvious 1 is the multiplicative identity.  The set (Subscript[Z, 4])  -  {0}  =  {1, 2, 3}  is not a group with respect to multiplication.  So it cannot be a field.  We find 2 * 2 = 0 which is outside the set {1,2,3}.   It is not an integral domain because  2*2 = 2*0 = 0.  But we don't have the cancellation law.  2 ≠ 0, if cancellation law were true, we get 2*2 = 2*0  => 2 = 0 which is nonsense.  

It satisfies all the conditions for a ring.  In fact, it is a commutative ring.

An example of a field

Roughly speaking, field is something you can do +, -, *, and /.   For example, the set of all rational numbers are closed under addition, subtraction, multiplication, and division.  The set of all real numbers can do the same.  So is the set of all complex numbers.   Division is allowed for all elements except when the devisor is 0 (the additive identity).   To verify that a set with two operations is a field, you need to check the axioms for field.

The examples above (rational number, real, and complex) are sets of infinite cardinality.  A finite field has a finite number of elements.   ((Subscript[Z, 5]); +, *) is a finite field, but ((Subscript[Z, 4]);+,*) is not.   It turns out that ((Subscript[Z, p]); +, *) for any prime number p is a field.   Here is the multiplication table for (Subscript[Z, 5]). 

+  |   0   1   2   3   4                            *  |   0   1   2   3   4
_____________________________________________
0  |   0   1   2   3   4                             0  |   0   0   0   0   0
1  |   1   2   3   4   0                             1  |   0   1   2   3   4
2  |   2   3   1   0   1                             2  |   0   2   4   1   3
3  |   3   4   0   1   2                             3  |   0   3   1   4   2
4  |   4   0   1   2   3                             4  |   0   4   3   2   1

To verify ((Subscript[Z, 5]); +) the addition table forms a group, we note that each row and each column is a permutation of the elements 0 to 4.   To verify ((Subscript[Z, 5]) -  {0}) with multiplication form a group, we note that the subtable without the column and row with 0's is a permutation of {1,2,3,4}.  We note that the multiplicative inverse of 2 is 3, we can write (2^(-1 )) = 3.   

You will see later on that modulo arithmetic (Subscript[Z, p]) with prime p is very useful for polynomial symbolic computation.

Euclidean Domains

Division can be performed in a field for any nonzero divisors.  Note that a/b = a∘(b^(-1)).  Since every nonzero elements in a field has a multiplicative inverse, the division is defined through inverse and multiplication.

In a ring or an integral domain, division can not be done in general, since the concept of inverse is not present.    However, if we can somehow do division with remainder (like integer division with remainder  a=q*b+r, |r|<|b|), we can still talk about divisibility and greatest common divisors.   This is axiomized in the following definition of Euclidean domain:

A Euclidean Domain is an integral domain D with a valuation v: D-{0} to N, which is a mapping from any nonzero element to a nonnegative integer, having the following properties:
P1:   For all a, b ∈ D-{0}, v(ab) ≥ v(a);
P2:   For all a, b ∈ D with b ≠ 0, there exist elements q, r ∈ D such that 
	a = b q + r
where r = 0, or v(r) < v(b).

If r = 0, we say b divides a. q is the quotient. r is the remainder.

Examples of Euclidean domains

The integers Z with usual addition and multiplication form a Euclidean domain with the valuation v(a) = |a|, since it is true that
	a = q*b + r,   |r| < |b|.
E.g.,  if a = 8, b = 3, we have 8 = 3*2 + 2,   or  8 = 3*3 - 1.
Note also |a*b| >= |b| for a ≠ 0, and b ≠ 0.

Polynomials over Fields

One of the important algebraic structure we shall use is polynomials with coefficients from a field F:

(Subscript[P, n])(
          x)  =  (Subscript[a, 0])  +  (Subscript[a, 1]) x  +  (Subscript[a, 2]) 
                (x^2)  +   ...    +  (Subscript[a, n]) (x^n).

The set of all such polynomial is denoted  by F[x].   It is a Euclidean domain with valuation v((Subscript[P, n])(x))  =  n. (why?)

For polynomials, we also have the division property  
  a(x) = b(x)*q(x) + r(x),  for a(x), b(x), q(x), r(x) ∈ F[x].
  
Example:
  Consider Q[x] (the set of all polynomial over rational numbers).  Let a(x) = 3  (x^3) + (x^2) + x + 5,  
      and b(x)  =  5  (x^2) - 3  x + 1.  To obtain the quotient and remainder, we use the long division method:
                               (3/5) x        +   (14/25)
  5  (x^2)-3  
          x+1    \(TraditionalForm\`\@\(3  x\^\(\(3\)\(\ \ \ \ \)\) + \ \ \ \ \ \ \ \ \ \ \ \ \ \ x\^\(\(2\)\(\ \ \ \)\)\ \ \ \  + \ \ \ \ \ \ x\ \ \ \ \  + \ \ \ \ \ \ \ 5\)\)
                              3 
           (x^3)    -        (9/5)  (x^2)       +  
        (3/5)  x
                              _____________________________
                                             (14/5) \(TraditionalForm\`x\^2\ \ \ \ \ \ \ \  + \ \ 2\/5\ x\ \ \ \ \ \  + \ \ \ \ \ \ 5\)
                                             (14/5) (x^2)         - (42/25) 
          x       +    (14/25)
                                           ________________________
                                                                (52/25) x        + (111/25)

What we did is to cancel the leading term.  Thus a(x)  =  b(x) q(x)  +  r(x) with
 q(x)  =  (3/5) x   +  14/15,   r(
          x)  =  (52/25) x  +  111/25

Greatest Common Divisors

Definition:  For a,  b,  x  ∈  integral domain D, if
	b  =  a ∘ x
a is called a divisor of b, and a divides b (denoted a | b).  b is called a multiple of a.

Greatest common divisor (GCD) of a and b 
is c such that if c | a and c | b, c is a multiple of every other element which divides both a and b.

Euclidean Algorithm

The Euclidean algorithm for GCD is based on the following theorem valid for any Euclidean domains.

Given \(TraditionalForm\`\(a\_, \) b, q, r\) ∈ D,  satisfying

a  =  b q  +  r,       v(r)  <  
        v(b), 
GCD(a, b)  =  GCD(b, r)

We have seen a version of GCD computation with a recursive definition in Mathematica.  A procedural based algorithm should be something like this:

Euclidean[a_, b_]  :=  
      Module[{r, c, d}, 
c  =  
          a; 
d  =  b; 
While[
          d  ≠  0, 
r  =  
            remainder[c, d]; 
c  =  
            d; 
d  =  
            r
]; 
c]

The point we want to make is not give you yet another Mathematica implementation of GCD, but to emphasize that this algorithm works for all Euclidean domains.  For integer Z, remainder is given by the usual Mod[c, d] function.  For polynomial over Q, we carry out the computation for the remainder similar to the long division.  Thus we can find GCD of two polynomials.