модифицировать Si, Ег и Ез таким способом, что тождество останется справедливым без добавления каких-нибудь новых трилинейных членов. Следовательно, М(п) < -Ь - п, когда п четное. Ь) Используйте метод (а), чтобы показать, что две независимые задачи умножения матриц размера т х п х s можно выполнить с mns + тп + ns + sm некоммутативными умножениями.

61. [М26] Пусть {Ujk)-тензор над произвольным полем. Определим rankd(tyfc) как минимальное значение г, такое, что существует реализация вида

Y,4iiu)bj,{u)ck,{u) = U,ku+0{u+), 1=1

где ац{и), bji{u), Cki{u)-полиномы от и над полем. Таким образом, гапко-обычный ранг тензора. Докажите, что

a) Ta.nkd+i{Ujk) < rankd(tyfc);

b) T&nk{Ujk) < гапкДу,);

c) Tankd{{tijk) Ф (tijk)) < iankd{tijk) +Ta,nkd{tijk) в смысле упр. 48;

d) iankd+d>{{tijk) <» {tijk)) < Taakd{tijk) Taakd>{t,jk);

e) Taakd+d{{tijk) <8 (tijk)) < гапк-(г(<;д,)), где г = Ta,nkd(tijk) и гТ означает прямую сумму Г ® • • • ® Т г копий Т.

62. [М24] Гранью ранга тензора (tijk), обозначенной через laxiklUjk). называется mmd>oTankd(tijk), где гапк определен в упр. 61. Докажите, что тензор (J °) J) имеет ранг 3, но грань ранга 2 над каждым полем.

63. [НМЗО] Пусть Т(т, п, s) -тензор умножения матрицы, как в упр. 60, и пусть M(N) - ранг T(N,N,N).

a) Покажите, что Т(т, п, s) 0 Т(М, N, S) = Т(тМ, nN, sS).

b) Покажите, что Tan.kd(T(mN,nN,sN)) < raiikd{M(N)T(m,n,s)) (см. упр. 61, (е)).

c) Если Т(т, п, s) имеет ранг < г, покажите, что M(N) = С)(ЛГ("».".».-)) при N оо, где u!(m, п, S, г) = 3 log г/ log mns.

d) Если грань ранга тензора (m,?!,) < г, покажите, что М(Л) = C>(A*"(logA)).

64. [МЗО] (А. Шёнхаге (А. Schonhage).) Покажите, что гаак2(Т(3,3,3)) < 21, так как

M(N)=0(N-).

► 65. [М27] (А. Шёнхаге.) Покажите, что

rank2(T(m, 1, п) ® Т(1, (m-l)(n-l), 1)) = тп+1. Указание. Рассмотрите трилинейную форму

т п

+ + иУц){ + "го) -(Х1+-- +Хт)(у1 + + Vn)Z,

1 = 1 j = l

когда 1:.,А„=Е;=1Уи=0.

66. [НМЗЗ] Воспользуйтесь результатом упр. 65 для уточнения асимптотических граней из упр. 63.

a) Докажите, что существует предел ш = Ишп-юо log М(n)/log п.

b) Докажите неравенство (mns)" < rank(Jfm. п. sX).

c) Пусть t-тензор T(m,n,s) ® T{M,N,S). Докажите, что (mns) + (MNS)" < rankftV Указание. Рассмотрите прямое произведение t с самим собой.

d) Докажите, следовательно, неравенство 16" + 9" < 17 и получите, что ш < 2.55.

67. [НМ40] (Д. Копперсмит (D. Coppersmith) и Ш. Виноград.) Обобщая упр. 65 и 66, можно получить даже лучшую верхнюю грань ш.

a) Скажем, тензор (Ujk) является невырожденным, если raak(tiyt)) = m, rank(tj(t,)) = п и raak{tk(ij)) = s в обозначениях леммы Т. Докажите, что тензор T{m,n,s) для умножения матриц размера тп х ns является невырожденным.

b) Покажите, что прямая сумма невырожденных тензоров является невырожденной.

c) Тензор t размера m х п х s с реализацией {А, В, С) длиной г называется допускающим улучшение, если он невырожден и существуют ненулевые элементы di, ..., dr, такие, что ]С[=1 aubjidi = о для 1<1<ти1<<п. Докажите, что в подобном случае грань ранга t ф Т{1,д, 1) < г, где q = г - т - п. Указание. Существуют матрицы V и W размера g х г, такие, что X;i=i vubjidi = XIii auWjidi = о и YL\=i vuWjidi = 6ij для всех соответствующих i и j.

d) Объясните, почему результат упр. 65 является частным случаем (с).

e) Докажите, что неравенство гаак(Г(т, п, s)) < г влечет

rank2(T(m, п, s) 0 Г(1, г - п{т + s - 1), 1)) < г + п.

f) Докажите, следовательно, что ш действительно меньше, чем log M(n)/log п для всех п > 1.

g) Обобщите (с) на случай, когда {А,В,С) - реализация t, только в слабом смысле упр. 61.

h) Из (d) следует, что гапк(Г(3,1,3)®Г(1,4,1)) < 10. Тогда из упр. 61, (d) также получим гаак(Г(9,1, 9) ® 2Г(3,4, 3) 0 Т(1,16,1)) < 100. Докажите, что, если просто удалить строки А VL в, соответствующие 16 + 16 переменным Т(1,16,1), можно получить реализацию Т(9,1,9) 0 2Г(3, 4,3), которая допускает улучшение. Значит, фактически получим галк(Т(9,1,9)0 2Г(3,4,3)® Г(1,34,1)) < 100.

i) Обобищв упр. 66, (с), покажите, что

Х(трПр5р)"/ < rank(ф Т(тр, Пр, Sp)). р=1 р=1

j) Докажите, следовательно, что ш < 2.5.

68. [М45] Можно ли вычислить полином

XiXj - Х\Х2 + Xn~lXn

l<i<j<n

с меньшим, чем п-1, количеством умножений и 2п-4 сложений? (Существует (j) членов.)

► 69. [НМ27] (В. Штрассен (V. Strassen), 1973.) Покажите, что определитель (31) матрицы размера пхп можно вычислить, произведя О(п) умножений и 0{п) сложений или вычитаний, но не делений. [Указание. Рассмотрите det(/ + Y), где Y = X - i.]

► 70. [НМ25] Хороктермстмческмйполммоле/А-(Л)матрицыХопределяется KaKdet (Л/-X). Докажите, что если А = ( у), где X, и, v иУ соответственно имеют размеры пхп, 1 X (п - 1), (п - 1) X 1 и (п - 1) X (п - 1), то

/х(Л) = /ИЛ) [Х-х--- - -------j.

Покажите, что это отношение позволяет вычислить коэффициенты fx с приблизительно п* умножениями, п* сложениями-вычитаниями и без делений. Указание. Используйте равенство

/А b\ fl 0 \ /a-bd-c в\ / I 0\

[с d)~\o d)\ о i)[d-c IJ

которое справедливо для любых матриц А, В, С я D размеров lxl,lxm., mxliimxm соответственно, когда D невырождена.

► 71. [НМЗО] Цепочка отношений полиномов подобна цепочке полиномов, но она допускает деление, как и сложение, вычитание и умножение. Докажите, что если /(xi,..., Хп) можно вычислить цепочкой отношений полиномов, имеющей т умножений в цепочке и d делений, то /(xi,..., Хп) и все п ее частные производные 9/(xi,..., Хп)/дхк для 1 < fc < п можно вычислить единственной цепочкой отношений полиномов, которая имеет максимум Зт + d умножений в цепочке и 2d делений. (Например, любой эффективный метод вычисления определителя матрицы приводит к эффективному методу вычисления всех ее алгебраических дополнений, а значит, и к эффективному методу вычисления обратной матрицы.)

72. [М48] Можно ли определить ранг любого данного тензора [tijk) над, скажем, полем рациональных чисел за конечное число шагов?

73. [НМ25] (Я. Моргенстерн (J. Morgenstern), 1973.) Докажите, что любая цепочка полиномов для дискретного преобразования Фурье (37) имеет по крайней мере mi ... Шп Ig mi... mn сложений-вычитаний, если не существует умножений в цепочке и если каждый параметр умножения является комплексной постоянной с q:j < 1. Указание. Рассмотрите матрицы линейных преобразований, вычисленных за первые к шагов.

74. [НМ35] (А. Нозаки (А. Nozaki), 1978.) Большая часть теории, посвященной вычислению полиномов, касается умножения в цепочке, однако умножение нецелочисленных постоянных также может быть весьма важным. Назначение этого упражнения - развить соответствующую теорию. Скажем, что векторы vi,...,Vs действительных чисел Z-зависимы, если существуют целые числа (fci,...,fcs), такие, что gcd(fci,..., fc) = 1 и k\V\ + + ksVs -полностью целочисленный вектор. Если не существует таких целых чисел (fci,..., fcs), то векторы vi, ..., Vs называются Z-независимыми.

a) Докажите, что если столбцы матрицы V размера г х s Z-независимы, то существуют столбцы матрицы VU, где U - любая унимодулярная матрица размера sx s (матрица из целых чисел с определителем, равным ±1).

b) Пусть V - матрица размера г х s с Z-независимыми столбцами. Докажите, что цепочка полиномов, которая вычисляет элементы Vx, зависящие от xi,...,Xs, где х = (xi,..., Xs), производит по крайней мере s умножений.

c) Пусть V - матрица размера г х t, имеющая s Z-независимых столбцов. Докажите, что цепочка полиномов, которая позволяет вычислить элементы Vx, зависящие от Xl,..., Х(, где X = (xi,..., Х(), обязательно производит по крайней мере s умножений.

d) Покажите, как вычислить пары значений {х/2 + у, х + у/3}, которые зависят от х и у, используя только одно умножение, несмотря на то, что необходимы два умножения для вычисления пары {х/2 -(- у, х -(- у/2}.