9
$\begingroup$

The orthogonality graph, $\Omega(n)$, has vertex set the set of $\pm 1$ vectors of length $n$, with orthogonal vectors being adjacent.

I am only interested when $4|n$, since otherwise $\Omega(n)$ is empty or bipartite. I am keen to know the spectrum of $\Omega(n)$ - the eigenvalues and their multiplicities. In particular I am seeking the inertia of $\Omega(n)$ - that is the numbers of positive, zero and negative eigenvalues. Many thanks Clive

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ If $n=4$, a computer calculation suggests that the eigenvalues are $6$ (multiplicity $2$), $-2$ (multiplicity $6$) and $0$ (multiplicity $8$). For $n=8$ we obtain eigenvalues $70$, $-10$, $6$, $0$ with multiplicities $2$, $56$, $70$, $128$. So perhaps $0$ is an eigenvalue with multiplicty $2^{n-1}$ in general. $\endgroup$
    – Philipp Lampe
    Commented Mar 8, 2018 at 11:07
  • 1
    $\begingroup$ @PhilippLampe Looking at the involved binomial coefficients, educated guesses for $n=12$ would be either $924^2(-72)^{330}70^{924}(-54)^{792}0^{2048}$ or $924^2(-48)^{330}70^{924}(-64)^{792}0^{2048}$. $\endgroup$
    – Wolfgang
    Commented Mar 8, 2018 at 14:37
  • 1
    $\begingroup$ Given a vertex $v$ in $\Omega(n)$. Then $v$ the negative $-v$ are not connected, but they have the same sets of neighbors in $\Omega(n)$. Define a vector $u\in\mathbb{Z}^{V(\Omega(n))}$ such that it has entry $1$ at $v$, entry $-1$ at $-v$ and zeros otherwise. Then $u$ is an eigenvector of the adjacency matrix of $\Omega(n)$ with eigenvalue $0$. This gives $2^{n-1}$ linearly independent eigenvectors with eigenvalue $0$ parametrized by pairs $(v,-v)$. $\endgroup$
    – Philipp Lampe
    Commented Mar 8, 2018 at 15:51
  • 2
    $\begingroup$ If two vertices $u,v$ in $\Omega(n)$ are connected, then $\vert \{i\in[n]\mid u_i=1\}\rvert$ and $\vert \{i\in[n]\mid v_i=1\}\rvert$ have the same parity. Hence $\Omega(n)$ is a disjoint union of two graphs each of which is regular with degree ${n \choose n/2}$. It follows that this number is an eigenvalue with multiplicity at least $2$. $\endgroup$
    – Philipp Lampe
    Commented Mar 8, 2018 at 16:16
  • 2
    $\begingroup$ This graph is a Cayley graph for $\mathbb{Z}_2^n$, so you can use the usual techniques for determining the eigenvalues of Cayley graphs for abelian groups for this graph. You get a sum of products of binomial coefficients. I think that this has been simplified by @ChrisGodsil in some unpublished notes. You could see if he is willing to share. $\endgroup$
    – David Roberson
    Commented Mar 9, 2018 at 12:41

3 Answers 3

Reset to default
9
$\begingroup$

If $G$ is a Cayley graph for $\mathbb{Z}_2^n$ with connection set $C \subseteq \mathbb{Z}_2^n \setminus \{0\}$, then for each element $a \in \mathbb{Z}_2^n$ there is an eigenvector $v$ given by $$v_x = (-1)^{x \cdot a}$$ where $x \cdot a$ is the usual inner product when $x$ and $a$ are thought of as 01-vectors (i.e., it is the number of 1's they have in common). This eigenvector has eigenvalue \begin{align*}\sum_{c \in C} (-1)^{c\cdot a} &= |\{c \in C: c \cdot a \equiv 0 \ \text{mod} \ 2 \}| - |\{c \in C: c \cdot a \equiv 1 \ \text{mod} \ 2 \}| \\ &= |C| - 2|\{c \in C: c \cdot a \equiv 1 \ \text{mod} \ 2 \}| \end{align*} This gives a full orthogonal set of eigenvectors for the graph $G$.

In your case, the graph can be described as a Cayley graph for $\mathbb{Z}_2^n$ with connection set consisting of all of the elements with $n/2$ 1's in them (when written as binary strings). We can think of the binary strings as subsets of the $n$ element set $[n]$. So for each subset $S \subseteq [n]$, we get an eigenvalue of $$\sum_{T \subseteq [n], |T| = n/2} (-1)^{|S \cap T|}.$$ If $S$ has size $k$ then this is equal to $$\sum_{i=0}^k \sum_{T \subseteq [n], |T| = n/2, |S \cap T| = i} (-1)^i = \sum_{i=0}^k (-1)^i\binom{k}{i}\binom{n-k}{n/2 - i}.$$ I may have stolen this from the aforementioned notes of @ChrisGodsil (I hope he does not mind), but it follows from the well-known technique for computing the eigenvalues of Cayley graphs for $\mathbb{Z}_2^n$ described above.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ I wrote a program to calculate the numbers of different eigenvalues according to your formula. The difference of the numbers of positive vs negative eigenvalues (pos $-$ neg) seems to be $(-4)^{n/4}$. $\endgroup$
    – Taneli Huuskonen
    Commented Mar 9, 2018 at 17:06
  • 1
    $\begingroup$ Note that ${k \choose i}={k\choose k-i}$ and ${n-k\choose n/2-i}={n-k\choose n/2 - (k-i)}$, so the sum is zero for odd $k$ and always even. Moreover, the sum is the same for $k$ and $n-k$, which is easy to see in terms of the subsets - the sums are identical for $S$ and $[n]\setminus S$ when $n/2$ is even. $\endgroup$
    – Taneli Huuskonen
    Commented Mar 9, 2018 at 17:18
5
$\begingroup$

To add to David E. Roberson's solution:

As already stated by Taneli Huuskonen's comment, the last sum is $0$ for odd $k$, so the eigenvalue $0$ has indeed the total multiplicity of $2^{n-1}$. For even $k=2K$ and putting $n=:2N$ (note that $N$ is still even), the sum can be simplified to $$(-1)^{k/2}\frac{(n-k)!(k)!}{(\frac n2)!(\frac {n-k}2)!(\frac k2)!} =(-1)^K\frac{\binom{2K}{ K}\binom{2(N-K)}{N-K}}{\binom NK}=:\lambda_{N,K},$$ and this eigenvalue occurs with multiplicity $2{\binom nk}=2{\binom n{2K}}$ for $K=0,...,\frac n4-1$ (by the symmetry $K\leftrightarrow N-K$) and with multiplicity ${\binom nk}$ for the "middle" one at $K=\frac n4=\frac N2.$

Improve this answer
$\endgroup$
0
3
$\begingroup$

The graph $\Omega(n)$ is one of the relations of the Hamming association scheme $H(n,2)$, namely, the one corresponding to the Hamming distance $n/2$, see e.g. here. Its eigenvalues are given by the values of the Krawchuk's polynomials $K_k(n/2)$, as $0\leq k\leq n$, see details in my answer to your MO question 295493, and multiplicities are just $\binom{n}{k}$, $0\leq k\leq n$.

For this one can e.g. compute that if $n$ is divisible by 4 then the number of 0 eigenvalues of $\Omega(n)$ is $2^{n-1}$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .