MIT 18.06SC, часть 2: ранг и четыре подпространства

Перевод официальных конспектов к четырём лекциям Гилберта Стрэнга из курса MIT 18.06SC. Карта курса — в путеводителе, предыдущая часть — матрицы как преобразования. Перевод распространяется под лицензией CC BY-NC-SA 4.0, © MIT OpenCourseWare.

Как читать вместе с курсом ChinaAI

Это фундамент к уроку «Ранг, SVD и низкоранговые приближения». В уроке ранг объяснён «на пальцах» — как число независимых направлений. Здесь Стрэнг показывает, как его посчитать (методом исключения) и что он говорит о решениях уравнений. Матрицы ранга 1 из лекции 11 — те самые кирпичики, из которых собирается LoRA (урок 6.2.1). Блоки «Проверьте в Python» — наше дополнение.

Лекция 7. Решаем Ax = 0: ведущие переменные, частные решения

У нас есть определение пространства столбцов и нуль-пространства матрицы, но как эти подпространства вычислить?

Вычисляем нуль-пространство

Нуль-пространство матрицы $A$ состоит из векторов $x$, для которых $Ax = 0$.

Пусть

$$A = \begin{bmatrix} 1 & 2 & 2 & 2 \\ 2 & 4 & 6 & 8 \\ 3 & 6 & 8 & 10 \end{bmatrix}.$$

(Заметьте, что столбцы этой матрицы $A$ не независимы.) Наш алгоритм вычисления нуль-пространства этой матрицы использует метод исключения, хотя $A$ необратима. Расширенная матрица не нужна: правая часть (вектор $b$) в этом вычислении равна $0$.

Преобразования строк в методе исключения не меняют решений $Ax = b$, поэтому не меняют и нуль-пространство. (Пространство столбцов они меняют.)

Первый шаг исключения даёт:

$$A = \begin{bmatrix} 1 & 2 & 2 & 2 \\ 2 & 4 & 6 & 8 \\ 3 & 6 & 8 & 10 \end{bmatrix} \longrightarrow \begin{bmatrix} 1 & 2 & 2 & 2 \\ 0 & 0 & 2 & 4 \\ 0 & 0 & 2 & 4 \end{bmatrix}.$$

Во втором столбце ведущего элемента (pivot) нет, поэтому следующий ведущий элемент — двойка в третьем столбце второй строки:

$$\begin{bmatrix} 1 & 2 & 2 & 2 \\ 0 & 0 & 2 & 4 \\ 0 & 0 & 2 & 4 \end{bmatrix} \longrightarrow \begin{bmatrix} 1 & 2 & 2 & 2 \\ 0 & 0 & 2 & 4 \\ 0 & 0 & 0 & 0 \end{bmatrix} = U.$$

Матрица $U$ имеет ступенчатую (echelon, «лестничную») форму. Третья строка нулевая, потому что строка 3 была линейной комбинацией строк 1 и 2 — она исключилась.

Ранг матрицы $A$ равен числу её ведущих элементов. В этом примере ранг $A$ (и $U$) равен 2.

Частные решения

Найдя $U$, можно обратной подстановкой найти решения $x$ уравнения $Ux = 0$. В нашем примере столбцы 1 и 3 — ведущие (в них есть ведущие элементы), а столбцы 2 и 4 — свободные. Переменным $x_2$ и $x_4$ можно присвоить любые значения; их называют свободными переменными. Пусть $x_2 = 1$ и $x_4 = 0$. Тогда

$$2x_3 + 4x_4 = 0 \implies x_3 = 0$$

и

$$x_1 + 2x_2 + 2x_3 + 2x_4 = 0 \implies x_1 = -2.$$

Значит, одно решение — $x = \begin{bmatrix} -2 \\ 1 \\ 0 \\ 0 \end{bmatrix}$ (потому что второй столбец ровно вдвое больше первого). Любое кратное этого вектора лежит в нуль-пространстве.

Если приравнять единице другую свободную переменную, а остальные свободные — нулю, получим другие векторы нуль-пространства. Например,

$$x = \begin{bmatrix} 2 \\ 0 \\ -2 \\ 1 \end{bmatrix}$$

с $x_4 = 1$ и $x_2 = 0$. Нуль-пространство $A$ — множество всех линейных комбинаций этих векторов «частных решений» (special solutions).

Ранг $r$ матрицы $A$ равен числу ведущих столбцов, поэтому свободных столбцов $n - r$: число столбцов (переменных) минус число ведущих. Это число частных решений и размерность нуль-пространства.

Приведённая ступенчатая форма

Продолжая исключение, можно привести $U$ к матрице $R$ в приведённой ступенчатой форме (reduced row echelon form, rref): ведущие элементы равны 1, а над и под ними стоят нули.

$$U = \begin{bmatrix} 1 & 2 & 2 & 2 \\ 0 & 0 & 2 & 4 \\ 0 & 0 & 0 & 0 \end{bmatrix} \to \begin{bmatrix} 1 & 2 & 0 & -2 \\ 0 & 0 & 2 & 4 \\ 0 & 0 & 0 & 0 \end{bmatrix} \to \begin{bmatrix} 1 & 2 & 0 & -2 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 0 \end{bmatrix} = R.$$

Переставив некоторые столбцы, $R$ можно записать так, чтобы в левом верхнем углу стояла единичная матрица, а справа, возможно, — свободные столбцы. Если некоторые строки $A$ линейно зависимы, нижние строки $R$ будут заполнены нулями:

$$R = \begin{bmatrix} I & F \\ 0 & 0 \end{bmatrix}.$$

(Здесь $I$ — квадратная матрица $r \times r$.)

Если $N$ — матрица нуль-пространства $N = \begin{bmatrix} -F \\ I \end{bmatrix}$, то $RN = 0$. (Здесь $I$ — квадратная матрица размера $(n - r) \times (n - r)$, а $0$ — матрица $m \times (n - r)$.) Столбцы $N$ — частные решения.

Проверьте в Python (дополнение переводчика)

import sympy as sp   # pip install sympy — точная арифметика, удобна для rref

A = sp.Matrix([[1, 2, 2, 2],
               [2, 4, 6, 8],
               [3, 6, 8, 10]])
R, pivots = A.rref()
print(R)            # Matrix([[1, 2, 0, -2], [0, 0, 1, 2], [0, 0, 0, 0]])
print(pivots)       # (0, 2) — ведущие столбцы 1 и 3 (нумерация с нуля)
print(A.rank())     # 2
print(A.nullspace())  # два частных решения: (-2, 1, 0, 0) и (2, 0, -2, 1)

Лекция 8. Решаем Ax = b: приведённая форма R

Когда у $Ax = b$ есть решения $x$ и как описать эти решения?

Условия разрешимости для $b$

Снова возьмём пример

$$A = \begin{bmatrix} 1 & 2 & 2 & 2 \\ 2 & 4 & 6 & 8 \\ 3 & 6 & 8 & 10 \end{bmatrix}.$$

Третья строка $A$ — сумма первой и второй, поэтому если $Ax = b$, то третья компонента $b$ равна сумме первой и второй. Если $b$ не удовлетворяет условию $b_3 = b_1 + b_2$, у системы нет решения. Если какая-то комбинация строк $A$ даёт нулевую строку, то такая же комбинация компонент $b$ должна давать ноль.

Один из способов узнать, разрешимо ли $Ax = b$, — применить исключение к расширенной матрице. Если строка $A$ исключилась целиком, то исключилась и соответствующая компонента $b$. В нашем примере строка 3 матрицы $A$ исключается полностью:

$$\left[\begin{array}{cccc|c} 1 & 2 & 2 & 2 & b_1 \\ 2 & 4 & 6 & 8 & b_2 \\ 3 & 6 & 8 & 10 & b_3 \end{array}\right] \to \cdots \to \left[\begin{array}{cccc|c} 1 & 2 & 2 & 2 & b_1 \\ 0 & 0 & 2 & 4 & b_2 - 2b_1 \\ 0 & 0 & 0 & 0 & b_3 - b_2 - b_1 \end{array}\right].$$

Если у $Ax = b$ есть решение, то $b_3 - b_2 - b_1 = 0$. Например, можно взять $b = \begin{bmatrix} 1 \\ 5 \\ 6 \end{bmatrix}$.

Из прошлой лекции мы знаем, что $Ax = b$ разрешимо ровно тогда, когда $b$ лежит в пространстве столбцов $C(A)$. У нас два условия на $b$; на самом деле они равносильны.

Полное решение

Чтобы найти все решения $Ax = b$, сначала проверяем, что уравнение разрешимо, затем находим одно частное решение (particular solution). Полное решение получается, если к частному решению прибавить все векторы нуль-пространства.

Частное решение

Один из способов найти частное решение $Ax = b$ — приравнять все свободные переменные нулю и найти ведущие.

Для нашей матрицы $A$ положим $x_2 = x_4 = 0$ и получим систему

$$\begin{aligned} x_1 + 2x_3 &= 1 \\ 2x_3 &= 3, \end{aligned}$$

у которой решение $x_3 = 3/2$, $x_1 = -2$. Наше частное решение:

$$x_p = \begin{bmatrix} -2 \\ 0 \\ 3/2 \\ 0 \end{bmatrix}.$$

Вместе с нуль-пространством

Общее решение $Ax = b$ даётся формулой $x_{\text{complete}} = x_p + x_n$, где $x_n$ — произвольный вектор нуль-пространства. Чтобы убедиться в этом, сложим $Ax_p = b$ и $Ax_n = 0$ и получим $A(x_p + x_n) = b$ для каждого вектора $x_n$ из нуль-пространства.

В прошлой лекции мы выяснили, что нуль-пространство $A$ — множество всех комбинаций частных решений $\begin{bmatrix} -2 \\ 1 \\ 0 \\ 0 \end{bmatrix}$ и $\begin{bmatrix} 2 \\ 0 \\ -2 \\ 1 \end{bmatrix}$. Поэтому полное решение уравнения $Ax = \begin{bmatrix} 1 \\ 5 \\ 6 \end{bmatrix}$ таково:

$$x_{\text{complete}} = \begin{bmatrix} -2 \\ 0 \\ 3/2 \\ 0 \end{bmatrix} + c_1 \begin{bmatrix} -2 \\ 1 \\ 0 \\ 0 \end{bmatrix} + c_2 \begin{bmatrix} 2 \\ 0 \\ -2 \\ 1 \end{bmatrix},$$

где $c_1$ и $c_2$ — вещественные числа.

Нуль-пространство $A$ — двумерное подпространство $\mathbb{R}^4$, а решения уравнения $Ax = b$ образуют плоскость, параллельную ему и проходящую через $x_p = \begin{bmatrix} -2 \\ 0 \\ 3/2 \\ 0 \end{bmatrix}$.

Ранг

Ранг матрицы равен числу её ведущих элементов. Если $A$ — матрица $m \times n$ ранга $r$, то $r \le m$ и $r \le n$.

Полный ранг по столбцам

Если $r = n$, то, как мы знаем из прошлой лекции, нуль-пространство имеет размерность $n - r = 0$ и содержит только нулевой вектор. Свободных переменных и частных решений нет.

Если у $Ax = b$ есть решение, оно единственно: решений либо 0, либо 1. Такие примеры, где столбцы независимы, часто встречаются в приложениях.

Мы знаем, что $r \le m$, поэтому при $r = n$ число столбцов матрицы не больше числа строк. Приведённая ступенчатая форма матрицы выглядит как $R = \begin{bmatrix} I \\ 0 \end{bmatrix}$. Для любого вектора $b$ из $\mathbb{R}^m$, который не является линейной комбинацией столбцов $A$, у $Ax = b$ нет решения.

Полный ранг по строкам

Если $r = m$, то в приведённой матрице $R = \begin{bmatrix} I & F \end{bmatrix}$ нет нулевых строк, и никаких требований к компонентам $b$ нет. Уравнение $Ax = b$ разрешимо при любом $b$. Свободных переменных $n - r = n - m$, поэтому у $Ax = 0$ есть $n - m$ частных решений.

Полный ранг и по строкам, и по столбцам

Если число ведущих элементов $r = m = n$, то $A$ — обратимая квадратная матрица, а $R$ — единичная матрица. Нуль-пространство имеет размерность ноль, и у $Ax = b$ единственное решение при любом $b$ из $\mathbb{R}^m$.

Итог

Если $R$ — приведённая ступенчатая форма с ведущими столбцами впереди (rref), результаты сводятся в таблицу:

	$r = m = n$	$r = n$, $r$ меньше $m$	$r = m$, $r$ меньше $n$	$r$ меньше $m$ и меньше $n$
$R$	$I$	$\begin{bmatrix} I \\ 0 \end{bmatrix}$	$\begin{bmatrix} I & F \end{bmatrix}$	$\begin{bmatrix} I & F \\ 0 & 0 \end{bmatrix}$
Число решений $Ax = b$	1	0 или 1	бесконечно много	0 или бесконечно много

Лекция 10. Четыре фундаментальных подпространства

В этой лекции мы обсуждаем четыре фундаментальных пространства, связанных с матрицей, и отношения между ними.

Четыре подпространства

Любая матрица $A$ размера $m \times n$ задаёт четыре подпространства (возможно, состоящих только из нулевого вектора).

Пространство столбцов, $C(A)$. Состоит из всех комбинаций столбцов $A$; это векторное пространство в $\mathbb{R}^m$.

Нуль-пространство, $N(A)$. Состоит из всех решений $x$ уравнения $Ax = 0$ и лежит в $\mathbb{R}^n$.

Пространство строк, $C(A^T)$. Комбинации векторов-строк $A$ образуют подпространство $\mathbb{R}^n$. Мы отождествляем его с $C(A^T)$ — пространством столбцов транспонированной матрицы.

Левое нуль-пространство, $N(A^T)$. Нуль-пространство $A^T$ называется левым нуль-пространством $A$. Это подпространство $\mathbb{R}^m$.

Базис и размерность

Пространство столбцов. $r$ ведущих столбцов образуют базис $C(A)$:

$$\dim C(A) = r.$$

Нуль-пространство. Частные решения $Ax = 0$ соответствуют свободным переменным и образуют базис $N(A)$. У матрицы $m \times n$ есть $n - r$ свободных переменных:

$$\dim N(A) = n - r.$$

Пространство строк. Можно было бы выполнить исключение для $A^T$, но вместо этого воспользуемся $R$ — приведённой ступенчатой формой $A$:

$$A = \begin{bmatrix} 1 & 2 & 3 & 1 \\ 1 & 1 & 2 & 1 \\ 1 & 2 & 3 & 1 \end{bmatrix} \to \cdots \to \begin{bmatrix} 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix} = \begin{bmatrix} I & F \\ 0 & 0 \end{bmatrix} = R.$$

Пространства столбцов $A$ и $R$ разные, но пространство строк $R$ совпадает с пространством строк $A$. Строки $R$ — комбинации строк $A$, а поскольку исключение обратимо, строки $A$ — комбинации строк $R$.

Первые $r$ строк $R$ — «ступенчатый» базис пространства строк $A$:

$$\dim C(A^T) = r.$$

Левое нуль-пространство. У матрицы $A^T$ $m$ столбцов. Мы только что видели, что $r$ — ранг $A^T$, значит, свободных столбцов у $A^T$ должно быть $m - r$:

$$\dim N(A^T) = m - r.$$

Левое нуль-пространство — множество векторов $y$, для которых $A^T y = 0$. Равносильно: $y^T A = 0$; здесь $y$ и $0$ — векторы-строки. Мы говорим «левое нуль-пространство», потому что в этом уравнении $y^T$ стоит слева от $A$.

Чтобы найти базис левого нуль-пространства, приведём расширенную версию $A$:

$$\begin{bmatrix} A_{m \times n} & I_{m \times m} \end{bmatrix} \longrightarrow \begin{bmatrix} R_{m \times n} & E_{m \times m} \end{bmatrix}.$$

Отсюда получаем матрицу $E$, для которой $EA = R$. (Если $A$ — квадратная обратимая матрица, то $E = A^{-1}$.) В нашем примере

$$EA = \begin{bmatrix} -1 & 2 & 0 \\ 1 & -1 & 0 \\ -1 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 2 & 3 & 1 \\ 1 & 1 & 2 & 1 \\ 1 & 2 & 3 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix} = R.$$

Нижние $m - r$ строк $E$ описывают линейные зависимости между строками $A$, потому что нижние $m - r$ строк $R$ нулевые. Здесь $m - r = 1$ (одна нулевая строка в $R$).

Нижние $m - r$ строк $E$ удовлетворяют уравнению $y^T A = 0$ и образуют базис левого нуль-пространства $A$.

Примечание переводчика: в оригинале расширенная матрица записана как $\begin{bmatrix} A_{m \times n} & I_{m \times n} \end{bmatrix}$; единичная матрица, которую дописывают к $A$, и получающаяся матрица $E$ имеют размер $m \times m$.

Новое векторное пространство

Множество всех матриц $3 \times 3$ образует векторное пространство; назовём его $M$. Матрицы можно складывать и умножать на числа, и есть нулевая матрица (нейтральный элемент по сложению). Если забыть, что матрицы можно перемножать между собой, они ведут себя в точности как векторы.

Некоторые подпространства $M$:

• все верхнетреугольные матрицы;
• все симметричные матрицы;
• $D$ — все диагональные матрицы.

$D$ — пересечение первых двух пространств. Его размерность равна 3; один из базисов $D$:

$$\begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix},\quad \begin{bmatrix} 1 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 0 \end{bmatrix},\quad \begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 7 \end{bmatrix}.$$

Проверьте в Python (дополнение переводчика)

import numpy as np

A = np.array([[1, 2, 3, 1],
              [1, 1, 2, 1],
              [1, 2, 3, 1]])
m, n = A.shape
r = np.linalg.matrix_rank(A)
print(r, n - r, m - r)        # 2 2 1: dim C(A)=dim C(Aᵀ)=2, dim N(A)=2, dim N(Aᵀ)=1

E = np.array([[-1, 2, 0],
              [1, -1, 0],
              [-1, 0, 1]])
print(E @ A)                  # приведённая форма R
y = E[-1]                     # последняя строка E — базис левого нуль-пространства
print(y @ A)                  # [0 0 0 0]: yᵀA = 0

Лекция 11. Пространства матриц; ранг 1; графы «тесного мира»

Мы много говорили о $\mathbb{R}^n$, но векторные пространства можно строить из любых «векторов», которые разрешают сложение и умножение на число.

Новые векторные пространства

Матрицы 3 на 3

Мы рассматривали пространство $M$ всех матриц $3 \times 3$ и нашли в нём несколько подпространств: симметричные матрицы $3 \times 3$ — $S$, верхнетреугольные матрицы $3 \times 3$ — $U$ и пересечение $D$ этих двух пространств — пространство диагональных матриц $3 \times 3$.

Размерность $M$ равна 9: чтобы задать элемент $M$, нужно выбрать 9 чисел. Пространство $M$ очень похоже на $\mathbb{R}^9$. Хороший выбор базиса:

$$\begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix},\ \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix},\ \begin{bmatrix} 0 & 0 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix},\ \ldots,\ \begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix},\ \begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}.$$

Подпространство симметричных матриц $S$ имеет размерность 6. Выбирая элемент $S$, мы задаём три числа на диагонали и три в правом верхнем углу, а они определяют, что стоит в левом нижнем. Один из базисов $S$:

$$\begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix},\ \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix},\ \begin{bmatrix} 0 & 0 & 1 \\ 0 & 0 & 0 \\ 1 & 0 & 0 \end{bmatrix},\ \begin{bmatrix} 0 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{bmatrix},\ \begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix},\ \begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}.$$

Размерность $U$ тоже равна 6: свободы в выборе элементов верхнетреугольной матрицы столько же, сколько в выборе симметричной. Базис $U$:

$$\begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix},\ \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix},\ \begin{bmatrix} 0 & 0 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix},\ \begin{bmatrix} 0 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{bmatrix},\ \begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{bmatrix},\ \begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}.$$

Он оказался частью базиса, выбранного для $M$, а вот для $S$ базиса, который был бы частью базиса $M$, нет.

Подпространство $D = S \cap U$ диагональных матриц $3 \times 3$ имеет размерность 3. Благодаря тому, как мы выбрали базисы $U$ и $S$, хороший базис $D$ — пересечение этих базисов.

Является ли $S \cup U$ — множество матриц $3 \times 3$, которые симметричны или верхнетреугольны, — подпространством $M$? Нет. Это как взять две прямые в $\mathbb{R}^2$ и спросить, образуют ли они вместе подпространство: промежуток между ними придётся заполнить. Если взять все возможные суммы элементов $S$ и элементов $U$, получится то, что называют суммой $S + U$. Это подпространство $M$. На самом деле $S + U = M$. Для сумм и пересечений размерности подчиняются правилу:

$$\dim S + \dim U = \dim(S + U) + \dim(S \cap U).$$

Примечание переводчика: в PDF-оригинале в этой формуле стоит $\dim S \cup U$; по смыслу абзаца (и по числам: $6 + 6 = 9 + 3$) должно быть $\dim(S + U)$.

Дифференциальные уравнения

Ещё один пример векторного пространства, которое не является $\mathbb{R}^n$, встречается в дифференциальных уравнениях.

Решения $y$ уравнения $\dfrac{d^2 y}{dx^2} + y = 0$ можно считать элементами нуль-пространства. Вот некоторые решения:

$$y = \cos x, \quad y = \sin x \quad\text{и}\quad y = e^{ix}.$$

Полное решение:

$$y = c_1 \cos x + c_2 \sin x,$$

где $c_1$ и $c_2$ — любые комплексные числа. Это пространство решений — двумерное векторное пространство с базисными векторами $\cos x$ и $\sin x$. (Хотя они не «похожи» на векторы, из них можно построить векторное пространство: их можно складывать и умножать на константу.)

Матрицы ранга 4

Пусть теперь $M$ — пространство матриц $5 \times 17$. Подмножество $M$ из всех матриц ранга 4 — не подпространство, даже если добавить нулевую матрицу: сумма двух матриц ранга 4 может иметь другой ранг.

В $\mathbb{R}^4$ множество всех векторов $v = \begin{bmatrix} v_1 \\ v_2 \\ v_3 \\ v_4 \end{bmatrix}$, для которых $v_1 + v_2 + v_3 + v_4 = 0$, — подпространство. Оно содержит нулевой вектор и замкнуто относительно сложения и умножения на число. Это нуль-пространство матрицы $A = \begin{bmatrix} 1 & 1 & 1 & 1 \end{bmatrix}$. Поскольку ранг $A$ равен 1, размерность этого нуль-пространства $n - r = 3$. Базис подпространства образуют частные решения:

$$\begin{bmatrix} -1 \\ 1 \\ 0 \\ 0 \end{bmatrix},\quad \begin{bmatrix} -1 \\ 0 \\ 1 \\ 0 \end{bmatrix},\quad \begin{bmatrix} -1 \\ 0 \\ 0 \\ 1 \end{bmatrix}.$$

Пространство столбцов $A$ — это $\mathbb{R}^1$. Левое нуль-пространство содержит только нулевой вектор, его размерность ноль, а базис — пустое множество. Пространство строк $A$ тоже имеет размерность 1.

Матрицы ранга 1

Ранг матрицы — размерность её пространства столбцов (или строк). Матрица

$$A = \begin{bmatrix} 1 & 4 & 5 \\ 2 & 8 & 10 \end{bmatrix}$$

имеет ранг 1, потому что каждый её столбец кратен первому:

$$A = \begin{bmatrix} 1 \\ 2 \end{bmatrix} \begin{bmatrix} 1 & 4 & 5 \end{bmatrix}.$$

Любую матрицу ранга 1 можно записать как $A = UV^T$, где $U$ и $V$ — векторы-столбцы. Матрицы ранга 1 будут служить нам кирпичиками для более сложных матриц.

Графы «тесного мира»

В этом курсе граф $G$ — это набор вершин, соединённых рёбрами:

$$G = \{\text{вершины}, \text{рёбра}\}.$$

Типичный граф показан на рисунке 1 (в оригинале — граф с 5 вершинами и 6 рёбрами). Другой пример графа: каждая вершина — человек, а две вершины соединены ребром, если эти люди дружат. Можно спросить, насколько два человека близки друг к другу в этом графе: какое наименьшее число дружеских связей их соединяет? Вопрос «каково наибольшее расстояние между двумя людьми в графе?» стоит за выражениями «шесть рукопожатий» и «мир тесен».

Ещё один граф — Всемирная паутина: вершины — сайты, рёбра — ссылки.

Мы будем описывать графы матрицами; так будет легко отвечать на вопросы о расстояниях между вершинами.

Ранг 1 и LoRA (дополнение переводчика)

Сумма $r$ матриц ранга 1 имеет ранг не больше $r$. LoRA дообучает не всю матрицу весов $W$ размера $d \times k$, а добавку $BA$, где $B$ — $d \times r$, $A$ — $r \times k$: это сумма $r$ матриц ранга 1, и параметров в ней $r(d + k)$ вместо $dk$. Подробности — в уроке 6.2.1.

import numpy as np

A = np.outer([1, 2], [1, 4, 5])           # U Vᵀ из лекции
print(A, np.linalg.matrix_rank(A))        # [[ 1  4  5] [ 2  8 10]] 1

rng = np.random.default_rng(0)
B = rng.normal(size=(512, 8))             # d × r
C = rng.normal(size=(8, 256))             # r × k
print(np.linalg.matrix_rank(B @ C))       # 8 — ранг произведения не больше r
print(512 * 256, 8 * (512 + 256))         # 131072 параметров против 6144

Словарик

EN	RU
pivot, pivot column	ведущий элемент, ведущий столбец
free column, free variable	свободный столбец, свободная переменная
rank	ранг
(row) echelon form	ступенчатая форма
reduced row echelon form (rref)	приведённая ступенчатая форма
nullspace	нуль-пространство (ядро)
column space / row space	пространство столбцов / пространство строк
left nullspace	левое нуль-пространство
special solution / particular solution	частное решение нуль-пространства / частное решение $Ax = b$
complete solution	полное (общее) решение
full column rank / full row rank	полный ранг по столбцам / по строкам
basis, dimension	базис, размерность
subspace, intersection, sum	подпространство, пересечение, сумма
rank one matrix	матрица ранга 1

Два «частных решения»

В английском тексте это разные слова: special solutions — базисные решения $Ax = 0$, которые получаются, когда одна свободная переменная равна 1, а остальные 0; particular solution $x_p$ — одно какое-нибудь решение $Ax = b$. По-русски оба часто называют частными решениями; не путайте их по смыслу.

Дальше: часть 3 — собственные числа и собственные векторы.