Adjacency Eigenvalue Bound Check

Problem

Check the spectral bound for a graph with adjacency matrix A: every eigenvalue lambda must satisfy |lambda| <= max degree.

Return True if all given eigenvalues satisfy the bound within 1e-9, otherwise False.

Hint

This bound follows from the Gershgorin circle theorem applied to the adjacency matrix.

case 1

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

expected: true

case 2

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

expected: true

case 3

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

expected: false

case 4

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

expected: false

Starter codePython

def adjacency_bound_holds(A, eigenvalues):
    # Your code here
    pass

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