线性基学习笔记

发布于 2019-03-09  213 次阅读


本文使用符号 $\vec{a_i}$ 来表示向量。

定义

是线性代数中的一个概念,它是描述,刻画线性空间的一个工具。在 OI 中经常和异或运算扯上关系。

前置芝士

向量空间

向量空间 - 维基百科
定义 $(F,V,+,\cdot)$ 为向量空间,其中 $F$ 为域,$V$ 是向量,$+$ 是向量乘法,$\cdot$ 是标量乘法,并且运算满足 8 条公理。(摘自维基百科)

线性无关

线性无关 - 维基百科
在线性代数里,向量空间的一组元素中,若没有向量可用有限个其他向量的线性组合所表示,则称为线性无关或线性独立(linearly independent),反之称为线性相关(linearly dependent)。
用数学一点的语言来表示:
对于向量空间中 $V$ 上 $n$ 个元素的向量组 ${(\vec{v_1},\cdots,\vec{v_n})}$,若存在不全为 $0$ 的数 $a_i \in F$,满足
$$\sum_{i=1}^n a_i \vec{v_i} = 0$$。
则称这 $n$ 个向量线性相关,否则称为线性无关。

线性组合

就是上面表示线性相关的式子中的 $\sum_{i=1}^n a_i \vec{v_i}$ 了。
显然一组向量线性无关等价于没有向量可以用有限个其他向量的线性组合所表示。

张成

对于向量空间上 $V$ 上 $n$ 个元素的向量组 ${\vec{v_1},\vec{v_2},\cdots,\vec{v_n}}$,其所有线性组合构成的集合称为它们的张成,记为 $\text{span}({\vec{v_1},\vec{v_2},\cdots,\vec{v_n}})$。

基(线性代数)
向量空间 $V$ 中一个向量组 $B$ 既是线性无关的又可以张成 $V$ 则称该向量组 $B$ 是 $V$ 的基。$B$ 中的元素称为基向量。如果基中元素个数有限,就称向量空间为有限向量空间,将元素的个数称为向量空间的维数。

性质

设 $B$ 是向量空间 $V$ 的基,则其有如下性质:
1. $V$ 是 $B$ 的极小生成集。
2. $B$ 是 $V$ 中线性无关向量的极大几何。
3. $V$ 中的所有向量都可以按照唯一的方式表达为 $B$ 中向量的线性组合。

线性相关性引理

如果 ${(\vec{v_1},\vec{v_2},\cdots,\vec{v_n})}$ 在 $V$ 中是线性相关的,并且 $\vec{v_1} \neq 0$,则有至少一个 $j \in {2,\cdots,m}$ 使得下列成立:
1. $\vec{v_j} \in \text{span}(\vec{v_1},\cdots,\vec{v_{j-1}})$
2. 如果从 ${(\vec{v_1},\cdots,\vec{v_n})}$ 中去掉第 $j$ 项,则剩余向量组的张成仍然等于 $\text{span}({\vec{v_1},\cdots,\vec{v_n}})$

证明:
设 $(\vec{v_1},\cdots,\vec{v_n})$ 在 $V$ 中是线性相关的,并且 $\vec{v_1} \neq 0$,则有不全为 $0$ 的 $a_1,\cdots,a_n \in F$,使得
$$\sum_{i=1}^m a_i\vec{v_i} = 0$$
$a_2,a_3,\cdots,a_n$ 不会全为 $0$(因为 $\vec{v_1} \neq 0$(因为 $\vec{v_1} \neq 0$)。设 $j$ 是 ${2,\cdots,m}$ 中使得 $a_j \neq 0$ 的最大者,那么
$$\vec{v_j} = -\frac{a_1}{a_j} \vec{v_1} - \cdots - \frac{a_{j-1}}{a_j} \vec{v_{j-1}}$$
这就有 $(1)$ 成立。
为了证明 $(2)$ 设 $\vec{u} \in \text{span} (\vec{v_1},\cdots,\vec{v_n})$,则存在 $c_1,\cdots,c_n \in F$,使得
$$\vec{u} = \sum_{i=1}^n c_i\vec{v_i}$$
在上面的等式中,可以用之前的等式右边来代替 $\vec{v_j}$。这样 $\vec{u}$ 包含于从 $(\vec{v_0},\cdots,\vec{v_n})$ 去掉第 $j$ 项的张成,因此 $(2)$ 成立。
(以上主要来自于 SengXian's Blog

OI 中的线性基

我们将一个数 $x$ 的二进制表示为 $(\vec{b_m},\cdots,\vec{b_0}) _ 2$ 看做一个向量。

我们的目标就是对于这样的向量组成的向量组求出一个基,这样它就会有一些很好的性质。
那我们考虑如何求出这样的一组基。
我们发现高斯消元时,如果某一行被前面的行消为 $0$ ,那么代表它可以表示成前面的线性组合。也可以得到结论:
方程组有解、系数矩阵行列式不为 $0$、系数矩阵满秩、系数矩阵的线性无关集合大小为 $n$ ——这四个命题等价。
对于新加入的数 $x$,如果它能被表示为 $R$ ,就代表他能被 $R$ 消成 $0$。
我们把高位写左边,低位写右边,对所有数做高斯消元,最终得到的不为 $0$ 的向量就是基,并且每个向量的最高位不同。
具体过程是在插入一个新的向量时,如果能与已有的元素相消就消,否则就插入到当前位置。
题目链接
求最大值直接从高位贪心即可。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define Re register
#define LL long long
#define U unsigned
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define SFOR(i,a,b,c) for(Re int i = a;i <= b;i+=c)
#define SROF(i,a,b,c) for(Re int i = a;i >= b;i-=c)
#define CLR(i,a) memset(i,a,sizeof(i))
#define BR printf("--------------------\n")
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
//#define int LL
const int MAXN = 50+5;
LL a[MAXN],b[MAXN*100],n,base=62;

inline void Gauss(){
    FOR(i,1,n){
        LL x = a[i];
        ROF(j,base,0){
            if((x>>j)&1){
                if(b[j]) x ^= b[j];
                else {b[j] = x;break;}
            }
        }
    }
}
LL ans = 0;
int main(){
    scanf("%lld",&n);
    FOR(i,1,n) scanf("%lld",a+i);
    Gauss();
    ROF(i,base,0) ans = std::max(ans,ans^b[i]);
    printf("%lld\n",ans);
    return 0;
}

一个OIer。