Поэтому {q+Qy < (/1 + 1)2"""2"сег для всех h. Следовательно, мы должны получить q + Q < 2«/("+:)г для всех б > 0.

(d) Пусть в упр. 65 m = и = 4, и заметим, что 16°-* + 9°-* > 17.

67. (а) Матрица (t(y)(0c>(ci>)) размера тп х mns имеет ранг тп, потому что она является матрицей перестановок, когда ограничены тп строк, для которых к = к = 1.

(b) {{t®t)i(jk)), по существу, является (ti(jk))®(ti(jk)) плюс ns + sn дополнительных нулевых столбцов. [Аналогично получаем {{t (g t)i(j*:)) = (Uuk)) ® (*i(j)c)) Для прямых произведений.]

(c) Пусть D-диагональная матрица djag(di,... ,dr), такая, что ADB - О. Из леммы Т известно, что гапк(А) = m и гапк(В) = п, отсюда rank(AD) = m и rank(DB) = п. Без потери общности можно предположить, что первые m столбцов матрицы А линейно независимы. Так как столбцы принадлежат пустому пространству AD, можно также предположить, что последние п столбцов матрицы В линейно независимы. Запишем матрицу А в виде разбиения (Ai Аг Аз), где Ai-матрица размера т х т (и невырожденная), Аг - размера m х g и Аз - размера т х п. Разобьем D так, что AD = (AiZ?i A2D2 A3D3). Тогда существует матрица W = {Wi 10) размера q х г, такая, что ADW = О, т. е. Wi = -D2A2 А" D. Аналогично можно записать В = {Bi В2 Вз) и найти VDB = О, когда V = (OIV3) - матрица размера g х г с V3 = - ОгВВ/з. Заметим, что UDV = D2. Таким образом, утверждение указания более или менее установлено (в конце концов, это было всего лишь указание).

Сейчас положим, что Аи(и) = ац для 1 < i < т, A(rn+i)i{u) = uvu/dm+i, Bji(u) = bji для 1 < j < n, В(„+ ,)((и) = Wjiu; Cki{u) - vCki для 1 < A; < s, Сь+1)г(и) = d(. Следовательно, Ег=] (")-Sji(w)Cfci(u) = utijk 4-0(u*), если к < s, к u[i>m][j>n], если /с = s 4-1. [При этом доказательстве не будет необходимости в предположении, что t невырожденная относительно С-]

(d) Рассмотрим следующую реализацию Т(т, 1,п) с г = тп 4-1: ац = [[ nJ = г - 1], bji =- [Zmodn = j], b(ij)i - [Z = (i-l)n + j], если / < тп; air = 1, bjr = -1, C(ij)r = 0. Она допускает улучшение с d; = 1 для 1 < I < г.

(e) Идея состоит в нахождении допускающей улучшение реализации Г(т, п, s). Предположим, что {А, В, С)-реализация длиной г. Пусть заданы произвольные целые qi, ..., От, fii, , fis- Расширим А, В и с, определяя

(иХг+р) = «;[/ =р], -BofcXr+p) = 0k[J=P}, C(ki-)(r+p) = О для 1 <р < п. Пусть dl = Y17=i Efc=i 04fikCki)i для i < г и di = -1, в других случаях получим

г+п m 5 Г п

YMi3)iB{jk)idi = YYOLiPkYAiij,)iB(jk)iCik,)i-Ylai[j=p\fik[i=P\ 1=1 i=ifc=i i=i p=i

= [}=}]aiPk -[З=з]афк =0.

Значит, такое расширение допускает улучшение, если di... dr / 0. Но di... dr -полиномы от [ai, - - - ,am,Pi, - - ,Ps), не равные тождественно нулю, так как без потери общности можно предположить, что не все столбцы матрицы С равны нулю. Следовательно, будет работать несколько наборов ак и fii-

(f) Если М(п) = п", то получим M(n) = n, отсюда

rank(T(n\ n\ n") © Т(1, п" - n"(2n" - 1), 1)) < n"" 4- п-

Из упр. 66, (с) следует неравенство п" + (п" - 2п 4- п)"/* < п" 4- п для всех h. Значит, ш = 2, однако это противоречит существованию нижней грани 2п - 1 (см. ответ к упр. 12).

(g) Пусть f{u) и g{u)-полиномы, такие, что элементы Vf{u) и Wg{u) являются полиномами. Затем снова определим

Ai+m)l = u+ll,;/(u)/di+m, Bj+„ii = uWjig{u)/p, Ckt = ucki,

где /(и)э(и) = pu+0{u+}. Значит, /=1 Ац{и)Вл{и)Ск1{и) равна u++4ijk+0{u++), если к < s, u[i > m][j > n], если к = s + 1. [Замечание. Следовательно, результат (е) имеет место для любого поля, если гапкг заменить rank, так как можно выбрать а* и /3, полиномами вида 1 4- 0(и).]

(h) Пусть строка р матрицы С приписывается компоненте Г(1,16,1). Основным является то, что Еь=1 <*>(и)Ь>/(и)Ср;(и) равна нулю (не просто 0(и)) для всех г и j, оставшихся после удаления. Кроме того, Ср;(и) ф О для всех I. Данные свойства справедливы для конструкций пп. (с) и (g), и они также остаются справедливыми для прямых произведений.

(i) Доказательство просто обобщается для полиномов с двумя и со многими переменными.

0) Из п. (h) следует неравенство Sl"/ + 2(36"/) 4- 34"/ < 100, поэтому ш < 2.52. Возведение в квадрат дает гапк(Г(81,1,81) Ф 4Г(27,4,27) ф 2Г(9,34,9) ф 4Г(9,16,9) ф 4Т(3,136,3) Ф Г(1,3334,1)) < 10000, что дает ш < 2.4999. Успех! Продолжаем возводить в квадрат и получаем все лучшую и лучшую грань, которая быстро сходится к значению 2.497723729083.... Если начать с Г(4,1,4) ф Г(1,9,1), а не с Г(3,1,3) ф Г(1,4,1), то предельной гранью будет значение 2.51096309----

[С помощью подобного ловкого приема получим ы < 2.496 (см. SICOMP 11 (1982), 472-492).]

68. Т. М. Вэри (Т. М. Уаг1) показал, что необходимо п-1 умножений, доказывая, что п

умножений необходимы для вычисления xf 4-----[Cornell Computer Science Report 120

(1972)]. Ч. Панду Ранган (С. Pandu Rangan) показал, что если вычислять такие полиномы,

как 1-1 ill 4-----hLn-iRn-i, где Li и Ri -линейные комбинации Хк, то необходимо хотя бы

п - 2 сложений для образования Li и Д,- [J. Algorithms 4 (1983), 282-285]. Но его нижняя грань, очевидно, не относится ко всем цепочкам полиномов.

69. Пусть yij = Xij - [i =j]. Примените рекурсивную конструкцию (31) к матрице / 4- У, используя арифметику степенных рядов от п переменных ytj и игнорируя все члены общей степени > п. Каждый элемент h матрицы представлен как сумма ho 4- hi 4- • 4- hn, где hk-значение однородного полинома степени к. Затем каждый шаг сложения приводит к п 4- 1 сложению и каждый шаг умножения приводит к » п умножениям и » п сложениям. Кроме того, каждое деление - это величина вида 1 4- hi 4- • • 4- hn, так как все деления в рекуррентной конструкции-это деления на 1, когда yij -полностью равны нулю; поэтому деление является незначительно более простым, чем умножение (см. 4.7-(3), где Уо = 1). Так как мы останавливаемся, когда размер определителя становится равным 2x2, нет необходимости вычитать 1 из yjj, когда j > п-2. Оказывается, если избавиться от избыточных вычислений, этот метод потребует 20(5)4-8(4)4-12(з)-4(2)4-5п-4 умножений и 20() 4- В{1) + Щ) + 24(5) - п сложений, т. е. п5 - 0{п*) операций. Подобный метод можно использовать для исключения деления во многих других случаях (см. СгеЛе 264 (1973), 184-202). (Однако в следующем упражнении строится конструкция, которая даже быстрее схемы без делений для определителей.)

70. Положим, что А = X - X, В = -и, C = -vhD = XI-Yb указанном равенстве,

затем вычислим определитель обеих частей, используя то, что А 4- Y/X + Y/X 4-----

обратная к D как формальный степенной ряд от 1/А. Следует вычислить иУ*г) только для О < А: < п - 2, так как известно, что /х(А)-полином степени п. Таким образом, необходимо всего п + 0{п) умножений и 4- 0{п) сложений для перехода от степени

n - 1 к степени п. Используя рекурсию, получим коэффициенты fx из элементов X после б() + 7(з) + 2(1) умножений и б(;) + 5() + 2() сложений-вычитаний.

Вычислив только detX = (-1)"/х(0), можно сэкономить 3(2) -п + 1 умножений и (") сложений. Этот свободный от деления метод для вычисления определителя на самом деле совершенно экономный, когда п - умеренная величина; это вариант схемы разложения по алгебраическим дополнениям, когда п > 4.

Если ш - показатель умножения матриц в упр. 66, то такое же приближение приводит к свободному от деления вычислению за 0(п"++) шагов, поскольку векторы иУ* для О < А: < п можно вычислить за 0(М(п) log п) шагов. Возьмем матрицу, первые 2 строк которой равны uY для О < А: < 2, и умножим ее на У. Тогда первые 2 строк произведения будут равны иУ* для 2 < А: < 2". [См. S. J. Berkowitz, Inf. Processing Letters 18 (1984), 147-150.] Конечно, такое "быстрое" асимптотическое умножение матриц представляет определенный теоретический интерес. Э. Калтофен (Е. Kaltofen) показал, как вычислять определители только с помощью 0{пу/М{п)) операций сложения, вычитания и умножения [Ргос. Int. Symp. Symb. Alg. Сотр. 17 (1992), 342-349]; его метод представляет интерес даже при М(п) = п.

71. Предположим, что 31 = ui о 1л, ..., gr = Ur о t;r и / = aigi + • • • + QrSr 4- ро, где Uk = /3*131 4- ••• + /3*(*-i)S*-i + Рк, Vk = fkigi + ••• + fk{k-i)9k-i + qk, каждый знак "о" является "х" или "/" и каждое pj или qj-полиномом степени < 1 от xi, х„. Вычислим произвольные величины Wk, Ук, Zk для А; = г, г - 1, ..., 1 следующим обра,эом:

Wk=ak+ Р{к+1)кУк+1 4- -flk+mZk+l + + РткУг + frkZr и

yk =Wk X Vk, Zk=Wk X Uk, если gjfc = ujfc X vk]

yk=WklVk, Zk = -укХ Qk, если Qk = Uk/Vk.

Затем / = po + plyr + qlZi -\-----Ь ргУг +qrZr, где означает производную по любому из

XI,..., х„. [W. Baur and V. Strassen, Theoretical Сотр. Sci. 22 (1983), 317-330. Родственный метод опубликовал С. Линнаинмаа (S. Linnainmaa, BIT 16 (1976), 146-160), который применил его к анализу округления ошибок.] Мы сэкономим два умножения в цепочке, если Уг = Ut X Vr, так как Wr = Ог. Повторив конструкцию, можно задать все вторые частные производные с максимум 9т + 3d умножениями в цепочке и 4d делениями.

72. Существует алгоритм вычисления ранга тензора над алгебраически замкнутыми полями, подобными комплексным числам, так как это частный случай результатов Альфреда Тарски (Alfred Tarski, А Decision Method for Elementary Algebra, and Geometry, 2nd edition (Berkeley, California: Univ. of California Press, 1951)). Однако известные методы не делают эти вычисления действительно осуществимыми, за исключением очень малых тензоров. Неизвестно, будет ли решена эта проблема над полем рациональных чисел за конечное время.

73. В таких цепочках полино.мов от Л переменных определитель любой матрицы размера N X N для N линейных форм, полученных после I шагов сложений-вычитаний, равен максимум 2. Ив дискретном преобразовании Фурье матрица последних N = mi.. .mn линейных форм имеет определитель N, поскольку ее квадрат равен N перестановкам матрицы из упр. 13 [JACM 20 (1973), 305-306].

74. (а) Если А: = (A:i,... ,A:s) - вектор взаимно простых целых чисел, значит, существует Uk, так как любой общий делитель элементов матрицы Uk делит все элементы А: = UUk. Следовательно, матрица VUk не может иметь все целые компоненты.

(Ь) Допустим, существует цепочка полиномов для Vx с t умножениями. Если t = О, твсе элементы матрицы V должны быть целыми числами, значит, s = 0. Иначе пусть А,- = а х А* или Ai = Aj X А* - первый шаг умножения. Можно предположить, что А*, = mxi + • • + ПаХ, + (S, где П1, ..., Па -целые числа, не все равные нулю, и /3 - постоянные. Найдем