Analytic aspects

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

2a. Determinant bound

We have seen so far that the algebraic theory of the Hadamard matrices, while very nice at the elementary level, ultimately leads to some difficult questions. So, let us step now into analytic questions. The first result here, found in 1893 by Hadamard , about 25 years after Sylvester's 1867 founding paper , and which actually led to such matrices being called Hadamard, is a determinant bound, as follows:

Theorem

Given a matrix [math]H\in M_N(\pm1)[/math], we have

[[math]] |\det H|\leq N^{N/2} [[/math]]

with equality precisely when [math]H[/math] is Hadamard.

Show Proof

We use here the fact, which often tends to be forgotten, that the determinant of a system of [math]N[/math] vectors in [math]\mathbb R^N[/math] is the signed volume of the associated parallelepiped:

[[math]] \det(H_1,\ldots,H_N)=\pm vol \lt H_1,\ldots,H_N \gt [[/math]]

This is actually the definition of the determinant, in case you have forgotten the basics, with the need for the sign coming for having good additivity properties. Now in the case where our vectors have their entries in [math]\{\pm1\}[/math], we therefore have the following inequality, with equality precisely when our vectors are pairwise orthogonal:

[[math]] \begin{eqnarray*} |\det(H_1,\ldots,H_N)| &\leq&||H_1||\times\ldots\times||H_N||\\ &=&(\sqrt{N})^N \end{eqnarray*} [[/math]]

Thus, we have obtained the result, straight from the definition of [math]\det[/math].

■

The above result is quite interesting, philosophically speaking. Let us recall indeed from chapter 1 that the set formed by the [math]N\times N[/math] Hadamard matrices is:

[[math]] Y_N=M_N(\pm1)\cap\sqrt{N}O_N [[/math]]

Thus, what we have in Theorem 2.1 is an analytic method for locating this Hadamard matrix set [math]Y_N[/math] inside the space of binary matrices [math]M_N(\pm1)[/math]. But this suggests doing several other analytic things, as for instance looking at the maximizers [math]H\in M_N(\pm1)[/math] of the quantity [math]|\det H|[/math], at values [math]N\in\mathbb N[/math] which are not multiples of 4. Things here are quite tricky, and as a basic result on the subject, at [math]N=3[/math] the situation is as follows:

Proposition

For a matrix [math]H\in M_3(\pm1)[/math] we have [math]|\det H|\leq4[/math], and this estimate is sharp, with the equality case being attained by the matrix

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

and its conjugates, via the Hadamard equivalence relation.

Show Proof

In order to get started, observe that Theorem 2.1 provides us with the following bound, which is of course not sharp, [math]\det H[/math] being an integer:

[[math]] |\det H|\leq 3\sqrt{3}=5.1961.. [[/math]]

Now observe that, [math]\det H[/math] being a sum of six [math]\pm1[/math] terms, it must be an even number. Thus, we obtain the estimate in the statement, namely:

[[math]] |\det H|\leq4 [[/math]]

Our claim now is that the following happens, with the nonzero situation appearing precisely for the matrix [math]Q_3[/math] in the statement, and its conjugates:

[[math]] \det H\in\{-4,0,4\} [[/math]]

Indeed, let us try to find the matrices [math]H\in M_3(\pm1)[/math] having the property [math]\det H\neq0[/math]. Up to equivalence, we can assume that the first row is [math](1,1,1)[/math]. Then, once again up to equivalence, we can assume that the second row is [math](1,1,-1)[/math]. And then, once again up to equivalence, we can assume that the third row is [math](1,-1,1)[/math]. Thus, we must have:

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

The determinant of this matrix being [math]-4[/math], we have proved our claim, and the last assertion in the statement too, as a consequence of our study.

■

In general, all this suggests the following definition:

Definition

A quasi-Hadamard matrix is a square binary matrix

[[math]] H\in M_N(\pm1) [[/math]]

which maximizes the quantity [math]|\det H|[/math].

We know from Theorem 2.1 that at [math]N\in 4\mathbb N[/math] such matrices are precisely the Hadamard matrices, provided that the Hadamard Conjecture holds at [math]N[/math]. At values [math]N\notin 4\mathbb N[/math], what we have here are certain matrices which can be thought of as being “generalized Hadamard matrices”, the simplest examples being the matrix [math]Q_3[/math] from Proposition 2.2, and its Hadamard conjugates. For more on all this, we refer to Park-Song .

As a comment, however, Proposition 2.2 might look a bit dissapointing, because it is hard to imagine that the matrix [math]Q_3[/math] there, which is not a very interesting matrix, can really play the role of a “generalized Hadamard matrix” at [math]N=3[/math]. We will come later with more interesting solutions to this latter problem, a first solution being as follows:

[[math]] K_3=\frac{1}{\sqrt{3}}\begin{pmatrix} -1&2&2\\ 2&-1&2\\ 2&2&-1 \end{pmatrix} [[/math]]

To be more precise, this matrix is of course not binary, but it is definitely an interesting matrix, that we will see to be sharing many properties with the Hadamard matrices. Also, we have as well another solution to the [math]N=3[/math] problem, which uses complex numbers, and more specifically the number [math]w=e^{2\pi i/3}[/math], which is as follows:

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

As a conclusion to this study, looking at the maximizers [math]H\in M_N(\pm1)[/math] of the quantity [math]|\det H|[/math] is not exactly an ideal method, when looking for analogues of the Hadamard matrices at the forbidden size values [math]N\notin 4\mathbb N[/math], at least when [math]N[/math] is small. The situation changes, however, when looking at such questions at big values of [math]N\in\mathbb N[/math], where the determinant problematics for the binary matrices becomes very interesting, and quite technical. As a generic statement here, which is a bit informal, we have:

Theorem

We have, in the [math]N\to\infty[/math] limit,

[[math]] \max_{H\in M_N(\pm1)}|\det H|\simeq N^{N/2} [[/math]]

along with even finer estimates, modulo the Hadamard Conjectuere.

Show Proof

As mentioned, this is just an informal statement, standing here as a modest introduction to the subject, in the lack of something more precise, and elementary. There are basically two ways of dealing with such questions, namely:

(1) A first idea, as mentioned, is that of using the existence of an Hadamard matrix [math]H_N\in M_N(\pm1)[/math], at values [math]N\in4\mathbb N[/math], modulo the Hadamard Conjecture of course, and then completing it into binary matrices [math]H_{N+k}\in M_{N+k}(\pm1)[/math], with [math]k=1,2,3[/math]:

[[math]] H_{N+k}= \begin{pmatrix} &&&*\\ &H_N&&*\\ &&&*\\ *&*&*&* \end{pmatrix} [[/math]]

The determinant estimates for such matrices are however quite technical, and we refer here once again to Park-Song , and related papers.

(2) A second method is by using probability theory. The set of binary matrices [math]M_N(\pm1)[/math] is a probability space, when endowed with the counting measure rescaled by [math]1/2^{N^2}[/math], and the determinant can be regarded as a random variable on this space:

[[math]] \det:M_N(\pm1)\to\mathbb Z [[/math]]

The point now is that the distribution of this variable can be computed, in the [math]N\to\infty[/math] limit, and as a consequence, we can investigate the maximizers of [math]|\det H|[/math]. Once again, all this is quite technical, and we refer here to Tao-Vu and related papers.

■

Summarizing, the Hadamard determinant bound provides us with an analytic method of locating the set [math]Y_N=M_N(\pm1)\cap\sqrt{N}O_N[/math] formed by the [math]N\times N[/math] Hadamard matrices inside [math]M_N(\pm1)[/math], and this leads to an interesting [math]N\to\infty[/math] theory.

2b. Norm maximizers

From a “dual” point of view, the question of locating [math]Y_N[/math] inside [math]\sqrt{N}O_N[/math], once again via analytic methods, makes sense as well. The result here, from , is as follows:

Theorem

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

[[math]] ||U||_1\leq N\sqrt{N} [[/math]]

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

Show Proof

We have indeed the following estimate, for any [math]U\in O_N[/math], which uses the Cauchy-Schwarz inequality, and the trivial fact that we have [math]||U||_2=\sqrt{N}[/math]:

[[math]] \begin{eqnarray*} ||U||_1 &=&\sum_{ij}|U_{ij}|\\ &\leq&N\left(\sum_{ij}|U_{ij}|^2\right)^{1/2}\\ &=&N\sqrt{N} \end{eqnarray*} [[/math]]

In addition, we know that the equality case holds when the variables are equal, and so when [math]|U_{ij}|=1/\sqrt{N}[/math], for any [math]i,j[/math]. But this amounts in saying that [math]H=\sqrt{N}U[/math] must satisfy [math]H\in M_N(\pm1)[/math]. Thus, this rescaled matrix [math]H[/math] must be Hadamard, as claimed.

■

We will need more general norms as well, so let record the following result:

Proposition

If [math]\psi:[0,\infty)\to\mathbb R[/math] is strictly concave/convex, the quantity

[[math]] F(U)=\sum_{ij}\psi(U_{ij}^2) [[/math]]

over [math]U_N[/math] is maximized/minimized by the rescaled Hadamard matrices, [math]U=H/\sqrt{N}[/math].

Show Proof

We recall that the Jensen theorem states that for [math]\psi[/math] convex we have the following inequality, with equality, when [math]\psi[/math] is strictly convex, when [math]x_i[/math] are all equal:

[[math]] \psi\left(\frac{x_1+\ldots+x_n}{n}\right)\leq\frac{\psi(x_1)+\ldots+\psi(x_n)}{n} [[/math]]

In our case, let us take [math]n=N^2[/math], and our variables to be as follows:

[[math]] \left\{x_1,\ldots,x_n\right\}=\left\{U_{ij}^2\big|i,j=1,\ldots,N\right\} [[/math]]

We obtain that for any convex function [math]\psi[/math], the following holds:

[[math]] \psi\left(\frac{1}{N}\right)\leq\frac{F(U)}{N^2} [[/math]]

Thus we have the following estimate, with [math]F[/math] being as in the statement:

[[math]] F(U)\geq N^2\psi\left(\frac{1}{N}\right) [[/math]]

Now if [math]\psi[/math] is strictly convex, the equality case holds when the numbers [math]U_{ij}^2[/math] are all equal, so when [math]H=\sqrt{N}U[/math] is Hadamard. The proof for concave functions is similar.

■

Of particular interest for us are the following consequences of Proposition 2.6:

Theorem

The rescaled versions [math]U=H/\sqrt{N}[/math] of the Hadamard matrices [math]H\in M_N(\pm1)[/math] can be characterized as being:

• The maximizers of the [math]p[/math]-norm on [math]O_N[/math], at any [math]p\in[1,2)[/math].
• The minimizers of the [math]p[/math]-norm on [math]O_N[/math], at any [math]p\in(2,\infty][/math].

Show Proof

Consider indeed the [math]p[/math]-norm on [math]O_N[/math], which at [math]p\in[1,\infty)[/math] is given by:

[[math]] ||U||_p=\left(\sum_{ij}|U_{ij}|^p\right)^{1/p} [[/math]]

Since [math]\psi(x)=x^{p/2}[/math] is concave at [math]p\in[1,2)[/math], and convex at [math]p\in(2,\infty)[/math], Proposition 2.6 applies and gives the results at [math]p\in[1,\infty)[/math], the precise estimates being as follows:

[[math]] ||U||_p: \begin{cases} \leq N^{2/p-1/2}&{\rm if}\ p \lt 2\\ =N^{1/2}&{\rm if}\ p=2\\ \geq N^{2/p-1/2}&{\rm if}\ p \gt 2 \end{cases} [[/math]]

As for the case [math]p=\infty[/math], this follows either by letting [math]p\to\infty[/math] in the above estimates, or directly via Cauchy-Schwarz, a bit as in the proof of Theorem 2.5.

■

As it was the case with the Hadamard determinant bound, all this suggests doing some further geometry and analysis, this time on the Lie group [math]O_N[/math], with a notion of “almost Hadamard matrix” at stake. Let us formulate indeed, in analogy with Definition 2.3:

Definition

An optimal almost Hadamard matrix is a rescaled orthogonal matrix

[[math]] H\in\sqrt{N}O_N [[/math]]

which maximizes the [math]1[/math]-norm.

Here the adjective “optimal” comes from the fact that, in contrast with what happens over [math]M_N(\pm1)[/math], in connection with the determinant bound, here over [math]\sqrt{N}O_N[/math] we have more flexibility, and we can talk if we want about the local maximizers of the 1-norm. These latter matrices are called “almost Hadamard”, and we will investigate them in the next chapter. Also, we will talk there about more general [math]p[/math]-norms as well.

We know from Theorem 2.6 that at [math]N\in 4\mathbb N[/math] the absolute almost Hadamard matrices are precisely the Hadamard matrices, provided that the Hadamard Conjecture holds at [math]N[/math]. At values [math]N\notin 4\mathbb N[/math], what we have are certain matrices which can be thought of as being “generalized Hadamard matrices”, and are waiting to be investigated. Let us begin with a preliminary study, at [math]N=3[/math]. The result here, from , is as follows:

Theorem

For any matrix [math]U\in O_3[/math] we have the estimate

[[math]] ||U||_1\leq 5 [[/math]]

and this is sharp, with the equality case being attained by the matrix

[[math]] U=\frac{1}{3}\begin{pmatrix} -1&2&2\\ 2&-1&2\\ 2&2&-1 \end{pmatrix} [[/math]]

and its conjugates, via the Hadamard equivalence relation.

Show Proof

By dividing by [math]\det U[/math], we can assume that we have [math]U\in SO_3[/math]. We use the Euler-Rodrigues parametrization for the elements of [math]SO_3[/math], namely:

[[math]] U=\begin{pmatrix} x^2+y^2-z^2-t^2&2(yz-xt)&2(xz+yt)\\ 2(xt+yz)&x^2+z^2-y^2-t^2&2(zt-xy)\\ 2(yt-xz)&2(xy+zt)&x^2+t^2-y^2-z^2 \end{pmatrix} [[/math]]

Here [math](x,y,z,t)\in S^3[/math] come from the map [math]SU_2\to SO_3[/math]. Now in order to obtain the estimate, we linearize. We must prove that for any numbers [math]x,y,z,t\in\mathbb R[/math] we have:

[[math]] \begin{eqnarray*} &&|x^2+y^2-z^2-t^2|+|x^2+z^2-y^2-t^2|+|x^2+t^2-y^2-z^2|\\ &&+2\left(|yz-xt|+|xz+yt|+|xt+yz|+|zt-xy|+|yt-xz|+|xy+zt|\right)\\ &&\leq 5(x^2+y^2+z^2+t^2) \end{eqnarray*} [[/math]]

The problem being symmetric in [math]x,y,z,t[/math], and invariant under sign changes, we may assume that we have:

[[math]] x\geq y\geq z\geq t\geq 0 [[/math]]

Now if we look at the 9 absolute values in the above formula, in 7 of them the sign is known, and in the remaining 2 ones the sign is undetermined. More precisely, the inequality to be proved is as follows:

[[math]] \begin{eqnarray*} &&(x^2+y^2-z^2-t^2)+(x^2+z^2-y^2-t^2)+|x^2+t^2-y^2-z^2|\\ &&+2\left(|yz-xt|+(xz+yt)+(xt+yz)+(xy-zt)+(xz-yt)+(xy+zt)\right)\\ &&\leq 5(x^2+y^2+z^2+t^2) \end{eqnarray*} [[/math]]

After simplification and rearrangement of the terms, this inequality reads:

[[math]] \begin{eqnarray*} &&|x^2+t^2-y^2-z^2|+2|xt-yz|\\ &\leq&3x^2+5y^2+5z^2+7t^2-4xy-4xz-2xt-2yz \end{eqnarray*} [[/math]]

In principle we have now 4 cases to discuss, depending on the possible signs appearing at left. It is, however, easier to proceed simply by searching for the optimal case. First, by writing [math]y=\alpha+\varepsilon,z=\alpha-\varepsilon[/math] and by making [math]\varepsilon[/math] vary over the real line, we see that the optimal case is when [math]\varepsilon=0[/math], hence when [math]y=z[/math]. The cases [math]y=z=0[/math] and [math]y=z=\infty[/math] being both clear, and not sharp, we can assume that we have:

[[math]] y=z=1 [[/math]]

Thus we must prove that for any numbers [math]x\geq 1\geq t\geq 0[/math] we have:

[[math]] |x^2+t^2-2|+2|xt-1|\leq 3x^2+8+7t^2-8x-2xt [[/math]]

In the case [math]xt\geq 1[/math] we have [math]x^2+t^2\geq 2[/math], and the inequality becomes:

[[math]] 2xt+4x\leq x^2+3t^2+6 [[/math]]

In the case [math]xt\leq 1,x^2+t^2\leq 2[/math] we get:

[[math]] x^2+1+2t^2\geq 2x [[/math]]

In the remaining case [math]xt\leq 1,x^2+t^2\geq 2[/math] we get:

[[math]] x^2+4+3t^2\geq 4x [[/math]]

But these inequalities are all true, and this finishes the proof of the estimate. Now regarding the maximum, we know that this is attained at [math](xyzt)=(1110)[/math] or at [math](xyzt)=(2110)[/math], plus permutations. The corresponding matrix is, modulo permutations:

[[math]] V=\frac{1}{3} \begin{pmatrix} 1&2&2\\ 2&1&-2\\ -2&2&-1 \end{pmatrix} [[/math]]

But for this matrix we have indeed [math]||V||_1=5[/math], and we are done.

■

In terms of Definition 2.8, the conclusion is as follows:

Theorem

The optimal almost Hadamard matrices at [math]N=3[/math] are

[[math]] K_3=\frac{1}{\sqrt{3}}\begin{pmatrix} -1&2&2\\ 2&-1&2\\ 2&2&-1 \end{pmatrix} [[/math]]

and its conjugates, via the Hadamard equivalence relation.

Show Proof

This is indeed a reformulation of Theorem 2.9, using Definition 2.8.

■

The above result and the matrix [math]K_3[/math] appearing there are quite interesting, because they remind the Hadamard matrix [math]K_4[/math] studied in chapter 1, given by:

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

To be more precise, all this suggests looking at the following remarkable family of matrices [math]K_N\in\sqrt{N}O_N[/math], having arbitrary size [math]N\in\mathbb N[/math]:

[[math]] K_N=\frac{1}{\sqrt{N}}\begin{pmatrix} 2-N&&2\\ &\ddots&\\ 2&&2-N \end{pmatrix} [[/math]]

These matrices are in general not optimal almost Hadamard, in the sense of Definition 2.8, for instance because at [math]N=2[/math] or at [math]N=8,12,16,\ldots[/math] they are obviously not Hadamard. We will see however in the next chapter that these matrices are “almost Hadamard”, in the sense that they locally maximize the 1-norm on [math]\sqrt{N}O_N[/math].

To summarize, the computation of the maximizers of the 1-norm on [math]O_N[/math] is a difficult question, a bit like the computation of the maximizers of [math]|\det|[/math] on [math]M_N(\pm1)[/math] was, and looking instead at the local maximizers of the 1-norm on [math]O_N[/math] is the way to be followed, with some interesting examples and combinatorics at stake. We will be back to this.

Let us discuss now, as a continuation of all this, an analytic reformulation of the Hadamard Conjecture. Following , the starting statement here is:

Proposition

We have the following estimate,

[[math]] \sup_{U\in O_N}||U||_1\leq N\sqrt{N} [[/math]]

with equality if and only if there exists an Hadamard matrix of order [math]N[/math].

Show Proof

This follows indeed from the inequality [math]||U||_1\leq N\sqrt{N}[/math], with equality in the rescaled Hadamard matrix case, [math]U=H/\sqrt{N}[/math], from Theorem 2.5.

■

We begin our study with the following observation:

Proposition

If the Hadamard Conjecture holds, then

[[math]] \sup_{U\in O_N}||U||_1\geq (N-4.5)\sqrt{N} [[/math]]

for any [math]N\in\mathbb N[/math].

Show Proof

If [math]N[/math] is a multiple of [math]4[/math] we can use an Hadamard matrix, and we are done. In general, we can write [math]N=M+k[/math] with [math]4|M[/math] and [math]0\leq k\leq 3[/math], and use an Hadamard matrix of order [math]N[/math], completed with an identity matrix of order [math]k[/math]. This gives:

[[math]] \begin{eqnarray*} \sup_{U\in O_N}||U||_1 &\geq& M\sqrt{M}+k\\ &\geq&(N-3)\sqrt{N-3}+3\\ &\geq&(N-4.5)\sqrt{N}+3 \end{eqnarray*} [[/math]]

Here the last inequality, which is something proved by taking squares, is valid for any [math]N\geq 5[/math]. Thus, we are led to the conclusion in the statement.

■

We would like to understand now which estimates on the quantity in Proposition 2.12 imply the Hadamard conjecture. We first have the following result:

Proposition

For any norm one vector [math]U\in\mathbb R^N[/math] we have the formula

[[math]] ||U||_1=\sqrt{N}\left(1-\frac{||U-H||^2}{2}\right) [[/math]]

where [math]H\in\mathbb R^N[/math] is the vector given by:

[[math]] H_i=\frac{{\rm sgn}(U_i)}{\sqrt{N}} [[/math]]

Show Proof

We indeed have the following computation:

[[math]] \begin{eqnarray*} ||U-H||^2 &=&\sum_i\left(U_i-\frac{{\rm sgn}(U_i)}{\sqrt{N}}\right)^2\\ &=&\sum_iU_i^2-\frac{2|U_i|}{\sqrt{N}}+\frac{1}{N}\\ &=&||U||^2-\frac{2||U||_1}{\sqrt{N}}+1\\ &=&2-\frac{2||U||_1}{\sqrt{N}} \end{eqnarray*} [[/math]]

But this gives the formula in the statement.

■

Next, we have the following estimate, also from :

Proposition

Let [math]N[/math] be even, and let [math]U\in O_N[/math] be a matrix such that

[[math]] H=\frac{S}{\sqrt{N}} [[/math]]

is not Hadamard, where [math]S_{ij}={\rm sgn}(U_{ij})[/math]. We have then the following estimate:

[[math]] ||U||_1\leq N\sqrt{N}-\frac{1}{N\sqrt{N}} [[/math]]

Show Proof

Since [math]H[/math] is not Hadamard, this matrix has two distinct rows [math]H_1,H_2[/math] which are not orthogonal. Since [math]N[/math] is even, we must have:

[[math]] | \lt H_1,H_2 \gt |\geq\frac{2}{N} [[/math]]

We obtain from this the following estimate:

[[math]] \begin{eqnarray*} ||U_1-H_1||+||U_2-H_2|| &\geq&| \lt U_1-H_1,H_2 \gt |+| \lt U_2-H_2,U_1 \gt |\\ &\geq&| \lt U_1-H_1,H_2 \gt + \lt U_2-H_2,U_1 \gt |\\ &=&| \lt U_2,U_1 \gt - \lt H_1,H_2 \gt |\\ &=&| \lt H_1,H_2 \gt |\\ &\geq&\frac{2}{N} \end{eqnarray*} [[/math]]

Now by applying the estimate in Proposition 2.13 to [math]U_1,U_2[/math], we obtain:

[[math]] \begin{eqnarray*} ||U_1||_1+||U_2||_1 &=&\sqrt{N}\left(2-\frac{||U_1-H_1||^2+||U_2-H_2||^2}{2}\right)\\ &\leq&\sqrt{N}\left(2-\left(\frac{||U_1-H_1||+||U_2-H_2||}{2}\right)^2\right)\\ &\leq&\sqrt{N}\left(2-\frac{1}{N^2}\right)\\ &=&2\sqrt{N}-\frac{1}{N\sqrt{N}} \end{eqnarray*} [[/math]]

By adding to this inequality the 1-norms of the remaining [math]N-2[/math] rows, all bounded from above by [math]\sqrt{N}[/math], we obtain the result.

■

We can now answer the question raised above, as follows:

Theorem

If [math]N[/math] is even and the following holds,

[[math]] \sup_{U\in O_N}||U||_1\geq N\sqrt{N}-\frac{1}{N\sqrt{N}} [[/math]]

then the Hadamard Conjecture holds at [math]N[/math].

Show Proof

Indeed, if the Hadamard conjecture does not hold at [math]N[/math], then the assumption of Proposition 2.14 is satisfied for any [math]U\in O_N[/math], and this gives the result.

■

As a related result now, also from , let us compute the average of the 1-norm on [math]O_N[/math]. For this purpose, we will use the following well-known result:

Proposition

We have the following formulae,

[[math]] \int_0^{\pi/2}\cos^pt\,dt=\int_0^{\pi/2}\sin^pt\,dt=\left(\frac{\pi}{2}\right)^{\varepsilon(p)}\frac{p!!}{(p+1)!!} [[/math]]

where [math]\varepsilon(p)=1[/math] if [math]p[/math] is even, and [math]\varepsilon(p)=0[/math] if [math]p[/math] is odd, and where

[[math]] m!!=(m-1)(m-3)(m-5)\ldots [[/math]]

with the product ending at [math]2[/math] if [math]m[/math] is odd, and ending at [math]1[/math] if [math]m[/math] is even.

Show Proof

Let us first compute the integral on the left in the statement:

[[math]] I_p=\int_0^{\pi/2}\cos^pt\,dt [[/math]]

We do this by partial integration. We have the following formula:

[[math]] \begin{eqnarray*} (\cos^pt\sin t)' &=&p\cos^{p-1}t(-\sin t)\sin t+\cos^pt\cos t\\ &=&p\cos^{p+1}t-p\cos^{p-1}t+\cos^{p+1}t\\ &=&(p+1)\cos^{p+1}t-p\cos^{p-1}t \end{eqnarray*} [[/math]]

By integrating between [math]0[/math] and [math]\pi/2[/math], we obtain the following formula:

[[math]] (p+1)I_{p+1}=pI_{p-1} [[/math]]

But this gives the first formula in the statement. As for the second formula, regarding [math]\sin t[/math], this follows from the first formula, with the change of variables [math]t=\pi/2-s[/math].

■

More generally, we have the following result, which is well-known as well:

Proposition

We have the following formula,

[[math]] \int_0^{\pi/2}\cos^pt\sin^qt\,dt=\left(\frac{\pi}{2}\right)^{\varepsilon(p)\varepsilon(q)}\frac{p!!q!!}{(p+q+1)!!} [[/math]]

where [math]\varepsilon(p)=1[/math] if [math]p[/math] is even, and [math]\varepsilon(p)=0[/math] if [math]p[/math] is odd, as before.

Show Proof

Let [math]I_{pq}[/math] be the integral in the statement. Observe that we have:

[[math]] \begin{eqnarray*} (\cos^pt\sin^qt)' &=&p\cos^{p-1}t(-\sin t)\sin^qt +\cos^pt\cdot q\sin^{q-1}t\cos t\\ &=&-p\cos^{p-1}t\sin^{q+1}t+q\cos^{p+1}t\sin^{q-1}t \end{eqnarray*} [[/math]]

By integrating between [math]0[/math] and [math]\pi/2[/math], we obtain, for [math]p,q \gt 0[/math]:

[[math]] pI_{p-1,q+1}=qI_{p+1,q-1} [[/math]]

Thus, we can compute [math]I_{pq}[/math] by recurrence, and we obtain the above formula.

■

Even more generally now, we have the following result, in [math]N[/math] dimensions:

Theorem

For any exponents [math]k_1,\ldots,k_N\in\mathbb N[/math] we have

[[math]] \int_{S^{N-1}}\left|x_1^{k_1}\ldots x_N^{k_N}\right|dx=\left(\frac{2}{\pi}\right)^{\Sigma(k_1,\ldots,k_N)}\frac{(N-1)!!k_1!!\ldots k_N!!}{(N+\Sigma k_i-1)!!} [[/math]]

with [math]\Sigma=[odds/2][/math] if [math]N[/math] is odd and [math]\Sigma=[(odds+1)/2][/math] if [math]N[/math] is even, where “odds” denotes the number of odd numbers in the sequence [math]k_1,\ldots,k_N[/math].

Show Proof

We use spherical coordinates, which are by definition as follows:

[[math]] \begin{cases} x_1\!\!\!&=\ r\cos t_1\\ x_2\!\!\!&=\ r\sin t_1\cos t_2\\ \vdots\\ x_{N-1}\!\!\!&=\ r\sin t_1\sin t_2\ldots\sin t_{N-2}\cos t_{N-1}\\ x_N\!\!\!&=\ r\sin t_1\sin t_2\ldots\sin t_{N-2}\sin t_{N-1} \end{cases} [[/math]]

The corresponding Jacobian [math]J_N[/math] can be computed by developing the corresponding determinant over the last column, which gives the following formula:

[[math]] \begin{eqnarray*} J_N &=&r\sin t_1\ldots\sin t_{N-2}\sin t_{N-1}\times \sin t_{N-1}J_{N-1}\\ &+&r\sin t_1\ldots \sin t_{N-2}\cos t_{N-1}\times\cos t_{N-1}J_{N-1}\\ &=&r\sin t_1\ldots\sin t_{N-2}(\sin^2 t_{N-1}+\cos^2 t_{N-1})J_{N-1}\\ &=&r\sin t_1\ldots\sin t_{N-2}J_{N-1} \end{eqnarray*} [[/math]]

Thus, we obtain by recurrence the following formula:

[[math]] J_N=r^{N-1}\sin^{N-2}t_1\sin^{N-3}t_2\,\ldots\,\sin^2t_{N-3}\sin t_{N-2} [[/math]]

With this in hand, the integral in the statement can be written in spherical coordinates, as follows, where [math]A[/math] is the area of the sphere, [math]J_N[/math] is the Jacobian, and the [math]2^N[/math] factor comes from the restriction to the [math]1/2^N[/math] part of the sphere where all coordinates are positive:

[[math]] I=\frac{2^N}{A}\int_0^{\pi/2}\ldots\int_0^{\pi/2}x_1^{k_1}\ldots x_N^{k_N}J_N\,dt_1\ldots dt_{N-1} [[/math]]

The normalization constant in front of the integral is:

[[math]] \frac{2^N}{A}=\left(\frac{2}{\pi}\right)^{[N/2]}(N-1)!! [[/math]]

As for the unnormalized integral, this is given by the following formula:

[[math]] \begin{eqnarray*} I'=\int_0^{\pi/2}\ldots\int_0^{\pi/2} &&(\cos t_1)^{k_1}\\ &&(\sin t_1\cos t_2)^{k_2}\\ &&\vdots\\ &&(\sin t_1\sin t_2\ldots\sin t_{N-2}\cos t_{N-1})^{k_{N-1}}\\ &&(\sin t_1\sin t_2\ldots\sin t_{N-2}\sin t_{N-1})^{k_N}\\ &&\sin^{N-2}t_1\sin^{N-3}t_2\ldots\sin^2t_{N-3}\sin t_{N-2}\\ &&dt_1\ldots dt_{N-1} \end{eqnarray*} [[/math]]

By rearranging the terms in the above product, we obtain:

[[math]] \begin{eqnarray*} I' &=&\int_0^{\pi/2}\cos^{k_1}t_1\sin^{k_2+\ldots+k_N+N-2}t_1\,dt_1\\ &&\int_0^{\pi/2}\cos^{k_2}t_2\sin^{k_3+\ldots+k_N+N-3}t_2\,dt_2\\ &&\vdots\\ &&\int_0^{\pi/2}\cos^{k_{N-2}}t_{N-2}\sin^{k_{N-1}+k_N+1}t_{N-2}\,dt_{N-2}\\ &&\int_0^{\pi/2}\cos^{k_{N-1}}t_{N-1}\sin^{k_N}t_{N-1}\,dt_{N-1} \end{eqnarray*} [[/math]]

Now by using the [math]N=2[/math] integration formula from Proposition 2.17, we obtain:

[[math]] \begin{eqnarray*} I' &=&\frac{\pi}{2}\cdot\frac{k_1!!(k_2+\ldots+k_N+N-2)!!}{(k_1+\ldots+k_N+N-1)!!}\left(\frac{2}{\pi}\right)^{\delta(k_1,k_2+\ldots+k_N+N-2)}\\ &&\frac{\pi}{2}\cdot\frac{k_2!!(k_3+\ldots+k_N+N-3)!!}{(k_2+\ldots+k_N+N-2)!!}\left(\frac{2}{\pi}\right)^{\delta(k_2,k_3+\ldots+k_N+N-3)}\\ &&\vdots\\ &&\frac{\pi}{2}\cdot\frac{k_{N-2}!!(k_{N-1}+k_N+1)!!}{(k_{N-2}+k_{N-1}+k_N+2)!!}\left(\frac{2}{\pi}\right)^{\delta(k_{N-2},k_{N-1}+k_N+1)}\\ &&\frac{\pi}{2}\cdot\frac{k_{N-1}!!k_N!!}{(k_{N-1}+k_N+1)!!}\left(\frac{2}{\pi}\right)^{\delta(k_{N-1},k_N)} \end{eqnarray*} [[/math]]

In order to compute this quantity, let us denote by [math]F[/math] the part involving the double factorials, and by [math]P[/math] the part involving the powers of [math]\pi/2[/math], so that we have:

[[math]] I'=F\cdot P [[/math]]

Regarding [math]F[/math], there are many cancellations there, and we end up with:

[[math]] F=\frac{k_1!!\ldots k_N!!}{(\Sigma k_i+N-1)!!} [[/math]]

As in what regards [math]P[/math], the [math]\delta[/math] exponents on the right sum up to the following number:

[[math]] \Delta(k_1,\ldots,k_N)=\sum_{i=1}^{N-1}\delta(k_i,k_{i+1}+\ldots+k_N+N-i-1) [[/math]]

In other words, with this notation, the above formula reads:

[[math]] \begin{eqnarray*} I' &=&\left(\frac{\pi}{2}\right)^{N-1}\frac{k_1!!k_2!!\ldots k_N!!}{(k_1+\ldots+k_N+N-1)!!}\left(\frac{2}{\pi}\right)^{\Delta(k_1,\ldots,k_N)}\\ &=&\left(\frac{2}{\pi}\right)^{\Delta(k_1,\ldots,k_N)-N+1}\frac{k_1!!k_2!!\ldots k_N!!}{(k_1+\ldots+k_N+N-1)!!}\\ &=&\left(\frac{2}{\pi}\right)^{\Sigma(k_1,\ldots,k_N)-[N/2]}\frac{k_1!!k_2!!\ldots k_N!!}{(k_1+\ldots+k_N+N-1)!!} \end{eqnarray*} [[/math]]

Here the formula relating [math]\Delta[/math] to [math]\Sigma[/math] follows from a number of simple observations, the first of which is the following one: due to obvious parity reasons, the sequence of [math]\delta[/math] numbers appearing in the definition of [math]\Delta[/math] cannot contain two consecutive zeroes. Thus, we have [math]I'[/math], and together with [math]I=(2^N/V)I'[/math], this gives the formula in the statement.

■

As a technical observation, the exponent [math]\Sigma[/math] appearing in the statement of Theorem 2.18 can be written as well in the following more compact form:

[[math]] \Sigma(k_1,\ldots,k_p)=\left[\frac{N+odds+1}{2}\right]-\left[\frac{N+1}{2}\right] [[/math]]

However, for concrete applications, the writing in Theorem 2.18 is more convenient. Now by using this result, we obtain the following estimate, from :

Theorem

We have the following estimate,

[[math]] \int_{O_N}||U||_1\,dU\simeq\sqrt{\frac{2}{\pi}}\cdot N\sqrt{N} [[/math]]

valid in the [math]N\to\infty[/math] limit.

Show Proof

We use the well-known fact that the row slices of [math]O_N[/math] are all isomorphic to the sphere [math]S^{N-1}[/math], with the restriction of the Haar measure of [math]O_N[/math] corresponding in this way to the uniform measure on [math]S^{N-1}[/math]. Together with a standard symmetry argument, this shows that the average of the 1-norm on [math]O_N[/math] is given by:

[[math]] \begin{eqnarray*} \int_{O_N}||U||_1\,dU &=&\sum_{ij}\int_{O_N}|U_{ij}|\,dU\\ &=&N^2\int_{O_N}|U_{11}|\,dU\\ &=&N^2\int_{S^{N-1}}|x_1|\,dx \end{eqnarray*} [[/math]]

We denote by [math]I[/math] the integral on the right. According to Theorem 2.18, we have:

[[math]] \begin{eqnarray*} I &=&\left(\frac{2}{\pi}\right)^{\Sigma(1)}\frac{(N-1)!!}{N!!}\\ &=&\begin{cases} \displaystyle{\frac{2}{\pi}\cdot\frac{2.4.6\ldots(N-2)}{3.5.7\ldots(N-1)}}& (N\ {\rm even})\\ \displaystyle{1\cdot\frac{3.5.7\ldots(N-2)}{2.4.6\ldots(N-1)}}& (N\ {\rm odd}) \end{cases}\\ &=& \begin{cases} \displaystyle{\frac{4^M}{\pi M}}\begin{pmatrix}2M\\ M\end{pmatrix}^{-1}& (N=2M)\\ 4^{-M}\begin{pmatrix}2M\\ M\end{pmatrix}& (N=2M+1) \end{cases} \end{eqnarray*} [[/math]]

Now by using the Stirling formula, we get from this:

[[math]] \begin{eqnarray*} I &\simeq&\begin{cases} \displaystyle{\frac{4^M}{\pi M}\cdot\frac{\sqrt{\pi M}}{4^M}}& (N=2M)\\ \displaystyle{4^{-M}\cdot\frac{4^M}{\sqrt{\pi M}}}& (N=2M+1) \end{cases}\\ &=&\begin{cases} \displaystyle{\frac{1}{\sqrt{\pi M}}}& (N=2M)\\ \displaystyle{\frac{1}{\sqrt{\pi M}}}& (N=2M+1) \end{cases}\\ &\simeq&\sqrt{\frac{2}{\pi N}} \end{eqnarray*} [[/math]]

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

■

The above result gives in particular the following estimate, in the [math]N\to\infty[/math] limit:

[[math]] \sup_{U\in O_N}||U||_1\,dU\simeq\sqrt{\frac{2}{\pi}}\cdot N\sqrt{N} [[/math]]

For better estimates, the problem is to compute the higher moments of the 1-norm:

[[math]] I_k=\int_{O_N}||U||_1^k\,dU [[/math]]

Indeed, the supremum that we are interested in is given by the following formula:

[[math]] \sup_{U\in O_N}||U||_1\,dU=\lim_{k\to\infty}I_k^{1/k} [[/math]]

However, the computation of the integrals [math]I_k[/math] is a difficult problem, and no concrete applications to the Hadamard Conjecture have been found so far. See .

2c. Bistochastic matrices

Let us discuss now a third analytic topic. The motivation here comes from the fact that the bistochastic Hadamard matrices look better than their non-bistochastic counterparts. As an illustration, [math]F_2[/math] looks better in complex bistochastic form:

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

Also, the matrix [math]W_4[/math] looks better in its bistochastic form, which is the matrix [math]K_4[/math]:

[[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} [[/math]]

We have the following algebraic result on the subject, which shows in particular that we cannot put any Hadamard matrix in bistochastic form:

Theorem

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

• [math]H[/math] is bistochastic, with sums [math]\lambda[/math].
• [math]H[/math] is row-stochastic, with sums [math]\lambda[/math], and [math]\lambda^2=N[/math].

In particular, is such a matrix exists, then [math]N\in 4\mathbb N[/math] must be a square.

Show Proof

Both the implications are elementary, as follows:

[math](1)\implies(2)[/math] If we denote by [math]H_1,\ldots,H_N\in(\pm1)^N[/math] the rows of [math]H[/math], we have indeed:

[[math]] \begin{eqnarray*} N&=&\sum_i \lt H_1,H_i \gt \\ &=&\sum_jH_{1j}\sum_iH_{ij}\\ &=&\sum_jH_{1j}\cdot\lambda\\ &=&\lambda^2 \end{eqnarray*} [[/math]]

[math](2)\implies(1)[/math] Consider the all-one vector [math]\xi=(1)_i\in\mathbb R^N[/math]. The fact that [math]H[/math] is row-stochastic with sums [math]\lambda[/math] reads:

[[math]] \begin{eqnarray*} \sum_jH_{ij}=\lambda,\forall i &\iff&\sum_jH_{ij}\xi_j=\lambda\xi_i,\forall i\\ &\iff&H\xi=\lambda\xi \end{eqnarray*} [[/math]]

Also, the fact that [math]H[/math] is column-stochastic with sums [math]\lambda[/math] reads:

[[math]] \begin{eqnarray*} \sum_iH_{ij}=\lambda,\forall j &\iff&\sum_jH_{ij}\xi_i=\lambda\xi_j,\forall j\\ &\iff&H^t\xi=\lambda\xi \end{eqnarray*} [[/math]]

We must prove that the first condition implies the second one, provided that the row sum [math]\lambda[/math] satisfies [math]\lambda^2=N[/math]. But this follows from the following computation:

[[math]] \begin{eqnarray*} H\xi=\lambda\xi &\implies&H^tH\xi=\lambda H^t\xi\\ &\implies&N\xi=\lambda H^t\xi\\ &\implies&H^t\xi=\lambda\xi \end{eqnarray*} [[/math]]

Thus, we have proved both the implications, and we are done.

■

In practice now, the even Walsh matrices, having size [math]N=4^n[/math], which is a square as required above, can be put in bistochastic form, as follows:

[[math]] W_{4^n}\sim K_4^{\otimes n} [[/math]]

As for the odd Walsh matrices, having size [math]N=2\times 4^n[/math], these cannot be put in bistochastic form. However, we can do this over the complex numbers, with the equivalence being as follows at [math]N=2[/math], and then by tensoring with [math]K_4^{\otimes n}[/math] in general:

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

This is quite interesting, and in general now, it is known from Idel-Wolf that any complex Hadamard matrix can be put in bistochastic form, by a certain non-explicit method. Thus, we have here some theory to be developed. We will be back to this.

There is as well an analytic approach to these questions, based on:

Theorem

For an Hadamard matrix [math]H\in M_N(\pm1)[/math], the excess,

[[math]] E(H)=\sum_{ij}H_{ij} [[/math]]

satisfies [math]|E(H)|\leq N\sqrt{N}[/math], with equality if and only if [math]H[/math] is bistochastic.

Show Proof

In terms of the all-one vector [math]\xi=(1)_i\in\mathbb R^N[/math], we have:

[[math]] \begin{eqnarray*} E(H) &=&\sum_{ij}H_{ij}\\ &=&\sum_{ij}H_{ij}\xi_j\xi_i\\ &=&\sum_i(H\xi)_i\xi_i\\ &=& \lt H\xi,\xi \gt \end{eqnarray*} [[/math]]

Now by using the Cauchy-Schwarz inequality, along with the fact that [math]U=H/\sqrt{N}[/math] is orthogonal, and hence of norm 1, we obtain, as claimed:

[[math]] \begin{eqnarray*} |E(H)| &\leq&||H\xi||\cdot||\xi||\\ &\leq&||H||\cdot||\xi||^2\\ &=&N\sqrt{N} \end{eqnarray*} [[/math]]

Regarding now the equality case, this requires the vectors [math]H\xi,\xi[/math] to be proportional, and so our matrix [math]H[/math] to be row-stochastic. But since [math]U=H/\sqrt{N}[/math] is orthogonal, we have:

[[math]] H\xi\sim\xi\iff H^t\xi\sim\xi [[/math]]

Thus our matrix [math]H[/math] must be bistochastic, as claimed.

■

2d. The glow

One interesting question, that we will discuss now, is that of computing the law of the excess over the equivalence class of [math]H[/math]. Let us start with the following definition:

Definition

The glow of [math]H\in M_N(\pm1)[/math] is the distribution of the excess,

[[math]] E=\sum_{ij}H_{ij} [[/math]]

over the Hadamard equivalence class of [math]H[/math].

Since the excess is invariant under permutations of rows and columns, we can restrict the attention to the matrices [math]\widetilde{H}\simeq H[/math] obtained by switching signs on rows and columns. More precisely, let [math](a,b)\in\mathbb Z_2^N\times\mathbb Z_2^N[/math], and consider the following matrix:

[[math]] \widetilde{H}_{ij}=a_ib_jH_{ij} [[/math]]

We can regard the sum of entries of [math]\widetilde{H}[/math] as a random variable, over the group [math]\mathbb Z_2^N\times\mathbb Z_2^N[/math], and we have the following equivalent description of the glow:

Proposition

Given a matrix [math]H\in M_N(\pm 1)[/math], if we define [math]\varphi:\mathbb Z_2^N\times\mathbb Z_2^N\to\mathbb Z[/math] as the excess of the corresponding Hadamard equivalent of [math]H[/math],

[[math]] \varphi(a,b)=\sum_{ij}a_ib_jH_{ij} [[/math]]

then the glow is the probability measure on [math]\mathbb Z[/math] given by [math]\mu(\{k\})=P(\varphi=k)[/math].

Show Proof

The function [math]\varphi[/math] in the statement can indeed be regarded as a random variable over the group [math]\mathbb Z_2^N\times\mathbb Z_2^N[/math], with this latter group being endowed with its uniform probability measure [math]P[/math]. The distribution [math]\mu[/math] of this variable [math]\varphi[/math] is then given by:

[[math]] \mu(\{k\})=\frac{1}{4^N}\#\left\{(a,b)\in \mathbb Z_2^N\times\mathbb Z_2^N\Big|\varphi(a,b)=k\right\} [[/math]]

By the above discussion, this distribution is exactly the glow.

■

The terminology in Definition 2.22 comes from the following picture. Assume that we have a square city, with [math]N[/math] horizontal streets and [math]N[/math] vertical streets, and with street lights at each crossroads. When evening comes the lights are switched on at the positions [math](i,j)[/math] where [math]H_{ij}=1[/math], and then, all night long, they are randomly switched on and off, with the help of [math]2N[/math] master switches, one at the end of each street:

[[math]] \begin{matrix} \to&&\diamondsuit&\diamondsuit&\diamondsuit&\diamondsuit\\ \to&&\diamondsuit&\times&\diamondsuit&\times\\ \to&&\diamondsuit&\diamondsuit&\times&\times\\ \to&&\diamondsuit&\times&\times&\diamondsuit\\ \\ &&\uparrow&\uparrow&\uparrow&\uparrow \end{matrix} [[/math]]

With this picture in mind, [math]\mu[/math] describes indeed the glow of the city. At a more advanced level now, all this is related to the Gale-Berlekamp game, and this is where our main motivation for studying the glow comes from. We refer to Fishburn-Sloane and Roth-Viswanathan for details on the Gale-Berlekamp game.

In order to compute the glow, it is useful to have in mind the following picture:

[[math]] \begin{matrix} &&b_1&\ldots&b_N\\ &&\downarrow&&\downarrow\\ (a_1)&\to&H_{11}&\ldots&H_{1N}&\Rightarrow&S_1\\ \vdots&&\vdots&&\vdots&&\vdots\\ (a_N)&\to&H_{N1}&\ldots&H_{NN}&\Rightarrow&S_N \end{matrix} [[/math]]

Here the columns of [math]H[/math] have been multiplied by the entries of the horizontal switching vector [math]b[/math], the resulting sums on rows are denoted [math]S_1,\ldots,S_N[/math], and the vertical switching vector [math]a[/math] still has to act on these sums, and produce the glow component at [math]b[/math].

With this picture in mind, we first have the following result:

Proposition

The glow of a matrix [math]H\in M_N(\pm 1)[/math] is given by

[[math]] \mu=\frac{1}{2^N}\sum_{b\in\mathbb Z_2^N}\beta_1(c_1)*\ldots*\beta_N(c_N) [[/math]]

where the measures on the right are convolution powers of Bernoulli laws,

[[math]] \beta_r(c)=\left(\frac{\delta_r+\delta_{-r}}{2}\right)^{*c} [[/math]]

and where [math]c_r=\#\{r\in|S_1|,\ldots,|S_N|\}[/math], with [math]S=Hb[/math].

Show Proof

We use the interpretation of the glow explained above. So, consider the decomposition of the glow over [math]b[/math] components:

[[math]] \mu=\frac{1}{2^N}\sum_{b\in\mathbb Z_2^N}\mu_b [[/math]]

With the notation [math]S=Hb[/math], as in the statement, the numbers [math]S_1,\ldots,S_N[/math] are the row sums of [math]\widetilde{H}_{ij}=H_{ij}a_ib_j[/math]. Thus the glow components are given by:

[[math]] \mu_b=law\left(\pm S_1\pm S_2\ldots\pm S_N\right) [[/math]]

By permuting now the sums on the right, we have the following formula:

[[math]] \mu_b=law\big(\underbrace{\pm 0\ldots\pm 0}_{c_0}\ \underbrace{\pm 1\ldots\pm 1}_{c_1}\,\ldots\ldots\,\underbrace{\pm N\ldots\pm N}_{c_N}\big) [[/math]]

Now since the [math]\pm[/math] variables each follow a Bernoulli law, and these Bernoulli laws are independent, we obtain a convolution product as in the statement.

■

We will need the following elementary fact:

Proposition

Let [math]H\in M_N(\pm1)[/math] be an Hadamard matrix of order [math]N\geq 4[/math].

• The sums of entries on rows [math]S_1,\ldots,S_N[/math] are even, and equal modulo [math]4[/math].
• If the sums on the rows [math]S_1,\ldots,S_N[/math] are all [math]0[/math] modulo [math]4[/math], then the number of rows whose sum is [math]4[/math] modulo [math]8[/math] is odd for [math]N=4(8)[/math], and even for [math]N=0(8)[/math].

Show Proof

This is something elementary, the proof being as follows:

(1) Let us pick two rows of our matrix, and then permute the columns such that these two rows look as follows:

[[math]] \begin{pmatrix} 1\ldots\ldots1&1\ldots\ldots1&-1\ldots-1&-1\ldots-1\\ \underbrace{1\ldots\ldots1}_a&\underbrace{-1\ldots-1}_b&\underbrace{1\ldots\ldots1}_c&\underbrace{-1\ldots-1}_d \end{pmatrix} [[/math]]

We have [math]a+b+c+d=N[/math], and by orthogonality we obtain [math]a+d=b+c[/math]. Thus [math]a+d=b+c=N/2[/math], and since [math]N/2[/math] is even we have [math]b=c(2)[/math], which gives the result.

(2) In the case where [math]H[/math] is “row-dephased”, in the sense that its first row consists of [math]1[/math] entries only, the row sums are [math]N,0,\ldots,0[/math], and so the result holds. In general now, by permuting the columns we can assume that our matrix looks as follows:

[[math]] H=\begin{pmatrix}1\ldots\ldots1&-1\ldots-1\\ \underbrace{\vdots}_x&\underbrace{\ \vdots\ }_y\end{pmatrix} [[/math]]

We have [math]x+y=N=0(4)[/math], and since the first row sum [math]S_1=x-y[/math] is by assumption 0 modulo 4, we conclude that [math]x,y[/math] are even. In particular, since [math]y[/math] is even, the passage from [math]H[/math] to its row-dephased version [math]\widetilde{H}[/math] can be done via [math]y/2[/math] double sign switches. Now, in view of the above, it is enough to prove that the conclusion in the statement is stable under a double sign switch. So, let [math]H\in M_N(\pm1)[/math] be Hadamard, and let us perform to it a double sign switch, say on the first two columns. Depending on the values of the entries on these first two columns, the total sums on the rows change as follows:

[[math]] \begin{eqnarray*} \begin{pmatrix}+&+&\ldots&\ldots\end{pmatrix}&:&S\to S-4\\ \begin{pmatrix}+&-&\ldots&\ldots\end{pmatrix}&:&S\to S\\ \begin{pmatrix}-&+&\ldots&\ldots\end{pmatrix}&:&S\to S\\ \begin{pmatrix}-&-&\ldots&\ldots\end{pmatrix}&:&S\to S+4 \end{eqnarray*} [[/math]]

We can see that the changes modulo 8 of the row sum [math]S[/math] occur precisely in the first and in the fourth case. But, since the first two columns of our matrix [math]H\in M_N(\pm1)[/math] are orthogonal, the total number of these cases is even, and this finishes the proof.

■

Observe that Proposition 2.24 and Proposition 2.25 (1) show that the glow of an Hadamard matrix of order [math]N\geq 4[/math] is supported by [math]4\mathbb Z[/math]. With this in hand, we have:

Theorem

Let [math]H\in M_N(\pm1)[/math] be an Hadamard matrix of order [math]N\geq 4[/math], and denote by [math]\mu^{even},\mu^{odd}[/math] the mass one-rescaled restrictions of [math]\mu\in\mathcal P(4\mathbb Z)[/math] to [math]8\mathbb Z,8\mathbb Z+4[/math].

• At [math]N=0(8)[/math] we have [math]\mu=\frac{3}{4}\mu^{even}+\frac{1}{4}\mu^{odd}[/math].
• At [math]N=4(8)[/math] we have [math]\mu=\frac{1}{4}\mu^{even}+\frac{3}{4}\mu^{odd}[/math].

Show Proof

We use the glow decomposition over [math]b[/math] components, from Proposition 2.24:

[[math]] \mu=\frac{1}{2^N}\sum_{b\in\mathbb Z_2^N}\mu_b [[/math]]

The idea is that the decomposition formula in the statement will occur over averages of the following type, over truncated sign vectors [math]c\in\mathbb Z_2^{N-1}[/math]:

[[math]] \mu'_c=\frac{1}{2}(\mu_{+c}+\mu_{-c}) [[/math]]

Indeed, we know from Proposition 2.25 (1) that modulo 4, the sums on rows are either [math]0,\ldots,0[/math] or [math]2,\ldots,2[/math]. Now since these two cases are complementary when pairing switch vectors [math](+c,-c)[/math], we can assume that we are in the case [math]0,\ldots,0[/math] modulo 4. Now by looking at this sequence modulo 8, and letting [math]x[/math] be the number of 4 components, so that the number of 0 components is [math]N-x[/math], we have:

[[math]] \frac{1}{2}(\mu_{+c}+\mu_{-c})=\frac{1}{2}\left(law(\underbrace{\pm0\ldots\pm 0}_{N-x}\,\underbrace{\pm4\ldots\pm 4}_x)+law(\underbrace{\pm 2\ldots\pm 2}_N)\right) [[/math]]

Now by using Proposition 2.25 (2), the first summand splits [math]1-0[/math] or [math]0-1[/math] on [math]8\mathbb Z,8\mathbb Z+4[/math], depending on the class of [math]N[/math] modulo 8. As for the second summand, since [math]N[/math] is even this always splits [math]\frac{1}{2}-\frac{1}{2}[/math] on [math]8\mathbb Z,8\mathbb Z+4[/math]. Thus, by making the average we obtain either a [math]\frac{3}{4}-\frac{1}{4}[/math] or a [math]\frac{1}{4}-\frac{3}{4}[/math] splitting on [math]8\mathbb Z,8\mathbb Z+4[/math], depending on the class of [math]N[/math] modulo 8, as claimed.

■

Various computer simulations suggest that the above measures [math]\mu^{even},\mu^{odd}[/math] don't have further general properties, so that the basic algebraic theory stops here. However, analytically speaking now, we have an interesting result about the glow. We will need:

Proposition

The moments of the normal law

[[math]] g_1=\frac{1}{\sqrt{2\pi}}e^{-x^2/2}dx [[/math]]

are the numbers [math]M_k=k!![/math], with the convention [math]k!!=0[/math] when [math]k[/math] is odd.

Show Proof

We have indeed the following computation:

[[math]] \begin{eqnarray*} M_k &=&\frac{1}{\sqrt{2\pi}}\int_\mathbb Rx^ke^{-x^2/2}dx\\ &=&\frac{1}{\sqrt{2\pi}}\int_\mathbb R(x^{k-1})\left(-e^{-x^2/2}\right)'dx\\ &=&\frac{1}{\sqrt{2\pi}}\int_\mathbb R(k-1)x^{k-2}e^{-x^2/2}dx\\ &=&(k-1)\times\frac{1}{\sqrt{2\pi}}\int_\mathbb Rx^{k-2}e^{-x^2/2}dx\\ &=&(k-1)M_{k-2} \end{eqnarray*} [[/math]]

On the other hand, we have [math]M_0=1[/math], [math]M_1=0[/math]. Thus by recurrence, the even moments vanish, and the odd moments are given by the formula in the statement.

■

We can now formulate our analytic result regarding the glow, as follows:

Theorem

The glow moments of [math]H\in M_N(\pm1)[/math] are given by:

[[math]] \int_{\mathbb Z_2^N\times\mathbb Z_2^N}\left(\frac{E}{N}\right)^{2p}=(2p)!!+O(N^{-1}) [[/math]]

In particular the normalized variable [math]F=E/N[/math] becomes Gaussian with [math]N\to\infty[/math].

Show Proof

Consider the variable in the statement, written as before, as a function of two vectors [math]a,b[/math], belonging to the group [math]\mathbb Z_2^N\times\mathbb Z_2^N[/math]:

[[math]] E=\sum_{ij}a_ib_jH_{ij} [[/math]]

Let [math]P_{even}(r)\subset P(r)[/math] be the set of partitions of [math]\{1,\ldots,r\}[/math] having all blocks of even size. The moments of [math]E[/math] are then given by:

[[math]] \begin{eqnarray*} \int_{\mathbb Z_2^N\times\mathbb Z_2^N}E^r &=&\int_{\mathbb Z_2^N\times\mathbb Z_2^N}\sum_{ix}a_{i_1}\ldots a_{i_r}b_{x_1}\ldots b_{x_r}H_{i_1x_1}\ldots H_{i_rx_r}\\ &=&\sum_{ix}H_{i_1x_1}\ldots H_{i_rx_r}\int_{\mathbb Z_2^N}a_{i_1}\ldots a_{i_r}\int_{\mathbb Z_2^N}b_{x_1}\ldots b_{x_r}\\ &=&\sum_{\pi,\sigma\in P_{even}(r)}\sum_{\ker i=\pi,\ker x=\sigma}H_{i_1x_1}\ldots H_{i_rx_r} \end{eqnarray*} [[/math]]

Thus the moments decompose over partitions [math]\pi\in P_{even}(r)[/math], with the contributions being obtained by integrating the following quantities:

[[math]] C(\sigma)=\sum_{\ker x=\sigma}\sum_iH_{i_1x_1}\ldots H_{i_rx_r}\cdot a_{i_1}\ldots a_{i_r} [[/math]]

Now by Möbius inversion, we obtain a formula as follows:

[[math]] \int_{\mathbb Z_2^N\times\mathbb Z_2^N}E^r=\sum_{\pi\in P_{even}(r)}K(\pi)N^{|\pi|}I(\pi) [[/math]]

To be more precise, here the coefficients on the right are as follows, where [math]\mu[/math] is the Möbius function of [math]P_{even}(r)[/math]:

[[math]] K(\pi)=\sum_{\sigma\in P_{even}(r)}\mu(\pi,\sigma) [[/math]]

As for the contributions on the right, with the convention that [math]H_1,\ldots,H_N\in\mathbb Z_2^N[/math] are the rows of our matrix [math]H[/math], these are as follows:

[[math]] I(\pi)=\sum_i\prod_{b\in\pi}\frac{1}{N}\left\langle\prod_{r\in b}H_{i_r},1\right\rangle [[/math]]

With this formula in hand, the first assertion follows, because the biggest elements of the lattice [math]P_{even}(2p)[/math] are the [math](2p)!![/math] partitions consisting of [math]p[/math] copies of a [math]2[/math]-block:

[[math]] \int_{\mathbb Z_2^N\times\mathbb Z_2^N}\left(\frac{E}{N}\right)^{2p}=(2p)!!+O(N^{-1}) [[/math]]

As for the second assertion, this follows from the moment formula, and from the fact that the glow of [math]H\in M_N(\pm1)[/math] is real, and symmetric with respect to [math]0[/math].

■

All the above was of course a bit technical, using some familiarity with probability theory, and for an introduction to this, we refer for instance to Durrett . We will be back to glow computations in chapter 11 below, in the complex setting.

General references

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