Inverse matrix#

Linear systems#

Система линейных алгебраических уравнений (СЛАУ) из \(m\) уравнений с \(n\) неизвестными имеет вид

\[\begin{split} \begin{align*} a_{11}x_1 &+ a_{12}x_2+ \ldots +a_{1n}x_n = b_1 \\ a_{21}x_1 &+ a_{22}x_2 + \ldots +a_{2n}x_n = b_2 \\ \ldots &\ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \\ a_{m1}x_1 &+ a_{m2}x_2 +\ldots + a_{mn}x_n = b_m \\ \end{align*}, \end{split}\]

где коэффициенты \(a_{ij}\) и числа в правой части \(b_i\) считаются известными, а найти надо неизвестные переменные \(x_j\). Записывать систему линейных уравнений в таком громоздком виде не очень удобно, вместо этого чаще используют матричную запись. Коэффициенты \(a_{ij}\) естественным образом образуют матрицу \(\boldsymbol A\in\mathbb R^{m\times n}\), правая часть — вектор \(\boldsymbol b \in \mathbb R^m\), а искомые переменные — вектор \(\boldsymbol x \in \mathbb R^n\). И тогда СЛАУ переписывается в чрезвычайно простом и коротком виде

\[ \boldsymbol{Ax} = \boldsymbol b. \]

If \(\boldsymbol b = \boldsymbol 0\), then the linear system is called homogeneous.

A square matrix \(\boldsymbol A\) is called singular if the homogeneous linear system \(\boldsymbol{Ax} = \boldsymbol 0\) has nonzero solution \(\boldsymbol x \ne \boldsymbol 0\). Otherwise \(\boldsymbol A\) is called non-singular or invertible. If \(\boldsymbol A\) is invertible, then the linear system \(\boldsymbol{Ax} = \boldsymbol b\) has unique solution for any \(\boldsymbol b\) which can be written as \(\boldsymbol x =\boldsymbol A^{-1} \boldsymbol b\).

In NumPy a linear system of equations with \(m=n\) can be solved by np.linalg.solve:

import numpy as np
from scipy.linalg import pascal
A = pascal(4, kind='lower')
A

array([[1, 0, 0, 0],
       [1, 1, 0, 0],
       [1, 2, 1, 0],
       [1, 3, 3, 1]], dtype=uint64)

b = np.array([1, -1, 1, -1])
np.linalg.solve(A, b)

array([ 1., -2.,  4., -8.])

Inverse matrix#

Квадратная матрица \(\boldsymbol A \in \mathbb R^{n\times n}\) называется обратимой, или невырожденной, если существует такая матрица \(\boldsymbol B \in \mathbb R^{n\times n}\), что \(\boldsymbol{AB} = \boldsymbol{BA} = \boldsymbol I\). Если такая матрица \(\boldsymbol B\) существует, то она называется обратной к матрице \(\boldsymbol A\) и обозначается \(\boldsymbol A^{-1}\); если же нет, то матрица \(\boldsymbol A\) называется вырожденной (или сингулярной).

Всякая система линейных уравнений \(\boldsymbol{Ax} = \boldsymbol b\) с обратимой матрицей имеет единственное решение, которое может быть получено домножением на \(\boldsymbol A^{-1}\) слева:

\[ \boldsymbol{Ax} = \boldsymbol b \iff \underbrace{\boldsymbol A^{-1}\boldsymbol A}_{\boldsymbol I} \boldsymbol x = \boldsymbol A^{-1}\boldsymbol b \iff \boldsymbol x = \boldsymbol A^{-1}\boldsymbol b. \]

В частности, однородная система уравнений \(\boldsymbol{Ax} = \boldsymbol 0\) с невырожденной матрицей имеет только нулевое решение \(\boldsymbol A^{-1} \boldsymbol 0 = \boldsymbol 0\).

In NumPy the inversed matrix can be found via np.linalg.inv:

import numpy as np
A = np.diag(np.linspace(0.2, 1, num=5))
np.linalg.inv(A)

array([[5.        , 0.        , 0.        , 0.        , 0.        ],
       [0.        , 2.5       , 0.        , 0.        , 0.        ],
       [0.        , 0.        , 1.66666667, 0.        , 0.        ],
       [0.        , 0.        , 0.        , 1.25      , 0.        ],
       [0.        , 0.        , 0.        , 0.        , 1.        ]])

Properties of inverse matrices#

  1. Если обратная матрица существует, то она единственна.

    Proof

    Пусть \(\boldsymbol{AB} = \boldsymbol{CA} = \boldsymbol I\), тогда

    \[ \boldsymbol C(\boldsymbol{AB}) = (\boldsymbol{CA})\boldsymbol B \iff \boldsymbol{CI} = \boldsymbol {IB} \iff \boldsymbol C = \boldsymbol B. \]

    Таким образом, для обратимой матрицы \(\boldsymbol A\) её правая обратная матрица \(\boldsymbol B\) и левая обратная матрица \(\boldsymbol C\) совпадают.

  2. Если матрица \(\boldsymbol A\) обратима, то \((\lambda \boldsymbol A)^{-1} = \frac 1\lambda \boldsymbol A^{-1}\) при \(\lambda \ne 0\).

  3. Если \(\boldsymbol A\) и \(\boldsymbol B\) — две обратимые матрицы одинакового размера, то

    \[ (\boldsymbol{AB})^{-1} = \boldsymbol B^{-1} \boldsymbol A^{-1}. \]

    Proof

    Пользуясь ассоциативностью матричного умножения, получаем

    \[ \boldsymbol{AB}\boldsymbol B^{-1} \boldsymbol A^{-1} = \boldsymbol A(\boldsymbol{BB}^{-1}) \boldsymbol A^{-1} = \boldsymbol A \boldsymbol A^{-1} = \boldsymbol I. \]

    Аналогично проверяется, что \(\boldsymbol B^{-1} \boldsymbol A^{-1} \boldsymbol{AB} = \boldsymbol I\).

  4. Обращение блочной матрицы: если матрицы \(\boldsymbol A\in\mathbb R^{m\times m}\) и \(\boldsymbol B\in\mathbb R^{n\times n}\) обратимы, то

    \[\begin{split} \begin{pmatrix} \boldsymbol A & \boldsymbol 0_{m\times n} \\ \boldsymbol 0_{n\times m} & \boldsymbol B \end{pmatrix}^{-1} = \begin{pmatrix} \boldsymbol A^{-1} & \boldsymbol 0_{m\times n} \\ \boldsymbol 0_{n\times m} & \boldsymbol B^{-1} \end{pmatrix}. \end{split}\]

  5. Обратная матрица к верхней (нижней) треугольной матрице с ненулевыми диагональными элементами \(d_1, \ldots, d_n\) также является верхней (нижней) треугольной с элементами \(\frac 1{d_1}, \ldots, \frac 1{d_n}\) на главной диагонали.

    Proof

    Пусть \(\boldsymbol U\) — верхняя треугольная матрицы размера \(n\times n\). При \(n=1\) утверждение тривиально, при \(n=2\) оно следует из явной формулы для обратной матрицы размера \(2\times 2\). Далее воспользуемся индукцией и запишем матрицу \(\boldsymbol U\) в блочном виде

    \[\begin{split} \boldsymbol U = \begin{pmatrix} d_1 & \boldsymbol u^\top \\ \boldsymbol 0 & \boldsymbol U_{n-1} \end{pmatrix}, \end{split}\]

    где \(\boldsymbol u \in \mathbb R^{n-1}\), верхняя треугольная матрица \(\boldsymbol U_{n-1}\) имеет размер \((n-1)\times(n-1)\), а её обратная матрица \( \boldsymbol U_{n-1}^{-1}\) тоже верхняя треугольная с элементами \(\frac 1{d_2}, \ldots, \frac 1{d_n}\) на главной диагонали. Поищем обратную матрицу \(\boldsymbol U^{-1}\) в таком же виде:

    (46)#\[\begin{split} \boldsymbol U^{-1} = \begin{pmatrix} \frac 1{d_{1}} & \boldsymbol v^\top \\ \boldsymbol 0 & \boldsymbol U_{n-1}^{-1} \end{pmatrix}. \end{split}\]

    По правилу перемножения блочных матриц получаем

    \[\begin{split} \boldsymbol U \boldsymbol U^{-1} = \begin{pmatrix} 1 & d_{1} \boldsymbol v^\top + \boldsymbol u^\top \boldsymbol U_{n-1}^{-1} \\ \boldsymbol 0 & \boldsymbol I_{n-1} \end{pmatrix}. \end{split}\]

    Таким образом, полагая \(\boldsymbol v^\top = -\frac 1{d_1} \boldsymbol u^\top \boldsymbol U_{n-1}^{-1}\), убеждаемся, что верхняя треугольная матрица (46) действительно является обратной к матрице \(\boldsymbol U\). Для нижних треугольных матриц доказательство аналогично.

  6. Если матрица обратима, то транспонированная к ней матрица также обратима, причём

    \[ \big(\boldsymbol A^\mathsf{T}\big)^{-1} = \big(\boldsymbol A^{-1}\big)^\mathsf{T}. \]

    Таким образом, операции транспонирония и взятия обратной матрицы коммутируют; применение подряд (в любом порядке) этих двух операций к матрице \(\boldsymbol A\) обозначают через \(\boldsymbol A^{-\mathsf{T}}\).

    Proof

    Транспонируя равенства \(\boldsymbol{AA}^{-1} = \boldsymbol{A}^{-1} \boldsymbol A = \boldsymbol I\), получаем

    \[ (\boldsymbol{A}^{-1})^\mathsf{T} \boldsymbol A^\mathsf{T} = \boldsymbol A^\mathsf{T} (\boldsymbol{A}^{-1})^\mathsf{T} = \boldsymbol I, \]

    откуда следует, то \((\boldsymbol A^\mathsf{T})^{-1} = (\boldsymbol A^{-1})^\mathsf{T}\).

  7. Если симметричная матрица обратима, то обратная к ней также симметрична.

Gauss—Jordan method#

Чтобы обратить невырожденную матрицу \(\boldsymbol A \in \mathbb R^{n\times n}\), нужно решить \(n\) систем линейных уравнений

(47)#\[ \boldsymbol{Ax}_1 = \boldsymbol e_1, \ldots, \boldsymbol{Ax}_n = \boldsymbol e_n,\]

и тогда \(\boldsymbol A^{-1} = [\boldsymbol x_1 \ldots \boldsymbol x_n]\).

Решение СЛАУ размера \(n\times n\) методом Гаусса требует \(O(n^3)\) арифметических операций. Если решать каждую систему из (47) по отдельности, то суммарная сложность составит \(O(n^4)\). Однако метод Гаусса—Жордана позволяет решить все СЛАУ (47) одновременно за \(O(n^3)\) операций. Для этого составляют блочную матрицу

(48)#\[(\;\boldsymbol A \;\vert\;\boldsymbol I\;)\]

и проводят с ней следующие шаги:

  1. методом Гаусса превращают матрицу \(\boldsymbol A\) в вернюю треугольную матрицу \(\boldsymbol U\);

  2. обратным ходом метода Гаусса из матрицы \(\boldsymbol U\) получают диагональную матрицу \(\boldsymbol D\);

  3. после деления на диагональные элементы \(\boldsymbol D\) становится единичной.

Шаги 1—3 применяются также и правому блоку матрицы (48), и после завершения работы метода Гаусса—Жордана на месте единичной матрицы оказывается обратная матрица \(\boldsymbol A^{-1}\).

Exercises#

  1. Prove that

    \[\begin{split} \begin{pmatrix} a & b \\ c & d \\ \end{pmatrix}^{-1} =\frac1{ad -bc} \begin{pmatrix} d & -b \\ -c & a \\ \end{pmatrix}. \end{split}\]

    if \(ad \ne bc\).

  2. Let \(\boldsymbol \Lambda = \mathrm{diag}\{\lambda_1, \ldots, \lambda_n\}\) be a diagonal matrix. Prove that \(\boldsymbol \Lambda^{-1} = \mathrm{diag}\big\{\frac 1{\lambda_1}, \ldots, \frac 1{\lambda_n}\big\}\) if \(\lambda_i \ne 0\) for all \(i\).

  3. Prove that \(\boldsymbol Q^{-1} = \boldsymbol Q^\mathsf{T}\) if \(\boldsymbol Q\) is orthogonal.

  4. (Sherman—Morrison formula) Let \(\boldsymbol A \in \mathbb R^{n\times n}\) be an invertible matrix and \(\boldsymbol u, \boldsymbol v \in \mathbb R^n\). Prove that

\[ (\boldsymbol A + \boldsymbol u \boldsymbol v^\mathsf{T})^{-1} = \boldsymbol A^{-1} - \frac{\boldsymbol A^{-1} \boldsymbol u \boldsymbol v^\mathsf{T} \boldsymbol A^{-1}}{1 + \boldsymbol v^\mathsf{T}\boldsymbol A^{-1} \boldsymbol u }. \]