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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s