pn矩陣類中跡相異pn矩陣集的構(gòu)造與mdpn值的確定

pn矩陣類中跡相異pn矩陣集的構(gòu)造與mdpn值的確定

0跡相異矩陣定義設(shè)置1n矩陣{a.apn={a.a，并將每行的列從1.2，以形成n的不同排列，以形成n的對稱排列}（n是1的最大值的自然數(shù)）。當n為導數(shù)時，pn.p2m和n為奇數(shù)時，pn.p2m-1，m.1，2，……。定義2稱主對角線元素分布不同的Pn矩陣為跡相異矩陣.定義3Pn矩陣集合中所含跡相異矩陣的數(shù)目記為MD[Pn].定義4P2m矩陣中滿足下列條件的矩陣類(其中e1,e2,…,e2m為1,2,…2m的一個排列):1°主對角線上含有i個相異的元素;2°主對角線上i個相異元素為e1,e2,…,ei;3°主對角線上i個相異e1,e2,…,ei出現(xiàn)的次數(shù)分別為k1,k2,…,ki,且k1+k2+…+ki=2m,kj(1≤j≤i)為偶數(shù);分別記作:1°Pi2mi2m;2°Pi2m—e1?e2???ei;3°Pi—k1+k2+…+ki2m—e1,e2,…,ei.本文未定義的概念見文獻[1～3].1ei、ej和k組合成權(quán)的同時互換定理1當且僅當圖G滿足下列條件:1°G為完全對稱有向圖;2°圖中每個頂點有且僅有一條自邊;3°每個頂點進入的(出來的)n條邊權(quán)為1,2,…,n的一個排列時,其連接矩陣為Pn矩陣.稱滿足上述條件的圖為G*圖.推論1(矩陣跡的圖論構(gòu)造法)G*圖中任意調(diào)換頂點Vi、Vj的位置后仍為G*圖.推論2?A∈Pn,任意調(diào)換A矩陣中的ei、ej的全部位置,新矩陣仍為Pn矩陣.證明調(diào)換A中兩元素ei、ej的全部位置,相當于在圖G(A)中邊權(quán)為ei、ej的所有邊權(quán)互換,顯然互換后的新圖仍然滿足定理1的條件,仍為G*圖,故其連接矩陣B∈Pn.定理2(P2m矩陣跡的結(jié)構(gòu))?A∈P2m,則A矩陣中主對角線上每個元素一定以偶次出現(xiàn).推論(P2m矩陣跡的結(jié)構(gòu))?A∈P2m,A矩陣主對角線上含不同元素的個數(shù)i滿足1≤i≤m.證明用反證法.若A中主對角線上所含不同元素的個數(shù)大于m,則由定理2可知,每個元素以偶次出現(xiàn),故主對角線上元素(包括重數(shù))應(yīng)大于2m,與A∈P2m矛盾.證畢.定理3對于任一自然數(shù)m,下列結(jié)論成立(1)Pi2m∩Pj2m=Φ1≤i≤m1≤j≤mi≠j(2)m∪i=1Ρi2m=Ρ2m證明1°因為?A∈Pi2m,B∈Pj2m,i≠j,A的主對角線上有i個相異的元素,B的主對角線上有j個相異的元素,i≠j,故B?Pi2m,A?Pj2m,則Pi2m∩Pj2m=Φ.2°由定理3的推論可知,?A∈P2m,A矩陣中對角線上不同元素的個數(shù)只能為i,并且1≤i≤m,故A∈Pi2m.而?A∈Pi2m,1≤i≤m,因為Pi2m?P2m,所以有A∈P2m.定理4?A∈P12m,A中元素ai?i與ai?j,aj?j與aj?i同時互換后,新矩陣B∈P2m.證明由P12m矩陣的定義可知,ai?j=aj?i,ai?i=aj?j,故互換后,每行每列仍由2m個元素的不同排列構(gòu)成,且對稱性不變,故B∈P2m矩陣.證畢.推論?A∈P12m,則A中必有K組元素(1≤K≤m)可同時互換,互換后矩陣B∈P2m(由定理2的推論與定理4可證).2構(gòu)造矩陣的構(gòu)造由定理3可知,構(gòu)造P2m矩陣亦即構(gòu)造Pi2m矩陣(1≤i≤m).定理5設(shè)e1,e2,…,e2m為1,2,…,2m的一個排列且為矩陣的第一行,則按下列方法構(gòu)造的矩陣屬于P12m—e1:ai?j={ei+j-1?i+j-1≤2m?1≤i<2mei+j-2mi+j-1>2m1≤j<2mi≠je1i=je2i-1j=2m?1<i≤me2i-2mj=2m?m<i<2me2j-1i=2m?1<j≤me2j-2mi=2m?m<j<2m證明先證每行由e1,e2,…,e2m的不同排列構(gòu)成,用反證法.設(shè)第r行與第k行排列相同,即ar?j=ak?j,r≠k,1≤j≤2m.情況1°ar?j=er+j-1ak?j=ek+j-1則er+j-1=ek+j-1,即r=k,矛盾.情況2°ar?j=er+j-2mak?j=ek+j-2m則er=ek,即r=k,矛盾.情況3°ar?j=er+j-1ak?j=ek+j-2m且1≤k<2m,1≤r<2m,則er+j-1=ek+j-2m,r-1=k-2m,然而r-1≥0,k-2m<0與等式矛盾.情況4°ar2m=e2r-1ak2m=e2k-1則e2r-1=e2k-1,即r=k,矛盾.情況5°ar2m=e2r-1ak2m=e2k-2m1<r≤m,m≤k<2m,則e2r-1=e2k-2m,即2r-1=2k-2m.然而2r-1為奇數(shù),2k-2m為偶數(shù),故等式不成立.情況6°ar2m=e2r-2mak2m=e2k-2m則e2k-2m=e2k-2m,即2r=2k,r=k,矛盾.情況7°ar?j=er+j-1ak?j=a2m?j=e4m-1則er+j-1=e4m-1,r+j=4m,與r+j<2m,矛盾.情況8°ar?j=er+j-1ak?j=a2m?j=e4m-2m則er+j-1=e2m,r+j-1=2m,與r+j<2m,矛盾.故所構(gòu)造的矩陣每行由e1,e2,…,e2m的不同排列構(gòu)成.同理可證每列由e1,e2,…,e2m的不同排列構(gòu)成.另外由構(gòu)造法可知ai?j=aj?i,且主對角線上元素皆為e1,因此,所構(gòu)造的矩陣為P12m—e1矩陣.證畢.定理6對任意自然數(shù)n≥1,跡相異Pn矩陣的數(shù)目有且僅有下式成立:ΜD[Ρn]={n!n=1,3,5,?n+n2∑i=2Cinn!i∏j=1kj!r∏j=1bj!n=2,4,6,?為證明定理6,先證明如下引理.引理1(P12m矩陣類的構(gòu)造)?自然數(shù)m≥2,存在且僅存在2m個跡相異的P12m矩陣.證明1°由P12m矩陣的性質(zhì),顯然MD[Pn]≤2m.2°當m≥2時,由定理5,構(gòu)造矩陣A∈P12m—e1,由定理1的推論2可知,分別互換矩陣中e1與e2,e3,…,e2m元素的全部位置后,得到的2m-1個新矩陣仍屬于P12m矩陣,因此共得到2m個主對角線元素分布互不相同的P12m.綜合1°、2°即得MD[P12m]=2m.證畢.引理2(Pi2m矩陣類的構(gòu)造)?i∈2≤i≤m,m≥2,則ΜD[Ρi2m]=Ci2m(2m)!i∏j=1kj!r∏j=1bj!其中b1,b2,…,br為k1,k2,…,ki中每個重復數(shù)的個數(shù).證明1°(一個Pi2m矩陣的構(gòu)造(1<i≤m,m≥2))由定理5做矩陣A∈P12m—e1,要構(gòu)造一個Pi—k1+k2+?+ki2m—e1?e2??ei類矩陣,即元素e1,e2,e3,…,ei在主對角線上分別出現(xiàn)k1,k2,…,ki次(不考慮元素的排列次序).根據(jù)定理1的推論2與定理4的推論中的方法,使矩陣A中主對角線元素與所需元素互換,即得矩陣B,且B∈Pi—k1+k2+?+ki2m—e1?e2???ei.2°由1°中的矩陣B,做圖G(B),對B中主對角線元素的任意一個不同的排列,調(diào)換G(B)中頂點v1,v2,…,v2m,使頂點自邊權(quán)與之對應(yīng).做出對應(yīng)圖的連接矩陣C,則C∈Pi—k1+k2+?+ki2m—e1?e2???ei.由此方法共可構(gòu)造主對角線元素排列相異的Pi—k1+k2+?+ki2m—e1?e2???ei矩陣(2m)!/(k1!k2!…ki!)個.3°由于Pi—k1+k2+?+ki2m—e1?e2???ei矩陣中,主對角線上i個元素e1,e2,…,ei出現(xiàn)的次數(shù)隨著k1,k2,…,ki的不同排列而改變,因此對應(yīng)的矩陣相異,而kj(1≤j≤i)中可能有些數(shù)相同,設(shè)有r個數(shù)重復,且重復次數(shù)依次為b1,b2,…,br,則i個數(shù)kj(1≤j≤i)的排列總數(shù)為i!/(b1!b2!…br!),故可構(gòu)造跡相異Pi2m—e1,e2,…,ei矩陣的數(shù)目為(2m)!i!i∏j=1kj!r∏j=1bj!.4°矩陣Pi2m(m≥2)的主對角線上含有i個不同元素,且是e1,e2,…,e2m中i個元素的一種組合,其組合數(shù)共有Ci2m種,即?i∈2≤m,至少可構(gòu)造Pi2m矩陣的數(shù)目為Ci2m(2m)!i!i∏j=1kj!r∏j=1bj!5°顯然,由上述構(gòu)造過程以及組合理論可知所構(gòu)造的跡相異的Pi2m矩陣數(shù)目與MD[Pi2m]相等,即ΜD[Ρi2m]=Ci2m(2m)!i!i∏j=1kj!r∏j=1bj!(1≤i≤m,m≥2)引理3設(shè)n為大于1的奇數(shù),至少存在n!個Pn矩陣,主對角線上