The Extremal Matrix of RS-matrices.pdf

1、華南師范大學碩士學位論文TheExtremalMatrixofRSmatrices姓名：譚學忠申請學位級別：碩士專業(yè)：運籌學與控制論指導教師：柳柏濂2003.6.11introductionandnotationLetA=(a／j)bea(0，1)matrixofordernandlet厶denotethesetfl，2，～，艇；Forgivensubsets璉and多of磊，8￡建添，躦bethesubmatrixofAconsist

2、ingofallrowsnumberedo，ot∈O／，andallcolumnsnumbered黟如∈8Aissaidtobereducible娃thereexistnonemptysubsets“，0of霸suchthai。＆n盧一垂，“u聲一厶，A[a，盧j=00tlmrwise。Aisirreduci接eEquivalentlyAisreducibleifthereexistapermutationmatrixPslchthat

3、pAP驢#善三)，whereBandDaresquarematricesSincetheprincipaldiagonall’8havenoeffectontheirreducibilityofA，wesupposeinthispaperthat魄=0，i=1，2，，骼unlessspecialIyindicateAis‘theadjacencymatrixofadigraphGwithnverticesanddarcsAisirred

4、ucihle蠢andor&vif溉di豁aphisstrongiyconnected弒、AprimalsubgraphOfGisthegraphobtainedfromGbydeletingonecortex，say，andallthearcsgoingoutfromiorintoitTheadjacencymatrixcorrespondingtothisprimalsubgraphistheprincipalsubma￡rix囊of

5、矗obtained姆deletingrowandcolumniofAInRef[4]，BSchwarzconjecturedthatifGisastronglyconnecteddigraphwithoutloops，with囂≥3verticesand纛arc8，where鎏《囂～t)i21i≤g≤禮(憶一1)，thenGhasastronglyconnectedprimalsubgraphHeverifiedhisCOnjectur

6、efor丸∞3，4，5TheCOnjectureisageneralizationofaresultofBrualdiandHwaag《蕊，Lemmal2b；；。，foragiven(011)matrixA；(aij)ofordern，wedenoteby鱷(A)ands(^)，i—l，，‰thenumberoftheoffdiagonalOsandls，respectivelyintheunionofrowandcolttmniofA

7、，and謗s棼；wedenotethetotalnumberofISinAObviously霹馨》4(A》=2《魏～≥)，i一1，，％(1j’Hs(以)=；∑si(舢(2)。蛹iInRef[1]，DavidLondonshowedthefollowingtheoremwhichimpliedthevalidityoftheconjectureforallnLemma1。1LetA≈垃話》如玨韓irreducible簿≯matrix醇od

8、er％satisfyingait∞0，i；1，一，禮，Ifs(A)≥【n(n～1)／2】1，thenthereexist《least蜉囂￡irreducibleprincipalsubmatrizA《of丑，Thisisabeautifulresult，Howeverthelowerboundofs(A)isnotnecessarM孫r囂=5，DavidLandonshowedthatLemma1，lholdsfors(A)≥10，an