4.6.4 EVALUATION OF (X web hosting) POLYNOMIALS 495 Theorem W (S.
4.6.4 EVALUATION OF POLYNOMIALS 495 Theorem W (S. Winograd, 1975). Let p(u) be a mom? polynomial of degree n whose complete factorization over a given infinite field is p(u) = p1(u)Q.. .p&p. (73) Then the rank of the tensor (72) corresponding to the bilinear forms (69) is 2n-q over this field. Proof. The bilinear forms can be evaluated with only 2n-q chain multiplications by using rules (56), (573, (58) m an appropriate fashion, so we must prove only that the rank r is 2 2n -q. The above discussion establishes the fact that rank(Tcij,k) = n; hence by Lemma T, any n X r realization A, B, C of (T,jk) has rank(C) = n. Our strategy will be to use Lemma T again, by finding a vector (~0,211,. . . , ~~-1) that has the following two properties: a) The vector (~0, ~1,. . . , u,-~)C has at most q + T - n nonzero coefficients. b) The matrix v(P) = C o < k < n vk Pk is nonsingular. - This and Lemma T will prove that q + T - n 2 n, since the identity shows how to realize the n X n X 1 tensor w(P) of rank n with q + r -n chain multiplications. We may assume for convenience that the first n columns of C are linearly independent. Let D be the n X n. matrix such that the first n columns of DC are equal to the identity matrix. Our goal will be achieved if there is a linear combination (~0, ~1, . . . , ~1,~~) of at most q rows of D, such that v(P) is nonsingular; such a vector will satisfy conditions (a) and (b). Since the rows of D are linearly independent, no irreducible factor PA(U) divides the polynomials corresponding to every row. Given a vector w = (wet Wl , . . . , w,–I), let covered(w) be the set of all X such that w(u) is not a multiple of PA(U). From two vectors v and w we can find a linear combination v + cyw such that covered(v + cyw) = covered(v) U covered(w), (74) for some a! in the field. The reason is that if X is covered by v or w but not both, then X is covered by v + aw for all nonzero cy; if X is covered by both v and w but X is not covered by v + QW, then X is covered by v + /3w for all p # cy. By trying q + 1 different values of (u, at least one must yield (74). In this way we can systematically construct a linear combination of at most q rows of D, covering all X for 1 5 X < q. I