線性基

線性基是競賽中常用來解決子集異或一類題目的算法。

基本介紹

• 中文名：線性基

定義

基：線上性代數中，基（也稱為基底）是描述、刻畫向量空間的基本工具。向量空間的基是它的一個特殊的子集，基的元素稱為基向量。向量空間中任意一個元素，都可以唯一地表示成基向量的線性組合。如果基中元素個數有限，就稱向量空間為有限維向量空間，將元素的個數稱作向量空間的維數。

同樣的，線性基是一種特殊的基，它通常會在異或運算中出現，它的意義是：通過原集合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的子集。

套用

信息學競賽中的各種題目。