編碼理論第2章

編碼理論

第二章數(shù)學基礎(chǔ)李麗香北京郵電大學二元運算定義：設G是一個集合，G上的二元運算*是這樣的規(guī)則，它對G中的每對元素a,b，在G中指定第三個唯一元素c=a*b例如：加法是實數(shù)域中的二元運算，乘法也是集合在二元運算*之下是封閉的：如果a,b∈G,那么a*b∈G二元運算*是結(jié)合的：a*(b*c)=(a*b)*c群的定義定義：一個集合G，在其上定義了一個二元運算*，若它滿足以下條件稱為群滿足封閉性，即對G中任意兩個元素a,b,有a*b∈G二元運算*滿足結(jié)合律G中存在一個元素e，稱為恒元或單位元，使得G中任何元素，有a*e=e*a=a對于G中任何一個元素a，G中存在另一個元素，稱作a的逆元，使得交換群：若群G的二元運算*還滿足，對G中任意的元素a和b有a*b=b*a,那么稱此群是可交換的，或稱為阿貝爾群群的例子例1：全體整數(shù)集合在實數(shù)加法運算下構(gòu)成可交換群，整數(shù)0為恒元，整數(shù)-a是整數(shù)a的逆元。全體整數(shù)集合對乘法不構(gòu)成群，因為不存在乘法逆元例2：除0以外的所有有理數(shù)集合，在實數(shù)乘法下是一個交換群例3：全體除0以外的有理數(shù)集合，在實數(shù)乘法下是一個交換群例4：全體實數(shù)集合對加法構(gòu)成交換群，單位元是0，a的逆元是-a。全體除0以外的實數(shù)集合對乘法運算構(gòu)成交換群，單位元是1，逆元是1/a群的例子例5：全體n階方陣集合對矩陣加法構(gòu)成交換群，單位元是零矩陣；全體非奇異的n階矩陣集合對矩陣乘法構(gòu)成交換群，單位元是n階單位矩陣例6：集合{0,1}對模2加運算構(gòu)成交換群，單位元是0，元素1的逆元是1例7：集合{0,1,...,m-1}對模m加運算構(gòu)成交換群例8：集合{0,1,...,p-1},p為素數(shù)，對模p乘法構(gòu)成交換群；如果p不是素數(shù)，該集合不是群群的性質(zhì)階的定義：群中元素的個數(shù)稱為群的階有限群：有限階的群；反之就是無限群定理1：群G的恒元是唯一的證明：假定G中有兩個的恒元e和，則有證畢定理2：任何一個群元素的逆元是唯一的證明：假定元素a有兩個逆元，則證畢群的性質(zhì)定理3：若a,b∈G，則

證明：所以a*b和互為逆元定理4：給定G中任意兩個元素a和b，則方程a*x=b和y*a=b在G中有唯一解

證明：方程a*x=b的解是x=a-1*b，這是因為

a*a-1*b=e*b=b，同理，y*a=b的解是y=b*a-1。下面證明解的唯一性。如果在方程a*x=b中，除了x=a-1*b，還有另外一個解x1，使a*x1=b,則把該式兩邊左乘以a的逆元a-1，則有a-1*a*x1=a-1*b，由此可得e*x1=x1=a-1*b。同理，可證方程y*a=b的解的唯一性循環(huán)群定義：若存在a∈G是一個集合，使得G中的每個元素都是a的某次冪，即an(n是整數(shù))，則稱G是循環(huán)群生成元：該循環(huán)群由a生成，a是該群的生成元例1：全體整數(shù)集合關(guān)于加法構(gòu)成循環(huán)群，1是生成元，因為該群有無限多個元素，故稱為無限循環(huán)群例2：在乘法下是一個交換循環(huán)群，該群只有3個元素，該群是有限循環(huán)群，1是乘法單位元，其中代表虛數(shù)單位循環(huán)群的性質(zhì)定義：使an=1的最小正整數(shù)n稱為元素a的階(注意將元素的階和群的階要分開)性質(zhì)1：若a是n階元素，則群G中的n個元素a0=1,a1,…,an-1互不相同性質(zhì)2：若a是n階元素，則由a的一切冪次生成的元素都在群G中性質(zhì)3：若a是n階元素，則am=1的充要條件是n|m性質(zhì)4：若a,b∈G，a是n階元素，b是m階元素，且(n,m)=1,則ab的階是nm,(n,m)表示n和m的最大公因數(shù)循環(huán)群的性質(zhì)性質(zhì)5：若a是n階元素，則ai元素的階為n/(i,n)性質(zhì)6：若a是mn階元素，則am元素的階為n性質(zhì)7：在n階循環(huán)群中，每個元素的階都是群階數(shù)n的因子例如：設a的階為63，a7的階為m，a9的階為k，根據(jù)性質(zhì)5，有m=63/(63,7)=9,k=63/(63,9)=7;令b1=a7,b2=a9，而(7,9)=1,根據(jù)性質(zhì)4，b1b2的階為63循環(huán)群的生成元根據(jù)性質(zhì)5，群G中的每個元素ai的階為n/(i,n),若(i,n)=1,則元素ai的階為n，即ai的全部冪次也可生成該循環(huán)群的全部元素定義：循環(huán)群G中的每個元素都是某個元素a∈G的冪次的形式，此時稱該群由a生成，a是該群的生成元環(huán)的定義定義：非空元素集合R中，定義了兩種二元運算，稱作加法和乘法，這樣的代數(shù)系統(tǒng)(R,+,·)稱為一個環(huán)，若它滿足以下條件R中全體元素在加法下構(gòu)成交換群，單位元為0，逆元記為-a乘法運算滿足封閉性滿足乘法結(jié)合率，即(a·b)·c=a·(b·c)

，加法和乘法之間滿足分配律

a·(b+c)=a·b+a·c,(b+c)·a=b·a+c·a,

交換環(huán)：若環(huán)關(guān)于乘法滿足交換律，即對任意的a,b∈R,都有a·b=b·a環(huán)的例子例1：全體整數(shù)集合在實數(shù)加法和乘法運算下構(gòu)成交換環(huán)例2：所有元素為實數(shù)的全體n階方陣集合，對矩陣加法和乘法構(gòu)成環(huán)例3：集合{0,1,...,n-1}在模n的加法運算和乘法運算下，構(gòu)成交換環(huán)例4：全體實數(shù)多項式集合構(gòu)成環(huán)例5：全體偶數(shù)集合構(gòu)成環(huán)域的定義定義：非空元素集合F中，定義了兩種二元運算，稱作加法和乘法，這樣的代數(shù)系統(tǒng)(F,+,·)稱為一個域，若它滿足以下條件F中全體元素在加法下構(gòu)成交換群，恒元為0F中非零元素在乘法下為交換群，恒元為1加法和乘法之間滿足分配律

(a+b)·c=a·c+b·c從域的定義可以看出：一個域中至少包含2個元素0和1。元素a的加法逆元用-a表示，其乘法逆元用a-1表示域的性質(zhì)性質(zhì)1：對域中的任意元素a，有a·0=0·a=0

證明：a=a·1=a·(1+0)=a+a·0,該式左右兩邊同時左加上-a，得到-a+a=-a+(a+a·0),推出0=0+a·0，即a·0=0;同理可證0·a=0，證畢性質(zhì)2：若a,b非零，則a·b≠0性質(zhì)3：若a·b=0且a≠0，則b=0(性質(zhì)2的推論)性質(zhì)4：-(a·b)=-a·b=a·(-b)

證明提示：0=0·b=(a+(-a))·b=ab+(-a)·b性質(zhì)5：若a≠0，a·b=a·c，則b=c

證明提示：用a-1左乘兩邊即可域的例子階：域中元素的個數(shù)有限域：階為有限的域，也稱為Galois(伽羅華)域例1：二元集合{0,1}對模2加法和模2乘法構(gòu)成一個域，記為GF(2)例2：令p為素數(shù)。考慮模p加法和模p乘法，則集合{0,1,…,p-1}構(gòu)成一個p元有限域，也稱為素域,記為GF(p)例3：全體有理數(shù)集合、全體實數(shù)集合、全體復數(shù)集合在加法和乘法運算下，構(gòu)成域，它們都是無限域有限域的擴域從域的例子2可看出，對任何素數(shù)p都存在一個p階有限域擴域的定義：對任何正整數(shù)m，可以將素域GF(p)擴展為有pm個元素的域，稱為GF(p)的擴域，記為GF(pm)。稱GF(p)為GF(pm)的基域。此外已經(jīng)證明：任何有限域的階都是素數(shù)的冪次有限域的特征：設F是域，0和e是加法和乘法的單位元，若對任意正整數(shù)n，都有ne≠0，則稱域F的特征是0；若有正整數(shù)n，使ne=0，則稱使ne=0成立的最小正整數(shù)n為域F的特征。域的特征或是0，或是有限的素數(shù)有限域的特征在域中必有乘法單位元1，若做1+1+…+1運算，對于無限域，則有可能n·1≠0，但在有限域中，必存在1+1+…+1=0，否則該域必成無限域，例如，在GF(2)中，1+1=0GF(2)的特征是2；若p為素數(shù)，GF(p)的特征是p定理：在特征為p的域中，若a是域中的任意元素，則均有pa=0證明：若a≠0，則pa=a+a+…+a=1·a+1·a+…+1·a=(1+1+…+1)·a=p·1·a=0·a=0，定理成立；若a=0，定理顯然成立。證畢有限域的性質(zhì)定理1：有限域的特征n是素數(shù)證明：設n≠0，假設n不是素數(shù)，即n=n1n2,1<n1<n,1<n2<n,于是0=ne=(n1n2)e=(n1e)(n2e),因此n1e=0或者n2e=0，但這與n的最小性相矛盾，所以n只能是素數(shù)。對于任意有限域，由于其只有有限個元素，所以其特征不可能為0，從而其特征一定為素數(shù)。有限域的性質(zhì)定理2：設a是有限域GF(q)的非零元素，則aq-1=1證明：令b1,b2,…,bq-1為GF(q)的q-1個非零元素，顯然q-1個非零元素ab1,ab2,…,abq-1非零且互不相同，因此

(ab1)·(ab2)·…·(abq-1)=b1·b2·…·bq-1

所以aq-1(b1·b2·…·bq-1)=b1·b2·…·bq-1

即有aq-1=1有限域的性質(zhì)定理3：設a是有限域GF(q)的非零元素，令n是a的階，則q-1能被n整除，即n|(q-1)

證明：假設q-1不能被n整除，則q-1=kn+r,其中0<r<n，于是aq-1=akn+r=aknar=(an)kar=ar,

根據(jù)aq-1=1，an=1，推出ar=1，這與n的定義矛盾，所以q-1必能被n整除。證畢有限域的階：設a是有限域GF(q)的非零元素，因為aq-1=1，所以有限域的階是q-1有限域的階定理1：有限域GF(q)的階是q-1或者是q-1的約數(shù)定理2：

GF(q)中每個非零元素是xq-1-1=0的根，反之，xq-1-1=0的根必在GF(q)中證明：q-1次方程至多q-1個根。因為GF(q)中q-1個非零元素構(gòu)成循環(huán)乘群，它由級為q-1的本原元a的所有次冪生成，即1,a,a2,…,aq-2，對本原元有aq-1=1，所以對于GF(q)中的每個元素ai，我們有(ai)q-1=(aq-1)i=1,i=0,1,…,q-2，所以GF(q)中每個非零元素是xq-1-1=0的根。反之，如果b是方程xq-1-1=0的根，則bq-1=1，因此b必是由GF(q)中的本原元的冪次，即b是GF(q)中的元素。有限域的特征定理1：在特征為p的域中，若a是域中的任意元素，則有pa=0

證明：若a≠0，則有pa=a+a+…+a=1·a+1·a+…+1·a=(1+1+…+1)·a=p·1·a=0·a=0，定理成立；若a=0，定理也成立。證畢。定理2：在特征為p的域中，若a是域中的任意元素，則有(x-a)p=xp-ap

證明：由二項式定理知其中已知p為素數(shù)，當k=1,2,…,p-1時，(k!,p)=1，由上式知含有素因子p，記，由于域的特征是p，故，所以(x-a)p=xp+(-a)p

=xp-ap有限域的特征推論1：在特征為p的域中，若a,b是域中的元素，則(a±b)p=ap+bp推論2：若k為p特征域GF(pm)中的域整數(shù)，則有證明：推論3：對GF(pm)中的任意域元素a，恒有證明：GF(pm)中的任意域元素都是的根，所以有限域的特征定理：在p特征域中，元素為域整數(shù)的充要條件是，該元素是xp-1-1=0的根證明：若k為特征域GF(q)中的域整數(shù)，根據(jù)上一頁ppt的推論3，可知kp=k,kp-k=0,kp-1-1=0，因此k是方程xp-1-1=0的根，反知，若k是方程xp-1-1=0的根，則kp-1-1=0，由第20頁ppt的定理2可知，它必在域GF(q)中本原元本原元：在有限域GF(q)中，若非零元素a的階為q-1，則稱之為本原元有限域的元素個數(shù)是有限的，域中的全體非零元素集合構(gòu)成有限乘群，乘群中每個元素的階是有限的，可以證明，該群是循環(huán)群，本原元能生成這個群例如：對于GF(5)={0,1,2,3,4}，元素1的階是1；元素2的階是4，因為21=2,22=4,23=3,24=1;元素3的階是4，因為31=2,32=4,33=2,34=1;元素4的階是2，因為41=4,42=1。元素2和3是本原元GF(2)上多項式的定義多項式定義：二元域GF(2)中表達式f(x)=f0+f1x+…+fnxn，其中fi=0或1。若fn≠0，則稱f(x)是n次多項式，記為deg(f(x))=n，fn稱為多項式的首項系數(shù)。GF(2)中共有2n個多項式首一多項式：首項系數(shù)為1的多項式例如：f(x)=3+7x+x3+5x4+x6是GF(8)上的首一多項式，多項式的次數(shù)是6GF(2)的擴域GF(2m)GF(2m)中的2m個元素GF(23)中的元素GF(23)

上的多項式GF(2)的擴域GF(2m)p(x)=1+x+x4是GF(2)上的本原多項式，假設a是本原元，則a4=1+a,由此可以構(gòu)造GF(24)GF(2)上多項式的加法和乘法設，則其中M=max{n,m},交換律：a(x)+b(x)=b(x)+a(x);a(x)b(x)=b(x)a(x)結(jié)合律：

a(x)+[b(x)+c(x)]=[a(x)+b(x)]+c(x)a(x)·[b(x)·c(x)]=[a(x)·b(x)]·c(x)分配律：

a(x)·[b(x)+c(x)]=a(x)·b(x)+a(x)·c(x)GF(2)上多項式的除法對于GF(2)上的每一對多項式a(x)和b(x)≠0，都存在唯一的一對多項式q(x)(商)和r(x)(余式)，使得a(x)=q(x)b(x)+r(x)，其中deg(r(x))<deg(b(x))如果r(x)=0，則稱b(x)整除a(x)，記為b(x)|a(x)，又稱b(x)是a(x)的因式，a(x)是b(x)的倍式例如，a(x)=2x3+3x2+5,b(x)=x2-2x-1，用關(guān)于多項式的長除法，得到a(x)=(2x-1)b(x)+(4x+4)，商是2x-1，余式是4x+4復習1010001=1011×1001+0000010二元序列及其對應的多項式1011011≌

x6+0·x5+x4+x3+0·x2+x+1=x6+x4+x3+x+1多項式加法：(x3+x+1)+(x2+1)=x3+x2+x多項式乘法：

(x3+x+1)+(x2+1)=x5+x3+x3+x+x2+1=x5+x2+x+1

二元序列及其對應的多項式多項式除法：

x6+x4+1=(x3+1)(x3++x+1)+x多項式的余式的性質(zhì)對于a(x)=q(x)b(x)+r(x)，將多項式的余式記成Rb(x)[a(x)]=r(x)，則對有限域上的多項式a(x),b(x),f(x)，有如下兩個性質(zhì)Rf(x)[a(x)+b(x)]=Rf(x)[a(x)]+Rf(x)[b(x)]Rf(x)[a(x)·b(x)]=Rf(x){Rf(x)[a(x)]·Rf(x)[b(x)]}a(x)與b(x)模f(x)同余：對有限域上的多項式a(x),b(x),f(x)≠0，有f(x)|(a(x)-b(x))f(x)為a(x)與b(x)的公因式：對有限域上的多項式a(x),b(x),f(x)≠0，有f(x)|a(x)，f(x)|b(x)多項式的公因式和公倍式最高公因式：若f(x)為a(x)與b(x)的所有公因式中次數(shù)最高的，并且首項系數(shù)為1，記為gcd(a(x),b(x))a(x)與b(x)互素：當a(x)≠0,b(x)≠0，并且gcd(a(x),b(x))=1f(x)為a(x)與b(x)的公倍式：當a(x)≠0,b(x)≠0，并且a(x)|f(x)，b(x)|f(x)最低公倍式：若f(x)為a(x)與b(x)的所有公倍式中次數(shù)最低的，并且首項系數(shù)為1，記為LCM(a(x),b(x))既約多項式定義：不能被任何次數(shù)更小的多項式整除的多項式稱為既約多項式例子：x3+x+1，x2+x+1都是既約多項式已經(jīng)證明：任意m≥1，存在m次既約多項式由定義可知，常數(shù)總是多項式的因子，不論在哪個域上，一次多項式都是既約多項式多項式a(x)是否是既約多項式與討論的域關(guān)系很大，例如：a(x)=x2+1在實數(shù)域上是既約的，在GF(2)是可約的，a(x)=x2+1=(x+1)(x+1)本原多項式定理：GF(2)上的任意次既約多項式可以除盡x(2^m-1)+1例子：x3+x+1除盡x7+1唯一因式分解定理：任一首一多項式a(x)必可分解為首一既約多項式之積，當不考慮因式的順序時，這種分解是唯一的推論：n次多項式不可能有多于n個的因式本原多項式定義：若m次既約多項式p(x)可以除盡xn+1的最小整數(shù)n滿足n=2m-1，則稱p(x)是本原多項式本原多項式驗證：a(x)=x4+x+1可以除盡x15+1，但不能除盡1≤n<15的xn+1，故x4+x+1是一個本原多項式GF(2)上的多項式f(x)滿足[f(x)]2=f(x2)根據(jù)上式進而有：對于任意的l≥0，(f(x))2l=f(x2l)擴域GF(2m)上的運算加法運算：擴域上的兩個元素相加得到的結(jié)果，仍然是該擴域里面的元素，例101+011=110乘法運算：擴域上的兩個元素相乘得到的結(jié)果，也必須是該擴域里面的元素，例101·011=？擴域GF(2m)上的乘法運算其中p(x)是次數(shù)為m的本元多項式本原多項式GF(23)上的多項式

多項式向量GF(23)上的乘法運算是個本原元乘法運算：本原多項式選擇本原元因為本原元a=x，所以p(a)=0GF(24)是個本原元GF(2)上多項式根的特點定理：若f(x)為GF(2)上的一個m次既約多項式，則其擴域GF(2m)含有f(x)的m個根；進一步的，若r|d，則任何GF(2d)含有f(x)的根例子：x4+x3+1在GF(2)上是既約多項式，所以它在GF(2)上沒有根，可以驗證它有取自GF(24)上的4個根，利用本章PPT25頁的內(nèi)容，可以驗證a7,a11,a13,a14都是該多項式的根，

(a7)4+(a7)3+1=a28+a21+1=a13+a6+1=(1+a2+a3)+(a2+a3)+1=0GF(2)上多項式根的特點定理：若f(x)是系數(shù)取自GF(2)的多項式，令b是GF(2)擴域中的元素，若b是f(x)的根，則對任意的l≥0，b2l也是f(x)的根證明：根據(jù)ppt第38頁上的式子，可知(f(x))2l=f(x2l)，代入b即可說明定理成立注：元素b2l稱為b的共軛元，以上定理說明若是b多項式f(x)的根，則b的所有共軛元b2l也是f(x)的根GF(2)上多項式根的特點令b是GF(2)擴域中的非零元素，根據(jù)ppt第19頁的定理，可知即b是多項式的根，根據(jù)上頁定理可知，GF(2)擴域中的每個非零元素都是多項式的根，因此GF(2m)中的所有非零元素構(gòu)成多項式的全部根定理：

GF(2m)中的所有非零元素構(gòu)成多項式的全部根推論：

GF(2m)中的所有元素構(gòu)成多項式的全部根最小多項式定義：令m(x)是使得m(b)=0成立的次數(shù)最低的多項式，則稱m(x)是b的最小多項式定理1：域元素b的最小多項式是既約的定理2：令f(x)是GF(2)上的多項式，m(x)是域元素b的最小多項式，若b是f(x)的根，則f(x)可以除盡m(x)

證明：反證法。假設f(x)=a(x)m(x)+r(x)，其中r(x)的次數(shù)小于m(x)的次數(shù)，將b帶入該方程，得到r(x)=0，這與假設矛盾，所以f(x)必可以除盡m(x)GF(2)上本原元的特點定理1：令f(x)是GF(2)上的既約多項式，b是GF(2m)中的元素，m(x)是域元素b的最小多項式，若f(b)=0，則m(x)=f(x)。(既約多項式有根，則必為該根的極小多項式)定理2：若a是GF(2m)中的本原元，則它的所有共軛元素也是GF(2m)中的本原元定理3：若a是GF(2m)中的n階元素，則它的所有共軛元素也是GF(2m)中的n階元素素域GF(p)上多項式根的特點將定義在素域GF(p)上多項式(p為素數(shù))記成定理：設f(x)是GF(p)上多項式，若p特征域中的元素b是f(x)的根，則也是f(x)的根證明：由已知條件f(b)=0,對該式兩邊重復取p次冪運算，用ppt第24頁的推論1，經(jīng)s次運算可得因為fi∈GF(p),根據(jù)ppt第24頁的推論2，所以，即也是f(x)的根素域GF(p)上共軛根系定義：若多項式f(x)以b為根，則稱為共軛根系注：如果b是p特征域中的n階元素，bn=1，則b是系數(shù)取自GF(p)上的多項式xn-1的根。系數(shù)取自GF(p)上且以b為根的多項式可以有多個，其中必有一個次數(shù)最低的多項式最小多項式：系數(shù)取自GF(p)上且以b為根的所有首一多項式中，必有一個次數(shù)最低的多項式，稱之為最小多項式，記作m(x)素域GF(p)上的最小多項式定理：在p特征有限域中，對每一個元素b，皆存在有唯一的最小多項式m(x)，具有以下性質(zhì)：(1)m(x)在GF(p)上是既約的；(2)若f(x)是GF(p)上多項式，且f(b)=0，則m(x)|f(x)，顯然證明：(1)若m(x)不是既約的,則m(x)=m1(x)m2(x)，deg(m1(x)),deg(m2(x))<deg(m(x))，因為b是f(x)的根，則有m(b)=m1(b)m2(b)=0，所以必有m1(b)=0或m2(b)=0，而這與m(x)是元素的多項式的前提相矛盾，因此m(x)是既約的。(2)由有限域上的多項式除法知f(x)=q(x)m(x)+r(x),deg(r(x))<deg(m(x))，因為f(b)=0,m(b)=0，所以r(x)=0,故有m(x)|f(x)。因為b∈GF(pm)，所以，故b是多項式的根，所以。(3)唯一性證明：若m1(x)是b的另一個最小多項式，根據(jù)性質(zhì)2，可知m1(x)|m(x)，又因為m(x)是b的最小多項式，所以有

m

(x)|m1(x)。故m1(x)=m(x)。證畢素域GF(p)上的本原多項式定義：系數(shù)取自GF(p)上，以GF(pm)中本原元為根的最小多項式注：本原多項式一定以n=pm-1階元素為根，設a為本原元，則以它為根的共軛根系是共有m個根，因此，以GF(pm)上的本原元為根的GF(p)上的本原多項式，必是m次多項式素域GF(p)上的本原多項式例1：f1(x)=x3+x+1,f2(x)=x4+x3+x2+x+1,f3(x)=x4+x+1,f4(x)=x4+x3+x2+1均是GF(2)上的多項式，可以驗證f1(x),f2(x),f3(x)是既約多項式,f4(x)不是既約多項式。因為x7+1=(x+1)(x3+x2+1)f1(x),f4(x)=(x+1)f1(x)x5+1=(x+1)f2(x),f3(x)|(x15+1)GF(2)上的既約多項式f1(x)和f3(x)是本原多項式，因為23-1=7，24-1=15；f2(x)不是本原多項式，因為24-1≠5例2：x3+x+1，x3+x2+1是GF(2)上的兩個三次本原多項式注：由定義可知，本原多項式必是既約多項式，反之則不然。對于正整數(shù)m，至少有一個m次本原多項式，但m次本原多項式可能有多個矢量空間定義：令V是元素的集合，在其上定義了一個稱作是加法(+)的二元運算。令F是域。在域F中的元素和V中的元素之間還定義了一個數(shù)乘運算(·)。若集合V滿足下述條件，就稱它為域F上的矢量空間或線性空間：條件1：V是加法下的可交換群條件2：對F中的任意元素a和V中的任意元素v，a·v是V中的元素條件3：分配率。對任意u,v∈V和a,b∈F，有a·(u+v)=a·u+a·v,(a+b)·v=a·v+b·v條件4：結(jié)合率。對任意v∈V和a,b∈F，有(a·b)·v=a·(b·v)條件5：令1是F的單位元，則對任意v∈V

，有1·v=v矢量空間矢量：矢量空間V中的元素稱作矢量標量：域F中的元素稱作標量矢量加法：V上的加法稱作矢量加法數(shù)乘：F中的標量和V中的矢量之間結(jié)合成V中矢量的乘法稱作數(shù)乘，V中的加法恒元以0表示矢量空間的性質(zhì)性質(zhì)1：令0是域F中的零元，對任意的v∈V，有0·v=v性質(zhì)2：對任意c∈F，有c·v=v性質(zhì)3：對任意c∈F和v∈V

，有

(-c)·v=c·(-v)=-(c·v)矢量空間上的加法和數(shù)乘n重：GF(2)上的n個分量的有序序列(a1,a2,…,an)稱作n重,共有2n個不同的n重，令Vn表示所有n重的集合在Vn中定義加法為對應分量的模2加，即u=(u1,u2,…,un),v=(v1,v2,…,vn)∈Vn，則u+v=(u1+v1,u2+v2,…,un+vn)∈VnVn在此加法之下是可交換群，全零n重(0,0,…,0)是加法恒元，Vn中每個n重的加法逆元就是它自己數(shù)乘：GF(2)中的元素a乘以一個n重v，定義為a·v=(av1,av2,…,avn)矢量空間GF(2)上所有n重的集合Vn形成GF(2)上的一個矢量空間實數(shù)域R上的全體n重矢量的集合{(a1,a2,…,an-1)|ai∈R}構(gòu)成矢量空間實數(shù)域R上小于n次的全體多項式的集合{f0+f1x+…+fn-1xn-1|fi∈R}構(gòu)成矢量空間任意域上的所有n重都構(gòu)成一個矢量空間子空間：若一個矢量空間V的子集S也是一個矢量空間，則S稱為V的一個子空間子空間定理：令S是域F上矢量空間V的一個非空子集，則當S滿足下列條件時，它是V的一個子空間：條件1：對S中的任意兩個矢量u,v，則u+v也是S中的矢量條件2：對F中的任意元素a和S中的任意矢量u，則a·u也在S中例：V5中的子集{(00000),(00111),(11010),(11101)}滿足條件1和條件2線性組合令v1,v2,…,vk∈V是k個矢量，a1,a2,…,ak∈F是k個標量，稱∑aivi為線性組合定理：

令v1,v2,…,vk是域F上矢量空間V的k個矢量，則v1,v2,…,vk的所有線性組合構(gòu)成V的一個子空間例：GF(2)中的兩個5重(00111)和(11101)的所有線性組合是：0·(00111)+0·(11101)=(00000),0·(00111)+1·(11101)=(11101),1·(00111)+0·(11101)=(00111),1·(00111)+1·(11101)=(11010),這4個5重構(gòu)成一個子空間線性相關(guān)和線性獨立定義：域F上矢量空間V的一組矢量v1,v2,…,vk稱作是線性相關(guān)的，當且僅當存在不全為0的標量a1,a2,…,ak，使得。否則稱v1,v2,…,vk是線性獨立的例：

矢量(10110),(01001)和(11111)是線性相關(guān)的，因為1·(10110)+1·(01001)+1·(11111)=(00000);但是(10110),(01001),(11011)是線性獨立的例子例1：判斷GF(2)中的3個三維矢量(100),(010),(001)是否線性相關(guān)答：由于在GF(2)上找不到不全為零的3個數(shù)n1,n2,n3使得n1(100)+n2(010)+n3(001)=0成立，即只有n1=n2=n3時，該式才成立，故此3個矢量線性無關(guān)例2：判斷GF(2)中的3個三維矢量(001),(101),(100)是否線性相關(guān)答：因為1(001)+1(101)+1(100)=0，故此3個矢量線性相關(guān)基和維數(shù)定義：稱矢量集合張成一個矢量空間V，若V中的每個矢量都是該集合中矢量的線性組合。在任何矢量空間或子空間中，都至少存在一個線性獨立的矢量集合B，它張成該空間。這個集合稱為矢量空間的基底或基。維數(shù)：矢量空間基底中矢量的數(shù)目注：任意兩個基底中矢量的數(shù)目相同有限維數(shù)線性空間：如果維數(shù)有限，否則就是無限維數(shù)線性空間例：GF(