4.6.4 ANSWERS (Web server on xp) TO EXERCISES 649 48. If A,
4.6.4 ANSWERS TO EXERCISES 649 48. If A, B, C and A , B , C are realizations of (tzjk) and (t:3k) of respective lengths r and r , then A = A @ A , B = B @ B , C = C @ C , and A = A @ A , B = B @J B , C = C @ C , are realizations of (tyJk) and (tyik) of respective lengths r + r and r . r . Note: Many people have made the natural conjecture that rank((t,,k) @ (tLJk)) = rank(t,,k) f rank($,), but the construction in exercise 60(b) makes this seem much less plausible than it once was. 49. By Lemma T, rank(tijk) 2 rank(ti(jk)). Conversely if M is a matrix of rank r we can transform it by row and column operations, finding nonsingular matrices F and G such that FMG has all entries 0 except for r diagonal elements that are 1; cf. Algorithm 4.6.2N. The tensor rank of FMG is therefore < r; and it is the same as the tensor rank of M, by exercise 44. 50. Let i = (i , i ) where 1 5 i 5 m and 1 2 i 5 n; then t(zr,2/t)3k = &u~&,~, and it iS Clear that rank(ti(jk)) = mn since (i&k)) is a permutation matrix. By Lemma L, rank(tijk) 2 mn. COnVf?rSdy, since (tljk) has only mn nonzero entries, its rank is clearly 2 mn. (There is consequently no normal scheme requiring fewer than the mn obvious multiplications. There is no such abnormal scheme either [Comm. Pure and Appl. Math. 3 (1970), 165-1791. But some savings can be achieved if the same matrix is used with s > 1 different column vectors, since this is equivalent to (m x n) times (n X s) matrix multiplication.) 51. (a) si = y0 + yl, s2 = y0 -yl; ml = $(x0 + ZI)SI, mz = +(x0 -sl)sz; w. = ml +mz, wi = ml -ms. (b) Here are some intermediate steps, using the methodology in the text: ((~0 -~2) + (m -ZZ)U)((YO -YZ) + (YI -~z)u)mod(u~ + u + 1) = ((zo -az)(yo -yz) -(21 -52)(Yl -y2)) + ((x0 - z)(Yo -y2) -(21 -ZO)(Yl -yo))u. The first realization is The second realization is The resulting algorithm computes si = yc + ~1, sz = yc -yl, ss = y2 -yc, s4 = y2 -yl, s5 = so + y2; ml = +(x0 + 21 + 22).5x, m2 = +(x0 + ZI -2z2)s2, m3 = +(x0 -2×1 + x2)53, m4 = &(-220 + zl +x2).%&; tl = ml + m2, t-2 = ml -m2, t3 = ml + m3, w0 = tl -m3, wl = t3 + m4, w2 = t2 -m4. 52. Let i = (i , i ) when i mod n = i and i mod n = i . Then we wish to compute W(k’,k”) = c x(i’,i”)y(~’,j”) summed for i + j = k (modulo n ) and i + j = Ic (modulo n ). This can be done by applying the n algorithm to the 272 vectors X,, and Y$ of length n , obtaining the n vectors wk . Each vector addition becomes n additions, each parameter multiplication becomes n parameter multiplications, and each chain multiplication of vectors is replaced by a cyclic convolution of degree n . [If the subalgorithms use the minimum number of chain multiplications, this algorithm uses 2(n -d(n ))(n -d(n )) more than the minimum, where d(n) is the number of divisors of n.]