Инструменты сайта


§

Вспомогательная страница к разделу МАТРИЦА


В настоящем разделе $ \mathbb A^{m \times n} $ обозначает множество матриц порядка $ m \times n $ с элементами из какого-то из множеств $ \mathbb Q, \mathbb R $ или $ \mathbb C $.

Умножение матриц

Для матрицы-строки $ U=(u_{1},\dots,u_n) $ и матрицы-столбца $ V=\left(\begin{array}{c} v_{1}\\ \vdots\\ v_n \end{array}\right) $ определим произведение $ U\cdot V_{} $ как число

$$ U\cdot V= u_1v_1+\dots+u_nv_n . $$

Для произвольных матриц $ A_{} $ и $ B_{} $ произведение матрицы $ A_{} $ на матрицу $ B_{} $ определяется тогда и только тогда, когда их порядки связаны ограничением:

количество столбцов матрицы $ A $ = количество строк матрицы $ B_{} $

т.е. если матрица $ A_{} $ имеет порядок $ m\times n_{} $, то матрица $ B_{} $ может иметь порядок $ n\times k_{} $ при $ \forall k\in{\mathbb N}_{} $. В этом случае произведение матрицы $ A_{} $ на матрицу $ B_{} $ обозначается1) $ A\cdot B_{} $ и представляет собой матрицу $ C_{} $ порядка $ m\times k_{} $: $$ \begin{array}{ccccc} C&=&A&\cdot&B ,\\ {m\times k}&&{m\times n}&&{n\times k} \end{array} $$ элементы которой вычисляются по следующему правилу $$ C=[c_{j\ell}]_{_{j=1,\dots,m\atop \ell=1,\dots,k }},\quad c_{j\ell}= A^{[j]}B_{[\ell]}=a_{j1}b_{1\ell}+a_{j2}b_{2\ell}+\dots+a_{jn}b_{n\ell} . $$ Таким образом, элемент, стоящий в $ j_{} $-й строке и $ \ell_{} $-м столбце матрицы $ C_{} $, равен произведению $ j_{} $-й строки матрицы $ A_{} $ на $ \ell_{} $-й столбец матрицы $ B_{} $.

В схематичном виде:

Порядок («размеры») матрицы $ C_{} $ определяется следующим образом: высота берется от первого сомножителя, а ширина — от второго.

При этом произведение $ B \cdot A_{} $ может и не быть определено!
Т

Теорема 1. Умножение матрицы $ A $ на матрицу $ B $ сводится к умножению матрицы $ A $ на столбцы матрицы $ B $: если

$$ B=\left[ B_{[1]} \mid B_{[2]} \mid \dots \mid B_{[k]} \right]\ , $$ то2) $$ AB= \left[ AB_{[1]} \mid AB_{[2]} \mid \dots \mid AB_{[k]} \right] \, . $$ Здесь $ \mid $ означает конкатенацию.

Аналогичным образом можно было бы свести вычисление произведения $ AB $ к умножению строк матрицы $ A $ на матрицу $ B $.
П

Пример.

$$ A=\left(\begin{array}{rr} 1&2\\ -1&0\\ 3&7 \end{array}\right),B=\left(\begin{array}{rrrr} \mathbf i&0&0&-1\\ 4&2&0&-2 \end{array}\right) \Longrightarrow A\cdot B=\left(\begin{array}{rrrr} 8+ \mathbf i&4&0&-5\\ -\mathbf i&0&0&1\\ 28+3\mathbf i&14&0&-17 \end{array}\right) $$

П

Пример.

$$ A=\left( \begin{array}{rrr} 3&-1&-1\\ 2&0&1\\ 1&1&1 \end{array}\right),B=\left(\begin{array}{rr} 2&1\\ -1&0\\ 0&1 \end{array}\right)\Longrightarrow A\cdot B= \left(\begin{array}{rr} 7&2\\ 4&3\\ 1&2 \end{array}\right) $$

П

Пример.

$$ A=\left(\begin{array}{c} 1\\ 0\\ 1\\ 1 \end{array}\right), B=(1,2,-1,-2) \Longrightarrow A\cdot B= \left(\begin{array}{rrrr} 1&2&-1&-2\\ 0&0&0&0\\ 1&2&-1&-2\\ 1&2&-1&-2 \end{array}\right) $$ $$ B \cdot A = ( - 2 ) \ . $$

Последний пример показывает некоторую неоднозначность определения произведения матриц. Что явилось результатом умножения: матрица порядка $ 1 \times 1_{} $ или ее (единственный) элемент? Обычно в математических рассуждениях эта неоднозначность не влияет на результаты и потому не принимается во внимание. Хотя с формальной точки зрения, можно, например, обсуждать следующее противоречие. Такое действие как умножение квадратичной формы $ f(x,y)=2\,x^2-4\,xy+3\,y^2 $ на матрицу произвольного порядка вполне определено. В то же время, если ту же квадратичную форму представить в матричном виде, то результат действий $$ (x,y) \cdot \left(\begin{array}{rr} 2 & -2 \\ -2 & 3 \end{array}\right) \left( \begin{array}{c} x \\ y \end{array} \right) $$ представится матрицей порядка $ 1\times 1 $. Последняя — в соответствии с формальным правилом умножения матриц — не может быть умножена ни на какую матрицу порядка $ m\times n_{} $ при $ m_{}>1 $. Кроме того, приходится учитывать неоднозначность определения операции умножения строки на столбец при программировании алгоритмов: типы объектов — число и матрица (массив) — все-таки различны.
Операция умножения матриц некоммутативна : даже если определены оба произведения $ A\cdot B_{} $ и $ B \cdot A_{} $, то, как правило, $ A\cdot B \ne B \cdot A $.

Ассоциативность

Т

Теорема 2. Операция умножения матриц подчиняется ассоциативному закону: $$ (A\cdot B) \cdot D = A\cdot (B \cdot D) $$ если хотя бы в одной части равенства произведение определено.

Доказательство. Пусть $ A \in \mathbb A^{m \times n}, B \in \mathbb A^{n \times k}, D \in \mathbb A^{k \times h} $. Пусть $$ A= \left( \begin{array}{lllll} a_{11} & a_{12} & a_{13}& \dots & a_{1n} \\ a_{21} & a_{22} & a_{23}& \dots & a_{2n} \\ \dots & & & & \dots \\ a_{m1} & a_{m2} & a_{m3}& \dots & a_{mn} \end{array} \right) \ , \quad B= \left(\begin{array}{llll} b_{11} & b_{12} & \dots & b_{1k} \\ b_{21} & b_{22} & \dots & b_{2k} \\ \dots & & & \dots \\ b_{m1} & b_{m2} & \dots & b_{mk} \end{array}\right) \, . $$ Докажем сначала справедливость равенства для частного случая матрицы $ D $: пусть она состоит только из одного столбца, т.е. $ h=1 $. Обозначим этот столбец $$ X= \left(\begin{array}{l} x_1 \\ x_2 \\ \vdots \\ x_n \end{array}\right) $$ Сделаем в векторе $$ AX=\left( \begin{array}{c} a_{11}x_1 +a_{12}x_2+ \ldots+a_{1n}x_n \\ a_{21}x_1 +a_{22}x_2+ \ldots +a_{2n}x_n \\ \dots \\ a_{m1}x_1 +a_{m2}x_2+ \ldots+a_{mn}x_n \end{array} \right) $$ замену переменных (подстановку) по формулам $$ X=BY \quad \iff \quad \left\{\begin{array}{l} x_1=b_{11}y_1+b_{12}y_2+\dots+b_{1k}y_k\ ,\\ \vdots\\ x_n=b_{n1}y_1+b_{n2}y_2+\dots+b_{nk}y_k\ . \end{array}\right. $$ Здесь $$ Y= \left(\begin{array}{l} y_1 \\ y_2 \\ \vdots \\ y_k \end{array}\right) $$ — вектор новых переменных.

Подстановка в $ a_{j1}x_1+a_{j2}x_2+\dots+a_{jn}x_n $ приводит к следующему: $$\begin{array}{rlc} a_{j1}x_1+a_{j2}x_2+\dots+a_{jn}x_n= &a_{j1}(b_{11}y_1+b_{12}y_2+\dots+b_{1k}y_k)&+\\ +&a_{j2}(b_{21}y_1+b_{22}y_2+\dots+b_{2k}y_k)&+\\ +& \qquad \qquad \dots & +\\ +&a_{jn}(b_{n1}y_1+b_{n2}y_2+\dots+b_{nk}y_k)&=\\ =&(a_{j1}b_{11}+a_{j2}b_{21}+\dots+a_{jn}b_{n1})y_1&+\\ +&(a_{j1}b_{12}+a_{j2}b_{22}+\dots+a_{jn}b_{n2})y_2&+\\ +& \qquad \qquad \dots&+\\ +&(a_{j1}b_{1k}+a_{j2}b_{2k}+\dots+a_{jn}b_{nk})y_k&=\\ =c_{j1}y_1+c_{j2}y_2+\dots+c_{jk}y_k ,& & \end{array} $$ где коэффициенты определяются формулой $$ c_{j\ell}=a_{j1}b_{1\ell}+a_{j2}b_{2\ell}+\dots+a_{jn}b_{n\ell} \, . $$ Однако, этой же формулой определяются элементы матрицы $$ C = A \cdot B \, . $$ Таким образом, справедливость равенства $$ A(BY)=(AB)Y $$ доказана для любого столбца $ Y \in \mathbb A^{k\times 1} $.

Распространить же его на матрицу $ D $ с произвольным количеством столбцов позволяет теорема $1$. Умножение матрицы $ C $ на матрицу $ D $ сводится к умножению матрицы $ C $ на каждый из столбцов матрицы $ D $: $$C\cdot [D_{[1]} \mid \dots \mid D_{[h]} ] =\left[C\cdot D_{[1]} \mid \dots \mid C \cdot D_{[h]} \right] = $$ На основании уже доказанной формулы имеем право записать $$(AB)D_{[1]}=A\left(BD_{[1]}\right),\dots, (AB)D_{[h]}=A\left(BD_{[h]}\right) \ . $$ Следовательно, наше произведение $$ = \left[A \left(BD_{[1]} \right) \mid \dots \mid A\left(BD_{[h]} \right) \right] = $$ Снова используем правило умножения матрицы на матрицу по теореме $ 1 $ (только теперь идем в обратном направлении — от столбцов переходим к матрице): $$ =A \left[BD_{[1]} \mid \dots \mid BD_{[h]} \right] = $$ и завершит доказательство еще одно применение того же правила: $$ =A(BD) \ . $$

Обоснование правила умножения матриц

Что послужило причиной введения такой операции умножения?

В приложениях используются и другие определения произведения двух матриц. Например, для матриц $ A_{} $ и $ B_{} $ одинакового порядка их адамаровым произведением называется матрица того же порядка, состоящая из поэлементных произведений: $ C=\left[ a_{jk} b_{jk} \right] $. Это умножение, очевидно, обладает свойством коммутативности. См. также и КРОНЕКЕРОВО ПРОИЗВЕДЕНИЕ.

– Для ответа на поставленный вопрос следует обратиться к изначальной области применения матричного формализма: матрицы служат удобным средством исследования систем линейных уравнений.

П

Пример: Cистему уравнений от четырех переменных

$$ \left\{ \begin{array}{rrrrcr} 2x_1&-3x_2&+x_3 &-5x_4 &=& 1 \\ -x_1& &+4x_3 &-3x_4 &=& -2 \\ & x_2 &-3x_3 &+7x_4 &=& 5 \end{array} \right. $$ можно переписать в виде: $$ \left( \begin{array}{r} 2 \\ -1 \\ 0 \end{array} \right)x_1 + \left( \begin{array}{r} -3 \\ 0 \\ 1 \end{array} \right)x_2+ \left( \begin{array}{r} 1 \\ 4 \\ -3 \end{array} \right)x_3+ \left( \begin{array}{r} -5 \\ -3 \\ 7 \end{array} \right)x_4= \left( \begin{array}{r} 1 \\ -2 \\ 5 \end{array} \right) , $$ и переформулировать задачу поиска решений этой системы в виде: найти такую линейную комбинацию столбцов $$ \left( \begin{array}{r} 2 \\ -1 \\ 0 \end{array} \right), \left( \begin{array}{r} -3 \\ 0 \\ 1 \end{array} \right), \left( \begin{array}{r} 1 \\ 4 \\ -3 \end{array} \right), \left( \begin{array}{r} -5 \\ -3 \\ 7 \end{array} \right) \ , $$ которая будет совпадать со столбцом $$ \left( \begin{array}{r} 1 \\ -2 \\ 5 \end{array} \right) \ . $$ Таким образом, мы задействовали операцию сложения матриц. С другой стороны, ту же самую систему уравнений можно переписать с помощью операции умножения матриц. Так, c использованием правила умножения строки на столбец, первое из уравнений системы переписывается в виде: $$ (2,-3,1,-5) \cdot \left( \begin{array}{r} x_1 \\ x_2 \\ x_3 \\ x_4 \end{array} \right) = 1 \ ; $$ обобщая этот результат, получаем матричную форму записи системы уравнений: $$ \left( \begin{array}{rrrr} 2&-3&1 &-5 \\ -1&0 &4 &-3 \\ 0& 1 &-3 &7 \end{array} \right) \left( \begin{array}{r} x_1 \\ x_2 \\ x_3 \\ x_4 \end{array} \right)= \left( \begin{array}{r} 1 \\ -2 \\ 5 \end{array} \right) \ . $$ Преимущества такой формы записи по сравнению с обычной, на первый взгляд, не очевидны. Попробуем, однако, усложнить задачу. Предположим, что неизвестные $ x_1,x_2,x_3,x_4 $, в свою очередь, зависят от других неизвестных — $ y_1,y_2,y_3 $, и эта зависимость линейная: $$ \begin{array}{rrrrr} x_1&=&3y_1 &-2y_2&+3y_3, \\ x_2&=&-y_1 &+5y_2&-7y_3, \\ x_3&=&y_1 &-y_2&+y_3, \\ x_4&=& &2y_2&-2y_3. \end{array} $$ Задачей ставится нахождение значений именно неизвестных $ y_1,y_2,y_3 $. Задачу в такой постановке можно решать последовательно: сначала выразить $ x_1,x_2,x_3,x_4 $ из системы уравнений (отметим, что приведенная система имеет бесконечное множество решений), а потом подставить каждый из получившихся наборов значений $ x_1,x_2,x_3,x_4 $ в уравнения, связывающую их с $ y_1,y_2,y_3 $. И попытаться решить получившиеся системы линейных уравнений относительно новых переменных (а вот эти новые системы, в большинстве своем, решений иметь не будут).

Ту же задачу можно решать и напрямую: в исходную систему уравнений относительно $ x_1,x_2,x_3,x_4 $ подставить выражения этих переменных через $ y_1,y_2,y_3 $ и решать уже получившуюся систему — которая, очевидно, также будет линейной. Осталось только выяснить по какому правилу образуются коэффициенты этой новой системы. При подстановке в первое уравнение системы $$ 2x_1-3x_2+x_3 -5x_4 = 1 $$ выражений для $ x_1,x_2,x_3,x_4 $ получаем: $$ 2(3y_1 -2y_2+3y_3)-3(-y_1 +5y_2-7y_3)+(y_1 -y_2+y_3) -5(2y_2-2y_3) = 1 \ . $$ Понаблюдаем каким образом генерируются коэффициенты при новых переменных: $$ \begin{array}{llllcl} (2\cdot 3 &+ (-3)\cdot (-1)& + 1 \cdot 1 & + (-5) \cdot 0)y_1 &+ \\ (2\cdot (-2)& + (-3)\cdot 5 & + 1 \cdot (-1)& + (-5) \cdot 2)y_2 &+ \\ (2\cdot 3 &+ (-3)\cdot (-7) &+ 1 \cdot 1 &+ (-5) \cdot (-2))y_3 &=1. \end{array} $$ Эти коэффициенты могут быть получены как результат перемножения матриц. Если переписать замену переменных в матричном виде: $$ \left( \begin{array}{r} x_1 \\ x_2 \\ x_3 \\ x_4 \end{array} \right)=\left( \begin{array}{rrr} 3&-2 &3 \\ -1& 5 &-7 \\ 1 &-1 &1 \\ 0 & 2 & -2 \end{array} \right) \left( \begin{array}{r} y_1 \\ y_2 \\ y_3 \end{array} \right) \ , $$ то умножение $$ (2,-3,1, -5) \left( \begin{array}{rrr} 3&-2 &3 \\ -1& 5 &-7 \\ 1 &-1 &1 \\ 0 & 2 & -2 \end{array} \right) \left( \begin{array}{r} y_1 \\ y_2 \\ y_3 \end{array} \right) $$ даст ту же левую часть уравнения относительно $ y_1,y_2,y_3 $. А результат замены переменных во всей системе может быть записан в матричном виде. Обозначим матрицу системы уравнений $$ A=\left( \begin{array}{rrrr} 2&-3&1 &-5 \\ -1&0 &4 &-3 \\ 0& 1 &-3 &7 \end{array} \right) $$ столбец правых частей системы: $$ {\mathcal H}= \left( \begin{array}{r} 1 \\ -2 \\ 5 \end{array} \right)\ , $$ и матрицу замены переменных $$ B=\left( \begin{array}{rrr} 3&-2 &3 \\ -1& 5 &-7 \\ 1 &-1 &1 \\ 0 & 2 & -2 \end{array} \right) \ . $$ Имеем: $$ A \cdot X={\mathcal H},\ X=B \cdot Y $$ и замена переменных в системе уравнений производится так, как если бы это были обычные числовые равенства: $$ A \cdot B \cdot Y ={\mathcal H} \ \iff \ \left( \begin{array}{rrrr} 2&-3&1 &-5 \\ -1&0 &4 &-3 \\ 0& 1 &-3 &7 \end{array} \right) \left( \begin{array}{rrr} 3&-2 &3 \\ -1& 5 &-7 \\ 1 &-1 &1 \\ 0 & 2 & -2 \end{array} \right) \left( \begin{array}{r} y_1 \\ y_2 \\ y_3 \end{array} \right) = \left( \begin{array}{r} 1 \\ -2 \\ 5 \end{array} \right) $$ $$ \left( \begin{array}{rrr} 10&-30 &38 \\ 1& -8 &7 \\ -4 &22 &-24 \end{array} \right)\left( \begin{array}{r} y_1 \\ y_2 \\ y_3 \end{array} \right) = \left( \begin{array}{r} 1 \\ -2 \\ 5 \end{array} \right) \ . $$ Переписав теперь это уравнение в привычном виде системы уравнений: $$ \left\{ \begin{array}{rrrr} 10y_1 &-30y_2&+38y_3 & = 1 \\ y_1 &-8y_2&+7y_3 &=-2 \\ -4y_1 &+22y_2&-24y_3 & =5. \end{array} \right. $$ мы можем ее решить, последовательно выражая переменные (см. метод Гаусса): $$ y_1=23/10,\ y_2=1/10,\ y_3=-1/2 \ . $$

Вывод. Произведение матриц вводится именно так, чтобы обеспечить операцию линейной замены переменных в системе линейных уравнений. Некоторые из свойств этой операции совпадают со свойствами обычного произведения чисел — и эта аналогия упрощает формализацию ряда алгоритмов. Однако, эта аналогия не распространяется на все свойства числовых операций — из-за отсутствия хотя бы той же коммутативности умножения матриц.

?

Выполнение равенства $ A \cdot B = 0 $ для чисел $ A $ и $ B $ влечет за собой обязательное выполнение хотя бы одного из равенств $ A = 0 $ или $ B = 0 $. Справедливо ли аналогичное утверждение для матриц?

?

Какую матрицу надо умножить на матрицу $ A_{} $, чтобы результатом стала матрица $ c\,A $, где $ c_{} $ — произвольное фиксированное число?

Алгоритмы быстрого умножения матриц

Коммутирующие матрицы

Говорят, что квадратные матрицы $ A $ и $ B $ коммутируют (или перестановочны), если $ AB=BA $.

Т

Теорема. Степени квадратной матрицы $ A $ коммутируют. Именно, справедливы равенства:

$$ A^k \cdot A^{\ell}=A^{\ell} \cdot A^k = A^{k+\ell} \quad npu \quad \forall \quad \{k,\ell\} \subset \{0,1,2,\dots \} \, . $$

?

Доказать, что если матрицы $ A $ и $ B $ коммутируют, то и произвольные степени этих матриц тоже коммутируют:

$$ AB = BA \ \Rightarrow \ A^k B^{\ell}=B^{\ell} A^k \quad npu \quad \forall \quad \{k,\ell\} \subset \{0,1,2,\dots \} \, . $$

Задачи

1)
Я также буду использовать и обозначение $ A\times B_{} $, хотя и реже…
2)
произведение распараллеливается
algebra2/assoc.txt · Последние изменения: 2021/11/03 16:58 — au