问题标题: 酷町堂：线性基

基本信息

• 中文名称

  线性基

目录

1定义

2性质

3应用

折叠编辑本段定义

基:在线性代数中，基(也称为基底)是描述、刻画向量空间的基本工具。向量空间的基是它的一个特殊的子集，基的元素称为基向量。向量空间中任意一个元素，都可以唯一地表示成基向量的线性组合。如果基中元素个数有限，就称向量空间为有限维向量空间，将元素的个数称作向量空间的维数。

同样的，线性基是一种特殊的基，它通常会在异或运算中出现，它的意义是:通过原集合S的某一个最小子集S1使得S1内元素相互异或得到的值域与原集合S相互异或得到的值域相同。

折叠编辑本段性质

1. 线性基能相互异或得到原集合的所有相互异或得到的值。
2. 线性基是满足性质1的最小的集合
3. 线性基没有异或和为0的子集。

证明:

反证法:设线性基S={a1,a2...,an};

若有子集a1^a2^...^at=0，则a1=a2^a3^...^at，则舍弃a1后一定能通过剩余的元素异或出所有需要a1参与异或的值。设Y=a1^X，因为{a1,a2,...,an}是一组线性基，X一定能由a2...an中相互异或得来。

Y=a1^X=a2^a3^...^at^X，将X中在a2...at中出现的元素删去，在a2...at中未出现的元素加入，则也能异或得到Y，所以a1于线性基无用，与线性基是最小子集的定义矛盾。

所以:线性基没有异或和为0的子集。

折叠编辑本段应用

信息学竞赛中的各种题目。