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 \left(\begin{array}{cccc}1& 1& 1& 1\\ 1& 1& -1& -1\\ 1& -1& 1& -1\\ 1& -1& -1& 1\end{array}\right)}$

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

${\displaystyle \left(\begin{array}{ccc}1& 1& 1\\ 1& 1& 0\\ 1& 0& 1\\ 1& 0& 0\end{array}\right)}$

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\ge 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:=\left(\begin{array}{cccccc}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{array}\right)}$

It is noteworthy that the rows are not random. These $6$ graphs share their eigenspaces $V_0,V_1,\dots ,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^{\prime }$ 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^{\prime })\le \text{rank}(E_4)$. Hence, $|Y|\le 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(\genfrac{}{}{0ex}{}{i}{h})(\genfrac{}{}{0ex}{}{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(\genfrac{}{}{0ex}{}{j}{h})(\genfrac{}{}{0ex}{}{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^{\prime }$ 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^{\prime })$. But $\text{rank}(E^{\prime })\le \text{rank}(E)=2\ell +1$. Therefore, $|Y|\le 2\ell +1$.

We also obtain an alternative proof for $|Y|\le 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!