Symbolic Computing

LT20, 4:00-6:00pm
Wed, 2 April 2003

From Mod p solutions to result in Z
for linear equations

22  x  + 44  y  + 74  z  =  
        1,           (1)
    15  x  + 14  y  - 
          10  z  =  -2,       (2)
-25 x  - 28  y  + 20  z  =  
        34.          (3)

Suppose that the above equations have been solved mod p for several values of p, how do we reconstruct the original solution in Z (or Q)?
Since there is a ring morphism from Z to Z\(TraditionalForm\`\_p\) (but not from Q), we need to work in Z.   Any equations that work in Z can be translated directly in Z\(TraditionalForm\`\_p\).

Formally, we can write the solution of the equation using Cramer's rule:
x  =  ((Subscript[d, x])/d),   y  =  
        ((Subscript[d, y])/d),    and  z =  ((Subscript[d, z])/d)
where
d = determinant of the coefficient matrix = 
=det(({{  22,   44, \(\(\ \ \ \)\(74\)\)}, {  15,   14, -10}, {-25, -28,   20}})).
(Subscript[d, x])  is obtained by replacing the first column of the matrix in d by the left-hand side column (the b column vector in  A x = b). 
(Subscript[d, x]) = det(({{1, 44, 74}, {-2, 14, -10}, {34, -28, 20}}))
 Similarly, for (Subscript[d, y]) (obtained by replacing second column by the b vector) and (Subscript[d, z]) (by replace third column).  
(Subscript[d, y]) = det(({{   22,    1, \(\(\ \ \ \)\(74\)\)}, {   15, -2, -10}, {-25,  34,    20}})),    (Subscript[d, z]) = det(({{   22,    44, \(\(\ \ \ \)\(1\)\)}, {   15,    14, -2}, {-25, -28,  34}})).

Note that the Cramer's rule is valid both in Q and in the field Z\(TraditionalForm\`\(\(\_p\)\(.\)\)\)  Thus  x*d  =  (Subscript[d, x]) is true in Z, it is equally valid in Z\(TraditionalForm\`\_p\).  Also, d,  (Subscript[d, x]),  
      (Subscript[d, y]),  (Subscript[d, z]) ∈ Z.  But x∈ Q.  We solve the equations in Z\(TraditionalForm\`\_p\) to determine x is (Subscript[Z, p]).  In addition, we also find the determinant d mod p.   From d  and x we can also find (Subscript[d, x]) mod p.    Applying the Chinese remainder theorem to d and (Subscript[d, x])  mod p, we find their values Z.   This gives us the solution x as a rational number in Q.

For example, working over Z\(TraditionalForm\`\_7\) the system becomes:
x  +  2  y  -  3  z  =  
        1, 
x                -  
          3  z  =  -2, 
3  
            x                 - 
          z  =  -1.  

Working in symmetric representation of Z\(TraditionalForm\`\_p\) (that is, use values -3,-2,-1,0,1,2,3), Gaussian elimination (or any other subtitution methods) gives
x  =  -1,  y  =  -2,  
      z  =  -2,  d  =  -2   (mod 7).
Thus (Subscript[d, x])  =  x *d  =  2,  
      (Subscript[d, y]) =  y*d  =  -3,  (Subscript[d, z]) = z*d = -3  (all mod 7).

How fast can we compute the determinant (i.e., best algorithm for computing det)?

Why (Subscript[d, x]) =  x*d (equivalently, x = (Subscript[d, x])/d) is valid in Z\(TraditionalForm\`\_p\)?

Why don't we apply Chinese Remainder theorem to x mod p?

Similarly, working in Z\(TraditionalForm\`\_11\), Z\(TraditionalForm\`\_13\), Z\(TraditionalForm\`\_17\) and Z\(TraditionalForm\`\_19\) gives
(Subscript[d, x])  =  -5 ,  
      (Subscript[d, y]) =  0,      (Subscript[d, z]) = -4 ,  
      d = 1          (all mod 11)
(Subscript[d, x])  =  -2 ,  
      (Subscript[d, y]) =  4,      (Subscript[d, z]) = 6 ,      d = 
        4          (all mod 13)
(Subscript[d, x])  =  5,      (Subscript[d, y])  =  -6,  
      (Subscript[d, z]) = -3,    d  =  -2    (all mod 17)
(Subscript[d, x])  =  9,      (Subscript[d, y])  =  
        6,      (Subscript[d, z])  =  
        7,     d  =  -8    (all mod 19)

Using the Garner's algorithm for Chinese remainder problem, we can find that 
(Subscript[d, x]) =  - 44280,   (Subscript[d, y]) =  40590,  
      (Subscript[d, z]) =  -11070,  d  =  -7380. 

Thus  x  =  (Subscript[d, x])/
            d  =  -44280/(-7380)  =  
            6, 
y  =  (Subscript[d, y])/
            d  =  40590/(-7380)  =  -11/
              2, 
z  =  (Subscript[d, z])/
            d   =  - 11070/(-7380)  =  3/2.

What is the point of using a long-winded way to compute a simple problem?

Factorization in integral domains

Factorization is one of the oldest problem in mathematics: we can write 12 = 2*6=3*4=3*2*2,  but we cannot write 13 as product of any two integers (expect the trivial case of 13 = 1*13).

Definition:   

Let D an integral domain.   An element p∈ D - {0} is called a prime (or irreducible) if
(a)   p is not a unit, and 
(b)   whenever p = a b either a or b is a unit.

If GCD(a, b) = 1, for a, b ∈ D, a and b are called relatively prime.

A unit in an integral D is an element that has multiplicative inverse.  In Z, -1 and 1 are units.   In Z (or any other integral domains), 0 is not a prime, 1 is not a prime,  but, 2, 3, 5, 7, 11, 13, etc are primes.  
Consider the set of all polynomials with integer coefficient Z[x].
Again, only 1 and -1 are units.  1 + x is a prime, but 1 - (x^2) = (1 + x) (1 - x) is not.   When talking about polynomials, we usually use the term "irreducible" polynomials (in a given algebraic domains).

If the polynomials are in R[x], i.e., the polynomials with real coefficients, then  again, 1 + x is a prime, and 1 + (x^2) is a prime (since (x + i) (x - i) is no longer in R[x]), but 1 - (x^2) is not.  In fact, in R[x], all the primes are polynomials of degree 2 or less.

What are the forms of prime (or irreducible) polynomials in C[x], i.e., polynomials with complex coefficients?  What are units in C[x]?

Square-Free Factorization algorithm

An element is square free if it does not contain repeated factor, prime or composite.  For example,   10 = 2*5 is square-free, but  20 = (2^2)*5 is not.  Similar  42 =  6*7 is square free, 252  =  6*6*7 is not.

The square-free concept is more useful for polynomials.  a(
          x)  =  ((x^2) + 
              1) ((((x^2) - 1))^4) ((((x^3) + 3  x))^5)  is a square-free factorization of a polynomial over Z.   The factor (x^2) + 1, (x^2) - 1, and (x^3) + 3  x is square-free.

Definition:

a ∈ D is square-free if it has no repeated factors, that is, if there exists no b (not a unit) such that (b^2)  |  a.

The square-free factorization of a is

a = (∏_(i = 1)^k) ((Subscript[a, i])^i)     ((Subscript[a, i]) rised to power i)
where each (Subscript[a, i]) is square-free (not necessarily prime) and 
GCD((Subscript[a, i]),  (Subscript[b, j]))  =  
        1   for  i ≠  j

Consider polynomials in Q[x].   Let c(x)  =  GCD(a(x), a' (x)), where a' (x) is the derivative of polynomial a(x).  It can be proved that a(x) has repeated factors if and only if c(x) is not a unit.  This leads to the following square-free factorization algorithm: