Cheap web hosting - 4.6.4 ANSWERS TO EXERCISES 641 10. c rlkcn(k
4.6.4 ANSWERS TO EXERCISES 641 10. c rlkcn(k + l)(kT1) = n(2%- -1) multiplications and xilkcn /~(~;i) = n2n-1 -2n + 1 additions. This is approximately half as many arithmetic operations as the method of exercise 9, although it requires a more complicated program to control the sequence. Approximately (rnTzl) + (ml.$-l) temporary storage locations must be used, and this grows exponentially large (on the order of 2n/,,/?i). The method in this exercise is equivalent to the unusual matrix factorization of the permanent function given by Jurkat and Ryser in J. Algebra 5 (1967), 342-357. It may also be regarded as an application of (39) and (40), in an appropriate sense. 12. Here is a brief summary of progress on this famous research problem: J. Hopcroft and L. R. Kerr proved, among other things, that seven multiplications are necessary in 2 X 2 matrix multiplication [SIAM J. Appl. Math. 20 (1971), 30-361. R. L. Probert showed that all 7-multiplication schemes, in which each multiplication takes a linear combination of elements from one matrix and multiplies by a linear combination of elements from the other, must have at least 15 additions [SIAM J. Computing 5 (1976), 187-2031. For n = 3, the best method known is due to J. D. Laderman [Bull. Amer. Math. Sot. 82 (1976), 126-1281, who showed that 23 noncommutative multiplications suffice. His construction has been generalized by Ondrej Sykora, who exhibited a method requiring n3-(n-l)2 noncommutative multiplications and n3-n2+11(n-l)2 additions, a result that also reduces to (36) when n = 2 [Lecture Notes in Comp. Sci. 53 (1977), 504-5121. The best lower bound known to hold for all n is the fact that 2n2 -1 nonscalar multiplications are necessary [Jean-Claude Lafon and S. Winograd, Theoretical Camp. Sci., to appear]. Pan has generalized this to a lower bound of mn + ns f m -n -1 in the m X n X s case [see SIAM J. Computing 9 (1980), 3411. The best upper bounds known for large n were changing rapidly as this book was being prepared for publication; see exercises 60-64. 13. By summing geometric series, we find that F(tr, . , t,) equals c 0js1