I spent the last few days in vain using several spectral arguments to bound the size of certain intersection problems. For instance what is the largest set of vectors in pairwise at Hamming distance at most (a problem solved by Kleitman, recently investigated by Huang, Klurman and Pohoata). Here the answer is and , , , , would be such an example. Or the largest set of vectors in pairwise at distance or . Here the answer is and an example is , , , , , , , . This is a problem which I recently investigated together with Hajime Tanaka, extending work by Frankl and others.
Usually, this playing around does not lead to anything. But this time …. It is actually the same. However, I did one useful thing which is the following: Generously counting, I do know five different easy spectral arguments which can be used to investigate these questions. This blog post presents these methods for the two problems mentioned above.
1. The Hypercube
Here is a picture of the -dimensional hypercube (missing a few edges, but I always feel that it is nice to have some picture in a post):
We want to show that , , , , is an example for a largest family of vertices in this graph such that all vertices in have at most distance . I guess that one can easily see this by playing around as there are only vertices, but we want to use (1) more generic methods which (2) use the spectrum of the adjacency matrix of the hypercube in some way.
Before we start, we define the following -matrices, all of them indexed by the elements of :
- is the identity matrix.
- has a at position if and have Hamming distance , and a otherwise.
- has a at position if and have Hamming distance , and a otherwise.
- Similarly, we define and : has a at position if and have Hamming distance , and a otherwise.
All of these matrices commute, so we know from our linear algebra lecture that we can diagonalize them simultanously. It turns out that the matrices have five common eigenspaces (of course individual matrices have less eigenspaces, for instance the only eigenspace of is just , but we can write the eigenspaces as sums of s). We end up with the following table where the columns are indexed by the five s, while the columns are indexed by the s:
From here we see that has the eigenvalues , , , , and . In particular, an eigenvector of in satisfies , while we have and .
We will also need the orthogonal projection onto the eigenspace . Luckily for us, the hypercubes have very special eigenspaces and we have that . I also have to mention that the dimension of (or the rank of ) is equal to .
The above is a short summary of some basic properties of so-called association schemes.
For the rest of this section let be a set of vertices of such that all vertices are pairwise at (Hamming) distance or .
1.1. Proof 1: The Inertia Bound
Recall Cauchy’s interlacing theorem:
Theorem 1 (Cauchy’s interlacing theorem) Let be an symmetric matrix with eigenvalues . Let be an principal submatrix of with eigenvalues . Then we have for all .
We consider the matrix . (Nothing is special about . There many other choices for and all the other matrices in this post, I just choose something that works for each particular argument.) Then the matrix tells us that the eigenvalues of are , , , , (ordered by the order of the s). The dimension of is and the dimension of is , so the multiplicity of is also . We conclude that has only non-negative eigenvalues.
Next we look at the principal submatrix of which is indexed by . We chose such that the submatrix indexed by is the all-zeroes matrix. Hence, the eigenvalues of are all . By Cauchy’s interlacing theorem, we have that . Hence, .
This bound is called inertia bound or Cvetkovic’s bound, see my previous post.
1.2. Proof 2: Another Multiplicity Bound
Again, we use a linear combination of matrices, but this time we use the s. Let . Notice that has rank as has rank () and has rank (). We can express as a linear combination of s: . Let be the principal submatrix of indexed by . Then . This matrix has full rank unless has size . In that case, has rank . As , we conclude that .
1.3. Proof 3: The Ratio Bound
To honor the name of my blog, a proof using the ratio bound (also called Hoffman’s bound). We will skip details here as it is a bit off-topic.
Consider the matrix . The eigenvalues of are , , , , and . The ratio bound says that
Furthermore, a more elaborate argument shows that equality occurs only if each element of has distance to vertices of and distance to the remaining vertices of . From this it is an easy puzzle to see that does not occur, so .
2. The Hypercube
Frankl investigated the maximal number of pairwise non-orthogonal vectors in . Of course these are just vectors in which have pairwise Hamming distances different to . Frankl noticed that one can reduce the problem to a different question on . For , we ask for a set in with vertices pairwise at distance or . It is easy to find such a set of size :
We will show that this is the best possible. Here is the analog of our matrix for :
Again, we will need the orthogonal projections onto the eigenspaces of . The relationship is as before, so this time we have . This time the dimension of (or the rank of ) is equal to .
2.1. Proof 4: The Ration Bound Again
First, let us mention that we can use the ratio bound again. Our is an independent set of the graph with adjacency matrix . The eigenvalues of are . If we apply the ratio bound now, then we get a terrible bound. But we are allowed to use weighted adjacency matrices! So let’s take . This is a matrix with eigenvalues . The largest eigenvalue is , the smallest is and we have vertices, so the ratio bound yields
2.2. Proof 5: Yet Another Multiplicity Bound
Now we consider the following matrix: . We can rewrite this using the ‘s as
Consider the submatrix of indexed by . As the distances , , , do not occur in , is also a submatrix of
which is the identity matrix modulo . Hence, is a submatrix of of rank . But we know (as in Proof 2) that has at most rank . Hence, .
2.3. Proof 6: One Last Multiplicity Bound
This proof does not really count as it will only show that . I included it because it works nicely in other cases.
If we limit ourselves to elements of even weight, then one can show that the -rank of is (if we do not restrict ourselves to even weight codewords, then the -rank is ). I verified this by computer, but I am sure that there are more clever ways of doing so. Now let the submatrix of indexed by . Then
It is easy to see that the -rank of is if divides and otherwise (this is trivial, but you can cite Theorem BLA in BLA if you want to cite something for it). As the -rank of is at most the -rank of , we conclude that .
3. Concluding Remarks
Let me conclude with some remarks. First of all I want to mention that this took me longer to write than I thought. There are several reasons for this, but one of the main ones is that I actually wanted to make sure that none of the stated arguments could be used for the stated problems and general . Except for Proof 6 (here I do not know the -ranks in general) I am sure of this.
Proof 1 generalizes, see the paper by Huang, Klurman and Pohoata. Proof 2 generalizes as well, see this paper by Frankl and this paper by Hajime Tanaka and me, but not to all . It fails the first time at . I also used Proof 6 before in joint work with Peter Sin and Qing Xiang. But that might deserve its own post as it uses some additional representation theory trick and lives in a more complicated graph related polar spaces.