数代数

线性空间与线性基

字数统计: 1.4k字   |   阅读时长: 5分
,

摘要: 本文介绍线性基的算法原理和代码模板。

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 高斯消元与线性方程组 中，我们学习了高斯消元的原理和代码模板。有了高斯消元算法的基础，本文我们看一下线性空间的概念，线性空间的极大线性无关线组称为线性基，通过高斯消元我们可以求出线性空间的秩和线性基。最后通过一道题，给出使用高斯消元求矩阵的秩和线性基的代码模板。

线性空间的知识点

线性空间是关于以下两种运算封闭的向量集合。

  1. $\vec{a} + \vec{b}$
  2. $k \cdot \vec{a}$

给定若干向量，$\vec{a_{1}}, \vec{a_{2}}, …, \vec{a_{k}}$，若向量 $\vec{b}$ 能够由 $\vec{a_{1}}, \vec{a_{2}}, …, \vec{a_{k}}$ 经过向量加法和标量乘法运算得出，称向量 $\vec{b}$ 可以由向量 $\vec{a_{1}}, \vec{a_{2}}, …, \vec{a_{k}}$ 表出。

线性空间的生成子集

$\vec{a_{1}}, \vec{a_{2}}, …, \vec{a_{k}}$ 能表出的所有向量构成一个线性空间，$\vec{a_{1}}, \vec{a_{2}}, …, \vec{a_{k}}$ 称为该线性空间的生成子集。

线性相关与线性无关

任意选出线性空间的若干向量，如果其中存在一个向量能被其它向量表出，则称这些向量线性相关，否则线性无关。

线性空间的基

定义1: 线性无关的生成子集称为线性空间的基。

定义2: 线性空间的极大线性无关子集。

线性空间的维数

一个线性空间的所有基的向量个数都相等，该数称为线性空间的基。

矩阵的秩

$N \times M$ 的矩阵，N 个行向量能够表出的所有向量构成行空间，该空间的维数称为行秩。类似地有列空间和列秩。

矩阵的行秩等于列秩，称为矩阵的秩。

矩阵的基

简化阶梯形矩阵的所有非零行向量线性无关，构成行空间的基。

题目

脸哥最近在玩一款神奇的游戏，这个游戏里有 n 件装备，每件装备有 m 个属性，用向量z[i]=(ai,1,ai,2,..,ai,m) 表示，每个装备需要花费 ci。

现在脸哥想买一些装备，但是脸哥很穷，所以总是盘算着怎样才能花尽量少的钱买尽量多的装备。

对于脸哥来说，如果一件装备的属性能用购买的其他装备组合出（也就是说脸哥可以利用手上的这些装备组合出这件装备的效果），那么这件装备就没有买的必要了。

严格的定义是，如果脸哥买了 z[i1],z[i2],…,z[ip]这 p 件装备，并且不存在实数 b1,b2,…,bp 使得z[k]=b1z[i1]+b2z[i2]+…+bpz[ip]，那么脸哥就会买z[k]，否则 z[k]对脸哥就是无用的了，自然不必购买。

脸哥想要在买下最多数量的装备的情况下花最少的钱，你能帮他算一下吗？

分析

基的向量个数 — 高斯消元求矩阵的秩

1
2
z[i][j] := 第 i 件装备的第 j 种属性
cost[i] := 第 i 件装备的花费

每个装备对应一个向量，即 z[i]。购买的装备是线性无关的。求可以买下的最多的装备组合，相当于求 n 个向量表出的线性空间的基。

矩阵 z 的秩就是线性空间的维度，也就是基的向量个数。

花费最少的基 — 贪心

贪心策略：在高斯消元过程中，对于每个主元 x[i]，在前 i - 1 列为 0, 第 i 列不为零的行向量中，选择价格最低的一个，消去其它行中第 i 列的值。

代码 (C++) (模板：高斯消元求矩阵的秩)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

const double EPS = 1e-8;

// const int N = 520;
// long double z[N][N];
// int cost[N];

int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<long double>> z(n + 1, vector<long double>(m + 1));
    // z[i][j] := 第 i 件装备的第 j 个属性
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
        {
            double x;
            scanf("%lf",&x);
            z[i][j] = x;
        }
    }
    vector<int> cost(n + 1);
    for(int i = 1; i <= n; ++i)
    {
        int x;
        scanf("%d", &x);
        cost[i] = x;
    }

    int dim = 0;
    int ans = 0;
    for(int i = 1; i <= m; ++i)
    {
        // 考虑元 x[i]
        int choose_j = -1;
        for(int j = dim + 1; j <= n; ++j)
        {
            if(fabs(z[j][i]) > EPS)
            {
                if((choose_j == -1 || cost[j] < cost[choose_j]))
                    choose_j = j;
            }
        }

        if(choose_j == -1)
            continue; // x[i] 为自由元

        ++dim; // x[i] 为主元
        ans += cost[choose_j];

        for(int k = 1; k <= m; ++k)
            swap(z[choose_j][k], z[dim][k]);
        swap(cost[choose_j],cost[dim]);

        // 消元 x[dim]
        for(int j = 1; j <= n; ++j)
        {
            if(j == dim) continue;
            if(fabs(z[j][i]) > EPS)
            {
                long double rate = z[j][i] / z[dim][i];
                for(int k = i; k <= m; ++k)
                    z[j][k] -= rate * z[dim][k];
            }
        }
    }

    cout << dim << " " << ans << endl;
}
Share