4.6.4 EVALUATION OF POLYNOMIALS 505 62. [M24] The (Web hosting directory)
4.6.4 EVALUATION OF POLYNOMIALS 505 62. [M24] The border rank of (&k), denoted by &(t,,k), is mind2srankd(tzjk), where rankd is defined in exercise 61. Prove that the tensor (i Y>(i i> has rank 3 but border rank 2, over every field. 63. [AR?O] Let T(m, n, s) be the tensor for matrix multiplication as in exercise 59. (a) Show that T(m, n, s) @ T(M, N, S) = T(mM,nN, sS). (b) If T(m,n, s) has rank 5 r, show that the number of noncommutative multiplications M(N) for the product of N x N matrices is O(N ( ~ z ~ )) as N + co, where p(m,n, S,T) = 3 logr/logmns. (c) If T(m, n, s) has border rank 5 r, show that we have M(N) = O(N p(mznzs,r)(log N)2). (d) If the tensor pT(m, n, s) obtained by taking the direct sum of p copies of T(m,n, s) has border rank 5 pr, where p < r, show that a similar formula holds. (This tensor corresponds to p independent matrix multiplications.) 64. [M40] (Pan and Winograd.) The purpose of this exercise is to combine the ideas of exercises 60-63, in order to obtain asymptotic bounds on M(N) as N + co. a) Modify the construction of exercise 60(b) to show that T(m, n, s) $ T(s, m, n) has border rank < mns + mn + ns. b) Show that the construction of exercise 60(c) can be altered to prove that the border rank of T(m, n, 2s) $ T(2n, s, m) @ T(s, 2m, n) is at most 2(m + l)n(s + 2) by finding constants oi, o2, . . . , os such that E c (C&j + Udxj, + C7ud+2Xki)(aud-1?J3g + C7UdYkt + yij) i,J,k,o x (ud+l z& + a&j + CTUd-2 &k) l tam QlffX23 + flu d+2 c, ~k,)((Y& + a Ud c, ykz) %,3>0 x (WZ%~ + Ud+l c, ZCJ + cy3 c ((Txi3 + Ud c, X?k)(Yi3 + Oud–l c, Y,,&) 2,3>a x (gzi? + cud- c, s&k) + a4 3Fo (0 xi tj + udX?k)(xi YQ + oud-llJ,L) x (g c, zij + cud- &k) + a5 c (O ci xV + Ud c, X?k)(C, %3 + CTud-l c, !&) jP x (g c, .& + gUd- c, ZJk) + @6 c (c ci %)(C, G> YG)(U c, jr0 (modulo uZdfl ), for sufficiently large d. Here the summations are to be carried out for 1 5-i 5 m, 1 5 j 5 n, 1 5 k 5 s, and o = fl; the subscript Z means ai, so that z takes the 2m values fl, . , +m. c) Use the result of(b) in connection with exercise 63 to show that M(N) = O(Np+ ) for all E > 0, where p = @m, n, 2s, #(m + l)n(s + 2)).