Inverse matrix

Linear systems

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

$$\begin{array}{r}\begin{array}{rl}{a}_{11}{x}_1& +a_{12}{x}_2+\dots +a_{1n}{x}_n=b_1\\ a_{21}{x}_1& +a_{22}{x}_2+\dots +a_{2n}{x}_n=b_2\\ \dots & \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \\ a_{m1}{x}_1& +a_{m2}{x}_2+\dots +a_{mn}{x}_n=b_m\end{array},\end{array}$$

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

$$\mathit{A}\mathit{x}=\mathit{b}.$$

If $\mathit{b}=\mathbf{0}$, then the linear system is called homogeneous.

A square matrix $\mathit{A}$ is called singular if the homogeneous linear system $\mathit{A}\mathit{x}=\mathbf{0}$ has nonzero solution $\mathit{x}\ne \mathbf{0}$. Otherwise $\mathit{A}$ is called non-singular or invertible. If $\mathit{A}$ is invertible, then the linear system $\mathit{A}\mathit{x}=\mathit{b}$ has unique solution for any $\mathit{b}$ which can be written as $\mathit{x}={\mathit{A}}^{-1}\mathit{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

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

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

$$\mathit{A}\mathit{x}=\mathit{b}⟺\underset{\mathit{I}}{\underbrace{{\mathit{A}}^{-1}\mathit{A}}}\mathit{x}={\mathit{A}}^{-1}\mathit{b}⟺\mathit{x}={\mathit{A}}^{-1}\mathit{b}.$$

В частности, однородная система уравнений $\mathit{A}\mathit{x}=\mathbf{0}$ с невырожденной матрицей имеет только нулевое решение ${\mathit{A}}^{-1}\mathbf{0}=\mathbf{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

   Пусть $\mathit{A}\mathit{B}=\mathit{C}\mathit{A}=\mathit{I}$, тогда

   $$\mathit{C}(\mathit{A}\mathit{B})=(\mathit{C}\mathit{A})\mathit{B}⟺\mathit{C}\mathit{I}=\mathit{I}\mathit{B}⟺\mathit{C}=\mathit{B}.$$

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

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

3. Если $\mathit{A}$ и $\mathit{B}$ — две обратимые матрицы одинакового размера, то

   $$(\mathit{A}\mathit{B}{)}^{-1}={\mathit{B}}^{-1}{\mathit{A}}^{-1}.$$

   Proof

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

   $$\mathit{A}\mathit{B}{\mathit{B}}^{-1}{\mathit{A}}^{-1}=\mathit{A}(\mathit{B}{\mathit{B}}^{-1}){\mathit{A}}^{-1}=\mathit{A}{\mathit{A}}^{-1}=\mathit{I}.$$

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

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

   $$\begin{array}{r}{\left(\begin{array}{cc}\mathit{A}& {\mathbf{0}}_{m\times n}\\ {\mathbf{0}}_{n\times m}& \mathit{B}\end{array}\right)}^{-1}=\left(\begin{array}{cc}{\mathit{A}}^{-1}& {\mathbf{0}}_{m\times n}\\ {\mathbf{0}}_{n\times m}& {\mathit{B}}^{-1}\end{array}\right).\end{array}$$

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

   Proof

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

   $$\begin{array}{r}\mathit{U}=\left(\begin{array}{cc}{d}_1& {\mathit{u}}^{\mathrm{\top }}\\ \mathbf{0}& {\mathit{U}}_{n-1}\end{array}\right),\end{array}$$

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

   (46)$$\begin{array}{r}{\mathit{U}}^{-1}=\left(\begin{array}{cc}\frac{1}{d_1}& {\mathit{v}}^{\mathrm{\top }}\\ \mathbf{0}& {\mathit{U}}_{n-1}^{-1}\end{array}\right).\end{array}$$

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

   $$\begin{array}{r}\mathit{U}{\mathit{U}}^{-1}=\left(\begin{array}{cc}1& d_1{\mathit{v}}^{\mathrm{\top }}+{\mathit{u}}^{\mathrm{\top }}{\mathit{U}}_{n-1}^{-1}\\ \mathbf{0}& {\mathit{I}}_{n-1}\end{array}\right).\end{array}$$

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

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

   $$({\mathit{A}}^{\mathsf{T}}{)}^{-1}=({\mathit{A}}^{-1}{)}^{\mathsf{T}}.$$

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

   Proof

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

   $$({\mathit{A}}^{-1}{)}^{\mathsf{T}}{\mathit{A}}^{\mathsf{T}}={\mathit{A}}^{\mathsf{T}}({\mathit{A}}^{-1}{)}^{\mathsf{T}}=\mathit{I},$$

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

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

Gauss—Jordan method

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

(47)$$\mathit{A}{\mathit{x}}_1={\mathit{e}}_1,\dots ,\mathit{A}{\mathit{x}}_n={\mathit{e}}_n,$$

и тогда ${\mathit{A}}^{-1}=[{\mathit{x}}_1\dots {\mathit{x}}_n]$.

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

(48)$$(\mathit{A}|\mathit{I})$$

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

1. методом Гаусса превращают матрицу $\mathit{A}$ в вернюю треугольную матрицу $\mathit{U}$;

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

3. после деления на диагональные элементы $\mathit{D}$ становится единичной.

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

Exercises

1. Prove that

   $$\begin{array}{r}{\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)}^{-1}=\frac{1}{ad-bc}\left(\begin{array}{cc}d& -b\\ -c& a\end{array}\right).\end{array}$$

   if $ad\ne bc$.

2. Let $\mathbf{\Lambda }=\mathrm{diag}\{{\lambda }_1,\dots ,{\lambda }_n\}$ be a diagonal matrix. Prove that ${\mathbf{\Lambda }}^{-1}=\mathrm{diag}\{\frac{1}{{\lambda }_1},\dots ,\frac{1}{{\lambda }_n}\}$ if ${\lambda }_i\ne 0$ for all $i$.

3. Prove that ${\mathit{Q}}^{-1}={\mathit{Q}}^{\mathsf{T}}$ if $\mathit{Q}$ is orthogonal.

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

$$(\mathit{A}+\mathit{u}{\mathit{v}}^{\mathsf{T}}{)}^{-1}={\mathit{A}}^{-1}-\frac{{\mathit{A}}^{-1}\mathit{u}{\mathit{v}}^{\mathsf{T}}{\mathit{A}}^{-1}}{1+{\mathit{v}}^{\mathsf{T}}{\mathit{A}}^{-1}\mathit{u}}.$$