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 which is defined as follows: Vertices are the elements of and two vertices are adjacent if they have Hamming distance or , that is they differ in or positions. On page 12, they obtain the following bound:

Theorem 1 A clique of has at most size .

Here we will discuss equality in this bound and a small improvement for even.

1. Equality for 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 Hadamard matrix and remove one column. Here an example for . This is the corresponding Hadamard matrix:

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

The rows above correspond to vertices pairwise at distance or . As Hadamard matrices of size , where , only exist if divides , we have that is odd for all examples obtained this way.

2. A Small Improvement

Now the small improvement for even.

Theorem 2 A clique of , even, has at most size .

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 implies the existence of a clique of size in .

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 . Let’s say that is the adjacency matrix of the distance- graph on . That is is if and have Hamming distance , and otherwise. The eigenvalues of these graphs are well-known. Here, the th column corresponds to the eigenvalue of the th graph ():

It is noteworthy that the rows are not random. These graphs share their eigenspaces , a common property of distance-regular graphs and, more generally, association schemes. A reason for those who want to know: The ‘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 also provides you with an explicit orthogonal projection matrix onto the eigenspace . Define the projection matrix by if and have Hamming distance . And we also know that the dimension of is equal to .

To show the theorem for , we look at . We do know that . If is a clique of , then we also know that the submatrix of index by is of the form . Clearly, this matrix has full rank, hence . Hence, as claimed.

Now let’s do the same in general with . We still have for and at distance and . The entries of , given by the Krawtchouk polynomials, are

We only care about with . In this case, the formula simplifies to

In fact, we only case about . We obtain , and . Hence, the submatrix of indexed by is a multiple of , so it has full rank if is even. Hence, . But . Therefore, .

We also obtain an alternative proof for for odd. Indeed, has rank if . Hence, the bound is worse by one in this case.

3. Equality for even

As the authors of the preprint mention, has clique number . Here is an example for equality:

11110
11001
10101
10011
01111

This is a Hadamard matrix of size 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.

Advertisement