Bipartite Spectrum Symmetry Check

Problem

Check whether a list of eigenvalues is symmetric about zero, a necessary condition for the adjacency spectrum of a graph to come from a bipartite graph.

For every value x there must be another value within tolerance of -x. Return a boolean. eigenvalues is a list of numbers and tol is the tolerance.

Hint

Symmetric spectra are a fingerprint of bipartiteness for connected graphs.

Test cases

case 1

in: [[2,1,0,-1,-2],1e-9]

expected: true

case 2

in: [[2,1,-1],1e-9]

expected: false

case 3

in: [[0,0],1e-9]

expected: true

case 4

in: [[3],1e-9]

expected: false

case 5

in: [[],1e-9]

expected: true

Starter codePython

def spectrum_symmetry(eigenvalues, tol):
    # Your code here
    pass

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