algebra.1semestr.lectures1-16

Предложение 70. Ek примитивный корень n-ой степени из 1 если и только если (k; n) = 1.

Доказательство. ). Так как Ek примитивный корень, то E1 = Ekl = E1kl для некоторого l, следовательно E1kl¡1 = 1. Рассматривая диаграмму для корней получаем, что n делит kl ¡ 1, поэтому (k; n) = 1.

(. Поскольку k и n взаимно просты, то существуют целые u; v такие, что ku + nv = 1.

Тогда E1 = E1ku+nv = (E1k)u ¢ (E1n)v. Поскольку E1k = Ek и E1n = 1, то Eku = E1, и тогда

Ekul = E1l = El для любого l = 0; : : : ; n ¡ 1.

Итак, все корни El встречаются в последовательности Eki , i = 1; : : : ; n ¡ 1, поэтому Ek примитивный корень. ¤

Например, среди корней 10-ой степени из единицы только E1; E3; E7 и E9 являются примитивными.

Следствие 71. Число примитивных корней n-ой степени из единицы равно '(n).

7. Лекция 7

L7

7.1. Перестановки и подстановки. Пусть X множество из n элементов. Поскольку индивидуальность этих элементов для нас не важна, то можно считать, что X = f1; 2; : : : ; ng состоит из первых n натуральных чисел.

Определение 72. Подстановкой называется любое биективное отображение f : X ! X.

Заметим, что любую подстановку можно записать в виде таблицы

f =	Ãf(1)	f(2) ::	::	::	f(n)!
	1	2			n

Поскольку f биекция, то в (нижней) строке (f(1); : : : ; f(n)) все числа от 1 до n встречаются без повторений. Строка вида (f(1); : : : ; f(n)) с последним свойством называется перестановкой из n чисел. Поскольку любая перестановка однозначно определяется своей подстановкой (и наоборот), то мы будем допускать определенную вольность в использовании этих терминов.

Предложение 73. Количество различных перестановок из n чисел равно n! = 1 ¢2 ¢¢ ¢ ¢¢n.

Например 4! = 1 ¢ 2 ¢ 3 ¢ 4 = 24, а число 100! превосходит число атомов во Вселенной.

Доказательство. Докажем утверждение индукцией по n, причем для n = 1 оно очевидно. Предположим, что мы уже проверили предложение для n, и докажем его для n + 1.

Единица может занимать первую, вторую, : : : , (n + 1)-позицию в перестановке длины n + 1. Для каждой из этих n + 1 возможностей оставшиеся n чисел могут быть расположены на

незанятые n мест n! способами. Ясно, что все такие перестановки будут различны.
Итак, общее число способов равно (n + 1) ¢ n! = (n + 1)!.	¤

21

Ясно (объясните почему!), что число различных подстановок на множестве из n элементов также равно n!.

Определим произведение подстановок f и g как их композицию: (fg)(i) = g(f(i)), то есть

первой применяется отображение f. Например, пусть
	1	2	3			1	2	3
	f = Ã3	2	1!	и	g =	Ã2	3	1! :
f	g							f	g

Тогда вычисляя 1 ¡! 3 ¡! 1 мы видим, что fg оставляет 1 на месте. Аналогично 2 ¡! 2 ¡! 3

дает fg(2) = 3, и тогда fg(3) = 2. Итак, fg = ( 11 23 32 ).

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

Предложение 74. Множество Sn всех подстановок на множестве из n элементов с только что введенной операцией умножения образует группу.

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

Пусть ¼ = (a1; : : : ; an) перестановка из n чисел, и fi; jg, i 6= j (неупорядоченная) пара элементов X. Мы скажем, что fi; jg порядок в ¼, если i < j и i стоит в (a1; : : : ; an) левее j, или i > j и i стоит в (a1; : : : ; an) правее j (то есть i; j появляются в перестановке (a1; : : : ; an) в естественном порядке). В противном случае скажем, что пара fi; jg образует

беспорядок (или инверсию) в ¼.

Например, в перестановке (132) пара f1; 2g образует порядок, а пара f2; 3g беспорядок.

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

Например, для перестановки (132) пары f1; 2g и f1; 3g образуют порядок, а пара f2; 3g

беспорядок, поэтому эта перестановка нечетная. С другой стороны (проверьте!) (231)

четная перестановка. Кроме того (объясните почему!) тождественная перестановка четная.

Определение 76. Транспозицией (ij), i =6 j называется подстановка f такая, что f(i) = j, f(j) = i и f(k) = k для любого k =6 i; j.

Транспозиция (ij) переставляет i и j местами и оставляет все остальные элементы на месте. Мы будем употреблять тот же символ для обозначения соответствующей перестановки. Заметим, что в транcпозиции (ij) пара fi; jg образует беспорядок, а все остальные пары образуют порядок. Поэтому любая транспозиция нечетна.

Теорема 77. Если перестановку умножить справа на транспозицию, то ее четность изменится на противоположную.

Доказательство. Пусть транспозиция (ij) применяется к перестановке ¼. Предположим сначала, что числа i; j стоят в ¼ на соседних местах.

22

Итак, ¼ = (: : : ij : : : ) и ¼(ij) = (: : : ji : : : ). Если fi; jg порядок в ¼, то он станет беспорядком в ¼(ij) и наоборот. Любая другая пара fk; lg является порядком в ¼ если и только если она является порядком в ¼(ij), откуда и следует нужное нам утверждение.

Рассмотрим теперь общий случай когда между i и j в ¼ стоят s ¸ 1 элементов: ¼ = (: : : ; i; a1; : : : ; as; j : : : ). Последовательно применим к ¼ траспозиции (i; a1), (i; a2), : : : , (i; as), то есть протащим i через набор (a1; : : : ; as), получая перестановку (: : : ; a1; : : : ; as; i; j : : : ) (мы применили s транспозиций). По первому шагу доказательства каждый раз четность перестановки меняется.

Теперь протащим j в начала кортежа a1; : : : ; as; i последовательно применяя транспозиции (ij), (as; j), : : : , (a1; j) (всего s + 1 транспозиций). В итоге мы получим нужную перестановку (: : : j; a1; : : : ; as; i : : : ). Общее число примененных транспозиций 2s + 1 нечетно, поэтому конечная перестановка ¼(ij) имеет четность противоположную четности ¼. ¤

Например, поскольку тождественная перестановка четна, то любая транспозиция является нечетной перестановкой.

Используя эту теорему, мы можем подсчитать число четных перестановок.

Предложение 78. При n > 1 число четных перестановок равно n!=2, и число нечетных перестановок равно n!=2.

Доказательство. По только что доказанной теореме умножение на транспозицию (12) задает отображение ® из множества четных перестановок в множество нечетных перестановок и наоборот, причем ®2 тождественное отображение. Из этого вытекает, что множества четных и нечетных перестановок содержат одинаковое число элементов. ¤

pere Предложение 79. От одной подстановки можно перейти к любой другой, умножив справа на конечное число транспозиций.

Доказательство. Пусть ¼ = (a1; : : : ; an) и ¾ = (b1; : : : ; bn) и a1 =6 b1. Тогда перестановка ¼(a1b1) = (b1; c2; : : : ; cn) имеет ту же (что и ¾) первую букву.

1

¼ ÄÄÄı?????¾

ÄÄÄ ?? a1±±;b1

(a1; b1)

Осталось применить индукцию по n (проделайте это!).

¤

Теорема 80. Любая подстановка разлагается в произведение транспозиций.

pere

Доказательство. Вытекает из предложения 79 (проведите необходимые рассуждения!). ¤

8. Лекция 8

L8

Если ¼ перестановка (или подстановка), то положим "(¼) = 1, если ¼ четная, и "(¼) = ¡1, если ¼ нечетная.

23

Следствие 81. Если ¼ = ¾1 ¢ : : : ¢ ¾k разложение перестановки ¼ в произведение транспозиций, то "(¼) = (¡1)k.

Доказательство. Ясно, что "(e) = 1. Кроме того, ¼ = e ¢ ¾1 ¢ : : : ¢ ¾k, и при применении каждой транспозиции четность перестановки меняется. ¤

Это следствие позволяет более просто (чем напрямую из определения) вычислять четность перестановки.

			1	2	3	4
Пример 82. Вычислить четность подстановки ¼ = Ã2				1	4	3!.
1	2	3	4			1	2	3	4
Решение. Имеем ¼ ¢ (12) = Ã1	2	4	3!, следовательно ¼(12)(34) = Ã1				2	3	4! = e.

Домножая это равенство на (34)(12) справа, получаем (объясните почему!) ¼ = (34)(12). Итак, "(¼) = (¡1)2 = 1, следовательно ¼ четная подстановка. ¤

Нетрудно привести пример (сделайте это!), что разложение подстановки в произведение транспозиций не единственно. Ситуацию можно исправить, разлагая подстановки в произведение циклов.

Определение 83. Подстановка ¼ называется циклом (длины k), если существуют различные i1; : : : ; ik такие, что ¼(i1) = i2, ¼(i2) = i3, : : : , ¼(ik¡1) = ik и ¼(ik) = i1 (то есть ¼ переставляет эти элементы по циклу).

i1 xxxxxxxx<±FFFFFFFF#

ik ±Y444 ®± i2 444±o_ _ _±¦®®®®®

ik¡1 i3

Мы будем использовать тот же термин, и то же обозначение (i1i2 : : : ik) для соответствующей ¼ перестановки.

shov Замечание 84. Четность цикла (i1i2 : : : ik) равна (¡1)k¡1.

Доказательство. Это утверждение вытекает из равенства (i1i2 : : : ik) = (i1i2)(i1i3) : : : (i1ik) (докажите это равенство!). ¤

Определение 85. Мы скажем, что циклы (i1; : : : ; ik) и (j1 : : : jl) независимы, если множества fi1; : : : ; ikg и fj1 : : : jlg не пересекаются.

Если ¼ перестановка, то supp(¼) состоит из чисел i таких, что ¼(i) =6 i (то есть из чисел, на которых ¼ действует нетривиально).

Лемма 86. Если ¼ и ¾ независимые циклы, то ¼¾ = ¾¼ (то есть эти циклы коммутируют).

24

Доказательство. Пусть C = supp(¼), D = supp(¾). По условию C \ D = ;. Тогда ¼¾ действует как ¼ на C, как ¾ на D, и тождественно на остальных числах; и то же самое верно для ¾¼. ¤

Это утверждение перестает быть верным, если циклы "зацепляются".

Пример 87. Пусть ¼ = (12) и ¾ = (23). Тогда ¼¾ = (132) =6 (123) = ¾¼.

Теорема 88. Любая перестановка ¼ =6 e 2 Sn является произведением независимых циклов длины ¸ 2, ¼ = ¼1 : : : ¼k, причем это разложение единственно с точностью до перестановки циклов.

Доказательство. Докажем сначала существование такого разложения.

Если supp ¼ = ;, то ¼ = e. Иначе выберем i1 2 supp ¼. Положим i2 = ¼(i1), i3 = ¼(i2) = ¼2(i1) и т. д. Поскольку наше множество конечно, то найдутся k; m ¸ 0 такие, что im = im+k+1. Сокращая (объясните, почему это возможно!) получаем i1 = ik+1. Выбирая самое маленькое такое k, заключаем, что все числа i1; : : : ; ik различны, следовательно ¼1 = (i1; : : : ; ik) цикл. Кроме того, ясно что ¼ = ¼1 ¢ ¼0, где ¼0 перестановка, действующая тождественно на supp(¼1). Осталось применить индукция по размеру supp(¼).

Проверим теперь единственность. Пусть ¼ = ¾1 ¢ : : : ¢ ¾l другое представление ¼ в виде произведения независимых циклов. Рассмотрим i1 2 supp(¼). Перенумеровав циклы, можно считать, что i1 2 supp ¼1; supp(¾1).

Поскольку все циклы в произведениях независимы, то i2 = ¼(i1) = ¼1(i1) = ¾1(¼1), в частности i2 2 supp(¼1); supp(¾1). Аналогично получаем, что весь цикл (i1; : : : ; ik) содержится в носителях ¼1; ¾1, и действия ¼1; ¾1 на этих числах совпадает с действием ¼. Из этого в частности вытекает, что ¼1 = ¾1. Сокращая равенство ¼ = ¼1 : : : ¼k = ¾1 : : : ¾l на ¼1 = ¾1, получаем ¼2 : : : ¼k = ¾2 : : : ¾l, следовательно достаточно применить индукцию по

мощности supp(¼) (проделайте это!).			¤
	shov
Из замечания		сразу же вытекает
	84

Следствие 89. Если ¼ = ¼1 ¢ : : : ¢ ¼k разложение перестановки ¼ в произведение независимых циклов ¼i длины ki, то "(¼) = Qki=1(¡1)ki¡1.

9. Матрицы

Под матрицей размера m £ n мы понимаем прямоугольную таблицу чисел (действи-

тельных или комплексных). Например, A =

2

¡1

3

2 £ 3 матрица составленная из

p

2

4

¡2

действительных чисел. Мы различаем в

матрице строки, которые нумеруются сверху вниз

³

´

и столбцы, которые нумеруются слева направо. Например, (p

; 4; ¡2) вторая строка

2

матрицы A, а

3

третий столбец этой матрицы. (Единственный!) элемент матрицы A,

¡2

стоящий на

пересечении i-ой строки и j-го столбца, обозначается a . Например, a

12

=

¡

1

¡

¢

ij

и a23 = ¡2.

Множество матриц фиксированного размера m £ n обозначается через Mm;n (обычно в скобках еще указывается поле, например R или C). Мы определим на этом множестве операцию сложения. А именно, если A; B 2 Mm;n, тогда C = A + B будет обозначать

25

матрицу того же размера, где cij = aij + bij (то есть сложение происходит покомпонентно).

¡

для

¡

¢

¡

¡3 2

¢

¡

¢

Например, если A =

1 ¡2

и B =

, то C = A+B =

¡2 0

, например c12

= a12 +b12 =

2 + 2 = 0

3 4

¡2 1

1 5

элемента стоящего в верхнем правом углу.

Свойства операции сложения немедленно вытекают из свойств сложения чисел (действительных или комплексных).

1)A + (B + C) = (A + B) + C для любых матриц A; B и C (одинакового размера).

2)A + B = B + A.

3)Пусть Om;n обозначает m £ n матрицу состоящую из одних нулей. Тогда A + Om;n = Om;n + A = A для любой матрицы A 2 Mm;n, то есть Om;n нейтральный элемент относительно сложения.

4)Если ¡A обозначает матрицу у которой (¡A)ij = ¡aij, то A + (¡A) = Om;n.

Итак, относительно сложения множество матриц фиксированного размера образует абелеву группу.

Квадратные матрицы (порядка n) это матрицы размера n £ n (то есть число строк равно числу столбцов). Множество квадратных матриц порядка n обозначается Mn.

Матрицы также можно умножать на (действительное или комплексное) число, получая матрицы того же размера. А именно, для ¸ 2 R; C положим (¸A)ij = ¸aij, то есть любой

элемент A умножается на ¸. Например 2	¢ ¡	2	¡1	=	¡	4	¡2	. Следующие свойства этой
операции почти очевидны (проверьте!)		¡2	1	¢		¡4	2	¢
1) 1 ¢ A = A.

2) (¸¹)A = ¸(¹A).

3) (¸ + ¹)A = ¸A + ¹A.

4) ¸(A + B) = ¸A + ¸B.

До сих пор все операции на матрицах были похожи на соответствующие операции для чисел. Операция умножения матриц существенно сложнее для понимания, позже мы увидим что она соответствует композиции геометрических преобразований (например, переноса и вращения).

Пусть A 2 Mm;n и B 2 Mn;k такие матрицы, что число столбцов A равно числу строк B.

Определим m£k матрицу C = AB равенством cij = ai1b1j +ai2b2j +¢ ¢ ¢+ainbnj

=

n

l=1 ailblj.

c

мы суммируем произведения элементов

i

матрицы A и

Итак, чтобы получить ij

-ой строки

P

j-го столбца матрицы B (по условию они имеют одинаковую длину).

12

¢ ¡

¢

¡ . ¡

¢

¡

2 ¡1

¢

¡2 7

2 матрица. Имеем

Например, пусть A =

1

0

и B =

. Тогда C = AB также 2

£

¡1 2

0 3

2 ¡1

c

= 1 (

1)+0 3 =

1 Продолжая вычисления, получаем C =

. С другой стороны

BA =

¡

3

¡2

¢

= AB

, поэтому операция умножения матриц не

коммутативна.

3

6

6

¡

¢

¡

Приведем свойства операции умножения.

главной диагонали стоят единицы, а

1) Пусть

I

n обозначает

n

£

n

матрицу у которой на

1 0 0

на остальных местах нули, например I2

1 0

³

0 0 1 ´. Тогда

= ( 0 1 ) и E3 =

0 1 0

Im ¢ A = A ¢ In = A для любой A 2 Mm;n.

2)A(B + C) = AB + AC для любых A 2 Mm;n, B; C 2 Mn;k и (A + B)C = AC + BC.

3)¸(AB) = (¸A)B = A(¸B).

26

4)0 ¢ A = A ¢ 0 = 0 (укажите размеры матриц!)

5)(AB)C = A(BC) (укажите размеры матриц!)

Доказательство. 3) Ясно, что размеры матриц совпадают. Имеем (¸(AB))ij = ¸(AB)ij =

¸ k aikbkj. Аналогично, ((¸A)B)ij =

k(¸A)ikbkj =

k ¸aik ¢ bkj, и эти выражения равны.

Последнее равенство проверяется аналогично.

P

P

P

5) Равенство размеров матриц легко проверяется (сделайте это!). Имеем

((AB)C)ij =

Pk

(AB) c

=

Pk

a b

c =

Pk;l

a b

c

.

Аналогично

ik

kj

¡Pl il

lk¢ kj

il

lk

kj

(A(BC))ij =

Pl ail(BC)lj

= Pl ail¡Pk blk¢ckj = Pk;l ailblkckj.

¤

10.

Лекция 9

L9

Главная диагональ матрицы A состоит из элементов a11; a22; : : : . Например, главную диа-

1 2 3

¢ составляют элементы

a

= 1

a

=

1

гональ матрицы ¡3 ¡1 4

11

d1и::: 220

¡ . Диагональной матрицей

называется квадратная матрица diag(d1; : : : ; dn) =

Ã

0...

.:::.. d...n !

у которой на диагонали сто-

ят элементы d1; : : : ; dn, а на остальных местах нули. Если все di равны, то матрица

diag(d; : : : ; d) называется скалярной.

Квадратная матрица, у которой все элементы ниже главной диагонали равны нулю назы-

вается верхнетреугольной. Это означает, что aij

= 0 для всех i > j. Схематично верхнетре-

d

:::

угольную матрицу обычно изображают в виде Ã 0...1 .:::.. d¤...n !, где ¤ обозначает произвольные

1 2 ¡3

´ верхнетреугольная, а ³

1 2 ¡3

0 2

2

1 0

2

элементы. Например, матрица ³0 0

3

0 0

3 ´ нет.

Множество верхнетреугольных матриц порядка n обозначается UTn (от английского

"upper triangular").

0... ! называются нижнетреугольными (дайте точное

Аналогично, матрицы вида Ãd...1

.:::..

¤

:::

dn

определение!). Например, матрица ( 12 03 ) нижнетреугольная. Множество нижнетреугольных матриц порядка n обозначается LUn (от "lower triangular").

Определим еще одну операцию на матрицах транспонирование. А именно, если A m£n матрица, то ее траспонированной называется n£m матрица At такая, что (At)ij = aji. Итак, матрица At получается из A отражением относительно главной диагонали. Если A не квадратная, то удобно дополнить ее до квадратной "пустыми" элементами, а затем отразить

и убрать пустые элементы. Например, если A = ¡												1	2	3	¢, то следующая диаграмма
												3 ¡1 4
					03			1	41		02			1		:1
					B	1	2		3			1		3		:
						:	:		:C	¡!	B3			4		:C
					@		¡		A		@			¡		A
t			1	3
	=	³	3	¡4	´.
дает A
			2	1

27

Свойства транспонирования.

1) (At)t = A.

2) (A + B)t = At + Bt. 3) (¸A)t = ¸At.

4) (AB)t = BtAt.

Доказательство. 3) Предположим, что A m £ n, а B n £ k матрицы, следовательно матрица AB имеет размер m £ k, а тогда (AB)t k £ m.

Тогда Bt имеет размер k £ n, At n £ m, следовательно BtAt матрица того же размера k £ m. Сравним элементы этих матриц. Имеем

X
((AB)t)ij = (AB)ji =	ajkbki :
k
Аналогично	X
X
(BtAt)ij = (Bt)ik(At)kj =	bkiajk :
k	k
Поскольку коэффициенты берутся из поля (R или C), то мы получаем нужное равенство.
	¤

Замечание 90. Если A квадратная матрица, то A 2 UTn если и только если At 2 LTn.

Определение 91. Матрица A называется симметричной, если A = At, то есть она симметрична относительно главной диагонали.

Заметим, что симметричная матрица всегда квадратная (почему?) и aij = aji для всех

1 2	³	1 3	2	´ нет.
		3 1	1
i; j. Например, матрица ( 2 1 ) симметрична, а		2 1	¡1

10.1. Элементарные преобразования матриц. Рассмотрим следующие действия над матрицами, которые называются элементарными преобразованиями строк.

1)Перестановка i-ой и j-ой строк, при i 6= j, в обозначениях Ri $ Rj.

2)Умножение i-ой строки на ненулевое число ¸, в обозначениях ¸Ri.

3)Прибавление к i-ой строке j-ой строки умноженной на ¸ (здесь i 6= j, но ¸ = 0 допускается), в обозначениях Ri + ¸Rj.

Приведем пример применения этих преобразований:

2	4	1	R R	1	2	3	R 2R	1	2	3		R 2	2	4	6	:
Ã1	2	3!	¡¡¡¡¡1$ !2	Ã2	4	1!	¡¡¡¡¡2¡ !1	Ã0	0	¡	5!	¡¡¡1!¢	Ã0	0	5!
															¡

Мы хотим, используя элементарные преобразования строк, максимально упростить данную матрицу.

Назовем лидером, или опорным элементом данной строки первый ее ненулевой элемент. Если строка нулевая, то она не имеет лидера. В следующем примере лидеры взяты в рамку:

01

B	0		1	0	3	C
	0	0		0	2
@	2	¡1		0	0	A

28

Определение 92. Скажем, что матрица A имеет ступенчатый вид, если выполнены следующие условия:

1)любая нулевая строка стоит после (то есть ниже) любой ненулевой строки;

2)если i < j номера ненулевых строк, то лидер j-ой (нижней) строки стоит строго правее лидера i-ой (верхней) строки.

Например, матрица из только что приведенного примера не имеет ступенчатого вида (какое условие нарушается?). Схематично матрицу ступенчатого вида можно изобразить так:

01

B * ¤ ¤ C

B0 * ¤ C

BC

B0 0 * C @ A

0 0 0

Горизонтальные черточки внутри матрицы выделяют ступеньки высоты 1. Звездочки в рамках отмечают основания ступенек, то есть лидеров соответствующих строк.

row-ech Теорема 93. Любую матрицу элементарными преобразованиями строк можно привести к ступенчатому виду.

Доказательство. Доказательство этой теоремы по сути дает алгоритм такого приведения. Рассмотрим первый столбец матрицы A. Если он нулевой, то забываем о нем и применяем индукцию к оставшейся (меньшей) матрице. Если этот столбец ненулевой, то, переставляя строки (то есть применяя элементарное преобразование 1-го типа), можно считать, что

первый элемент первой строки ненулевой.

Используя этот элемент и элементарные преобразования третьего типа, нетрудно аннулировать все элементы, кроме первого, в первом столбце A, тем самым построив первую ступеньку.

Удалим теперь первую строку и применим индукцию к оставшейся матрице (восполните

недостающие аргументы!)																	¤
								0 2 3		´		к ступенчатому виду:
Применяя этот алгоритм, приведем матрицу ³4 4 2
								1 3 0
0	2	3	R1$R2 0	1	3	0	R3¡4R1 0	1		3		0	R3+4R2 0	1	3	0	1
01	3	01		0	2	31		0		2		31		0	2	3
B4	4	2C	¡¡¡¡¡! B	4	4	2C	¡¡¡¡¡! B	0	¡		8	2C	¡¡¡¡¡! B	0	0	14	C
@		A	@			A	@					A	@				A

Заметим, что элементарные операции над строками матриц обратимы, то есть мы всегда можем вернуться к исходной матрице, выполняя (возможно другие) элементарные операции. Действительно, следующие вычисления доказывают это (объясните, почему!):

1)	Ri$Rj	Ri$Rj
	A ¡¡¡¡! B 1¡¡¡¡! A.
2)	¸Ri	¸¡ Ri
	A ¡¡! B ¡¡¡¡! A.
3)	Ri+¸Rj	Ri¡¸Rj
	A ¡¡¡¡¡! B ¡¡¡¡¡! A.

29

Назовем две матрицы A и B (одного размера) строчно эквивалентными, в обозначениях A »r B, если A может быть превращена в B используя элементарные преобразования строк. По только что доказанному, это определение симметрично (объясните, что это значит!)

Предложение 94. A »r B если и только если A и B могут быть приведены к одному и тому же ступенчатому виду.

Доказательство. (. Пусть C ступенчатая матрица, и стрелки A 99K C, B 99K C обозначают последовательности элементарных преобразований, которые приводят A и B к C. По только что доказанному свойству последнюю стрелку можно обратить: C 99K B. Тогда композиция A 99K C 99K B редуцирует A к B.

). Приведем B к ступенчатому виду: B 99K C. Поскольку A приводится к B (A 99K B), то, комбинируя стрелки A 99K B 99K C, получаем редукцию A к C. ¤

Пусть i 6= j и ¸ число. Элементарной матрицей Eij(¸) называется матрица у которой на главной диагонали стоят единицы, на месте (i; j) стоит ¸, а на всех остальных местах

нули. Например, для матриц третьего порядка E23(¡3) = ³	1 0	0	´.
	0 1	3
	0 0	¡1

Заметим, что применение элементарного преобразования Ri + ¸Rj к матрице A (размера m £ n) эквивалентно умножению этой матрицы слева на m £ m матрицу Eij(¸). В качестве примера рассмотрим 2 £ 2 матрицы:

E12(¸) ¢ A =	Ã0	1!	¢	Ãc d!	= Ã	c	d	! :
	1	¸		a b		a + ¸c	b + ¸d

Действительно, к первой строке прибавилось вторая, умноженная на ¸!

Выполнение элементарных преобразований 1-го и 2-го типов также сводится к умножения слева на некоторые матрицы (найдите их!).

Аналогично элементарные операции можно выполнять и со столбцами матрицы. В этом случае умножать нужно на некоторые матрицы справа. Проведем эксперимент:

A ¢ E12(¸) =	Ãc d!	¢	Ã0	1!	=	Ãc c¸ + d!	:
	a b		1	¸		a a¸ + b

Итак, при умножении матрицы A справа на матрицу Eij(¸) к j-му столбцу добавляется i-ый умноженный на ¸, то есть выполняется преобразование Cj + ¸Ci.

До какой степени можно упростить данную матрицу, используя элементарные преобразования строк (заметим, что мы еще не применяли преобразования 2-го типа)?

10.2. Улучшенный ступенчатый вид. Скажем, что матрица A имеет улучшенный ступенчатый вид (вид Гаусса), если выполнены следующие условия:

1)A имеет ступенчатый вид;

2)любой лидер равен 1;

3)все элементы над любым лидером равны нулю.

30