502 ARITHMETIC 4.6.4 45. [AA%] Prove that all
502 ARITHMETIC 4.6.4 45. [AA%] Prove that all pairs (~1,~s) of bilinear forms in ($1, ~2) and (~1, yz) can be evaluated with at most three chain multiplications. In other words, show that every 2 X 2 X 2 tensor has rank 2 3. 46. [M.%] Prove that for all m, n, and s there exists an m X n X s tensor whose rank is at least [mns/(m + n + .s)j. Conversely, show that every m X n X s tensor has rank at most mns/max(m, n, s). 47. [MQ?] Is it possible to determine the rank of any given tensor (tijk) over, say, the field of rational numbers, in a finite number of steps? (There is a finite way to compute the tensor rank over algebraically closed fields like the complex numbers, since this is a special case of the results of Alfred Tarski, A Decision Method for Elementary Algebra and Geometry, 2nd ed. (Berkeley, California: Univ. of California Press, 1951); but the known algorithms do not make this computation really feasible except for very small tensors. Over the field of rational numbers, the problem isn t even known to be solvable in finite time.) 48. [M49] If (&k) and (tijk) are tensors of sizes m X n X s and m X n X s , respectively, their direct sum (tijk)@(t&J = (tGk) is the (m+m ) x (n+n ) X (s+s ) tensor defined by tck = tzjk if i 5 m, j 5 n, k 2 s; t$k = t:–m,j–n,k–s if i > m, j > n, k > s; and tyjk = 0 otherwise. Their direct product (tijk) @ (tlzjk) = (trik) is the mm X nn X SS tensor defined by t(iif)(jj )(kk!) = tijktiljlkt. Derive the upper bounds rank(tyJk) 2 rank(tijk) + rank($,) and rank(t ,i,) 2 rank(tijk) . rank(t&,). b 49. [HA&&Y] Show that the rank of an m X n X 1 tensor (tijk) is the same as its rank as an m X n matrix (tijl), according to the traditional definition of matrix rank as the maximum number of linearly independent rows. 50. [HMZO] (S. Winograd.) Let (tijk) be the mn X n X m tensor corresponding to multiplication of an m X n matrix by an n X 1 column vector. Prove that the rank of (&jk) is mn. b 51. [M.Z4] (S. Winograd.) Devise an algorithm for cyclic convolution of degree 2 that uses 2 multiplications and 4 additions, not counting operations on the 5%. Similarly, devise an algorithm for degree 3, using 4 multiplications and 11 additions. (Cf. (67), which solves the analogous problem for degree 4.) 52. [M25] (S. Winograd.) Let n = n n where gcd(n ,n ) = 1. Given normal schemes for cyclic convolutions of degrees n and n , using respectively (m , m ) chain multiplications, (p , p ) parameter multiplications, and (a , a ) additions, show how to construct a normal scheme for cyclic convolution of degree n using m m chain multiplications, p n + m p parameter multiplications, and a n + m a additions. @. [HM40] (S. Winograd.) Let w be a complex mth root of unity, and consider the one-dimensional discrete Fourier transform for s 5 f(s)= c wwst, 1 5 m. (a) When m = pe is a power of an odd prime, show that efficient normal schemes for computing cyclic convolutions of degrees (p-l)pk, for 0 5 k < e, will lead to efficient algorithms for computing the Fourier transform on m complex numbers. Give a similar construction for the case p = 2. (b) When m = m m and gcd(m , m ) = 1, show that Fourier transformation algorithms for m and m can be combined to yield a Fourier transformation algorithm for m elements.