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
    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
    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
    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
    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
    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
    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
    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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.