🧮 Линейна алгебра: Базиси, ранг и линейни системи
Линейната алгебра е фундаментален математически инструмент в състезателното програмиране, особено при работа със системи от уравнения, матрични операции и оптимизационни задачи. Макар пълната дълбочина на линейната алгебра рядко да е необходима в състезания, разбирането на ключови концепции като ранг на матрица, линейна независимост, гаусова елиминация и XOR базис е от решаващо значение за решаването на усложнени задачи.
Тази тема обхваща съществените концепции от линейната алгебра, които се появяват в състезателното програмиране: - Ранг на матрица и линейна независимост - Гаусова елиминация за решаване на линейни системи - XOR базис като специален случай на гаусова елиминация - Детерминанти и техните приложения - Практични имплементации и оптимизации
📚 Основни концепции
Линейна независимост и зависимост
Множество от вектори (или редове/колони в матрица) е линейно независимо, ако никой вектор не може да бъде изразен като линейна комбинация от останалите.
Пример:
// Векторите v1 = [1, 2], v2 = [2, 4] са линейно зависими
// защото v2 = 2 * v1
// Векторите v1 = [1, 2], v2 = [3, 5] са линейно независими
// защото нито един не може да бъде изразен като скаларно умножение на другия
Ключови свойства: - Ако векторите са линейно зависими, един може да бъде премахнат без загуба на информация - Максималният брой линейно независими вектори в \(\mathbb{R}^n\) е \(n\) - Линейната независимост е ключова за определянето на ранга на матрицата
Векторни пространства и обхват
Обхватът на множество вектори е всички възможни линейни комбинации на тези вектори.
// Пример: Обхватът на {[1,0], [0,1]} е цялото 2D пространство R^2
// Обхватът на {[1,2], [2,4]} е само права (защото са зависими)
Базис е минимално множество от линейно независими вектори, които обхващат пространство.
🎹 Ранг на матрица
Рангът на матрица е едно от най-важните ѝ свойства, представляващо максималния брой линейно независими редове (или еквивалентно, колони).
Дефиниция и свойства
Рангът може да бъде дефиниран по няколко еквивалентни начина: 1. Брой линейно независими редове 2. Брой линейно независими колони 3. Размерност на пространството на колоните (или редовете) 4. Размер на най-големия ненулев минор (детерминанта на подматрица) 5. Брой ненулеви редове след гаусова елиминация
Ключови свойства: - \(\text{rank}(A) \leq \min(\text{редове}, \text{колони})\) - \(\text{rank}(A) = \text{rank}(A^T)\) (транспонираната има същия ранг) - \(\text{rank}(AB) \leq \min(\text{rank}(A), \text{rank}(B))\) - Пълен ранг: рангът е равен на по-малката размерност (обратима ако е квадратна)
Изчисляване на ранг чрез гаусова елиминация
Стандартният метод за изчисляване на ранг е гаусовата елиминация:
#include <bits/stdc++.h>
using namespace std;
const double EPS = 1e-9;
int computeRank(vector<vector<double>>& matrix) {
int n = matrix.size(); // редове
int m = matrix[0].size(); // колони
int rank = 0;
for (int col = 0; col < m && rank < n; col++) {
// Намери пивот (най-голяма абсолютна стойност за числена стабилност)
int pivot_row = rank;
for (int i = rank + 1; i < n; i++) {
if (abs(matrix[i][col]) > abs(matrix[pivot_row][col])) {
pivot_row = i;
}
}
// Ако колоната е цяла от нули, пропусни я
if (abs(matrix[pivot_row][col]) < EPS) {
continue;
}
// Размени текущия ред с пивот реда
swap(matrix[rank], matrix[pivot_row]);
// Елиминирай колоната под пивота
for (int i = rank + 1; i < n; i++) {
double factor = matrix[i][col] / matrix[rank][col];
for (int j = col; j < m; j++) {
matrix[i][j] -= factor * matrix[rank][j];
}
}
rank++;
}
return rank;
}
int main() {
// Пример: 3x4 матрица
vector<vector<double>> A = {
{1, 2, 3, 4},
{2, 4, 6, 8}, // Този ред е 2 * ред 1 (зависим)
{1, 3, 5, 7}
};
cout << "Ранг: " << computeRank(A) << "\n"; // Изход: 2
return 0;
}
Времева сложност: \(O(\min(n,m) \cdot n \cdot m) = O(n^2 m)\) за \(n \times m\) матрица
Приложения на ранга на матрица
1. Определяне на съществуването на решение
За система \(Ax = b\): - Уникално решение: \(\text{rank}(A) = \text{rank}([A|b]) = n\) (брой неизвестни) - Безброй решения: \(\text{rank}(A) = \text{rank}([A|b]) < n\) - Няма решение: \(\text{rank}(A) \neq \text{rank}([A|b])\)
bool hasUniqueSolution(vector<vector<double>>& A, vector<double>& b) {
int n = A.size();
int m = A[0].size();
// Създай разширена матрица [A|b]
vector<vector<double>> augmented(n, vector<double>(m + 1));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
augmented[i][j] = A[i][j];
}
augmented[i][m] = b[i];
}
int rank_A = computeRank(A);
int rank_Aug = computeRank(augmented);
if (rank_A != rank_Aug) {
return false; // Няма решение
}
return rank_A == m; // Уникално ако рангът е равен на броя променливи
}
2. Намиране на независимо подмножество
// Намери максимално линейно независимо подмножество от редове
vector<int> findIndependentRows(vector<vector<double>>& matrix) {
int n = matrix.size();
int m = matrix[0].size();
vector<int> independent_rows;
vector<vector<double>> selected;
for (int i = 0; i < n; i++) {
selected.push_back(matrix[i]);
int new_rank = computeRank(selected);
if (new_rank > independent_rows.size()) {
independent_rows.push_back(i);
} else {
selected.pop_back(); // Този ред е зависим
}
}
return independent_rows;
}
🔧 Гаусова елиминация
Гаусовата елиминация е фундаменталният алгоритъм за решаване на линейни системи \(Ax = b\).
Стандартна гаусова елиминация
vector<double> gaussianElimination(vector<vector<double>> A, vector<double> b) {
int n = A.size();
// Предна елиминация
for (int col = 0; col < n; col++) {
// Намери пивот
int pivot_row = col;
for (int i = col + 1; i < n; i++) {
if (abs(A[i][col]) > abs(A[pivot_row][col])) {
pivot_row = i;
}
}
// Провери дали матрицата е сингулярна
if (abs(A[pivot_row][col]) < EPS) {
cout << "Не съществува уникално решение\n";
return {};
}
// Размени редове
swap(A[col], A[pivot_row]);
swap(b[col], b[pivot_row]);
// Елиминирай
for (int i = col + 1; i < n; i++) {
double factor = A[i][col] / A[col][col];
b[i] -= factor * b[col];
for (int j = col; j < n; j++) {
A[i][j] -= factor * A[col][j];
}
}
}
// Обратна замяна
vector<double> x(n);
for (int i = n - 1; i >= 0; i--) {
x[i] = b[i];
for (int j = i + 1; j < n; j++) {
x[i] -= A[i][j] * x[j];
}
x[i] /= A[i][i];
}
return x;
}
int main() {
// Пример: Реши система
// x + 2y + 3z = 14
// 2x + 5y + 8z = 35
// 3x + 8y + 14z = 58
vector<vector<double>> A = {
{1, 2, 3},
{2, 5, 8},
{3, 8, 14}
};
vector<double> b = {14, 35, 58};
vector<double> solution = gaussianElimination(A, b);
cout << "Решение: ";
for (double x : solution) {
cout << x << " ";
}
cout << "\n"; // Изход: 1 2 3
return 0;
}
Времева сложност: \(O(n^3)\) за \(n \times n\) система
Гаус-Джордан елиминация (редуцирана редово стъпаловидна форма)
Гаус-Джордан отива по-далеч, за да произведе редуцирана редово стъпаловидна форма (RREF):
void gaussJordan(vector<vector<double>>& A, vector<double>& b) {
int n = A.size();
for (int col = 0; col < n; col++) {
// Намери пивот
int pivot = col;
for (int i = col + 1; i < n; i++) {
if (abs(A[i][col]) > abs(A[pivot][col])) {
pivot = i;
}
}
if (abs(A[pivot][col]) < EPS) continue;
swap(A[col], A[pivot]);
swap(b[col], b[pivot]);
// Нормализирай пивот реда
double divisor = A[col][col];
for (int j = 0; j < n; j++) {
A[col][j] /= divisor;
}
b[col] /= divisor;
// Елиминирай колоната във ВСИЧКИ други редове (не само под)
for (int i = 0; i < n; i++) {
if (i == col) continue;
double factor = A[i][col];
for (int j = 0; j < n; j++) {
A[i][j] -= factor * A[col][j];
}
b[i] -= factor * b[col];
}
}
// Решението вече е директно във вектора b
}
Предимство: Решението е директно налично без обратна замяна
Целочислена гаусова елиминация
За задачи с целочислени коефициенти можем да използваме модулна аритметика:
const long long MOD = 1e9 + 7;
long long modInv(long long a, long long mod) {
// Разширен алгоритъм на Евклид
long long m0 = mod, x0 = 0, x1 = 1;
while (a > 1) {
long long q = a / mod;
long long t = mod;
mod = a % mod;
a = t;
t = x0;
x0 = x1 - q * x0;
x1 = t;
}
return (x1 % m0 + m0) % m0;
}
vector<long long> gaussianEliminationMod(vector<vector<long long>> A,
vector<long long> b) {
int n = A.size();
for (int col = 0; col < n; col++) {
// Намери ненулев пивот
int pivot = -1;
for (int i = col; i < n; i++) {
if (A[i][col] % MOD != 0) {
pivot = i;
break;
}
}
if (pivot == -1) continue;
swap(A[col], A[pivot]);
swap(b[col], b[pivot]);
long long inv = modInv(A[col][col], MOD);
// Елиминирай
for (int i = col + 1; i < n; i++) {
long long factor = (A[i][col] * inv) % MOD;
b[i] = ((b[i] - factor * b[col]) % MOD + MOD) % MOD;
for (int j = col; j < n; j++) {
A[i][j] = ((A[i][j] - factor * A[col][j]) % MOD + MOD) % MOD;
}
}
}
// Обратна замяна (подобно, но с модулна аритметика)
vector<long long> x(n);
for (int i = n - 1; i >= 0; i--) {
x[i] = b[i];
for (int j = i + 1; j < n; j++) {
x[i] = ((x[i] - A[i][j] * x[j]) % MOD + MOD) % MOD;
}
x[i] = (x[i] * modInv(A[i][i], MOD)) % MOD;
}
return x;
}
⊕ XOR базис като гаусова елиминация
XOR базисът (от Тема 22 - Побитови операции) всъщност е специален случай на гаусова елиминация над \(GF(2)\) (полето с два елемента: 0 и 1).
Разбиране на XOR като линейна алгебра
В \(GF(2)\): - Събирането е XOR: \(1 + 1 = 0\), \(1 + 0 = 1\) - Умножението е AND: \(1 \cdot 1 = 1\), \(1 \cdot 0 = 0\)
Всяко число може да се разглежда като вектор от битове:
XOR е векторно събиране в \(GF(2)\):
Конструиране на XOR базис
struct XORBasis {
static const int MAXLOG = 60; // За 64-битови цели числа
long long basis[MAXLOG];
int size;
XORBasis() {
memset(basis, 0, sizeof(basis));
size = 0;
}
// Вмъкни число в базиса (гаусова елиминация)
bool insert(long long x) {
for (int i = MAXLOG - 1; i >= 0; i--) {
if ((x & (1LL << i)) == 0) continue;
if (basis[i] == 0) {
basis[i] = x;
size++;
return true; // x е линейно независимо
}
x ^= basis[i]; // Елиминирай бит i
}
return false; // x е линейно зависимо
}
// Провери дали стойността може да бъде представена
bool canRepresent(long long x) {
for (int i = MAXLOG - 1; i >= 0; i--) {
if ((x & (1LL << i)) == 0) continue;
if (basis[i] == 0) return false;
x ^= basis[i];
}
return x == 0;
}
// Вземи максимална XOR стойност
long long getMax() {
long long result = 0;
for (int i = MAXLOG - 1; i >= 0; i--) {
result = max(result, result ^ basis[i]);
}
return result;
}
// Вземи минимална XOR стойност
long long getMin() {
for (int i = 0; i < MAXLOG; i++) {
if (basis[i] != 0) return basis[i];
}
return 0;
}
// Брой различни XOR стойности възможни
long long countDistinct() {
return (1LL << size);
}
};
int main() {
XORBasis basis;
vector<long long> numbers = {3, 5, 7, 10};
// Двоично: 0011, 0101, 0111, 1010
for (long long x : numbers) {
basis.insert(x);
}
cout << "Размер на базиса: " << basis.size << "\n";
cout << "Макс XOR: " << basis.getMax() << "\n";
cout << "Различни стойности: " << basis.countDistinct() << "\n";
return 0;
}
Защо е гаусова елиминация
Конструирането на XOR базис е точно гаусова елиминация:
- Избор на пивот: Избери най-високата битова позиция
- Редово стъпаловидна форма: Всеки базисен елемент има уникален най-висок бит
- Линейна зависимост: Ако можем да редуцираме число до 0, то е зависимо
- Базис: Ненулевите редове образуват базис за векторното пространство
Матричен изглед:
Числа: 13, 7, 10, 5
Двоична матрица:
1 1 0 1 (13)
0 1 1 1 (7)
1 0 1 0 (10)
0 1 0 1 (5)
След гаусова елиминация над GF(2):
1 1 0 1 (13)
0 1 1 1 (7)
0 0 1 1 (XOR резултат)
0 0 0 0 (зависим)
Базис: {13, 7, нещо}
Приложения на XOR базис
1. Максимален XOR подмасив
long long maxXORSubarray(vector<long long>& arr) {
XORBasis basis;
long long prefix_xor = 0;
basis.insert(0); // Празен подмасив
for (long long x : arr) {
prefix_xor ^= x;
basis.insert(prefix_xor);
}
return basis.getMax();
}
2. Брой различни XOR стойности
// Брой различни XOR стойности от подмножество на масив
long long countDistinctXOR(vector<long long>& arr) {
XORBasis basis;
for (long long x : arr) {
basis.insert(x);
}
return basis.countDistinct();
}
3. Проверка за XOR достижимост
// Можем ли да получим целева XOR стойност от някое подмножество?
bool canGetXOR(vector<long long>& arr, long long target) {
XORBasis basis;
for (long long x : arr) {
basis.insert(x);
}
return basis.canRepresent(target);
}
🔍 Детерминанти
Детерминантата е скаларна стойност, която кодира важни свойства на квадратна матрица.
Свойства и значение
- \(\det(I) = 1\) (единична матрица)
- \(\det(AB) = \det(A) \cdot \det(B)\)
- \(\det(A^T) = \det(A)\)
- \(\det(A) \neq 0 \iff\) матрицата е обратима
- \(|\det(A)|\) е фактор на мащабиране на обема на линейното преобразование
Изчисляване на детерминанта чрез гаусова елиминация
double determinant(vector<vector<double>> A) {
int n = A.size();
double det = 1.0;
for (int i = 0; i < n; i++) {
// Намери пивот
int pivot = i;
for (int j = i + 1; j < n; j++) {
if (abs(A[j][i]) > abs(A[pivot][i])) {
pivot = j;
}
}
if (abs(A[pivot][i]) < EPS) {
return 0; // Сингулярна матрица
}
if (pivot != i) {
swap(A[i], A[pivot]);
det *= -1; // Размяната на редове променя знака
}
det *= A[i][i];
// Елиминирай
for (int j = i + 1; j < n; j++) {
double factor = A[j][i] / A[i][i];
for (int k = i; k < n; k++) {
A[j][k] -= factor * A[i][k];
}
}
}
return det;
}
Времева сложност: \(O(n^3)\)
Детерминанта по модул просто число
long long determinantMod(vector<vector<long long>> A, long long mod) {
int n = A.size();
long long det = 1;
for (int i = 0; i < n; i++) {
int pivot = -1;
for (int j = i; j < n; j++) {
if (A[j][i] % mod != 0) {
pivot = j;
break;
}
}
if (pivot == -1) return 0;
if (pivot != i) {
swap(A[i], A[pivot]);
det = (mod - det) % mod;
}
det = (det * A[i][i]) % mod;
long long inv = modInv(A[i][i], mod);
for (int j = i + 1; j < n; j++) {
long long factor = (A[j][i] * inv) % mod;
for (int k = i; k < n; k++) {
A[j][k] = ((A[j][k] - factor * A[i][k]) % mod + mod) % mod;
}
}
}
return det;
}
💡 Практични съвети и оптимизации
Числена стабилност
// Използвайте частичен избор на пивот, за да избегнете деление на малки числа
int findPivot(vector<vector<double>>& A, int col, int start) {
int pivot = start;
double max_val = abs(A[start][col]);
for (int i = start + 1; i < A.size(); i++) {
if (abs(A[i][col]) > max_val) {
max_val = abs(A[i][col]);
pivot = i;
}
}
return pivot;
}
Оптимизация на паметта
// За много големи системи използвайте представяне на разредена матрица
struct SparseMatrix {
map<pair<int,int>, double> entries;
int rows, cols;
double get(int i, int j) {
auto it = entries.find({i, j});
return (it == entries.end()) ? 0.0 : it->second;
}
void set(int i, int j, double val) {
if (abs(val) > EPS) {
entries[{i, j}] = val;
} else {
entries.erase({i, j});
}
}
};
Оптимизация с bitset за GF(2)
// За двоични матрици използвайте bitset за 64x ускорение
const int MAXN = 2000;
bitset<MAXN> matrix[MAXN];
int gaussianEliminationBinary(int n, int m) {
int rank = 0;
for (int col = 0; col < m && rank < n; col++) {
int pivot = -1;
for (int i = rank; i < n; i++) {
if (matrix[i][col]) {
pivot = i;
break;
}
}
if (pivot == -1) continue;
swap(matrix[rank], matrix[pivot]);
for (int i = 0; i < n; i++) {
if (i != rank && matrix[i][col]) {
matrix[i] ^= matrix[rank]; // XOR цели редове наведнъж!
}
}
rank++;
}
return rank;
}
🎯 Често срещани задачи и решения
Задача 1: Проверка за линейна независимост
bool areIndependent(vector<vector<double>>& vectors) {
// Ако рангът е равен на броя вектори, те са независими
return computeRank(vectors) == vectors.size();
}
Задача 2: Намиране на всички решения
// Върни параметрична форма на всички решения на Ax = b
struct Solution {
vector<double> particular; // Едно конкретно решение
vector<vector<double>> null_space; // Базис за нулевото пространство
};
Задача 3: Обръщане на матрица
vector<vector<double>> invert(vector<vector<double>> A) {
int n = A.size();
vector<vector<double>> inv(n, vector<double>(n));
// Създай разширена матрица [A | I]
for (int i = 0; i < n; i++) {
inv[i][i] = 1;
}
// Приложи Гаус-Джордан към двете страни
// ... (подобно на gaussJordan, но работи върху A и inv)
return inv;
}
🏁 Заключение
Линейната алгебра в състезателното програмиране се фокусира върху практични алгоритмични техники:
Ключови изводи:
- Ранг на матрица: Основна мярка за линейна независимост
- Изчислява се чрез гаусова елиминация в \(O(n^3)\)
-
Определя съществуването и уникалността на решението
-
Гаусова елиминация: Основен алгоритъм за линейни системи
- Предна елиминация + обратна замяна
-
Работи с плаваща точка, цели числа по модул p или двоични
-
XOR базис: Специален случай над \(GF(2)\)
- Гаусова елиминация върху битови вектори
-
Приложения: макс XOR, различни XOR стойности, достижимост
-
Детерминанти: Кодират обратимост и обем
- Изчисляват се по време на гаусова елиминация
- Полезни за обръщане на матрици и изчисляване на площи
Обобщение на сложността:
| Операция | Времева сложност | Памет |
|---|---|---|
| Гаусова елиминация | \(O(n^3)\) | \(O(n^2)\) |
| Ранг на матрица | \(O(n^2 m)\) | \(O(nm)\) |
| Детерминанта | \(O(n^3)\) | \(O(n^2)\) |
| XOR базис вмъкване | \(O(\log \max(x))\) | \(O(\log \max(x))\) |
| XOR базис заявка | \(O(\log \max(x))\) | \(O(\log \max(x))\) |
Често срещани състезателни шаблони:
- ДП с матрично степенуване (обхванато в други теми)
- XOR базис за задачи с XOR подмножества
- Гаусова елиминация по модул p за линейни рекурсии
- Детерминанта за броене на обхващащи дървета (теорема Matrix-Tree)
В състезания "Линейна алгебра" рядко означава собствени стойности, собствени вектори или SVD. Почти винаги означава: - Матрично умножение за ДП - Гаусова елиминация за линейни системи - XOR базис за побитови задачи - Прости изчисления на детерминанти
Овладейте тези основни техники и ще бъдете добре подготвени да се справяте със задачи по линейна алгебра в състезателното програмиране!