4.6.1 ANSWERS TO EXERCISES 621 C3. Find (Web hosting packages) Q
4.6.1 ANSWERS TO EXERCISES 621 C3. Find Q and R such that ~1 = Qvz + R, where deg(R) < deg(wz). (We have w(Q2r2 + R) = 2~2712, so ulR = (2~2 -u1Q)v2 = R wz.) C4. Set (WI, w2, w:, w;, a, ~2, z:, zl,, UI, u2, WI, 7~2) + (w: -WIQ, w z -w2&, WI, wz, z;, zk, zl -Qz:, z2 -Qz/,, 212 - ZL~&, ~1, 2)2, ~1 -Qw2) and n + n + 1. Go back to C2. m This extension of Euclid s algorithm includes most of the features we have seen in previous extensions, all at the same time, so it provides new insight into the special cases already considered. To prove that it is valid, note first that deg(v2) decreases in step C4, so the algorithm certainly terminates. At the conclusion of the algorithm, v1 is a common right divisor of Vl and V2, since wlvl = (-l)nV1 and -w2w1 = (-l)nV2; also if d is any common right divisor of VI and V2, it is a right divisor of zlV1 + z2V2 = ol. Hence w1 = gcrd(K, V,). Also if m is any common left multiple of Vl and Vz, we may assume without loss of generality that m = UlVl = U2V.2, since the sequence of values of Q does not depend on Ul and U2. Hence m = (-l) (--u2z~)Vl = (-1) (u2z~)V2 is a multiple of zi VI. In practice, if we just want to calculate gcrd(Vl,Vz), we may suppress the com- putation of n, WI, ~2, wi, w& zl, ~2, zi, 2;. These additional quantities were added to the algorithm primarily to make its validity more readily established. Note: Nontrivial factorizations of string polynomials, such as the example given with this exercise, can be found from matrix identities such as (f x ix: x -:x -3c -3 =(:, 3 since these identities hold even when multiplication is not commutative. For example, (abc + a + c)(l + ba) = (ab + l)(cba + a + c). (Compare this with the continuant polynomials of Section 4.5.3.) 19. [Cf. Eugene Cahen, TMorie des AJombres 1 (Paris: A. Hermann & fils, 1914), 336-338.1 If such an algorithm exists, D is a gcrd by the argument in exercise 18. Let us regard A and B as a single 2n X n matrix C whose first n rows are those of A, and whose second n rows are those of B. Similarly, P and Q can be combined into a 2n X n matrix R; X and Y can be combined into an n X 2n matrix 2. The desired conditions now reduce to two equations C = RD, D = ZC. If we can find a 2n X 2n integer matrix U with determinant fl such that the last n rows of U- C are all zero, then R = (first n columns of U), D = (first n rows of U-lC), Z = (first n rows of U- ) solves the desired conditions. Hence, for example, the following algorithm may be used (with m = 2n): Algorithm T (Triangularization). Let C be an m X n matrix of integers. This algorithm finds m X m integer matrices U and V such that UV = I and VC is upper triangular. (The entry in row i and column j of VC is zero if i > j.) Tl. [Initialize.] Set U +-V +-I, the m X m identity matrix; and set T + C. (Throughout the algorithm we will have T = VC and UV = 1.) T2. [Iterate on j.] Do step T3 for j = 1, 2, . . . , min(m, n), and terminate the algorithm. T3. [Zero out column j.] Perform the following transformation zero or more times until Tij is zero for all i > j: Let Tkj be a nonzero element of { Tzj , T(,+l), , . , T,, } having the smallest absolute value. Interchange rows Ic and j of T and of V; interchange columns Ic and j of U. Then subtract LTij/TjjJ times row j from row i, in matrices T and V, and add the same multiple of column. i to column j in matrix U, for j < i 5 m. 1