Edelman,A.,Rao,N.R.,Random matrix theory

《Edelman,A.,Rao,N.R.,Random matrix theory》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

ActaNumerica(2005),pp.233297
cCambridgeUniversityPress,2005DOI:10.1017/S0962492904000236PrintedintheUnitedKingdomRandommatrixtheoryAlanEdelmanDepartmentofMathematics,MassachusettsInstituteofTechnology,Cambridge,MA02139,USAE-mail:edelman@math.mit.eduN.RajRaoDepartmentofElectricalEngineeringandComputerScience,MassachusettsInstituteofTechnology,Cambridge,MA02139,USAE-mail:raj@mit.eduRandommatrixtheoryisnowabigsubjectwithapplicationsinmanydiscip-linesofscience,engineeringandfinance.Thisarticleisasurveyspecificallyorientedtowardstheneedsandinterestsofanumericalanalyst.Thissur-veyincludessomeoriginalmaterialnotfoundanywhereelse.Weincludetheimportantmathematicswhichisaverymoderndevelopment,aswellasthecomputationalsoftwarethatistransformingthetheoryintousefulpractice.CONTENTS1Introduction2342Linearsystems2343Matrixcalculus2354Classicalrandommatrixensembles2435Numericalalgorithmsstochastically2546Classicalorthogonalpolynomials2577Multivariateorthogonalpolynomials2628Hypergeometricfunctionsofmatrixargument2649Painlev´eequations26510Eigenvaluesofabillionbybillionmatrix27511Stochasticoperators27812Freeprobabilityandinfiniterandommatrices28313Arandommatrixcalculator28514Non-Hermitianandstructuredrandommatrices28815Asegue290References291 234A.EdelmanandN.R.Rao1.IntroductionTextson‘numericalmethods’teachthecomputationofsolutionstonon-randomequations.Typicallyweseeintegration,differentialequations,andlinearalgebraamongthetopics.Wefind‘random’theretoo,butonlyinthecontextofrandomnumbergeneration.Themodernworldhastaughtustostudystochasticproblems.Alreadymanyarticlesexistonstochasticdifferentialequations.Thisarticlecov-erstopicsinstochasticlinearalgebra(andoperators).Here,theequationsthemselvesarerandom.Likethephysicsstudentwhohasmasteredthelecturesandnowmustfacethesourcesofrandomnessinthelaboratory,nu-mericalanalysisisheadinginthisdirectionaswell.Theironytonewcomersisthatoftenrandomnessimposesmorestructure,notless.2.LinearsystemsThelimitationsonsolvinglargesystemsofequationsarecomputermemoryandspeed.Thespeedofcomputation,however,isnotonlymeasuredbyclockinghardware;italsodependsonnumericalstability,andforiterativemethods,onconvergencerates.Atthistime,thefastestsupercomputerperformsGaussianelimination,i.e.,solvesAx=bonannbynmatrixAforn≈106.Wecaneasilyimaginen≈109onthehorizon.ThestandardbenchmarkHPL(‘high-performanceLINPACK’)choosesAtobearandommatrixwithelementsfromauniformdistributionon[−1/2,1/2].Forsuchlargen,aquestiontoaskwouldbewhetheradoubleprecisioncomputationwouldgiveasingleprecisionanswer.Turningbacktheclock,in1946vonNeumannandhisassociatessawn=100asthelargenumberonthehorizon.HowdowepickagoodtestmatrixA?ThisiswherevonNeumannandhiscolleaguesfirstintroducedtheassumptionofrandomtestmatricesdistributedwithelementsfromindependentnormals.Anyanalysisofthisproblemnecessarilybeginswithanattempttocharacterizetheconditionnumberκ=σ1/σnofthen×nmatrixA.Theygivevarious‘rulesofthumb’forκwhenthematricesaresodistributed.Sometimestheseestimatesarereferredtoasanexpectationandsometimesasaboundthatholdswithhigh,thoughunspecified,probability.Itisinterestingtocomparetheir‘rulesofthumb’withwhatwenowknowabouttheconditionnumbersofsuchrandommatricesasn→∞fromEdelman(1989).Quote.Fora‘randommatrix’oforderntheexpectationvaluehasbeenshowntobeaboutn.(vonNeumann1963,p.14)Fact.E[κ]=∞. Randommatrixtheory235√Quote....wechoosetwodifferentvaluesofκ,namelynand10n.(vonNeumann1963,p.477)√Fact.Pr(κ>ans=1.0e+49*3.320698776793943.32069639128242Thisis,inshort,the‘proofbymatlab’toshowhowJacobianscanbecomputednumericallywithfinitedifferences.3.3.JacobiansofmatrixfactorizationsThecomputationsofmatrixJacobianscanbesignificantlymorecomplicatedthanthescalarderivativesfamiliarinelementarycalculus.ManyJacobi-anshavebeenrediscoveredinvariouscommunities.WerecommendOlkin(1953,2002),andthebooksbyMuirhead(1982)andMathai(1997).WhencomputingJacobiansofmatrixtransformationsorfactorizations,itisim-portanttoidentifythedimensionoftheunderlyingspaceoccupiedbythematrixperturbations.WedgeproductsandtheaccompanyingnotationareusedtofacilitatethecomputationofmatrixJacobians.Thenotationalsocomesinhandyforexpressingtheconceptofvolumeoncurvedsurfacesasindifferentialgeometry.Mathai(1997)andMuirhead(1982)areexcellentreferencesforreaderswhotrulywishtounderstandwedgeproductsasatoolforcom-putingtheJacobiansofcommonlyusedmatrixfactorizationssuchasthoselistedbelow.Whileweexpectourreaderstobefamiliarwithrealandcomplexmatrices,itisreasonabletoconsiderquaternionmatricesaswell.TheparameterβhasbeentraditionallyusedtocountthedimensionoftheunderlyingalgebraasinTable3.2.Inotherbranchesofmathematics,theparameterα=2/βisused.Weprovide,withoutproof,theformulascontainingtheJacobiansoffamil-iarmatrixfactorizations.WeencouragereaderstonoticethatthevanishingTable3.2.Notationusedtodenotewhethertheelementsofamatrixarereal,complexorquaternion(β=2/α).βαDivisionalgebra12real(R)21complex(C)41/2quaternion(H) Randommatrixtheory241oftheJacobianisconnectedtodifficultnumericalproblems.TheparametercountisonlyvalidwheretheJacobiandoesnotvanish.QR(Gram–Schmidt)decomposition(A=QR).Validforallthreecases(β=1,2,4).Qisorthogonal/unitary/symplectic,Risuppertriangu-lar.AandQarem×n(assumem≥n),Risn×n.TheparametercountfortheorthogonalmatrixisthedimensionoftheStiefelmanifoldVm,n.Parametercount:n(n−1)n(n−1)βmn=βmn−β−n+β+n.22Jacobian:nβ(m−i+1)−1(dA)=r(dR)(QdQ).(3.6)iii=1Notation:(dA),(dR)arevolumesoflittleboxesaroundAandR,while(QdQ)denotesthevolumeofalittleboxaroundthestrictlyuppertrian-gularpartoftheantisymmetricmatrixQdQ(seeanumericalillustrationinSection3.2).LU(Gaussianelimination)decomposition(A=LU).Validforallthreecases(β=1,2,4).Allmatricesaren×n,LandUareloweranduppertriangularrespectively,lii=1forall1≤i≤n.Assumethereisnopivoting.Parametercount:2n(n−1)n(n+1)βn=β+β.22Jacobian:n(dA)=|u|β(n−i)(dL)(dU).(3.7)iii=1QΛQ
(symmetriceigenvalue)decomposition(A=QΛQ
).Validforallthreecases(β=1,2,4).HereAisn×nsymmetric/Hermitian/self-dual,Qisn×nandorthogonal/unitary/symplectic,Λisn×ndiagonalandreal.Tomakethedecompositionunique,wemustfixthephasesofthecolumnsofQ(thateliminates(β−1)nparameters)andordertheeigen-values.Parametercount:n(n−1)n(n+1)β+n=β−n−(β−1)n+n.22Jacobian:(dA)=(λ−λ)β(dΛ)(QdQ).(3.8)ijij. Randommatrixtheory249Table4.7.Jointelementdensitiesofann×nmatrixAfromaGaussianensemble.orthogonalβ=11112Gaussianunitaryβ=2exp−AF2n/2πn/2+n(n−1)β/42symplecticβ=4Recallthatthenormaldistributionwithmeanµandvarianceσ2,i.e.,N(µ,σ2),hasadensitygivenby1(x−µ)2√exp−,2πσ22σ2fromwhichitisfairlystraightforwardtoverifythatthejointelementdensityofAwrittenas11exp−A2/2(4.2)2n/2πn(n+1)/4FcanbeobtainedbytakingproductsofthennormalsalongthediagonalhavingdensityN(0,1)andn(n−1)/2normalsintheoff-diagonalshavingdensityN(0,1/2).Table4.7liststhejointelementdensityforthethreeGaussianensemblesparametrizedbyβ.Nowthatwehaveobtainedthejointelementdensities,wesimplyhavetofollowtheprescriptiondiscussedearliertoobtainthejointeigenvaluedensities.InthecaseoftheGaussianensembles,thematrixfactorizationA=QΛQdirectlyyieldstheeigenvaluesandtheeigenvectors.Hence,applyingtheJacobianforthistransformationgivenby(3.8)allowsustoderivethejointdensitiesfortheeigenvaluesandtheeigenvectorsofA.Weobtainthejointeigenvaluedensitiesby‘integrating’outtheeigenvectors.Weliketothinkofthenotionofthe‘mostnatural’matrixfactorizationthatallowsustocomputethejointeigenvaluedensitiesintheeasiestman-ner.FortheGaussianensembles,thesymmetriceigenvaluedecompositionA=QΛQisthemostobviouschoice.ThisnotthecasefortheWishartandthemanovaensembles.Inthiscontext,whatmakesamatrixfactorization‘natural’?Allowustoelaborate.ConsidertheWishartmatrixensembleWβ(m,n)=AA,whereA=Gβ(m,n)isamultivariateGaussian.Itsjointelementdensitycanbecom-putedratherlaboriouslyinatwo-stepmannerwhosefirststepinvolveswrit-ingW=QRandthenintegratingouttheQ,leavingtheR.ThesecondstepisthetransformationW=RRwhichistheCholeskyfactorizationofamatrixinnumericalanalysis.TheconclusionisthatalthoughwemayobtainthejointdensityoftheelementsofWaslistedinTable4.8,thisprocedureismuchmoreinvolvedthanitneedstobe. 250A.EdelmanandN.R.RaoTable4.8.JointelementdensityoftheWishartensembleWβ(m,n)(m≥n).orthogonalβ=1etr(−W/2)(detW)β(m−n+1)/2−1Wishartunitaryβ=22mnβ/2Γβsymplecticβ=4n(mβ/2)Thisiswherethenotionofa‘natural’matrixfactorizationcomesin.ThoughitseemsstatisticallyobvioustothinkofWishartmatricesasco-variancematricesandcomputethejointdensityoftheeigenvaluesofAAdirectly,itismorenaturaltoderivethejointdensityofthesingularvaluesofAinstead.SinceAisamultivariateGaussian,theJacobianofthefac-torizationA=UΣVgivenby(3.9)canbeusedtodirectlydeterminethejointdensityofthesingularvaluesandthesingularvectorsofWfromthejointelementdensityofAin(4.1).WecanthenintegrateoutthesingularvectorstoobtainthejointdensityofthesingularvaluesofAandhencetheeigenvaluesofW=AA.ThetechnicalitiesofthismaybefoundinEdelman(1989).Similarly,thecorresponding‘natural’factorizationforthemanovaen-semblesisthegeneralizedsingularvaluedecomposition.NotethatthesquareofthegeneralizedsingularvaluesoftwomatricesAandBisthesameastheeigenvaluesof(BB)−1(AA),sothattheeigenvaluesofthemanovamatrixJβ(m1,m2,n)=(I+W(m1,n)−1W(m2,n))−1canbeob-tainedbyasuitabletransformation.Table4.1summarizesthematrixfactorizationsassociatedwiththeclas-sicalrandommatrixensemblesthatallowustocomputethejointeigen-valuedensitiesinthemostnaturalmanner.Laterwewilldiscussadditionalconnectionsbetweenthesematrixfactorizations,andclassicalorthogonalpolynomials.4.5.JointeigenvaluedensitiesoftheclassicalensemblesThethreeGaussianensembleshavejointeigenvalueprobabilitydensityfunc-tionPββ−nλ2/2Gaussian:fβ(λ)=c|λi−λj|ei=1i,(4.3)Hiπ(j)ori>j.TheresultfromrandommatrixtheoryisthatthenumberofpermutationsoflengthnwithlongestincreasingsubsequencelessthanorequaltolengthkisgivenbyE|tr(Q)|2n.QkkWecanverifythisnumericallyusingwhatweknowaboutgeneratingHaarunitaryrandommatricesfromSection4.6.WecanconstructafunctioninmatlabthatgeneratesaHaarunitarymatrix,computesthequantity|trQk|2nandaveragesitovermanytrials:functionL=longestsubsq(n,k,trials);expt=[];foridx=1:trials,%GenerateHaarunitarymatrix[Q,R]=qr(randn(k)+i*randn(k));Q=Q*diag(exp(i*2*pi*rand(k,1)));expt=[expt;abs(trace(Q))^(2*n)];endmean(exp) 254A.EdelmanandN.R.RaoTable4.9.Permutationsforn=4.123421343124412312432143314241321324231432144213134223413241423114232413341243121432243134214321Forn=4,thereare24possiblepermutationslistedinTable4.9.Weunderlinethefourteenpermutationswithlongestincreasingsubsequenceoflength≤2.Ofthese,onepermutation(4321)haslength1andtheotherthirteenhavelength2.Ifweweretorunthematlabcodeforn=4andk=2and30000trialswewouldget:>>longestsubsq(4,2,30000)ans=14.1120whichisapproximatelyequaltothenumberofpermutationsoflengthlessthanorequalto2.Itcanbereadilyverifiedthatthecodegivestherightan-swerforothercombinationsofnandkaswell.Wenotethatforthisnumer-icalverification,itwascriticallyimportantthataHaarunitarymatrixwasgenerated.IfweweretouseamatrixwithoutHaarmeasure,forexamplesimplyusingthecommand[Q,R]=qr(randn(n)+i*randn(n))withoutran-domlyperturbingthephases,asdescribedinSection4.6,wewouldnotgettherightanswer.Theauthorsstillfinditremarkablethattheanswertoaquestionthissimple(atleastintermsofformulation)involvesintegralsoverHaarunitarymatrices.Thereis,ofcourse,adeepmathematicalreasonforthisthatisrelatedtothecorrespondencebetween,ontheonehand,permutationsandcombinatorialobjectsknownasYoungtableaux,viatheSchenstedcorrespondence,and,ontheotherhand,representationsofthesymmetricgroupandtheunitarygroup.ThereadermaywishtoconsultRains(1998),AldousandDiaconis(1999)andOdlyzkoandRains(1998)foradditionaldetails.RelatedworksincludeBorodin(1999),TracyandWidom(2001)andBorodinandForrester(2003).5.NumericalalgorithmsstochasticallyMatrixfactorizationalgorithmsmaybeperformedstochasticallygivenGaussianinputs.Whatthismeansisthatinsteadofperformingthematrixreductionsonacomputer,theycanbedonebymathematics.Thethree Randommatrixtheory255thatarewellknown,thoughwewillfocusonthelattertwo,are:(1)Gram–Schmidt(theqrdecomposition)(2)symmetrictridiagonalization(standardfirststepofeig),and(3)bidiagonalization(standardfirststepofsvd).ThebidiagonalizationmethodisduetoGolubandKahan(1965),whilethetridiagonalizationmethodisduetoHouseholder(1958).Thesetwolinearalgebraalgorithmscanbeappliedstochastically,anditisnotveryhardtocomputethedistributionsoftheresultingmatrix.Thetwokeyideasare:(1)theχrdistribution,and(2)theorthogonalinvarianceofGaussians.Theχristheχ-distributionwithrdegreesoffreedomwhererisanyrealnumber.ItcanbederivedfromtheunivariateGaussianandisalsothesquarerootoftheχ2r-distribution.HenceitmaybegeneratedusingthematlabStatisticsToolboxusingthecommandsqrt(chi2rnd(r)).Iftheparameterrisapositiveintegern,onedefinitionofχnisgivenbyG(n,1)2,inotherwords,the2-normofann×1vectorofindepend-entstandardnormals(ornorm(randn(n,1))inmatlab).Theprobabilitydensityfunctionofχncanthenbeextendedtoanyrealnumberrsothattheprobabilitydensityfunctionofχrisgivenby1xr−1−x2/2fr(x)=r/2−11e.2Γr2TheorthogonalinvarianceofGaussiansismentionedinSection4.3.InthisformitmeansthatG1GG1G..D..H.=.,......G1GifeachGdenotesanindependentstandardGaussianandHanyindependentorthogonalmatrix(suchasareflector).Thus,forexample,thefirsttwostepsofGram–Schmidtappliedtoann×nrealGaussianmatrix(β=1)are:GG···GχnG···GχnG···GGG···GG···Gχn−1···G......→....→.....···..···.···.GG···GG···GGG 256A.EdelmanandN.R.RaoTable5.1.Tri-andbidiagonalmodelsfortheGaussianandWishartensembles.N(0,2)χ(n−1)βGaussianχ(n−1)βN(0,2)χ(n−2)βEnsembleHβ√1......n∼2...n∈Nχ2βN(0,2)χβχβN(0,2)Wishartβββ
ensembleLn=BnBn,whereχ2an∈Nχβ(n−1)χ2a−ββa∈RBn∼....β..a>(n−1)2χβχ2a−β(n−1)ApplyingthesameideasfortridiagonalorbidiagonalreductiongivestheanswerlistedinTable5.1,wheretherealcasecorrespondstoβ=1,complexβ=2andquaternionβ=4.FortheGaussianensembles,beforescalingthediagonalelementsarei.i.d.normalswithmean0andvariance2.Thesubdiagonalhasindependentelementsthatareχvariablesasindicated.Thesuperdiagonaliscopiedtocreateasymmetrictridiagonalmatrix.ThediagonalandthesubdiagonalsforthebidiagonalWishartensemblesareindependentelementsthatareχ-distributedwithdegreesoffreedomhavingarithmeticprogressionsofstepsizeβ.Thereisatridiagonalmatrixmodelfortheβ-Jacobiensemblealso,asdescribedinKillipandNenciu(2004);thecorrespondencebetweentheCSdecompositionandtheJacobimodelisspelledoutinSutton(2005).Othermodelsfortheβ-JacobiensembleincludeLippert(2003).Thereisbothanimportantcomputationalandtheoreticalimplicationofapplyingthesematrixfactorizationsstochastically.Computationallyspeak-ing,oftenmuchofthetimegoesintoperformingthesereductionsforagivenrealizationoftheensemble.HavingthemavailableanalyticallymeansthattheconstructionsinSection4.3arehighlyinefficientfornumericalsimu-lationsoftheHermiteandLaguerreensembles.Instead,wecangeneratethenmuchmoreefficientlyusingmatlabcodeandtheStatisticsTool-boxaslistedinTable5.2.ThetangiblesavingsinstorageO(n2)toO(n)isreflectedinsimilarsavingsincomputationalcomplexitywhencomput-ingtheireigenvaluestoo.Notsurprisingly,theseconstructionshavebeenrediscoveredindependentlybyseveralauthorsindifferentcontexts.Trot-ter(1984)useditinhisalternatederivationofWigner’ssemi-circularlaw. Randommatrixtheory257Table5.2.Generatingtheβ-Hermiteandβ-Laguerreensemblesefficiently.Ensemblematlabcommands%Pickn,betad=sqrt(chi2rnd(beta*[n:-1:1]))’;β-HermiteH=spdiags(d,1,n,n)+spdiags(randn(n,1),0,n,n);H=(H+H’)/sqrt(2);%Pickm,n,beta%Picka>beta*(n-1)/2;d=sqrt(chi2rnd(2*a-beta*[0:1:n-1]))’;β-Laguerres=sqrt(chi2rnd(beta*[n:-1:1]))’;B=spdiags(s,-1,n,n)+spdiags(d,0,n,n)L=B*B’;Similarly,Silverstein(1985)and,morerecently,BaxterandIserles(2003)haverederivedthisresult;probablymanyothershaveaswell.Theoreticallytheparameterβplaysanewimportantrole.Theanswersshowthatinsistingonβ=1,2and4isnolongernecessary.Whilethesethreevalueswillalwaysplaysomethingofaspecialrole,likethemath-ematicianwhoinventstheGammafunctionandforgetsaboutcountingpermutations,wenowhaveawholecontinuumofpossiblebetasavailabletous.Whileclearlysimplifyingthe‘book-keeping’intermsofwhethertheelementsarereal,complexorquaternion,thisformalismcanbeusedtore-interpretandrederivefamiliarresultsasinDumitriu(2003).ThegeneralβversionrequiresageneralizationofGβ(1,1).Wehavenotseenanyliteraturebutformallyitseemsclearhowtoworkwithsuchanobject(rulesofalgebraarestandard,rulesofadditioncomefromthenormaldistribution,andtheabsolutevaluemustbeaχβdistribution).Fromthere,wemightformallyderiveageneralQforeachβ.6.ClassicalorthogonalpolynomialsWehavealreadyseeninSection4thattheweightfunctionassociatedwithclassicalorthogonalpolynomialsplaysanimportantroleinrandommatrixtheory.Givenaweightfunctionw(x)andaninterval[a,b]theorthogonalpoly-nomialssatisfytherelationshipbpj(x)pk(x)w(x)dx=δjk.aInrandommatrixtheorythereisinterestinmatriceswithjointeigen- 258A.EdelmanandN.R.RaoTable6.1.Theclassicalorthogonalpolynomials.PolynomialInterval[a,b]w(x)2Hermite(−∞,∞)e−x/2Laguerre[0,∞)xke−xJacobi(−1,1)(1−x)a(1+x)bvaluedensityproportionaltow(λi)|∆(λ)|βwhere∆(x)=(xi−xj).i0)sin(π(x−y))V‘bulk’[−s,s]sineπ(x−y)√√√√√√yJα(x)Jα(y)−xJα(y)Jα(x)III‘hardedge’(0,s]Bessel2(x−y)Ai(x)Ai(y)−Ai(x)Ai(y)II‘softedge’[s,∞)Airyx−y 268A.EdelmanandN.R.RaobulkhardedgedensityofeigenvaluessoftedgeFigure9.1.Regionscorrespondingtoeigenvaluedistributionsthatareofinterestinrandommatrixtheory.edge’applies(becausethereisstill‘wiggleroom’)whenthedensityhitsthehorizontalaxis,whilethe‘hardedge’applieswhenthedensityhitstheverticalaxis(nofurtherroomontheleftbecauseofpositivityconstraintsontheeigenvalues,forexampleasisthecaseforthesmallesteigenvalueoftheLaguerreandJacobianensembles).ThisisillustratedinFigure9.1andisreflectedinthechoiceoftheintegrationintervalsinTable9.1aswell.Thedistributionsarisingherearebecomingincreasinglyimportantastheyareshowingupinmanyplaces.Authorshaveimaginedaworld(per-hapsinthepast)wherethenormaldistributionmightbefoundexperiment-allyormathematicallybutwithoutthecentrallimittheoremtoexplainwhy.ThisishappeningherewiththesedistributionsasintheconnectiontothezerosoftheRiemannzetafunction(discussedinSection9.3),combinator-ialproblems(Deift2000),andgrowthprocesses(Johansson2000a).Therelevanceofβinthiscontexthasnotbeenfullyexplored.9.2.ThelargesteigenvaluedistributionandPainlev´eIIThedistributionoftheappropriatelynormalizedlargesteigenvaluesoftheHermite(β=1,2,4)andLaguerre(β=1,2)ensemblescanbecomputedfromthesolutionofthePainlev´eIIequation:q=sq+2q3(9.2) Randommatrixtheory269withtheboundaryconditionq(s)∼Ai(s),ass→∞.(9.3)TheprobabilitydistributionsthusobtainedarethefamousTracy–Widomdistributions.Theprobabilitydistributionf2(s),correspondingtoβ=2,isgivenbydf2(s)=F2(s),(9.4)dswhere∞F(s)=exp−(x−s)q(x)2dx.(9.5)2sThedistributionsf1(s)andf4(s)forβ=1andβ=4arethederivativesofF1(s)andF4(s)respectively,whicharegivenby∞F(s)2=F(s)exp−q(x)dx(9.6)12sand22s∞F42=F2(s)coshq(x)dx.(9.7)23sThesedistributionscanbereadilycomputednumerically.Tosolveusingmatlab,firstrewrite(9.2)asafirst-ordersystem:dqq=3.(9.8)dsqsq+2qThiscanbesolvedasaninitialvalueproblemstartingats=s0=suffi-cientlylargepositivenumber,andintegratingbackwardsalongthes-axis.Theboundarycondition(9.3)thenbecomestheinitialvaluesq(s0)=Ai(s0),(9.9)q(s)=Ai(s).00Thisproblemcanbesolvedinjustafewlinesofmatlabusingthebuilt-inRunge–Kutta-basedODEsolverode45.Firstdefinethesystemofequationsasaninlinefunctiondeq=inline(’[y(2);s*y(1)+2*y(1)^3]’,’s’,’y’);Nextspecifytheintegrationintervalandthedesiredoutputtimes:s0=5;sn=-8;sspan=linspace(s0,sn,1000);Theinitialvaluescanbecomputedasy0=[airy(s0);airy(1,s0)] 270A.EdelmanandN.R.Rao0.7β=1β=20.6β=40.50.4f(s)β0.30.20.10−0.1−8−6−4−20246sFigure9.2.TheTracy–Widomdistributionsforβ=1,2,4.Now,theintegrationtolerancescanbesetandthesystemintegrated:opts=odeset(’reltol’,1e-13,’abstol’,1e-15);[s,y]=ode45(deq,sspan,y0,opts);q=y(:,1);Thefirstentryofthematlabvariableyisthefunctionq(s).Thedistribu-tionsF2(s),F1(s)andF4(s)canbeobtainedfromq(s)byfirstsettingtheinitialvalues:dI0=I0=J0-0;thennumericallyintegratingtoobtain:dI=-[0;cumsum((q(1:end-1).^2+q(2:end).^2)/2.*diff(s))]+dI0;I=-[0;cumsum((dI(1:end-1)+dI(2:end))/2.*diff(s))]+I0;J=-[0;cumsum((q(1:end-1)+q(2:end))/2.*diff(s))]+J0;Finally,usingequations(9.5),(9.6),and(9.7)weobtainthedesireddistri-butionsas:F2=exp(-I);F1=sqrt(F2.*exp(-J));F4=sqrt(F2).*(exp(J/2)+exp(-J/2))/2;s4=s/2^(2/3);Notethatthetrapezoidalrule(cumsumfunctioninmatlab)isusedtoapproximatenumericallytheintegralsin(9.5),(9.6)and(9.7)respectively. Randommatrixtheory271Theprobabilitydistributionsf2(s),f1(s),andf4(s)canthencomputedbynumericaldifferentiation:f2=gradient(F2,s);f1=gradient(F1,s);f4=gradient(F4,s4);TheresultisshowninFigure9.2.NotethatmoreaccuratetechniquesforcomputingtheTracy–WidomdistributionsareknownandhavebeenimplementedasinEdelmanandPersson(2002).Dieng(2004)discussesthenumericsofanothersuchimplementation.Thesedistributionsareconnectedtorandommatrixtheorybythefol-lowingtheorems.Theorem9.1.(TracyandWidom2000a)Letλmaxbethelargestei-genvalueofGβ(n,n),theβ-Hermiteensemble,forβ=1,2,4.Thenormal-izedlargesteigenvalueλmaxiscalculatedas1√λmax=n6(λmax−2n).Then,asn→∞,Dλmax−→Fβ(s).Theorem9.2.(Johnstone2001)LetλmaxbethelargesteigenvalueofW1(m,n),therealLaguerreensemble(β=1).Thenormalizedlargesteigenvalueλiscalculatedasmaxλmax−µmnλmax=,σmnwhereµmnandσmnaregivenby1√√2√√113µmn=(m−1+n),σmn=(m−1+n)√+.m−1nThen,ifm/n→γ≥1asn→∞,Dλmax−→F1(s).Theorem9.3.(Johansson2000b)LetλmaxbethelargesteigenvalueofW2(m,n),thecomplexLaguerreensemble(β=2).Thenormalizedlargesteigenvalueλiscalculatedasmaxλmax−µmnλmax=,σmnwhereµmnandσmnaregivenby1√√2√√113µmn=(m+n),σmn=(m+n)√+.mn 272A.EdelmanandN.R.Raoβ=1β=20.60.60.50.50.40.4Probability0.3Probability0.30.20.20.10.100−6−4−2024−6−4−2024NormalizedandscaledlargesteigenvalueNormalizedandscaledlargesteigenvalueFigure9.3.ProbabilitydistributionofscaledlargesteigenvalueoftheHermiteensembles(105repetitions,n=109).Then,ifm/n→γ≥1asn→∞,Dλmax−→F2(s).Figure9.3comparestheprobabilitydistributionofthescaledlargeei-genvalueoftheGOE,andGUEwiththenumericalresultsforabillionbybillionmatrixover105trials.Wetalkabouthowwegeneratedatapointsforabillionbybillionmatrixlaterinthisarticle.RelatedresultsincludeSoshnikov(1999).Dieng(2004)derivesPainlev´e-typeexpressionsforthedistributionofthekth-largesteigenvalueintheGOEandGSEintheedgescalinglimit.9.3.TheGUElevelspacingsdistributionandPainlev´eVAnotherquantitywithaninterestingprobabilitydistributionisthespa-cingsoftheeigenvaluesoftheGaussianunitaryensemble,G2(n,n).Thenormalizedspacingsoftheeigenvaluesλ1≤λ2≤···≤λmarecomputedaccordingtoλk+1−λk2δk=2βn−λk,k≈n/2.(9.10)πβThedistributionoftheeigenvaluesisalmostuniform,withaslightdeviationatthetwoendsofthespectrum.Therefore,onlyhalfoftheeigenvaluesareused,andonequarteroftheeigenvaluesateachendisdiscarded. Randommatrixtheory273Randommatrixeigenvaluedistribution10.90.80.70.60.5Probability0.40.30.20.100123456NormalizedconsecutivespacingsFigure9.4.ProbabilitydistributionofconsecutivespacingsoftheeigenvaluesofaGUEensemble(1000repetitions,n=1000).Theprobabilitydistributionp(s)fortheeigenvaluespacingswhenβ=2canbecomputedwiththesolutiontothePainlev´eVnonlineardifferentialequation:(tσ)2+4(tσ−σ)tσ−σ+(σ)2=0(9.11)withtheboundarycondition2tt+σ(t)≈−−,ast→0.(9.12)ππThenp(s)isgivenbyd2p(s)=E(s),(9.13)ds2whereπsσ(t)E(s)=expdt.(9.14)0tExplicitdifferentiationgives1p(s)=πsσ(πs)−σ(πs)+σ(πs)2E(s).(9.15)s2Thesecond-orderdifferentialequation(9.11)canbewrittenasafirst-order 274A.EdelmanandN.R.Raosystemofdifferentialequations:dσσ=22.(9.16)dtσ−(σ−tσ)(tσ−σ+(σ))tThisissolvedasaninitialvalueproblemstartingatt=t0=verysmallpositivenumber.Thevaluet=0hastobeavoidedbecauseofthedivisionbytinthesystemofequations.Thisisnotaproblem,sincetheboundarycondition(9.12)providesanaccuratevalueforσ(t0)(aswellasE(t0/π)).Theboundaryconditionsforthesystem(9.16)thenbecomeσ(t)=−t0−(t0)2,0ππ(9.17)σ(t)=−1−2t0.0ππThissystemcanbesolvednumericallyusingmatlab.9.4.TheGUElevelspacingsdistributionandtheRiemannzetazerosIthasbeenobservedthatthezerosoftheRiemannzetafunctionalongthecriticallineRe(z)=1(forzlarge)behavesimilarlytotheeigenvaluesof2randommatricesintheGUE.Here,thedistributionofthescaledspacingsofthezerosiscomparedtothecorrespondinglevelspacingdistributioncomputedusingthePainlev´eVequation.Riemannzetazerodistribution10.90.80.70.60.5Probability0.40.30.20.100123456NormalizedconsecutivespacingsFigure9.5.ProbabilitydistributionofconsecutivespacingsofRiemannzetazeros(30,000zeros,n≈1012,1021,1022). Randommatrixtheory275Definethenthzeroγnas1ζ+iγn=0,0<γ1<γ2<···.(9.18)2Computeanormalizedspacing:γnlogγn/2πγ˜n==γn·.(9.19)avspacingnearγn2πZerosoftheRiemannzetafunctioncanbedownloadedfromOdlyzko(2001).Assumingthatthematlabvariablegammacontainsthezeros,andthevari-ableoffsettheoffset,thesetwolinescomputetheconsecutivespacingsγ˜n+1−γ˜nandplotthehistogram:delta=diff(gamma)/2/pi.*log((gamma(1:end-1)+offset)/2/pi);%NormalizeandplotthehistogramofthespacingsTheresultcanbefoundinFigure9.5,alongwiththePainlev´eVdistri-bution.10.EigenvaluesofabillionbybillionmatrixWediscusshowknowledgeofnumericalalgorithmsandsoftwareallowustoperformrandommatrixsimulationsveryefficiently.Inthiscasestudy,weillustrateanimprovementrarelyseenincomputation.Wesucceededingoingfromn=100ton=109,i.e.,wecancomputethelargesteigenvalueofabillionbybillionmatrixinthetimerequiredbynaivemethodsforahundredbyhundredmatrix.Pushington=1012iswithinreach.WedeviseanumericalexperimenttoverifythatthedistributionoftheappropriatelynormalizedandscaledlargesteigenvalueoftheGOEensembleisgivenbytheTracy–WidomdistributionF2(s)in(9.5).RecallthataninstanceoftheGOEensemble(β=1)canbecreatedconvenientlyinmatlabas:A=randn(n);A=(A+A’)/2;Itisnowstraightforwardtocomputethedistributionforλmaxbysimulation:foridx=1:trialsA=randn(n);A=(A+A’)/2;lmax=max(eig(A));lmaxscaled=n^(1/6)*(lmax-2*sqrt(n));%Storelmaxend%Createandplothistogram 276A.EdelmanandN.R.RaoTheproblemwiththistechniqueisthatthecomputationalrequirementsandthememoryrequirementsgrowrapidlywithn.StoringthematrixArequiresn2double-precisionnumbers,soonmostcomputerstodaynhastobelessthan104.Furthermore,computingalltheeigenvaluesofafullHermitianmatrixrequirescomputingtimeproportionalton3.Thismeansthatitwilltakemanydaystocreateasmoothhistogrambysimulation,evenforrelativelysmallvaluesofn.Toimproveuponthissituation,wecaninsteadstudytheβ-Hermitetri-diagonalensembleasinTable5.1:N(0,2)χ(n−1)βχ(n−1)βN(0,2)χ(n−2)βHβ∼√1.......(10.1)n...2χ2βN(0,2)χβχβN(0,2)RecallthatN(0,2)isazero-meanGaussianwithvariance2,andχristhesquare-rootofaχ2-distributednumberwithrdegreesoffreedom.Notethatthematrixissymmetric,sothesubdiagonalandthesuperdiagonalarealwaysequal.Thismatrixhasatridiagonalsparsitystructure,andonly2n−1double-precisionnumbersarerequiredtostoreaninstanceofit.Thetimeforcomputingthelargesteigenvalueisproportionalton,eitherusingKrylovsubspace-basedmethodsorthemethodofbisection(TrefethenandBau1997).Thisiscertainlyanimprovement,thoughnotsubstantialenoughtodoasimulationofabillionbybillionGOEasinFigure9.3.Thefollowingcodecan,however,beusedtocomputethelargesteigen-valueofabillionbybillionGOE(β=1):beta=1;n=1e9;opts.disp=0;opts;issym=1;alpha=10;k=round(alpha*n^(1/3));%cutoffparametersd=sqrt(chi2rnd(beta*n:-1:(n-k-1)))’;H=spdiags(d,1,k,k)+spdiags(randn(k,1),0,k,k);H=(H+H’)/sqrt(4*n*beta);%Scalesolargesteigenvalueisnear1eigs(H,1,1,opts);Thetechnologyunderlyingthiscodeisremarkableanddeservestobewidelyknown.Anumberofinterestingtricksarecombinedtogether.•Theobservationthatifk=10n1/3,thenthelargesteigenvalueisde-terminednumericallybythetopk×ksegmentofn.(ThisisrelatedtothedecayoftheAiryfunctionthatarisesinthekernelwhoseeigenval-uesdeterminethelargesteigenvaluedistribution.The‘magicnumber’10hereisnotmeanttobeprecise.Itapproximatestheindexksuchthatv(k)≈,where=2−52fordoubleprecisionarithmetic,andvisv(1) Randommatrixtheory277theeigenvectorcorrespondingtothelargesteigenvalue.Forsmallβ,itmaybenecessarytocrankupthenumber10toalargervalue.)•Sparsematrixstorage.(OnlyO(n)storageisused.)•Tridiagonalensembleformulas.(Anybetaisavailableduetothetri-diagonalensemble.)•TheLanczosalgorithmforeigenvaluecomputation.(Thisallowsthecomputationofthelargesteigenvaluefasterthantypicalgeneralpur-poseeigensolvers.)•Theshift-and-invertacceleratortoLanczosandArnoldi.(Sinceweknowtheeigenvaluesarenear1,wecanacceleratetheconvergenceofthelargesteigenvalue.)•Thearpacksoftwarepackageasmadeavailableseamlesslyinmatlab.(TheArnoldipackagecontainsstateoftheartdatastructuresandnumericalchoices.)Twoofthesetricksaremathematical.ThefirstoneistheabilitytousetridiagonalensemblestogeneratematriceswhoseeigenvaluesmatchtheGOEdistribution.Thisallowsustoavoidusingdensematricesagainforrandommatrixexperiments.Thesecondmathematicaltrickistheabilitytocutoffthetopsegmentofthematrixtoobtainaccuratelythelargesteigenvalue.Itwouldbealltooeasytotakeforgrantedthetechnologyavailablefortheremainingtricks.Itwasnotsomanyyearsagothattheuserwouldhavetocodeupthesparsematrixstoragemadeavailablebythe‘spdiags’commandortheabilitytopeeloffthelargesteigenvalueandgiveastartingguessthatismadeavailablein‘eigs’.Thoughnumericalanalystsarewellversedinsuchnumericaltechniques,wewouldprobablystillnothavebotheredtoimplementtheshift-and-invertArnoldi-stylealgorithmsourselves.Ithasbeensaidthattechnologyadvancesbythenumberofoperationsthatwedonothavetothinkabout.Thisisagreatexample.Incidentally,forusersinterestedinalloftheeigenvaluesofthetridiag-onalmatrix(HermiteensemblessuchastheGOE,GUE,GSE)orallthesingularvaluesofabidiagonalmatrix(LaguerreensemblessuchasWis-hartmatrices),thenthelapackroutinesDSTEQRandDBDSQRcancomputetheeigenvalueswithlinearstorageandinquadratictime.Userswhosimplyusematlab’seig,Mathematica’sEigenvalues,orMaple’slinalg[eigenvalues]areataseveredisadvantage.Weremarkthatfurtherimprovementsarepossible(andhavebeenimple-√mented!)ifweusetheapproximationχ≈n+√1G.Thisapproximationn2formsthebasisoftheideasinthenextsection.Therearefurthertricksavailable,suchasusingthemethodofbisection(TrefethenandBau1997) 278A.EdelmanandN.R.Rao√andapproximatingχnwithsimplyn.SeeEdelmanandPersson(2002)formoredetails.11.Stochasticoperators√Foryears,thefirstauthorwasmystifiedbythenotationdtoftenfoundinintegralsconnectedwiththeBlack–Scholesmodelofoptionspricinginfinance.Thesimplefactthathewasmissingisthat,ifonehasGaussianrandomvariables,thenaturalquantitythatadds(thus,thelinearfunction)isthevariance,whichisconnectedtothesquareofthevariable.Thereissomemathematicstobecompletedtounderstandfullyhowwell-definedisthenotionoftheeigenvaluesofastochasticoperator.Carefulanalysiswilltellwhetherdifferentdiscretizationsgivethesamelimitingeigenvaluedistributions.Nonetheless,aswewilloutline,thereisanideaherethatwefeelissufficientlyimportantthatwecannotaffordtowaitforthissortofanalysis.WedefineaWienerprocessdifferentiallyas√dW=(standardnormal)·dt.TheintegralofsuchaprocessW(t)(Brownianmotion)isW(t)=dW.Thisisprobablybestgraphedinmatlabwiththecommand:t=[dt:dt:1]’;W=cumsum(randn(length(t),1))*sqrt(dt);plot([0;t],[0;W])wheredt=verysmallnumbernotequaltozeroandW(0)=0.AgoodreferenceonBrownianmotionisKaratzasandShreve(1991).Everytimewe‘rollthedice’wegetanewW,butitisalwaysthecasethatW(t)isaGaussianwithvariancet.Weareinterestedinoperatorsexactlyorcloselyrelatedtotheformd2+V(x)+σdW.dx2↑↑↑Discretization:tridiagonaldiagonaldiagonalortridiagonalWhendiscretizedeachtermcanbethoughtofasatridiagonalordiagonalmatrix.ThelastpartrequiresGaussians. Randommatrixtheory27911.1.FromrandommatricestostochasticoperatorsConsidertheβ-Hermiteensemble.Theeigenvaluedistributionofthisen-sembleissharedbyatridiagonalmatrixwithrealelementsthatcouldbeconstructedas√2Gχβ(n−1)√χβ(n−1)2Gχβ(n−2)β√1......Hn=....2√χβ·22Gχβ√χβ2GThismatrixissymmetricwithindependententriesintheuppertriangularpart.GrepresentsanelementtakenfromthestandardGaussiandistri-bution,andχrrepresentsanelementtakenfromtheχ-distributionwithrdegreesoffreedom.Weareinterestedinthedistributionofthelargesteigenvalue,whichisrelatedtothesolutionofthePainlev´eIItranscendent.Considertheβ-Hermiteensemblefromanumericallinearalgebrapointofβview.ThetridiagonalformsuggeststhatHnmaybeafinitedifferenceap-proximationtosomedifferentialoperator.Weproposedthattheβ-HermiteensembleisafinitedifferenceapproximationofthestochasticAiryoperator:d2−x+σdW,(11.1)dx2inwhichdWrepresentsaWienerprocess.RecallthattheAirykernelinTable9.1playsanimportantrole.Hence,therandommatrixmodelitselfhasalargenlimit,andtheeigen-valuesshouldconvergeindistributiontotheeigenvaluesofthestochasticAiryoperatorasn→∞.Whenσ=0,thestochasticAiryoperatorin(11.1)specializestothewell-known,non-noisy,Airyoperatoron[0,∞)withboundaryconditionu(0)=0.IthasaparticularlysimpleeigendecompositionintermsoftheAiryspecialfunction,d2−xu(x)=u(x)−xu(x)=λu(x),dx2iiiiiwhichhassolutions1ui(x)=2Ai(x+λi),Ai(λi)whereλiistheithrootoftheAiryfunction,Ai(x). 280A.EdelmanandN.R.RaoWecandiscretizethenon-noisyAiryoperatorusingfinitedifferences.Takingsomemeshsizeh=h(n)→0anddefiningxi=hi,thematrix−21x11−21x21An=.........−...h21−21xn−11−2xn12=2Dn−hdiag(1,2,...,n)hisanaturalfinitedifferenceapproximationtothenon-noisyAiryoperator,i.e.,thestochasticAiryoperatorin(11.1)withσ=0.Weexpecttheeigenvaluesnearest0andthecorrespondingeigenvectorstoconvergetotheeigenvaluesandeigenfunctionsoftheAiryoperatorasn→∞.βTheβ-HermiteensembleHn,whichisclearly‘noisy’,admitsasimilarrepresentation.Therearesomemanipulationsthatneedtobedonetogettothatform.Thefirststepistoobtaintherightscaling,focusingonthelargesteigen-value.FromTracyandWidom’sresultonthedistributionofthelargesteigenvalue,weknowthatthelargesteigenvalueof√2H˜β=√n1/6(Hβ−2βnI)nmβconvergesindistributionasn→∞forβ=1,2,4.√Usingtheapproximationχ≈r+√1G,validforlarger,andbreakingr2thematrixintoasumofanon-randompartandarandompart,itfollowsthat√−2n2/3n1/6n−1n1/6√n−1−2n2/3n1/6√n−2H˜β≈......n...√√n1/62−2n2/3n1/61√n1/61−2n2/32GGG2GG1+√n1/6..........2βG2GGG2G Randommatrixtheory281√Next,replacingn−iwiththefirst-orderTaylorseriesexpansion√n−1n−1/2i,thefollowingapproximationisobtained:2−212GG1−21G2GG1H˜β≈n2/3......+√n1/6......n......2β1−21G2GG1−2G2G1121−n−1/3..........2n−2n−1n−1Thefirsttermisaseconddifferenceoperator,thesecondterminjectsnoise,andthethirdtermresemblesadiagonalmultiplication.Introducingh=n−1/3andreplacingthesecondandthirdtermswithanalogousdiagonalmatrices,preservingtotalvariance,thefinalapproximationobtainedis:H˜β≈1D2−hdiag(1,2,...,n)+√2√1diag(G,G,...,G)nh2nβh21≈An+√√diag(G,G,...,G),βhh=n−1/3.ThisfinalapproximationappearstobeareasonablediscretizationofthestochasticAiryoperatord22Lβ=−x+√dW,(11.2)dx2βwiththeboundaryconditionsf(0)=f(+∞)=0,inwhichWisGaussianwhitenoise.Therefore,thelargesteigenvaluedistributionofLβshouldfollowtheTracy–Widomdistributioninthecasesβ=1,2,4.Figure11.1plotsthedistributionforβ=1,2,4andcomparesittosimulationresultsforβ=1.Thestochasticoperatorapproachisalsoadvantageouswhendealingwith‘generalβ’.Thetraditionalapproachesarelimitedtothecasesβ=1,2,4.Inthestochasticoperatorapproach,βisrelatedtothevarianceofthenoise;√specifically,σ=2/βinthecaseofthestochasticAiryoperatorasin(11.2).Insteadofworkingwiththreediscretevaluesofβ,thestochasticoperatorsvarycontinuouslywithβ.Numericalsimulations,asinFigure11.1,indicate 282A.EdelmanandN.R.Raoβ=1β=2β=40.6stochasticoperatorβ=10.50.4Probability0.30.20.10−5−4−3−2−101234xFigure11.1.Thelargesteigenvaluedistribution:comparisonofdiscretizedstochasticAiryoperatorwiththeTracy–Widomlaw(β=1).MonteCarlosimulationsinvolved105trialsof500-by-500matrices.somesortofconvection-diffusionprocessthatcanbeexplainedingeneralterms.Thediffusioncomesfromthehighnoiseassociatedwithsmallβ.Increasethevolatility(decreaseβ)andweincreasetherange.Theconvectioncomesfromtherepulsionofeigenvaluesseenbyanyperturbation.Thereadercanplaywithasimpleexperimenttoobservethesamephe-nomenon.Considerthe2×2symmetricrandommatrixxz2G0+√,zyβ0GwheretheGareindependentstandardnormals.Asβ→0thelargesteigenvaluewillhavealargermeanandalargervariancenomatterwhatmatrixyoustartwith,i.e.,foranychoiceofx,y,andz.SimilarstochasticoperatorscorrespondingtothediscretizationofthesineandBesselkernelsinTable9.1canalsobereadilyderived,asdetailedinSutton(2005). Randommatrixtheory28312.FreeprobabilityandinfiniterandommatricesThereisanewmathematicalfieldof‘freeprobability’emergingasacounter-parttoclassicalprobability.SomegoodreferencesareVoiculescu,DykemaandNica(1992),HiaiandPetz(2000)andBiane(2003).Thesereferencesandeventhename‘freeprobability’areworthyofsomeintroduction.TheforthcomingbookbySpeicherandNica(2005)promisestoserveasinvalu-ableresourceformakingthissubjectmoreaccessible.Webeginwithaviewpointonclassicalprobability.Ifwearegivenprob-abilitydensitiesfandgforrandomvariablesXandYrespectively,andifweknowthatXandYareindependent,wecancomputethemomentsofX+Y,andXY,forexample,fromthemomentsofXandY.Ourviewpointonfreeprobabilityissimilar.Giventworandommatrices,AandBwitheigenvaluedensityfandg,wewouldliketocomputetheeigenvaluedensitiesforA+BandABintermsofthemomentsoffandg.Ofcourse,AandBdonotcommutesoweareintherealmofnon-commutativealgebra.SinceallpossibleproductsofAandBareallowed,wehavethe‘free’product,i.e.,allwordsinAandBareallowed.(Werecallthatthisispreciselythedefinitionofthefreeproductinalgebra.)Thetheoryoffreeprobabilityallowsustocomputethemomentsoftheseproductsinthelimitoflargematrices,aslongasatleastoneofAorBhaswhatamountstoeigenvectorsthatareessentiallyuniformlydistributedwithHaarmeasure.Speicher(2003)placesthesemomentcomputationsinanelegantcombinatorialcontext.Weliketothinkofthedifferencebetweenclassicalandfreeprobabilityasbeingillustratedbythefollowingmaxim:sumoftheeigenvaluesofrandommatrices(classicalprobability)versuseigenvaluesofthesumofrandommatrices(freeprobability)Wetakeacloserlookwithanexample.SupposeAiisanm×mmatrixfromtheGaussianorthogonalensemble(GOE).Letλibearandomeigenvaluechosenuniformlyfromthemeigen-valuesofAi.Theclassicalcentrallimittheoremstatesthatifweformλ1+λ2+···+λnλ=√,nnomatterwhatmis,forlargen,weobtainanormaldistribution.Thecentrallimittheoremdoesnotcareatallthattheseλiswereeigenvaluesofrandommatrices. 284A.EdelmanandN.R.RaoHowever,ifratherλisarandomeigenvalueofA1+···+An(eigenvalueofthesum),thenλisnolongernormal.Freeprobabilitytellsusthatasm,n→∞,theλfollowsWigner’ssemi-circulardensity.Thisistheanalogous‘free’centrallimittheoremforasymptoticallylargerandommatrices.Inabroadersense,freeprobabilityisstudiedinthecontextofnon-commutativeoperatoralgebras.Thesynergybetweenrandommatricesandfreeprobabilityarisesbecausematricesareanaturalmodelforanon-commutativealgebra.Thegeneraltheoryoffreeprobabilityis,however,morethanjustinfiniterandommatrixtheory.Inthissense,wefinditremarkablethatfreeprobabilistswereabletoderivemanyofthewell-knownresultsininfiniterandommatrixtheorybyabstractingawaythematrixinquestion.Inspecialcases,techniquesfirstusedbyMarˇcenkoandPastur(1967)andlaterperfectedbySilverstein(1986)andGirko(1998)yieldthesameresultsaswell.MoredetailsonthesetechniquescanbefoundinBai(1999)andthereferencestherein.12.1.FinitefreeprobabilityWeproposethatthereisafinitecounterpart,whichwemightcallfinitefreeprobability.ThisisanareathatisyettobefullyexploredbutsomeoftheformulasforthemomentsofABmaybecomputedusingtheJackpolynomialtheorymentionedinSection7.Therewouldbeabetadepend-encethatisnotnecessarywhenn=1orn=∞,butotherwisethetheoryissensible.InFigure12.1,weillustrate(whatwecall)thefinitefreecentrallimittheoremforacasewhenn=5andβ=2(complexrandommatrices).Theanswerisneitherasemi-circleasinstandardfreeprobabilityoranormaldistributionasinclassicalprobability.Herewetook5×5complexWishart0.350.30.250.2Probability0.150.10.050−4−3−2−101234xFigure12.1.Finitefreeprobability:theleveldensityoftheβ=2,n=5Hermiteensembleobtainedbysummingalargenumberofindependentrealizationsoftheβ=2,n=5Laguerreensemble. Randommatrixtheory285matrices,subtractedthemeanandaddedthem.Thereisasensiblenotionoffinitefreeprobability,thoughitisnotcleariffinitefreecumulantscanordoexist.Thedetailshaveyettobeworkedout,thougheffortsbymanyauthorsondifferentfrontsareunderway.Weinvitereaderstoworkinthisarea.13.ArandommatrixcalculatorInprinciple,theformulasfromfreeprobabilityallowustocombineverygeneralcombinationsofrandommatricesandstillcomputetheeigenvaluedensities.Inpractice,however,researchershavebeenconstrainedfromdoingsobecausetherelevanttheoremsareexpressedexplicitlyintermsoftransformsthataredifficulttocomputebeyondsomesimple‘toyexamples’.Itturnsoutthatthesetheoremscanbedescribedimplicitlyaswell.Thekeyobjectisnotthetransformitselfbutthealgebraicequationthatthetransformsatisfies.Thepracticalimplicationofthisisthatwecanactuallycomputethelimitingleveldensityandmomentsforaninfinitelylargeclassofrandommatrices.Welabelsuchrandommatricesas‘characterizable’.Figure13.1usesacalculatoranalogytodescribehowonecharacterizablematrixcanbeconstructedfromanother.
A
BlevelleveldensitydensitydeterministicpA+qIA+αIα×AA−1rA+sIstochastic(A1/2+G)A+W(c)W(c)×AW−1(c)×A×(A1/2+G)Figure13.1.Arandommatrixcalculatorwhereasequenceofdeterministicandstochasticoperationsperformedona‘characterizable’matrixAproducesa‘characterizable’matrixB.Theleveldensityandmomentsofa‘characterizable’matrixcanbecomputedanalytically. 286A.EdelmanandN.R.RaoThe‘buttons’inthetoprowofFigure13.1representdeterministicoper-ationsthatcanbeperformedonit(α,p,q,r,sarescalars).The‘buttons’inthebottomrowarestochasticoperationswhereadditionalrandomnessisinjected.TheGmatrixisanm×nmatrixwithindependent,identicallydistributed(i.i.d.)zeromeanelementswithavarianceof1/nandboundedhigher-ordermoments.WecouldgenerateGofthisforminmatlabasG=randn(m,n)/sqrt(n);orG=sign(randn(m,n))/sqrt(n);asexamples.TheW(c)matrixisaWishart-likematrixconstructedasW(c)=GGwherem/n→c>0asm,n→∞.TheideabehindthecalculatoristhatifwestartoffwithacharacterizablematrixAandifweweretogeneratethematrixBbypressinganyofthebuttonsofthecalculatorwegenerateanothercharacterizablematrixB.Wecanrepeatthisprocessforever,andbyvirtueofitbeingcharacterizablewecancomputethelimitingleveldensityandlimitingmoments,ofteninclosedform.Wecanextendthisideaevenfurtherbyusingthetheoremsoffreeprobab-ility.Ifwearegiventwocharacterizablerandommatrices,A1andA2,thenwecanmakethem‘free’relativetoeachotherbylettingA2=QA2Q,whereQisanindependentHaarorthogonal/unitarymatrix.ThenthematricesA1+A2,andA1A2arecharacterizableaswell.Othertransformationssuchasi(A1A2−A2A1)(thematrixcommutatorinLiealgebra)arepossibleaswell.Themathematicalprinciplesbehindthismethodandthecomputa-tionalrealizationthatmakesallofthispossiblemaybefoundinRaoandEdelman(2005)andRao(2005).Weillustratethiswithanexample.SupposewestartoffwithA1=I.Inmatlabweperformasequenceofsimpletransformationscorrespondingtobuttonsonourcalculator:%Pickn,N1,N2c1=n/N1;c2=n/N2;A1=eye(n,n);Then,wegenerateA2=W1(c1)×A1:G1=randn(n,N1)/sqrt(N1);W1=G1*G1’;A2=A1*W1;LetA=A−1andA=W(c)×A:324223A3=inv(A2);G2=randn(n,N2)/sqrt(N2);W2=G2*G2’;A4=A3*W2 Randommatrixtheory287(a)A=W(c)(b)A−12113=A21.5110.50.5ProbabilityProbability000.511.520123xx(c)A4=A3×W2(c2)(d)A5=A4+I110.50.5ProbabilityProbability00−202460246xx−1(f)A=A+QAQ(e)A6=A57662110.5ProbabilityProbability0000.5100.511.52xxFigure13.2.Comparisonofthetheoreticallimitingleveldensity(solidline)withtheexperimentalleveldensityfor1000randommatrixensemblerealizationswithc1=0.1,c2=0.625,withn=100,N1=n/c1=1000andN2=n/c2=160.Now,A=A+IandA=A−1:5465A5=A4+eye(n,n);A6=inv(A5);GenerateaHaarunitarymatrixandletA7=A6+QA6Q:[Q,R]=qr(randn(n)+i*randn(n));Q=Q*diag(exp(2*pi*i*rand(n,1)));A7=A6+Q*A6*Q’;%Collecteigenvalues%Repeatoverseveraltrials%HistogrameigenvaluesSinceweconstructedthematricesA2toA7usingthe‘buttons’oftherandommatrixcalculator,theyturnouttobecharacterizable.Figure13.2showsthelimitingleveldensityofthesematrixensemblescomparedwiththeexperimentalversion.Itisclearthatalthoughthepredictionswereasymptoticinnature(withrespecttolargen,N1,N2)theagreementwith 288A.EdelmanandN.R.Raoexperimentaldataisexcellent.Empiricalevidencesuggeststhata10×10matrixisoften‘goodenough’tocorroboratethelimitingpredictionsoffreeprobability.14.Non-HermitianandstructuredrandommatricesOurunderstandingofnon-Hermitianandstructuredrandommatricesisverylimitedatpresent.Relativelyrecentresultsonnon-HermitianrandommatricesincludetheworksbyGoldsheidandKhoruzhenko(2000),Fyo-dorov,KhoruzhenkoandSommers(1997),andFeinbergandZee(1997).Themostcelebratedtheorem,Girko’scircularlaw(Girko1994)statesthatunderreasonableconditions,theeigenvaluesofann×nmatrixwithindependententriesofmean0andvariance1/nfalluniformlyonacirculardiskofradius1asn→∞.Figure14.1illustratesthisnumerically.Thetheoremiscorrectwhetherthematrixisrealorcomplex.Whenthematrixisrealthereisalargerattractionofeigenvaluesontherealaxisandasmallrepulsionjustofftheaxis.Thisdisappearsasn→∞.MehligandChalker(2000)studytheeigenvectorsofsuchnon-Hermitianrandommatrices.Generalquestionsregardingeigenvectorsorspacingsremainopenatthistime,asdostudiesoftheβ-arbitrarygeneralization.1.510.50−0.5−1−1.5−1.5−1−0.500.511.5Figure14.1.Theeigenvaluesofa500×500Gaussianrandommatrix(randn(500)/sqrt(500)inmatlab)inthecomplexplane. Randommatrixtheory289Thetheoryofpseudospectraisarichareathatallowsforthestudyofnon-Hermitianmatrices,specificallythosethatarehighlynon-normal.Manytoolsfordrawingpseudospectraareavailable,suchasEigToolbyWright(2000).Figure14.2showsthepseudospectraforthesamerandommatrixwhoseeigenvalueswereplottedinFigure14.1.ThePseudospectraGatewaycompiledbyEmbreeandTrefethen(2000)andtheirwell-researchedbook,TrefethenandEmbree(2005),containdiscussionsofnonsymmetricrandommatrices.Randommatrixtheoryisrelevantintwodistinctways.Aninstanceofarandommatrixitselfbecomesavaluableobjecttostudy,asinGirko’scircularlaworintheHatanoandNelson’snon-HermitianAndersonmodelasdescribedbyTrefethen,ContediniandEmbree(2001).Also,perturbingamatrixrandomlyallowsforinsightsintothepseudospectraandhasbeenelevatedtothelevelofatool,asinthebookbyChaitin-ChatelinandFrayss´e(1996),where,forexample,theJordanstructureisstudied.Anotherinterestingresultconcernstheprobabilitypn,kthatG1(n,n)haskrealeigenvalues.AformulaforthismaybefoundinEdelman(1997).NumericalanalystsmightbeinterestedintheuseoftherealSchurdecom-positioninthecomputationpn,k.Thisisthedecompositionusedinstandard1.5−110.50−2−0.5−1−1.5−3−1.5−1−0.500.511.5Figure14.2.Thepseudospectraofa500×500Gaussianrandommatrix(randn(500)/sqrt(500)inmatlab).TheillustrationwasproducedwiththeeigtoolpseudospectraplotterfromOxfordUniversity.Thevaluesonthecolourbarshow10log10. 290A.EdelmanandN.R.Raoeigenvaluecomputations.Forexample,tocomputetheprobabilitythatamatrixhasallrealeigenvalues,oneintegratesthemeasureonG1(n,n)overmatricesoftheformA=QRQT,whereQisorthogonalandRisuppertriangularwithordereddiagonalelements.ThisistheSchurformforrealmatriceswithallrealeigenvalues.ForrandomsparsematriceswereferthereadertoRodgersandBray(1988)andSemerjianandCugliandolo(2002),andthegeneraltheoryofrandomgraphs(Bollob´as1985).InSpiridonov(2005)onefindsaninterest-ingfractalpatterninthehistogramoftheeigenvaluesofasparserandommatrixdependingonthedegreeofsparsity.TheclassicalreferenceondeterministicToeplitzmatricesisGrenanderandSzeg˝o(1958).RecentworkbyByrc,DemboandJiang(2005)providesafreeprobability-likecharacterizationofthelimitingspectralmeasureofToeplitz,HankelandMarkovrandommatrices.AndersonandZeitouni(2005)discusscentrallimittheoremsrelatedtogeneralized‘banded’randommatrixmodels.15.AsegueWemakesomefinalpredictionsabouttheapplicationofrandommatrixtheory:thepatternwillfollowthatofnumericalanalysisingeneral.Mostdisciplinesofscienceandengineeringwillfindrandommatrixtheoryavalu-abletool.Randommatrixhistorystartedinthephysicsofheavyatomsandmultivariatestatistics.Ithasfounditswayintowirelesscommunicationsandcombinatorialmathematics.Thelatestfieldisfinancialanalysis.Morewillfollow;thewordhastospread.Hopefully,thisisastart.AcknowledgementsWewouldliketoacknowledgethecontributionsofIoanaDumitriu,BrianSutton,Per-OlofPerssonandPlamenKoev.Wefeelprivilegedtohavethemascolleaguesandhaveoftenbeeninspiredbyinteractingwiththem,includ-ingwhilewritingthisarticle.Therehavebeenmanyinstanceswhen,inthemidstofourdiscussion,werealizedthattheyhadsaidsomethingbetterthanwecouldeverhave;thisarticlethusreflectstheirwordsandthoughtsonthisfascinatingsubjectalongwithourown.Inparticular,portionsofIoana’s(Dumitriu2003)andBrian’s(Sutton2005)dissertationworkformedthebasisforSection4andSection11respectively.WeborrowedthematlabcodeinSection9fromPersson’sbeautifullywrittendocumentationofthesameinEdelmanandPersson(2002).WethankPierre-AntoineAbsil,PeterForrester,MatthewHarding,NickHigham,EricKostlan,JuliusKusuma,GilStrang,CraigTracy,andNickTrefethenfortheirvaluablefeedback.Especially,wethankAriehIserlesandBradBaxterfortheircommentsand Randommatrixtheory291encouragement,GlennisStarlingforbeingincrediblypatientwithusinthefaceofseveretimeconstraints,andBrettCoonleyforhistypesettingwiz-ardry.WethanktheNationalScienceFoundation(DMS-0411962)andtheSingapore-MITAllianceforsupportingourwork.REFERENCESM.AbramowitzandI.Stegun,eds(1970),HandbookofMathematicalFunctions,DoverPublications,NewYork.P.-A.Absil,A.EdelmanandP.Koev(2004),‘Onthelargestprincipalanglebetweenrandomsubspaces’.Submitted.D.AldousandP.Diaconis(1999),‘Longestincreasingsubsequences:frompa-tiencesortingtotheBaik–Deift–Johanssontheorem’,Bull.Amer.Math.Soc.36,413–432.G.W.AndersonandO.Zeitouni(2005),ACLTforabandmatrixmodel:arXiV.org/math.PR/0412040.C.Andr´eief(1883),‘Notesurunerelationlesint´egralesd´efiniesdesproduitsdesfonctions’,M´em.delaSoc.Sci.Bordeaux2,1–14.J.-M.Aza¨ısandM.Wschebor(2004),UpperandlowerboundsforthetailsofthedistributionoftheconditionnumberofaGaussianmatrix:www.lsp.ups-tlse.fr/Azais/publi/upper.ps.Z.D.Bai(1999),‘Methodologiesinspectralanalysisoflarge-dimensionalran-dommatrices:areview’,Statist.Sinica9(3),611–677.WithcommentsbyG.J.RodgersandJ.W.Silverstein,andarejoinderbytheauthor.B.J.C.BaxterandA.Iserles(2003),Onthefoundationsofcomputationalmath-ematics,inHandbookofNumericalAnalysis,Vol.XI,North-Holland,Ams-terdam,pp.3–34.P.Biane(2003),Freeprobabilityforprobabilists,inQuantumprobabilitycommu-nications,Vol.XI:Grenoble,1998,WorldScientific,RiverEdge,NJ,pp.55–71.P.BleherandA.Its(1999),‘Semiclassicalasymptoticsoforthogonalpolynomials,Riemann–Hilbertproblem,andtheuniversalityinthematrixmodel’,Ann.Math.150,185–266.B.Bollob´as(1985),RandomGraphs,AcademicPress,London.A.Borodin(1999),‘Longestincreasingsubsequencesofrandomcoloredpermuta-tions’,Electron.J.Combin.6,#13(electronic).A.BorodinandP.J.Forrester(2003),‘Increasingsubsequencesandthehard-to-softedgetransitioninmatrixensembles’,J.Phys.A36(12),2963–2981.W.Byrc,A.DemboandT.Jiang(2005),SpectralmeasureoflargerandomHankel,Markov,andToeplitzmatrices:arXiV.org/abs/math.PR/0307330.M.CaselleandU.Magnea(2004),‘Randommatrixtheoryandsymmetricspaces’,Phys.Rep.394(2–3),41–156.F.Chaitin-ChatelinandV.Frayss´e(1996),LecturesonFinitePrecisionComputa-tions:Software,Environments,andTools,SIAM,Philadelphia,PA.A.Constantine(1963),‘Somenoncentraldistributionproblemsinmultivariateana-lysis’,Ann.Math.Statist.34,1270–1285. 292A.EdelmanandN.R.RaoP.A.Deift(1999),OrthogonalPolynomialsandRandomMatrices:ARiemann–HilbertApproach,Vol.3ofCourantLectureNotesinMathematics,NewYorkUniversityCourantInstituteofMathematicalSciences,NewYork.P.Deift(2000),‘Integrablesystemsandcombinatorialtheory’,NoticesAmer.Math.Soc.47(6),631–640.P.Deift,A.ItsandX.Zhou(1997),‘ARiemann–Hilbertproblemapproachtoasymptoticproblemsarisinginthetheoryofrandommatrixmodels,andalsointhetheoryofintegrablestatisticalmechanics’,Ann.Math.146(1),149–235.M.Dieng(2004),‘Distributionfunctionsforedgeeigenvaluesinorthogonalandsymplecticensembles:Painlev´erepresentations’:arXiV.org/math.PR/0411421.I.Dumitriu(2003),Eigenvaluestatisticsforbeta-ensembles,PhDthesis,Depart-mentofMathematics,MassachusettsInstituteofTechnology,Cambridge,MA.I.DumitriuandA.Edelman(2004),MOPS:MultivariateOrthogonalPolynomials(symbolically):arXiV.org/abs/math-ph/0409066.F.J.Dyson(1963),‘Thethreefoldway:algebraicstructuresofsymmetrygroupsandensemblesinquantummechanics’,J.Math.Phys.3,1199–1215.A.Edelman(1989),Eigenvaluesandconditionnumbersofrandommatrices,PhDthesis,DepartmentofMathematics,MassachusettsInstituteofTechnology,Cambridge,MA.A.Edelman(1997),‘TheprobabilitythatarandomrealGaussianmatrixhaskrealeigenvalues,relateddistributions,andthecircularlaw’,J.Multivar.Anal.60,203–232.A.EdelmanandP.-O.Persson(2002),Numericalmethodsforrandommatrices.Technicalreport,MassachusettsInstituteofTechnology:arXiV.org/abs/math-ph/0501068.A.EdelmanandB.Sutton(2004),‘Tailsofconditionnumberdistributions’.Sub-mitted.M.EmbreeandL.N.Trefethen(2000),‘Pseudospectragateway’:www.comlab.ox.ac.uk/pseudospectra.A.Erd´elyi,W.Magnus,F.OberhettingerandF.G.Tricomi(1955),HigherTran-scendentalFunctions,Vol.III,McGraw-Hill,NewYork/Toronto/London.A.Erd´elyi,W.Magnus,F.OberhettingerandF.G.Tricomi(1981a),HigherTran-scendentalFunctions,Vol.I,RobertE.Krieger,Melbourne,FL.Reprintofthe1953original.A.Erd´elyi,W.Magnus,F.OberhettingerandF.G.Tricomi(1981b),HigherTran-scendentalFunctions,Vol.II,RobertE.Krieger,Melbourne,FL.Reprintofthe1953original.J.FeinbergandA.Zee(1997),‘Non-Hermitianrandommatrixtheory:methodofHermitianreduction’,NuclearPhys.B504(3),579–608.P.J.Forrester(2000),Painlev´etranscendentevaluationofthescaleddistributionofthesmallesteigenvalueintheLaguerreorthogonalandsymplecticensembles.Technicalreport:www.lanl.gov,arXiV.org/nlin.SI/0005064.P.J.Forrester(2005),Log-GasesandRandomMatrices,bookinprogress. Randommatrixtheory293P.J.ForresterandN.S.Witte(2004),‘Applicationoftheτ-functiontheoryofPainlev´eequationstorandommatrices:PVI,theJUE,CyUE,cJUEandscaledlimits’,NagoyaMath.J.174,29–114.Y.Fyodorov,B.A.KhoruzhenkoandH.-J.Sommers(1997),‘Almost-Hermitianrandommatrices:CrossoverfromWigner–DysontoGinibreeigenvaluestat-istics’,Phys.Rev.Lett.79,557–560.F.P.GantmacherandM.G.Krein(2002),OscillationMatricesandKernelsandSmallVibrationsofMechanicalSystems,revisededn,AMSChelseaPublish-ing,Providence,RI.Translationbasedonthe1941Russianoriginal.W.Gautschi(1996),Orthogonalpolynomials:Applicationsandcomputation,inActaNumerica,Vol.5,CambridgeUniversityPress,pp.45–119.V.L.Girko(1994),‘Thecircularlaw:tenyearslater’,RandomOper.Stoch.Equa-tions2,235–276,377–398.V.L.Girko(1998),AnIntroductiontoStatisticalAnalysisofRandomArrays,VSP,Utrecht.TranslatedfromtheRussian.I.Y.GoldsheidandB.A.Khoruzhenko(2000),‘Eigenvaluecurvesofasymmetrictridiagonalrandommatrices’,Electron.J.Probab.5,#16(electronic).G.GolubandW.Kahan(1965),‘Calculatingthesingularvaluesandpseudo-inverseofamatrix’,SIAMJ.Numer.Anal.2,205–224.U.GrenanderandG.Szeg˝o(1958),ToeplitzFormsandtheirApplications,Cali-forniaMonographsinMathematicalSciences,UniversityofCaliforniaPress,Berkeley.P.J.Hanlon,R.P.StanleyandJ.R.Stembridge(1992),Somecombinatorialaspectsofthespectraofnormallydistributedrandommatrices,inHypergeo-metricFunctionsonDomainsofPositivity,JackPolynomials,andApplica-tions:Tampa,FL,1991,Vol.138ofContemp.Math.,AMS,Providence,RI,pp.151–174.F.HiaiandD.Petz(2000),TheSemicircleLaw,FreeRandomVariablesandEn-tropy,MathematicalSurveysandMonographs,AMS.A.S.Householder(1958),‘Unitarytriangularizationofanonsymmetricmatrix’,J.Assoc.Comput.Mach.5,339–342.A.Its,C.A.TracyandH.Widom(2001),‘Randomwords,ToeplitzdeterminantsandintegrablesystemsII’,Physica152–153D,199–224.D.A.Ivanov(2002),Random-matrixensemblesinp-wavevortices,inProc.DresdenWorkshop‘VorticesinUnconventionalSuperconductorsandSuper-fluids’,Springer,Heidelberg:arXiV.org/abs/cond-mat/0103089.H.Jack(1970),‘Aclassofsymmetricpolynomialswithaparameter’,Proc.R.Soc.Edinburgh69,1–18.A.T.James(1964),‘Distributionsofmatrixvariatesandlatentrootsderivedfromnormalsamples’,Ann.Math.Stat.35,475–501.K.Johansson(2000a),‘Randomgrowthandrandommatrices’,EuropeanCongressofMathematicsI,445–456.K.Johansson(2000b),‘Shapefluctuationsandrandommatrices’,Comm.Math.Phys.209,437–476.I.M.Johnstone(2001),‘Onthedistributionofthelargesteigenvalueinprincipalcomponentsanalysis’,Ann.Statist.29(2),295–327. 294A.EdelmanandN.R.RaoD.Jonsson(1982),‘Somelimittheoremsfortheeigenvaluesofasamplecovariancematrix’,J.Multivar.Anal.12,1–38.I.KaratzasandS.E.Shreve(1991),BrownianMotionandStochasticCalculus,Vol.113ofGraduateTextsinMathematics,secondedn,Springer,NewYork.R.KillipandI.Nenciu(2004),‘Matrixmodelsforcircularensembles’,Int.Math.ResearchNotices50,2665–2701.F.KnopandS.Sahi(1997),‘ArecursionandacombinatorialformulaforJackpolynomials’,Invent.Math.128(1),9–22.P.Koev(2002),Accurateandefficientmatrixcomputationwithstructuredmatrices,PhDthesis,UniversityofCalifornia,Berkeley.P.KoevandA.Edelman(2004),Theefficientevaluationofthehypergeometricfunctionofamatrixargument.Preprint.A.B.J.Kuijlaars(2000),‘WhicheigenvaluesarefoundbytheLanczosmethod?’,SIAMJ.MatrixAnal.Appl.22(1),306–321(electronic).A.B.J.Kuijlaars(2003),Riemann–Hilbertanalysisfororthogonalpolynomials,inOrthogonalPolynomialsandSpecialFunctions:Leuven,2002,Vol.1817ofLectureNotesinMathematics,Springer,Berlin,pp.167–210.A.KuijlaarsandK.T.-R.McLaughlin(2000),‘Genericbehaviorofthedensityofstatesinrandommatrixtheoryandequilibriumproblemsinthepresenceofrealanalyticexternalfields’,Comm.PureAppl.Math.53,736–785.R.A.Lippert(2003),‘Amatrixmodelfortheβ-Jacobiensemble’,J.Math.Phys.44(10),4807–4816.I.Macdonald(1982),‘Someconjecturesforrootsystems’,SIAMJ.Math.Anal.13,998–1004.I.Macdonald(1998),SymmetricFunctionsandHallPolynomials,OxfordMath-ematicalMonographs,2ndedn,OxfordUniversityPress.B.D.McKay(1981),‘Theexpectedeigenvaluedistributionofalargeregulargraph’,LinearAlgebraAppl.40,203–216.V.MarˇcenkoandL.Pastur(1967),‘Distributionofeigenvaluesforsomesetsofrandommatrices’,MathUSSRSbornik1,457–483.A.Mathai(1997),JacobiansofMatrixTransformationsandFunctionsofMatrixArguments,WorldScientific,Singapore.B.MehligandJ.T.Chalker(2000),‘Statisticalpropertiesofeigenvectorsinnon-HermitianGaussianrandommatrixensembles’,J.Math.Phys.41(5),3233–3256.M.L.Mehta(1991),RandomMatrices,secondedn,AcademicPress,Boston.V.D.MilmanandG.Schechtman(1986),AsymptoticTheoryofFiniteDimen-sionalNormedSpaces,Vol.1200ofLectureNotesinMathematics,Springer.R.J.Muirhead(1982),AspectsofMultivariateStatisticalTheory,Wiley,NewYork.A.M.Odlyzko(2001),‘TablesofzerosoftheRiemannzetafunction’:www.dtc.umn.edu/~odlyzko/zetatables/index.html.A.OdlyzkoandE.Rains(1998),Onlongestincreasingsubsequencesinrandompermutations.Technicalreport,AT&TLaboratories.I.Olkin(1953),‘Noteon“TheJacobiansofcertainmatrixtransformationsusefulinmultivariateanalysis”’,Biometrika40,43–46.I.Olkin(2002),‘The70thanniversaryofthedistributionofrandommatrices:asurvey’,LinearAlgebraAppl.354,231–243. Randommatrixtheory295E.M.Rains(1998),‘Increasingsubsequencesandtheclassicalgroups’,Electron.J.Combin.5,#12(electronic).N.R.Rao(2005),Infiniterandommatrixtheoryformulti-channelsignalpro-cessing,PhDthesis,MassachusettsInstituteofTechnology.N.R.RaoandA.Edelman(2005),Thepolynomialmethodforrandommatrices.Preprint.G.J.RodgersandA.J.Bray(1988),‘Densityofstatesofasparserandommatrix’,Phys.Rev.B(3)37(7),3557–3562.A.Sankar(2003),SmoothedanalysisofGaussianelimination,PhDthesis,Mas-sachusettsInstituteofTechnology.A.Sankar,D.A.SpielmanandS.-H.Teng(2004),Smoothedanalysisofthecon-ditionnumbersandgrowthfactorsofmatrices:arXiV.org/abs/cs.NA/0310022.G.SemerjianandL.F.Cugliandolo(2002),‘Sparserandommatrices:theeigen-valuespectrumrevisited’,J.Phys.A35(23),4837–4851.J.Shen(2001),‘OnthesingularvaluesofGaussianrandommatrices’,LinearAlgebraAppl.326(1–3),1–14.J.W.Silverstein(1985),‘Thesmallesteigenvalueofalarge-dimensionalWishartmatrix’,Ann.Probab.13(4),1364–1368.J.W.Silverstein(1986),Eigenvaluesandeigenvectorsoflargedimensionalsamplecovariancematrices,chapterinRandomMatricesandtheirApplications,AMS,Providence,RI,pp.153–159.A.Soshnikov(1999),‘UniversalityattheedgeofthespectruminWignerrandommatrices’,Comm.Math.Phys.207,697–733.J.SpanierandK.B.Oldham(1987),AnAtlasofFunctions,Taylor&Francis/Hemisphere.R.Speicher(2003),Freeprobabilitytheoryandrandommatrices,inAsymptoticCombinatoricswithApplicationstoMathematicalPhysics:St.Petersburg,2001,Vol.1815ofLectureNotesinMathematics,Springer,Berlin,pp.53–73.R.SpeicherandA.Nica(2005),Combinatoricsoffreeprobability.Inpreparation.A.N.Spiridonov(2005),Spectraofsparsegraphsandmatrices.Preprint.R.P.Stanley(1989),‘SomecombinatorialpropertiesofJacksymmetricfunctions’,Adv.Math.77,76–115.G.W.Stewart(1980),‘Theefficientgenerationofrandomorthogonalmatriceswithanapplicationtoconditionestimators’,SIAMJ.Numer.Anal.17(3),403–409(loosemicrofichesuppl).B.D.Sutton(2005),Thestochasticoperatorapproachtorandommatrixtheory,PhDthesis,MassachusettsInstituteofTechnology,DepartmentofMathem-atics.K.Takasaki(2000),‘Painlev´eequations’,SolitonLaboratory,ChronologyofMath-ematics:www.math.h.kyoto-u.ac.jp/~takasaki/soliton-lab/chron/painleve.html.C.A.TracyandH.Widom(1993),Introductiontorandommatrices,inGeometricandQuantumAspectsofIntegrableSystems(G.Helminck,ed.),Vol.424ofLectureNotesinPhysics,Springer,Berlin,pp.103–130.C.A.TracyandH.Widom(1994a),‘Fredholmdeterminants,differentialequationsandmatrixmodels’,Comm.Math.Phys.163,33–72. 296A.EdelmanandN.R.RaoC.A.TracyandH.Widom(1994b),‘Level-spacingdistributionsandtheBesselkernel’,Comm.Math.Phys.161,289–310.C.A.TracyandH.Widom(1998),‘Correlationfunctions,clusterfunctionsandspacingdistributionsforrandommatrices’,J.Statist.Phys.92,809–835.C.A.TracyandH.Widom(2000a),ThedistributionofthelargesteigenvalueintheGaussianensembles,inCalogero–Moser–SutherlandModels,Vol.4ofCRMSeriesinMathematicalPhysics(J.vanDiejenandL.Vinet,eds),Springer,Berlin,pp.461–472.C.A.TracyandH.Widom(2000b),UniversalityofthedistributionfunctionsofrandommatrixtheoryII,inIntegrableSystems:FromClassicaltoQuantum(J.Harnad,G.SabidussiandP.Winternitz,eds),Vol.26ofCRMProceedings&LectureNotes,AMS,Providence,pp.251–264.C.A.TracyandH.Widom(2001),‘Onthedistributionsofthelengthsofthelongestmonotonesubsequencesinrandomwords’,Probab.TheoryRel.Fields119,350–380.L.N.TrefethenandD.Bau,III(1997),NumericalLinearAlgebra,SIAM,Phil-adelphia,PA.L.N.TrefethenandA.Embree(2005),SpectraandPseudospectra:TheBehaviorofNonnormalMatricesandOperators,Princeton.L.N.TrefethenandR.S.Schreiber(1990),‘Average-casestabilityofGaussianelimination’,SIAMJ.MatrixAnal.Appl.11(3),335–360.L.N.Trefethen,M.ContediniandM.Embree(2001),‘Spectra,pseudospectra,andlocalizationforrandombidiagonalmatrices’,Comm.PureAppl.Math.54(5),595–623.H.F.Trotter(1984),‘EigenvaluedistributionsoflargeHermitianmatrices;Wigner’ssemi-circlelawandatheoremofKac,Murdock,andSzeg˝o’,Adv.Math.54,67–82.C.F.VanLoan(2000),‘TheubiquitousKroneckerproduct’,J.Comput.Appl.Math.123(1–2),85–100.P.vanMoerbeke(2001),Integrablelattices:randommatricesandrandomper-mutations,inRandomMatricesandtheirApplications,MSRIPublications,CambridgeUniversityPress,Cambridge.J.M.Varah(1993),‘Theprolatematrix’,LinearAlgebraAppl.187,269–278.D.ViswanathandL.N.Trefethen(1998),‘Conditionnumbersofrandomtriangularmatrices’,SIAMJ.MatrixAnal.Appl.19(2),564–581(electronic).D.V.Voiculescu,K.J.DykemaandA.Nica(1992),FreeRandomVariables,AMS,Providence,RI.J.vonNeumann(1963),CollectedWorks,Vol.V:DesignofComputers,TheoryofAutomataandNumericalAnalysis(A.H.Taub,ed.),PergamonPress,Macmillan,NewYork.J.vonNeumannandH.H.Goldstine(1947),‘Numericalinvertingofmatricesofhighorder’,Bull.Amer.Math.Soc.53,1021–1099.E.W.Weisstein(2005),‘Specialfunction’,FromMathWorld,AWolframWebResource:http://mathworld.wolfram.com/SpecialFunction.htmlE.P.Wigner(1955),‘Characteristicvectorsofborderedmatriceswithinfinitedimensions’,Ann.Math.62,548–564. Randommatrixtheory297E.P.Wigner(1958),‘Onthedistributionoftherootsofcertainsymmetricmatrices’,Ann.Math.67,325–327.J.Wishart(1928),‘Thegeneralizedproductmomentdistributioninsamplesfromanormalmultivariatepopulation’,Biometrika20A,32–52.T.G.Wright(2000),‘EigTool’:www.comlab.ox.ac.uk/projects/pseudospectra/eigtool.M.-C.YeungandT.F.Chan(1997),‘ProbabilisticanalysisofGaussianeliminationwithoutpivoting’,SIAMJ.MatrixAnal.Appl.18(2),499–517.M.R.Zirnbauer(1996),‘Riemanniansymmetricsuperspacesandtheirorigininrandom-matrixtheory’,J.Math.Phys.37(10),4986–5018.