Засучиваем рукава и начинаем разбираться с матрицами
Делиться
Это вторая глава в книге по линейной алгебре, которая находится в процессе написания. Содержание на данный момент:
- Глава 1: Основы
- Глава 2: Измерение карты (текущее)
Оставайтесь с нами для будущих глав.
Линейная алгебра — инструмент многих измерений. Неважно, что вы делаете, как только вы масштабируетесь до ( n ) измерений, линейная алгебра выходит на сцену.
В предыдущей главе мы описали абстрактные линейные отображения. В этой мы засучим рукава и начнем работать с матрицами. Теперь начнут изучаться практические соображения, такие как численная устойчивость, эффективные алгоритмы и т. д.
Примечание: все изображения в этой статье, если не указано иное, принадлежат автору.
I) Как количественно оценить линейную карту
Определители являются одним из древнейших понятий в линейной алгебре. Корни предмета лежат в решении систем линейных уравнений. И определители «определяли», есть ли вообще решение, которое стоит искать. Но в большинстве случаев, когда у системы есть решение, оно предоставляет дополнительную полезную информацию. В современной структуре линейных отображений определители предоставляют единую квантификацию линейных отображений.
В предыдущей главе мы обсудили концепцию векторных пространств (по сути, n-мерных наборов чисел — и, в более общем смысле, наборов полей) и линейных отображений, которые работают с двумя из этих векторных пространств, перенося объекты из одного в другое.
В качестве примера таких видов карт, одно векторное пространство может быть поверхностью планеты, на которой вы сидите, а другое может быть поверхностью стола, за которым вы можете сидеть. Буквальные карты мира также являются картами в этом смысле, поскольку они «отображают» каждую точку на поверхности Земли в точку на бумаге или поверхности стола, хотя они не являются линейными картами, поскольку они не сохраняют относительные площади (например, Гренландия кажется намного больше, чем она есть на самом деле в некоторых проекциях).
Как только мы выбираем основу для векторного пространства (набор из n «независимых» векторов в пространстве; в общем случае выбор может быть бесконечным), всем линейным отображениям в этом векторном пространстве присваиваются уникальные матрицы.
На данный момент давайте ограничим наше внимание картами, которые переводят векторы из 𝑛-мерного пространства обратно в 𝑛-мерное пространство (позже мы обобщим). Матрицы, соответствующие этим линейным картам, — это 𝑛×𝑛 (см. раздел III главы 1). Может быть полезно «количественно оценить» такую линейную карту, выразить ее влияние на векторное пространство ℝⁿ одним числом. Тип карты, с которой мы имеем дело, фактически берет векторы из ℝⁿ и «искажает» их в некоторые другие векторы в том же пространстве. Как исходный вектор 𝑣, так и вектор 𝑢, в который карта его преобразовала, имеют некоторую длину (скажем, |𝑣| и |𝑢|). Мы можем подумать о том, насколько длина вектора изменяется картой, |𝑢|∕|𝑣|. Может быть, это может количественно оценить влияние карты? Насколько он «растягивает» векторы?
Этот подход имеет фатальный недостаток. Соотношение зависит не только от линейной карты, но и от вектора 𝑣, на который она действует. Поэтому это не строго свойство самой линейной карты.
Что если мы возьмем два вектора, 𝑣₁ и 𝑣₂, которые преобразуются линейным отображением в векторы 𝑢₁ и 𝑢₂. Так же как мерой одного вектора 𝑣 была его длина, мерой двух векторов является площадь параллелограмма, заключенного между ними.
Так же, как мы рассматривали величину, на которую изменилась длина 𝑣, теперь мы можем говорить о величине, на которую изменится площадь между 𝑣₁ и 𝑣₂, когда они пройдут через линейную карту и станут 𝑢₁, 𝑢₂. И увы, это снова зависит не только от линейной карты, но и от выбранных векторов.
Далее мы можем перейти к трем векторам и рассмотреть изменение объема параллелепипеда между ними и столкнуться с той же проблемой, когда исходные векторы имеют решающее значение.
Но теперь рассмотрим n-мерную область в исходном векторном пространстве. Эта область будет иметь некоторую «n-мерную меру». Чтобы понять это, двумерная мера — это площадь (измеряется в квадратных километрах). Трехмерная мера — это объем, используемый для измерения воды (в литрах). Четырехмерная мера не имеет аналога в привычном нам физическом мире, но она столь же математически обоснована, мера объема четырехмерного пространства, заключенного в параллелепипеде, образованном четырьмя 4-мерными векторами и так далее.
𝑛 исходных векторов (𝑣₁, 𝑣₂, …, 𝑣ₙ) образуют параллелепипед, который преобразуется линейной картой в 𝑛 новых векторов, 𝑢₁, 𝑢₂, …, 𝑢ₙ, которые образуют свой собственный параллелепипед. Затем мы можем спросить о 𝑛-мерной мере новой области по отношению к исходной. И это отношение, как оказывается, действительно является функцией только линейной карты. Независимо от того, как выглядела исходная область, где она была размещена и так далее, отношение ее меры после того, как на нее подействовала линейная карта, к ее мере до этого будет тем же самым — функцией исключительно линейной карты. Это отношение 𝑛-мерных мер (после к до) и есть то, что мы искали: исключительное свойство линейной карты, которое количественно определяет ее эффект одним числом.
Это отношение, на которое мера любого 𝑛-мерного участка пространства изменяется линейным отображением, является хорошим способом количественно оценить эффект, который оно оказывает на пространство, на которое оно действует. Оно называется определителем линейного отображения (причина такого названия станет ясна в разделе V).
На данный момент мы просто констатировали тот факт, что величина, на которую линейное отображение из ℝⁿ в ℝⁿ «растягивает» любой участок 𝑛-мерного пространства, зависит только от отображения, не предлагая доказательств, поскольку целью здесь была мотивация. Мы рассмотрим доказательство позже (раздел VI), как только вооружимся каким-нибудь оружием.
II) Вычисление определителей
Теперь, как нам найти этот определитель, если задано линейное отображение из векторного пространства ℝⁿ обратно в ℝⁿ? Мы можем взять любые 𝑛 векторов, найти меру параллелепипеда между ними и меру нового параллелепипеда после того, как линейное отображение подействовало на все из них. Наконец, разделим последнее на первое.
Нам нужно сделать эти шаги более конкретными. Для начала давайте начнем играть в этом ℝⁿ векторном пространстве.
Вектор ℝⁿ — это просто набор 𝑛 действительных чисел. Простейший вектор — это просто 𝑛 нулей — [0, 0, …, 0]. Это нулевой вектор. Если мы умножим на него скаляр, то просто получим нулевой вектор. Неинтересно. Для следующего простейшего вектора мы можем заменить первый 0 на 1. Это приводит к вектору: 𝑒₁ = [1, 0, 0, …, 0]. Теперь, умножая на скаляр, 𝑐 дает нам другой вектор.
$$c.[1, 0, 0,.., 0] = [c, 0, 0, …, 0]$$
Мы можем «охватить» бесконечное число векторов с помощью 𝑒₁ в зависимости от выбранного нами скаляра 𝑐.
Если 𝑒₁ — это вектор, в котором только первый элемент равен 1, а остальные равны 0, то чему равен 𝑒₂? Второй элемент равен 1, а остальные равны 0, кажется логичным выбором.
$$e_2 = [0,1,0,0,точки 0]$$
Доводя это до логического завершения, мы получаем набор из n векторов:
Эти векторы образуют базис векторного пространства ℝⁿ. Что это значит? Любой вектор 𝑣 в ℝⁿ можно выразить как линейную комбинацию этих 𝑛 векторов. Это означает, что для некоторых скаляров 𝑐₁, 𝑐₂, …, 𝑐ₙ:
$$v = c_1.e_1+c_2.e_2+dots +c_n.e_n$$
Все векторы 𝑣 «охвачены» набором векторов 𝑒₁, 𝑒₂, …, 𝑒ₙ.
Этот конкретный набор векторов не является единственным базисом. Любой набор 𝑛 векторов работает. Единственное предостережение заключается в том, что ни один из 𝑛 векторов не должен быть «охвачен» остальными. Другими словами, все 𝑛 векторы должны быть линейно независимыми. Если мы выберем 𝑛 случайных чисел из большинства непрерывных распределений и повторим процесс 𝑛 раз, чтобы создать 𝑛 векторов, вы получите набор линейно независимых векторов со 100% вероятностью («почти наверняка» в терминах вероятности). Просто очень, очень маловероятно, что случайный вектор окажется «охвачен» некоторыми другими 𝑘 < 𝑛 случайными векторами.
Возвращаясь к нашему рецепту в начале этого раздела, чтобы найти определитель линейного отображения, теперь у нас есть базис для выражения наших векторов. Фиксация базиса также означает, что наше линейное отображение может быть выражено в виде матрицы (см. раздел III главы 1). Поскольку это линейное отображение возвращает векторы из ℝⁿ обратно в ℝⁿ, соответствующая матрица равна 𝑛 × 𝑛.
Далее нам понадобилось 𝑛 векторов для формирования нашего параллелепипеда. Почему бы не взять стандартный базис 𝑒₁, 𝑒₂, …, 𝑒ₙ, который мы определили ранее? Мера участка пространства, заключенного между этими векторами, по определению равна 1. Надеюсь, что изображение ниже для ℝ³ прояснит это.
Если собрать эти векторы из стандартного базиса в матрицу (строки или столбцы), то получим единичную матрицу (1 на главной диагонали, 0 везде в остальном):
Когда мы сказали, что можем применить наше линейное преобразование к любому n-мерному участку пространства, мы могли бы также применить его к этому «стандартному» участку.
Но легко показать, что умножение любой матрицы на единичную матрицу дает ту же самую матрицу. Таким образом, результирующие векторы после применения линейной карты являются столбцами матрицы, представляющей саму линейную карту. Таким образом, величина, на которую линейная карта изменила объем «стандартного патча», совпадает с n-мерной мерой параллелепипеда между векторами-столбцами матрицы, представляющей саму карту.
Подводя итог, мы начали с мотивировки детерминанта как отношения, на которое линейная карта изменяет меру n-мерного участка пространства. И теперь мы показали, что это отношение само по себе является n-мерной мерой. В частности, мерой, содержащейся между векторами-столбцами любой матрицы, представляющей линейную карту.
III) Мотивация основных свойств
В предыдущем разделе мы описали, как определитель линейной карты должен быть просто мерой, содержащейся между векторами любого из его матричных представлений. В этом разделе мы используем двумерное пространство (где меры являются площадями), чтобы мотивировать некоторые фундаментальные свойства, которыми должен обладать определитель.
Первое свойство — это мультилинейность. Определитель — это функция, которая берет кучу векторов (собранных в матрицу) и отображает их в один скаляр. Поскольку мы ограничиваемся двумерным пространством, мы рассмотрим два вектора, оба двумерные. Наш определитель (поскольку мы мотивировали его как площадь параллелограмма между векторами) можно выразить как:
$$det = A(v_1, v_2)$$
Как должна вести себя эта функция, если мы добавим вектор к одному из двух векторов? Свойство мультилинейности требует:
$$A(v_1+v_3, v_2) = A(v_1,v_2)+A(v_3,v_2)tag{1}$$
Это видно из движущегося изображения ниже (обратите внимание на добавление новой области).
И эту визуализацию можно также использовать, чтобы увидеть (масштабируя один из векторов вместо добавления к нему другого вектора):
$$A(c.v_1, v_2) = cA(v_1, v_2) tag{2}$$
Это второе свойство имеет важное следствие. Что, если мы подставим отрицательное c в уравнение?
Площадь 𝐴(𝑣₁, 𝑣₂) тогда должна иметь противоположный знак по отношению к 𝐴(𝑐·𝑣₁, 𝑣₂).
Это значит, что нам необходимо ввести понятие отрицательной площади и отрицательного определителя.
Это имеет большой смысл, если мы согласны с концепцией отрицательных длин. Если длины — меры в одномерном пространстве — могут быть положительными или отрицательными, то само собой разумеется, что площади — меры в двумерном пространстве — также должны быть отрицательными. И, следовательно, меры в пространстве любой размерности должны быть такими же.
Вместе уравнения (1) и (2) представляют собой свойство полилинейности.
Другим важным свойством, связанным со знаком определителя, является свойство знакопеременности. Оно требует:
$$A(v_1, v_2) = -A(v_2, v_1)$$
Изменение порядка двух векторов меняет знак определителя (или меры между ними). Если вы знаете о векторном произведении трехмерных векторов, это свойство будет для вас очень естественным. Чтобы мотивировать это, давайте сначала подумаем об одномерном расстоянии между двумя векторами положения, 𝑑(𝑣₁, 𝑣₂). Очевидно, что 𝑑(𝑣₁, 𝑣₂) = −𝑑(𝑣₂, 𝑣₁), поскольку при переходе от 𝑣₂ к 𝑣₁ мы движемся в противоположном направлении по сравнению с переходом от 𝑣₁ к 𝑣₂. Аналогично, если площадь, охватываемая векторами 𝑣₁ и 𝑣₂, положительна, то площадь между 𝑣₂ и 𝑣₁ должна быть отрицательной. Это свойство сохраняется и в 𝑛-мерном пространстве. Если в 𝐴(𝑣₁, 𝑣₂, …, 𝑣ₙ) мы поменяем местами два вектора, это приведет к изменению знака.
Свойство чередования также подразумевает, что если один из векторов является просто скалярным множителем другого, то определитель должен быть равен 0. Это происходит потому, что перестановка двух векторов должна привести к отрицанию определителя:
$$begin{align}A(v_1, v_1) = -A(v_1, v_1)
=> 2 А(v_1, v_1) = 0
=> A(v_1, v_1) = 0end{align}$$
Также имеем по мультилинейности (уравнение 2):
$$A(v_1, c.v_1) = c A(v_1, v_1) = 0$$
Это имеет геометрический смысл, поскольку если два вектора параллельны друг другу, то площадь между ними равна ( 0 ).
Видео [6] охватывает геометрическую мотивацию этих свойств с действительно хорошей визуализацией, а видео [4] довольно хорошо визуализирует переменное свойство.
IV) Переходим к алгебре: вывод формулы Лейбница
В этом разделе мы отходим от геометрической интуиции и подходим к теме определителей с альтернативного пути — путем холодных алгебраических вычислений.
Видите ли, полилинейность и переменные свойства, которые мы обосновали в последнем разделе с помощью геометрии, (что примечательно) достаточны, чтобы дать нам весьма конкретную алгебраическую формулу для определителя, называемую формулой Лейбница.
Эта формула помогает нам увидеть свойства определителя, которые было бы очень и очень трудно наблюдать с помощью геометрического подхода или других алгебраических формул.
Формулу Лейбница можно затем свести к разложению Лапласа, включающему в себя обход строки или столбца и вычисление сомножителей, что многие изучают в средней школе.
Давайте выведем формулу Лейбница. Нам нужна функция, которая принимает 𝑛 векторов-столбцов, 𝛼₁, 𝛼₂, …, 𝛼ₙ матрицы в качестве входных данных и преобразует их в скаляр, 𝑐.
$$c=f(vec{a_1}, vec{a_2}, dots vec{a_n})$$
Мы можем выразить каждый вектор-столбец через стандартный базис пространства.
Теперь мы можем применить свойство мультилинейности. Пока что к первому столбцу, 𝛼₁.
То же самое можно сделать и для второго столбца. Давайте возьмем только первый член из суммы выше и посмотрим на полученные члены.
Обратите внимание, что в первом члене мы получаем вектор 𝑒₁, появляющийся дважды. И по свойству чередования функция 𝑓 для этого члена становится равной 0.
Чтобы появились два 𝑒₁, вторые индексы двух 𝑎 в произведении должны стать равными 1.
Итак, как только мы сделаем это для всех столбцов, термины, которые не станут нулевыми из-за свойства чередования, будут теми, где вторые индексы 𝑎 не имеют повторений — то есть все различные числа от 1 до 𝑛. Другими словами, мы ищем перестановки от 1 до 𝑛, которые появятся во вторых индексах 𝑎.
Что насчет первых индексов 𝑎? Это просто числа от 1 до 𝑛 по порядку, так как мы сначала вытаскиваем 𝑎₁ₓ, затем 𝑎₂ₓ и так далее. В более компактной алгебраической записи,
В выражении справа площади 𝑓(𝑒_{𝑗₁}, 𝑒_{𝑗₂}, …, 𝑒_{𝑗ₙ}) могут быть равны +1, −1 или 0, поскольку 𝑒ⱼ являются единичными векторами, ортогональными друг другу. Мы уже установили, что любой член, который имеет какие-либо повторяющиеся 𝑒ⱼ, станет 0, оставляя нам только перестановки (без повторений). Среди этих перестановок мы иногда будем получать +1, а иногда −1.
Понятие перестановок несет с собой знаки. Знаки площадей эквивалентны знакам перестановок. Если обозначить через 𝑆ₙ множество всех перестановок [1, 2, …, 𝑛], то получим формулу Лейбница для определителя:
$$det([vec{a_1}, vec{a_2}, dots vec{a_n}]) = |A| = sumlimits_{sigma in S_n} sgn(sigma) prod limits_{i=1}^n a_{i,sigma(i)} tag{3}$$
Эта формула также подробно описана в посте mathexchange, [3]. И чтобы сделать вещи конкретными, вот простой код Python, который ее реализует (вместе с тестовым случаем).
На самом деле не следует использовать эту формулу для вычисления определителя матрицы (если только это не просто ради развлечения или наглядности). Она работает, но комично неэффективна, учитывая сумму по всем перестановкам (которая равна 𝑛!, что является суперэкспоненциальным числом).
Однако многие теоретические свойства определителя становятся тривиальными для рассмотрения с формулой Лейбница, тогда как их было бы очень трудно расшифровать или доказать, если бы мы исходили из другой ее формы. Например:
- Предложение-1: С помощью этой формулы становится очевидным, что матрица и ее транспонированная матрица имеют один и тот же определитель: |𝐴| = |𝐴ᵀ|. Это простое следствие симметрии формулы.
- Предложение-2: Очень похожий вывод вышеприведенного может быть использован для того, чтобы показать, что для двух матриц 𝐴 и 𝐵, |𝐴𝐵| = |𝐴| ⋅ |𝐵|. См. этот ответ в посте mathexchange, [8]. Это очень удобное свойство, поскольку умножение матриц постоянно встречается в различных разложениях матриц, и рассуждения об определителях этих разложений могут быть мощным инструментом.
- Предложение-3: С помощью формулы Лейбница мы можем легко увидеть, что если матрица является верхней треугольной или нижней треугольной (нижняя треугольная означает, что каждый элемент матрицы над диагональю равен нулю), определитель является просто произведением элементов на диагонали. Это потому, что все перестановки, за исключением одной: (𝑎₁₁ ⋅ 𝑎₂₂ ⋯ 𝑎ₙₙ) (главная диагональ) получают какой-то нулевой член или другой и делают их члены в сумме равными 0.
Третий факт фактически приводит к наиболее эффективному алгоритму вычисления определителя, который используют большинство библиотек линейной алгебры. Матрицу можно эффективно разложить на нижнюю и верхнюю треугольные матрицы (называемую LU-разложением, которое мы рассмотрим в следующей главе). После выполнения этого разложения третий факт используется для умножения диагоналей этих нижних и верхних матриц, чтобы получить их определители. И, наконец, второй факт используется для умножения этих двух определителей и получения определителя исходной матрицы.
Многие люди в старших классах или университетах, впервые столкнувшись с определителем, узнают о разложении Лапласа, которое включает в себя разложение по строке или столбцу, нахождение сомножителей для каждого элемента и суммирование. Это можно вывести из приведенного выше разложения Лейбница, собрав подобные члены. См. этот ответ на пост mathexchange, [2].
V) Историческая мотивация
Определитель был впервые обнаружен в контексте линейных систем уравнений. Допустим, у нас есть 𝑛 уравнений с 𝑛 переменными (𝑥₀, 𝑥₁, …, 𝑥ₙ).
Эту систему можно выразить в матричной форме:
И более компактно:
$$Ax = б$$
Важный вопрос заключается в том, имеет ли система выше единственное решение, x. А определитель — это функция, которая «определяет» это. Единственное решение существует тогда и только тогда, когда определитель A не равен нулю.
Этот исторически вдохновленный подход мотивирует детерминант как многочлен, который возникает, когда мы пытаемся решить линейную систему уравнений, связанную с линейным отображением. Мы рассмотрим это более подробно в главе 5.
Более подробную информацию по этому вопросу можно найти в превосходном ответе в посте mathexchange [8].
VI) Доказательство собственности, которой мы мотивировали
Мы начали эту главу, мотивируя определитель как величину, на которую линейное отображение ℝⁿ → ℝⁿ изменяет меру n-мерного участка пространства. Мы также сказали, что это не работает для 1, 2, … n − 1 мер. Ниже приведено доказательство этого, в котором мы используем некоторые свойства, с которыми мы столкнулись в остальных разделах.
Определим (𝑉, 𝑈) как матрицы 𝑛 × 𝑘, где
$$ V = (v_1, v_2, dots, v_k) $$
По определению,
$$|v_1, v_2, dots, v_k| = sqrt{det(V^t V)} $$ и
$$ |u_1, u_2, dots, u_k| = sqrt{det(U^t U)} = sqrt{det((AV)^t (AV))} = sqrt{det(V^t A^t AV)} $$
Только когда n = k, V является квадратной матрицей, поэтому
$$|v_1, v_2, dots, v_k| = sqrt{det(V^t A^t AV)}$$
$$= sqrt{det(V^t) det(A^t) det(A) det(V)} $$
$$= det(A) sqrt{det(V^t V)} = det(A) |v_1, v_2, dots, v_k| $$
Ссылки
[1] Сообщение Mathexchange: Определитель линейного отображения не зависит от базисов: https://math.stackexchange.com/questions/962382/determinant-of-linear-transformation
[2] Сообщение Mathexchange: Определитель матрицы разложения Лапласа (формула средней школы) https://math.stackexchange.com/a/4225580/155881
[3] Сообщение Mathexchange: Понимание формулы Лейбница для определителей https://math.stackexchange.com/questions/319321/understanding-the-leibniz-formula-for-determinants#:~:text=The%20formula%20says%20that%20det,permutation%20get%20a%20minus%20sign.&text=where%20the%20minus%20signs%20correspond%20to%20the%20odd%20permutations%20from%20above.
[4] Видео на Youtube: 3B1B о детерминантах https://www.youtube.com/watch?v=Ip3X9LOh2dk&t=295s
[5] Связь формулы Лейбница с геометрией https://math.stackexchange.com/questions/593222/leibniz-formula-and-determinants
[6] Видео на Youtube: Формула Лейбница — площадь: https://www.youtube.com/watch?v=9IswLDsEWFk
[7] Сообщение Mathexchange: произведение определителей является определителем произведения https://math.stackexchange.com/questions/60284/how-to-show-that-detab-deta-detb
[8] Исторический контекст для мотивирующего детерминанта: https://math.stackexchange.com/a/4782557/155881
Источник: towardsdatascience.com
