!!§!! Вспомогательная страница к разделу ((:algebra2 МАТРИЦА)) ---- В настоящем разделе $ \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_{} $ обозначается[[Я также буду использовать и обозначение $ A\times B_{} $, хотя и реже...]] $ 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_{} $. В схематичном виде: {{ :mat_mul.gif?600 |}} Порядок ("размеры") матрицы $ C_{} $ определяется следующим образом: высота берется от первого сомножителя, а ширина --- от второго. При этом произведение $ B \cdot A_{} $ может и не быть определено! !!Т!! **Теорема 1.** //Умножение матрицы// $ A $ //на матрицу// $ B $ //сводится к умножению матрицы// $ A $ //на столбцы матрицы// $ B $: //если// $$ B=\left[ B_{[1]} \mid B_{[2]} \mid \dots \mid B_{[k]} \right]\ , $$ //то//[[произведение распараллеливается]] $$ AB= \left[ AB_{[1]} \mid AB_{[2]} \mid \dots \mid AB_{[k]} \right] \, . $$ //Здесь// $ \mid $ //означает ((:algebra2#konkatenacija конкатенацию))//. Аналогичным образом можно было бы свести вычисление произведения $ 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 $ на матрицу произвольного порядка вполне определено. В то же время, если ту же квадратичную форму представить в ((:2form#матричная_форма_записи_квадратичной_формы матричном виде)), то результат действий $$ (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] $. Это умножение, очевидно, обладает свойством коммутативности. См. также и ☞ ((algebra2:kronecker_prod КРОНЕКЕРОВО ПРОИЗВЕДЕНИЕ)). -- Для ответа на поставленный вопрос следует обратиться к изначальной области применения матричного формализма: матрицы служат удобным средством исследования ((:algebra2:linearsystems#системы_линейных_уравнений систем линейных уравнений)). !!П!! **Пример:** 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) , $$ и переформулировать задачу поиска решений этой системы в виде: найти такую ((:linear_space#линейная_зависимость_базис_координаты линейную комбинацию)) столбцов $$ \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. $$ мы можем ее решить, последовательно выражая переменные (см. ☞ ((algebra2:linearsystems#исключение_переменных_метод_гаусса метод Гаусса))): $$ 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 \} \, . $$ ==Задачи==