The Laplacian - Yale University

1 spectral Graph TheoryLecture 2 The LaplacianDaniel A. SpielmanSeptember 4, Eigenvectors and EigenvectorsI ll begin this lecture by recalling some definitions of eigenvectors and eigenvalues, and some oftheir basic properties. First, recall that a vectorvis an eigenvector of a matrixMof eigenvalue ifMv= almost all the matrices we encounter in this class will be symmetric (or morally symmetric), I llremind you of the special properties of the spectra of symmetric matrices. Ifv1is an eigenvectorofMof eigenvalue 1,v2is an eigenvector ofMof eigenvalue 26= 1, andMsymmetric, thenv1is orthogonal tov2. To see this, note that 1vT1v2=vT1Mv2=vT1 2v2= 2vT1v2impliesvT1v2= 0, assuming 16= 2. On the other hand, ifv1andv2are both eigenvectors ofeigenvalue , thenv1+v2is as a symmetric matrixM, themultiplicityof an eigenvalue is the dimension of the space ofeigenvectors of eigenvalue.

2 Also recall that everyn-by-nsymmetric matrix hasneigenvalues,counted with multiplicity. Thus, it has an orthonormal basis of eigenvectors,{v1,..,vn}witheigenvalues 1 2 nso thatMvi= ivi,for we letVbe the matrix whoseith column isviand be the diagonal matrix whoseith diagonalis i, we can write this more compactly asMV=V .Multiplying byVTon the right, we obtain the eigen-decompisition ofM:M=MV VT=V VT= i The Laplacian MatrixWe will now recall the definition of the Laplacian matrix of a weighted graph, and present it ina more useful form. Recall that a weighted undirected graphG= (V,E,w) is just an undirected2-1 Lecture 2: September 4, 20092-2graphG= (V,E) along with a functionw:E IR+, where IR+denotes the set of positive Realnumbers. The adjacency matrix of a weighted graphGwill be denotedAG, and is given byAG(i,j) ={w(i,j) if (i,j) E, degree matrix of a weighted graphGwill be denotedDG, and is the diagonal matrix such thatDG(i,i) = jAG(i,j).}

3 The Laplacian matrix of a weighted graphGwill be denotedLG. Last class, we defined it byLG=DG will now see a more convenient definition of the Laplacian . To begin, letG1,2be the graph ontwo vertices with one edge1of weight 1. We defineLG1,2def=[1 1 11.]Note thatxTLG1,2x= (x(1) x(2))2.( )For the graph withnvertices and just one edge between verticesuandv, we can define theLaplacian similarly. For concreteness, I ll call this graphGu,v. It s Laplacian matrix is then-by-nmatrix whose only non-zero entries are in the intersections of rows and columnsuandv. Thetwo-by-two matrix at the intersections of these rows and columns is, of course,[1 1 11].For a weighted graphG= (V,E,w), we now defineLGdef= (u,v) Ew(u,v)LGu, should verify for yourself that this is equivalent to the definition I gave elementary properties of the Laplacian follow from this definition.

4 In particular, it is imme-diate that for allx IRVxTLGx= (u,v) Ew(u,v)(x(u) x(v))2.( )1 Generally, we will view unweighted graphs as graphs in which all edges have weight 1. If I do not mention theweight of an edge, assume it is 2: September 4, 20092-3 For an eigenvectorvof eigenvalue , this tells us thatvTLGv= vTv , every eigenvalue of a Laplacian matrix is non-negative. That is, the matrix ispositive the vertex set really doesn t matter, I actually prefer the notationL(E) whereEis a set of edges. Had I used this notation above, it would have eliminated some subscripts. Forexample, I could have writtenL{u,v}instead ofLGu, ConnectivityFrom ( ), we see that if all entries ofxare the same, thenxTLGxequals zero. From the definitionLG=DG AG, we can immediately see thatLGx=0, so the constant vectors are eigenvectors ofeigenvalue (V,E)be a graph, and let0 = 1 2 nbe the eigenvalues ofits Laplacian matrix.

5 Then, 2>0if and only ifGis first show that 2= 0 ifGis disconnected. IfGis disconnected, then it can be describedas the union of two graphs,G1andG2. After suitably re-numbering the vertices, we can writeLG=[LG100LG2].So,LGhas at least two orthogonal eigenvectors of eigenvalue zero:[01]and[10].where we have partitioned the vectors as we did the the other hand, assume thatGis connected and thatxis an eigenvector ofLGof eigenvalue ,we havexTLGx= (u,v) E(x(u) x(v))2= , for each pair of vertices (u,v) connected by an edge, we havex(u) =x(v). As every pairof verticesuandvare connected by a path, we may inductively apply this fact to show thatx(u) =x(v) for all verticesuandv. Thus,xmust be a constant vector. We conclude that theeigenspace of eigenvalue 0 has dimension course, the same holds for weighted 2: September 4, Some Fundamental GraphsWe now examine the eigenvalues and eigenvectors of the Laplacians of some fundamental particular, we will examine The complete graph onnvertices,Kn, which has edge set{(u,v) :u6=v}.

6 The star graph onnvertices,Sn, which has edge set{(1,u) : 2 u n}. The path graph onnvertices,Pn, which has edge set{(u,u+ 1) : 1 u < n}. The ring graph onnvertices,Rn, which has all the edges of the path graph, plus the edge(1,n).Lemma Laplacian ofKnhas eigenvalue0with multiplicity1andnwith multiplicityn multiplicty of the zero eigenvalue follows from Lemma compute the non-zero eigenvalues, letvbe any non-zero vector orthogonal to the all-1s vector,so iv(i) = 0.( )Assume, without loss of generality, thatv(1)6= 0. We may now compute the first coordinate ofLKnv, and then divide byv(1) to compute . We find(LKnv) (1) = (n 1)v(1) n j=2v(j) =nv(1),by ( ).So, every vector orthogonal to the all-1s vector is an eigenvector of determine the eigenvalues ofSn, we first observe that each vertexi 2 has degree 1, and thateach of these degree-one vertices has the same neighbor.

7 Whenever two degree-one vertices sharethe same neighbor, they provide an eigenvector of eigenvalue (V,E)be a graph, and letiandjbe vertices of degree one that are bothconnected to another vertexk. Then, the vectorvgiven byv(u) = 1u=i 1u=j0otherwise,is an eigenvector of the Laplacian ofGof eigenvalue can immediately verify thatLGv= 2: September 4, 20092-5 The existence of this eigenvector implies thatv(i) =v(j) for every eigenvectorvof a graphSnhas eigenvalue0with multiplicity1, eigenvalue1with multiplicityn 2, and eigenvaluenwith multiplicty of the eigenvalue 0 follows from Lemma Applying Lemma toverticesiandi+ 1 for 2 i < n, we findn 2 linearly independent eigenvectors of eigenvalue 1. Todetermine the last eigenvalue, recall that the trace2of a matrix equals the sum of its know that the trace ofLSnis 2n 2, and we have identifiedn 1 eigenvalues that sum ton 2.

8 So, the remaining eigenvalue must ben. Knowing this, and the fact that the correspondingeigenvector must be constant across vertices 2 throughn, make it an easy exercise to compute thelast Laplacian ofRnhas eigenvectorsxk(u) = sin(2 ku/n),andyk(u) = cos(2 ku/n),for1 k n/2. Whennis even,xn/2is the all-zero vector, so we only haveyn/2. Eigenvectorsxkandykhave eigenvalue2 2 cos(2 k/n). best way to see thatxkandykare eigenvectors is to plot the graph on the circle usingthese vectors as coordinates. That they are eigenvectors is geometrically obvious. To compute theeigenvalue, just consider vertex 1, and use the double-angle formula to compute:(LRnxk) (1) = 2xk(1) xk(0) xk(2)= 2 sin(2 k/n) sin(2 k2/n)= 2 sin(2 k/n) 2 sin(2 k/n) cos(2 k/n)= (2 cos(2 k/n))x(1).The computation for cos follows Laplacian ofPnhas the same eigenvalues asR2n, and eigenvectorsvk(u) = cos( ku/n k/2n).

9 For0 k < is our first interesting example. We derive the eigenvectors and eigenvalues by treatingPnas a quotient ofR2n: we will identify vertexuofPnwith both verticesuand 2n+ 1 an eigenvector ofR2nin whichz(u) =z(2n+ 1 u) for allu. I then claim that the firstncomponents ofzgive an eigenvector sum of its diagonal entriesLecture 2: September 4, 20092-6To obtain such an eigenvectorz, takezk(u) = cos (2 k(u 1/2)/(2n))= cos (2 ku/(2n)) cos ( k/(2n))+ sin (2 ku/(2n)) sin ( k/(2n))=yk(u) cos ( k/(2n)) +xk(u) sin ( k/(2n)).So,zkis an eigenvector ofR2nof eigenvalue kdef= 2 cos(2 k/2n).We now setvk(i) =zk(i) for 1 i n. To see whyvkis an eigenvector ofLPnof eigenvalue k,note that for 1< i < n,(LPnvk) (i) = 2vk(i) vk(i 1) vk(i+ 1)=12(2zk(i) zk(i 1) zk(i+ 1)+ 2zk(2n+ 1 i) zk(2n+ 1 (i 1)) zk(2n+ 1 (i+ 1)))=12( kzk(i) + kzk(2n+ 1 i))= kvk(i).Fori= 1, we have(LPnvk) (1) =vk(1) vk(2)= 2vk(1) vk(2) vk(1)= 2zk(1) zk(2) zk(2n)= kzk(1)= kvk(1).

10 Of course, the other end is quotient construction used in this proof is an example of a generally applicable have now seen that thekth eigenvector of the path graph alternates in signk 1 times. This isconsistent with our intuition that the Laplacian of the path graph is a discretization of a continuousstring, and that its eigenvectors are approxmations of its fundamental modes of vibration when itsends are this intuition is correct, then it should continue to be true even if we discretize a string whosematerial changes along its length. This corresponds to a weighted path graph.