Description

Homework policy. Please turn in all your homework through GradeScope as a single .pdf file. For computational problems, turn in listings of any code you wrote; any sample output and plots; and an interactive session transcript as a Matlab diary file, Jupyter notebook .pdf, etc.
You are forbidden from searching the web in any way to find answers to these problems. However, you are welcome to search the web for advice on using Matlab, Julia, and other software tools. Stackoverflow is great.
Problem 1. Complete bipartite graph. Let m and n be integers. Let Km,n be the complete bipartite graph on m + n vertices. (Think of this graph as having m red vertices, n blue vertices, and all mn possible edges joining a red vertex to a blue vertex.) What are the eigenvalues of the Laplacian of Km,n? Prove your answer correct. (Note: You can do this by pure thinking. If it were me, I would do it by computing the eigenvalues for a few examples in Matlab/Julia/Python, guessing the pattern, and proving my answer correct.)
Problem 2. Semidefinite ordering and eigenvalues. We noted in class that if for graphs G and H (or indeed for any two symmetric matrices), then λi(G) ≤ λi(H) for every i. Show that the converse of this statement is false, by finding unweighted graphs G and H, both with n vertices, for which λi(G) ≤ λi(H) for 1 ≤ i ≤ n but . (Hint: I did this by first finding a very simple example consisting of two small symmetric matrices that were not graph Laplacians, and then figuring out how to make the same thing happen with an unweighted Laplacian matrix.)
Problem 3. Inverse and pseudoinverse. For this problem, A is an n-by-n symmetric matrix with eigenvalues λ1 ≤ λ2 ≤ ··· ≤ λn (possibly including duplicates) associated with mutually orthogonal unit-length eigenvectors w1,w2,…,wn. As we know, we can write A as a sum over eigenvalues as
.
3.1. Prove that, if A is nonsingular, its inverse can be written as
.
1
3.2. Whether A is singular or not, its pseudoinverse is defined as
,
where the sum is taken over the nonzero eigenvalues of A. If A is nonsingular, then A† = A−1.
Prove that if x is orthogonal to the null space of A (that is, xT wi = 0 whenever λi = 0), then
A†Ax = AA†x = x.
3.3. Prove that if 0 then
3.4 Prove that if 0 and null(A) = null(B) = span(1), then . (Hint: Take 1T x = 0, let y = A†x − B†x, and look at yT By.)
Problem 4. Kronecker products and product graphs. If A is an m-by-m symmetric matrix and B is an n-by-n symmetric matrix, their Kronecker product is the mn-by-mn matrix that can be written in block form as
.
In words, A⊗B is built by replacing each entry of A with a complete copy of B multiplied by that entry. (The Kronecker product is defined for nonsymmetric and non-square matrices too, but we will stick to the square symmetric case here.)
4.1. Prove that if Av = λv and Bw = νw, then λν is an eigenvalue of A ⊗ B. What is the corresponding eigenvector (as a function of v and w)?
4.2. In class, I defined the product of two graphs G×H, using the same notation and definition as Section 6.3 of Spielman. Spielman mentions that if G has m vertices and H has n vertices, then
LG×H = (LG ⊗ In) + (Im ⊗ LH).
I actually prefer using this equality as the definition of the graph product, so I won’t ask you to prove it from Spielman’s definition. Use this equality (not Spielman’s definition) to prove that if λ is an eigenvalue of G (that is, of LG) and ν is an eigenvalue of H, then λ + ν is an eigenvalue of G × H.
2