糾錯碼環(huán)與域的基本概念演示文稿

糾錯碼環(huán)與域的基本概念演示文稿目前一頁\總數(shù)一百一十七頁\編于十二點（優(yōu)選）糾錯碼環(huán)與域的基本概念目前二頁\總數(shù)一百一十七頁\編于十二點

例R1

全體整數(shù)構(gòu)成環(huán)，用Z表示。例R2

全體偶數(shù)構(gòu)成環(huán)。例R3

某一整數(shù)m的倍數(shù)全體構(gòu)成環(huán)，如3的倍數(shù)全體…，-3，0，3，6，9，…，構(gòu)成一個環(huán)。例R4

模整數(shù)m的全體剩余類構(gòu)成環(huán)，稱此環(huán)為剩余類環(huán)，用Zm表示。如模m=7所構(gòu)成的全體剩余類：0，1，2，3，4，5，6

構(gòu)成環(huán)Z7，且為可換環(huán)。例R5

實系數(shù)多項式全體構(gòu)成環(huán)。例R6

n階方陣全體構(gòu)成環(huán)。目前三頁\總數(shù)一百一十七頁\編于十二點

定理2.3.1任何a，b∈R，有

(1)a0=0a=0；

(2)a(-b)=(-a)b=-ab。除了以上性質(zhì)外，環(huán)中還有許多較特殊的性質(zhì)。

(1)環(huán)中可以有零因子。設(shè)a、b∈R，且a≠0，b≠0，若ab=0∈R，則a、b為零因子，稱有零因子的環(huán)為有零因子環(huán)。目前四頁\總數(shù)一百一十七頁\編于十二點

二、域除上面所講的群、格和環(huán)以外，域在編碼理論中起著關(guān)鍵作用。域是定義了兩種代數(shù)運算的系統(tǒng)。定義2.3.2非空元素集合F，若在F中定義了加和乘兩種運算，且滿足下述公理：目前五頁\總數(shù)一百一十七頁\編于十二點(1)F關(guān)于加法構(gòu)成阿貝爾群。其加法恒等元記為0。

(2)F中非零元素全體對乘法構(gòu)成阿貝爾群。其乘法恒等元(單位元)記為1。

(3)加法和乘法間有如下分配律：a(b+c)=ab+ac(b+c)a=ba+ca則稱F是一個域。目前六頁\總數(shù)一百一十七頁\編于十二點

例F1有理數(shù)全體、實數(shù)全體、復(fù)數(shù)全體對加法、乘法都分別構(gòu)成域，分別稱有理數(shù)域、實數(shù)域和復(fù)數(shù)域。且這3個域中的元素個數(shù)有無限多個，所以稱它們?yōu)闊o限域。例F20、1兩個元素按模2加和模2乘構(gòu)成域。該域中只有兩個元素，記為GF(2)或F2。目前七頁\總數(shù)一百一十七頁\編于十二點

定理2.3.2設(shè)p為素數(shù)，則整數(shù)全體關(guān)于模p的剩余類：0

，1

，2

，…，p-1

，在模p運算下(模p相加和相乘)，構(gòu)成p階有限域Fp(GF(p))。目前八頁\總數(shù)一百一十七頁\編于十二點

證明由前面已知，模m整數(shù)(m不一定為素數(shù))剩余類集合構(gòu)成交換環(huán)Zm，現(xiàn)在只需證明當(dāng)m=p為素數(shù)時，非0元素有逆元即可。1為單位元，因為p為素數(shù)，因此任何小于p的數(shù)a和p均互素。所以，由歐幾里德算法可知：

(a，p)=1=Aa+Bp

在等式兩邊對p取模，則

1≡Aa(modp)

所以1

=Aa

也就是剩余類中任一元素a均有逆元a-1=A。目前九頁\總數(shù)一百一十七頁\編于十二點

例F3以p=3為模的剩余類全體：0

，1

，2

構(gòu)成一個三階有限域GF(3)，它們的模3加法和乘法運算表如下所示：目前十頁\總數(shù)一百一十七頁\編于十二點§2.4子群、正規(guī)子群和商群

一、子群定義2.4.1若群G的非空子集H對于G中定義的代數(shù)運算也構(gòu)成群，則稱H為群G的子群。例如，偶數(shù)全體構(gòu)成的群是全體整數(shù)所構(gòu)成加群的一個子群。每個群一定有兩個子群，群自己和由一個恒等元所構(gòu)成的群，稱這兩個子群為假子群或平凡子群。除這兩個假子群以外，所有其它子群稱為真子群。目前十一頁\總數(shù)一百一十七頁\編于十二點

定理2.4.1群G的非空子集H為G的子群的充要條件是：

(1)若a∈H，b∈H，則ab∈H；

(2)若a∈H，則a的逆元a-1∈H。證明若H為子群，則(1)、(2)自然成立。反之，由(1)可知，H關(guān)于G的代數(shù)運算封閉。由(2)知，H中的每一元素均有逆元。因為H是G的子集，所以G中的結(jié)合律在H中同樣適用，又因a∈H，a-1∈H及aa-1=e∈H(由(1)條件)，H中有單位元，故H是一個群。目前十二頁\總數(shù)一百一十七頁\編于十二點

定理2.4.2H是G的子群的充要條件是：對任何a，b∈H，恒有ab-1∈H。證明若H是G的子群，則上述條件自然成立。反之，假定上述條件成立，現(xiàn)在要證H是G的子群。因為H為非空子集。所以必有a∈H，再令b=a，由假設(shè)條件可得aa-1∈H，而aa-1=e，所以e∈H，H中有單位元存在。目前十三頁\總數(shù)一百一十七頁\編于十二點

其次，由a∈H，e∈H，由條件可推出ea-1∈H，而ea-1=a-1，a-1∈H，故H中的每一元素a均有逆元a-1存在。最后，由a∈H，b∈H(從而b-1∈H)，再根據(jù)條件可知a(b-1)-1=ab∈H，所以在H中封閉性成立。由此可知，H滿足群的公理，所以H是一子群。目前十四頁\總數(shù)一百一十七頁\編于十二點二、陪集若G中有子群H，則可用H把G劃分成等價類，如下所示：設(shè)群G的元素是：g1，g2，g3，g4，…；子群H的元素是：h1，h2，h3，…；目前十五頁\總數(shù)一百一十七頁\編于十二點h1=eh2h3

…

子群

g1h1=g1g1h2g1h3

…

左陪集

g2h1=g2g2h2g2h3

…

左陪集…

…

…

…gnh1=gngnh2gnh3

…

左陪集

↑

陪集首

目前十六頁\總數(shù)一百一十七頁\編于十二點

定義2.4.2設(shè)H是群G的子群，g是G中的任一元素，將g左(右)乘H中的每一元素，便得到gh(hg)的元素集合，記gH(Hg)，稱之為它的子群H在群G中的一個左(右)陪集，稱e，g1，g2，…，gn為陪集首。目前十七頁\總數(shù)一百一十七頁\編于十二點

由定義可知，若g=e∈H，則eH=H。因此子群本身就是一個左(右)陪集。同樣，若b∈gH，即b=gh(h∈H)，則bH=ghH=g(hH)=gH。這表明左(或右)陪集gH可由其中任一元素唯一確定。從上可知，陪集其實就是把G中的元素按子群H劃分成等價類，在同一陪集中都含有一個共同的元素gi(陪集首)。目前十八頁\總數(shù)一百一十七頁\編于十二點

在阿貝爾群中，由于對任何g，h∈G，gh=hg，因此左陪集等于右陪集。例如，全體整數(shù)構(gòu)成一個加群，以m為倍數(shù)的整數(shù)全體是其中的一個子群，所以可以按此子群把全體整數(shù)劃分陪集。如m=5，則陪集表如下：目前十九頁\總數(shù)一百一十七頁\編于十二點子群

H:

0

5

-5

10

-10

…，

01+h：

1

6

-4

11

-9

…，

12+h：

2

7

-3

12

-8

…，

23+h：

3

8

-2

13

-7

…，

34+h：

4

9

-1

14

-6

…，

4目前二十頁\總數(shù)一百一十七頁\編于十二點

引理2.4.1群G的兩個元素ga、gb屬于子群H的同一陪集的充要條件是g-1agb∈H。證明若ga、gb屬于H的同一陪集，則

ga=gihj

gb=gihk

j≠k

gi為該陪集的陪集首。由此

g-1agb=(gihj)-1gihk=h-1jg-1igihk=h-1jehk=h-1jhk∈H目前二十一頁\總數(shù)一百一十七頁\編于十二點

反之，若g-1agb∈H，現(xiàn)證ga、gb屬于H的同一陪集中。

g-1agb∈H，所以g-1agb=h′∈H，兩邊同乘ga得gb=gah′。因此，若設(shè)ga=gihj，則gb=gihjh′=gihi，因為hi∈H，所以ga與gb都在以gi為陪集首的陪集中。目前二十二頁\總數(shù)一百一十七頁\編于十二點

定理2.4.3兩個陪集要么相等要么不相交。證明若兩個倍集g1H與g2H相交，則必定有公共的元素c，即H存在有元素h1、h2，使g1h1=g2h2=c，則g1h1h-11=g2h2h-11，h2h-1=h，g1=g2h。所以，

g-12g1=h∈H，由引理2.4.1可知，g2、g1必在同一陪集中，所以兩個陪集完全相等。目前二十三頁\總數(shù)一百一十七頁\編于十二點

前面已談到過，群中元素的個數(shù)可以是無限的，也可以是有限的。例如，所有整數(shù)全體所構(gòu)成的加法群，其元素個數(shù)為無限的，是一無限群。若元素個數(shù)為有限的，則稱為有限群，且稱元素的個數(shù)為有限群的階。同樣，我們稱子群中元素的個數(shù)為子群的階。目前二十四頁\總數(shù)一百一十七頁\編于十二點

由上面的討論可以得出如下結(jié)論：

(1)有限群G可以按子群H劃分成有限個互不相交的陪集，且各陪集都具有相同的元素個數(shù)，即等于子群H的階。

(2)在劃分陪集的以下陣列(稱Slepian陣)中，若僅有j個陪集：目前二十五頁\總數(shù)一百一十七頁\編于十二點H：

1h1h2

…h(huán)na2H:a2a2h1a2h2

…a2hn…

…

…

…

…aj-1H:aj-1aj-1h1aj-1h2

…aj-1hn

目前二十六頁\總數(shù)一百一十七頁\編于十二點

則G中的所有元素都在此陣列中，無一遺漏。若有一元素b∈G不在該陣列中，則我們可再作陪集bH，若它與上述某一陪集重合，則b含于該陪集中，否則便得到第j+1個陪集，而這與僅有j個倍集的假設(shè)相矛盾。因此，G中所有元素都在該陣列中。所以，若G的階為N，H的階為n，有j個陪集，則N=jn。由此得到以下的定理。目前二十七頁\總數(shù)一百一十七頁\編于十二點

格拉朗日(Lagranges

)定理有限群的子群的階數(shù)，一定是整個群的階數(shù)的因子。例如，模m=9的剩余類全體：0

，1

，…，8

，對模9加法運算構(gòu)成一個群，而0

，3

，6

是它的一個子群，以此子群劃分陪集：

H

：0

3

6

1+H：1

4

7

2+H：2

5

8

共有3個陪集。子群的階為三，是群的階(等于九)的因子。目前二十八頁\總數(shù)一百一十七頁\編于十二點

三、正規(guī)子群定義2.4.3設(shè)H是G的一個子群，若對每一個a∈G，恒有aH=Ha，則稱H是G的一個正規(guī)子群或不變子群。該定義表明，群G的正規(guī)子群H是這樣的一個子群：對每一個a∈G，都有aH=Ha。因此，阿貝爾群的每一個子群都是正規(guī)子群。定理2.4.4H是G的正規(guī)子群的充要條件是：對每一個a∈G，恒有a-1

ha∈H，h∈H。目前二十九頁\總數(shù)一百一十七頁\編于十二點

證明若H是G的正規(guī)子群，則由定義可知：

H=He=H(aa-1)=Ha(a-1)=aHa-1

立即得到

aha-1∈H

h∈H

反之，若a-1ha∈H，現(xiàn)證明H是正規(guī)子群。目前三十頁\總數(shù)一百一十七頁\編于十二點

因為對每一個h∈H，都有a-1

ha∈H，因此

a-1

Ha=H

兩邊左乘a，便得

aa-1

Ha=aH

所以

Ha=aH

例如，全體整數(shù)在加法下構(gòu)成群，其中整數(shù)m的一切倍數(shù)所構(gòu)成的一個子群M，就是正規(guī)子群。

目前三十一頁\總數(shù)一百一十七頁\編于十二點

定理2.4.5若H為群G的正規(guī)子群，則H的全體陪集必構(gòu)成群。證明首先，定義陪集之間的乘法運算。設(shè)a=aH，b=bH是H的兩個陪集，我們規(guī)定：以ab為代表的元的陪集ab=(ab)H定義為陪集aH與bH之積，即ab=ab

。為表明這一規(guī)定的合理性，我們必須證明，如此規(guī)定的陪集(ab)H并不因從陪集aH與bH中所選取代表元的不同而改變，即它僅與陪集aH與bH自身有關(guān)，而與所選的代表元是什么無關(guān)。目前三十二頁\總數(shù)一百一十七頁\編于十二點

事實上，若分別從aH和bH中另選兩個代表元，設(shè)為a1和b1，則可令

a1=ah1

b1=bh2

h1h2∈Ha1b1=ah1bh2

由于H是正規(guī)子群，故bH=Hb，因而h1b∈Hb=bH，所以可將h1b寫為

h1b=bh3

h3∈H目前三十三頁\總數(shù)一百一十七頁\編于十二點

因此

a1b1=a(h1b)h2=a(bh3)h2=(ab)(h3h2)=abh

式中，h=h3h2∈H。這表明a1b1∈abH，故

(a1b1)H=abH

目前三十四頁\總數(shù)一百一十七頁\編于十二點

定義2.4.4設(shè)H是群G的正規(guī)子群，于是把H的全體陪集所構(gòu)成的群稱為G關(guān)于H的商群，記為G／H。因此模m的剩余類群也可寫成Z／M，可知模m的剩余類群與商群Z／M同構(gòu)。目前三十五頁\總數(shù)一百一十七頁\編于十二點§2.5子格與劃分

一、子格定義2.5.1若格Λ中的部分格點集合Λ′滿足格的條件，則稱Λ′為Λ的子格。由此可知，子格其實就是Λ中的子群。例如Z2是一個格，則RZ2就是其中的一個子格。它就是二維整數(shù)平面上格點范數(shù)為偶數(shù)的點的集合，如圖2-3中的黑點·集合。

目前三十六頁\總數(shù)一百一十七頁\編于十二點圖2–3Z2格和它的子格目前三十七頁\總數(shù)一百一十七頁\編于十二點

又如m是任一整數(shù)，則m的整數(shù)倍所組成的格mZ就是Z格的子格。它類似于整數(shù)加群中所有m的整數(shù)倍是整數(shù)加群的子群。因此子格mZ與模m的剩余類加群同構(gòu)?？芍?Z子格就是分量的范數(shù)為偶數(shù)的格點集合所組成，它與整數(shù)加群中的偶整數(shù)子群同構(gòu)，也與模2剩余類加群同構(gòu)。目前三十八頁\總數(shù)一百一十七頁\編于十二點

二、劃分(分割)

一個格Λ的陪集用Λ+C表示，這里λ∈Λ，而C是一個n重(類似于陪集首)?？芍?C這一陪集其實就是在n維歐氏空間中，Λ平移一個C。與定理2.4.2相同，若兩個格點的差在Λ中則兩個格點處在同一陪集。目前三十九頁\總數(shù)一百一十七頁\編于十二點

在格Λ中，若以Λ的子格Λ′對Λ劃分等價類，則稱為按模Λ′對Λ進(jìn)行劃分(分割)，用Λ′+C表示。因此每一個格均包含一個劃分，用Λ／Λ′表示。與群一樣，Λ／Λ′也組成一個群。劃分的階數(shù)也就是Λ／Λ′中等價類的數(shù)目，用｜Λ／Λ′｜表示。例如｜Z2／RZ2｜=2，如圖2-3所示。可知按Λ′劃分的每一等價類，其實就是Λ′的一個陪集，從幾何上講就是Λ′的一種平移。目前四十頁\總數(shù)一百一十七頁\編于十二點

用［Λ／λ′］

表示Λ′劃分Λ／Λ′的陪集表示。因此，格Λ中的每一格點λ可唯一地表示成λ=λ′+C，λ∈Λ′，C∈［Λ／Λ′］

是等價類的代表元，也就是陪集表示中的陪集首。所以，λ′=λ-C，與定理的意義相同。稱

Λ=Λ′+［Λ／Λ′］(2.5.1)目前四十一頁\總數(shù)一百一十七頁\編于十二點

為格Λ的陪集分解。如Z2按RZ2的陪集分解，可表示為

Z2=RZ2+［RZ2(10)］

相應(yīng)于圖2-3中黑點與白點集合。在Zn格中，mZn是子格，它的陪集表示是

Zn=mZn+［Zn／mZn］(2.5.2)目前四十二頁\總數(shù)一百一十七頁\編于十二點

三、某些重要的格這里簡單介紹一下在編碼理論中起著重要作用的一些格。

(1)D4(Schlafli)格。D4格是四維整數(shù)格，它由四維整數(shù)空間中偶范數(shù)的格點組成。因此，它是Z4的一個子格，其陪集分解表示為

D4=RZ4+［RZ4+(1010)］

目前四十三頁\總數(shù)一百一十七頁\編于十二點(2)二進(jìn)制格。二進(jìn)制格是最有用的一類格，它與二進(jìn)制分組碼密切相關(guān)。定義2.5.2一個n維實數(shù)格Λ，對某一整數(shù)m，若有一個整數(shù)格2mZn作為子格，則稱格Λ為二進(jìn)制格，m稱為格的2-層次。目前四十四頁\總數(shù)一百一十七頁\編于十二點E8

格是另一個非常重要的模2格，它是八維實數(shù)空間中的一個子格，其最小均方距離d2m(E8)=4，它與以后將講到的距離為4的(8，4)RM碼相對應(yīng)。E8格也稱Gosset格。里奇(Leech)格Λ24是一個很重要的二十四維模4格，它的d2m(Λ24)=8，它與以后講到的擴(kuò)張Golay碼密切相關(guān)。有關(guān)格及格與編碼的詳細(xì)關(guān)系請參閱文［5］

。目前四十五頁\總數(shù)一百一十七頁\編于十二點§2.6線性空間和矩陣

一、線性空間

1.線性空間和子空間由一般的初等數(shù)學(xué)可知，平面上二維矢量的全體構(gòu)成一個二維的矢量空間?？臻g中，三維矢量的全體構(gòu)成三維矢量空間，現(xiàn)加以推廣引入一般的線性空間概念。目前四十六頁\總數(shù)一百一十七頁\編于十二點

定義2.6.1如果域F上的n重元素集合V滿足下述條件時：

(1)V關(guān)于加法構(gòu)成阿貝爾群。

(2)對V中任何元素v和F中任何元素c，cv∈V。我們稱V中元素v為矢量(向量)，F(xiàn)中元素c為純量或標(biāo)量，稱乘c運算為數(shù)乘。目前四十七頁\總數(shù)一百一十七頁\編于十二點(3)分配律成立，對任何u，v∈V，c，d∈F恒有：

c(u+v)=cu+cv

(c+d)v=cv+dv

(4)若c，d∈F

，v∈V，有：

(cd)v=c(dv)1·v=v1∈F

則稱V是域F上的一個n維線性空間或矢量空間，一般用VnF表示。目前四十八頁\總數(shù)一百一十七頁\編于十二點

例L1

實數(shù)域R上的n重數(shù)組全體：{(a1，a2，…，an)；ai∈R}組成一線性空間VnR。例L2GF(2)上的n重數(shù)組全體：{(a1，a2，…，an)；ai∈GF(2)}是一線性空間Vn2。目前四十九頁\總數(shù)一百一十七頁\編于十二點

例L3

系數(shù)取自實數(shù)域R上的次數(shù)小于n次的多項式全體：{(f0+f1x+…+fn-1xn-1)；fi∈R}也組成一個線性空間。上述例中的兩個數(shù)組相加是對應(yīng)的分量相加，數(shù)乘c是對每位分量乘以c，這將在后面更詳細(xì)講到。目前五十頁\總數(shù)一百一十七頁\編于十二點

定義2.6.2若子集V1∈V，且滿足線性空間的條件，則稱V1是V的一個子空間。例L4例L1中所有偶數(shù)分量(ai=2b∈R)所組成的線性空間就是實數(shù)n維數(shù)組線性空間中的一個子空間。例L5例L2

中的第i個分量ai=0的n重數(shù)組全體是它的一個子空間。例L6平面上的通過原點的任一條直線是平面上二維矢量空間中的一個子空間。目前五十一頁\總數(shù)一百一十七頁\編于十二點

定義2.6.3域F上的矢量v1，v2，…，vk的線性組合定義為

u=b1v1+b2v2+…bkvk

bi∈F

例如線性空間V：{(a1a2a3)；ai∈GF(3)}是一個三重數(shù)組。設(shè)v1是(012)，v2是(011)，v3是(002)，b1=2，b2=0，b3=1，則

u=2(012)+0(011)+1(002)=(021)+(000)+(002)=(020)目前五十二頁\總數(shù)一百一十七頁\編于十二點

定理2.6.1線性空間V中矢量v1，v2，…，vk的所有線性組合所構(gòu)成的集合S是V的子空間。證明只要證明S中矢量加法和數(shù)乘封閉即可。令：

w=b1v1+b2v2+…+bkvk

bi∈F，vi∈Vu=c1v1+c2v2+…+ckvk

ck∈F

目前五十三頁\總數(shù)一百一十七頁\編于十二點是S中的任兩個矢量，則

w+u=(b1+c1)v1+(b2+c2)v2+…+(bk+ck)vk

=d1v1+d2v2+…+dkvk(bi+ci)=di∈Faw=ab1v1+ab2v2+…+abkvk

=e1v1+e2v2+…+ekvkabi=ei∈F

仍在集合S中，因此S是一線性空間。目前五十四頁\總數(shù)一百一十七頁\編于十二點

定義2.6.4設(shè)v1，v2，…，vk是線性空間V中的一組非全零矢量，當(dāng)且僅當(dāng)存在有一組不全為零的純量c1，c2，…，ck(ci∈F；i=1，2，…，k)使

c1v1+c2v2+…+ckvk=0

成立時，則稱這組矢量線性相關(guān)。否則，稱這組矢量線性無關(guān)(或稱線性獨立)。目前五十五頁\總數(shù)一百一十七頁\編于十二點

例L7判斷GF(2)上的三重：(010)，(100)，(001)是否線性相關(guān)，關(guān)鍵是看能否找到3個不全為0的數(shù)c1，c2，c3∈GF(2)，使

c1(010)+c2(100)+c3(001)=(000)

成立。顯然找不到，故這3個矢量線性獨立。例L8GF(2)上的三重：(010)，(100)，(110)是否線性相關(guān)？

1(010)+1(100)+1(110)=(000)

所以這3個矢量線性相關(guān)。目前五十六頁\總數(shù)一百一十七頁\編于十二點

定理2.6.2線性空間中，非零矢量v1，v2，…，vk為線性相關(guān)的充要條件是：存在有一個矢量vk，它可以表示為其余矢量的線性組合。該定理的證明比較簡單，讀者可自行證明。下面介紹張成的概念。定義2.6.5線性空間V中的每一矢量，如果可以由其中的一組矢量集S′中的矢量線性組合生成，則我們說S′張成了矢量空間V。目前五十七頁\總數(shù)一百一十七頁\編于十二點

例L9GF(3)上二重數(shù)組：(00)，(10)，(01)，(20)，(21)，(11)，(12)，(22)，(02)組成一個矢量空間V。在其中挑選(11)，(20)兩個矢量組成子集S′，顯然，通過這兩個矢量的線性組合，可以生成中的所有9個矢量。例如：

(21)=1(11)+2(20)=(11)+(10)=(21)

所以(21)、(01)這兩個矢量的線性組合張成了線性空間V。目前五十八頁\總數(shù)一百一十七頁\編于十二點

又例如挑(21)、(01)矢量組成子集S′，顯然，通過它們的線性組合也能生成V中的所有矢量。例如：

(21)=1(21)+0(01)=(21)(12)=2(21)+0(01)=(12)

因此，在V中可以存在有很多組的矢量子集，它們都能張成整個矢量空間。下面我們討論這些都能張成同一空間的矢量組有什么特點。目前五十九頁\總數(shù)一百一十七頁\編于十二點

引理2.6.1如果k個矢量的集合v1，v2，…，vk張成了含有m個線性獨立的矢量u1，u2，…，um的空間V，則k≥m。證明因為v1，v2，…，vk張成V，而u1，u2，…，um在V中，所以

u1=a1v1+a2v2+…+akvk

ai∈F目前六十頁\總數(shù)一百一十七頁\編于十二點

且總有一個ai≠0。設(shè)a1≠0，則

v1=a-11u1-a-11a2v2-…-a-11akvk

所以v1可用u1，v2，…，vk的線性組合表示。因此，V可以由u1，v2，v3，…，vk張成。由于u2∈V，所以u2也可以由u1，v2，…，vk的線性組合表示，即

u2=b1u1+b2v2+…+bkvk

bi∈F目前六十一頁\總數(shù)一百一十七頁\編于十二點

式中，至少有一個bi不為0，設(shè)b2≠0，則v2也可由u1，u2，v3，…，vk的線性組合表示，即

v2=b-12u2-b1b-12u1-…-b-12bkvk

所以，u1，u2，v3，…，vk可以張成整個線性空間。由于u1，u2，…，um是線性獨立的，因此在

uj=c1u1+c2u2+…+cj-1uj-1+cjvj+…+ckvk

中，至少存在有一個不為0的系數(shù)cj，使上述用uj替換vj的過程一直能進(jìn)行下去，直到全部vj用完為止，由于每一步只替換一個v，因此m≤k。目前六十二頁\總數(shù)一百一十七頁\編于十二點

定理2.6.3如果兩組線性獨立矢量集合張成同一空間，則在每一組集合中含有相同多的矢量數(shù)。證明設(shè)一個矢量集合中矢量數(shù)為m，另一個為k，則由引理知m≤k和k≥m，所以m=k。目前六十三頁\總數(shù)一百一十七頁\編于十二點

該定理說明張成同一空間的集合，含有相同的獨立矢量的數(shù)目，在例L9中，(11)、(20)與(21)、(01)這兩組矢量集都能張成GF(3)上的二重矢量組的全體，且這兩組矢量集中的矢量均是線性獨立，獨立矢量數(shù)均是2。目前六十四頁\總數(shù)一百一十七頁\編于十二點

定義2.6.6在任何線性空間中，能張成該空間的線性獨立矢量的集合稱為該線性空間的基底。而稱這組線性獨立矢量的數(shù)目為該線性空間的維數(shù)。若基底中矢量的個數(shù)為有限，則稱為有限維數(shù)線性空間，否則，稱無限維數(shù)線性空間。在例L9中GF(3)上二重數(shù)組構(gòu)成的線性空間維數(shù)為2，所以稱為二維空間。它的基底是(11)，(20)或(21)，(01)等。下面定理給出了如何尋找矢量空間的基底。目前六十五頁\總數(shù)一百一十七頁\編于十二點

定理2.6.4如果V是k維線性空間，則V中任意k個線性獨立的矢量是V的基底。證明用反證法。設(shè)v1，v2，…，vk是V中k個線性獨立矢量，如果它們不能張成整個空間V，則V中必定還有一個矢量v，不能由v1，v2，…，vk的線性組合表示，所以v，v1，v2，…，vk共k+1個矢量是線性獨立的，但這和V是k維線性空間的假設(shè)相矛盾。所以，v1，v2，…，vk必張成整個空間V。目前六十六頁\總數(shù)一百一十七頁\編于十二點

推論如果線性空間V1V2中，且二者有相同的維數(shù)，則V1=V2。證明V1的基底必含在V2中，且是V2中的k個線性獨立的矢量(設(shè)V1和V2的維數(shù)為k)。所以，這k個線性獨立的矢量不僅張成V1，也必張成V2。反之也一樣，V2中的k個線性獨立矢量也必張成V1，故V1=V2。目前六十七頁\總數(shù)一百一十七頁\編于十二點2.n維數(shù)組的內(nèi)積(點積)和正交由前面知，域F上的n維數(shù)組是n重：(a1，a2，…，an)，ai∈F。若我們?nèi)缦露xn維數(shù)組之間的相加和數(shù)乘運算：

+：a+b=(a1，a2，…，an)+(b1，b2，…，bn)=(a1+b1，a2+b2，…，an+bn)ai，bi∈F

數(shù)乘：ca=c(a1，a2，…，an)=(ca1，ca2，…，can)c∈F，ai∈F

則n維數(shù)組全體所構(gòu)成的n維線性空間，它的自然基底是：

(10…0)，(010…0)，(0010…0)，…，(00…01)目前六十八頁\總數(shù)一百一十七頁\編于十二點

定義2.6.7兩個n維數(shù)組a、b的內(nèi)積(或點積)表示為

a·b=(a1，a2，…，an)·(b1，b2，…，bn)=a1b1+a2b2+…+anbn

ai，bi∈F

它是一個純量。如果兩個矢量a、b的內(nèi)積a·b=0，則a、b矢量互為正交。顯然

a·b=b·a

a·(b+c)=a·b+a·c目前六十九頁\總數(shù)一百一十七頁\編于十二點3.線性結(jié)合代數(shù)定義2.6.8域F上的有限維線性空間A，若元素之間定義了乘法，且有如下性質(zhì)：

(1)乘法封閉。對每一個a，b∈A，恒有ab∈A。

(2)乘法結(jié)合律成立。對每一個a，b，c∈A恒有

(ab)c=a(bc)。

(3)分配律成立。

①a(αb+βc)=α(ab)+β(ac)②(αb+βc)a=α(ba)+β(ca)α，β∈F,a，b，c∈A目前七十頁\總數(shù)一百一十七頁\編于十二點

則稱A是一個線性結(jié)合代數(shù)。它的階數(shù)定義為它作為線性空間時的維數(shù)。如果A關(guān)于乘法有逆元(0元除外)，則稱A為可除代數(shù)。從上面定義看來，線性結(jié)合代數(shù)非常像一個環(huán)。目前七十一頁\總數(shù)一百一十七頁\編于十二點

二、矩陣從環(huán)R中選出m×n個元素aij(i=1，2，…，m；j=1，2，…，n)，按一定次序排列成如下m行n列的方陣：稱為環(huán)R上的一個m×n階矩陣，用Am×n或［aij］m×n(有時以簡寫A或［aij］)表示之。目前七十二頁\總數(shù)一百一十七頁\編于十二點

在今后學(xué)習(xí)的糾錯碼論中，矩陣內(nèi)的第i行第j列元素aij一般取自域上，今后我們僅討論域上的矩陣。下面我們首先介紹矩陣的基本運算，然后介紹行空間與列空間的概念。矩陣中的行數(shù)m與列數(shù)n通常情況并不相等。如m=n，則稱為方陣，n稱為方陣的階。目前七十三頁\總數(shù)一百一十七頁\編于十二點1.矩陣的轉(zhuǎn)置、相等、相加和相乘m×n階矩陣A的轉(zhuǎn)置矩陣AT(或A′)表示為

AT=［aij］T=［aji］

它是把A矩陣的第一行變成AT矩陣的第一列，第二行變成第二列等等而得到的。若A為m×n階矩陣，則AT為n×m階矩陣。

目前七十四頁\總數(shù)一百一十七頁\編于十二點

兩個m×n階矩陣［aij］和［bij］相等，定義為它們對應(yīng)位的元素相等，即

aij=bij

i=1，2，…，m；j=1，2，…，n

兩個m×n階矩陣［aij］和［bij］相加，定義為它們對應(yīng)位元素相加，即目前七十五頁\總數(shù)一百一十七頁\編于十二點目前七十六頁\總數(shù)一百一十七頁\編于十二點m×n階矩陣［aij］和域元素c∈F相乘之積定義為m×n階矩陣［aij］和n×k階矩陣［bij］相乘定義為目前七十七頁\總數(shù)一百一十七頁\編于十二點式中是［aij］矩陣的第i行與［bij］矩陣的第j列的內(nèi)積，因此要兩個矩陣能相乘，第一個矩陣的列數(shù)與第二個矩陣的行數(shù)必須相等，否則不能相乘。目前七十八頁\總數(shù)一百一十七頁\編于十二點例M1實數(shù)域上的兩個矩陣相乘目前七十九頁\總數(shù)一百一十七頁\編于十二點

應(yīng)注意的是，在相乘或相加運算中，矩陣中元素之間的運算必須按域的運算規(guī)則進(jìn)行。若兩個矩陣［aij］、［bij］為n×n階矩陣，則可以交換相乘，但結(jié)果一般不相同，即

［aij］［bij］≠［bij］［aij］目前八十頁\總數(shù)一百一十七頁\編于十二點

例M2在GF(2)上的兩個方陣相乘，例如而目前八十一頁\總數(shù)一百一十七頁\編于十二點顯然也就是說，矩陣相乘不滿足交換律。目前八十二頁\總數(shù)一百一十七頁\編于十二點

下面介紹分塊矩陣概念。如果我們把矩陣的每一行(或每一列)看成一個

n(或m)維數(shù)組，或者行(列)矢量，則可把一個m×n階矩陣［aij］表示如下：目前八十三頁\總數(shù)一百一十七頁\編于十二點或目前八十四頁\總數(shù)一百一十七頁\編于十二點

像這種表示方法稱為分塊矩陣的一種表示。因兩個矩陣［aij］和［bjk］相乘也可表示成

根據(jù)矩陣相乘的規(guī)則，顯然只有［aij］矩陣中行矢的維數(shù)等于［bjk］中列矢的維數(shù)時，相乘才有意義，否則不能相乘。目前八十五頁\總數(shù)一百一十七頁\編于十二點

矩陣不僅可以按列或按行進(jìn)行分塊，也可以按照需要，以幾行幾列分塊。如目前八十六頁\總數(shù)一百一十七頁\編于十二點

可按陣中虛線所示劃分成4塊。在分塊矩陣表示下，兩個矩陣［aij］和［bjk］的相乘可寫成

根據(jù)矩陣乘法規(guī)則，必須保證分塊矩陣中每一塊矩陣相乘有意義，即只有Aij

的列數(shù)等于Bjk

的行數(shù)時，這兩個分塊才能相乘。目前八十七頁\總數(shù)一百一十七頁\編于十二點2.矩陣的秩定義2.6.9m×n階矩陣A的行(列)空間是以A的行(列)作為矢量所張成的空間，它是n(m)維矢量空間中的一個子空間。行(列)空間的維數(shù)叫做行(列)秩，它等于行(列)空間中的線性無關(guān)的最大行(列)數(shù)(即基底中的矢量數(shù))。上面定義了矩陣的行(列)秩概念，而矩陣的秩定義為：矩陣中不等于零的子式(矩陣的子行列式)的最大階數(shù)，或定義為行(列)秩。今后我們主要用后者的定義計算矩陣的秩。目前八十八頁\總數(shù)一百一十七頁\編于十二點例M3在GF(2)上的以下矩陣：由行矢：(10001)，(01010)，(10101)張成的行空間共有8個矢量：(10001)，(01010)，(10101)，(11011)，(00100)，(11111)，(01110)及(00000)。顯然，這3個行矢是該行空間的一組基底，所以是五維空間的一個三維子空間。目前八十九頁\總數(shù)一百一十七頁\編于十二點

由列矢(101)，(010)，(001)，(010)，(101)，張成的列空間也有8個矢量：(101)，(010)，(001)，(110)，(111)，(100)，(011)，(000)。其中(101)，(010)，(001)是一組基底。故列秩為3。由此可知，矩陣的秩為3。目前九十頁\總數(shù)一百一十七頁\編于十二點3.初等行運算矩陣的初等行運算定義為：(1)交換矩陣任意兩行(或兩列)。例如把以下矩陣交換第一行與第二行，變?yōu)槟壳熬攀豁揬總數(shù)一百一十七頁\編于十二點這相當(dāng)于用以下的m×m階矩陣左乘A矩陣。目前九十二頁\總數(shù)一百一十七頁\編于十二點若稱主對角線元素均為1，其余元素均為0的矩陣

為m×m階單位方陣，則交換矩陣Am×n的第j和第i行，就是把Im×m矩陣交換第j行和第i行后左乘Am×n矩陣得到的。而交換矩陣Am×n的第j列和第k列，就是把In×n矩陣交換第j列和第k列后右乘Am×n得到的。目前九十三頁\總數(shù)一百一十七頁\編于十二點例M4交換以下矩陣的第二與第三行為目前九十四頁\總數(shù)一百一十七頁\編于十二點(2)以非0元素c∈F，乘以任一行。如矩陣Am×n

用c∈F乘以矩陣Am×n的第二行，則為目前九十五頁\總數(shù)一百一十七頁\編于十二點這相當(dāng)于進(jìn)行以下運算：目前九十六頁\總數(shù)一百一十七頁\編于十二點(3)任意第j行的c倍加至第k(≠j)行。這種運算，相當(dāng)于把Im×m階單位方陣的第j行的1換成c，與第k行相加后，左乘Am×n矩陣。例如：目前九十七頁\總數(shù)一百一十七頁\編于十二點

定義2.6.10完成初等行運算的矩陣稱為初等矩陣。由此定義可知，初等行運算的逆也是同類型的初等行運算，得到的矩陣也是初等矩陣。例如：目前九十八頁\總數(shù)一百一十七頁\編于十二點就是(3)例中的逆運算，而就是(2)例中的逆運算，而這些例中的左乘Am×n矩陣的方陣，例如：等均稱為初等矩陣。目前九十九頁\總數(shù)一百一十七頁\編于十二點

定理2.6.5如果一個矩陣可以由另一矩陣逐次施行初等運算得到，則該二矩陣有同樣的行空間，稱這兩個矩陣為等價矩陣。目前一百頁\總數(shù)一百一十七頁\編于十二點

證明在(1)、(2)初等運算中定理顯然成立?，F(xiàn)檢驗(3)，設(shè)矩陣A3是A作第(3)種行運算得到的，它的行空間為V3，A的行空間為V。由于A3中改變了的行僅是A中相應(yīng)行的線性組合，所以A3中行的線性組合就是A中行的線性組合，故V3V。但是A可由A3作逆變換得到，所以A的行空間V在A3的行空間V3內(nèi)，

VV3，由此得到V3=V。目前一百零一頁\總數(shù)一百一十七頁\編于十二點

推論2.6.2初等行運算中，矩陣的秩不變。上面所述的3條初等行運算和定理，同樣也適用于初等列運算。今后，初等行運算或初等列運算統(tǒng)稱為矩陣的初等運算。目前一百零二頁\總數(shù)一百一十七頁\編于十二點4.梯形標(biāo)準(zhǔn)(典型)陣為了很快地得到矩陣的秩，可以通過初等運算把矩陣化成梯形標(biāo)準(zhǔn)陣或梯形典型陣。定義2.6.11如下形式的矩陣稱為梯形標(biāo)準(zhǔn)陣：

1°非0行自左算起，第一個非0元素為1。

2°包含這一個首項的，列的其余元素均為0。

3°下一行的首項元素，在上一行首項元素的右邊，所有0行均在非0行的下面。

目前一百零三頁\總數(shù)一百一十七頁\編于十二點例M5如下兩個矩陣：都是梯形典型陣。顯然，任一矩陣的梯形標(biāo)準(zhǔn)陣是唯一的，梯形標(biāo)準(zhǔn)陣的非0行均線性無關(guān)，所以梯形標(biāo)準(zhǔn)陣中非0行的數(shù)目，就是行空間的維數(shù)，也是矩陣的秩。目前一百零四頁\總數(shù)一百一十七頁\編于十二點例M6求GF(2)上矩陣的秩。把該矩陣進(jìn)行初等行運算化成梯形典型陣目前一百零五頁\總數(shù)一百一十七頁\編于十二點第1行與第2行交換第2行加第3行為第3行第3行與第4行相加為第4行由此可知，該矩陣只有三行線性獨立，故矩陣的秩是3。目前一百零六頁\總數(shù)一百一十七頁\編于十二點

推論2.6.3任何矩陣的秩等于其等價梯形標(biāo)準(zhǔn)陣中非0行的數(shù)目。

5.奇異與非奇異矩陣定義2.6.12n階方陣的每行若為線性獨立，則稱該方陣為非奇異(或稱滿秩)矩陣；否則，稱為奇異(非滿秩)矩陣。目前一百零七頁\總數(shù)一百一十七頁\編于十二點

顯然，n×n階