addition18jjj.com

RelativePerturbationTheory:IEigenvalueandSingularValueVariationsRen-CangLiMathematicalScienceSectionOakRidgeNationalLaboratoryP.
O.
Box2008,Bldg6012OakRidge,TN37831-6367li@msr.
epm.
ornl.
govLAPACKworkingnotes84rstpublishedJuly,1994,revisedJanuary,1996AbstractTheclassicalperturbationtheoryformatrixeigenvalueandsingularvalueprob-lemsprovidesboundsontheabsolutedierencesbetweenapproximateeigenvaluessingularvaluesandthetrueeigenvaluessingularvaluesofamatrix.
Theseboundsmaybebadnewsforsmalleigenvaluessingularvalues,whichtherebysuerworserelativeuncertaintythanlargeones.
However,therearesituationswhereevensmalleigenvaluesaredeterminedtohighrelativeaccuracybythedata,muchmoreaccu-ratelythantheclassicalperturbationtheorywouldindicate.
Inthispaper,westudyhoweigenvaluesofamatrixAchangewhenitisperturbedtoeA=D1AD2andhowsingularvaluesofanonsquarematrixBchangewhenitisperturbedtoeB=D1BD2,whereD1andD2areassumedtobeclosetounitarymatricesofsuitabledimensions.
Itisprovedthatunderthesekindsofperturbations,smalleigenvaluessingularvaluessuerrelativechangesnoworsethanlargeeigenvaluessingularvalues.
Wehavebeenabletoextendmanywell-knownperturbationtheorems,includingHoman-WielandttheoremandWeyl-Lidskiitheorem.
Asapplications,weobtainedboundsforpertur-bationsofgradedmatricesinbothsingularvalueproblemsandnonnegativedeniteHermitianeigenvalueproblems.
Thismaterialisbasedinpartuponworksupported,duringJanuary,1992August,1995,byArgonneNationalLaboratoryundergrantNo.
20552402andbytheUniversityofTennesseethroughtheAdvancedResearchProjectsAgencyundercontractNo.
DAAL03-91-C-0047,bytheNationalScienceFoundationundergrantNo.
ASC-9005933,andbytheNationalScienceInfrastructuregrantsNo.
CDA-8722788andCDA-9401156,andsupported,sinceAugust,1995,byaHouseholderFellowshipinScienticComputingatOakRidgeNationalLaboratory,supportedbytheAppliedMathematicalSciencesResearchProgram,OceofEnergyResearch,UnitedStatesDepartmentofEnergycontractDE-AC05-96OR22464withLock-heedMartinEnergyResearchCorp.
Partofthisworkwasdoneduringsummerof1994whiletheauthorwasatDepartmentofMathematics,UniversityofCaliforniaatBerkeley.
1Ren-CangLi:RelativePerturbationTheory21IntroductionTheclassicalperturbationtheoryformatrixeigenvalueproblemsprovidesboundsontheabsolutedierencesj,ejbetweenapproximateeigenvalueseandthetrueeigenvaluesofasymmetricmatrixA.
Wheneiscomputedusingstandardnumericalsoftware,theboundsonj,ejaretypicallyonlymoderatelybiggerthankAk14,33,42,whereistheroundingerrorthresholdcharacteristicsofthecomputer'sarithmetic.
Theseboundsarebadnewsforsmalleigenvalues,whichtherebysuerworserelativeuncertaintythanlargeones.
Generally,theclassicalerrorboundsarebestpossibleifperturbationsarearbitrary.
However,therearesituationswhereperturbationshavespecialstructuresandunderthesespecialperturbationsevensmalleigenvaluessingularvaluesaredeterminedtohighrel-ativeaccuracybythedata,muchmoreaccuratelythantheclassicalperturbationtheorywouldindicate.
Therelativeperturbationtheoryisthencalledfortoexploitthesituationstoprovideboundsontherelativedierencesbetweeneand.
ThedevelopmentofsuchatheorywentbacktoasearlyasKahan18,1966andisbecomingaveryactiveresearchareainthelastsixyearsorsoandeversince1,6,7,8,9,10,11,13,15,21,29,34.
Inthispaper,wedevelopatheorybyaunifyingtreatmentthatsharpensexistingboundsandcoversalmostallpreviouslystudiedcases.
1.
1WhattobeCoveredThispaperdealswithperturbationsofthefollowingkinds:Eigenvalueproblems:1.
AandeA=DADforHermitiancase,whereDisnonsingularandclosetotheidentitymatrixormoregenerallytoaunitarymatrix;2.
AandeA=D1AD2forgeneraldiagonalizablecase,whereD1andD2arenonsingularandclosetotheidentitymatrixormoregenerallytosomeunitarymatrix;3.
A=SHSandeA=SeHSforthegradednonnegativeHermitiancase,whereitisassumedthatHandeHarenonsingularandoftenthatSisahighlygradeddiagonalmatrixthisassumptionisnotnecessarytoourtheorems.
Singularvalueproblems:1.
BandeB=D1BD2,whereD1andD2arenonsingularandclosetoidentitymatricesormoregenerallytounitarymatrices;2.
B=GSandeB=eGSforthegradedcase,whereitisassumedthatGandeGarenonsingularandoftenthatSisahighlygradeddiagonalmatrixthisassumptionisnotnecessarytoourtheorems.
Theseperturbationscovercomponent-wiserelativeperturbationstoentriesofsymmetrictridiagonalmatriceswithzerodiagonal8,18,entriesofbidiagonalandbiacyclicmatricesRen-CangLi:RelativePerturbationTheory31,7,8,andperturbationsingradednonnegativeHermitianmatrices9,29,ingradedmatricesofsingularvalueproblems9,29andmore10.
Whatdistinguishesthesepertur-bationsfromthemostgeneraladditiveperturbationsstudiedbytheclassicalperturbationtheoryistheirmultiplicativestructures.
Forthisreason,wecallsuchperturbationsmulti-plicativeperturbations.
Theaboveperturbationsforgradedmatricescanbetransformedtotakeformsofmultiplicativeperturbationsaswillbeseenfromproofsofthispaper.
AdditiveperturbationsarethemostgeneralinthesensethatifAisperturbedtoeA,onlypossibleknowninformationisonsomenormofAdef=eA,A.
Suchperturbations,nomatterhowsmall,cannotguaranteerelativeaccuracyineigenvaluessingularvaluesofthematrixunderconsiderations.
Forexample,Aissingular,theneAcanbemadenonsingularnomatterhowsmallanormofAis;thussomezeroeigenvaluesareperturbedtononzeroonesandthereforelosetheirrelativeaccuracycompletely.
Retaininganyrelativeaccuracyofzeroatallendsupnotchangingit.
1.
2NotationWewilladoptthisconvention:capitallettersdenoteunperturbedmatricesandcapitalletterswithtildedenotetheirperturbedones.
Forexample,XisperturbedtoeX.
Throughoutthepaper,capitallettersareformatrices,lowercaseLatinlettersforcolumnvectorsorscalars,andlowercaseGreeklettersforscalars.
Thefollowingisadetailedlistofourspecialnotation.
Otherswillbeintroducedwhenitappearsforthersttime.
Cmn:thesetofmncomplexmatrices;Cm:Cm1;C:C1;Rmn:thesetofmnrealmatrices;Rm:Rm1;R:R1;Un:thesetofnnunitarymatrices;0m;n:themnzeromatrixwemaysimplywrite0instead;In:thennidentitymatrixwemaysimplywriteIinstead;X:thecomplexconjugateofamatrixX;X:thesetoftheeigenvaluesofX,countedaccordingtotheiralgebraicmultiplicities;X:thesetofthesingularvaluesofX,countedaccordingtotheiralgebraicmultiplicities;minX:thesmallestsingularvalueofX2Cmn;maxX:thelargestsingularvalueofX2Cmn;kXk2:thespectralnormofX,i.
e.
,maxX;kXkF:theFrobeniusnormofX,i.
e.
,rPi;jjxijj2,whereX=xij;kXkp:thep-HolderoperatornormofXtobedenedlater;jjjXjjj:someunitaryinvariantnormofXtobedenedlater.
Ren-CangLi:RelativePerturbationTheory41.
3OrganizationofthePaperWerstinx2summarizewhatwehaveaccomplishedinthispaper,togetherwiththecorrespondingwell-knownclassicalperturbationtheoremsthatarebeingextended.
Inx3,wedenetwokindsofrelativedistancesp1p1andwhichwillbeheavilyusedintherestofthispaper.
VariouspropertiesthatarerelevanttoourrelativeperturbationtheoryarestudiedinthesectionandinAppendixAwhereitisprovedpisindeedametriconR.
Someoftheclassicalperturbationtheoremsthatwillbeextendedtoourrelativeperturbationtheoryarepresentedandbrieydiscussedinx4.
Wedevotetwosectionstopresentanddiscussmaintheoremsofthispaper:x5isfortheoremsconcerningnonnegativedenitematrixeigenvaluevariationsandsingularvaluevariations;whilex6isfortheoremsconcerningnon-denitematrixeigenvaluevariations.
Proofsarepostponedtolatersectionsxx8|10.
Wediscussotherdevelopmentsinliteratureonrelativeperturbationtheoriesinx7.
Wewilltouchhowourrelativeperturbationtheoremscanbeappliedtogeneralizedeigenvalueproblemsandgeneralizedsingularvalueproblemsinx11.
Finally,wepresentourconclusions.
2SummaryofResultsTohelpthereadertograspquicklywhatwehaveaccomplishedinthispaper,wegivehereatabletosummarizepartiallythesimpliedsometimesweakenedversionsofourtheoremsincomparisonwiththeircorrespondingwell-knownclassicaltheoremsinliterature.
Fullstatementofthesetheoremsandtheirstrongerversionswillbegiveninx5andx6.
AtheoremofOstrowskiin1959andmorerecentdevelopmentsontherelativeperturbationtheorywillbediscussedinx7.
Inwhatfollows,westicktothenotation:1.
A;eA2CnnwitheigenvaluesA=f1;;ngandeA=fe1;;eng:2.
1Whenever,alli'sandej'sarereal,weorderthemdescendingly12n;e1e2en:2.
22.
B;eB2CmnwithsingularvaluesB=f1;;ngandeB=fe1;;eng2.
3orderedsothat12n0;e1e2en0;2.
4Inthetable,alwaysstandsforsomepermutationsoff1;2;;ng,andtworelativedistancespandaredenedfor;e2Cbyp;e=j,ejppjjp+jejpfor1p1,and;e=j,ejpjej;withconvention0=0=0forconvenience.
Fordetailedstudiesofthem,seex3.
Ren-CangLi:RelativePerturbationTheory5Table3.
1.
PerturbationTheoremsforEigenvaluesClassicalBoundsNewRelativeBoundsAandeADeniternPi=1ji,eij2keA,AkFTheorems4.
1and4.
3eA=DADrnPi=1hi;eii2kD,D,1kFTheorem5.
1AandeADeniteji,eijkeA,Ak2Theorem4.
3eA=DADi;eikD,D,1k2Theorem5.
1AandeAHermitianrnPi=1ji,eij2keA,AkFTheorems4.
1and4.
3eA=DADrnPi=1h2i;eii2pkI,Dk2F+kI,D,1k2FTheorem6.
3AandeAHermitianji,eijkeA,Ak2Theorem4.
3eA=DAD1i;eikI,DDk2,i;eikI,DDk2minDsee7.
3and7.
4AandeAnormalrnPi=1ji,eij2keA,AkFTheorem4.
1eA=D1AD2rnPi=1h2i;eii2minqkI,D1k2F+kI,D,12k2F;qkI,D,11k2F+kI,D2k2FTheorem6.
2A=XX,1eA=eXeeX,1,emaybecomplexrnPi=1ji,eij2XeXkeA,AkFTheorem4.
2eA=D1AD2rnPi=1h2i;eii2XeXminqkI,D1k2F+kI,D,12k2F,qkI,D,11k2F+kI,D2k2FTheorem6.
1A=XX,1eA=eXeeX,1anderealnonnegativeji,eijqXeXkeA,Ak2Theorem4.
4eA=D1AD2pi;eiXeXminqpkI,D1kq2+kI,D,12kq2;qpkI,D,1kq2+kI,D2kq2Theorem6.
4Ren-CangLi:RelativePerturbationTheory6Table3.
1continued.
PerturbationTheoremsforSingularValuesClassicalBoundsNewRelativeBoundsBandeBrnPi=1ji,eij2keB,BkFTheorem4.
7eB=D1BD2rnPi=1i;ei212kD1,D,11kF+kD2,D,12kF1,132kD1,D,11k2kD2,D,12k2Theorem5.
2BandeBrnPi=1ji,eij2keB,BkFTheorem4.
7eB=D1BD2rnPi=1pi;ei2121+1=p,kD1,D,11kF+kD2,D,12kFTheorem5.
3BandeBji,eijkeB,Bk2Theorem4.
7eB=D1BD2i;ei12kD1,D,11k2+kD2,D,12k21,132kD1,D,11k2kD2,D,12k2Theorem5.
2BandeBji,eijkeB,Bk2Theorem4.
7eB=D1BD2pi;ei121+1=p,kD1,D,11k2+kD2,D,12k2Theorem5.
3Table3.
1continued.
ABauer-FikeTypeTheoremClassicalBoundsNewRelativeBoundsA=XX,18e2eA,92A,suchthatje,jXkeA,Ak2Theorem4.
6EithereA=ADoreA=DA:8e2eA,92A,suchthatje,jjjXkI,Dk2Theorem6.
6Finally,let'sconsiderthegradedcases:1.
A=SHSandeA=SeHSaretwonngradednonnegativedeniteHermitianmatrices.
HisnonsingularandkH,1k2kHk21,whereHdef=eH,H.
2.
B=GSandeB=eGSaretwomngradedmatriceswhosesingularvaluesareofinterest.
GisnonsingularandkG,1k2kGk21,whereGdef=eG,G.
Inapplications,Sisscalingmatricesandoftenarediagonal;butourresultsdonotassumethis.
TheelementsofScanvarywildly.
TheinterestingcaseiswhenHGismuchbetterconditionedthanAB,andwhenHGissmalleventhoughA,eAB,eBisnot.
Ren-CangLi:RelativePerturbationTheory7Table3.
1continued.
PerturbationTheoremsforGradedMatricesClassicalBoundsNewRelativeBoundsAandeADeniternPi=1ji,eij2keA,AkFTheorems4.
1and4.
3A=SHSeA=SeHSrnPi=1hi;eii2kH,1k2kHkFp1,kH,1k2kHk2Theorem5.
4AandeADeniteji,eijkeA,Ak2Theorem4.
3A=SHSeA=SeHSi;eikH,1k2kHk2p1,kH,1k2kHk2Theorem5.
4BandeBrnPi=1ji,eij2keB,BkFTheorem4.
7B=GSandeB=eGSrnPi=1i;ei22,kG,1k2kGk221,kG,1k2kGk2kG,1k2kGkFTheorem5.
5BandeBji,eij2keB,Bk2Theorem4.
7B=GSandeB=eGSi;ei2,kG,1k2kGk221,kG,1k2kGk2kG,1k2kGk2Theorem5.
53RelativeDistancesThissectionisdevotedtostudyingtwodierentkindsofrelativedistancesmeasuringrelativeerrorsbetweentwocomplexnumbersandeoneofwhichisanapproximationoftheother.
Classically,therelativeerrorine=1+asanapproximationtoismeasuredby=relativeerrorine=e,:3.
1Whenjjwesaythattherelativeperturbationtoisatmostsee,e.
g.
,8.
Suchanmeasurementlacksmathematicalpropertiesuponwhichanicerelativeperturbationtheorycanbebulit:forexample,itlackssymmetrybetweenandeandthusitcannotbeametricamongspacesofnumbersthatareofinteresttous.
Nonetheless,itisgoodenoughformeasuringcorrectdigitsofnumericalapproximations.
Inwhatfollows,newrelativedistanceswillbeproposedandstudied.
Thesedistanceshavebettermathematicalpropertiesthatallowustodevelopaniceperturbationtheoryandyettheyaretopologicallyequivalenttotheclassicalmeasurementjjasdenedin3.
1.
Ren-CangLi:RelativePerturbationTheory83.
1Thep-RelativeDistanceThep-relativedistancebetween;e2Cisdenedasp;edef=j,ejppjjp+jejpfor1p1.
3.
2Wedene,forconvenience,0=0def=0.
1wasrstusedbyDeift,Demmel,Li,andTomei6,1991todenerelativegaps.
Proposition3.
1Let1p1and;e2C.
1.
p;e0;andp;e=0ifandonlyif=e.
2.
p;e=pe;.
3.
p;e=p;eforall06=2C.
4.
p1=;1=e=p;efor6=0ande6=0.
5.
p;e21,1=p;andp;e=21,1=pifandonlyif=,e6=0inthecasep1;1;e=1ifandonlyife0andatleastoneofandeisnotzero.
6.
p;01if6=0;andp;e1;forp1ande0,1;forallp1ande0.
7.
p;eincreasesaspdoes,andp;e2p;e21=2pp;e:8.
if;;e;e2Randee,then1;e1;e;if,inadditiontothelistedconditions,alsoe0,thenp;ep;eforp1,3.
3andinequality3.
3isstrictifeitheroreeholds.
Proof:Properties16areeasytoverify.
Property7holdsbecauseppjjp+jejpisadecreasingfunctionofpfor1p1,andjjp+jejp1=pp2qjj2p+jej2p1=p=21=2pjj2p+jej2p1=2p;Ren-CangLi:RelativePerturbationTheory9bytheCauchy-Schwarzinequality1.
ToproveProperty8,weconsiderfunctionfdenedbyfdef=1,pp1+jjp;where,11.
Whenp=1,f=1;for,10,21+,1;for01;sofdecreasesmonotonicallyanddecreasesstrictlymonotonicallyfor01.
Weareabouttoprovethatwhenp1functionfsodenedisstrictlymonotonicallydecreasing.
Thisistrueifp=1.
When1p1,sethdef=fpandgdef=f,p.
Becausefor01h0=,p1,p,11+p,11+p20andg0=p1+p,11,p,11+p20;for01,hisstrictlymonotonicallydecreasing,andgisstrictlymonotonicallyincreasing.
Thusfunctionfisstrictlymonotonicallydecreasingforp1.
ThereareseveralcasestodealwithforconrmingProperty8.
Assumeatleastoneofandeeisstrict.
1.
0ee,then0=e=e1;thusp;e=f=ef=e=p;e:2.
0eeore0e,thenProperty6impliesp;e1p;e:Itiseasytoverifythattheequalitiesinthetwo's"cannotbesatisedsimuta-neously.
3.
0ee.
Onlyp=1shallbeconsidered:1;e=11=1;e:4.
ee0,then0e=e=1;thusp;e=fe=fe==p;e:1Holderinequality:For;e;;e0,and1p1,+eeppp+epqqq+eqandtheequalityholdsifandonlyifpeq=epq,whereq=p=p,1.
Whenp=2,thisistheCauchy-Schwarzinequality.
TheHolderinequalitywillbeusedfrequentlylaterinourproofs.
Ren-CangLi:RelativePerturbationTheory10TheproofofProperty8iscompleted.
Remark:InProperty8ofProposition3.
1,assumptione0forthecasep1isessential.
Acounterexampleis:let0,andlet=,=,e=e.
Thenp;e=+ppp+p21,1=p=p;e:Thefollowingpropositionestablishesthetopologicalequivalencebetweentheclassicalmeasurementsee3.
1andournewrelativedistancesp.
Proposition3.
2Let01,and;e2R.
Wehavethefollowing:e,1p;epp1+1,p;3.
4andp;emaxe,1;e,121=p1,:3.
5Asymptotically,lime!
p;ee,1=21=p;thus3.
4and3.
5areatleastasymptoticallysharp.
Proof:e,1impliesje=j1,;sop;e=e,1pp1+je=jppp1+1,p:Thisconrms3.
4.
3.
5p=1and3.
5p=1canbeprovedanalogouslytowhatwearegoingtodofor1p1.
Let=e=or==e.
Then10byProposition3.
1.
p;eimpliesdef=j,1jpp1+p:3.
6Nowif1,thenj,1jpp1+p21=p.
Assume1andwrite=,10.
3.
6yields=pp1+1+p;andthusp1+p,p+p=0:Considerfunctionfx=p1+xp,xp+pforx0.
Itiseasytoseethatf0=0;f00=pp0;andf+10,andf0xvanishesonlyonceatx=q=1,q,whereq=p=p,1;Sofxhasauniquepositivezerowhichis.
Nowifwecanshowf21=p1,0,then21=p1,mustbetrue;andthenby21=p1,21=p1,Ren-CangLi:RelativePerturbationTheory11aswastobeshown.
Wehavetoprovef21=p1,0.
Thisisequivalentto1+21=p,1p+1,p,20:Considerfunctiongx=1+21=p,1xp+1,xp,2for0x1.
Itiseasytoseethatg0=g1=0;g00=,p2,21=p0;g01=p2,21=q0;andg0xvanishesonlyonceforx0;somustgx0for0x1.
Proposition3.
3Lete=1+12Cande=1+22C.
Ifjij1,thenp;1,+1,p;ep;1+,1+;3.
7p;1,+21=q1,pe;ep;1+,21=q1+;3.
8whereq=p=p,1.
Proof:Wewillonlyprovideaproofof3.
8sincetheproofof3.
7isanalogous.
Noticethatjj1,jejjj1+andjj1,jejjj1+;sope;e=je,ejpqjejp+jejpj,j,j1,2jppjjp+jjp1+j,j,ppjjp+jjpqpq+qppjjp+jjp1+=p;1+,21=q1+;pe;ej,j+j1,2jppjjp+jjp1,j,j+ppjjp+jjpqpq+qppjjp+jjp1,=p;1,+21=q1,;asweretobeshown.
Proposition3.
4For;e2Cand1p1,wehaveh21,1=2p,2p;ei2p;ep2;e221,1=2p2p;e2p;e;3.
9for;e2Rande0,wehavep;e2p;ep2;e2:3.
10Ren-CangLi:RelativePerturbationTheory12Proof:Noproofisnecessaryif=e=0.
Assumeatleastoneofandeisnotzero.
Noticethatp2;e2=j2,e2jjj2p+jej2p1=p=j+ejjj2p+jej2p1=2pj,ejjj2p+jej2p1=2p=j+ejjj2p+jej2p1=2p2p;e:andthatj+ej21,1=2p,jj2p+jej2p1=2p.
Thenp2;e221,1=2p2p;e2p;ebyProperty7ofProposition3.
1.
Tocompletetheproofof3.
9,wealsonoticethatwithoutlossofgenerality,assumingjjjej.
j+ejjj2p+jej2p1=2p=j2,,ejjj2p+jej2p1=2pj2jjj2p+jej2p1=2p,j,ejjj2p+jej2p1=2p=21+2p1=2p,2p;e21,1=2p,2p;e;where0=je=j1.
Toprove3.
10,weseeundertheconditione0thatj+ej=jj+jej,jj2p+jej2p1=2p.
Letf1;2;;ngandfe1;e2;;engbetwosequencesofnrealnumbersorderedascendingly2,i.
e.
,12n;e1e2en:3.
11Nowweaddressthefollowingquestion:Whatarethebestone-onepairingsbetweenthei'sandtheej'sundercertainmeasures.
Suchaquestionwillbecomeimportantlaterinthispaperwhenwetrytopairtheeigenvaluesofonematrixtotheseofanother.
Proposition3.
5max1in1i;ei=minmax1in1i;ei;andforp1ifalli'sandej'sarenonnegative,max1inpi;ei=minmax1inpi;ei:Heretheminimizationsaretakenoverallpermutationsoff1;2;;ng.
Proof:Foranypermutationoff1;2;;ng,theideaofourproofistoconstructn+1permutationsjsuchthat0=;n=identitypermutation2Thesituationwhentheyareordereddescendinglycanbehandledinexactlythesameway.
Ren-CangLi:RelativePerturbationTheory13andforj=0;1;2;;n,1max1inpi;ejimax1inpi;ej+1i:Theconstructionofthesej'sgoesasfollows:Set0=.
Givenj,ifjj+1=j+1,setj+1=j;otherwisedenej+1i=8:ji;for,1jj+16=i6=j+1,j+1;fori=j+1;jj+1;fori=,1jj+1:Inthislattercase,jandj+1dieronlyattwoindexsasshowninthefollowingpicturenoticethat,1jj+1j+1andjj+1j+1:sej+1sejj+1sj+1s,1jj+1AAAAUXXXXXXXXXXXXXXXz9j+1j+1jjWithProperty8inProposition3.
1,itiseasytoprovethatmaxpj+1;ejj+1;p,1jj+1;ej+1maxpj+1;ej+1;p,1jj+1;ejj+1:Thusj'ssoconstructedhavethedesiredproperties.
Remark.
Proposition3.
5mayfailifnotallofthei'sandej'sareofthesamesigninthecasep1.
Acounterexampleisasfollows:n=2and1=,22=1ande1=2e2=4:ThenseeProposition3.
1maxfp1;e1;p2;e2g=p1;e1=21,1=p6pp2p+4p=p1;e2=maxfp1;e2;p2;e1g:Anotherpointwewanttomakeisthatgiventwosequencesofi'sandej'sorderedasin3.
11,generallynXi=1pi;ei26=minnXi=1hpi;eii2;3.
12evenifalli;ej0.
Hereisacounterexample:n=201e12=e2=2e2;Ren-CangLi:RelativePerturbationTheory14where1issucientlycloseto0,ande1issucientlycloseto2whichisxed.
Sinceas1!
0+ande1!
,2p1;e22+p2;e12!
1;p1;e12+p2;e22!
1+1pp2p+1;3.
12mustfailforsome01e12=e2=2e2.
Proposition3.
6Suppose1k0=k+1==k+`=0k+`+1n;ande1ek0=ek+1==ek+`=0ek+`+1en:Thengivenapermutationoff1;2;;ng,thereexistsanotherpermutationoff1;2;;ngsuchthat1jkfor1jk,andj=jforj=k+1;;k+`andpi;eipi;eifori=1;2;;n.
Proof:WiththehelpofProperty6ofProposition3.
1,atwo-stepproofcanbegivenasfollows.
1.
Findapermutation1suchthat11jk+`for1jk+`,andpi;eipi;e1ifori=1;2;;n;2.
Findapermutationsuchthat1jkfor1jk,andj=jforj=k+1;;k+`,andpi;e1ipi;e2ifori=1;2;;n.
Thedetailislefttothereader.
3.
2Barlow-Demmel-VeselicRelativeDistanceWeintroduceanotherrelativedistancebetweenande:;edef=j,ejpjej:3.
13Wetreat1=0=1andagain0=00.
ItwasrstusedbyBarlowandDemmel1,1990andDemmelandVeselic9,1992todenerelativegapsbetweenthespectraoftwomatrices.
WecallittheBarlow-Demmel-VeselicRelativeDistancebetweenandeProposition3.
7Let;e2C.
Ren-CangLi:RelativePerturbationTheory151.
;e0;and;e=0ifandonlyif=e.
2.
;e=e;.
3.
;e=;eforall06=2C.
4.
1=;1=e=;efor6=0ande6=0.
5.
;0=1if6=0.
6.
if;e2Rande0,then;e2.
7.
if;;e;e2Randeeande0,then;e;e:3.
14Proof:Properties15areeasytoverify.
Property6followsfromwhene0,;e=j,ejpjej=jj+jejpjej2pjjjejpjej=2;bytheCauchy-Schwarzinequality.
ToproveProperty7,wenoticethatfunction1x,xfor0x1ismonotonicallydecreasingand0=e=e1;thus;e=1p=e,q=e1q=e,q=e=;e;aswastobeshown.
Remark:InProperty7ofProposition3.
7,assumptione0isessential,sincein-equality3.
14isclearlyviolatedif0eeandissucientlycloseto0.
Thefollowingpropositionestablishesthetopologicalequivalencebetweentheclassicalmeasurementsee3.
1andournewrelativedistance.
Proposition3.
8Let;e2R.
If01,thene,1;ep1,;3.
15if02,then;emaxe,1;e,10@2+s1+241A:3.
16Asymptotically,lime!
;ee,1=1;thus3.
15and3.
16areatleastasymptoticallysharp.
Ren-CangLi:RelativePerturbationTheory16Proof:e,1impliese=1+forsome2Rwithjj.
So;e=jjp21+p1,;asrequired.
Toprove3.
16,weseteither==eor=e=.
20seeProperty6ofProposition3.
7.
;edef=givesj,1jp=2,2+2+1=0;solvingwhichyields=2+2p2+22,42=1+0@2s1+241A:Hencej,1j0@2+s1+241A0@2+s1+241Aaswastobeshown.
Proposition3.
9Lete=1+.
Assumethatjjjjandjj1,then;p1,+p1,;e;p1+,p1+:3.
17Proof:Sincejj1,jejjj1+andj=j1,;e=j,ejqjejj,j,jjqjejj,j,jjpjj1+;p1+,p1+;;ej,j+jjqjejj,j+jjpjj1,;p1,+p1,;asrequired.
Remark.
Proposition3.
9,incontrasttoProposition3.
3,onlyprovidesboundsonhowvarieswhenitsargumentsmallerinmagnitudeisperturbedalittle.
Whenbothargumentsareperturbed,followingthelinesoftheproofabove,oneobtains;1,+1,jj+jjpjje;e;1+,1+jj+jjpjj;wheree=1+1ande=1+2withjij.
Theratiojj+jjpjjwhichcouldbearbitrarilylargeplaysacrucialrolehere.
Itcanshownthat2jj+jjpjj2+;:Ren-CangLi:RelativePerturbationTheory17Proposition3.
10For;e2C,wehave2,;e;e2;e22+;e;e;3.
18if,moreover,;e0,then2;e2;e2;3.
19andtheequalityholdsifandonlyif=e.
Proof:Noproofisnecessaryif=e=0.
Assumethatatleastoneofandeisnotzero.
Noticethat2;e2=j+ejpjejj,ejpjej=j+ejpjej;e:Toprove3.
18,withoutlossofanygenerality,wemayassumethatjjjej;thenj+ejpjej=j,e+2ejpjejj,ejpjej+j2ejpjej;e+2;j+ejpjej=j2,,ejpjejj2jpjej,j,ejpjej2,;e:Theseconrm3.
18.
Nowif;e0,thenj+ejpjej=+epe2pepe=2;aswastobeshown.
Remark.
Thereisnouniversalconstantc0,independentofande,suchthatforall;e2C,2;e2isboundedbyc;e,unlike3.
9inProposition3.
4.
Proposition3.
11For;e2C,p;e2,1=p;e;andtheequalityholdsifandonlyifjj=jej.
Ifp;e2,1=p,then;e21=pp;eq1,21=pp;e:Proof:BytheCauchy-Schwarzinequality,wehavejjp+jejp2qjjpjejp=2qjejppqjjp+jejp21=pqjej;fromwhichtherstinequalityfollows.
Toprovethesecondone,wenoticethat;e=j,ejppjjp+jejpppjjp+jejppjej=ppjjp+jejppjejp;e:Ren-CangLi:RelativePerturbationTheory18Withoutlossofanygenerality,wemayassumethatjjjej.
Undertheconditionp;e2,1=p,wehavepjejppjjp+jejp=sjjppjjp+jejpjejppjjp+jejp=sj,e+ejppjjp+jejpjejppjjp+jejpvuutjejppjjp+jejp,j,ejppjjp+jejp!
jejppjjp+jejp=s1pp1+p,p;e1pp1+pHere,=jjjej1.
q2,1=p,p;e2,1=p=2,1=pq1,21=pp;efromwhichthesecondinequalitynowfollows.
Proposition3.
11isusefulinthatanyboundwithyieldsaboundwithp,andanyboundwithpyieldsaboundwithwithadditionalassumptions.
Nowweconsideragainthequestion:whatisthebestwaytopairtwosequencesofrealnumbersorderedasin3.
11WiththehelpofProperty7inProposition3.
7wecanproveinthesamewayasprovingProposition3.
5thatProposition3.
12Ifalli'sandej'sarenonnegativeandorderedasin3.
11,thenmax1ini;ei=minmax1ini;ei;wheretheminimizationistakenoverallpermutationsoff1;2;;ng.
Remark.
Proposition3.
12mayfailifnotalli'sandej'sareofthesamesign.
Acounterexampleisasfollows:n=2and1=,12=1ande1=14e2=2:Thenmaxf1;e1;2;e2g=maxn5=2;1=p2o=5=23=p2=maxn3=p2;3=2o=maxf1;e2;2;e1g:Lemma3.
1Let012and0e1e2.
Then1;e12+2;e221;e22+2;e12;orinotherwords,e1,12e11+e2,22e22e2,12e21+e1,22e12;andtheequalityholdsifandonlyifeither1=2ore1=e2.
Ren-CangLi:RelativePerturbationTheory19Proof:Itcanbeveriedthate1,12e11+e2,22e22,e2,12e21,e1,22e12=,2,1e2,e1e1e2+12e11e220;andtheequalityholdsifandonlyifeither1=2ore1=e2.
ArmedwithLemma3.
1,bysimilarreasoningasintheproofofProposition3.
5,onecanshowthatProposition3.
13Letf1;;ngandfe1;;engbetwosequencesofnpositivenum-bersorderedascendinglyasin3.
11.
ThennXi=1i;ei2=minnXi=1hi;eii2;wheretheminimizationistakenoverallpermutationsoff1;2;;ng.
Remark.
Proposition3.
13mayfailifnotalli'sandej'sareofthesamesign.
Hereisacounterexample:n=2and1=,22=1ande1=1e2=2:Then1;e12+2;e22=3=p22+1=p22=54=4=p42+02=1;e22+2;e12:3.
3ArepandMetricsLetXbeaspace.
Recallthatafunctiond:XX7!
0;1iscalledametricifithasthefollowingthreeproperties:for;;2X1.
d;=0ifandonlyif=;2.
d;=d;;3.
d;d;+d;.
ThisdenitionexcludesimmediatelythepossibilitythatisametriconC,norevenonRsince;0=1for6=0.
Togetaroundthis,wecalld:XX7!
0;1ageneralizedmetricifitpossessestheabovethreeproperties.
FromPropositions3.
1and3.
7,weseethatfunctionspandonCCsatisfythersttwopropertiesinthedenitionofageneralizedmetric.
Naturally,wewouldliketoRen-CangLi:RelativePerturbationTheory20ask:IspametriconCisageneralizedmetriconCInotherwords,weliketoknowwhetherfor;;2Cp;p;+p;3.
203.
21Aquickanswerto3.
21isNo,evenfor;;0,bythefollowingproposition.
Proposition3.
14For0,wehave3.
22Theequalityholdsifandonlyifeither=or=.
Proof:Itcanbeveriedthatp,pp,pp,pp0:Itiszeroifandonlyif=or=.
=implies=and=.
Inequality3.
22isexactlytheoppositeof3.
21which,otherwise,wouldbetrueifwereametriconR.
However,ittakesafewpagesofworktoanswer3.
20for;;2R.
WeleavethedetailtoAppendixA,whereitisproved:Proposition3.
153.
20holdsfor;;2R,andthuspfor1p1isametriconR.
StillthequestionwhetherpisametriconCisopen.
4KnownPerturbationTheoremsforEigenvalueandSin-gularValueVariationsInthissection,wewillbrieyreviewseveralmostcelebratedtheoremsforeigenvalueandsingularvaluevariationswhichwillbeextendedlater.
MostofthesetheoremscanbefoundinBhatia3,1987,GolubandVanLoan14,1989,Parlett33,1980andStewartandSun35,1990.
Notationintroducedatthebeginningofx2willbefollowedstrictly.
HomanandWielandt16,1953provedTheorem4.
1Homan-WielandtIfAandeAarenormal,thenthereisapermuta-tionoff1;2;;ngsuchthatvuutnXi=1ji,eij2keA,AkF:Ren-CangLi:RelativePerturbationTheory21ForanonsingularmatrixY2Cnn,thespectralconditionnumberYisdenedasYdef=kYk2kY,1k2:Theorem4.
1wasgeneralizedbySun38,1984andZhang43,1986totwodiagonalizablematrices.
Theorem4.
2Sun-ZhangAssumethatbothAandeAarediagonalizableandadmitthefollowingdecompositionsA=XX,1andeA=eXeeX,1;4.
1whereXandeXarenonsingularand=diag1;2;;nande=diage1;e2;;en:4.
2Thenthereisapermutationoff1;2;;ngsuchthatvuutnXi=1ji,eij2XeXkeA,AkF:SuchmatricesAandeAasdescribedinTheorem4.
2arecallednormalizable.
Sun38,1984provedthistheoremwhenAisnormalandeAnormalizable;laterZhang43,1986foundthataslightmodicationofSun'sproofservesthecasewhenbothAandeAarenormalizable.
Wewillconsiderunitarilyinvariantnormsjjjjjjofmatrices.
InthiswefollowMirsky31,1960andStewartandSun35,1990.
ThatanormjjjjjjisunitarilyinvariantonCmnmeansthatitsatises,besidestheusualpropertiesofanynorm,also1.
jjjUYVjjj=jjjYjjj,foranyU2Um,andV2Un;2.
jjjYjjj=kYk2,foranyY2CmnwithrankY=1.
Twounitarilyinvariantnormsusedfrequentlyarethespectralnormkk2andtheFrobeniusnormkkF.
Letjjjjjjbeaunitarilyinvariantnormonsomematrixspace.
Thefollowinginequalities35,p.
80willbeemployedfrequentlyintherestofthispaper:jjjWYjjjkWk2jjjYjjjandjjjYZjjjjjjYjjjkZk2:Theorem4.
3SupposethatAandeAarebothHermitian,andthattheireigenvaluesareordereddescendinglyasin2.
2.
Thenforanyunitarilyinvariantnormjjjjjjdiag1,e1;2,e2;;n,enA,eA:4.
3Theorem4.
3wasprovedbyWeyl40,1912forthespectralnormandbyLoewner27,1934fortheFrobeniusnorm.
Also,fortheFrobeniusnormitisacorollaryofTheorem4.
1byHomanandWielandt16,1953.
Forallunitarilyinvariantnorms,4.
3wasprovedbyMirsky31,1960.
HederiveditfromatheoremofLidskii26,1950andWielandt41,1955.
ExtensionstoTheorem4.
3havebeenmadeintheliterature.
ThefollowingtheoremisduetoLi25,1996andLu28,1994.
Ren-CangLi:RelativePerturbationTheory22Theorem4.
4TothehypothesesofTheorem4.
2addsthis:alli'sandej'sarerealandareordereddescendinglyasin2.
2.
Thenforanyunitarilyinvariantnormjjjjjjdiag1,e1;2,e2;;n,enqXeXA,eA:4.
4SuchmatricesAandeAasdescribedinTheorem4.
4arecalledsymmetrizable.
Inequality4.
4forjjjjjj=kk2wasprovedbyLu28,1994;forallunitarilyinvariantnormsitisduetoLi25,1996.
Thisinequalityimprovessubstantiallydiag1,e1;2,e2;;n,enXeXA,eA4.
5duetoBhatia,DavisandKittaneh4,1991.
Abriefhistorybehindinequality4.
5isasfollows:ItwasprovedbyKahan20,1975forthespectralnorm,andfortheFrobeniusnormitcanbededucedwithoutmuchdicultyfromatheoreminKahan19,1967;alsoforFrobeniusnormitisacorollaryofTheorem4.
2bySun38,1984andZhang43,1986.
Forallunitarilyinvariantnorms,itisduetoBhatia,DavisandKittaneh4,1991.
Forotherimprovementsofinequality4.
5,thereaderisreferredtoLi25,1996.
Inequality4.
3forthespectralnormwasgeneralizedalsoto`poperatornorm.
Thep-Holdernormofavectory=i2Cnisdenedbykykpdef=pvuutnXi=1jijp:The`p-operatornormofamatrixY2CmnisdenedbykYkpdef=maxkykp=1kYykp:IfYissquareandnonsingular,its`pconditionnumberisdenedbypYdef=kYkpkY,1kp:Clearly,2=,thespectralconditionnumber.
ThefollowingtheoremisduetoLi23,p.
225,1993.
Theorem4.
5LiUndertheconditionsofTheorem4.
4.
Thenmax1inji,eijpXpeXkA,eAkp;4.
6where1p1.
Remark.
ItwouldbeinterestingtoknowwhetherpXpeXininequality4.
6couldbeimprovedtoqpXpeXasasimilarthinghappenedbetween4.
4and4.
5.
Generally,ifoneofAandeAisdiagonalizableandtheotherisarbitrary,wehavethefollowingresultduetoBauerandFike32,1960.
3Onecanproveaslightlymorestrongerinequalitythan4.
7je,jkX,1eA,AXk2:Ren-CangLi:RelativePerturbationTheory23Theorem4.
6Bauer-FikeAssumeAisdiagonalizable,i.
e.
,A=XX,1;where=diag1;;n:Thenforanye2eA,thereexistsa2Asuchthatje,jXkeA,Ak2:4.
7Regardingsingularvalueperturbations,thefollowingtheoremwasestablishedinMirsky31,1960,basedonresultsfromLidskii26,1950andWielandt41,1955.
Theorem4.
7Foranyunitarilyinvariantnormjjjjjj,wehavejjjdiag1,e1;2,e2;;n,enjjjB,eB:4.
85RelativePerturbationTheoremsforNonnegativeDe-niteMatrixEigenvaluesandforSingularValuesThissectionisdevotedtotherelativeperturbationtheoryforeigenvaluesofnonnegativedenitematricesandforsingularvalues.
Thefollowingproblemswillbeconsidered.
Eigenvalueproblems:1.
AandeA=DAD,whereAisnonnegativedenite,andDisclosetosomeunitarymatrix.
2.
A=SHSandeA=SeHS,whereHispositivedeniteandkH,1k2keH,Hk21,andSissomesquarematrix.
Singularvalueproblems:1.
BandeB=D1BD2,whereD1andD2areclosetosomeunitarymatricesofsuitabledimensions.
2.
B=GSandeB=eGS,whereGisnonsingularandkG,1k2keG,Gk21,andSissomesquarematrix.
Theoremspresentedhereareoftensharperthantheseinthenextsectionwhenapplyingtononnegativedenitematrices.
Wewillmakethismoreconcreteinthecomingsection.
5.
1EigenvalueVariationsforAandeA=DADTheorem5.
1LetAandeA=DADbetwonnHermitianmatriceswitheigenval-ues2.
1ordereddescendinglyasin2.
2,whereDisnonsingular.
AssumethatAisnonnegativedenite4.
Thenmax1ini;eikD,D,1k2;5.
1vuutnXi=1hi;eii2kD,D,1kF:5.
24TheneAmustbenonnegativedeniteaswell.
Ren-CangLi:RelativePerturbationTheory24Itiseasytorelatetheright-handsidesoftheinequalities5.
1and5.
2tothesingularvaluesofD.
Infact,letthesingularvaluedecompositionSVDofDbeD=UddVd;5.
3whereUdandVdareunitary,anddisadiagonalmatrixwhosediagonalentriesarethesingularvaluesofD.
OnehasforanyunitarilyinvariantnormjjjjjjD,D,1=Vdd,,1dUd=d,,1d:5.
2SingularValueVariationsforBandeB=D1BD2Theorem5.
2LetBandeB=D1BD2betwomnmatriceswithsingularvalues2.
3ordereddescendinglyasin2.
4,whereD1andD2aresquareandnonsingular.
IfkD1,D,11k2kD2,D,12k232,thenmax1ini;ei12kD1,D,11k2+kD2,D,12k21,132kD1,D,11k2kD2,D,12k2;5.
4vuutnXi=1i;ei212kD1,D,11kF+kD2,D,12kF1,132kD1,D,11k2kD2,D,12k2:5.
5Now,Let'smentionapossibleapplicationofTheorem5.
2.
Ithassomethingtodowithdeationincomputingthesingularvaluedecompositionofabidiagonalmatrix.
Formoredetails,thereaderisreferredto6,8,10,30.
Weformulatetheapplicationintoacorollary.
Corollary5.
1AssumeinTheorem5.
2,oneofD1andD2istheidentitymatrixandtheothertakestheformD=IXI!
;whereXisamatrixofsuitabledimensions.
WiththenotationofTheorem5.
2,wehavemax1ini;ei12kXk2;5.
6vuutnXi=1i;ei21p2kXkF:5.
7Proof:NoticethatD,D,1=IXI!
,I,XI!
=XX!
;andthuskD,D,1k2=kXk2andkD,D,1kF=p2kXkF.
Ren-CangLi:RelativePerturbationTheory25ItwasprovedbyEisenstatandIpsen10,1993thatjei,ijkXk2i;orequivalentlyeii,1kXk2:5.
8Ourinequality5.
6issharperbyroughlyafactor1=2,aslongaskXk2issmall.
Asamatteroffact,itfollowsfrom5.
6andProposition3.
8thatifkXk24theneii,10@kXk24+s1+kXk22161AkXk22=kXk22+OkXk242!
:Ourinequality5.
7istherstofitskind.
Theorem5.
3LetBandeB=D1BD2betwomnmatriceswithsingularvalues2.
3ordereddescendinglyasin2.
4,whereD1andD2aresquareandnonsingular.
Thenmax1inpi;ei121+1=pkD1,D,11k2+kD2,D,12k2;5.
9vuutnXi=1pi;ei2121+1=pkD1,D,11kF+kD2,D,12kF:5.
10AstraightforwardcombinationofProposition3.
11andTheorem5.
2willleadtoboundsthatareweakerthantheseinTheorem5.
3byafactor1,132kD1,D,11k2kD2,D,12k2,1whichmayplayaninsubstantialrolebecausekD1,D,11k2kD2,D,12k2isofsecondorder.
5.
3GradedMatricesTheorem5.
4LetA=SHSandeA=SeHSbetwonnnonnegativedeniteHermitianmatriceswitheigenvalues2.
1ordereddescendinglyasin2.
2,andletH=eH,H.
IfkH,1k2kHk21,thenmax1ini;eiI+H,1=2HH,1=21=2,I+H,1=2HH,1=2,1=22kH,1k2kHk2p1,kH,1k2kHk2;5.
11vuutnXi=1hi;eii2I+H,1=2HH,1=21=2,I+H,1=2HH,1=2,1=2FkH,1k2kHkFp1,kH,1k2kHk2:5.
12Thelastinequalityin5.
11isderivablefromaboundduetoDemmelandVeselic9,1992see7.
10below.
Ren-CangLi:RelativePerturbationTheory26Theorem5.
5LetB=GSandeB=eGSbetwonnmatriceswithsingularvalues2.
3ordereddescendinglyasin2.
4,whereGandeGarenonsingular,andletG=eG,G.
IfkGk2kG,1k21,thenmax1ini;ei12I+GG,1,I+GG,1,12kGG,1+G,Gk2kGG,1k2+kGG,1k21,kGG,1k2!
kGG,1k221+11,kG,1k2kGk2kG,1k2kGk22;5.
13vuutnXi=1i;ei212I+GG,1,I+GG,1,1FkGG,1+G,GkFkGG,1kF+kGG,1k21,kGG,1k2!
kGG,1kF21+11,kG,1k2kGk2kG,1k2kGkF2:5.
14Thelastinequalityin5.
13isderivablefromaboundduetoMathias29,1994see7.
12below.
Remark.
ItisinterestingtonoticethatifGG,1isveryskew,theni;ei=o,kGG,1k2,especiallykGG,1+G,Gk2=OkGG,1k22i;ei=OkGG,1k22:6RelativePerturbationTheoremsforNon-DeniteMa-trixEigenvaluesThissectionisdevotedtotheperturbationtheorywithpforthefollowingmatrixeigen-valueproblems.
1.
AandeA=DADfortheHermitiancase,whereDisnonsingularandclosetoIormoregenerallytoaunitarymatrix.
2.
AandeA=D1AD2forageneraldiagonalizablecase,whereD1andD2arenonsin-gularandclosetoIormoregenerallytosomeunitarymatrix.
Comparisonsamongtheoremsinthissectionandtheseintheprevioussectionwillbeconducted.
ThefollowingtheoremisageneralizationofTheorems4.
1and4.
2.
Theorem6.
1AssumethatnnmatrixAisperturbedtoeA=D1AD2andbothD1andD2arenonsingular.
AssumealsothatbothAandeAarediagonalizableandadmitRen-CangLi:RelativePerturbationTheory27thedecompositionsasdescribedin4.
1and4.
2.
Thenthereisapermutationoff1;2;;ngsuchthatvuutnXi=1h2i;eii2minkeX,1k2kXk2qkX,1I,D2eXk2F+kX,1D,1,IeXk2F;kX,1k2keXk2qkeX,1I,D1Xk2F+keX,1D,12,IXk2F6.
1XeXminqkI,D1k2F+kI,D,12k2F;qkI,D,11k2F+kI,D2k2F:ForanygivenU2Un,UeAU=D1UAD2UhasthesameeigenvaluesaseAdoes,andmoreoverfrom4.
1UeAU=eXU,1eeXU.
ApplyingTheorem6.
1tomatricesAandUeAUleadstothefollowingtheoremwhichwewillreferasTheorem6.
1s,wheres"isforindicatingthatitisstronger.
Theorem6.
1sLetallconditionsofTheorem6.
1hold.
Thenthereisapermutationoff1;2;;ngsuchthatvuutnXi=1h2i;eii2XeX6.
2minU2UnminqkU,D1k2F+kU,D,12k2F;qkU,D,11k2F+kU,D2k2F:SupposenowA2Cnisannormalmatrix,i.
e.
,AA=AA,andperturbAtoeA=D1AD2.
Thequestionis:WheniseAalsonormalThisisaratherinterestingquestion,andaninstantansweristhateAisnormalprovidedD2AD1D1AD2=D1AD2D2AD1:However,thisconditionis,perhaps,toogeneraltobeuseful.
Idonotknowhowtoapproachthisproblemyetandthereforethisquestionwillnotbeaddressedfurtherinwhatfollows.
Ontheotherhand,ifwehappentoknowthateAisalsonormal,thefollowingtheorem,asacorollaryofTheorem6.
1s,indicatesthattheeigenvaluesofAandeAagreetohighrelativeaccuracy.
Theorem6.
2LetAandeA=D1AD2betwonnnormalmatriceswitheigenvalues2.
1,whereD1andD2arenonsingular.
Thenthereisapermutationoff1;2;;ngsuchthatvuutnXi=1h2i;eii26.
3minU2UnminqkU,D1k2F+kU,D,12k2F;qkU,D,11k2F+kU,D2k2F:Ren-CangLi:RelativePerturbationTheory28Generallywedonotknowhowtorelatetheupperboundin6.
3tothesingularvaluesofD1andD2,unlessfurtherinformationonD1andD2isavailable.
InthecaseofD1=D2=D,thereisasimplesolution.
Infact,wecansolveeasilythefollowingminimizationproblem:ndaU02UnsuchthatforanyunitarilyinvariantnormjjjjjjminU2UnjjjU,Djjj=jjjU0,DjjjandminU2UnU,D,1=U0,D,16.
4intermsofSVDofD.
Asamatteroffact,letSVDofDbegivenby5.
3.
ItfollowsfromTheorem4.
7thatjjjU,DjjjjjjI,djjjandU,D,1I,,1d:6.
5Ontheotherhand,thereisoneU0def=UdVdwhichrealizesthetwoequality.
NowapplyingTheorem6.
2toHermitianmatricesleadstoTheorem6.
3LetAandeA=DADbetwonnHermitianmatriceswitheigenvalues2.
1,whereDisnonsingular.
Thenthereisapermutationoff1;2;;ngsuchthatvuutnXi=1h2i;eii2minU2UnqkU,Dk2F+kU,D,1k2F=qkI,dk2F+kI,,1dk2F:6.
6ItisworthmentioningthatthepermutationinTheorem6.
3maynotbetheidentitypermutation,assumingeigenvaluesareordereddescendinglyasin2.
2.
However,onecanalwayschooseasuchthateigenvaluesofthesamesignarepairedtoeachotherandzeroeigenvaluestozeroeigenvalues.
SeeProposition3.
6.
Acomparisonofthistheoremandtheinequality5.
2inTheorem5.
1leadstothefollowingconclusions:1.
Theorem6.
3coversboththedenitecaseandtheindenitecase,whiletheinequality5.
2inTheorem5.
1isforthedenitecaseonly.
2.
Whenapplyingtothedenitecase,5.
2issharperthan6.
6.
Asamatteroffact,6.
6isacorollaryof5.
2inthiscase.
Infact,ifAisnonnegativedenitevuutnXi=1h2i;eii21p2vuutnXi=1hi;eii2byProposition3.
111p2kd,,1dkFby5.
2qkI,dk2F+kI,,1dk2F:byLemma6.
1belowLemma6.
11p2kd,,1dkFqkI,dk2F+kI,,1dk2F;andtheequalityholdsifandonlyifd=I,i.
e.
,Disunitary.
Ren-CangLi:RelativePerturbationTheory29Proof:Noticethatfor2R,1,1+1,1j,1j+1,1p2sj,1j2+1,12andtheequalitysignholdsifandonlyif=1.
ThetheorembelowisageneralizationofTheorems4.
3and4.
4forthespectralnormandthatofTheorem4.
5.
Theorem6.
4TothehypothesesofTheorem6.
1addthis:alli'sandej'sarenonnega-tiveandarearrangeddescendinglyasdescribedin2.
2.
Thenwehavemax1inpi;eirXreX6.
7minqqkI,D1kqr+kI,D,12kqr;qqkI,D,1kqr+kI,D2kqr;where1r1andq=p=p,1.
SimilarlytoTheorem6.
1,thereisastrongerversionofthistheoremforr=2asfollows.
Theorem6.
4sLetallconditionsofTheorem6.
4hold.
Thenmax1inpi;eiXeX6.
8minU2UnminqqkU,D1kq2+kU,D,12kq2;qqkU,D,11kq2+kU,D2kq2;whereq=p=p,1.
Asaconsequenceofthistheoremandoursolutiontotheoptimizationproblem6.
4,wededucethatTheorem6.
5UndertheconditionsofTheorem6.
3,ifAisnonnegativedeniteandtheeigenvaluesofAandeAareordereddescendinglyasin2.
2,thenmax1inpi;ei=qqkI,dkq2+kI,,1dkq2;6.
9wheredisdenedin5.
3andq=p=p,1.
However,Theorem6.
5issupersededbyTheorem5.
1.
Toseethis,wenoticethat1.
BothTheorem5.
1andTheorem6.
5workforthenonnegativedenitecase.
2.
6.
9canbededucedfrom5.
1.
Infact,5.
1andProposition3.
11implythatmax1inpi;ei2,1=pi;ei2,1=pkd,,1dk2qqkI,dkq2+kI,,1dkq2;byLemma6.
2below.
Butstill6.
9looksniceandclean.
Ren-CangLi:RelativePerturbationTheory30Lemma6.
2kd,,1dk221=pqqkI,dkq2+kI,,1dkq2;6.
10andtheequalityholdsifandonlyifd=I,i.
e.
,Disunitary.
Proof:Let2Dbetheonesuchthatkd,,1dk2=,1:Thenkd,,1dk2=,1j,1j+1,121=pqsj,1jq+1,1q21=pqqkI,dkq2+kI,,1dkq2;asrequired.
SofarwehaveconsideredthecasewhenbothAandeAarediagonalizable.
Inwhatfollows,weweakenthisassumptionbyrequiringonlyAtobediagonalizableandderivearelativeeigenvalueperturbationboundofBauer-FikeType2.
Theorem6.
6AssumethatA2Cnnisdiagonalizableandadmitsthefollowingdecom-positionA=XX,1where=diag1;;n:6.
11Assume5alsoeithereA=DAoreA=AD.
Thenforanye2eAthereexistsa2Asuchthatmin2Aje,jjjkX,1D,IXkppXkI,Dkp:6.
127ATheoremofOstrowskiandOtherDevelopmentsInthissection,webrieyreviewthecurrentstateofresearchontheproblemslistedinx1.
1andpresentourremarks.
LetAbeannnHermitianmatrix.
PerturbingAtoDAD,whereDisnonsingular,isactuallyperformingacongruencetransformationtoAbyD.
ThefollowingtheoremisduetoOstrowski32,1959seealso17,pp.
224225.
Theorem7.
1OstrowskiLetAandeA=DADbetwonnHermitianmatriceswitheigenvalues2.
1ordereddescendinglyasin2.
2,whereDisnonsingular.
Thenthereexistj'ssothatminD2jmaxD2andej=jjfor1jn.
5Unlikeinourprevioustheorems,herewedonothavetoassumethatDisnonsingular.
Ofcourse,ifDisfarawayfromI,thebound6.
12doesnottellusmuch;ifDiscloseenoughtoI,ithastobenonsingular.
Ren-CangLi:RelativePerturbationTheory31Ostrowski'stheoremimpliesimmediatelyarelativeperturbationboundonHermitianeigenvalues.
Theorem7.
2LettheconditionsofTheorem7.
1hold.
Thenjej,jjjjjkI,DDk2for1jn,orinotherwords,ej=j1+jwithjjjkI,DDk2for1jn.
Inequality5.
1ofTheorem5.
1andTheorem7.
2areindependentinthesensethatonecannotbeinferredfromtheother;butTheorem7.
2coversmorewhileTheorem5.
1coversnonnegativedenitematricesonly.
Ostrowski'stheoremalsoappliestosingularvaluevariationsformatricesBandeB=D1BDbyworkingwithHermitianmatricesBB!
andeBeB!
=D2D1!
BB!
D2D1!
:7.
1Giventhesingularvalues2.
3ofBandeB,itisknownthatbesidesm,nifmnzeroeigenvalues,theeigenvaluesofthetwomatricesin7.
1arei,andei,respectively.
Corollary7.
1LetBandeB=D1BD2betwomnmatriceswithsingularvalues2.
3ordereddescendinglyasin2.
4,whereD1andD2arenonsingular.
ThenminfminD12;minD22gejjmaxfmaxD12;maxD22gfor1jnwhichgivesjej,jjjmaxfkI,D1D1k2;kI,D2D2k2gfor1jn;orinotherwords,ej=j1+jwithjjjmaxfkI,D1D1k2;kI,D2D2k2gfor1jn:Thiscorollary,though,animmediateconsequenceoftheaboveOstrowski'stheoremandtheequation7.
1,hasappearednowhere.
ItturnsoutthatCorollary7.
1providesalesssharpboundthanthefollowingtheoremduetoEisenstatandIpsen10,1993.
ItcanalsobederivedfromOstrowski'stheorem.
Theorem7.
3Eisenstat-IpsenUndertheconditionsofCorollary7.
1,wehaveminD1minD2ejjmaxD1maxD2for1jnRen-CangLi:RelativePerturbationTheory32whichyieldsjej,jjjmaxfj1,minD1minD2j;j1,maxD1maxD2jgfor1jn;orinotherwords,ej=j1+jwithjjjmaxfj1,minD1minD2j;j1,maxD1maxD2jg;for1jn.
Theorem7.
3alwaysprovidesasharperboundthanCorollary7.
1does,asthefollowinglemmaindicates.
Lemma7.
1For;0,maxfj1,2j;j1,2jgj1,j;7.
2andtheequalityholdsifandonlyif=.
Proof:Theinequalityisobviousifeithermaxf;g1orminf;g1.
Itisalsoclearlytrueifeither=1or=1.
Nowitsucesforustoconsiderthecasewhen01.
Therearetwosubcases:2,11,2or2,11,2.
1.
2,11,22+2222+22bytheCauchy-Schwarzinequalityandsince6=1.
Nownoticethat21,21,=j1,j:2.
2,11,22+22+22+222,11,;ontheotherhand,22,1,1.
So2,1maxf1,;,1g=j1,j:Fromtheaboveproof,itisclearthatmaxfj1,2j;j1,2jg=j1,jcannothappenwhen01;itisnothardtoseewhenmaxf;g1orminf;g1,theequalitycannothappen,either,unless=.
Regardingtogradedmatrices,thefollowingtwotheoremsareduetoDemmelandVeselic9,1992andMathias29,1994.
Theorem7.
4Demmel-VeselicUndertheconditionsofTheorem5.
4,wehavejej,jjjjjkH,1k2kHk2for1jn;orinotherwords,ej=j1+jwithjjjkH,1k2kHk2for1jn:Ren-CangLi:RelativePerturbationTheory33Theorem7.
5MathiasUndertheconditionsofTheorem5.
5,wehavejej,jjjkG,1k2kGk2for1jn;orinotherwords,ej=j1+jwithjjjkG,1k2kGk2for1jn:Finally,letusseewhatwecangetfromTheorems7.
2,7.
4,7.
5and7.
3andCorol-lary7.
1,intermsofthetwokindsofrelativedistancesdenedinx3.
1.
FromTheorem7.
2,wehavefor1jnpj;ej1j;ejkI,DDk2;7.
3j;ejkI,DDk2minD:7.
4Theinequality7.
3holdsbecause1j;ej=jej,jjmaxfjjj;jejjgjej,jjjjjkI,DDk2;andtheinequality7.
4holdsbecausej;ej=jej,jjqjjjjejj=jej,jjjjjsjjjjejjkI,DDk2minD:2.
FromCorollary7.
1andbysimilarreasoningsabove,wehavefor1jn1j;ejmaxfkI,D1D1k2;kI,D2D2k2g;7.
5j;ejmaxfkI,D1D1k2;kI,D2D2k2gminfminD1;minD2g:7.
63.
FromTheorem7.
3,wehavefor1jn1j;ejmaxfj1,minD1minD2j;j1,maxD1maxD2jg;7.
7j;ejmaxfj1,minD1minD2j;j1,maxD1maxD2jgpminD1minD2:7.
8Inequalities7.
7and7.
8aresharperthan7.
5and7.
6,respectively.
4.
FromTheorem7.
4,wehavefor1jn1j;ejkH,1k2kHk2;7.
9j;ejkH,1k2kHk2p1,kH,1k2kHk2:7.
10Inequality7.
10hasbeenderivedinTheorem5.
4.
Ren-CangLi:RelativePerturbationTheory345.
FromTheorem7.
5,itfollowsfor1jn1j;ejkG,1k2kGk2;7.
11j;ejkG,1k2kGk2p1,kG,1k2kGk2:7.
12Inequality7.
12turnsouttobesharperthanthelast"in5.
13ofTheorem5.
5,butnotthersttwo.
8ProofsofTheorems6.
1and6.
4Toprovethetheorems,weneedalittlepreparation.
AmatrixY=yij2Rnnisdoublystochasticifallyij0andnXk=1yik=nXk=1ykj=1fori;j=1;2;;n.
AmatrixP2Rnniscalledapermutationmatrixifexactlyoneentryineachrowandeachcolumnequalsto1andallothersarezero.
LeteibetheithcolumnvectorofIn.
EachpermutationmatrixPcorrespondstoauniquepermutationoff1;2;;nginsuchaway:P=e1;e2;;en;andviceversa.
Thustherearen!
permutationmatrices.
ThefollowingwonderfulresultisduetoBirkho5,1946seealso17,pp.
527528.
Lemma8.
1BirkhoAnnnmatrixisdoublystochasticifandonlyifitliesintheconvexhullofpermutationmatrices.
Lemma8.
2LetY=yijbeannndoublystochasticmatrix,andletM=mij2Cnn.
Thenthereexistsapermutationoff1;2;;ngsuchthatnXi;j=1jmijj2yijnXi=1jmiij2:Proof:DenoteallnnpermutationmatricesasPk,andtheircorrespondingpermutationsoff1;2;;ngask,wherek=1;2;;n!
.
ItfollowsfromLemma8.
1thatYcanbewrittenasY=n!
Pk=1kPk,wherek0andn!
Pk=1k=1.
HencenXi;j=1jmijj2yij=n!
Xk=1knXi=1jmikij2min1kn!
nXi=1jmikij2;aswastobeshown.
Ren-CangLi:RelativePerturbationTheory35Thetechniqueintheaboveproofisquitestandard.
ItwasrstusedbyHomanandWielandt16,1953toproveTheorem4.
1,andlaterbySun36,1982toproveaHoman-Wielandttypetheoremforaspecialclassofmatrixpencilsandbymaybemanyothers.
ThefollowinglemmaisduetoElsnerandFriedland12,1995.
Lemma8.
3Elsner-FriedlandLetY=yij2Cnn.
ThenthereexisttwonndoublystochasticmatricesY1;Y2suchthatentrywiselyminY2Y1jyijj2maxY2Y2:ProofofTheorem6.
1:Letusrstderiveourperturbationequations.
A,eA=A,D1AD2=A,AD2+AD2,D1AD2=AI,D2+D,1,IeA:Pre-andpost-multiplytheequationsbyX,1andeX,respectively,togetX,1eX,X,1eXe=X,1I,D2eX+X,1D,1,IeXe:8.
1SetYdef=X,1eX=yij;Edef=X,1I,D2eX=eij;eEdef=X,1D,1,IeX=eeij:Thenequation8.
1readsY,Ye=E+eEe,orcomponentwiseiyij,yijej=ieij+eeijej,sojij2+jejj2jeijj2+jeeijj2jieij+eeijejj=ji,ejyijj2;whichyieldsjeijj2+jeeijj2h2i;eji2jyijj2.
HencekX,1I,D2eXk2F+kX,1D,1,IeXk2FnXi;j=1h2i;eji2jyijj2:8.
2Inequality8.
2,Lemmas8.
2and8.
3implythatkX,1I,D2eXk2F+kX,1D,1,IeXk2FminY2nXi=1h2i;eii2forsomepermutationoff1;2;;ng.
SinceminY=kY,1k,12=keX,1Xk,12keX,1k,12kXk,12;wehavekeX,1k2kXk2qkX,1I,D2eXk2F+kX,1D,1,IeXk2FkeX,1k2kXk2minYvuutnXi=1h2i;eii2vuutnXi=1h2i;eii2:8.
3Ren-CangLi:RelativePerturbationTheory36Ontheotherhand,wehaveA,eA=A,D1AD2=A,D1A+D1A,D1AD2=I,D1A+eAD,12,I:Pre-andpost-multiplytheequationsbyeX,1andX,respectively,togeteX,1X,eeX,1X=eX,1I,D1X+eeX,1D,12,IX:8.
4SeteYdef=eX,1X=eyij.
Similarly,wehavekeX,1I,D1Xk2F+keX,1D,12,IXk2FnXi;j=1h2i;eji2jeyjij2:8.
5Inequality8.
5,Lemmas8.
2and8.
3implythatkeX,1I,D1Xk2F+keX,1D,12,IXk2FmineY2nXi=1h2i;eii2:NoticenowmineY=keY,1k,12=kX,1eXk,12kX,1k,12keXk,12.
Alongthelinesforproving8.
3,weobtainkX,1k2keXk2qkeX,1I,D1Xk2F+keX,1D,12,IXk2FvuutnXi=1h2i;eii2:8.
6Inequality6.
1isnowaconsequenceof8.
3and8.
6.
TheproofofTheorem6.
4belowneedsthefollowingresultduetoLi23,pp.
207208,1993.
ForX2Cmn,weintroducethefollowingnotationforak`submatrixofX=xij:Xi1ikj1j`!
def=0BBBB@xi1j1xi1j2xi1j`xi2j1xi2j2xi2j`.
.
.
.
.
.
.
.
.
.
.
.
xikj1xikj2xikj`1CCCCA;8.
7where1i1iknand1j1j`n.
Lemma8.
4LiSupposethatX2Cnnisnonsingular,and1i1iknand1j1j`n,andk+`n.
ThenXi1ikj1j`!
pkX,1k,1p.
Moreover,ifXisunitary,thenXi1ikj1j`!
2=1.
ProofofTheorem6.
4:Letkbetheindexsuchthatpdef=max1inpi;ei=pk;ek:Ren-CangLi:RelativePerturbationTheory37Ifp=0,inequality6.
7clearlyholds.
Assumep0.
Alsoassume,withoutlossofanygenerality,thatkek0:PartitionX;X,1;eXandeX,1conformallyasfollows:X=X1;X2;X,1=W1W2!
;eX=eX1;eX2;eX,1=fW1fW2!
;whereX1;W12CnkandeX1;fW12Cnk,1;andwrite=diag1;2ande=diage1;e2,where12Rkkande12Rk,1k,1.
Itfollowsfromequations8.
1and8.
4that1W1eX2,W1eX2e2=1W1I,D2eX2+W1D,1,IeX2e2;fW2X11,e2fW2X1=fW2I,D1X11+e2fW2D,12,IX1whichgiveW1eX2,,11W1eX2e2=W1I,D2eX2+,11W1D,1,IeX2e2;8.
8fW2X1,e2fW2X1,11=fW2I,D1X1+e2fW2D,12,IX1,11:8.
9Lemma8.
4impliesfor1r1W1eX2rX,1eX,1,1reX,1X,1rkeX,1k,1rkXk,1r;8.
10fW2X1reX,1X,1,1rX,1eX,1rkX,1k,1rkeXk,1r;8.
11sinceW1eX2isakn,k+1submatrixofX,1eX,andfW2X1isan,k+1ksubmatrixofeX,1Xandk+n,k+1=n+1n.
Bearinginmindthatk,11kr=1=kande2r=ek,wehave1,ekk!
keX,1k,1rkXk,1r1,ekk!
W1eX2rby8.
10=W1eX2r,k,11krW1eX2re2rW1eX2r,,11W1eX2e2rW1eX2,,11W1eX2e2r=W1I,D2eX2+,11W1D,1,IeX2e2rby8.
8W1I,D2eX2r+ekkW1D,1,IeX2rkW1krkeX2krkI,D2kr+ekkkD,1,Ikr!
kX,1krkeXkrps1+epkpkqqkI,D2kqr+kI,D,1kqr:Ren-CangLi:RelativePerturbationTheory38Similarly,from8.
9weobtain1,ekk!
kX,1k,1rkeXk,1rkeX,1krkXkrpvuut1+epkpkqqkI,D,12kqr+kI,D1kqr:Inequality6.
7isnowaconsequenceofaboveinequalities.
9ProofsofTheorems5.
1,5.
2,5.
3,5.
4,and5.
5ProofofTheorem5.
1:SinceAisnonnegativedenite,thereisamatrixB2CnnsuchthatA=BB.
WiththisB,eA=DAD=DBBD=eBeB,whereeB=BD.
LetSVDsofBandeBbeB=U1=2VandeB=eUe1=2eV;where1=2=diagp1;p2;;pnande1=2=diagqe1;qe2;;qen.
Inwhatfollows,weactuallyworkwithBBandeBeB,insteadofA=BBandeA=eBeB.
WehaveeBeB,BB=eBDB,eBD,1B=eBD,D,1B:Pre-andpost-multiplytheaboveequationsbyeUandU,respectively,togeteeUU,eUU=e1=2eVD,D,1V1=2:9.
1WriteQdef=eUU=qij.
Equation9.
1implieskeVD,D,1Vk2F=kD,D,1k2F=nXi;j=1jei,jjqeijjqijj2:Sincejqijj2isadoublystochasticmatrix,applyingLemma8.
2andProposition3.
13concludestheproofofinequality5.
2.
Toconrm5.
1,letkbetheindexsuchthatpdef=max1ini;ei=k;ek:Ifp=0,noproofisnecessary.
Assumep0.
Alsoassume,withoutlossofanygenerality,thatkek0:PartitionU;V;eU;eVasfollowsU=U1;U2;V=V1;V2;eU=eU1;eU2andeV=eV1;eV2;whereU1;V12CnkandeU1;eV12Cnk,1,andwrite=diag1;2ande=diage1;e2,where12Rkkande12Rk,1k,1.
Itfollowsfromequation9.
1thate2eU2U1,eU2U11=e1=22eV2D,D,1V11=21:Ren-CangLi:RelativePerturbationTheory39Post-multiplythisequationby,11togete2eU2U1,11,eU2U1=e1=22eV2D,D,1V1,1=21:9.
2Lemma8.
4impliesthateU2U12=1sinceeU2U1isan,k+1ksubmatrixofeUUandk+n,k+1=n+1n.
Bearinginmindthatke2k2=ek=e1=2222andk,11k2=1=k=,1=2122,wehave1,ekk=eU2U12,ke2k2eU2U12k,11k2eU2U12,e2eU2U1,112eU2U1,e2eU2U1,112=e1=22eV2D,D,1V1,1=212by9.
2ke1=22k2eV2D,D,1V12k,1=21k2=sekkeV2D,D,1V12sekkkD,D,1k2;animmediateconsequenceofwhichisinequality5.
1.
Lemma9.
1For;;0,wehave189.
3Thusif;;8,then1,18;;:Proof:Withoutlossofanygenerality,wemayassume.
Nowifor,byProperty7ofProposition3.
7;if;if:Soinequality9.
3hastobetrue.
Considerthecase.
FromtheproofofProposition3.
14,wehavep;pp;pp;p:Ren-CangLi:RelativePerturbationTheory40Byinequality3.
19ofProposition3.
10,wegetimmediatelyinequality9.
3.
ProofofTheorems5.
2and5.
3:SetbB=BD2anddenoteitssingularvaluesbyb1b2bn.
ApplyingTheorem5.
1toBBandbBbB=D2BBD2leadstomax1in2i;b2ikD2,D,12k2andvuutnXi=12i;b2i2kD2,D,12kF:Nowapplyinequality3.
19ofProposition3.
10toobtainmax1ini;bi12kD2,D,12k2andvuutnXi=1i;bi212kD2,D,12kF:9.
4SimilarlyforbB=BD2andeB=D1BD2=D1bB,wehavemax1inbi;ei12kD1,D,11k2andvuutnXi=1bi;ei212kD1,D,11kF:9.
5UndertheassumptionsofTheorem5.
2,byLemma9.
1,wehavei;bibi;ei14kD1,D,11k2kD2,D,12k21432=8;sowehavei;eii;bi+bi;ei1,18i;bibi;ei12kD1,D,11k2+kD2,D,12k21,132kD1,D,11k2kD2,D,12k2;vuutnXi=1i;ei2vuutnXi=1"i;bi+bi;ei1,18i;bibi;ei2snPi=1i;bi2+snPi=1bi;ei21,18max1ini;bibi;ei12kD1,D,11kF+kD2,D,12kF1,132kD1,D,11k2kD2,D,12k2;asexpected.
ThiscompletestheproofofTheorem5.
2.
ToproveTheorem5.
3,wenoticethatpi;eipi;bi+pbi;eipisametriconR2,1=pi;bi+2,1=pbi;eibyProposition3.
112,1,1=pkD2,D,12k2+kD1,D,11k2;by9.
4and9.
5Ren-CangLi:RelativePerturbationTheory41andvuutnXi=1pi;ei2vuutnXi=1pi;bi+pbi;ei2pisametriconRvuutnXi=1pi;bi2+vuutnXi=1pbi;ei22,1=pvuutnXi=1i;bi2+2,1=pvuutnXi=1bi;ei2byProposition3.
112,1,1=pkD2,D,12kF+kD1,D,11kF:by9.
4and9.
5TheseinequalitiescompletetheproofofTheorem5.
3.
ProofofTheorem5.
4:RewriteAandeAasA=SHS=H1=2SH1=2S;eA=SH1=2I+H,1=2HH,1=2H1=2S=I+H,1=2HH,1=21=2H1=2SI+H,1=2HH,1=21=2H1=2S:SetBdef=H1=2SandeBdef=I+H,1=2HH,1=21=2H1=2S,thenA=BBandeA=eBeB.
SetD=I+H,1=2HH,1=21=2,theneB=DB.
NoticethatA=BB=BBandeA=eBeB=eBeBandeBeB=DBBD.
ApplyingTheorem5.
1toBBandeBeByieldstherst"inboth5.
11and5.
12.
ProofofTheorem5.
5:WriteeB=G+GS=I+GG,1GS=DB;whereD=I+GG,1.
NowapplyingTheorem5.
2toBandeB=DByieldstherstinequalitiesinboth5.
13and5.
14.
Togetthesecondinequalities,wenoticeI+E,I+E,1=I+E,1Xi=0,1iEi=E+E+E1Xi=2,1iEi,1;whereE=GG,1andkEk2kG,1k2kGk21;thereforeforanyunitarilyinvariantnormjjjjjjI+E,I+E,1jjjE+Ejjj+jjjEjjj1Xi=1kEki2=jjjE+EjjjjjjEjjj+kEk21,kEk2jjjEjjj:Therestisjustapplicationsofthisinequalityforjjjjjj=kk2andforjjjjjj=kkF.
Ren-CangLi:RelativePerturbationTheory4210ProofofTheorem6.
6Noproofisnecessaryife2A.
Assumethate62A.
HereweconsiderthecasewheneA=DAonly,sincethesituationforthecasewheneA=ADisverysimilar.
eA,eI=A,eI+eA,A=X,eIX,1+D,IXX,1=XhI+X,1D,IX,eI,1i,eIX,1:SinceeA,eIissingular,wehaveforany1p1,kX,1D,IX,eI,1kp1whichgives1kX,1D,IXkpk,eI,1kp=kX,1D,IXkpmax2Ajjje,jaswastobeshown.
11GeneralizedEigenvalueProblemsandGeneralizedSin-gularValueProblemsInthissection,wearegoingtosayafewwordsforthefollowingperturbationsforScaledGeneralizedEigenvalueProblemsandScaledGeneralizedSingularValueProblems.
Asweshallsee,theresultsinprevioussections,aswellasthoseinLi24,1994,canbeappliedtoderiverelativeperturbationboundsforthem.
Generalizedeigenvalueproblem:A1,A2S1H1S1,S2H2S2andeA1,eA2S1eH1S1,S2eH2S2,whereH1andH2arepositivedeniteandkH,1ik2keHi,Hik21fori=1;2,andS1andS2aresomesquarematricesandoneofthemisnonsingular.
Generalizedsingularproblem:fB1;B2gfG1S1;G2S2gandfeB1;eB2gfeG1S1;eG2S2g,whereG1andG2arenonsingularandkG,1ik2keGi,Gik21fori=1;2,andS1andS2aresomesquarematricesandoneofthemisnonsingular.
Forthescaledgeneralizedeigenvalueproblemjustmentioned,withoutlossofanygeneral-ity,weconsiderthecasewhenS2isnonsingular.
ThenthegeneralizedeigenvalueproblemforA1,A2S1H1S1,S2H2S2isequivalenttothestandardeigenvalueproblemforAdef=H,1=22S,12S1H1S1S,12H,1=22;andthegeneralizedeigenvalueproblemforeA1,eA2S1eH1S1,S2eH2S2isequivalenttothestandardeigenvalueproblemforeAdef=D2H,1=22S,12S1eH1S1S,12H,1=22D2;Ren-CangLi:RelativePerturbationTheory43whereD2=D2def=I+H,1=22H2H,1=22,1=2andH2def=eH2,H2:SoboundingrelativedistancesbetweentheeigenvaluesofA1,A2andtheseofeA1,eA2istransformedtoboundingrelativedistancesbetweentheeigenvaluesofthematrixAandtheseofthematrixeA.
Thelattercanbeaccomplishedintwosteps:1.
BoundingrelativedistancesbetweentheeigenvaluesofthematrixAandtheseofbAdef=D2H,1=22S,12S1H1S1S,12H,1=22D2:2.
BoundingrelativedistancesbetweentheeigenvaluesofthematrixbAandtheseofthematrixeA.
DenoteandordertheeigenvaluesofA,bAandeAas1nandb1bnande1en:SetD1=D1def=I+H,1=21H1H,1=21,1=2andH1def=eH1,H1:ByTheorems5.
1and5.
4,wehavefor1jni;bikD2,D,12k2andbi;eikD1,D,11k211.
1andvuutnXi=1hi;bii2kD2,D,12kFandvuutnXi=1hbi;eii2kD1,D,11kF:11.
2ByLemma9.
1,wehavefor1jnifkD1,D,11k2kD2,D,12k28,i;eii;bi+bi;ei1,18i;bibi;eikD2,D,12k2+kD1,D,11k21,18kD1,D,11k2kD2,D,12k2andvuutnXi=1hi;eii2vuutnXi=1"i;bi+bi;ei1,18i;bibi;ei2snPi=1hi;bii2+snPi=1hbi;eii21,18max1ini;bibi;eikD2,D,12kF+kD1,D,11kF1,18kD1,D,11k2kD2,D,12k2:Ren-CangLi:RelativePerturbationTheory44Noticealsothatfori=1;2andforanyunitarilyinvariantnormjjjjjjDi,D,1ikH,1ik2jjjHijjjq1,kH,1ik2kHik2:SowehaveprovedTheorem11.
1LetA1,A2S1H1S1,S2H2S2andeA1,eA2S1eH1S1,S2eH2S2,whereH1andH2arennandpositivedeniteandkH,1ik2keHi,Hik21fori=1;2,andS1andS2aresomesquarematricesandoneofthemisnonsingular.
LetthegeneralizedeigenvaluesofA1,A2andeA1,eA2be1nande1en:IfkD1,D,11k2kD2,D,12k28,thenmax1ini;ei1kH1k2+2kH2k21,1812kH1k2kH2k2;vuutnXi=1hi;eii21kH1kF+2kH2kF1,1812kH1k2kH2k2;whereidef=kH,1ik2q1,kH,1ik2kHik2fori=1;2.
Ontheotherhand,from11.
1and11.
2andProposition3.
11,wegetpi;bi2,1=pkD2,D,12k2andpbi;ei2,1=pkD1,D,11k2andvuutnXi=1hpi;bii22,1=pkD2,D,12kFandvuutnXi=1hpbi;eii22,1=pkD1,D,11kF:SincepisametriconR,wehavefor1jnpi;eipi;bi+pbi;ei2,1=pkD2,D,12k2+kD1,D,11k2andvuutnXi=1hpi;eii2vuutnXi=1hpi;bi+pbi;eii2vuutnXi=1hpi;bii2+vuutnXi=1hpbi;eii22,1=pkD2,D,12kF+kD1,D,11kF:Ren-CangLi:RelativePerturbationTheory45Theorem11.
2LetallconditionsofTheorem11.
1,exceptkD1,D,11k2kD2,D,12k28,hold.
Thenmax1inpi;ei2,1=p1kH1k2+2kH2k2;vuutnXi=1hpi;eii22,1=p1kH1kF+2kH2kF:Astothescaledgeneralizedsingularproblemmentionedabove,weshallconsideritscorrespondinggeneralizedeigenvalueproblem22,37,39forS1G1G1S1,S2G2G2S2andS1eG1eG1S1,S2eG2eG2S2;11.
3instead.
Theorem11.
3LetfB1;B2gfG1S1;G2S2gandfeB1;eB2gfeG1S1;eG2S2g,whereG1andG2arennandnonsingularandkG,1ik2keGi,Gik21fori=1;2,andS1andS2aresomesquarematricesandoneofthemisnonsingular.
LetthegeneralizedsingularvaluesoffB1;B2gandfeB1;eB2gbe1nande1en:If122232,whereit=I+GiG,1i,I+GiG,1i,1tfori=1;2andt=2;F;thenmax1ini;ei1212+221,1321222;vuutnXi=1i;ei2121F+2F1,1321222:Itcanbeprovedthatfori=1;2andt=2;FitkGiG,1i+G,iGiktkGiG,1ikt+kGiG,1ik21,kGiG,1ik2!
kGiG,1ikt1+11,kG,1ik2kGik2!
kG,1ik2kGikt:Proof:ConsiderthecasewhenS2isnonsingular.
ThecasewhenS1isnonsingularcanbehandledanalogously.
By11.
3,weknowthatthesingularvaluesofBdef=G1S1S,12G,12andeBdef=eG1S1S,12eG,12are1nande1en.
SetD1=I+G1G,11;G1=eG1,G1;andD2=I+G2G,12;G2=eG2,G2;Ren-CangLi:RelativePerturbationTheory46theneB=D1BD,12.
ByTheorem5.
2,wehavemax1ini;ei12kD1,D,11k2+kD,2,D2k21,132kD1,D,11k2kD,2,D2k2;vuutnXi=1i;ei212kD1,D,11kF+kD,2,D2kF1,132kD1,D,11k2kD,2,D2k2;asweretobeshown.
Theorem11.
4LetallconditionsofTheorem11.
1,except122232,hold.
Thenmax1inpi;ei121+1=p12+22;vuutnXi=1pi;ei2121+1=p1F+2F:Proof:bythersthalfoftheproofofTheorem11.
3andbyTheorem5.
312ConclusionsWehavedevelopedarelativeperturbationtheoryforeigenvalueandsingularvaluevari-ationsundermultiplicativeperturbations.
Inthetheory,extensionsofthecelebratedHoman-WielandttheoremandWeyl-Lidskiitheoremfromtheclassicalperturbationthe-oryaremade.
Forthis,weintroducedtwokindsofrelativedistancespand.
Topolog-ically,ournewrelativedistancesareequivalenttotheclassicalmeasurementforrelativeaccuracy,butthenewdistanceshavebettermathematicalproperties.
ItisprovedthatpisindeedametriconR;whileisnot.
Oftenitisthecasethatperturbationboundsusingaresharperthanboundsusingp.
Ourunifyingtreatmentinthispapercoversalmostallpreviouslystudiedcasesandyieldssharperboundsthanexistingones.
OurresultsareapplicableimmediatelytothecomputationsofsharperrorboundsintheDemmel-KahanQR8,1990algorithmandFernando-Parlett'simplementationoftheRutishauserQDalgorithm13,1994.
Suchapplicationswillbepublishedelsewhere.
Appendix.
ApisaMetriconRInthisappendix,wewillprove3.
20p;p;+p;for;;2R.
3.
20Asaresult,wehaveRen-CangLi:RelativePerturbationTheory47TheoremA.
1pisametriconR.
WestronglyconjecturethatpisametriconC.
Unfortunately,weareunabletoproveitatthispoint.
LemmaA.
1Thefollowingstatementsareequivalent:1.
p;p;+p;;2.
p;p;+p;forsome06=2C;3.
p;p;+p;forall06=2C.
ThislemmafollowsfromProperty3ofProposition3.
1.
Inwhatfollows,wewillbeworkingwithrealnumbers.
SincepissymmetricwithrespecttoitstwoargumentsProperty2ofProposition3.
1,wemayassume,withoutlossofanygenerality,thatfromnowon:A.
1Therearethreepossiblepositionsfor:oror:A.
2LemmaA.
23.
20holdsfor,andtheequalityholdsifandonlyif=or=.
AproofofthislemmawillbegiveninxA.
3.
Twodierentcasesshallbeconsidered,inordertoconrm3.
20.
1.
0.
2.
0.
A.
1TheCase0.
LemmaA.
2showsthat3.
20istrueif.
Ifeitheror,byProperty8ofProposition3.
1,wehavep;p;p;+p;;if;p;p;+p;;if:A.
2TheCase0.
Wemayassume0and0seeassumptionA.
1.
ConsiderthethreepossiblepositionsA.
2for.
1.
0.
Inthissubcase,1=1=01=.
ByLemmaA.
2andProperty4ofProposition3.
1,wehavep;=p1=;1=p1=;1=+p1=;1==p;+p;:2.
.
ThissubcasehasbeentakencareofbyLemmaA.
2.
3.
0.
Inthissubcase,1=01=1=.
Therestisthesameasinsubcase1above.
Ren-CangLi:RelativePerturbationTheory48A.
3ProofofLemmaA.
2ByLemmaA.
1andbythatswappinganddoesnotlossanygenerality,wemayevenassume,besidesA.
1,thatjj:A.
3Inequality3.
20clearlyholdsifoneof;;iszeroor=or=or=.
Sofromnowon,weassume;and6=0;6=0;6=0:For1p1p;=,ppp+jjp=,+,ppp+jjp=,ppp+jjp+,ppp+jjp=,ppp+jjp+,ppjjp+jjp+,1ppp+jjp,1ppp+jjp!
+,1ppp+jjp,1ppjjp+jjp!
=p;+p;+,jjp,jjpppp+jjpppp+jjpppp+jjp,ppp+jjpjjp,jjp+,jjp,pppp+jjpppjjp+jjpppjjp+jjp,ppp+jjpjjp,p:Nowifjj,thenjjp,jjp0andjjp,p0,andthus,jjp,jjpppp+jjpppp+jjpppp+jjp,ppp+jjpjjp,jjp+,jjp,pppp+jjpppjjp+jjpppjjp+jjp,ppp+jjpjjp,p0:Hencep;p;+p;.
Considernowjj.
Then,jjp,jjpppp+jjpppp+jjpppp+jjp,ppp+jjpjjp,jjp+,jjp,pppp+jjpppjjp+jjpppjjp+jjp,ppp+jjpjjp,p,,jjppp+jjp1ppp+pp,jjp,jjppp+p,ppp+jjpp,jjp,1ppjjp+pp,p,ppjjp+p,ppp+jjpp,p!
0:Ren-CangLi:RelativePerturbationTheory49Thelast"istruebecauseppp+pppjjp+p1ppp+p1ppjjp+pand0p,jjp,jjp,p,;0ppp+p,ppp+jjpp,jjpppjjp+p,ppp+jjpp,p:TheseinequalitiesareconsequencesofLemmaA.
3belowsincefor1p1,fx=xpisconvexandgx=ppxisconcave.
Sowealsohavep;p;+p;forjj.
Theproofforthecasep1iscompleted.
Whenp=1,1=,+,maxfjj;jjg+,1,1maxfjj;jjg1;+1;;aswastobeshown.
LemmaA.
3Supposefunctionsfxandgxaredenedontheintervala;b,andsup-posefxisconvexandgxconcave.
Let.
Thenf,f,f,f,andg,g,g,g,:AproofofthislemmacanbefoundinmostMathematicalAnalysisbooks.
Intuitively,thetwoinequalitiesinLemmaA.
3arewellexplainedbyFigure1.
Acknowledgement:IthankProfessorW.
Kahanforhisconsistentencouragementandsupport,ProfessorJ.
DemmelforhelpfuldiscussionsonopenproblemsinthisresearchareaandProfessorB.
N.
ParlettfordrawingmyattentiontoOstrowskitheorem.
IalsothankDrs.
MingGu,HuanRenandYuhuaWuforhelpingmetoprovewhether2isametriconR.
TheproofofLemmaA.
2wasdiscoveredonlyafterDrs.
MingGuandYuhuaWushowingmetheirprooffor2.
References1J.
BarlowandJ.
Demmel.
Computingaccurateeigensystemsofscaleddiagonallydominantmatrices.
SIAMJournalonNumericalAnalysis,27:762791,1990.
2F.
L.
BauerandC.
T.
Fike.
Normsandexclusiontheorems.
NumerischeMathematik,2:137141,1960.
3R.
Bhatia.
PerturbationBoundsforMatrixEigenvalues.
PitmanResearchNotesinMath-ematics.
LongmannScientic&Technical,Harlow,Essex,1987.
PublishedintheUSAbyJohnWiley.
Ren-CangLi:RelativePerturbationTheory50βγy=f(x)isconvex.
αβγαy=g(x)isconcave.
Figure1:Explaininginequalitiesforconvexandconcavefunctions.
4R.
Bhatia,C.
Davis,andF.
Kittaneh.
Someinequalitiesforcommutatorsandanapplicationtospectralvariation.
AequationesMathematicae,41:7078,1991.
5G.
D.
Birkho.
Tresobservacionessobreelalgebralineal.
UniversidadNacionaldeTucumanRevista,SerieA,5:147151,1946.
6P.
Deift,J.
Demmel,L.
-C.
Li,andC.
Tomei.
ThebidiagonalsingularvaluedecompositionandHamiltonianmechanics.
SIAMJournalonNumericalAnalysis,28:14631516,1991.
7J.
DemmelandW.
Gragg.
Oncomputingaccuratesingularvaluesandeigenvaluesofmatriceswithacyclicgraphs.
LinearAlgebraanditsApplication,185:203217,1993.
8J.
DemmelandW.
Kahan.
Accuratesingularvaluesofbidiagonalmatrices.
SIAMJournalonScienticandStatisticalComputing,11:873912,1990.
9J.
DemmelandK.
Veselic.
Jacobi'smethodismoreaccuratethanQR.
SIAMJournalonMatrixAnalysisandApplications,134:12041245,1992.
10S.
C.
EisenstatandI.
C.
F.
Ipsen.
Relativeperturbationtechniquesforsingularvalueproblems.
ResearchReportYALEUDCSRR942,DepartmentofComputerScience,YaleUniversity,1993.
11S.
C.
EisenstatandI.
C.
F.
Ipsen.
Relativeperturbationboundsforeigenspacesandsingularvectorsubspaces.
InJ.
G.
Lewis,editor,ProceedingsoftheFifthSIAMConferenceonAppliedLinearAlgebra,pages6266,Philadelphia,1994.
SIAMPublications.
12L.
ElsnerandS.
Friedland.
Singularvalues,doublystochasticmatrices,andapplications.
LinearAlgebraanditsApplications,220:161169,1995.
13K.
V.
FernandoandB.
N.
Parlett.
Accuratesingularvaluesanddierentialqdalgorithms.
NumerischeMathematik,67:191229,1994.
14G.
H.
GolubandC.
F.
VanLoan.
MatrixComputations.
JohnsHopkinsUniversityPress,Baltimore,Maryland,2ndedition,1989.
Ren-CangLi:RelativePerturbationTheory5115M.
GuandS.
C.
Eisenstat.
Relativeperturbationtheoryforeigenproblems.
ResearchReportYALEUDCSRR934,DepartmentofComputerScience,YaleUniversity,1993.
16A.
J.
HomanandH.
W.
Wielandt.
Thevariationofthespectrumofanormalmatrix.
DukeMathematicalJournal,20:3739,1953.
17R.
A.
HornandC.
R.
Johnson.
MatrixAnalysis.
CambridgeUniversityPress,Cambridge,1985.
18W.
Kahan.
Accurateeigenvaluesofasymmetrictridiagonalmatrix.
TechnicalReportCS41,ComputerScienceDepartment,StanfordUniversity,Stanford,CA,1966.
revisedJune1968.
19W.
Kahan.
InclusiontheoremsforclustersofeigenvaluesofHermitianmatrices.
Technicalreport,ComputerScienceDepartment,UniversityofToronto,1967.
20W.
Kahan.
SpectraofnearlyHermitianmatrices.
ProceedingsoftheAmericanMathematicalSociety,48:1117,1975.
21G.
DiLena,R.
I.
Peluso,andG.
Piazza.
Resultsontherelativeperturbationofthesingularvaluesofamatrix.
BIT,33:647653,1993.
22R.
-C.
Li.
Boundsonperturbationsofgeneralizedsingularvaluesandofassociatedsubspaces.
SIAMJournalonMatrixAnalysisandApplications,14:195234,1993.
23R.
-C.
Li.
Normsofcertainmatriceswithapplicationstovariationsofthespectraofmatricesandmatrixpencils.
LinearAlgebraanditsApplication,182:199234,1993.
24R.
-C.
Li.
Relativeperturbationtheory:iieigenspaceandsingularsubspacevariations.
Tech-nicalReportUCBCSD-94-856,ComputerScienceDivision,DepartmentofEECS,Univer-sityofCaliforniaatBerkeley,1994.
revisedJanuary1996.
25R.
-C.
Li.
Eigenvaluesofsymmetrizablematrices.
Manuscript,OakRidgeNationalLaboratory,1996.
26V.
B.
Lidskii.
Thepropervaluesofthesumandproductofsymmetricmatrices.
DokladyAkademiiNaukSSSR,75:769772,1950.
InRussian.
TranslationbyC.
BensteravailablefromtheNationalTranslationCenteroftheLibraryofCongress.
27K.
Loewner.
Ubermonotonematrixfunktionen.
Math.
Z.
,38:177216,1934.
28T.
-X.
Lu.
Perturbationboundsofeigenvaluesofsymmetrizablematrices.
NumericalMathe-matics:aJournalofChineseUniversities,16:177185,1994.
InChinese.
29R.
Mathias.
Spectralperturbationboundsforgradedpositivedenitematrices.
Manuscript,DepartmentofMathematics,CollegeofWilliam&Mary,1994.
30R.
MathiasandG.
W.
Stewart.
AblockQRalgorithmandthesingularvaluedecomposition.
LinearAlgebraandItsApplications,182:91100,1993.
31L.
Mirsky.
Symmetricgaugefunctionsandunitarilyinvariantnorms.
QuarterlyJournalofMathematics,11:5059,1960.
32A.
M.
Ostrowski.
AquantitativeformulationofSylvester'slawofinertia.
Proc.
NationalAcad.
SciencesUSA,45:740744,1959.
33B.
N.
Parlett.
TheSymmetricEigenvalueProblem.
Prentice-Hall,EnglewoodClis,NewJersey,1980.
34I.
Slapnicar.
AccurateSymmetricEigenreductionByaJacobiMethod.
PhDthesis,derFer-nuniversitatGesamthochschuleHagen,desFacbereichsMathematik,1992.
Ren-CangLi:RelativePerturbationTheory5235G.
W.
StewartandJ.
-G.
Sun.
MatrixPerturbationTheory.
AcademicPress,Boston,1990.
36J.
-G.
Sun.
Theperturbationboundsofgeneralizedeigenvaluesofaclassofmatrix-pairs.
Math.
Numer.
Sinica,4:2329,1982.
InChinese.
37J.
-G.
Sun.
Perturbationanalysisforthegeneralizedsingularvaluedecomposition.
SIAMJournalonNumericalAnalysis,20:611625,1983.
38J.
-G.
Sun.
Ontheperturbationoftheeigenvaluesofanormalmatrix.
Math.
Numer.
Sinica,6:334336,1984.
InChinese.
39C.
F.
VanLoan.
Generalizingthesingularvaluedecomposition.
SIAMJournalonNumericalAnalysis,13:7683,1976.
40H.
Weyl.
DasasymptotischeVerteilungsgesetzderEigenwertlinearerpartiellerDierential-gleichungenmiteinerAnwendungaufderTheoriederHohlraumstrahlung.
MathematischeAnnalen,71:441479,1912.
41H.
Wielandt.
Anextremumpropertyofsumsofeigenvalues.
ProceedingsoftheAmericanMathematicalSociety,6:106110,1955.
42J.
H.
Wilkinson.
TheAlgebraicEigenvalueProblem.
ClarendonPress,Oxford,England,1965.
43Z.
Zhang.
Ontheperturbationoftheeigenvaluesofanon-defectivematrix.
Math.
Numer.
Sinica,6:106108,1986.
InChinese.