The orthogonality graph $\Omega(n)$ with $2^n$ vertices is the graph with vertex set $\{-1,+1\}^n$, with two vertices being adjacent if and only if they are orthogonal (as vectors in the standard inner product space $\mathbb{Q}^n$). Since two such vectors are orthogonal if and only if the number of components of like sign is exactly equal to $n/2$, this graph is isomorphic to the graph with vertex set $\lbrace0,1\rbrace^n$ and two vertices adjacent if and only if their Hamming distance is equal to $n/2$. I am seeking the spectrum of $\Omega(n)$ - not just the eigenvalues but their multiplicities. In particular I am looking for the inertia of these graphs - that is the numbers of positive, zero and negative eigenvalues. Does anyone know where I should look?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.