620 ANSWERS TO EXERCISES (Web hosting resellers) 4.6.1 15. Let cij
620 ANSWERS TO EXERCISES 4.6.1 15. Let cij = aiiajl + . . . + a,,ajn; we may assume that czZ > 0 for all i. If cZ3 # 0 for some i # j, we can replace row i by (a,~ -caJr,. . , uZn. -cajn), where c = c,,/c,,; this does not change the value of the determinant, and it decreases the value of the upper bound we wish to prove, since cii is replaced by cii -&/c2j. These replacements can be done in a systematic way for increasing i and for j < i, until czj = 0 for all i # j. [The latter algorithm is called Schmidt s orthogonalization process ; see Math. Annden 63 (1907), 442.1 Then det(A) = det(AAT) = ~11 cnn. 16. Let f(zi, . , zn) = gm(zz, , s,)zy + . + go(sz, . . , xn) and g(sz, . . . , 2,) = gm(22,. . . , 2n)2 + . . . + go(ra, . . , 2%) ; the latter is not identically zero. We have aN 5 m(2N + I)+’ $ (2N + l)bN, where bN counts t,he integer solutions of g(za, . . . , xn) = 0 with variables bounded by JV. Hence limN,, aN/(zN + 1) = limN+co b.w/(aN + l)n-l, and this is zero by induction. 17. (a) For convenience, let us describe the algorithm only for A = {a, b}. The hy- potheses imply that deg(QlU) = deg(QaV) 2 0, deg(Qi) 5 deg(Qz). If deg(Qi) = 0, then Qr is just a nonzero rational number, so we set Q = &a/&i. Otherwise we let &I = U&II -I– b&12 + rl, Qz = aQzl + b&22 + ra, where ri and rz are rational numbers; it follows that &IV -Q2V = a(QllU -QzlV) + b(Q12U _ Q22v) + rlU _ r2v. We must have either deg(Qrr) = deg(Qi) -1 or deg(Qia) = deg(Qi) -1. In the former case, deg(QiiU -QzlV) < deg(QiiU), by considering the terms of highest degree that start with a; so we may replace Qi by &ii, &a by Q2r, and repeat the process. Similarly in the latter case, we may replace (Qi, Q2) by (Qia, Q22) and repeat the process. (b) We may assume that deg(U) 2 deg(V). If deg(R) 2 deg(V), note that &IV -Q2V = QiR -(Qz -Q1Q)V has degree less than deg(V) 2 deg(QrR), so we can repeat the process with U replaced by R; we obtain R = Q V + R , U = (Q + Q )V + R , where deg(R ) < deg(R), so eventually a solution will be obtained. (c) The algorithm of (b) gives VI = UV2 +R, deg(R) < deg(V2); by homogeneity, R = 0 and U is homogeneous. (d) We may assume that deg(V) 5 deg(U). If deg(V) = 0, set W + U; otherwise use (c) to find U = QV, so that QVV = VQV, (QV -VQ)V = 0. This implies that QV = VQ, so we can set U + V, V t Q and repeat the process. For further details about the subject of this exercise, see P. M. Cohn, Proc. Cambridge Phil. Sot. 57 (1961), 18-30. The considerably more difficult problem of characterizing all string polynomials such that UV = VU has been solved by G. M. Bergman [Ph.D. thesis, Harvard University, 19671. 18. [P. M. Cohn, Transactions Amer. Math. Sot. 109 (1963), 332-356.1 Cl. Set ui + Ul, 2~2 + U2, u1 + VI, v2 + V2, z1 + 2; + WI + wh + 1, Z: + 22 t w; + w2 + 0, n + 0. C2. (At this point the identities given in the exercise hold, and uivi = 1~1~12; vz = 0 if and only if ui = 0.) If 212 = 0, the algorithm terminates with gcrd(Vi , V2) = VI, lclm(Vi,Va) = z:V, = -2LV2. (Also, by symmetry, we have gcld(Ui,Us) = ILL and lcrm(Ui, Uz) = Uizui = -U2w2.)