On eigenvalues of symmetric (+1, -1) matrices

Abstract

To every symmetric matrix A with entries ±1, we associate a graph G(A), and ask (for two different definitions of distance) for the distance of G(A) to the nearest complete bipartite graph (cbg). Let λ 1(A), λ 1 (A) be respectively the algebraically largest and least eigenvalues of A. The Frobenius distance (see Section 4) to the nearest cbg is bounded above and below by functions of n -λ 1 (A), where n=ord A. The ordinary distance (see Section 1) to the nearest cbg is shown to be bounded above and below by functions of λ 1 (A). A curious corollary is: there exists a function f (independent of n, and given by (1.1)), such that |λ i (A) | ≦f(λ 1(A), where λ i (A) is any eigenvalue of A other than λ i (A). © 1974 Hebrew University.