编码理论第2章

编码理论

第二章数学基础李丽香北京邮电大学二元运算定义：设G是一个集合，G上的二元运算*是这样的规则，它对G中的每对元素a,b，在G中指定第三个唯一元素c=a*b例如：加法是实数域中的二元运算，乘法也是集合在二元运算*之下是封闭的：如果a,b∈G,那么a*b∈G二元运算*是结合的：a*(b*c)=(a*b)*c群的定义定义：一个集合G，在其上定义了一个二元运算*，若它满足以下条件称为群满足封闭性，即对G中任意两个元素a,b,有a*b∈G二元运算*满足结合律G中存在一个元素e，称为恒元或单位元，使得G中任何元素，有a*e=e*a=a对于G中任何一个元素a，G中存在另一个元素，称作a的逆元，使得交换群：若群G的二元运算*还满足，对G中任意的元素a和b有a*b=b*a,那么称此群是可交换的，或称为阿贝尔群群的例子例1：全体整数集合在实数加法运算下构成可交换群，整数0为恒元，整数-a是整数a的逆元。全体整数集合对乘法不构成群，因为不存在乘法逆元例2：除0以外的所有有理数集合，在实数乘法下是一个交换群例3：全体除0以外的有理数集合，在实数乘法下是一个交换群例4：全体实数集合对加法构成交换群，单位元是0，a的逆元是-a。全体除0以外的实数集合对乘法运算构成交换群，单位元是1，逆元是1/a群的例子例5：全体n阶方阵集合对矩阵加法构成交换群，单位元是零矩阵；全体非奇异的n阶矩阵集合对矩阵乘法构成交换群，单位元是n阶单位矩阵例6：集合{0,1}对模2加运算构成交换群，单位元是0，元素1的逆元是1例7：集合{0,1,...,m-1}对模m加运算构成交换群例8：集合{0,1,...,p-1},p为素数，对模p乘法构成交换群；如果p不是素数，该集合不是群群的性质阶的定义：群中元素的个数称为群的阶有限群：有限阶的群；反之就是无限群定理1：群G的恒元是唯一的证明：假定G中有两个的恒元e和，则有证毕定理2：任何一个群元素的逆元是唯一的证明：假定元素a有两个逆元，则证毕群的性质定理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的解的唯一性循环群定义：若存在a∈G是一个集合，使得G中的每个元素都是a的某次幂，即an(n是整数)，则称G是循环群生成元：该循环群由a生成，a是该群的生成元例1：全体整数集合关于加法构成循环群，1是生成元，因为该群有无限多个元素，故称为无限循环群例2：在乘法下是一个交换循环群，该群只有3个元素，该群是有限循环群，1是乘法单位元，其中代表虚数单位循环群的性质定义：使an=1的最小正整数n称为元素a的阶(注意将元素的阶和群的阶要分开)性质1：若a是n阶元素，则群G中的n个元素a0=1,a1,…,an-1互不相同性质2：若a是n阶元素，则由a的一切幂次生成的元素都在群G中性质3：若a是n阶元素，则am=1的充要条件是n|m性质4：若a,b∈G，a是n阶元素，b是m阶元素，且(n,m)=1,则ab的阶是nm,(n,m)表示n和m的最大公因数循环群的性质性质5：若a是n阶元素，则ai元素的阶为n/(i,n)性质6：若a是mn阶元素，则am元素的阶为n性质7：在n阶循环群中，每个元素的阶都是群阶数n的因子例如：设a的阶为63，a7的阶为m，a9的阶为k，根据性质5，有m=63/(63,7)=9,k=63/(63,9)=7;令b1=a7,b2=a9，而(7,9)=1,根据性质4，b1b2的阶为63循环群的生成元根据性质5，群G中的每个元素ai的阶为n/(i,n),若(i,n)=1,则元素ai的阶为n，即ai的全部幂次也可生成该循环群的全部元素定义：循环群G中的每个元素都是某个元素a∈G的幂次的形式，此时称该群由a生成，a是该群的生成元环的定义定义：非空元素集合R中，定义了两种二元运算，称作加法和乘法，这样的代数系统(R,+,·)称为一个环，若它满足以下条件R中全体元素在加法下构成交换群，单位元为0，逆元记为-a乘法运算满足封闭性满足乘法结合率，即(a·b)·c=a·(b·c)

，加法和乘法之间满足分配律

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

交换环：若环关于乘法满足交换律，即对任意的a,b∈R,都有a·b=b·a环的例子例1：全体整数集合在实数加法和乘法运算下构成交换环例2：所有元素为实数的全体n阶方阵集合，对矩阵加法和乘法构成环例3：集合{0,1,...,n-1}在模n的加法运算和乘法运算下，构成交换环例4：全体实数多项式集合构成环例5：全体偶数集合构成环域的定义定义：非空元素集合F中，定义了两种二元运算，称作加法和乘法，这样的代数系统(F,+,·)称为一个域，若它满足以下条件F中全体元素在加法下构成交换群，恒元为0F中非零元素在乘法下为交换群，恒元为1加法和乘法之间满足分配律

(a+b)·c=a·c+b·c从域的定义可以看出：一个域中至少包含2个元素0和1。元素a的加法逆元用-a表示，其乘法逆元用a-1表示域的性质性质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，证毕性质2：若a,b非零，则a·b≠0性质3：若a·b=0且a≠0，则b=0(性质2的推论)性质4：-(a·b)=-a·b=a·(-b)

证明提示：0=0·b=(a+(-a))·b=ab+(-a)·b性质5：若a≠0，a·b=a·c，则b=c

证明提示：用a-1左乘两边即可域的例子阶：域中元素的个数有限域：阶为有限的域，也称为Galois(伽罗华)域例1：二元集合{0,1}对模2加法和模2乘法构成一个域，记为GF(2)例2：令p为素数。考虑模p加法和模p乘法，则集合{0,1,…,p-1}构成一个p元有限域，也称为素域,记为GF(p)例3：全体有理数集合、全体实数集合、全体复数集合在加法和乘法运算下，构成域，它们都是无限域有限域的扩域从域的例子2可看出，对任何素数p都存在一个p阶有限域扩域的定义：对任何正整数m，可以将素域GF(p)扩展为有pm个元素的域，称为GF(p)的扩域，记为GF(pm)。称GF(p)为GF(pm)的基域。此外已经证明：任何有限域的阶都是素数的幂次有限域的特征：设F是域，0和e是加法和乘法的单位元，若对任意正整数n，都有ne≠0，则称域F的特征是0；若有正整数n，使ne=0，则称使ne=0成立的最小正整数n为域F的特征。域的特征或是0，或是有限的素数有限域的特征在域中必有乘法单位元1，若做1+1+…+1运算，对于无限域，则有可能n·1≠0，但在有限域中，必存在1+1+…+1=0，否则该域必成无限域，例如，在GF(2)中，1+1=0GF(2)的特征是2；若p为素数，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，定理显然成立。证毕有限域的性质定理1：有限域的特征n是素数证明：设n≠0，假设n不是素数，即n=n1n2,1<n1<n,1<n2<n,于是0=ne=(n1n2)e=(n1e)(n2e),因此n1e=0或者n2e=0，但这与n的最小性相矛盾，所以n只能是素数。对于任意有限域，由于其只有有限个元素，所以其特征不可能为0，从而其特征一定为素数。有限域的性质定理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有限域的性质定理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,

根据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的约数定理2：

GF(q)中每个非零元素是xq-1-1=0的根，反之，xq-1-1=0的根必在GF(q)中证明：q-1次方程至多q-1个根。因为GF(q)中q-1个非零元素构成循环乘群，它由级为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为素数，当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)中的域整数，则有证明：推论3：对GF(pm)中的任意域元素a，恒有证明：GF(pm)中的任意域元素都是的根，所以有限域的特征定理：在p特征域中，元素为域整数的充要条件是，该元素是xp-1-1=0的根证明：若k为特征域GF(q)中的域整数，根据上一页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，则称之为本原元有限域的元素个数是有限的，域中的全体非零元素集合构成有限乘群，乘群中每个元素的阶是有限的，可以证明，该群是循环群，本原元能生成这个群例如：对于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称为多项式的首项系数。GF(2)中共有2n个多项式首一多项式：首项系数为1的多项式例如：f(x)=3+7x+x3+5x4+x6是GF(8)上的首一多项式，多项式的次数是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,由此可以构造GF(24)GF(2)上多项式的加法和乘法设，则其中M=max{n,m},交换律：a(x)+b(x)=b(x)+a(x);a(x)b(x)=b(x)a(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)+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，用关于多项式的长除法，得到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多项式的余式的性质对于a(x)=q(x)b(x)+r(x)，将多项式的余式记成Rb(x)[a(x)]=r(x)，则对有限域上的多项式a(x),b(x),f(x)，有如下两个性质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)的所有公因式中次数最高的，并且首项系数为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)的所有公倍式中次数最低的，并且首项系数为1，记为LCM(a(x),b(x))既约多项式定义：不能被任何次数更小的多项式整除的多项式称为既约多项式例子：x3+x+1，x2+x+1都是既约多项式已经证明：任意m≥1，存在m次既约多项式由定义可知，常数总是多项式的因子，不论在哪个域上，一次多项式都是既约多项式多项式a(x)是否是既约多项式与讨论的域关系很大，例如：a(x)=x2+1在实数域上是既约的，在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的最小整数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)根据上式进而有：对于任意的l≥0，(f(x))2l=f(x2l)扩域GF(2m)上的运算加法运算：扩域上的两个元素相加得到的结果，仍然是该扩域里面的元素，例101+011=110乘法运算：扩域上的两个元素相乘得到的结果，也必须是该扩域里面的元素，例101·011=？扩域GF(2m)上的乘法运算其中p(x)是次数为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页的内容，可以验证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)是系数取自GF(2)的多项式，令b是GF(2)扩域中的元素，若b是f(x)的根，则对任意的l≥0，b2l也是f(x)的根证明：根据ppt第38页上的式子，可知(f(x))2l=f(x2l)，代入b即可说明定理成立注：元素b2l称为b的共轭元，以上定理说明若是b多项式f(x)的根，则b的所有共轭元b2l也是f(x)的根GF(2)上多项式根的特点令b是GF(2)扩域中的非零元素，根据ppt第19页的定理，可知即b是多项式的根，根据上页定理可知，GF(2)扩域中的每个非零元素都是多项式的根，因此GF(2m)中的所有非零元素构成多项式的全部根定理：

GF(2m)中的所有非零元素构成多项式的全部根推论：

GF(2m)中的所有元素构成多项式的全部根最小多项式定义：令m(x)是使得m(b)=0成立的次数最低的多项式，则称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)的次数小于m(x)的次数，将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为素数)记成定理：设f(x)是GF(p)上多项式，若p特征域中的元素b是f(x)的根，则也是f(x)的根证明：由已知条件f(b)=0,对该式两边重复取p次幂运算，用ppt第24页的推论1，经s次运算可得因为fi∈GF(p),根据ppt第24页的推论2，所以，即也是f(x)的根素域GF(p)上共轭根系定义：若多项式f(x)以b为根，则称为共轭根系注：如果b是p特征域中的n阶元素，bn=1，则b是系数取自GF(p)上的多项式xn-1的根。系数取自GF(p)上且以b为根的多项式可以有多个，其中必有一个次数最低的多项式最小多项式：系数取自GF(p)上且以b为根的所有首一多项式中，必有一个次数最低的多项式，称之为最小多项式，记作m(x)素域GF(p)上的最小多项式定理：在p特征有限域中，对每一个元素b，皆存在有唯一的最小多项式m(x)，具有以下性质：(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的另一个最小多项式，根据性质2，可知m1(x)|m(x)，又因为m(x)是b的最小多项式，所以有

m

(x)|m1(x)。故m1(x)=m(x)。证毕素域GF(p)上的本原多项式定义：系数取自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)上的两个三次本原多项式注：由定义可知，本原多项式必是既约多项式，反之则不然。对于正整数m，至少有一个m次本原多项式，但m次本原多项式可能有多个矢量空间定义：令V是元素的集合，在其上定义了一个称作是加法(+)的二元运算。令F是域。在域F中的元素和V中的元素之间还定义了一个数乘运算(·)。若集合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：结合率。对任意v∈V和a,b∈F，有(a·b)·v=a·(b·v)条件5：令1是F的单位元，则对任意v∈V

，有1·v=v矢量空间矢量：矢量空间V中的元素称作矢量标量：域F中的元素称作标量矢量加法：V上的加法称作矢量加法数乘：F中的标量和V中的矢量之间结合成V中矢量的乘法称作数乘，V中的加法恒元以0表示矢量空间的性质性质1：令0是域F中的零元，对任意的v∈V，有0·v=v性质2：对任意c∈F，有c·v=v性质3：对任意c∈F和v∈V

，有

(-c)·v=c·(-v)=-(c·v)矢量空间上的加法和数乘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重的加法逆元就是它自己数乘：GF(2)中的元素a乘以一个n重v，定义为a·v=(av1,av2,…,avn)矢量空间GF(2)上所有n重的集合Vn形成GF(2)上的一个矢量空间实数域R上的全体n重矢量的集合{(a1,a2,…,an-1)|ai∈R}构成矢量空间实数域R上小于n次的全体多项式的集合{f0+f1x+…+fn-1xn-1|fi∈R}构成矢量空间任意域上的所有n重都构成一个矢量空间子空间：若一个矢量空间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的所有线性组合构成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重构成一个子空间线性相关和线性独立定义：域F上矢量空间V的一组矢量v1,v2,…,vk称作是线性相关的，当且仅当存在不全为0的标量a1,a2,…,ak，使得。否则称v1,v2,…,vk是线性独立的例：

矢量(10110),(01001)和(11111)是线性相关的，因为1·(10110)+1·(01001)+1·(11111)=(00000);但是(10110),(01001),(11011)是线性独立的例子例1：判断GF(2)中的3个三维矢量(100),(010),(001)是否线性相关答：由于在GF(2)上找不到不全为零的3个数n1,n2,n3使得n1(100)+n2(010)+n3(001)=0成立，即只有n1=n2=n3时，该式才成立，故此3个矢量线性无关例2：判断GF(2)中的3个三维矢量(001),(101),(100)是否线性相关答：因为1(001)+1(101)+1(100)=0，故此3个矢量线性相关基和维数定义：称矢量集合张成一个矢量空间V，若V中的每个矢量都是该集合中矢量的线性组合。在任何矢量空间或子空间中，都至少存在一个线性独立的矢量集合B，它张成该空间。这个集合称为矢量空间的基底或基。维数：矢量空间基底中矢量的数目注：任意两个基底中矢量的数目相同有限维数线性空间：如果维数有限，否则就是无限维数线性空间例：GF(