Lecture 1: Linear Algebra Review, Adjacency and Laplacian Matrices Associated with a Graph, Example Laplacians

18.409 An Algorithmist’s Toolkit September 10, 2009 Lecture 1 Scribe: Jesse Geneson (2009) Lecturer: Jonathan Kelner 1 Overview The class’s goals, requirements, and policies were introduced, and topics in the class were described. Every­ thing in the overview should be in the course syllabus, so please consult that for a complete description. 2 Linear Algebra Review This course requires linear algebra, so here is a quick review of the facts we will use frequently. Definition 1 Let M by an n × n matrix. Suppose that M x = λx for x ∈ Rn , x = � 0, and λ ∈ R. Then we call x an eigenvector and λ an eigenvalue of M . Proposition 2 If M is a symmetric n × n matrix, then • If v and w are eigenvectors of M with different eigenvalues, then v and w are orthogonal (v · w = 0). • If v and w are eigenvectors of M with the same eigenvalue, then so is q = av + bw, so eigenvectors with the same eigenvalue need not be orthogonal. • M has a full orthonormal basis of eigenvectors v1 , . . . , vn . All eigenvalues and eigenvectors are real. • M is diagonalizable: M = V ΛV T where V is orthogonal (V V T = In ), with columns equal to v1 , � . . . , vn , and Λ is diagonal, with the n corresponding eigenvalues of M as its diagonal entries. So M = i=1 λi vi viT . In Proposition 2, it was important that M was symmetric. No results stated there are necessarily true in the case that M is not symmetric. Definition 3 We call the span of the eigenvectors with the same eigenvalue an eigenspace. 3 Matrices for Graphs During this course we will study the following matrices that are naturally associated with a graph: • The Adjacency Matrix • The Random Walk Matrix • The Laplacian Matrix • The Normalized Laplacian Matrix 1-1 Let G = (V, E) be a graph, where |V | = n and |E| = m. We will for this lecture assume that G is unweighted, undirected, and has no multiple edges or self loops. Definition 4 For a graph G, the adjacency matrix A = AG is the n × n matrix given by � 1 if (i, j) ∈ E Ai,j = 0 otherwise For an unweighted graph G, AG is clearly symmetric. Definition 5 Given an unweighted graph G, the Laplacian matrix L = LG is the n × n matrix given by ⎧ ⎨ −1 if (i, j) ∈ E di if i = j Li,j = ⎩ 0 otherwise where di is the degree of the ith vertex. For unweighted G, the Laplacian matrix is clearly symmetric. An equivalent definition for the Laplacian matrix is LG = DG − AG , where DG is the diagonal matrix with ith diagonal entry equal to the degree of vi , and AG is the adjacency matrix. 4 Example Laplacians Consider the graph H with adjacency matrix ⎛ ⎜ ⎜ AH = ⎜ ⎜ ⎝ 0 1 0 1 0 1 0 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 ⎞ ⎟ ⎟ ⎟ ⎟ ⎠ This graph has Laplacian ⎛ ⎜ ⎜ LH = ⎜ ⎜ ⎝ 2 −1 0 −1 0 −1 2 −1 0 0 Now consider the graph G with adjacency matrix ⎛ AG 0 =⎝ 1 0 0 −1 3 −1 −1 1 0 1 ⎞ −1 0 0 0 ⎟ ⎟ −1 −1 ⎟ ⎟ 2 0 ⎠ 0 1 ⎞ 0 1 ⎠ 0 This graph has Laplacian ⎛ LG 1 = ⎝ −1 0 −1 2 −1 ⎞ 0 −1 ⎠ 1 LG is a matrix, and thus a linear transformation. We would like to understand how LG acts on a vector v. To do this, it will help to think of a vector v ∈ R3 as a map X : V → R. We can thus write v as 1-2 ⎛ ⎞ X(1) v = ⎝ X(2) ⎠ X(3) The action of LG on v is then ⎞ ⎛ ⎞⎛ ⎞ ⎛ ⎞ ⎛ 1 −1 0 X(1) X(1) − X(2) � X(1) − X(2) � ⎜ ⎟ LG v = ⎝ −1 2 −1 ⎠ ⎝ X(2) ⎠ = ⎝ 2X(2) − X(1) − X(3) ⎠ = ⎝ 2 X(2) − [ X(1)+X(3) ] ⎠ 2 0 −1 1 X(3) X(3) − X(2) X(3) − X(2) For a general Laplacian, we will have [LG v]i = [di ∗ (X(i) − average of X on neighbors of i)] Remark For any G, 1 = (1, . . . , 1) is an eigenvector of LG with eigenvalue 0, since for this vector X(i) always equals the average of its neighbors’ values. Proposition 6 We will see later the following results about the eigenvalues λi and corresponding eigenvec­ tors vi of LG : • Order the eigenvalues so λ1 ≤ . . . ≤ λn , with corresponding eigenvectors v1 , . . . , vn . Then v1 = 1 and λ1 = 0. So for all i λi ≥ 0. • One can get much information about the graph G from just the first few nontrivial eigenvectors. 5 Matlab Demonstration As remarked before, vectors v ∈ Rn may be construed as maps Xv : V → R. Thus each eigenvector assigns a real number to each vertex in G. A point in the plane is a pair of real numbers, so we can embed a connected graph into the plane using (Xv2 , Xv3 ) : V → R2 . The following examples generated in Matlab show that this embedding provides representations of some planar graphs. Image courtesy of Dan Spielman. Used with Permission. Figure 1: Plots of the first two nontrivial eigenvectors for a ring graph and a grid graph 1-3 Image courtesy of Dan Spielman. Used with Permission. Figure 2: Handmade graph embedding (left) and plot of the first two nontrivial eigenvectors (right) for an interesting graph due to Spielman Image courtesy of Dan Spielman. Used with Permission. Figure 3: Handmade graph embedding (left) and plot of first two nontrivial eigenvectors (right) for a graph used to model an airfoil 1-4