4.7 ANSWERS TO EXERCISES 655 62. (Christian web host) The rank
4.7 ANSWERS TO EXERCISES 655 62. The rank is 3, by the method of proof in Theorem W with P = (i i). The border rank cannot be 1, since we cannot have al(zl)bl(u)cl(u) = al(u)b~(zl)cz(u) = ud and al(~)bz(u)ci(u) E ai(u)bi(u)cz(u) G 0 (modulo &l). The border rank is 2 because of the realization (L A), ( f T), (A -A). 63. (a) Let the elements of T(m, n, s) and T(A4, N, S) be denoted by t(2,J~)(3,k~)(k,z~) and T(I,J~)(J,K~)(K,I~), respectively. Each element ~I,J,)(J,K,)(K,I,) of the direct product, where 1 = (6 I), J = (j, J), and K = (b K), is equal to t(,,j,)(j,k,)(k,zl)~(~,~/)(J,KI)(K,r ) by definition, so it is 1 iff I = I and J = J and K = K. (b) We have M(mns) 5 r3, since T(mns, mns, mns) = T(m, n, s) @ T(n, s, m) @ T(s, m, n). If M(P) 5 R we have A4(Ph) 5 Rh for all h, and it follows that M(N) 5 J,f(pk= 1) 2 RhP Nl 2 RN1 gR/logP, [This result appears in Pan s 1972 paper.] (c) We have Md(mns) < r3 for some d, where ?&(n) = rankd(T(n,n,n)). If l&(P) 2 R we have ?&d(Ph) 5 Rh for all h, and the stated formula follows since WPh) 5 2 >Rh by exercise 61. In an infinite field we save a factor of log N. ( hdt2 [This result is due to Bini and Schonhage, 1979.1 (d) Let P = mns; we can perform p 3h independent Ph X Ph matrix multi- plications with at most (hdzfz)p3hr3h noncommutative scalar multiplications. Reduce M(P2h) to A4(Ph) matrix multiplications of size Ph x Ph; thus we have M(Pzh) 5 (hdt2)~3hM(Ph)(l f O(~/T)~~). Iterating this recurrence gives 2 M(N) = O(N p(m,n,s,r)) exp(O(log log n)2). 64. (a) Let a = xij, A = U&z, b = yjk, B = Yt3, c = u&z, C = zjk, so that CZ = O(u ) can be eliminated. [When m = s = 7 and n = 1, this gives M(N) = O(N2e6).] (b) Take cyi = s -1, ~2 = –oc , t23=Q4=-1,C25=1,(-Y6=S-1, and d > 4. [We assume that o-l exists in the field.] (c) Taking the direct product of T(m, n, 2s) $ T(2n, s, m) $ T(s, 2m, n) with itself 3h times gives a tensor whose border rank is at most (2(m + l)n(s + 2))3h. This tensor is the direct sum of 33h terms of the form T(m (2n)3sk, n2s3(2m)k, (2s)%m3nk) where i +j + k = 3h, and (3h)!/h!3 of these have i = j = Ic = h. Thus if we let P = (2mns)h and p = (3h)!/h!3, the border rank of pT(P, P, P) is at most pr, where r = (2(m + l)n(s + 2))3h/p. Exercise 63(d) now implies that M(N) = O(N P(P,PZP, )fe) for all 6 > 0; here P and r are functions of h. We complete the proof by letting h be large in p(P, P, I , r) = log r/log P = (3h log 2(m + l)n(s + 2) -3h log 3 + O(log h))/(3h log Zmns), which equals ,@m, n, 2s, $(m + l)n(s + 2)) + O((log h)/h). [The best value is obtained for m = 5, n = 1, s = 11, p = 31og,,, 52 < 2.522.1 SECTION 4.7 1. Find the first nonzero coefficient V,, as in (4), and divide both U(z) and V(z) by zm (shifting the coefficients m places to the left). The quotient will be a power series iff UO = . . . = U,-1 = 0.