Almost a Hadamard Matrix

Recently, Yu Hin Au, Nathan Lindzey, and Levent Tunçel published a preprint with various spectral bounds on the arXiv. They investigate generalizations of bounds due to Delsarte and Hoffman in the context of the Lovász-Schrijver SDP. Page 12 of that article I knew for a few more days because Nathan asked me if their bound is known. The bound is simply an example to showcase their techniques. Here I will present another method of showing the same bound. Consider the graph $ {G_\ell}$ which is defined as follows: Vertices are the elements of $ {\{ 0, 1 \}^{2\ell+1}}$ and two vertices are adjacent if they have Hamming distance $ {\ell}$ or $ {\ell+1}$, that is they differ in $ {\ell}$ or $ {\ell+1}$ positions. On page 12, they obtain the following bound:

Theorem 1 A clique of $ {G_\ell}$ has at most size $ {2\ell+2}$.

Here we will discuss equality in this bound and a small improvement for $ {\ell}$ even.

1. Equality for $ {\ell}$ odd

Yu, Nathan and Levent use a version of the ratio bound, so the proof is very nice. They also mention that the bound is tight as we can take a $ {(2\ell+2)\times (2\ell+2)}$ Hadamard matrix and remove one column. Here an example for $ {\ell=1}$. This is the corresponding Hadamard matrix:

$ \displaystyle \begin{pmatrix} 1 & 1 & 1 & 1\\ 1 & 1 & -1 & -1\\ 1 & -1 & 1 & -1\\ 1 & -1 & -1 & 1 \end{pmatrix} $

Our graph has $ {0}$s and $ {1}$s, so let’s replace $ {-1}$s by $ {0}$s and chop the last column:

$ \displaystyle \begin{pmatrix} 1 & 1 & 1\\ 1 & 1 & 0\\ 1 & 0 & 1\\ 1 & 0 & 0 \end{pmatrix} $

The rows above correspond to $ {2\ell+2 = 4}$ vertices pairwise at distance $ {1}$ or $ {2}$. As Hadamard matrices of size $ {2\ell+2}$, where $ {2\ell+2 \geq 4}$, only exist if $ {4}$ divides $ {2\ell+2}$, we have that $ {\ell}$ is odd for all examples obtained this way.

2. A Small Improvement

Now the small improvement for $ {\ell}$ even.

Theorem 2 A clique of $ {G_\ell}$, $ {\ell}$ even, has at most size $ {2\ell+1}$.

This is probably somewhere in literature, but I would like to know where (this was Nathan’s question to me). And I would also like to know if there is a construction to obtain equality in this bound. Using Hadamard matrices, but this time adding a column to them, it is easy to see that the existence of a Hadamard matrix of size $ {2\ell}$ implies the existence of a clique of size $ {2\ell}$ in $ {G_\ell}$.

So how do we prove this better bound? We use a method from an old blog post of mine here. We will first do this for $ {\ell=2}$. Let’s say that $ {A_j}$ is the adjacency matrix of the distance-$ {j}$ graph on $ {\{ 0, 1\}^5}$. That is $ {(A_j)_{xy}}$ is $ {1}$ if $ {x}$ and $ {y}$ have Hamming distance $ {j}$, and $ {0}$ otherwise. The eigenvalues of these graphs are well-known. Here, the $ {j}$th column corresponds to the eigenvalue of the $ {j}$th graph ($ {j = 0, 1, 2, 3, 4, 5}$):

$ \displaystyle P := \begin{pmatrix} 1 & 5 & 10 & 10 & 5 & 1\\ 1 & 3 & 2 & -2 & -3 & -1\\ 1 & 1 & -2 & -2 & 1 & 1\\ 1 & -1 & -2 & 2 & 1 & -1\\ 1 & -3 & 2 & 2 & -3 & 1\\ 1 & -5 & 10 & -10 & 5 & -1 \end{pmatrix}$

It is noteworthy that the rows are not random. These $ {6}$ graphs share their eigenspaces $ {V_0, V_1, \ldots, V_5}$, a common property of distance-regular graphs and, more generally, association schemes. A reason for those who want to know: The $ {A_j}$’s commute, so we can diagonalize them simultaneously. Another well-known and very nice thing about this set of graphs is that the eigenvalue matrix $ {P}$ also provides you with an explicit orthogonal projection matrix onto the eigenspace $ {V_i}$. Define the projection matrix $ {E_i}$ by $ {2^5 \cdot (E_i)_{xy} = P_{ji}}$ if $ {x}$ and $ {y}$ have Hamming distance $ {j}$. And we also know that the dimension of $ {V_i}$ is equal to $ {P_{0i}}$.

To show the theorem for $ {\ell=2}$, we look at $ {E_4}$. We do know that $ {\text{rank}(E_4) = \text{dim}(V_4) = 5}$. If $ {Y}$ is a clique of $ {G_2}$, then we also know that the submatrix $ {E’}$ of $ {E_4}$ index by $ {Y}$ is of the form $ {2^{-5} (5I + (J-I))}$. Clearly, this matrix has full rank, hence $ {|Y| = \text{rank}(E’) \leq \text{rank}(E_4)}$. Hence, $ {|Y| \leq 5}$ as claimed.

Now let’s do the same in general with $ {n=2\ell+1}$. We still have $ {2^{-n} (E_i)_{xy} = P_{ji}}$ for $ {x}$ and $ {y}$ at distance $ {j}$ and $ {\dim(V_i) = P_{0i}}$. The entries of $ {P}$, given by the Krawtchouk polynomials, are

$ \displaystyle P_{ij} = \sum_{h=0}^j (-1)^h \binom{i}{h} \binom{n-i}{j-h}. $

We only care about $ {P_{ji}}$ with $ {i=n-1}$. In this case, the formula simplifies to

$ \displaystyle P_{j,n-1} = \sum_{h=0}^{n-1} (-1)^h \binom{j}{h} \binom{n-j}{n-1-h} = (-1)^{j-1} j + (-1)^j (n-j) = (-1)^j (n-2j). $

In fact, we only case about $ {j=0,\ell,\ell+1}$. We obtain $ {P_{0,2\ell} = n}$, and $ {P_{\ell,2\ell} = (-1)^\ell = P_{\ell+1,2\ell}}$. Hence, the submatrix $ {E’}$ of $ {E_{2\ell}}$ indexed by $ {Y}$ is a multiple of $ {nI + (-1)^\ell (J-I)}$, so it has full rank if $ {\ell}$ is even. Hence, $ {|Y| = \text{rank}(E’)}$. But $ {\text{rank}(E’) \leq \text{rank}(E) = 2\ell+1}$. Therefore, $ {|Y| \leq 2\ell+1}$.

We also obtain an alternative proof for $ {|Y| \leq 2\ell+2}$ for $ {\ell}$ odd. Indeed, $ {nI – (J-I)}$ has rank $ {|Y|-1}$ if $ {|Y| = 2\ell+2}$. Hence, the bound is worse by one in this case.

3. Equality for $ {\ell}$ even

As the authors of the preprint mention, $ {G_2}$ has clique number $ {5 = 2\ell+1}$. Here is an example for equality:

11110
11001
10101
10011
01111

This is a Hadamard matrix of size $ {4}$ with one column and row added. As mentioned before, I would be curious to know if one can do this more generally.

Acknowledgements My thanks go to Nathan Lindzey for having a look at a draft of this article.

Follow the blog!