MIT18_06SCF11_Ses1.12Matrix Spaces; Rank 1; Small World Graphs

《MIT18_06SCF11_Ses1.12Matrix Spaces; Rank 1; Small World Graphs》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Graphs,networks,incidencematricesWhenweuselinearalgebratounderstandphysicalsystems,weoftenfindmorestructureinthematricesandvectorsthanappearsintheexampleswemakeupinclass.Therearemanyapplicationsoflinearalgebra;forexample,chemistsmightuserowreductiontogetaclearerpictureofwhatelements

2、gointoacomplicatedreaction.Inthislectureweexplorethelinearalgebraassociatedwithelectricalnetworks.GraphsandnetworksAgraphisacollectionofnodesjoinedbyedges;Figure1showsonesmallgraph.1423Figure1:Agraphwithn=4nodesandm=5edges.Weputanarrowoneachedgetoindicatethepositivedirectionforcurr

3、entsrunningthroughthegraph.1423Figure2:ThegraphofFigure1withadirectiononeachedge.IncidencematricesTheincidencematrixofthisdirectedgraphhasonecolumnforeachnodeofthegraphandonerowforeachedgeofthegraph:⎡⎤−1100⎢⎢0−110⎥⎥A=⎢⎢−1010⎥⎥.⎣−1001⎦00−11Ifanedgerunsfromnodeatonodeb,therowcor

4、respondingtothatedgehas−1incolumnaand1incolumnb;allotherentriesinthatroware0.Ifwewere1studyingalargergraphwewouldgetalargermatrixbutitwouldbesparse;mostoftheentriesinthatmatrixwouldbe0.Thisisoneofthewaysmatricesarisingfromapplicationsmighthaveextrastructure.Notethatnodes1,2and3ande

5、dges�,�and�formaloop.Thematrixdescribingjustthosenodesandedgeslookslike:⎡⎤−1100⎣0−110⎦.−1010Notethatthethirdrowisthesumofthefirsttworows;loopsinthegraphcorrespondtolinearlydependentrowsofthematrix.TofindthenullspaceofA,wesolveAx=0:⎡⎤⎡⎤x2−x10⎢⎢x3−x2⎥⎥⎢⎢0⎥⎥Ax=⎢⎢x3−x1⎥⎥=⎢⎢0⎥⎥.⎣x4−x1⎦⎣0⎦

6、x4−x30Ifthecomponentsxiofthevectorxdescribetheelectricalpotentialatthenodesiofthegraph,thenAxisavectordescribingthedifferenceinpotentialacrosseachedgeofthegraph.WeseeAx=0whenx1=x2=x3=x4,sothenullspacehasdimension1.Intermsofanelectricalnetwork,thepotentialdifferenceiszerooneachedgei

7、feachnodehasthesamepotential.Wecan’ttellwhatthatpotentialisbyobservingtheflowofelectricitythroughthenetwork,butifonenodeofthenetworkisgroundedthenitspotentialiszero.Fromthatwecandeterminethepotentialofallothernodesofthegraph.Thematrixhas4columnsanda1dimensionalnullspace,soitsrankis3

8、.Thefirst,secondandfourthco