Линейная алгебра: векторы, пространства, базисы и линейная независимость

Если спросить инженера, какой раздел математики окупился сильнее всего, чаще всего услышишь «линейная алгебра». Причина простая: это единственная область, где мы умеем решать задачи точно, быстро и в огромных размерностях. Как только реальную задачу удаётся согнуть до линейной, у неё появляется алгоритм с предсказуемой сложностью и готовая реализация в BLAS/LAPACK, оптимизированная под конкретный процессор тридцать лет подряд.

Эта статья — фундамент. Здесь нет матриц как отдельного объекта (они в следующей статье трека), нет собственных значений и разложений. Здесь мы разбираемся с тем, что лежит под всем этим: что такое вектор, что такое пространство, что значит «набор векторов содержит лишний» и почему размерность — это не количество чисел в кортеже.

Зачем это программисту: три сцены из практики

Сцена 1. Эмбеддинги. Текст, картинка, пользователь, товар — всё превращают в вектор из 384/768/1536 чисел. Поиск похожего — это косинус угла между векторами. Кластеризация — геометрия в этом пространстве. Всё, что делает векторная БД (pgvector, Qdrant, FAISS), — это геометрия в R^n с индексом сверху.

Сцена 2. Отладка «странной» модели. Матрица признаков не обращается, регрессия выдаёт безумные коэффициенты, которые скачут при добавлении одной строки данных. Диагноз почти всегда один: колонки признаков линейно зависимы (мультиколлинеарность). Вы добавили price, price_usd и price_eur — три числа, но одно направление информации.

Сцена 3. Коды и криптография. CRC, коды Хэмминга, Рида–Соломона, схемы разделения секрета Шамира, erasure-кодирование в Ceph и HDFS — это линейная алгебра над конечным полем. Те же базисы и та же независимость, только арифметика по модулю 2 или в GF(256).

Ни одна из трёх сцен не про «стрелочки на плоскости». Поэтому начинать надо с правильного определения вектора.

Что такое вектор: три ответа, и только третий верный

Есть три распространённых ответа, и разница между ними — не педантизм, а рабочий инструмент.

1. Физик: вектор — направленный отрезок, у него есть длина и направление.
2. Программист: вектор — это массив чисел, float[3], np.array([1.0, 2.0, 3.0]).
3. Математик: вектор — это элемент векторного пространства, то есть любой объект, который умеет складываться сам с собой и умножаться на скаляр по определённым правилам.

Первые два — частные случаи третьего. И именно третий даёт мощность: как только вы доказали теорему про абстрактное векторное пространство, она автоматически верна для стрелок, массивов, многочленов, функций, матриц, сигналов и решений линейных ОДУ. Один раз доказали — бесконечно много применений.

Строгое определение

Пусть F — поле (для начала думайте R — вещественные числа; про поля подробнее в статье Абстрактная алгебра). Векторное пространство над F — это множество V с двумя операциями:

сложение:            + : V × V -> V
умножение на скаляр: · : F × V -> V

удовлетворяющими восьми аксиомам для всех u, v, w ∈ V и a, b ∈ F:

A1 (ассоциативность)    (u + v) + w = u + (v + w)
A2 (коммутативность)     u + v = v + u
A3 (нейтральный)         существует 0 ∈ V:  v + 0 = v
A4 (обратный)            для каждого v существует -v:  v + (-v) = 0
S1 (согласованность)     a·(b·v) = (a·b)·v
S2 (единица)             1·v = v
S3 (дистрибутивность 1)  a·(u + v) = a·u + a·v
S4 (дистрибутивность 2)  (a + b)·v = a·v + b·v

Первые четыре аксиомы говорят, что (V, +) — абелева группа. Остальные — что скаляры действуют «разумно». Всё. Больше ничего в определении нет: ни длины, ни угла, ни координат. Это критично: длина и угол — дополнительная структура (скалярное произведение), которую добавляют отдельно, и в конце статьи мы к ней придём.

Примеры пространств, которые не выглядят как стрелки

Последняя строка — любимый пример: множество решений однородного линейного дифференциального уравнения образует векторное пространство размерности 2, а {sin, cos} — его базис. Именно поэтому общее решение записывают как линейную комбинацию.

Пример с GF(2)^8 — прямо про код. Байт — это вектор из 8 бит, сложение векторов — это XOR, скаляры всего два (0 и 1). Отсюда, например, свойство a ^ b ^ b == a, на котором построены RAID-5, one-time pad и erasure-коды.

А что НЕ является векторным пространством

Проверка аксиом — не формальность, она ловит ошибки моделирования.

• Множество векторов с неотрицательными координатами (x ≥ 0) — не пространство: нет обратного элемента (A4).
• Прямая y = x + 1 — не пространство: не содержит нуля (A3), и сумма двух точек с неё с неё же уходит. А вот y = x — пространство. Общее правило: подпространство обязано проходить через 0.
• Множество нормированных векторов (||v|| = 1, сфера) — не пространство: сумма двух единичных векторов не единична. Это ловушка для тех, кто нормализует эмбеддинги и потом усредняет их: среднее нормированных векторов уже не нормировано, надо нормировать повторно.
• R^n с покомпонентным max вместо сложения — не пространство: нет обратного (тропическая полукольцевая структура, отдельная интересная тема).

import numpy as np

# Аксиомы легко проверить эмпирически — это хороший property-based тест
rng = np.random.default_rng(0)
u, v, w = rng.normal(size=(3, 5))
a, b = 2.5, -1.25

assert np.allclose((u + v) + w, u + (v + w))          # A1
assert np.allclose(a * (b * v), (a * b) * v)          # S1
assert np.allclose(a * (u + v), a * u + a * v)        # S3
assert np.allclose((a + b) * v, a * v + b * v)        # S4

Заметьте np.allclose, а не ==: с float арифметика не ассоциативна точно, только приближённо. Это первый намёк на то, что численная линейная алгебра — отдельная дисциплина; подробности в статье Численные методы.

Линейная комбинация и линейная оболочка (span)

Определение. Линейная комбинация векторов v1..vk с коэффициентами a1..ak ∈ F — это вектор a1·v1 + ... + ak·vk.

Определение. Линейная оболочка span{v1..vk} — множество всех линейных комбинаций этих векторов.

Интуиция: span — это «куда я могу добраться, имея только эти направления и возможность масштабировать и складывать». Один ненулевой вектор натягивает прямую. Два непараллельных — плоскость. Три «настоящих» направления в R³ — всё пространство.

Ключевое свойство: span всегда является подпространством — он замкнут относительно сложения и умножения на скаляр и содержит ноль (возьмите все коэффициенты нулевыми). Это самый естественный способ порождать подпространства.

Практический смысл: если ваши признаки в модели — это v1..vk, то модель линейной регрессии физически способна выразить только функции из span этих признаков (плюс свободный член). Никакая оптимизация не выведет её за пределы оболочки — надо добавлять новые признаки.

import numpy as np

def in_span(vectors, target, tol=1e-10):
    """Лежит ли target в span(vectors)? Решаем МНК и смотрим на невязку.
    vectors: список векторов (строки). Сложность O(n·k^2) по времени, O(n·k) по памяти."""
    A = np.array(vectors, dtype=float).T          # столбцы — базисные кандидаты
    coeffs, *_ = np.linalg.lstsq(A, target, rcond=None)
    residual = np.linalg.norm(A @ coeffs - target)
    return residual < tol * max(1.0, np.linalg.norm(target)), coeffs

u = np.array([1.0, 2.0, 0.0])
v = np.array([0.0, 1.0, 1.0])

print(in_span([u, v], np.array([2.0, 5.0, 1.0])))   # (True,  [2., 1.])
print(in_span([u, v], np.array([0.0, 0.0, 1.0])))   # (False, ...)

Обратите внимание на относительный допуск tol * ||target||: абсолютный порог 1e-10 на данных с масштабом 1e6 бессмысленен. Это одна из самых частых ошибок в числовом коде.

Линейная независимость: самое важное понятие статьи

Определение. Векторы v1..vk линейно независимы, если равенство

a1·v1 + a2·v2 + ... + ak·vk = 0

выполняется только при a1 = a2 = ... = ak = 0. Если существует хотя бы одна нетривиальная комбинация, дающая ноль, векторы линейно зависимы.

Интуиция. Зависимость означает «один из векторов лишний»: его можно выразить через остальные. Действительно, если a1 ≠ 0, то

v1 = -(a2/a1)·v2 - ... - (ak/a1)·vk

то есть v1 не добавляет нового направления, а span набора не изменится, если его выбросить. Независимость — это «нет избыточности, каждый вектор несёт информацию, которой нет у остальных».

Второе, эквивалентное определение, которое стоит держать в голове: набор независим тогда и только тогда, когда разложение любого вектора из его span единственно. Это и есть причина, по которой независимость важна: она превращает «представление» в «координаты».

Разбор руками

Проверим v1 = (1, 2, 3), v2 = (2, 4, 6), v3 = (0, 1, 1).

Сразу видно v2 = 2·v1, значит 2·v1 - 1·v2 + 0·v3 = 0 — нетривиальная комбинация. Набор зависим. При этом v3 не выражается через v1, поэтому span{v1, v2, v3} = span{v1, v3} — плоскость, размерность 2.

Теперь честный ручной счёт для w1 = (1, 1, 0), w2 = (0, 1, 1), w3 = (1, 0, 1). Записываем систему a·w1 + b·w2 + c·w3 = 0 покомпонентно:

a       + c = 0     (первая координата)
a + b       = 0     (вторая)
    b + c   = 0     (третья)

Из первого c = -a, из второго b = -a, подставляем в третье: -a + (-a) = -2a = 0, значит a = 0, дальше b = c = 0. Только тривиальное решение — векторы независимы, и они образуют базис R³.

Забавный контрапункт: те же три вектора над GF(2) (арифметика по модулю 2) уже зависимы! Там -2a = 0 выполняется при любом a, потому что 2 = 0. Проверьте: w1 + w2 + w3 = (1+0+1, 1+1+0, 0+1+1) = (0,0,0) mod 2. Мораль: линейная независимость зависит от поля скаляров, и это не абстрактная тонкость — на этом ломаются реализации кодов коррекции ошибок.

import numpy as np

def is_independent(vectors, tol=None):
    """Проверка независимости через численный ранг (SVD).
    Время O(n·k^2), память O(n·k). Это надёжный способ; определитель — нет."""
    A = np.array(vectors, dtype=float).T
    s = np.linalg.svd(A, compute_uv=False)
    if tol is None:
        tol = max(A.shape) * np.finfo(float).eps * (s[0] if s.size else 0.0)
    rank = int((s > tol).sum())
    return rank == A.shape[1], rank, s

print(is_independent([[1,2,3],[2,4,6],[0,1,1]])[:2])   # (False, 2)
print(is_independent([[1,1,0],[0,1,1],[1,0,1]])[:2])   # (True, 3)

# Тот же набор над GF(2): считаем ранг гауссовым исключением по модулю 2
def gf2_rank(rows):
    rows = [int("".join(map(str, r)), 2) for r in rows]   # строка -> битовая маска
    rank = 0
    for bit in reversed(range(max(r.bit_length() for r in rows))):
        pivot = next((i for i in range(rank, len(rows)) if rows[i] >> bit & 1), None)
        if pivot is None:
            continue
        rows[rank], rows[pivot] = rows[pivot], rows[rank]
        for i in range(len(rows)):
            if i != rank and (rows[i] >> bit & 1):
                rows[i] ^= rows[rank]                      # XOR = вычитание в GF(2)
        rank += 1
    return rank

print(gf2_rank([[1,1,0],[0,1,1],[1,0,1]]))   # 2 — над GF(2) зависимы!

Реализация gf2_rank — это, по сути, продакшн-приём: над GF(2) целая строка матрицы помещается в машинное слово, а элементарные преобразования — это XOR. Так работают быстрые декодеры LDPC и erasure-кодов.

Почему определитель — плохой детектор зависимости

Классический школьный рецепт «если det = 0, векторы зависимы» математически верен, но численно почти бесполезен:

• он работает только для квадратного набора (k = n);
• определитель масштабируется как t^n: умножьте все векторы на 0.1 в размерности 20 — и det упадёт в 10^20 раз, не изменив ни одного геометрического свойства;
• он говорит «да/нет», а нужно «насколько близко к зависимости».

Правильный инструмент — сингулярные числа и число обусловленности cond = s_max / s_min. Если cond порядка 1e12, набор формально независим, но практически вырожден: коэффициенты регрессии будут мусором. Подробно этот аппарат разбирается в статье Собственные значения, SVD и матричные разложения.

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

Определение. Базис пространства V — линейно независимый набор, span которого равен V. То есть минимальный порождающий набор, он же максимальный независимый.

Основная теорема (о размерности). Все базисы конечномерного пространства содержат одинаковое количество векторов. Это число называют размерностью dim V.

Доказательство опирается на лемму о замене (Steinitz exchange lemma): если {u1..um} независимы, а {w1..wn} порождают V, то m ≤ n, и любые m векторов из порождающего набора можно заменить на u. Применив лемму к двум базисам в обе стороны, получаем m ≤ n и n ≤ m, то есть m = n. Аккуратное изложение — у Axler, «Linear Algebra Done Right» (https://linear.axler.net/), глава 2; это лучший источник, если хочется понять линейную алгебру без матричной каши.

Что даёт базис. Ровно одно, но решающее: координаты. Если B = {b1..bn} — базис, то любой v ∈ V записывается единственным образом:

v = x1·b1 + ... + xn·bn        =>  [v]_B = (x1, ..., xn)

Единственность — прямое следствие независимости: если бы было два разложения, их разность дала бы нетривиальный ноль. Отображение v -> [v]_B — изоморфизм V и F^n. Именно поэтому любое n-мерное пространство над R «то же самое», что R^n: многочлены, матрицы, решения ОДУ — всё это можно программировать как массивы, выбрав базис.

Координаты — это не сам вектор

Главное концептуальное заблуждение всей темы: путать вектор и его координаты. Вектор p на картинке — один и тот же геометрический объект. В стандартном базисе он (3, 2), в базисе {(2,1), (−1,1)} — (5/3, 1/3). Числа разные, объект один.

Практический вывод: массив чисел без указания базиса — неполные данные. Это ровно та ошибка, из-за которой ломаются пайплайны с эмбеддингами: вектор из модели v1 и вектор из модели v2 имеют одинаковую длину 768 и одинаковый тип float32, но живут в разных базисах разных пространств. Косинус между ними — случайное число. Отсюда правило: эмбеддинги всегда версионируются вместе с моделью, а при смене модели индекс переиндексируется целиком.

import numpy as np

B = np.array([[2.0, -1.0],
              [1.0,  1.0]])          # столбцы — базисные векторы b1, b2

p_std = np.array([3.0, 2.0])         # координаты в стандартном базисе
p_B = np.linalg.solve(B, p_std)      # координаты в базисе B
print(p_B)                           # [1.6667 0.3333] = (5/3, 1/3)

# обратный переход — просто умножение на матрицу базиса
print(B @ p_B)                       # [3. 2.]

Матрица B здесь — «матрица перехода»: её столбцы — базисные векторы, записанные в старых координатах. Переход «из базиса в стандартный» — умножение, «из стандартного в базис» — решение системы. Формализм смены базиса и его роль в линейных отображениях — тема следующей статьи трека.

Мини-таксономия понятий

Подпространства и как они возникают в коде

Определение. U ⊆ V — подпространство, если U непусто и замкнуто относительно сложения и умножения на скаляр. Эквивалентно: 0 ∈ U и a·u + b·w ∈ U для всех u, w ∈ U.

Три подпространства, с которыми вы столкнётесь постоянно:

• Ядро (kernel/null space) линейного отображения — множество векторов, переходящих в 0. В прикладном смысле: «направления, которые модель не различает». Если ядро матрицы признаков нетривиально, у задачи регрессии бесконечно много решений с одинаковым качеством.
• Образ (image/column space) — span столбцов. То, что модель в принципе способна выразить.
• Ортогональное дополнение U⊥ — всё, что перпендикулярно U. На нём стоит вся теория наименьших квадратов: невязка МНК ортогональна образу.

Фундаментальное соотношение (теорема о ранге и дефекте, rank–nullity):

dim ker(A) + dim im(A) = число столбцов A

Читается так: «каждое измерение входа либо переживает отображение (попадает в образ), либо схлопывается (попадает в ядро)». Это одна из самых практичных теорем: она сразу говорит, сколько степеней свободы останется у решения системы.

Диаграмма кодирует две классические теоремы: из любого порождающего набора можно выделить базис (выбрасыванием) и любой независимый набор можно дополнить до базиса (добавлением). Обе конструктивны и обе реализуются одним и тем же алгоритмом — гауссовым исключением.

Скалярное произведение: откуда берутся длина и угол

До сих пор в пространстве не было ни длины, ни угла — аксиомы про них молчат. Добавим структуру.

Определение. Скалярное произведение на вещественном V — отображение ⟨·,·⟩ : V × V -> R, которое:

1) симметрично:     ⟨u, v⟩ = ⟨v, u⟩
2) линейно:         ⟨a·u + b·w, v⟩ = a·⟨u, v⟩ + b·⟨w, v⟩
3) положительно:    ⟨v, v⟩ > 0 для любого v ≠ 0

Из него выводятся норма ||v|| = sqrt(⟨v, v⟩) и угол. Стандартное («евклидово») произведение в R^n — это sum(u_i * v_i), но оно не единственное: скажем, ⟨u, v⟩ = sum(w_i * u_i * v_i) с положительными весами тоже подходит и соответствует взвешенным метрикам, а ⟨f, g⟩ = ∫ f·g dx делает то же самое для функций (отсюда ряды Фурье как разложение по ортогональному базису).

Неравенство Коши–Буняковского–Шварца:

|⟨u, v⟩| <= ||u|| · ||v||

Именно оно гарантирует, что cos θ = ⟨u, v⟩ / (||u||·||v||) лежит в [-1, 1] и косинусная близость — корректная величина. Без него косинусный поиск не имел бы смысла.

Ортогональность: u ⊥ v, если ⟨u, v⟩ = 0. Ключевой факт: ненулевые попарно ортогональные векторы автоматически линейно независимы. Доказательство в одну строку: если sum a_i·v_i = 0, скалярно умножим на v_j — все члены кроме одного обнулятся, останется a_j·||v_j||² = 0, значит a_j = 0.

Отсюда практическая ценность ортонормированных базисов: координаты в них вычисляются проекцией, без решения системы:

если {q1..qn} ортонормирован, то  v = ⟨v,q1⟩·q1 + ... + ⟨v,qn⟩·qn

Стоимость падает с O(n^3) (решение системы) до O(n^2) (n скалярных произведений), и результат численно устойчив. Ровно поэтому в вычислениях везде стремятся к ортогональности: QR-разложение, DFT, вейвлеты, PCA.

Грам–Шмидт: как сделать базис ортонормированным

import numpy as np

def modified_gram_schmidt(vectors, tol=1e-12):
    """Модифицированный Грам–Шмидт: численно устойчивее классического.
    Время O(n·k^2), память O(n·k). Побочно даёт ранг набора."""
    Q = []
    for v in np.array(vectors, dtype=float):
        w = v.copy()
        for q in Q:                       # ключевое отличие MGS: вычитаем
            w -= np.dot(q, w) * q         # проекцию из УЖЕ обновлённого w
        nrm = np.linalg.norm(w)
        if nrm > tol * np.linalg.norm(v): # относительный порог, не абсолютный
            Q.append(w / nrm)
    return np.array(Q)

V = [[1, 1, 0], [1, 0, 1], [0, 1, 1]]
Q = modified_gram_schmidt(V)
print(Q.shape)                          # (3, 3) — ранг 3
print(np.round(Q @ Q.T, 12))            # единичная матрица: ортонормированность

Разница между классическим и модифицированным Грам–Шмидтом — одна строка кода и на порядки разная потеря ортогональности при плохо обусловленных данных. Классический вычитает проекции исходного v, модифицированный — последовательно обновляемого w. Численный анализ этого эффекта — у Trefethen & Bau, «Numerical Linear Algebra» (лекции 7–9). В продакшене для QR-разложения используют не Грам–Шмидта вовсе, а отражения Хаусхолдера (numpy.linalg.qr, LAPACK dgeqrf) — они устойчивы безусловно.

Где это всплывает в реальном коде

Пара примеров детальнее.

Мультиколлинеарность. Здесь теория ядра работает буквально. Возьмём признак, который точно выражается через два других:

import numpy as np

rng = np.random.default_rng(42)
n = 500
x1 = rng.normal(size=n)
x2 = rng.normal(size=n)
x3 = 2 * x1 - 0.5 * x2                       # ТОЧНО зависимый признак

X = np.column_stack([x1, x2, x3])
y = 3 * x1 + 2 * x2 + 0.1 * rng.normal(size=n)

s = np.linalg.svd(X, compute_uv=False)
print("сингулярные:", np.round(s, 4))        # [49.4291 22.6356 0.    ]
print("ранг:", np.linalg.matrix_rank(X))     # 2, а столбцов 3

# По rank-nullity: dim ker = 3 - 2 = 1. Вот это направление ядра:
d = np.array([2.0, -0.5, -1.0])
print("X @ d =", np.abs(X @ d).max())        # 0.0 — ровно ноль

w, *_ = np.linalg.lstsq(X, y, rcond=None)
for t in (0.0, 5.0, -100.0):
    wt = w + t * d
    print(np.round(wt, 3), "невязка:", round(np.linalg.norm(X @ wt - y), 6))

[1.096   2.474    0.955]  невязка: 2.276851
[11.096 -0.026   -4.045]  невязка: 2.276851
[-198.904 52.474 100.955] невязка: 2.276851

Три совершенно разных набора весов дают бит в бит одинаковое качество. Это не численная погрешность и не недоученность — задача просто не имеет единственного решения: любое смещение вдоль ядра невидимо для модели. Отсюда практическое следствие: интерпретировать коэффициенты при коллинеарных признаках нельзя — «важность» признака x1 тут не определена в принципе.

Хуже, когда зависимость не точная, а почти точная — тогда ранг формально полный, предупреждений нет, а решение уже мусор:

x3n = 2 * x1 - 0.5 * x2 + 1e-7 * rng.normal(size=n)   # почти зависимый
Xn = np.column_stack([x1, x2, x3n])
print("cond =", f"{np.linalg.cond(Xn):.3e}")          # 5.008e+07
print("ранг:", np.linalg.matrix_rank(Xn))             # 3 — формально полный!

def normal_eq(A, b):                                   # так делать НЕ надо
    return np.linalg.solve(A.T @ A, A.T @ b)

noise = 1e-9 * rng.normal(size=Xn.shape)               # возмущение в 9-м знаке
print("нормальные ур-я:", np.round(normal_eq(Xn, y), 1))
print("       и с шумом:", np.round(normal_eq(Xn + noise, y), 1))

нормальные ур-я: [ 33542.8  -8382.9 -16769.9]
       и с шумом: [ 32755.8  -8186.2 -16376.4]

Истинные веса — (3, 2, 0), а получили десятки тысяч, уезжающие на сотни от возмущения в девятом знаке. Причина известна точно: нормальные уравнения возводят обусловленность в квадрат (cond(AᵀA) = cond(A)²), и 5e7 превращается в 2.5e15 — на грани разрешающей способности float64.

Отдельная ловушка: наивная замена на lstsq тут не спасает. С параметром по умолчанию rcond=None порог отсечения сингулярных чисел берётся порядка машинного эпсилон, а наше s_min до него не дотягивает — и lstsq честно возвращает тот же мусор. Помогает только явное указание порога (или регуляризация):

for rcond in (None, 1e-6):
    a, *_ = np.linalg.lstsq(Xn, y, rcond=rcond)
    b, *_ = np.linalg.lstsq(Xn + noise, y, rcond=rcond)
    print(f"rcond={str(rcond):>5}:", np.round(a, 3), "->", np.round(b, 3))

rcond= None: [32806.355 -8198.841 -16401.675] -> [32127.962 -8029.243 -16062.478]
rcond=1e-06: [    1.096     2.474      0.955] -> [    1.096     2.474      0.955]

С порогом 1e-6 алгоритм отбрасывает почти нулевое сингулярное число, признаёт задачу вырожденной и возвращает решение минимальной нормы — устойчиво и воспроизводимо. Обратите внимание: это ровно тот же вектор [1.096, 2.474, 0.955], что и в точно вырожденном случае выше.

И главная честная оговорка: устойчивое решение — не значит истинное. Ни (3, 2, 0), ни [1.096, 2.474, 0.955] не «правильнее» другого; регуляризация лишь выбирает один конкретный элемент из целого множества равнохороших решений (по критерию минимальной нормы). Восстановить исходные веса невозможно в принципе — информация об этом направлении отсутствует в данных. Лечится это не выбором солвера, а работой с признаками: отбором, PCA или осознанной ридж-регуляризацией.

Схема разделения секрета Шамира. Секрет прячут в свободный член многочлена степени t-1 над конечным полем, а участникам раздают его значения в разных точках. Восстановить многочлен можно ровно тогда, когда набранных точек хватает: t точек дают независимую систему (матрица Вандермонда невырождена), t-1 — недоопределённую, где секрет остаётся равновероятным. Вся «магия» криптостойкости — это ровно утверждение о размерности пространства решений.

Типичные заблуждения

1. «Размерность — это длина массива». Нет. Три вектора в R^100 натягивают пространство размерности ≤ 3. И наоборот: пространство многочленов степени ≤ 3 имеет размерность 4, хотя «выглядит» как функции. Размерность — свойство пространства, а не представления.
2. «Зависимые = пропорциональные». Пропорциональность — только частный случай для двух векторов. (1,0), (0,1), (1,1) — попарно непропорциональны, но набор зависим.
3. «Любые n векторов в R^n образуют базис». Только если независимы. Зато верно ослабленное: n независимых векторов в n-мерном пространстве автоматически порождают его — проверять span отдельно не нужно. Это экономит половину работы.
4. «Ортогональность = независимость». Импликация только в одну сторону. (1,0) и (1,1) независимы, но не ортогональны.
5. «det == 0 надёжно ловит вырожденность». Численно — нет, см. выше. Используйте numpy.linalg.matrix_rank (внутри SVD с разумным порогом) или явно смотрите на сингулярные числа.
6. «Нормировать эмбеддинги можно один раз». После любого усреднения/сложения нормировку надо повторять: сфера не замкнута относительно сложения.
7. «Ноль-вектор может входить в независимый набор». Никогда: 1·0 = 0 — уже нетривиальная комбинация. Любой набор, содержащий ноль, зависим.
8. «Базис единственен». Их бесконечно много (при бесконечном поле). Единственна только размерность. Весь смысл PCA, вейвлетов и Фурье — в выборе удобного базиса под задачу.

Trade-offs: какой базис выбирать на практике

Последняя строка важна: иногда единственность разложения сознательно приносят в жертву ради разреженности. Это осознанный отказ от базиса в пользу переполненной системы — область compressed sensing (обзор: Candès & Wakin, https://arxiv.org/abs/0803.0131).

Мини-итог

• Вектор — элемент множества с восемью аксиомами; массив чисел лишь одно из представлений.
• span — всё, что достижимо комбинациями; это всегда подпространство и всегда проходит через ноль.
• Линейная независимость = отсутствие избыточности = единственность разложения. Она зависит от поля скаляров.
• Базис — минимальный порождающий набор; его размер (размерность) одинаков для всех базисов данного пространства.
• Координаты бессмысленны без указания базиса; смена базиса — это решение системы или умножение на матрицу перехода.
• Скалярное произведение — дополнительная структура, дающая длину, угол и ортогональность; ортонормированные базисы превращают O(n^3) в O(n^2) и стабилизируют вычисления.
• В численном коде судите о независимости по сингулярным числам и относительным порогам, а не по определителю.

Источники

• Sheldon Axler. Linear Algebra Done Right, 4-е изд. — свободно доступна: https://linear.axler.net/. Лучшее строгое изложение без матричной перегрузки.
• Gilbert Strang. Introduction to Linear Algebra и курс MIT 18.06: https://ocw.mit.edu/courses/18-06-linear-algebra-spring-2010/. Ортогональный по духу источник: всё через матрицы и приложения.
• Trefethen, Bau. Numerical Linear Algebra, SIAM, 1997. Про то, что происходит с этой теорией в арифметике с плавающей точкой.
• Golub, Van Loan. Matrix Computations, 4-е изд. — справочник по алгоритмам и их устойчивости.
• 3Blue1Brown. Essence of Linear Algebra: https://www.3blue1brown.com/topics/linear-algebra — геометрическая интуиция для span и базисов.
• Документация NumPy: https://numpy.org/doc/stable/reference/routines.linalg.html, в частности matrix_rank, lstsq, qr.
• LAPACK Users’ Guide: https://www.netlib.org/lapack/lug/ — что на самом деле вызывается под капотом numpy/scipy.
• Boyd, Vandenberghe. Introduction to Applied Linear Algebra (VMLS): https://web.stanford.edu/~boyd/vmls/ — свободная книга, ориентированная на прикладные задачи и код.

Соседние темы трека: язык доказательств, которым мы пользовались («тогда и только тогда», «от противного»), разобран в статье Математическая логика и доказательства; поля скаляров и почему GF(2) ведёт себя иначе — в статье Абстрактная алгебра; а прикладная сторона эмбеддингов и PCA — в треке Машинное обучение.

Что дальше

Мы построили пространство и научились задавать в нём систему координат. Следующий шаг — научиться преобразовывать его: линейные отображения, их матричные представления, определитель как коэффициент растяжения объёма и решение систем уравнений.

Читайте дальше: Матрицы, линейные отображения, определители и системы уравнений.