Heat Kernel Trace Lite

Problem

Compute the heat kernel trace of an undirected graph: trace(exp(-t L)) = sum of exp(-t * lambda) over the Laplacian eigenvalues.

Build the Laplacian, diagonalize it with Jacobi rotations, and sum the exponentials of the negated scaled eigenvalues. edges is a list of [u, v] pairs and t is the diffusion time. Return a float.

Hint

The heat trace decays fastest along the highest-frequency Laplacian modes.

Test cases

case 1

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

expected: 1.4176665095393064

case 2

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

expected: 1.4462603202968596

case 3

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

expected: 2

case 4

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

expected: 1.1353352832366128

Starter codePython

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

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