6a. Basic obstructions

[math] \newcommand{\mathds}{\mathbb}[/math]

This article was automatically generated from a tex file and may contain conversion errors. If permitted, you may login and edit this article to improve the conversion.

Many interesting examples of complex Hadamard matrices [math]H\in M_N(\mathbb T)[/math], including the real ones [math]H\in M_N(\pm1)[/math], have as entries roots of unity, of finite order. We discuss here this case, and more generally the “regular” case, where the combinatorics of the scalar products between the rows comes from vanishing sums of roots of unity. Let us begin with the following definition, going back to the work of Butson :

Definition

An Hadamard matrix is called of Butson type if its entries are roots of unity of finite order. The Butson class [math]H_N(l)[/math] consists of the Hadamard matrices

[[math]] H\in M_N(\mathbb Z_l) [[/math]]

where [math]\mathbb Z_l[/math] is the group of the [math]l[/math]-th roots of unity. The level of a Butson matrix [math]H\in M_N(\mathbb T)[/math] is the smallest integer [math]l\in\mathbb N[/math] such that [math]H\in H_N(l)[/math].

As basic examples, we have the real Hadamard matrices, which form the Butson class [math]H_N(2)[/math]. The Fourier matrices are Butson matrices as well, because we have [math]F_N\in H_N(N)[/math], and more generally [math]F_G\in H_N(l)[/math], with [math]N=|G|[/math], and with [math]l\in\mathbb N[/math] being the smallest common order of the elements of [math]G[/math]. There are many other examples, as for instance most of those at [math]N=6[/math] discussed in chapter 5, at 1 values of the various parameters [math]q,r,s[/math] there.

Generally speaking, the main question regarding the Butson matrices is that of understanding when [math]H_N(l)\neq 0[/math], via a theorem providing obstructions, and then a result or conjecture stating that these obstructions are the only ones. Let us begin with:

Proposition (Sylvester obstruction)

The following holds,

[[math]] H_N(2)\neq\emptyset\implies N\in\{2\}\cup 4\mathbb N [[/math]]

due to the orthogonality of the first [math]3[/math] rows.

Show Proof

This is something that we know from chapter 1, with the obstruction, going back to Sylvester's paper , being explained there.

■

The above obstruction is fully satisfactory, because according to the HC, its converse should hold. Thus, we are fully done with the case [math]l=2[/math]. Our purpose now will be that of finding analogous statements at [math]l\geq3[/math], theorem plus conjecture. At very small values of [math]l[/math] this is certainly possible, and in what regards the needed obstructions, we can get away with the following simple fact, from Butson and Winterhof :

Proposition

For a prime power [math]l=p^a[/math], the vanishing sums of [math]l[/math]-th roots of unity

[[math]] \lambda_1+\ldots+\lambda_N=0\quad,\quad\lambda_i\in\mathbb Z_l [[/math]]

appear as formal sums of rotated full sums of [math]p[/math]-th roots of unity.

Show Proof

This is something elementary, coming from basic number theory. Consider indeed the full sum of [math]p[/math]-th roots of unity, taken in a formal sense:

[[math]] S=\sum_{k=1}^p(e^{2\pi i/p})^k [[/math]]

Let also [math]w=e^{2\pi i/l}[/math], and for [math]r\in\{1,2,\ldots ,l/p\}[/math] let us denote by [math]S_p^r=w^r\cdot S[/math] the above formal sum of roots of unity, rotated by [math]w^r[/math]:

[[math]] S_p^r=\sum_{k=1}^pw^r(e^{2\pi i/p})^k [[/math]]

We must show that any vanishing sum of [math]l[/math]-th roots of unity appears as a sum of such quantities [math]S_p^r[/math]. For this purpose, consider the following map, which assigns to the abstract elements of the group ring [math]\mathbb Z[\mathbb Z_l][/math] their precise numeric values, inside [math]\mathbb Z(w)\subset\mathbb C[/math]:

[[math]] \Phi:\mathbb Z[\mathbb Z_l]\to\mathbb Z(w) [[/math]]

Our claim is that the elements [math]\{S_p^r\}[/math] form a basis of the vector space [math]\ker\Phi[/math]. In order to prove this claim, observe first that we have:

[[math]] S_p^r\in\ker\Phi [[/math]]

Also, the elements [math]S_p^r[/math] are linearly independent, because the support of [math]S_p^r[/math] contains a unique element of the subset [math]\{1,2,\ldots ,p^{a-1}\}\subset\mathbb Z_l[/math], namely the element [math]r\in\mathbb Z_l[/math], so all the coefficients of a vanishing linear combination of such sums [math]S_p^r[/math] must vanish. Thus, we are left with proving that [math]\ker\Phi[/math] is spanned by the elements [math]\{S_p^r\}[/math]. For this purpose, let us recall the well-known fact that the minimal polynomial of [math]w[/math] is as follows:

[[math]] \frac{X^{p^{a}}-1}{X^{{p^{a-1}}}-1}=1+X^{p^{a-1}}+X^{2p^{a-1}}+\ldots+X^{(p-1)p^{a-1}} [[/math]]

We conclude that the dimension of [math]\ker\Phi[/math] is given by:

[[math]] \dim(\ker\Phi) =p^a-(p^a-p^{a-1}) =p^{a-1} [[/math]]

Now since this is exactly the number of the sums [math]S_p^r[/math], this finishes the proof of our claim. Thus, any vanishing sum of [math]l[/math]-th roots of unity must be of the form [math]\sum\pm S_p^r[/math], and the above support considerations show the coefficients must be positive, as desired.

■

We can now formulate a result in the spirit of Proposition 6.2, as follows:

Proposition (Butson obstruction)

The following holds,

[[math]] H_N(p^a)\neq\emptyset\implies N\in p\mathbb N [[/math]]

due to the orthogonality of the first [math]2[/math] rows.

Show Proof

This follows indeed from Proposition 6.3, because the scalar product between the first 2 rows of our matrix is a vanishing sum of [math]l[/math]-th roots of unity.

■

WIth these obstructions in hand, we can discuss the case [math]l\leq5[/math], as follows:

Theorem

We have the following results,

• [math]H_N(2)\neq\emptyset\implies N\in\{2\}\cup 4\mathbb N[/math],
• [math]H_N(3)\neq\emptyset\implies N\in3\mathbb N[/math],
• [math]H_N(4)\neq\emptyset\implies N\in2\mathbb N[/math],
• [math]H_N(5)\neq\emptyset\implies N\in5\mathbb N[/math],

with in cases [math](1,3)[/math], a conjecture stating that the converse should hold as well.

Show Proof

In this statement (1) is the Sylvester obstruction, and (2,3,4) are particular cases of the Butson obstruction. As for the last assertion, which is of course something rather informal, but which is important for our purposes, the situation is as follows:

(1) At [math]l=2[/math], as already mentioned, we have the Hadamard Conjecture, which comes with solid evidence, as explained in chapter 1 above.

(2) At [math]l=4[/math] we have an old conjecture, dealing with complex Hadamard matrices over [math]\{\pm1,\pm i\}[/math], going back to the work of Turyn in , and called Turyn Conjecture.

■

At [math]l=3[/math] things are complicated, due to the following result of de Launey :

Proposition (de Launey obstruction)

The following holds,

[[math]] H_N(l)\neq\emptyset\implies\exists\,d\in\mathbb Z[e^{2\pi i/l}],\,|d|^2=N^N [[/math]]

due to the orthogonality of all [math]N[/math] rows. In particular, we have

[[math]] 5|N\implies H_N(6)=\emptyset [[/math]]

so in particular [math]H_{15}(3)=\emptyset[/math], showing that the Butson obstruction is too weak at [math]l=3[/math].

Show Proof

The obstruction follows from the unitarity condition [math]HH^*=N[/math] for the complex Hadamard matrices, by applying the determinant, which gives:

[[math]] |{\rm det}(H)|^2=N^N [[/math]]

Regarding the second assertion, let [math]w=e^{2\pi i/3}[/math], and assume that [math]d=a+bw+cw^2[/math] with [math]a,b,c\in\mathbb Z[/math] satisfies [math]|d|^2=0(5)[/math]. We have the following computation:

[[math]] \begin{eqnarray*} |d|^2 &=&(a+bw+cw^2)(a+bw^2+cw)\\ &=&a^2+b^2+c^2-ab-bc-ac\\ &=&\frac{1}{2}[(a-b)^2+(b-c)^2+(c-a)^2] \end{eqnarray*} [[/math]]

Thus our condition [math]|d|^2=0(5)[/math] leads to the following system, modulo 5:

[[math]] x+y+z=0 [[/math]]

[[math]] x^2+y^2+z^2=0 [[/math]]

But this system has no solutions. Indeed, let us look at [math]x^2+y^2+z^2=0[/math]:

(1) If this equality appears as [math]0+0+0=0[/math] we can divide [math]x,y,z[/math] by [math]5[/math] and redo the computation.

(2) Otherwise, this equality can only appear as [math]0+1+(-1)=0[/math].

Thus, modulo permutations, we must have [math]x=0,y=\pm1,z=\pm2[/math], which contradicts [math]x+y+z=0[/math]. Finally, the last assertion follows from [math]H_{15}(3)\subset H_{15}(6)=\emptyset[/math].

■

At [math]l=5[/math] now, things are a bit unclear, with the converse of Theorem 6.5 (4) being something viable, at the conjectural level, at least to our knowledge. At [math]l=6[/math], however, the situation becomes again complicated, as follows:

Proposition (Haagerup obstruction)

The following holds, due to Haagerup's [math]N=5[/math] classification result, involving the orthogonality of all [math]5[/math] rows of the matrix:

[[math]] H_5(l)\neq\emptyset\implies 5|l [[/math]]

In particular we have [math]H_5(6)=\emptyset[/math], which follows by the way from the de Launey obstruction as well, in contrast with the fact that we generally have [math]H_N(6)\neq\emptyset[/math].

Show Proof

In this statement the obstruction [math]H_5(l)=\emptyset\implies 5|l[/math] comes indeed from Haagerup's classification result in , explained in chapter 5. As for the last assertion, this is something informal, the situation at small values of [math]N[/math] being as follows:

-- At [math]N=2,3,4[/math] we have the matrices [math]F_2,F_3,W_4[/math].

-- At [math]N=6,7,8,9[/math] we have the matrices [math]F_6,P_7^1,W_8,F_3\otimes F_3[/math].

-- At [math]N=10[/math] we have the following matrix, found in by using a computer, and written in logarithmic form, with [math]k[/math] standing for [math]e^{k\pi i/3}[/math]:

[[math]] X^6_{10}= \left(\begin{array}{cccccccccccccc} 0&0&0&0&0&0&0&0&0&0\\ 0&4&1&5&3&1&3&3&5&1\\ 0&1&2&3&5&5&1&3&5&3\\ 0&5&3&2&1&5&3&5&3&1\\ 0&3&5&1&4&1&1&5&3&3\\ 0&3&3&3&3&3&0&0&0&0\\ 0&1&1&5&3&4&3&0&2&4\\ 0&1&5&3&5&2&4&3&2&0\\ 0&5&3&5&1&2&0&2&3&4\\ 0&3&5&1&1&4&4&2&0&3 \end{array}\right) [[/math]]

We refer to for more details on this topic.

■

All this is not good news. Indeed, there is no hope of conjecturally solving our [math]H_N(l)\neq\emptyset[/math] problem in general, because this would have to take into account, and in a simple and conceptual way, both the subtle arithmetic consequences of the de Launey obstruction, and the Haagerup classification result at [math]N=5[/math], and this does not seem feasible.

General references

Banica, Teo (2024). "Invitation to Hadamard matrices". arXiv:1910.06911 [math.CO].