Множитель ( - 1)г+3 det(A[jjj) называется алгебраическим дополнением (cofactor) элемента а.

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

Теорема 31.4 (Свойства определителя)

Определитель квадратной матрицы А обладает следующими свойствами:

•Если в какой-либо строке или каком-либо столбце матрицы стоят одни нули, то её определитель равен 0.

•Если умножить все элементы какой-либо строки матрицы на некоторое число А, то её определитель умножится на А.

•Если прибавить к элементам одной строки соответствующие элементы другой, то определитель не изменится (аналогично для столбцов).

•Определители матриц А и АТ равны.

•При перестановке двух строк или столбцов матрицы её определитель меняет знак.

Если А и В - квадратные матрицы одинакового размера, то det(AB) = det(A) det(B). Теорема 31.5

Квадратная матрица А вырождена тогда и только тогда, когда det(A) = 0.

Положительно определённые матрицы

Матрица А размера га X га называется положительно определённой (positive-definite), если х1Ах > 0 для любого ненулевого вектора х размера га. Например, единичная матрица положительно определена, поскольку для вектора х = (ж1, ж2,... , хп)Т ф 0 мы имеем

ЖГ- Т у. - у.у. J. yi, * - *х * ъ

П 8 = 1

> 0.

Часто положительно определённые матрицы возникают так: Теорема 31.6

Для любой матрицы А полного столбцового ранга матрица АтА положительно определена. Доказательство.

Покажем, что хт(АтА)х > 0 для произвольного ненулевого век-

тора ж. В самом деле,

хТ(АТА)х = (Ах)1 (Ах)(Упражнение 31.1-3)

= \\Ах\\2(31.8)

> О

Выражение Аж2 представляет собой сумму квадратов элементов вектора Ах. Если Аж2 = 0, то все элементы вектора Ах равны О, то есть Ах = 0. Но А - матрица полного столбцового ранга, поэтому по теореме 31.2 отсюда следует, что ж = 0.

Другие свойства положительно определённых матриц указаны разделе 31.6.

Упражнения

31.1-1

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

31.1-2

Пусть Р и А - (га X га) матрицы, причём Р - матрица перестановки. Докажите, что матрица РА получается из А перестановкой строк, а АР - перестановкой столбцов. Докажите, что произведение двух матриц перестановки снова будет матрицей перестановки. Докажите, что если Р - матрица перестановки, то Р обратима, Р~г = Рт, и Рт также является матрицей перестановки.

31.1-3

Докажите, что (АВ)Т = ВтАт. Докажите, что матрица АтА является симметрической для любой матрицы А. 31.1-4

Докажите, что обратная матрица единственна: если матрицы В и С являются обратными к матрице А, то В = С. 31.1-5

Пусть даны (га X га)-матрицы А и В, для которых AB = I. Пусть А получается из А прибавлением j-й строки к г-й. Докажите, что матрица В, обратная к А, может быть получена вычитанием г-го столбца из j-ro в матрице В.

31.1-6

Пусть А - комплексная (га X га)-матрица. Докажите, что все элементы А-1 будут вещественными в том и только том случае, если вещественны все элементы А.

31.1-7

Покажите, что если невырожденная матрица А является симметрической, то матрица А-1 тоже будет симметрической. Покажите, что для всякой матрицы В надлежащего размера матрица

ВАВТ будет симметрической. 31.1-8

Покажите, что для матриц полного столбцового ранга, и только для них, из равенства Ах = 0 следует равенство х = 0. (Указание. Запишите условие линейной зависимости столбцов как матричное уравнение.)

31.1-9

Докажите, что для любых матриц Ап В согласованных размеров

rank(AB) mm(rank(A), гапк(В)),

причём это неравенство обращается в равенство, если одна из матриц квадратная и невырожденная, (Указание. Воспользуйтесь вторым определением ранга.) 31.1-10

Матрицей Вандермонда (Vandermonde matrix) называется матрица

V(x0,

-п-1 J

Л

1

Vi

Xq х\

r-n-l

-п-1

.Г1

„п-1

Докажите, что

det(V(x0, xi,

-п-1

))

П <

O.j.k.n-1

(Указание. Последовательно полагая г = п-1, п - 2,... , 1 прибавьте к [г + 1)-му столбцу г-й, умноженный на ( -жо), а затем примените индукцию.)

31.2. Алгоритм Штрассена умножения матриц

В этом разделе излагается открытый Штрассеном рекурсивный алгоритм, умножающий две га X га матрицы за время 0(ralg7) = О (га2,81). При достаточно больших га он работает быстрее простейшего алгоритма Matrix-Multiply из раздела 26.1.

Общая схема алгоритма.

Алгоритм Штрассена действует по принципу «разделяй и властвуй». Пусть нужно вычислить произведение двух (га X га)-матриц С = АВ. Предположив, что га является точной степенью 2, разделим каждую из матриц А,В и С на 4 блока размера (га/2 X га/2). Перепишем равенство С = АВ следующим образом:

:) -1) 0") • (3l9)