Особое значение имеют следующие типы матриц. Матрица Вандермонда aij = xj

fX\ XI ... Хп\

xl xl ... xl

Комбинаторная матрица

aij = y + 6ijX /Х + У у ... у

У x + y ... у

\ V

... x + yj

Матрица Коши aij = l/(xi + yj)

1/(Х1+У2) ... l/(xi+j/„)

l/(a;2+J/l) 1/(Х2+У2) ... l/(X2 + J/„)

\l/(x„+yi) 1/(х„+У2) ... +

36. \M23] Покажите, что определитель комбинаторной матрицы равен х""(х + ni/). ► 37. [М24] Покажите, что определитель матрицы Вандермонда равен

П П ~

1<J<" l<t<j<n

38. [М25} Покажите, что определитель матрицы Коши равен

П iJ ~ i)(yj - Vi) / П (i+yj)

l<i<j<n I l<i,j<n

39. [M23] Покажите, что матрица, обратная комбинаторной,-этожомбинаторная матрица С элементами bij = {-у + Sij (х + пу))/х{х + пу).

40. [М24] Покажите, что элементы матрицы, обратной матрице Вандермонда, имеют вид / \

bi, =

(-iy-xfc,...xfc„ .

\1<*1<. ••<fc„ j<n *1.....k„-ii

/xi Д (Xk-Xi). I \<к<п

kjti

Пусть вас не пугает сложная сумма в числителе - это просто коэффициент при х- в многочлене (ц - х)... (хп - x)/(xi - х).

41. [М26] Покажите, что элементы матрицы, обратной матрице Коши, имеют вид

bij = ( П + ( + у*] /+ уп П -) ( П y-yi)

\1<к<п \l<fc<n /Vl<fc<n /

kjtj ki

42. [M18] Чему равна сумма всех п элементов матрицы, обратной комбинаторной?

43. [М24] Чему равна сумма всех п элементов матрицы, обратной матрице Вандермонда? [Указание. Воспользуйтесь упр. 33.]

> 44. [М26\ Чем> равна сумма всех п элементов матрицы, обратной матрице Коши?

► 45. [М25] Матрица Гильберта, которую иногда называют сегментом размера п х п (бесконечной) матрицы Гильберта,-это матрица, элементы которой имеют следующий вид: Oij - + J - 1). Покажите, «то матрица Гильберта является частным случаем матрицы Коши; найдите для нее oeparaVro матрицу; покажите, что все элементы этой обратной матрицы являются целыми числами и что сумма всех элементов обратной матрицы равна п. [Замечание. Матрицы Гильберта часто используются для тестирования различных алгоритмов, в которых выполняются операции над матрицами, так как, во-первых, они численно неустойчивы относительно преобразований и, во-вторых, для них известны обратные матрицы. Но было бы ошибкой сравнивать известную обратную матрицу, заданную в этом упражнении, с вычисленной обратной матрицей к матрице Гильберта, поскольку, пр>ежде чем находить обратную матрицу, необходимо округлить элементы первоначальной матрицы. В результате из-за уже упомянутой неустойчивости обратная матрица к округленной матрте Гильберта будет несколько отличаться от точного варианта обратной матрицы. Элементы обратной матрицы являются целыми числами, т. е. их не надо округлять, поэтому обратная матрица определена точно и можно попытаться ее обратить. Но заметим, что обратная матрица так же неустойчива, как и первоначальная. Кроме того, элементами обратной матрицы являются достаточно большие числа.] Для решения данной задачи необходимо знание основных фактов о факториалах и биномиальных коэффициентах, о которых будет говориться в разделах 1.2.5 и 1.2.6.

► 46. [МЗО] Пусть А - матрица размера m хп, а В - матрица размера пхт. При условии, что 1 < ji, J2, -. ,jm < п, обозначим через Ajij2...j„ матрицу размера тп х тп, состоящую из столбцов ji,..., jm матрицы А, а через Bjj.j -матрицу размера тпхт, состоящую из строк ji,..., jm матрицы В. Докажите тождество Бине-Коши

det(AB)= Y1 det(>l„j, .i„)det(Bi,j,...,„).

1<>1<У2<-<>т<П

(Обратите внимание на частные случаи; (i) т = п, (ii) m = 1, (iii) В - А, (iv) m > n, (v)m = 2.)

47. [M2T\ (K. Краттенхалер (С. Ktattenthaler).) Докажите, чт

+ 92)(ar-J-дз) (x-{-pi){x-k-q3) {x-k-p{){x-det -I-92)(y-I-дз) (у + Р1)(у-Ьдз) {y-k-pi){y \ (г + 92)(г-I-дз) {zP\){zqz) (z-l-pi

= (ar - y)(x - z){y - z){pi - дз){р1 - дз)(р2 - дз),

и обобщите это равенство для определителя матрицы размера п х п, зависящего от Зп - 2 переменных xi, Хп, Pi, . -., Pn-i, фг, ..., gn- Сравните полученную формулу с результатом упр. 38.

1.2.4. Целочисленные функции и элементарная теория чисел

Для произвольного действительного числа х введем следующие обозначения:

[arj -наибольшее целое, которое меньше или равно х ("пол" (floor) х);

\х] -наименьшее целое, которое больше или равно х ("потолок" (ceiling) х).

До 1970 года запись [х] часто использовалась для обозначения одной из этих двух функций, но обычно для первой. Приведенные выше обозначения, введенные К. Ю- Айверсоном в начале бО-х годов, более удобны потому, что на практике функции [х\ и [а;] встречаются одинаково часто. Функцию [х\ иногда называют целой частью числа х.

0l)(x-hp2)\ 0l){y+P2) I 9l)(2+P2)/

Приведем формулы и примеры, которые очень легко проверить:

[v/2j=l, \f2]=2, [+J=0, Г-1=0, [-J =-1 (а «е нулю!);

\х\ = [х\ тогда и только тогда, когда х - целое число; [х] = [xJ + 1 тогда и только тогда, когда х не является целым числом; [-xJ = - Н; X - 1 < [xJ < X < ("х] < X + 1.

в упражнениях, приведенных в конце раздела, даны также другие важные формулы, которые связаны с операциями "пол" и "потолок"

Для произвольных действительных чисел х и г/ определим следующую бинарную операцию:

X mod 2/= X - 2/[x/2/J, еслиуфО; xmodO = :?.

Из этого определения видно, что если у фО,то

0<-

У LyJ

xmody (2)

Следовательно,

a) если 2/ > О, то О < X mod у < у;

b) если 2/ < О, то О > X mod у > у;

c) величина х - (х mod у) является целочисленным кратным у.

Выражение xmody называется остатком от деления х на ?/; аналогично [х/у\ называется частным.

Если X и у являются целыми числами, то "mod" -это знакомая нам операция:

5 mod 3 = 2, 18 mod 3 = 0, -2 mod 3=1.

Имеем X mod у = О тогда и только тогда, когда х кратно у, т. е. тогда и только тогда, когда х делится на у. Запись у\х читается как "у делит х", т. е. у - это положительное целое число и х mod у - 0.

Операция "mod" применяется также в том случае, когда х иу принимают произвольные действительные значения. Например, для тригонометрических функций можно записать следующее:

tan X = tan (х mod тг).

Величина xmod 1-это дробная часть числа х. Из (1) получаем, что

X = [xJ -Ь (х mod 1). (4)

В работах по теории чисел сокращение "mod" часто используется в несколько ином, хотя и близком смысле. Для описания теоретико-числового понятия сравнимость (конгруэнтность) будем применять следующую запись:

X = у {по модулю z). (5)

Это означает, что х mod z = у mod г, т. е. х - у - целое число, Кратное z. Запись (5) читается следующим образом: х сравнимо с у по модулю г".