Lecture 2: Properties of the Laplacian, Positive Semidefinite Matricies, Spectra of Common Graphs, Connection to the Continuous Laplacian

18.409 An Algorithmist’s Toolkit September 15, 2007 Lecture 2 Scribe: Mergen Nachin 2009 Lecturer: Jonathan Kelner 1 Administrative Details • Signup online for scribing. 2 Review of Lecture 1 All of the following are covered in detail in the notes for Lecture 1: • The definition of LG , specifically that LG = DG − AG , where DG is a diagonal matrix of degrees and AG is the adjacency matrix of graph G. • The action of LG on a vector x, namely that [LG x]i = deg(i) (xi − average of x on neighbors of i) • The eigenvalues of LG are λ1 ≤ · · · ≤ λn with corresponding eigenvectors v1 , . . . , vn . The first and the most trivial eigenvector is v1 = 1 with an eigenvalue λ1 = 0. We are mostly interested in v2 and λ2 . 3 Properties of the Laplacian 3.1 Some simple properties Lemma 1 (Edge Union) If G and H are two graphs on the same vertex set with disjoint edge sets, LG∪H = LG + LH (additivity) (1) Lemma 2 (Isolated Vertices) If a vertex i ∈ G is isolated, then the corresponding row and column of the Laplacian are zero, i.e. [LG ]i,j = [LG ]j,i = 0 for all j. Lemma 3 (Disjoint Union) These together imply that the Laplacian of the disjoint union of G and H is direct sum of LG and LH , i.e.: � � LG 0 ‘ LG H = LG ⊕ LH = (2) 0 LH Proof Consider the graph G � v(H) = (VG ∪ VH , EG ), namely the graph consisting of G along with the vertex set of H as disjoint vertices. Define v(G) � H similarly. By the second remark, � � � � 0 0 LG 0 and Lv(G)�H = . LG�v(H) = 0 0 0 LH By definition, G � H = (G � v(H)) ∪ (v(G) � H), and so by the first remark: � � 0 LG ‘ . LG H = LG ⊕ LH = 0 LH This implies the Laplacian is the direct sum of the Laplacians of the connected components. Thus, 2-1 Theorem 4 (Disjoint Union Spectrum) If LG has eigenvectors v1 , . . . , vn with eigenvalues λ1 , . . . , λn , and LH has eigenvectors w1 , . . . , wn with eigenvalues µ1 , . . . , µn , then LG�H has eigenvectors: v1 ⊕ 0, . . . , vn ⊕ 0, 0 ⊕ w1 , . . . , 0 ⊕ wn with corresponding eigenvalues: λ1 , . . . , λn , µ1 , . . . , µn . Proof By the previous lemma, � LG ‘ H ∗ (v1 ⊕ 0) = LG 0 �� 0 LH v1 0 � � = λ1 v1 0 � Thus v1 ⊕ 0 is an eigenvector of LG�H with eigenvalue λ1 . The rest follow by symmetry. 3.2 The Laplacian of an edge Definition 5 Let Le be the Laplacian of the graph on n vertices consisting of just the edge e. Example 1 If e is the edge (v1 , v2 ), then ⎛ ⎜ ⎜ ⎜ Le = ⎜ ⎜ ⎝ −1 1 0 .. . 0 0 0 0 0 LG = � 1 −1 0 0 ··· .. . ··· 0 0 0 .. . ⎞ ⎟ ⎟ ⎟ ⎟. ⎟ ⎠ 0 By additivity, this lets us write: Le (3) e∈E This will allow us to prove a number of facts about the Laplacian by proving them for one edge and adding them up. The more general technique, which we’ll use more later, is to bound Laplacians by adding matrices of substructures. So for an edge e, � Le = −1 1 1 −1 � ⊕ [zeros] . Note that: � and so � √1 2 − √12 1 −1 �T −1 1 � = � 1 −1 � � 1 � −1 =2 √1 2 − √12 � � √1 2 − √12 � , is an eigenvector with eigenvalue 2. This decomposition implies: xT Le x = Remark � � x1 x2 � � 1 −1 � � 1 −1 � � x1 x2 � The Laplacian is a quadratic form, specifically: � � � 2 xT LG x = xT ( Le )x = xT Le x = (xi − xj ) e∈E e∈E This implies that L is positive semidefinite. 2-2 (i,j)∈E 2 = (x1 − x2 ) . (4) (5) 3.3 Review of Positive Semidefiniteness Definition 6 A symmetric matrix M is positive semidefinite (PSD) if ∀x ∈ Rn , xT M x ≥ 0. M is positive definite (PD) if the inequality is strict ∀x = � 0. Lemma 7 M is PSD iff all eigenvalues λi ≥ 0. Similarly M is PD iff all eigenvalues λi > 0. Proof Let’s consider the matrix M in its eigenbasis, that is M = QT ΛQ. Clearly, y T Λy = for all y ∈ Rn iff λi ≥ 0 for all i. Similar for PD matrix. � i λi yi2 ≥ 0 Lemma 8 (PSD Matrix Decomposition) M is PSD iff there exists a matrix A such that M = AT A. (6) Note that A can be (n × k) for any k, and that it need not be square. Importantly, note that A is not unique. Proof (⇒) If M is positive semidefinite, recall that M can be diagonalized as M = QT ΛQ, thus where Λ1/2 has � �T � � M = QT Λ1/2 Λ1/2 Q = Λ1/2 Q Λ1/2 Q , √ λi on the diagonal. (⇐) If M = AT A, then xT M x = xT AT Ax = (Ax)T (Ax) Letting y = (Ax) ∈ Rk , we see that: xT M x = y T y = ||y||2 ≥ 0. 3.4 Factoring the Laplacian We know from the previous section that we can factor L as AT A using eigenvectors, but there also exists a much nicer factorization which we will show here. Definition 9 Let m be the number of edges and n be the number of vertices. Then the incidence matrix � = �G is the m × n matrix given by: ⎧ if e = (v, w) and v < w ⎨ 1 −1 if e = (v, w) and v > w �e,v = (7) ⎩ 0 otherwise. 2-3 Example 2 The Laplacian and the Incidence matrix of the graph G= 4 3 ⎛ b 1 c a is 3 ⎜ −1 LG = ⎜ ⎝ −1 −1 −1 1 0 0 ⎞ −1 0 ⎟ ⎟ 0 ⎠ 1 −1 0 1 0 ⎛ 1 −1 �G = ⎝ 1 0 1 0 0 −1 0 ⎞ 0 0 ⎠ −1 2 Lemma 10 LG = �T �. �� � � � � � Proof Observe that �T � ij = (ith column of �)·(jth column of �) = e [�]e,vi [�]e,vj This gives three cases: • When i = j, �2 �� � T � � � ij = [�]e,vi = e � 1 = deg(i). e incident to vi • When i �= j and no edge exists between vi and vj , �� � �� � T � � � ij = [�]e,vi [�]e,vj = 0 e as every edge is non-incident to at least one of vi , vj . • When i �= j and exists an edge e� between vi and vj , �� � � �� � �� � T � � � ij = [�]e,vi [�]e,vj = [�]e� ,vi [�]e� ,vj = −1. e Corollary 11 Note that � xT LG x = ||�x||2 = 2 (xi − xj ) , (i,j)∈E This gives another proof that L is PSD. 3.5 Dimension of the Null Space Theorem 12 If G is connected, the null space is 1-dimensional and spanned by the vector 1. Proof Let x ∈ null(L), i.e. LG x = 0. This implies � 2 xT LG x = (xi − xj ) = 0. (i,j)∈E Thus, xi = xj for every (i, j) ∈ E. As G is connected, this means that all xi are equal. Thus every member of the null space is a multiple of 1. Corollary 13 If G is connected, λ2 > 0. Corollary 14 The dimension of the null space of LG is exactly the number of connected components of G. 2-4 4 Spectra of Some Common Graphs We compute the spectra of some graphs: Lemma 15 (Complete graph) The Laplacian for the complete graph Kn on n vertices has eigenvalue 0 with multiplicity 1 and eigenvalue n with multiplicity n − 1 and associated eigenspace {x|x · 1 = 0}. Proof By corollary 13, we conclude that eigenvalue 0 has multiplicity 1. Now, take any vector v which is orthogonal to 1 and consider [LKn v]i . Note that this value is equal to � � (n − 1)vi − vj = nvi − vj = nvi � j=i j Hence any vector v which is orthogonal to 1 is an eigenvector with an eigenvalue n. Lemma 16 (Ring graph) The Laplacian for the ring graph Rn on n vertices has eigenvectors xk (u) yk (u) = sin(2πku/n), and = cos(2πku/n) for 0 ≤ k ≤ n/2. Both xk and yk have eigenvalue 2 − 2 cos(2πk/n). Note that, x0 = 0 should be ignored and y0 is 1, and when n is even xn/2 = 0 should be ignored and we only have yn/2 . Proof . The best way to see is to plot the graph on the circle using these vectors as coordinates. Below is the plot for a k = 3. Just consider vertex 1. Keep in mind that sin(2x) = 2 sin(x) cos(x). Then, [Lxk ]1 = 2xk (1) − xk (0) − xk (2) = 2 sin(2πk/n) − 0 − sin(2πk2/n) = 2 sin(2πk/n) − 2 sin(2πk/n) cos(2πk/n) = (2 − 2 cos(2πk/n)) sin(2πk/n) (2 − 2 cos(2πk/n))xk (1) = Note that this shows that x(u) = �(e2πi(ku+c)/n ) is an eigenvector for any k ∈ Z, c ∈ C. Lemma 17 (Path graph) The Laplacian for the path graph Pn on n vertices has the same eigenvalues as R2n and eigenvectors vk (u) = sin(πku/n + π/2n) for 0 ≤ k < n 2-5 Proof 0 9 1 2 3 8 7 6 R10 4 5 P5 0 1 2 3 4 We will realize Pn as quotient of R2n . Suppose z was an eigenvector of LR2n in which zi = z2n−1−i for 0 ≤ i < n. Take the first n components of z and call this vector v. Note that for 0 < i < n: � [LPn v]i = 2(vi − neighbors of i in Pn ) � = 2(zi − neighbors of i in R2n ) � � = (zi − neighbors of i in R2n ) + (z2n−i−1 − neighbors of (2n − i − 1) in R2n ) = 1 ([LR2n z]i + [LR2n z]2n−i−1 ) 2 1 (λzi + λz2n−i−1 ) 2 λzi = λvi = = Now consider the case when i = 0. [LPn v]0 = v0 − v1 = 2v0 − v1 + v0 = 2z0 − z1 + z0 = 2z0 − z1 + z2n−1 = λz0 = λv0 Hence, v is an eigenvector of LPn . Now we show that such v exists, that is, there exists eigenvector z of LR2n in which zi = z2n−1−i for 0 ≤ i < n. Take z, zk (u) = = = sin(πku/n + π/2n) sin(πku/n) cos(π/2n) + cos(πku/n) sin(π/2n) xk (u) cos(π/2n) + yk sin(π/2n) We see that zk is in the span of xk and yk . Hence, zk is an eigenvector of LR2n with an eigenvalue 2 − 2 cos(2πk/n) by lemma 16. Check that zk satisfies zk (i) = zk (2n − 1 − i) 4.1 Graph Products The next natural example is the grid graph, which will follow from general theory about product graphs. 2-6 Definition 18 Let G = (V, E), and H = (W, F ). The product graph G × H has vertex set V × W and edge set: ((v1 , w), (v2 , w)) , ((v, w1 ), (v, w2 )) , ∀(v1 , v2 ) ∈ E, w ∈ W and ∀(w1 , w2 ) ∈ F, v ∈ V. Example 3 Pn × Pm = Gn,m . We see that the vertices of Pn × Pm are: ⎧ (v1 , w1 ) (v1 , w2 ) · · · (v1 , wm ) ⎪ ⎪ ⎪ ⎨ (v2 , w1 ) (v2 , w2 ) · · · (v2 , wm ) v(Gn,m ) = .. .. .. .. ⎪ . . . . ⎪ ⎪ ⎩ (vn , w1 ) (vn , w2 ) · · · (vn , wm ) ⎫ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎭ The vertices are written in the above layout because it makes the edges intuitive. The edges are: • For a fixed w, i.e. a column in the above layout, a copy of Pn . • For a fixed v, i.e. a row in the above layout, a copy of Pm . Thus Pn × Pm = Gn,m , which is to say the product of two path graphs is the grid graph. Theorem 19 (Graph Products) If LG has eigenvectors v1 , . . . , vn with eigenvalues λ1 , . . . , λn , and LH has eigenvectors w1 , . . . , wk with eigenvalues µ1 , . . . , µk , then LG×H has, for all 1 ≤ i ≤ n, 1 ≤ j ≤ k, an eigenvector: zij (v, w) = xi (v)yj (w) of eigenvalue λi + µj . Note importantly that eigenvalues add here, they do not multiply. Proof Let Am be the graph with m isolated vertices. We can then decompose the product as: G × H = (G × Ak ) ∪ (An × H), i.e. the edge union of k disjoint copies of G and n disjoint copies of H, exactly as in the definition. By Lemmas 1 and 3 we have LG×H = LG×Ak + LAn ×H = LG ⊗ Ik + In ⊗ LH Consider zij = xi ⊗ yj as above for a fixed i and j, we see that: LG×H zij = (LG ⊗ Ik ) (xi ⊗ yj ) + (In ⊗ LH ) (xi ⊗ yj ) = (λi xi ⊗ yj ) + (xi ⊗ µj yj ) = (λi + µj ) (xi ⊗ yj ) = (λi + µj )zij . Corollary 20 Gn,m has eigenvectors and eigenvalues completely determined by those of Pn and Pm as above. 5 Why is this called the Laplacian? It turns out that the graph Laplacian is very naturally related to the continuous Laplacian. • In 1 dimension, the continuous Laplacian is d dx . • In 2 dimensions, the continuous Laplacian is �f = 2-7 d2 f dx2 + d2 f dy 2 . 5.1 Discretizing Derivatives, 1d case Consider a 1d function f : R → R, which we wish to discretize at the points (. . . , k−2, k−1, k, k+1, k+2, . . .): We approximate the first derivative at the line midpoints, between the values at the adjacent points: df dx , up to scaling, by taking the differences The discrete first derivative of f is a function on edges, and is, up to scaling �Pn f , the incidence matrix 2 of Pn defined earlier. In order to compute the second derivative at the original points, ddxf2 , again up to scaling, we take the differences of the adjacent midpoints at the vertices: The discrete second derivative of f is thus, up to scaling, −LPn f . 5.2 Discretizing Derivatives, 2d case Here we discretize f : R2 → R on a grid: f(k-1,k+1) f(k,k+1) f(k+1,k+1) f(k-1,k) f(k,k) f(k+1,k) f(k-1,k-1) f(k,k-1) f(k+1,k-1) To compute the discrete derivative in the x and y directions, we’ll just look at a little piece. On the df df horizontal edges, we approximate dx up to scaling, and do likewise on the vertical edges with dy : 2-8 f(k,k+1)-f(k,k) f(k+1,k)-f(k,k) f(k,k)-f(k-1,k) f(k,k)-f(k,k-1) Again, the discrete derivative of f is a function on edges. When we consider the concatenation of the two discretization of the directional derivatives, we see that the discretization of the gradient, up to scaling, is �Gn,m f . Finally we use this to compute the discretized Laplacian, up to scaling, and get: f(k,k+1)+f(k,k-1)+f(k+1,k)+f(k-1,k) -4 f(k,k) Thus the discretized Laplacian in two dimensions of f is −LGn,m f . 5.3 A Note on Fourier Coefficients We observed that paths and rings had eigenvectors that looked like Fourier coefficients. In the continuous case: d2 sin(kx + c) dx2 2 d cos(kx + c) dx2 = k 2 sin(kx + c) = k 2 cos(kx + c) Thus sin(kx + c) and cos(kx + c) are eigenfunctions of the eigenvalue k 2 . 6 d2 dx2 operator, i.e. the 1d Laplacian, both with Bounding Laplacian Eigenvalues Lemma 21 (Sum of the eigenvalues) Given an n-vertex graph G with degrees di , where dmax = maxi di , and Laplacian LG with eigenvalues λi , � � λi = di ≤ dmax n (8) i i Proof The first two expressions are both the trace, the upper bound is trivial. Lemma 22 (Bounds on λ2 and λn ) Given λi and di as above, � i di λ2 ≤ n−1 2-9 (9) � λn ≥ di n−1 i (10) Proof By the previous slide and the fact that λ1 = 0, we get bounds follow immediately. 7 �n i=2 λi = � i di . As λ2 ≤ · · · ≤ λn , the Bounding λ2 and λmax Theorem 23 (Courant-Fischer Formula) For any n × n symmetric matrix A, λ1 = λ2 = λmax = min xT Ax = min xT Ax xT x min xT Ax = min xT Ax xT x ||x||=1 � x=0 ||x||=1 x=0 � x⊥v1 x⊥v1 max xT Ax = ||x||=1 max x=0 � (11) xT Ax xT x Proof We consider the diagonalization A = QT ΛQ. As seen earlier, xT Ax = (Qx)T Λ(Qx). As Q is orthogonal, we also have ||Qx|| = x. Thus it suffices to consider diagonal matrices. Moreover, all of the equalities on the right follow immediately from linearity. Thus we need to consider, for ||x|| = 1: ⎛ ⎞⎛ ⎞ λ1 x1 � λ x2 ⎜ ⎟ ⎜ .. ⎟ � 2 .. � i 2i . = λ xT Λx = (x1 · · · xn ) ⎝ x = ⎠⎝ . ⎠ i i . xi λn xn We compute the gradient and find: � � �� 2λi x3 2λi xi �x xT Λx i = � 2 − � i 2 = 2λi (xi − x3i ) xi ( x2i ) thus all extremal values occur when one xi = 1 and the rest are 0. The identities follow immediately. Corollary 24 (Rayleigh Quotient) Letting G = (V, E) be a graph with Laplacian LG , λ1 = 0 λ2 xT LG x = min x⊥v1 xT x v1 = 1 � = λmax = xT LG x max x=0 � xT x min P � x=0 2 (i,j)∈E x=0 i∈V � x=0 � = max x=0 � (xi − xj ) � (i,j)∈E � x2i (xi − xj ) i∈V (12) 2 x2i The Rayleigh Quotient is a useful tool for bounding graph spectra. Whereas before we had to consider all possible vectors x, now in order to get an upper bound on λ2 we need only produce a vector with small Rayleigh quotient. Likewise to get a lower bound on λmax we need only to find a vector with large Rayleigh quotient. Examples next lecture! 2-10