Spectral Embedding First Two Eigenvectors

Problem

Compute the first two Laplacian eigenvectors of an undirected graph, forming a spectral embedding of its nodes.

Diagonalize the Laplacian with Jacobi rotations, order the eigenvalues, and return an n by 2 matrix whose columns are the eigenvectors of the two smallest eigenvalues. Each column is sign-normalized so its first nonzero entry is positive. edges is a list of [u, v] pairs.

Hint

The two smallest Laplacian eigenvectors give the classic spectral layout.

Test cases

case 1

in: [4,[[0,1],[1,2],[2,3]]]

expected: [[0.49999999999999983,0.6532814824381882],[0.49999999999999983,0.27059805007309834],[0.5000000000000001,-0.2705980500730985],[0.49999999999999994,-0.65328148243…

case 2

in: [4,[[0,1],[0,2],[0,3]]]

expected: [[0.5,0],[0.4999999999999998,0.7045253021425352],[0.5,-0.7096602923347868],[0.5,0.005134990192251667]]

case 3

in: [3,[[0,1],[1,2],[2,0]]]

expected: [[0.5773502691896258,0.7071067811865475],[0.5773502691896258,-0.7071067811865475],[0.5773502691896258,0]]

case 4

in: [2,[[0,1]]]

expected: [[0.7071067811865475,0.7071067811865475],[0.7071067811865475,-0.7071067811865475]]

Starter codePython

import math
def spectral_embedding(n, edges):
    # Your code here
    pass

4 test cases · run your code against them in the editor