Матрицы обладают многими . Единичная матрица является нейтральным элементом по отношению к умножению. Умножение на нулевую матрицу дает нулевую матрицу. Умножение матриц ассоциативно. Умножение матриц дистрибутивно относительно сложения. Для п . в общем случае АВ . Произведения матрицы и вектора или двух векторов легко вычисляются, если вспомнить, что вектор — это матрица размером п х . Например, если хну — векторы размера п, то произведение я . , по сути, одно число. Норма вектора х размером п определяется как длина вектора в . Некоторые ненулевые квадратные матрицы не имеют обратных матриц. Матрица, для которой не существует обратной матрицы, называется вырожденной. Если же обратная матрица существует, то она единственная. Если А и В — невырожденные матрицы размером п х п, то . Кроме того, операция обращения коммутативна с операцией транспонирования. Столбцовым рангом ненулевой матрицы А размером тхп называется размер наибольшего множества линейно независимых столбцов А. Аналогично строчным рангом той же матрицы называется размер наибольшего множества линейно независимых строк А. Фундаментальным свойством любой матрицы А является равенство ее строчного и столбцового рангов, так что обычно говорят о просто ранге матрицы. Эквивалентное определение ранга ненулевой матрицы А размером тхп — это наименьшее число г, для которого существуют матрицы В и С размером соответственно тхг и гхп такие, что А . Квадратная матрица размером пхп имеет полный ранг, если ее ранг равен п. Полный ранг квадратная матрица имеет тогда и только тогда, когда она невырождена. Определитель, или детерминант, матрицы А размером пхп можно определить рекурсивно при помощи миноров следующим образом. Определитель квадратной матрицы А обладает следующими свойствами. Кроме того, для любых квадратных матриц А и В . Квадратная матрица А вырождена тогда и только тогда, когда . Умножение матриц Как было сказано выше, если А . Отсюда непосредственно следует простейший алгоритм умножения матриц. Никакие другие действия с матрицами в данной главе выполняться не будут, так что с методической точки зрения использование такого непритязательного класса вполне оправданно. Методические же соображения поясняют и выбор класса . При разработке собственных классов и реализаций алгоритмов на С. Кажется, что улучшить эффективность алгоритма умножения невозможно, но это не так. Здесь не будет приведен полный вывод алгоритма Штрассена. Алгоритм основан на методе декомпозиции. Рассмотрим произведение матриц С . Считая, что пявляется точной степенью . После этого результат умножения матриц получается следующим образом. Постоянный множитель, скрытый во времени работы алгоритма Штрассена, существенно превышает постоянный множитель во времени работы . Для разреженных матриц имеются специализированные более эффективные методы умножения. Алгоритм Штрассена несколько менее численно устойчив, чем простой алгоритм умножения матриц. Построение подматриц на каждом шаге рекурсии приводит к повышенному расходу памяти. Так что такая реализация будет проигрывать в эффективности реализации простого алгоритма перемножения матриц, основанного на определении этой операции. Таким образом, здесь мы ограничимся только изложением самого алгоритма. К этому следует добавить, что имеется теорема, согласно которой умножение матриц и обращение матрицы — задачи одного уровня сложности, так что обращение матрицы требует того же асимптотического времени, что и перемножение матриц. В настоящее время наиболее эффективный алгоритм перемножения матриц Копперсмита. Решение систем линейных уравнений представляет собой фундаментальную задачу, возникающую в различных приложениях. Итак, нам требуется решить систему из п уравнений с п неизвестными, где п — некоторое, обычно достаточно большое число. Идея этого метода заключается в преобразовании системы п линейных уравнений с п неизвестными в эквивалентную ей систему с верхнетреугольной матрицей коэффициентов. Используя матричные обозначения, это действие можно записать как где Ах . Сначала мы вычисляем значение хп из последнего уравнения. Выполняя такие подстановки вычисленных значений переменных в очередные уравнения, мы получим значения всех п переменных — от хп до х,. Это можно сделать при помощи последовательности следующих элементарных операций. Поскольку ни одна из перечисленных операций не изменяет решение системы линейных уравнений, любая система линейных уравнений, полученная из исходной при помощи серии описанных операций, будет иметь то же решение, что и исходная. Начнем наши преобразования. Для начала используем в качестве опорного элемента аи для того, чтобы сделать все коэффициенты при х, в строках ниже первой нулевыми. В частности, заменим второе уравнение разностью между ним и первым уравнением, умноженным на . Выполняя то же для третьей, четвертой и далее строк и умножая первое уравнение соответственно на ам. Затем обнулим все коэффициенты при х. Повторяя эти действия для каждой . Заметим, что можно работать не с двумя матрицами — коэффициентов и свободных членов, а только с матрицей коэффициентов, к которой в качестве . Другими словами, нет необходимости явно использовать имена переменных системы линейных уравнений или знаки . Вот как можно записать псевдокод только что рассмотренного этапа преобразования алгоритма решения систем линейных уравнений методом исключения Гаусса. В этом случае мы должны воспользоваться первой из описанных ранее операций и обменять . Поскольку мы все равно должны быть готовы к возможному обмену строк, следует учесть еще одну потенциальную сложность — возможность того, что величина аи будет столь мала . Чтобы избежать этой проблемы, можно всегда выбирать строку с наибольшим абсолютным значением коэффициента в г. Такая модификация алгоритма, называющаяся выбором ведущего элемента, гарантирует, что значение масштабирующего множителя никогда не превысит . Измененный с учетом рассмотренных замечаний псевдокод приведен ниже.