= Consider an undirected graph G = {V, E} with no isolated vertices and no self-loops. Let A be the adjacency matrix of G, and D the diagonal matrix with dii = degree(vi). Let K = D + A be the kernel matrix and L = D - A be the graph Laplacian (as defined in class). We define the normalized adjacency matrix by = D-1/2 AD-1/2, the normalized kernel matrix by K = D-1/2KD-1/2, and the normalized graph Laplacian by = D-1/2 LD-1/2. 1. Argue why D-1/2 exists, and what is its form. Show that K I + and ] = 1 - A. 2. Show that K and L are positive semi-definite. Prove that K and are positive semi-definite as well. 3. Show that the smallest eigenvalue li of L is 0, and that if G has k connected components, then the multiplicity of li is at least k (in fact, it is exactly k, but I am not asking you to prove that). Prove that the same is true for the smallest eigenvalue 11 of . 4. Show that the largest eigenvalue any of is 1, and that the largest eigenvalue Ny of K is 2. 5. Argue that the eigenvalues of K are non-negative. Prove that the eigenvalues of A are greater than or equal to -1. 6. Finish any arguments needed to conclude that: The eigenvalues of A satisfy: -1