17. (а) Для удобства опишем алгоритм только для А = {а, 6}. Из наших посылок следует, что deg(Qi[7) = deg(Q2V) > О, deg(Qi) < deg(Q2). Если deg(Qi) = О, то Qi представляет собой просто ненулевое рациональное число, так что мы считаем Q = Qi/Qi- В противном случае пусть Qi = aQu + bQ\2 + ri, Q2 - aQ2i + 622 + Г2, где n и Г2 -рациональные числа; отсюда следует, что

QiU - Q2V = a{QnU - Q21V) + b{Qx2U - Q22V) + nU - Г2К

У нас должно быть либо deg(Qii) = deg(Qi)-l, либо deg(Qi2) = deg(Qi)-l. В первом случае, рассматривая члены высшей степени, которые начинаются с о, имеем deg(QiiJ7- Q21V) < degiQuU); так что можем заменить Qi на Qn, Q2 на Q21 и повторить процесс. Подобным образом в последнем случае можно заменить (Qi, Q2) на (Q12, Q22) и повторить процедуру.

(b) Положим, 4Todeg(J7)>deg(y). Если deg(jR) >deg(y), то заметьте, 4toQiU-Q2V = QiR - {Q2 - QiQ)V имеет степень, меньшую, чем deg(y) < deg{QiR), так что можно повторить процесс с U, замененным на R. Получим R = QV + R, U = {Q + Q)V + R, где deg{R) < deg{R), так что в конце концов решение будет получено.

(c) Алгоритм из (Ь) дает Vi = UV2 + R, deg{R) < deg(V2); в силу однородности R = Q и и однородно.

(d) Мы можем положить, что deg(y) < deg(J7). Если deg(y) = О, установить W U; в противном случае воспользуемся результатом (с) для поиска U = QV, так что QVV = VQV, {QV - VQ)V = 0. Отсюда следует, что QV = VQ, так что можно установить J7 4- У, У 4- Q и повторить процесс.

Более подробная информация о рассматриваемом вопросе приводится в работе Р. М. Cohn, Proc. Cambridge Phil. Soc. 57 (1961), 18-30. Существенно более сложная задача описания всех строковых полиномов, таких, что UV = VU, была решена Дж. М. Бергманом (G. М. Bergman) [Ph. D. thesis, Harvard University, 1967].

18. [P. M. Cohn, IVansactions 0/ the Amer. Math. Soc. 109 (1963), 332-356.]

Cl. Установить «1 Ul, U2 4- U2, fi Vi, Щ 4- У2, zi +- z2 w\ w2 <r- 1,

zl 4- 22 4- Ц Ш2 0, n 4- 0.

C2. (B этот момент выполняются данные в условии упражнения тождества и uiDi = U1V2; V2 = О тогда и только тогда, когда щ = 0.) Если V2 = О, алгоритм завершается с Н0ПД(У1, У2) = vi, Н0ЛК(У1, V2) = 2iyi = -222- (Кроме того, в силу симметрии имеем Н0ЛД({/1, Г/г) = U2 и H0nK(J7i, Г/г) = Uiwi = -U2W2.)

СЗ. Найти Qk R, такие, что vi - Qv2 + R, где deg(jR) < deg(D2). (Имеем ui{Qv2+R) = U2V2, так что uiR = («2 - uiQ)v2 = Rv2.)

04. Установить {wi, гиг, ul, w2, 21, 22, 21, 22, г*1, иг, vi, V2) (wl - wiQ, w2 - 12, wi,W2, 21, 22, 21 -Q2i, 22 -Q22, U2-U1Q, ui, 1)2, V1-QV2) и n n + 1. Вернуться к шагу C2. I

Это расширение алгоритма Евклида включает большинство особенностей, которые встречались в предыдущих расширениях алгоритма Евклида. Это приводит нас к новому пониманию уже рассмотренных частных случаев. Для доказательства корректности алгоритма сначала заметим, что deg(D2) уменьшается на шаге С4, так что алгоритм обязательно завершается. По завершении алгоритма vi представляет собой общий правый делитель Vi и Уг, поскольку u;ii;i = (-1)"У1 и -W2V1 = (-1)"Уг. Также, если d является любым общим правым делителем Vi и V2, он является и правым делителем ziVi +zV2 = vi. Следовательно, i;i = Н0ПД(У1,Уг). Кроме того, если т является любым общим левым кратным Vl и Уг, без потери общности можно считать, что m = UiVi = U2V2, поскольку последовательность значений Q не зависит от Ui и U2. Значит, т = (-1)"(-U22i)yi = (-1)"(г*222)Уг кратно 211.

На практике, чтобы вычислить только Н0ПД(У1, V2), можно опустить вычисление п, wi, W2, wl, W2, zi, Z2, zl, z2. Эти дополнительные величины были добавлены к алгоритму, в первую очередь, чтобы более просто установить его корректность.

Примечание. Нетривиальное разложение строковых полиномов, таких, как приведенные в качестве примера в этом упражнении, могут быть найдены из матричных тождеств наподобие

/о 1W6 iWc IW0 IWO IWO О

\1 о)\1 о)\1 о)\1 -с)\1 -ь)\1 -а)~\0 iJ поскольку эти тождества выполняются даже при некоммутативности умножения, например

(обе + а + с)(1 -I- Ьо) = (оЬ + 1){сЬа + а + с).

(Сравните это с континуантами из раздела 4.5.3.)

19. [См. Eugene Cahen, Theorie des Nombres 1 (Paris, 1914), 336-338.] Если такой алгоритм существует, то в соответствии с рассуждениями из упр. 18 D является НОПД. Рассмотрим А к В как единую матрицу С размера 2п х п, первые п строк которой представлены строками А, а следующие п строк - строками В. Точно так же можно комбинировать матрицы Р и Q в матрицу R размера 2пхп, а X и Y - в матрицу Z размера п х 2п. Требуемые условия теперь сводятся к двум уравнениям: С = RD, D = ZC. Если можно найти целочисленную матрицу U размера 2п х 2п с детерминантом ±1, такую, что все последние п строк U~C нулевые, то решением будут матрицы R = (первые п столбцов U), D = (первые п строк U~C), Z = (первые п строк [/"). Поэтому можно использовать, например, следующий алгоритм (с m = 2п).

Алгоритм Т (Триангуляризация). Пусть С - целочисленная матрица размера т х п. Данный алгоритм находит целочисленные матрицы U viV размера тхт такие, что UV - I и VC представляет собой треугольную матрицу (такую, что элемент на пересечении г-й строки и j-ro столбца матрицы VC равен нулю, если i> j).

Tl. [Инициализация.] Установить J7 4- У /(/ - единичная матрица размера mхт)

и Т 4- С. (На протяжении всего алгоритма будут выполняться соотношения

Т = VC hUV = 1.)

Т2. [Итерация по j.] Выполнить шаг ТЗ для j = 1, 2, ..., niin(m, п); затем прекратить выполнение алгоритма.

ТЗ. [Обнуление столбца j] Не выполнять следующие действия или выполнять их до тех пор, пока Ту не станет равным нулю для всех i > j. Пусть Tkj -ненулевой элемент {T,j,T(j+i)j,..., Tmj}, имеющий наименьшее абсолютное значение. Переставим строки к и j матриц Т и У и переставим столбцы к и j матрицы и. Затем вычтем строку j из строки i [Tij/Tjj\ раз в матрицах Т и У и прибавим столько же раз столбец i к столбцу j в матрице U для j < i < т.

Для приведенного в упражнении примера алгоритм дает (3 I) = Ц j), (2 j) =

(2 DCo -1). (о = (2 -2)(з 4) + а о)(2 (На самом деле в этом частном случае НОПД будет являться любая матрица с детерминантом ±1.)

20. Рассмотрите построение из упр. 4.6.2-22, но такое, что р™ заменено малым числом е.

21. Для получения верхней грани положим, что алгоритм R используется только при m - п < 1 и коэффициенты ограничены согласно (26) с m = п. [Указанная формула дает практическое время вычисления, а не только верхнюю грань. Более подробную информацию можно найти в работе G. Е. Collins, Ргос. 1968 Summer Inst, on Symbolic Mathematical Computation, edited by Robert G. Tobey (IBM Federal Systems Center, June, 1969), 195-231.]

22. Последовательность знаков не может содержать два идущих подряд нуля, поскольку Uk+i{x) - ненулевая константа в (29). Кроме того, в качестве подпоследовательности не может встретиться "+, О, +" или "-, О, -" Формула V(u,a) - V{u,b), очевидно, верна при 6 = а, так что ее необходимо проверить только при увеличивающемся 6. Полиномы щ{х) имеют конечное количество корней, и V(u, Ь) изменяется только тогда, когда 6 встречается или проходит через такие корни. Пусть х - корень некоторого (возможно, нескольких) Uj. Когда 6 увеличивается от х - б до х, знаковая последовательность около j переходит от "+, ±, -" к "+, О, или от "-, ±, +" к "-, О, +" при 3 > 0; при j = О -от "+, -" к "О, -" или от "-, +" к "О, +" (поскольку и(х)-производная, и(х) отрицательна при уменьшении и(х)). Таким образом, изменение V составляет -5jo- При возрастании Ь от х до X + б подобное рассмотрение показывает, что V остается неизменным.

[Л. Э. Хайндел (L. Е. Heindel) в работе JACM 18 (1971), 533-548, применил эти идеи для построения алгоритма обособления действительных нулей данного полинома и(х) за время, растущее как полином от deg(w) и logN, где все коэффициенты Uj-целые числа \щ\ N, а все операции абсолютно точны.]

23. Если V имеет п - 1 действительный корень между п действительными корнями и, то, рассмотрев изменения знаков, получим, что и(х) mod v{x) имеет п - 2 действительных корня, лежащих между п-1 корнем v.

24. Сначала покажите, что hj = д/ •••52 > а затем -что

показатель степени в левой части (18) имеет вид йг +5ix, где х = йг Н-----1- +

1 - 62(63 + +6j-i + 1) -<5з(1 - 52){б4 + • • • +<5j-i + 1)-----5j-i{l - йг)... (1 - <5j-2)(l).

Однако X = 1, поскольку он не зависит от 6j-i, и можно принять, что iJj-i = О, и т. д. Подобное доказательство работает и для дз, gt, , а упрощение-для (23).

25. Каждый коэффициент Uj{x) может быть выражен как детерминант, в котором один столбец Содержит только £{и), i{v) и нули. Чтобы использовать этот факт, модифицируем алгоритм С следующим образом. На шаге С1 установим д +- gcd{i{u), i{v)) и /i +- 0. На шаге СЗ, если к = О, установим и{х) +- v{x), v{x) +- r{x)/g, h +- £{uY/g, g +- i{u) и вернемся к шагу С2. В противном случае будем работать по немодифицированному алгоритму. Эффект этой новой инициализации заключается в простой замене и,(х) иа Uj{x)/gcd{e{u),e{v)) для всех j > 3. Таким образом, в (28) j-* становится £2j-«,

26. Фактически верно даже большее. Обратите внимание, что алгоритм из упр. 3 вычисляет ±Рп{х) и Tqn{x) для п > -1. Пусть е„ = deg(g„) и d„ = deg(p„u - q„v). В упр. 3 мы видели, что d„ i + е„ = deg(u) для п > 0. Докажем, что условия deg(g) < е„ и deg(pu - qv) < dn-2 влекут за собой р(х) = c{x)pn-i{x) и q(x) = c(x)g„ i(x). По данным р и q можно найти с(х) и d(x), такие, что р(х) = c(x)p„ i(x) + d(x)p„(x) и q{x) = c(x)g„ i(x) + d(x)g„(x), поскольку p„-i(x)g„(x) - p„(x)g„-i(x) = ±1. Следовательно, pu - qv = c{pn-iu-qn-iv)+d(p„u-q„v). Если d(x) ф 0, мы должны иметь deg(c) +e„ i = deg(d) + e„, так как deg(g) < deg(g„). Отсюда следует, что deg(c) + d„-i > deg(d) + d„, поскольку это, несомненно, верно, если dn = -00. В противном случае dn-i + вп = d„ +е„+1 > d„ + е„-1. Таким образом, deg(pu - qv) = deg(c) + d„-i. Но мы предположили, что deg(pu - qv) < dn-2 = d„-i + вп - e„ i, так что deg(c) < е„ - e„ i и deg(d) < О, что приводит к противоречию.

[Этот результат, по сути, получен в работе L. Kronecker, Monatsberichte Konigl. preuB. Akad. Wiss. (Berlin, 1881), 535-600. Отсюда вытекает следующая теорема. "Пусть u(x) и v{x) - взаимно простые полиномы над полем и пусть d < deg(t;) < deg(w). Если q(x) является полиномом наименьшей степени, таким, что существуют полиномы р(х) и г(х), такие, что р(х)и(х) - q{x)v{x) = г(х) и deg(r) = d, то p{x)/q{x) = pn{x)/qn{x) для некоторого п". Для dn-2 > d > dn-i существует решение q{x), такое, что deg(q) = e„ i +d - dn-i < en- Итак, все решения столь низкой степени имеют указанное свойство.]