Circulant matrices

[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.

9a. Cyclic roots

After some 200 pages of analysis, time to do some analysis. In this third part of the present book we discuss a number of more specialized analytic topics, in relation with the following questions, regarding the complex Hadamard matrices:

-- Circulant Hadamard matrices. We will discuss here Björck's cyclic root formalism , the Butson matrix analogues of the CHC, the Haagerup counting result in , and, following , an analytic approach to the CHC, using the 4-norm.

-- Bistochastic Hadamard matrices. These matrices, covering all the circulant ones, and very interesting objects, due to a result of Idel-Wolf , stating that any unitary matrix, and so any complex Hadamard matrix, can be put in bistochastic form.

-- The glow of Hadamard matrices. This is another interesting theme, related on one hand to the glow computations from the real case, that we did in chapter 1, motivated by the Gale-Berlekamp game, and on the other hand, by the Idel-Wolf theorem.

-- Almost Hadamard matrices. The study here, from , initially paralleling the study from the real case, from chapter 3, leads to an unexpected and potentially far-reaching conjecture, stating that “being complex Hadamard is a local property”.

All in all, many things to be discussed, and we should mention too that all this will be rather research-grade material, quite recent, and with more conjectures than theorems, and with all this waiting for some enthusiastic young people. Like you.

Getting started now, we will first discuss an important class of complex Hadamard matrices, namely the circulant ones. There has been a lot of work here, starting with the Circulant Hadamard Conjecture (CHC) in the real case, and with many results in the complex case as well. We will present here the main techniques in dealing with such matrices. It is convenient to introduce the circulant matrices as follows:

Definition

A complex matrix [math]H\in M_N(\mathbb C)[/math] is called circulant when we have

[[math]] H_{ij}=\gamma_{j-i} [[/math]]

for some [math]\gamma\in\mathbb C^N[/math], with the matrix indices [math]i,j\in \{0,1,\ldots,N-1\}[/math] taken modulo [math]N[/math].

Here the index convention is quite standard, as for the Fourier matrices [math]F_N[/math], and with this coming from some Fourier analysis considerations, that we will get into later on. In practice now, the fact that a matrix is circulant means that it has the following pattern, with the entries in the first row “circulating” downwards and to the right:

[[math]] H=\begin{pmatrix} a&b&c&d\\ d&a&b&c\\ c&d&a&b\\ b&c&d&a \end{pmatrix} [[/math]]

As a basic example of a circulant Hadamard matrix, in the real case, we have the matrix [math]K_4[/math]. The circulant Hadamard conjecture states that this matrix is, up to equivalence, the only circulant Hadamard matrix [math]H\in M_N(\pm1)[/math], regardless of the value of [math]N\in\mathbb N[/math]:

\begin{conjecture}[Circulant Hadamard Conjecture (CHC)] The only circulant real Hadamard matrices [math]H\in M_N(\pm1)[/math] are the matrix

[[math]] K_4=\begin{pmatrix}-1&1&1&1\\1&-1&1&1\\1&1&-1&1\\1&1&1&-1\end{pmatrix} [[/math]]

and its Hadamard conjugates, and this regardless of the value of [math]N\in\mathbb N[/math]. \end{conjecture} As explained in chapter 1, this conjecture is something of different nature from the Hadamard Conjecture (HC). Indeed, while the HC might look like something simple, at the first glance, working a bit on it quickly reveals that this is certainly something quite complicated, or even worse, that this might be one of these “black holes” in the mathematical landscape, including too the Riemann Hypothesis, the Jacobian Conjecture, the Collatz Problem and so on, all questions having little to do with modern mathematics as we know it, since Newton and others, and better to be avoided.

Regarding the CHC, however, it is quite unclear where the difficulty comes from. Indeed, if we denote by [math]S\subset\{1,\ldots,N\}[/math] the set of positions of the [math]-1[/math] entries of the first row vector [math]\gamma\in(\pm1)^N[/math], the Hadamard matrix condition reads, for any [math]k\neq0[/math]:

[[math]] |S\cap(S+k)|=|S|-N/4 [[/math]]

Thus, the CHC simply states that at [math]N\neq 4[/math], such a set [math]S[/math] cannot exist. Let us record here this latter statement, originally due to Ryser :

\begin{conjecture}[Ryser Conjecture] Given an integer [math]N \gt 4[/math], there is no set

[[math]] S\subset\{1,\ldots,N\} [[/math]]

satisfying [math]|S\cap(S+k)|=|S|-N/4[/math] for any [math]k\neq 0[/math], taken modulo [math]N[/math]. \end{conjecture} And prove this if you can. This question is 60 years old, and many competent people have looked at it, with basically 0 serious advances. So, most likely, what we have here is the same type of annoying question as the HC, Riemann, Collatz and so on.

Erdős famously said about Collatz that “mathematics is not ready for such things”. But, will it ever be ready? Probably not. Never. It is always good to remember here that modern mathematics as we know it was developed by Newton and others, with inspiration from classical mechanics. And so, want it or not, mathematics as we know it “is” classical mechanics. And this might explain why the HC, CHC, Riemann, Collatz and so on are so inaccessible, these are probably simply questions which are orthogonal to classical mechanics, and so are orthogonal to mathematics as we know it too.

You might say then, why not trying mathematics inspired from some other physics, like quantum mechanics. Well, the problem is that quantum mechanics, or at least quantum mechanics as we know it, is in fact not that far from classical mechanics. Same types of beasts, like functions, derivatives, integrals and so on, all good old stuff going back to Newton, doing most of the mathematics that we know, in the quantum world.

But then you would say why not sending to trash all modern mathematics, and developing some new, original mathematics, especially tailored for problems like the HC, CHC, Riemann, Collatz and so on. Well, people have tried, for instance with design theory for the HC, CHC, and this does not work either. And why? No one really knows the answer here, but this is probably because there is no physics that you can rely upon, and intuition in general, for making that original mathematics of yours strong and reliable.

Looks like we are in a kind of vicious circle, with all these questions. Math needs physics, and so, want it or not, the physics surrounding us ultimately dictates what's doable and what's not, mathematically speaking. As a conjecture, in some alien world where the physics is different, the HC, CHC, Riemann, Collatz and so on might be all trivial. But that little green men who know how to solve all these questions might, on the other hand, have things like partial integration as longstanding, open problems.

And let us end this discussion with a famous quote by Dirac, “shut up and compute”. This is what he used to say to students asking too many questions about quantum mechanics. Computation is our only tool, so let's compute some more. After all, there is still a chance that the HC, CHC might be related to mechanics. And so, be doable.

Back to work now, we will in fact not start with computations for the CHC, which looks quite scary. Our first purpose will be that of showing that the CHC dissapears in the complex case, where we have examples at any [math]N\in\mathbb N[/math]. As a first result, we have:

Proposition

The following are circulant and symmetric Hadamard matrices,

[[math]] F_2'=\begin{pmatrix}i&1\\1&i\end{pmatrix}\qquad,\qquad F_3'=\begin{pmatrix}w&1&1\\1&w&1\\1&1&w\end{pmatrix} [[/math]]

[[math]] F_4''=\begin{pmatrix}-1&\nu&1&\nu\\\nu&-1&\nu&1\\1&\nu&-1&\nu\\ \nu&1&\nu&-1\end{pmatrix} [[/math]]

where [math]w=e^{2\pi i/3},\nu=e^{\pi i/4}[/math], equivalent to the Fourier matrices [math]F_2,F_3,F_4[/math].

Show Proof

The orthogonality between rows being clear, we have here complex Hadamard matrices. The fact that we have an equivalence [math]F_2\sim F_2'[/math] follows from:

[[math]] \begin{pmatrix}1&1\\1&-1\end{pmatrix} \sim\begin{pmatrix}i&i\\1&-1\end{pmatrix} \sim\begin{pmatrix}i&1\\1&i\end{pmatrix} [[/math]]

At [math]N=3[/math] now, the equivalence [math]F_3\sim F_3'[/math] can be constructed as follows:

[[math]] \begin{pmatrix}1&1&1\\1&w&w^2\\1&w^2&w\end{pmatrix} \sim\begin{pmatrix}1&1&w\\1&w&1\\w&1&1\end{pmatrix} \sim\begin{pmatrix}w&1&1\\1&w&1\\1&1&w\end{pmatrix} [[/math]]

As for the case [math]N=4[/math], here the equivalence [math]F_4\sim F_4''[/math] can be constructed as follows, where we use the logarithmic notation [math][k]_s=e^{2\pi ki/s}[/math], with respect to [math]s=8[/math]:

[[math]] \begin{bmatrix}0&0&0&0\\0&2&4&6\\0&4&0&4\\0&6&4&2\end{bmatrix}_8 \sim\begin{bmatrix}0&1&4&1\\1&4&1&0\\4&1&0&1\\1&0&1&4\end{bmatrix}_8 \sim\begin{bmatrix}4&1&0&1\\1&4&1&0\\0&1&4&1\\1&0&1&4\end{bmatrix}_8 [[/math]]

Thus, the Fourier matrices [math]F_2,F_3,F_4[/math] can be put indeed in circulant form.

■

We will explain later the reasons for denoting the above matrix [math]F_4''[/math], instead of [math]F_4'[/math], the idea being that [math]F_4'[/math], not introduced yet, will be a matrix belonging to a certain series. Getting back now to the real circulant matrix [math]K_4[/math], this is equivalent to the Fourier matrix [math]F_G=F_2\otimes F_2[/math] of the Klein group [math]G=\mathbb Z_2\times\mathbb Z_2[/math], as shown by:

[[math]] \begin{pmatrix}-1&1&1&1\\1&-1&1&1\\1&1&-1&1\\1&1&1&-1\end{pmatrix} \sim\begin{pmatrix} 1&1&1&-1\\ 1&-1&1&1\\ 1&1&-1&1\\ -1&1&1&1 \end{pmatrix} \sim\begin{pmatrix} 1&1&1&1\\ 1&-1&1&-1\\ 1&1&-1&-1\\ 1&-1&-1&1 \end{pmatrix} [[/math]]

In fact, we have the following construction of circulant and symmetric Hadamard matrices at [math]N=4[/math], which involves an extra parameter [math]q\in\mathbb T[/math]:

Proposition

The following circulant and symmetric matrix is Hadamard,

[[math]] K_4^q=\begin{pmatrix}-1&q&1&q\\q&-1&q&1\\1&q&-1&q\\q&1&q&-1\end{pmatrix} [[/math]]

for any [math]q\in\mathbb T[/math]. At [math]q=1,e^{\pi i/4}[/math] recover respectively the matrices [math]K_4,F_4''[/math].

Show Proof

The rows of the above matrix are pairwise orthogonal for any [math]q\in\mathbb C[/math], and so at [math]q\in\mathbb T[/math] we obtain an Hadamard matrix. As for the last assertion, this is clear.

■

As a first conclusion, coming from the above considerations, we have:

Theorem

The complex Hadamard matrices of order [math]N=2,3,4,5[/math], namely

[[math]] F_2,F_3,F_4^s,F_5 [[/math]]

can be put, up to equivalence, in circulant and symmetric form.

Show Proof

As explained in chapter 5, the complex Hadamard matrices at [math]N=2,3,4,5[/math] are, up to equivalence, those in the statement, with the classification being something elementary at [math]N=2,3,4[/math], and with the [math]N=5[/math] result being due to Haagerup .

(1) At [math]N=2,3[/math] the problem is solved by Proposition 9.4.

(2) At [math]N=4[/math] now, our claim is that, with [math]s=q^{-2}[/math], we have:

[[math]] K_4^q\sim F_4^s [[/math]]

Indeed, by multiplying the rows and columns of [math]K_4^q[/math] by suitable scalars, we have:

[[math]] K_4^q =\begin{pmatrix}-1&q&1&q\\q&-1&q&1\\1&q&-1&q\\q&1&q&-1\end{pmatrix}\sim\begin{pmatrix} 1&-q&-1&-q\\ 1&-\bar{q}&1&\bar{q}\\ 1&q&-1&q\\ 1&\bar{q}&1&-\bar{q}\end{pmatrix} \sim\begin{pmatrix} 1&1&1&1\\ 1&s&-1&-s\\ 1&-1&1&-1\\ 1&-s&-1&s\end{pmatrix} [[/math]]

On the other hand, by permuting the second and third rows of [math]F_4^s[/math], we obtain:

[[math]] F_4^s =\begin{pmatrix} 1&1&1&1\\ 1&-1&1&-1\\ 1&s&-1&-s\\ 1&-s&-1&s \end{pmatrix} \sim \begin{pmatrix} 1&1&1&1\\ 1&s&-1&-s\\ 1&-1&1&-1\\ 1&-s&-1&s\end{pmatrix} [[/math]]

Thus these matrices are equivalent, and the result follows from Proposition 9.5.

(3) At [math]N=5[/math] now, the matrix that we are looking for is as follows, with [math]w=e^{2\pi i/5}[/math]:

[[math]] F_5'=\begin{pmatrix} w^2&1&w^4&w^4&1\\ 1&w^2&1&w^4&w^4\\ w^4&1&w^2&1&w^4\\ w^4&w^4&1&w^2&1\\ 1&w^4&w^4&1&w^2 \end{pmatrix} [[/math]]

It is indeed clear that this matrix is circulant, symmetric, and complex Hadamard, and the fact that we have [math]F_5\sim F_5'[/math] follows either directly, or by using Haagerup .

■

Summarizing, many interesting examples of complex Hadamard matrices are circulant. This is in stark contrast with the real case, where the CHC, discussed above, states that the only circulant real matrices should be those appearing at [math]N=4[/math]. Let us prove now, as a generalization of all this, that any Fourier matrix [math]F_N[/math] can be put in circulant and symmetric form. We use Björck's cyclic root formalism , which is as follows:

Theorem

Assume that a matrix [math]H\in M_N(\mathbb T)[/math] is circulant, [math]H_{ij}=\gamma_{j-i}[/math]. Then [math]H[/math] is a complex Hadamard matrix precisely when the vector

[[math]] z=(z_0,z_1,\ldots,z_{N-1}) [[/math]]

given by [math]z_i=\gamma_i/\gamma_{i-1}[/math] satisfies the following equations:

[[math]] \begin{eqnarray*} z_0+z_1+\ldots+z_{N-1}&=&0\\ z_0z_1+z_1z_2+\ldots+z_{N-1}z_0&=&0\\ \vdots\\ z_0z_1\ldots z_{N-2}+\ldots+z_{N-1}z_0\ldots z_{N-3}&=&0\\ z_0z_1\ldots z_{N-1}&=&1 \end{eqnarray*} [[/math]]

If so is the case, we say that [math]z=(z_0,\ldots,z_{N-1})[/math] is a cyclic [math]N[/math]-root.

Show Proof

Assume that a matrix of type [math]H\in M_N(\mathbb T)[/math] is circulant, [math]H_{ij}=\gamma_{j-i}[/math], and set [math]z_i=\gamma_i/\gamma_{i-1}[/math], as in the statement. Observe that we have:

[[math]] z_0z_1\ldots z_{N-1}=1 [[/math]]

Up to a multiplication by a scalar [math]w\in\mathbb T[/math], our matrix is then as follows:

[[math]] H=\begin{pmatrix} z_0&z_0z_1&z_0z_1z_2&\ldots\ldots&z_0\ldots z_{N-1}\\ z_0\ldots z_{N-1}&z_0&z_0z_1&\ldots\ldots&z_0\ldots z_{N-2}\\ z_0\ldots z_{N-2}&z_0\ldots z_{N-1}&z_0&\ldots\ldots&z_0\ldots z_{N-3}\\ \vdots&\vdots&\vdots&&\vdots\\ z_0z_1&z_0z_1z_2&z_0z_1z_2z_3&\ldots\ldots&z_0 \end{pmatrix} [[/math]]

Since this matrix is circulant, it is Hadamard precisely when the first row [math]R_0[/math] is orthogonal to the other rows [math]R_1,\ldots,R_{N-1}[/math]. And the equations here are as follows:

[math](R_0\perp R_1)[/math]. Here the orthogonality condition is as follows:

[[math]] \overline{z_1\ldots z_{N-1}}+z_1+z_2+\ldots+z_{N-1}=0 [[/math]]

Now by using [math]z_0z_1\ldots z_{N-1}=1[/math], this is the 1st equation for cyclic roots, namely:

[[math]] z_0+z_1+z_2+\ldots+z_{N-1}=0 [[/math]]

[math](R_0\perp R_2)[/math]. Here the orthogonality condition is as follows:

[[math]] \overline{z_1\ldots z_{N-2}}+\overline{z_2\ldots z_{N-1}}+z_1z_2+\ldots+z_{N-2}z_{N-1}=0 [[/math]]

By using again [math]z_0z_1\ldots z_{N-1}=1[/math], this is the 2nd equation for cyclic roots, namely:

[[math]] z_{N-1}z_0+z_0z_1+z_1z_2+\ldots+z_{N-2}z_{N-1}=0 [[/math]]

\ \ \ \ [math]\vdots[/math]

[math](R_0\perp R_{N-1})[/math]. Here the orthogonality condition is as follows:

[[math]] \overline{z}_1+\overline{z}_2+\overline{z}_3+\ldots+z_1\ldots z_{N-1}=0 [[/math]]

And again by using [math]z_0z_1\ldots z_{N-1}=1[/math], this is the last equation for cyclic roots, namely:

[[math]] z_2\ldots z_{N-1}z_0+z_3\ldots z_{N-1}z_0z_1+z_4\ldots z_{N-1}z_0z_1z_2+\ldots+z_1\ldots z_{N-1}=0 [[/math]]

Thus, we are led to the conclusion in the statement.

■

The above manipulation might look like something very simple, but in practice this considerably simplifies things, and leads to non-trivial results. Technically speaking now, observe that, up to a multiplication by a scalar [math]w\in\mathbb T[/math], the first row vector [math]\gamma=(\gamma_0,\ldots,\gamma_{N-1})[/math] of the matrix [math]H\in M_N(\mathbb T)[/math] constructed in Theorem 9.7 is as follows:

[[math]] \gamma=(z_0,z_0z_1,z_0z_1z_2,\ldots\ldots,z_0z_1\ldots z_{N-1}) [[/math]]

We will use this observation several times, in what follows. Now back to the Fourier matrices, we have the following result:

Theorem

Given [math]N\in\mathbb N[/math], construct the following complex numbers:

[[math]] \nu=e^{\pi i/N}\quad,\quad q=\nu^{N-1}\quad,\quad w=\nu^2 [[/math]]

We have then a cyclic [math]N[/math]-root as follows, in the above sense,

[[math]] (q,qw,qw^2,\ldots,qw^{N-1}) [[/math]]

and the corresponding complex Hadamard matrix [math]F_N'[/math] is circulant and symmetric, and equivalent to the Fourier matrix [math]F_N[/math].

Show Proof

Given two numbers [math]q,w\in\mathbb T[/math], let us find out when [math](q,qw,qw^2,\ldots,qw^{N-1})[/math] is a cyclic root. We have two conditions to be verified, as follows:

(1) In order for the [math]=0[/math] equations in Theorem 9.7 to be satisfied, the value of [math]q[/math] is irrelevant, and [math]w[/math] must be a primitive [math]N[/math]-root of unity.

(2) As for the [math]=1[/math] equation in Theorem 9.7, this states in our case that we must have:

[[math]] q^Nw^{\frac{N(N-1)}{2}}=1 [[/math]]

We conclude from this that we must have:

[[math]] q^N=(-1)^{N-1} [[/math]]

Thus, with the values of [math]q,w\in\mathbb T[/math] in the statement, we have indeed a cyclic [math]N[/math]-root. Now construct [math]H_{ij}=\gamma_{j-i}[/math] as in Theorem 9.7. We have:

[[math]] \begin{eqnarray*} \gamma_k=\gamma_{-k} &\iff&q^{k+1}w^{\frac{k(k+1)}{2}}=q^{-k+1}w^{\frac{k(k-1)}{2}}\\ &\iff&q^{2k}w^k=1\\ &\iff&q^2=w^{-1} \end{eqnarray*} [[/math]]

But this latter condition holds indeed, because we have:

[[math]] q^2 =\nu^{2N-2} =\nu^{-2} =w^{-1} [[/math]]

We conclude that our circulant matrix [math]H[/math] is symmetric as well, as claimed. It remains to construct an equivalence [math]H\sim F_N[/math]. In order to do this, observe that, due to our conventions [math]q=\nu^{N-1},w=\nu^2[/math], the first row vector of [math]H[/math] is given by:

[[math]] \begin{eqnarray*} \gamma_k &=&q^{k+1}w^{\frac{k(k+1)}{2}}\\ &=&\nu^{(N-1)(k+1)}\nu^{k(k+1)}\\ &=&\nu^{(N+k-1)(k+1)} \end{eqnarray*} [[/math]]

Thus, the entries of [math]H[/math] are given by the following formula:

[[math]] \begin{eqnarray*} H_{-i,j} &=&H_{0,i+j}\\ &=&\nu^{(N+i+j-1)(i+j+1)}\\ &=&\nu^{i^2+j^2+2ij+Ni+Nj+N-1}\\ &=&\nu^{N-1}\cdot\nu^{i^2+Ni}\cdot\nu^{j^2+Nj}\cdot\nu^{2ij} \end{eqnarray*} [[/math]]

With this formula in hand, we can now finish the proof. Indeed, this shows that the matrix [math]H=(H_{ij})[/math] is equivalent to the following matrix:

[[math]] H'=(H_{-i,j}) [[/math]]

Now regarding this latter matrix [math]H'[/math], observe that in the above formula, the factors [math]\nu^{N-1}[/math], [math]\nu^{i^2+Ni}[/math], [math]\nu^{j^2+Nj}[/math] correspond respectively to a global multiplication by a scalar, and to row and column multiplications by scalars. Thus this matrix [math]H'[/math] is equivalent to the matrix [math]H''[/math] obtained from it by deleting these factors. But this latter matrix is:

[[math]] H''_{ij}=\nu^{2ij}\quad,\quad \nu=e^{\pi i/N} [[/math]]

Since this is precisely the Fourier matrix [math]F_N[/math], we are done.

■

As an illustration, let us work out the cases [math]N=2,3,4,5[/math]. We have here:

Proposition

The matrices [math]F_N'[/math] are as follows:

• At [math]N=2,3[/math] we obtain the old matrices [math]F_2',F_3'[/math].
• At [math]N=4[/math] we obtain the following matrix, with [math]\nu=e^{\pi i/4}[/math]:
  [[math]] F_4'=\begin{pmatrix} \nu^3&1&\nu^7&1\\ 1&\nu^3&1&\nu^7\\ \nu^7&1&\nu^3&1\\ 1&\nu^7&1&\nu^3 \end{pmatrix} [[/math]]
• At [math]N=5[/math] we obtain the old matrix [math]F_5'[/math].

Show Proof

With notations from Theorem 9.8, the proof goes as follows:

(1) At [math]N=2[/math] we have [math]\nu=i,q=i,w=-1[/math], so the cyclic root is [math](i,-i)[/math]. The first row vector is [math](i,1)[/math], and we obtain indeed the old matrix [math]F_2'[/math].

At [math]N=3[/math] we have [math]\nu=e^{\pi i/3}[/math] and [math]q=w=\nu^2=e^{2\pi i/3}[/math], the cyclic root is [math](w,w^2,1)[/math]. The first row vector is [math](w,1,1)[/math], and we obtain indeed the old matrix [math]F_3'[/math].

(2) At [math]N=4[/math] we have [math]\nu=e^{\pi i/4}[/math] and [math]q=\nu^3,w=\nu^2[/math], the cyclic root is [math](\nu^3,\nu^5,\nu^7,\nu)[/math]. The first row vector is [math](\nu^3,1,\nu^7,1)[/math], and we obtain the matrix in the statement.

(3) At [math]N=5[/math] we have [math]\nu=e^{\pi i/5}[/math] and [math]q=\nu^4=w^2[/math], with [math]w=\nu^2=e^{2\pi i/5}[/math], and the cyclic root is therefore [math](w^2,w^3,w^4,1,w)[/math]. The first row vector is [math](w^2,1,w^4,w^4,1)[/math], and we obtain in this way the old matrix [math]F_5'[/math], as claimed.

■

Regarding the above matrix [math]F_4'[/math], observe that this is equivalent to the matrix [math]F_4''[/math] from Proposition 9.4, with the equivalence [math]F_4'\sim F_4''[/math] being obtained by multiplying everything by [math]\nu=e^{\pi i/4}[/math]. While both these matrices are circulant and symmetric, and of course equivalent to [math]F_4[/math], one of them, namely [math]F_4'[/math], is “better” than the other, because the corresponding cyclic root comes from a progression. This is the reason for our notations [math]F_4',F_4''[/math].

Let us discuss now the case of the generalized Fourier matrices [math]F_G[/math]. In this context, the assumption of being circulant is somewhat unnatural, because this comes from a [math]\mathbb Z_N[/math] symmetry, and the underlying group is no longer [math]\mathbb Z_N[/math]. It is possible to fix this issue by talking about [math]G[/math]-patterned Hadamard matrices, with [math]G[/math] being a finite abelian group, but for our purposes here, the best is to formulate the result in a weaker form, as follows:

Theorem

The generalized Fourier matrices [math]F_G[/math], associated to the finite abelian groups [math]G[/math], can be put in symmetric and bistochastic form.

Show Proof

We know from Theorem 9.8 that any usual Fourier matrix [math]F_N[/math] can be put in circulant and symmetric form. Since circulant implies bistochastic, in the sense that the sums on all rows and all columns must be equal, the result holds for [math]F_N[/math]. In general now, if we decompose our group as [math]G=\mathbb Z_{N_1}\times\ldots\times\mathbb Z_{N_k}[/math], we have:

[[math]] F_G=F_{N_1}\otimes\ldots\otimes F_{N_k} [[/math]]

Now since the property of being circulant is stable under taking tensor products, and so is the property of being bistochastic, we therefore obtain the result.

■

We have as well the following alternative generalization of Theorem 9.8, coming from Backelin's work in , and remaining in the circulant and symmetric setting:

Theorem

Let [math]M|N[/math], and set [math]w=e^{2\pi i/N}[/math]. We have a cyclic root as follows,

[[math]] (\,\underbrace{q_1,\ldots,q_M}_M\,,\,\underbrace{q_1w,\ldots,q_Mw}_M\,,\ldots\ldots,\,\underbrace{q_1w^{N-1},\ldots,q_Mw^{N-1}}_M\,) [[/math]]

provided that [math]q_1,\ldots,q_M\in\mathbb T[/math] satisfy the following condition:

[[math]] (q_1\ldots q_M)^N=(-1)^{M(N-1)} [[/math]]

Moreover, assuming that the following conditions are satisfied,

[[math]] q_1q_2=1\quad,\quad q_3q_M=q_4q_{M-1}=\ldots=w [[/math]]

which imply [math](q_1\ldots q_M)^N=(-1)^{M(N-1)}[/math], the Hadamard matrix is symmetric.

Show Proof

We have several things to be proved, the idea being as follows:

(1) Let us first check the [math]=0[/math] equations for a cyclic root. Given arbitrary numbers [math]q_1,\ldots,q_M\in\mathbb T[/math], if we denote by [math](z_i)[/math] the vector in the statement, we have:

[[math]] \begin{eqnarray*} \sum_iz_{i+1}\ldots z_{i+K} &=&\begin{pmatrix}q_1\ldots q_K+q_2\ldots q_{K+1}+\ldots\ldots+q_{M-K+1}\ldots q_M\\ +q_{M-K+2}\ldots q_Mq_1w+\ldots\ldots+q_Mq_1\ldots q_{K-1}w^{K-1}\end{pmatrix}\\ &&\times(1+w^K+w^{2K}+\ldots+w^{(N-1)K}) \end{eqnarray*} [[/math]]

Now since the sum on the right vanishes, the [math]=0[/math] conditions are satisfied.

(2) Regarding now the [math]=1[/math] condition, the total product of the numbers [math]z_i[/math] is given by:

[[math]] \begin{eqnarray*} \prod_iz_i &=&(q_1\ldots q_M)^N(1\cdot w\cdot w^2\ldots w^{N-1})^M\\ &=&(q_1\ldots q_M)^Nw^{\frac{MN(N-1)}{2}} \end{eqnarray*} [[/math]]

By using [math]w=e^{2\pi i/N}[/math] we obtain that the coefficient on the right is:

[[math]] \begin{eqnarray*} w^{\frac{MN(N-1)}{2}} &=&e^{\frac{2\pi i}{N}\cdot\frac{MN(N-1)}{2}}\\ &=&e^{\pi iM(N-1)}\\ &=&(-1)^{M(N-1)} \end{eqnarray*} [[/math]]

Thus, if [math](q_1\ldots q_M)^N=(-1)^{M(N-1)}[/math], we obtain a cyclic root, as stated. For further details on all this, we refer to the papers of Backelin and Faugère .

(3) The corresponding first row vector can be written as follows:

[[math]] V=\left(\underbrace{q_1,q_1q_2,\ldots,q_1\ldots q_M}_M\,,\ldots\ldots\ldots,\underbrace{\frac{w^{M-1}}{q_2\ldots q_M},\ldots,\frac{w^2}{q_{M-1}q_M},\frac{w}{q_M},1}_M\right) [[/math]]

Thus, the corresponding circulant complex Hadamard matrix is as follows:

[[math]] H=\begin{pmatrix} q_1&q_1q_2&q_1q_2q_3&q_1q_2q_3q_4&q_1q_2q_3q_4q_5&\ldots\\ 1&q_1&q_1q_2&q_1q_2q_3&q_1q_2q_3q_4&\ldots\\ \frac{w}{q_M}&1&q_1&q_1q_2&q_1q_2q_3&\ldots\\ \frac{w^2}{q_{M-1}q_M}&\frac{w}{q_M}&1&q_1&q_1q_2&\ldots\\ \frac{w^3}{q_{M-2}q_{M-1}q_M}&\frac{w^2}{q_{M-1}q_M}&\frac{w}{q_M}&1&q_1&\ldots\\ \vdots&\vdots&\vdots&\vdots&\vdots&\ddots \end{pmatrix} [[/math]]

We are therefore led to the symmetry conditions in the statement, and we are done.

■

Observe that the story is not over here, because Theorem 9.11 still remains to be unified with Theorem 9.10. There are many interesting questions here.

9b. Butson matrices

Still in relation with the CHC, the problem of investigating the existence of circulant Butson matrices of a given level appears. Following Turyn , we first have:

Proposition

The size of a circulant real Hadamard matrix

[[math]] H\in M_N(\pm 1) [[/math]]

must be of the form [math]N=4n^2[/math], with [math]n\in\mathbb N[/math].

Show Proof

Let [math]a,b\in\mathbb N[/math] with [math]a+b=N[/math] be the number of [math]1,-1[/math] entries in the first row of [math]H[/math]. If we denote by [math]H_0,\ldots,H_{N-1}[/math] the rows of [math]H[/math], by summing over columns we get:

[[math]] \begin{eqnarray*} \sum_{i=0}^{N-1} \lt H_0,H_i \gt &=&a(a-b)+b(b-a)\\ &=&(a-b)^2 \end{eqnarray*} [[/math]]

On the other hand, by orthogonality of the rows, the quantity on the left is:

[[math]] \lt H_0,H_0 \gt =N [[/math]]

Thus [math]N=(a-b)^2[/math] is a square, and since [math]N\in 2\mathbb N[/math], this gives [math]N=4n^2[/math], with [math]n\in\mathbb N[/math].

■

Also found by Turyn in is the fact that the above number [math]n\in\mathbb N[/math] must be odd, and not a prime power. In the general Butson matrix setting now, we have:

Proposition

Assume that [math]H\in H_N(l)[/math] is circulant, let [math]w=e^{2\pi {\rm i}/l}[/math]. If

[[math]] a_0,\ldots,a_{l-1}\in\mathbb N [[/math]]

with [math]\sum a_i=N[/math] are the number of [math]1,w,\ldots,w^{l-1}[/math] entries in the first row of [math]H[/math], then:

[[math]] \sum_{ik}w^ka_ia_{i+k}=N [[/math]]

This condition, with [math]\sum a_i=N[/math], will be called “Turyn obstruction” on [math](N,l)[/math].

Show Proof

Indeed, by summing over the columns of [math]H[/math], we obtain:

[[math]] \begin{eqnarray*} \sum_i \lt H_0,H_i \gt &=&\sum_{ij} \lt w^i,w^j \gt a_ia_j\\ &=&\sum_{ij}w^{i-j}a_ia_j \end{eqnarray*} [[/math]]

Now since the left term is [math] \lt H_0,H_0 \gt =N[/math], this gives the result.

■

We can deduce from this a number of concrete obstructions, as follows:

Theorem

When [math]l[/math] is prime, the Turyn obstruction is

[[math]] \sum_i(a_i-a_{i+k})^2=2N [[/math]]

for any [math]k\neq 0[/math]. Also, for small values of [math]l[/math], the Turyn obstruction is as follows:

• At [math]l=2[/math] the condition is:
  [[math]] (a_0-a_1)^2=N [[/math]]
• At [math]l=3[/math] the condition is:
  [[math]] (a_0-a_1)^2+(a_1-a_2)^2+(a_2-a_3)^2=2N [[/math]]
• At [math]l=4[/math] the condition is:
  [[math]] (a_0-a_2)^2+(a_1-a_3)^2=N [[/math]]
• At [math]l=5[/math] the condition is:
  [[math]] \sum_i(a_i-a_{i+1})^2=\sum_i(a_i-a_{i+2})^2=2N [[/math]]

Show Proof

We use the fact, from chapter 6, that when [math]l[/math] is prime, the vanishing sums of [math]l[/math]-roots of unity are exactly the sums of the following type, with [math]c\in\mathbb N[/math]:

[[math]] S=c+cw+\ldots+cw^{l-1} [[/math]]

We conclude that the Turyn obstruction is equivalent to the following system of equations, one for each [math]k\neq 0[/math]:

[[math]] \sum_ia_i^2-\sum_ia_ia_{i+k}=N [[/math]]

Now by forming squares, this gives the equations in the statement. Regarding now the [math]l=2,3,4,5[/math] assertions, these follow from the first assertion when [math]l[/math] is prime, [math]l=2,3,5[/math]. Also, at [math]l=4[/math] we have [math]w=i[/math], so the Turyn obstruction reads:

[[math]] (a_0^2+a_1^2+a_2^2+a_3^2)+i\sum a_ia_{i+1}-2(a_0a_2+a_1a_3)-i\sum a_ia_{i+1}=N [[/math]]

Thus the imaginary terms cancel, and we obtain the formula in the statement.

■

The above results are of course just some basic observations on the subject, and the massive amount of work on the CHC has a number of interesting Butson matrix extensions. For some more advanced theory on all this, we refer to , .

9c. Haagerup count

Let us go back now to the pure complex case, and discuss Fourier analytic aspects. From a traditional linear algebra viewpoint, the circulant matrices are best understood as being the matrices which are Fourier-diagonal, and we will exploit this here. Let us fix [math]N\in\mathbb N[/math], and denote by [math]F=(w^{ij})/\sqrt{N}[/math] with [math]w=e^{2\pi i/N}[/math] the rescaled Fourier matrix, with indices [math]i,j=0,1,\ldots,N-1[/math], which is unitary, given by the following formula:

[[math]] F=\frac{1}{\sqrt{N}}\begin{pmatrix} 1&1&1&\ldots&1\\ 1&w&w^2&\ldots&w^{N-1}\\ 1&w^2&w^4&\ldots&w^{2(N-1)}\\ \vdots&\vdots&\vdots&&\vdots\\ 1&w^{N-1}&w^{2(N-1)}&\ldots&w^{(N-1)^2} \end{pmatrix} [[/math]]

Also, given a vector [math]q\in\mathbb C^N[/math], once again with cyclic indices, [math]i=0,1,\ldots,N-1[/math], we denote by [math]Q\in M_N(\mathbb C)[/math] the diagonal matrix having [math]q[/math] as vector of diagonal entries:

[[math]] Q=\begin{pmatrix} q_0\\ &\ddots\\ &&q_{N-1} \end{pmatrix} [[/math]]

With these conventions, we have the following well-known result, that we have already used in this book, but that we reproduce here for convenience:

Theorem

For a complex matrix [math]H\in M_N(\mathbb C)[/math], the following are equivalent:

• [math]H[/math] is circulant, [math]H_{ij}=\xi_{j-i}[/math] for some [math]\xi\in\mathbb C^N[/math].
• [math]H[/math] is Fourier-diagonal, [math]H=FQF^*[/math] with [math]Q[/math] diagonal.

In addition, the first row vector of [math]FQF^*[/math] is given by [math]\xi=Fq/\sqrt{N}[/math].

Show Proof

If [math]H_{ij}=\xi_{j-i}[/math] is circulant then [math]Q=F^*HF[/math] is diagonal, given by:

[[math]] \begin{eqnarray*} Q_{ij} &=&\frac{1}{N}\sum_{kl}w^{jl-ik}\xi_{l-k}\\ &=&\delta_{ij}\sum_rw^{jr}\xi_r \end{eqnarray*} [[/math]]

Also, if [math]Q=diag(q)[/math] is diagonal then [math]H=FQF^*[/math] is circulant, given by:

[[math]] \begin{eqnarray*} H_{ij} &=&\sum_kF_{ik}Q_{kk}\bar{F}_{jk}\\ &=&\frac{1}{N}\sum_kw^{(i-j)k}q_k \end{eqnarray*} [[/math]]

Thus, we have proved the equivalence between the conditions in the statement. Finally, regarding [math]\xi=Fq/\sqrt{N}[/math], this follows from the last formula established above.

■

The above result is useful in connection with any question regarding the circular matrices, and in relation with the orthogonal and unitary cases, we have:

Proposition

The various sets of circulant matrices are as follows:

• The set of all circulant matrices is:
  [[math]] M_N(\mathbb C)^{circ}=\left\{FQF^*\Big|q\in\mathbb C^N\right\} [[/math]]
• The set of all circulant unitary matrices is:
  [[math]] U_N^{circ}=\left\{FQF^*\Big|q\in\mathbb T^N\right\} [[/math]]
• The set of all circulant orthogonal matrices is:
  [[math]] O_N^{circ}=\left\{FQF^*\Big|q\in\mathbb T^N,\bar{q}_i=q_{-i},\forall i\right\} [[/math]]

In addition, the first row vector of [math]FQF^*[/math] is given by [math]\xi=Fq/\sqrt{N}[/math].

Show Proof

All this follows from Theorem 9.15, as follows:

(1) This assertion, along with the last one, is Theorem 9.15 itself.

(2) This is clear from (1), because the eigenvalues must be on the unit circle [math]\mathbb T[/math].

(3) In order to prove this result, observe first that for a vector [math]q\in\mathbb C^N[/math] we have the following formula, with [math]\tilde{q}_i=\bar{q}_{-i}[/math]:

[[math]] \overline{Fq}=F\tilde{q} [[/math]]

We conclude from this that the vector [math]\xi=Fq[/math] is real if and only if [math]\bar{q}_i=q_{-i}[/math] for any [math]i[/math]. Together with (2), this gives the result.

■

Observe that in Proposition 9.16 (3), the equations for the parameter space for [math]O_N^{circ}[/math] are as follows, going until [math][N/2]+1[/math]:

[[math]] q_0=\bar{q}_0\quad,\quad \bar{q}_1=q_{n-1}\quad,\quad \bar{q}_2=q_{n-2}\quad,\quad \ldots [[/math]]

Thus, with the convention [math]\mathbb Z_\infty=\mathbb T[/math], we have the following formula:

[[math]] O_N^{circ}\simeq \begin{cases} \mathbb Z_2\times\mathbb Z_\infty^{{(N-1)}/2}&(N\ {\rm odd})\\ \mathbb Z_2^2\times\mathbb Z_\infty^{(N-2)/2}&(N\ {\rm even}) \end{cases} [[/math]]

In terms of circulant Hadamard matrices, we have the following statement:

Theorem

The sets of complex and real circulant Hadamard matrices are:

[[math]] X_N^{circ}=\left\{\sqrt{N}FQF^*\Big|q\in\mathbb T^N\right\}\cap M_N(\mathbb T) [[/math]]

[[math]] Y_N^{circ}=\left\{\sqrt{N}FQF^*\Big|q\in\mathbb T^N,\bar{q}_i=q_{-i}\right\}\cap M_N(\pm1) [[/math]]

In addition, the sets of [math]q[/math] parameters are invariant under cyclic permutations, and also under mutiplying by numbers in [math]\mathbb T[/math], respectively under multiplying by [math]-1[/math].

Show Proof

All the assertions are indeed clear from Proposition 9.16, by intersecting the sets computed there with [math]M_N(\mathbb T)[/math].

■

The above statement is of course something quite theoretical in the real case, where the CHC states that we should have [math]Y_N^{circ}=\emptyset[/math], at any [math]N\neq 4[/math]. However, in the complex case all this is useful, and complementary to Björck's cyclic root formalism. Indeed, let us discuss now a number of geometric and analytic aspects, in the complex matrix case. First, we have the following deep counting result, due to Haagerup :

Theorem

When [math]N[/math] is prime, the number of circulant [math]N\times N[/math] complex Hadamard matrices, counted with certain multiplicities, is exactly:

[[math]] N_{circ}=\binom{2N-2}{N-1} [[/math]]

Show Proof

This is something advanced, using a variety of techiques from Fourier analysis, number theory, complex analysis and algebraic geometry. The idea is as follows:

(1) As explained in , when [math]N[/math] is prime, Björck's cyclic root formalism, explained above, can be further manipulated, by using discrete Fourier transforms, and we are eventually led to a simpler system of equations.

(2) This simplified system can be shown then to have a finite number of solutions, the key ingredient here being a well-known theorem of Chebotarev, which states that when [math]N[/math] is prime, all the minors of the Fourier matrix [math]F_N[/math] are nonzero.

(3) With this finiteness result in hand, the precise count can be done as well, by using various techniques from classical algebraic geometry, and we are led to the formula in the statement. For the details here, we refer to Haagerup's paper .

■

When [math]N[/math] is not prime, the situation is considerably more complicated, with some values leading to finitely many solutions, and with other values leading to an infinite number of solutions, and with many other new phenomena appearing. We refer here to the papers of Björck , Björck-Fröberg , Björck-Haagerup and Haagerup .

9d. Analytic aspects

Let us discuss now an alternative take on these questions, based on the [math]p[/math]-norm considerations from chapter 3. As explained in , the most adapted exponent for the circulant case is [math]p=4[/math]. So, as a starting point, let us formulate:

Proposition

Given a matrix [math]U\in U_N[/math] we have

[[math]] ||U||_4\geq 1 [[/math]]

with equality precisely when [math]H=U/\sqrt{N}[/math] is Hadamard.

Show Proof

This is something that we already know, from chapter 3, as a particular case of our results there regarding [math]p[/math]-norms, obtained by using the Jensen inequality. However, this follows as well directly from the Cauchy-Schwarz inequality, as follows:

[[math]] \begin{eqnarray*} ||U||_4^4 &=&\sum_{ij}|U_{ij}|^4\\ &\geq&\frac{1}{N^2}\left(\sum_{ij}|U_{ij}|^2\right)^2\\ &=&1 \end{eqnarray*} [[/math]]

Thus we have [math]||U||_4\geq 1[/math], with equality if and only if [math]H=\sqrt{N}U[/math] is Hadamard.

■

In the circulant case now, and in Fourier formulation, the estimate is as follows:

Theorem

Given a vector [math]q\in\mathbb T^N[/math], written [math]q=(q_0,\ldots,q_{N-1})[/math] consider the following quantity, with all the indices being taken modulo [math]N[/math]:

[[math]] \Phi=\sum_{i+k=j+l}\frac{q_iq_k}{q_jq_l} [[/math]]

Then this quantity [math]\Phi[/math] is real, and we have the estimate

[[math]] \Phi\geq N^2 [[/math]]

with the equality case happening precisely when [math]\sqrt{N}q[/math] is the eigenvalue vector of a circulant Hadamard matrix [math]H\in M_N(\mathbb C)[/math].

Show Proof

By conjugating the formula of [math]\Phi[/math] we see that this quantity is indeed real, as stated. In fact, [math]\Phi[/math] appears by definition as a sum of [math]N^3[/math] terms, consisting of [math]N(2N-1)[/math] values of [math]1[/math] and of [math]N(N-1)^2[/math] other complex numbers of modulus 1, coming in pairs [math](a,\bar{a})[/math]. Regarding now the second assertion, by using the various identifications in Theorem 9.15 and Proposition 9.16, and the formula [math]\xi=Fq/\sqrt{N}[/math] there, we have:

[[math]] \begin{eqnarray*} ||U||_4^4 &=&N\sum_s|\xi_s|^4\\ &=&\frac{1}{N^3}\sum_s\left|\sum_iw^{si}q_i\right|^4\\ &=&\frac{1}{N^3}\sum_s\sum_iw^{si}q_i\sum_jw^{-sj}\bar{q}_j\sum_kw^{sk}q_k\sum_lw^{-sl}\bar{q}_l\\ &=&\frac{1}{N^3}\sum_s\sum_{ijkl}w^{(i-j+k-l)s}\frac{q_iq_k}{q_jq_l}\\ &=&\frac{1}{N^2}\sum_{i+k=j+l}\frac{q_iq_k}{q_jq_l} \end{eqnarray*} [[/math]]

Thus Proposition 9.19 gives the following estimate:

[[math]] \Phi =N^2||U||_4^4 \geq N^2 [[/math]]

Moreover, we have equality precisely in the Hadamard matrix case, as claimed.

■

The above result is something quite subtle, and even surprising, at the level of the consequences. We have as well the following more direct explanation for it:

Proposition

With the above notations, we have the formula

[[math]] \Phi=N^2+\sum_{i\neq j}(|\nu_i|^2-|\nu_j|^2)^2 [[/math]]

where [math]\nu=(\nu_0,\ldots,\nu_{N-1})[/math] is the vector given by [math]\nu=Fq[/math].

Show Proof

This follows by replacing in the above proof the Cauchy-Schwarz estimate by the corresponding sum of squares. More precisely, we know from the above proof that:

[[math]] \Phi=N^3\sum_i|\xi_i|^4 [[/math]]

On the other hand the matrix [math]U_{ij}=\xi_{j-i}[/math] being unitary, we have:

[[math]] \sum_i|\xi_i|^2=1 [[/math]]

We therefore have the following computation:

[[math]] \begin{eqnarray*} 1 &=&\sum_i|\xi_i|^4+\sum_{i\neq j}|\xi_i|^2\cdot|\xi_j|^2\\ &=&N\sum_i|\xi_i|^4-\left((N-1)\sum_i|\xi_i|^4-\sum_{i\neq j}|\xi_i|^2\cdot|\xi_j|^2\right)\\ &=&\frac{1}{N^2}\Phi-\sum_{i\neq j}(|\xi_i|^2-|\xi_j|^2)^2 \end{eqnarray*} [[/math]]

Now by multiplying by [math]N^2[/math], this gives the formula in the statement.

■

Let us explore now the minimization problem for [math]\Phi[/math], by using various combinatorial and analytic methods. As an illustration for the difficulties in dealing with this problem, let us work out the case where [math]N[/math] is small. At [math]N=1[/math] our inequality [math]\Phi\geq N^2[/math] is simply:

[[math]] \Phi=1\geq 1 [[/math]]

At [math]N=2[/math] our inequality is also clearly true, as follows:

[[math]] \Phi=6+\left(\frac{q_0}{q_1}\right)^2+\left(\frac{q_1}{q_0}\right)^2\geq 4 [[/math]]

At [math]N=3[/math] now, the inequality is something more subtle:

[[math]] \Phi=15+4Re\left(\frac{q_0^3+q_1^3+q_2^3}{q_0q_1q_2}\right)\geq 9 [[/math]]

Observe that in terms of [math]a=q_0^2/(q_1q_2)[/math], [math]b=q_1^2/(q_0q_2)[/math], [math]c=q_2^2/(q_0q_1)[/math], which satisfy [math]|a|=|b|=|c|=1[/math] and [math]abc=1[/math], our function is:

[[math]] \Phi=15+4Re(a+b+c) [[/math]]

Thus at [math]N=3[/math] our inequality still has a quite tractable form, namely:

[[math]] |a|=|b|=|c|=1,abc=1\implies Re(a+b+c)\geq-\frac{3}{2} [[/math]]

At [math]N=4[/math] however, the formula of [math]\Phi[/math] is as follows:

[[math]] \begin{eqnarray*}\Phi &=&28+4\left(\frac{q_0q_1}{q_2q_3}+\frac{q_2q_3}{q_0q_1}+\frac{q_0q_3}{q_1q_2}+\frac{q_1q_2}{q_0q_3}\right)+\left(\frac{q_0^2}{q_2^2}+\frac{q_2^2}{q_0^2}+\frac{q_1^2}{q_3^2}+\frac{q_3^2}{q_1^2}\right)\\ &&+2\left(\frac{q_0q_2}{q_1^2}+\frac{q_1^2}{q_0q_2}+\frac{q_0q_2}{q_3^2}+\frac{q_3^2}{q_0q_2}+\frac{q_1q_3}{q_0^2}+\frac{q_0^2}{q_1q_3}+\frac{q_1q_3}{q_2^2}+\frac{q_2^2}{q_1q_3}\right) \end{eqnarray*} [[/math]]

It is not clear how to obtain a simple, direct proof of [math]\Phi\geq 16[/math], based on this formula. This is actually a quite challenging calculus problem, and we will be back to it, most likely on the occasion of our next exercise session.

As an application of the above considerations, in the real Hadamard matrix case, we have the following analytic reformulation of the CHC, from :

Theorem

For a vector [math]q\in\mathbb T^N[/math] satisfying [math]\bar{q}_i=q_{-i}[/math] the following quantity is real,

[[math]] \Phi=\sum_{i+j+k+l=0}q_iq_jq_kq_l [[/math]]

and satisfies the following inequality:

[[math]] \Phi\geq N^2 [[/math]]

The CHC states that we cannot have equality at [math]N \gt 4[/math].

Show Proof

This follows indeed from Theorem 9.20, via the identifications from Proposition 9.16, the parameter space in the real case being [math]\left\{q\in\mathbb T^N|\bar{q}_i=q_{-i}\right\}[/math].

■

Following , let us further discuss all this. We first have the following result:

Theorem

Let us decompose the above function as

[[math]] \Phi=\Phi_0+\ldots+\Phi_{N-1} [[/math]]

with each [math]\Phi_i[/math] being given by the same formula as [math]\Phi[/math], namely

[[math]] \Phi=\sum_{i+k=j+l}\frac{q_iq_k}{q_jq_k} [[/math]]

but keeping the index [math]i[/math] fixed. Then:

• The critical points of [math]\Phi[/math] are those where [math]\Phi_i\in\mathbb R[/math], for any [math]i[/math].
• In the Hadamard case we have [math]\Phi_i=N[/math], for any [math]i[/math].

Show Proof

This follows by doing some elementary computations, as follows:

(1) The first observation is that the non-constant terms in the definition of [math]\Phi[/math] involving the variable [math]q_i[/math] are the terms of the sum [math]K_i+\bar{K}_i[/math], where:

[[math]] K_i=\sum_{2i=j+l}\frac{q_i^2}{q_jq_l}+2\sum_{k\neq i}\sum_{i+k=j+l}\frac{q_iq_k}{q_jq_l} [[/math]]

Thus if we fix [math]i[/math] and we write [math]q_i=e^{i\alpha_i}[/math], we obtain:

[[math]] \begin{eqnarray*} \frac{d\Phi}{d\alpha_i} &=&4Re\left(\sum_k\sum_{i+k=j+l}i\cdot\frac{q_iq_k}{q_jq_l}\right)\\ &=&4Im\left(\sum_{i+k=j+l}\frac{q_iq_k}{q_jq_l}\right)\\ &=&4Im(\Phi_i) \end{eqnarray*} [[/math]]

Now since the derivative must vanish for any [math]i[/math], this gives the result.

(2) We first perform the end of the Fourier computation in the proof of Theorem 9.20 above backwards, by keeping the index [math]i[/math] fixed. We obtain:

[[math]] \begin{eqnarray*} \Phi_i &=&\sum_{i+k=j+l}\frac{q_iq_k}{q_jq_l}\\ &=&\frac{1}{N}\sum_s\sum_{ijkl}w^{(i-j+k-l)s}\frac{q_iq_k}{q_jq_l}\\ &=&\frac{1}{N}\sum_sw^{si}q_i\sum_jw^{-sj}\bar{q}_j\sum_kw^{sk}q_k\sum_lw^{-sl}\bar{q}_l\\ &=&N^2\sum_sw^{si}q_i\bar{\xi}_s\xi_s\bar{\xi}_s \end{eqnarray*} [[/math]]

Here we have used the formula [math]\xi=Fq/\sqrt{N}[/math]. Now by assuming that we are in the Hadamard case, we have [math]|\xi_s|=1/\sqrt{N}[/math] for any [math]s[/math], and so we obtain:

[[math]] \begin{eqnarray*} \Phi_i &=&N\sum_s w^{si}q_i\bar{\xi}_s\\ &=&N\sqrt{N}q_i\overline{(F^*\xi)}_i\\ &=&Nq_i\bar{q}_i\\ &=&N \end{eqnarray*} [[/math]]

Thus, we have obtained the conclusion in the statement.

■

Let us discuss now a probabilistic approach to all this. Given a compact manifold [math]X[/math] endowed with a probability measure, and a bounded function [math]\Theta:X\to[0,\infty)[/math], the maximum of this function can be recaptured via following well-known formula:

[[math]] \max\Theta=\lim_{p\to\infty}\left(\int_X\Theta(x)^p\,dx\right)^{1/p} [[/math]]

In our case, we are rather interested in computing a minimum, and we have:

Proposition

We have the formula

[[math]] \min\Phi=N^3-\lim_{p\to\infty}\left(\int_{\mathbb T^N}(N^3-\Phi)^p\,dq\right)^{1/p} [[/math]]

where the torus [math]\mathbb T^N[/math] is endowed with its usual probability measure.

Show Proof

This follows from the above formula, with [math]\Theta=N^3-\Phi[/math]. Observe that [math]\Theta[/math] is indeed positive, because [math]\Phi[/math] is a sum of [math]N^3[/math] complex numbers of modulus 1.

■

Let us restrict now the attention to the problem of computing the moments of [math]\Phi[/math], which is more or less the same as computing those of [math]N^3-\Phi[/math]. We have here:

Proposition

The moments of [math]\Phi[/math] are given by

[[math]] \int_{\mathbb T^N}\Phi^p\,dq=\#\left\{ \begin{pmatrix}i_1k_1\ldots i_pk_p\\ j_1l_1\ldots j_pl_p\end{pmatrix}\Big|i_s+k_s=j_s+l_s,[i_1k_1\ldots i_pk_p]=[j_1l_1\ldots j_pl_p]\right\} [[/math]]

where the sets between brackets are by definition sets with repetition.

Show Proof

This is indeed clear from the formula of [math]\Phi[/math]. See .

■

Regarding now the real case, an analogue of Proposition 9.25 holds, but the combinatorics does not get any simpler. One idea in dealing with this problem is by considering the “enveloping sum”, obtained from [math]\Phi[/math] by dropping the condition [math]i+k=j+l[/math]:

[[math]] \tilde{\Phi}=\sum_{ijkl}\frac{q_iq_k}{q_jq_l} [[/math]]

The point is that the moments of [math]\Phi[/math] appear as “sub-quantities” of the moments of [math]\tilde{\Phi}[/math], so perhaps the question to start with is to understand very well the moments of [math]\tilde{\Phi}[/math]. And this latter problem sounds like a quite familiar one, because:

[[math]] \tilde{\Phi}=\left|\sum_iq_i\right|^4 [[/math]]

We will be back to this later. For the moment, let us do some combinatorics:

Proposition

We have the moment formula

[[math]] \int_{\mathbb T^N}\tilde{\Phi}^p\,dq=\sum_{\pi\in P(2p)}\binom{2p}{\pi}\frac{N!}{(N-|\pi|)!} [[/math]]

where the coefficients on the right are given by

[[math]] \binom{2p}{\pi}=\binom{2p}{b_1,\ldots,b_{|\pi|}} [[/math]]

with [math]b_1,\ldots,b_{|\pi|}[/math] being the lengths of the blocks of [math]\pi[/math].

Show Proof

Indeed, by using the same method as for [math]\Phi[/math], we obtain:

[[math]] \int_{\mathbb T^N}\tilde{\Phi}(q)^p\,dq=\#\left\{ \begin{pmatrix}i_1k_1\ldots i_pk_p\\ j_1l_1\ldots j_pl_p\end{pmatrix}\Big|[i_1k_1\ldots i_pk_p]=[j_1l_1\ldots j_pl_p]\right\} [[/math]]

The sets with repetitions on the right are best counted by introducing the corresponding partitions [math]\pi=\ker\begin{pmatrix}i_1k_1\ldots i_pk_p\end{pmatrix}[/math], and this gives the formula in the statement.

■

In order to discuss now the real case, we have to slightly generalize the above result, by computing all the half-moments of [math]\widetilde{\Phi}[/math]. The result here is best formulated as:

Proposition

We have the moment formula

[[math]] \int_{\mathbb T^N}\left|\sum_iq_i\right|^{2p}\,dq=\sum_kC_{pk}\frac{N!}{(N-k)!} [[/math]]

with the coefficients being given by

[[math]] C_{pk}=\sum_{\pi\in P(p),|\pi|=k}\binom{p}{b_1,\ldots,b_{|\pi|}} [[/math]]

where [math]b_1,\ldots,b_{|\pi|}[/math] are the lengths of the blocks of [math]\pi[/math].

Show Proof

This follows indeed exactly as Proposition 9.26, by replacing the exponent [math]p[/math] by the exponent [math]p/2[/math], and by splitting the resulting sum as in the statement.

■

Finally, here is a random walk formulation of the problem:

Theorem

The moments of [math]\Phi[/math] have the following interpretation:

• First, the moments of the enveloping sum [math]\int\widetilde{\Phi}^p[/math] count the loops of length [math]4p[/math] on the standard lattice [math]\mathbb Z^N\subset\mathbb R^N[/math], based at the origin.
• [math]\int\Phi^p[/math] counts those loops which are “piecewise balanced”, in the sense that each of the [math]p[/math] consecutive [math]4[/math]-paths forming the loop satisfy [math]i+k=j+l[/math] modulo [math]N[/math].

Show Proof

The first assertion follows from the formula in the proof of Proposition 9.26, and the second assertion follows from the formula in Proposition 9.25.

■

There are many interesting questions here. We refer to for more on all this.

General references

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