Local estimates

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

12a. Norm maximizers

We discuss here some further analytic questions, regarding the complex Hadamard matrices, following , in analogy with the considerations from chapter 3. We will be interested in the complex analogue of the notion of almost Hadamard matrix. This looks more as a routine topic, and for a long time it was believed that there is no hurry in developing all this, since complex Hadamard matrices exist anyway at any [math]N\in\mathbb N[/math], and so there is no really need for almost Hadamard matrices, in the complex setting.

However, some work on this subject was eventually done in , and surprise, it turned out that, at least conjecturally, there are no almost Hadamard matrices, in the complex sense. Which is very good news, because this shows, again conjecturally, that for a matrix [math]H\in\sqrt{N}U_N[/math], the property of being complex Hadamard is “local”. Which itself is a surprising and potentially far-reaching statement, suggesting reformulating all the Hadamard matrix problematics, including the HC and CHC, in local terms.

We will explain this exciting material in this chapter. To start with, we have the following basic estimate, that we already know, from chapter 11:

Proposition

Given [math]\psi:[0,\infty)\to\mathbb R[/math], the following function over [math]U_N[/math],

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

satisfies the following inequality, when [math]\psi[/math] is convex/concave,

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

and assuming that [math]\psi[/math] is strictly convex/concave, the equality case appears precisely for the rescaled Hadamard matrices, [math]U=H/\sqrt{N}[/math] with [math]H\in M_N(\mathbb T)[/math] Hadamard.

Show Proof

This follows indeed from the Jensen inequality applied to the function in the statement, exactly as in the real case, as explained in chapter 2.

■

Of particular interest for us are the power functions [math]\psi(x)=x^{p/2}[/math], which are concave at [math]p\in[1,2)[/math], and convex at [math]p\in(2,\infty)[/math]. These lead to the following statement:

Theorem

Let [math]U\in U_N[/math], and set [math]H=\sqrt{N}U[/math].

• For [math]p\in[1,2)[/math] we have [math]||U||_p\leq N^{2/p-1/2}[/math],
• For [math]p\in(2,\infty][/math] we have [math]||U||_p\geq N^{2/p-1/2}[/math].

In both cases, the equality situation happens precisely when [math]H[/math] is Hadamard.

Show Proof

Consider indeed the [math]p[/math]-norm on [math]U_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]]

By the above discussion, involving the functions [math]\psi(x)=x^{p/2}[/math], Proposition 12.1 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 with [math]p\to\infty[/math], or directly via Cauchy-Schwarz.

■

For future reference, let us record as well the particular cases [math]p=1,4,\infty[/math] of the above result, that we already met before, and which are of particular interest:

Theorem

For any matrix [math]U\in U_N[/math] we have the estimates

[[math]] ||U||_1\leq N\sqrt{N}\quad,\quad ||U||_4\geq 1\quad,\quad ||U||_\infty\geq\frac{1}{\sqrt{N}} [[/math]]

which in terms of the rescaled matrix [math]H=\sqrt{N}U[/math] read

[[math]] ||H||_1\leq N^2\quad,\quad ||H||_4\geq\sqrt{N}\quad,\quad ||H||_\infty\geq1 [[/math]]

and in each case, the equality case holds when [math]H[/math] is Hadamard.

Show Proof

These results follow from Theorem 12.2 at [math]p=1,4,\infty[/math], with the remark that for each of these particular exponents, we do not really need the Hölder inequality, with a basic application of the Cauchy-Schwarz inequality doing the job.

■

The above results suggest the following definition:

Definition

Given [math]U\in U_N[/math], the matrix [math]H=\sqrt{N}U[/math] is called:

• Almost Hadamard, if [math]U[/math] locally maximizes the [math]1[/math]-norm on [math]U_N[/math].
• [math]p[/math]-almost Hadamard, with [math]p \lt 2[/math], if [math]U[/math] locally maximizes the [math]p[/math]-norm on [math]U_N[/math].
• [math]p[/math]-almost Hadamard, with [math]p \gt 2[/math], if [math]U[/math] locally minimizes the [math]p[/math]-norm on [math]U_N[/math].
• Absolute almost Hadamard, if it is [math]p[/math]-almost Hadamard at any [math]p\neq2[/math].

We have as well real versions of these notions, with [math]U_N[/math] replaced by [math]O_N[/math].

All this might seem a bit complicated, but this is the best way of presenting things. We are mainly interested in (1), but as explained in chapter 9, the exponent [math]p=4[/math] from (3) is interesting as well, and once we have (3) we must formulate (2) as well, and finally (4) is a useful thing too, because the absolute case is sometimes easier to study. As for the “doubling” of all these notions, via the last sentence, this is necessary too, because given a function [math]F:U_N\to\mathbb R[/math], an element [math]U\in O_N[/math] can be a local extremum of the restriction [math]F_{|O_N}:O_N\to\mathbb R[/math], but not of the function [math]F[/math] itself, and we will see examples of this.

Let us first study the critical points. Things are quite tricky here, and complete results are available so far only at [math]p=1[/math]. Following , we first have the following result:

Theorem

If [math]U\in U_N[/math] locally maximizes the [math]1[/math]-norm, then

[[math]] U_{ij}\neq 0 [[/math]]

must hold for any [math]i,j[/math].

Show Proof

We use the same method as in the real case, namely a rotation trick. Let us denote by [math]U_1,\ldots,U_N[/math] the rows of [math]U[/math], and let us perform a rotation of [math]U_1,U_2[/math]:

[[math]] \begin{bmatrix}U^t_1\\ U^t_2\end{bmatrix} =\begin{bmatrix}\cos t\cdot U_1-\sin t\cdot U_2\\ \sin t\cdot U_1+\cos t\cdot U_2\end{bmatrix} [[/math]]

In order to compute the 1-norm, let us permute the columns of [math]U[/math], in such a way that the first two rows look as follows, with [math]X,Y,A,B[/math] having nonzero entries:

[[math]] \begin{bmatrix}U_1\\ U_2\end{bmatrix} =\begin{bmatrix}0&0&Y&A\\0&X&0&B\end{bmatrix} [[/math]]

The rotated matrix will look then as follows:

[[math]] \begin{bmatrix}U_1^t\\ U_2^t\end{bmatrix} =\begin{bmatrix} 0&-\sin t\cdot X&\cos t\cdot Y&\cos t\cdot A-\sin t\cdot B\\ 0&\cos t\cdot X&\sin t\cdot y&\sin t\cdot A+\cos t\cdot B\end{bmatrix} [[/math]]

Our claim is that [math]X,Y[/math] must be empty. Indeed, if [math]A[/math] and [math]B[/math] are not empty, let us fix a column index [math]k[/math] for both [math]A,B[/math], and set [math]\alpha=A_k[/math], [math]\beta=B_k[/math]. We have then:

[[math]] \begin{eqnarray*} |(U_1^t)_k|+|(U_2^t)_k| &=&|\cos t\cdot\alpha-\sin t\cdot\beta|+|\sin t\cdot\alpha+\cos t\cdot\beta|\\ &=&\sqrt{\cos^2t\cdot|\alpha|^2+\sin^2t\cdot|\beta|^2-\sin t\cos t(\alpha\bar{\beta}+\beta\bar{\alpha})}\\ &+&\sqrt{\sin^2t\cdot|\alpha|^2+\cos^2t\cdot|\beta|^2+\sin t\cos t(\alpha\bar{\beta}+\beta\bar{\alpha})} \end{eqnarray*} [[/math]]

Since [math]\alpha,\beta\neq 0[/math], the above function is differentiable at [math]t=0[/math], and we obtain:

[[math]] \begin{eqnarray*} \frac{d\left(|(U_1^t)_k|+|(U_2^t)_k|\right)}{dt} &=&\frac{\sin 2t(|\beta|^2-|\alpha|^2)-\cos 2t(\alpha\bar{\beta}+\beta\bar{\alpha})}{2\sqrt{\cos^2t\cdot|\alpha|^2+\sin^2t\cdot|\beta|^2-\sin t\cos t(\alpha\bar{\beta}+\beta\bar{\alpha})}}\\ &+&\frac{\sin 2t(|\alpha|^2-|\beta|^2)+\cos 2t(\alpha\bar{\beta}+\beta\bar{\alpha})}{2\sqrt{\sin^2t\cdot|\alpha|^2+\cos^2t\cdot|\beta|^2+\sin t\cos t(\alpha\bar{\beta}+\beta\bar{\alpha})}} \end{eqnarray*} [[/math]]

Thus at [math]t=0[/math], we obtain the following formula:

[[math]] \frac{d\left(|(U_1^t)_k|+|(U_2^t)_k|\right)}{dt}(0)=\frac{\alpha\bar{\beta}+\beta\bar{\alpha}}{2}\left(\frac{1}{|\beta|}-\frac{1}{|\alpha|}\right) [[/math]]

Now since our matrix [math]U[/math] locally maximizes the 1-norm, both directional derivatives of [math]||U^t||_1[/math] must be negative in the limit [math]t\to 0[/math]. On the other hand, if we denote by [math]C[/math] the contribution coming from the right, which might be zero in the case where [math]A[/math] and [math]B[/math] are empty, i.e. the sum over [math]k[/math] of the above quantities, we have:

[[math]] \begin{eqnarray*} \frac{d||U^t||_1}{dt}_{\big|t=0^+} &=&\frac{d}{dt}_{\big|t=0^+}(|\cos t|+|\sin t|)(||X||_1+||Y||_1)+C\\ &=&(-\sin t+\cos t)_{\big|t=0}(||X||_1+||Y||_1)+C\\ &=&||X||_1+||Y||_1+C \end{eqnarray*} [[/math]]

As for the derivative at left, this is given by the following formula:

[[math]] \begin{eqnarray*} \frac{d||U^t||_1}{dt}_{\big|t=0^-} &=&\frac{d}{dt}_{\big|t=0^-}(|\cos t|+|\sin t|)(||X||_1+||Y||_1)+C\\ &=&(-\sin t-\cos t)_{\big|t=0}(||X||_1+||Y||_1)+C\\ &=&-||X||_1-||Y||_1+C \end{eqnarray*} [[/math]]

We therefore obtain the following inequalities, where [math]C[/math] is as above:

[[math]] \begin{eqnarray*} ||X||_1+||Y||_1+C &\leq& 0\\ -||X||_1-||Y||_1+C&\leq& 0 \end{eqnarray*} [[/math]]

Consider now the matrix obtained from [math]U[/math] by interchanging [math]U_1,U_2[/math]. Since this matrix must be as well a local maximizer of the 1-norm, and since the above formula shows that [math]C[/math] changes its sign when interchanging [math]U_1,U_2[/math], we obtain:

[[math]] \begin{eqnarray*} ||X||_1+||Y||_1-C &\leq& 0\\ -||X||_1-||Y||_1-C&\leq& 0 \end{eqnarray*} [[/math]]

The four inequalities that we have give altogether the following conclusion:

[[math]] ||X||_1+||Y||_1=C=0 [[/math]]

Now from [math]||X||_1+||Y||_1=0[/math] we obtain that both the vectors [math]X,Y[/math] must be empty, as claimed. As a conclusion, up to a permutation of the columns, the first two rows of our matrix [math]U[/math] must be of the following form, with [math]A,B[/math] having only nonzero entries:

[[math]] \begin{bmatrix}U_1\\ U_2\end{bmatrix} =\begin{bmatrix}0&A\\0&B\end{bmatrix} [[/math]]

By permuting the rows of [math]U[/math], the same must hold for any two rows [math]U_i,U_j[/math]. Now since [math]U[/math] cannot have a zero column, we conclude that [math]U[/math] cannot have zero entries, as claimed.

■

Let us compute now the critical points. Following , we have:

Theorem

Let [math]\varphi:[0,\infty)\to\mathbb R[/math] be a differentiable function. A unitary matrix with nonzero entries [math]U\in U_N^*[/math] is a critical point of the quantity

[[math]] F(U)=\sum_{ij}\varphi(|U_{ij}|) [[/math]]

precisely when [math]WU^*[/math] is self-adjoint, where [math]W_{ij}={\rm sgn}(U_{ij})\varphi'(|U_{ij}|)[/math].

Show Proof

Again, this follows like in the real case, by performing modifications where needed. We regard [math]U_N[/math] as a real algebraic manifold, with coordinates [math]U_{ij},\bar{U}_{ij}[/math]. This manifold consists by definition of the zeroes of the following polynomials:

[[math]] A_{ij}=\sum_kU_{ik}\bar{U}_{jk}-\delta_{ij} [[/math]]

A given matrix [math]U\in U_N[/math] is then a critical point of [math]F[/math] precisely when [math]dF\in span(dA_{ij})[/math]. Regarding the space [math]span(dA_{ij})[/math], this consists of the following quantities:

[[math]] \begin{eqnarray*} \sum_{ij}M_{ij}dA_{ij} &=&\sum_{ijk}M_{ij}(U_{ik}d\bar{U}_{jk}+\bar{U}_{jk}dU_{ik})\\ &=&\sum_{jk}(M^tU)_{jk}d\bar{U}_{jk}+\sum_{ik}(M\bar{U})_{ik}dU_{ik}\\ &=&\sum_{ij}(M^tU)_{ij}d\bar{U}_{ij}+\sum_{ij}(M\bar{U})_{ij}dU_{ij} \end{eqnarray*} [[/math]]

In order to compute [math]dF[/math], observe first that, with [math]S_{ij}=sgn(U_{ij})[/math], we have:

[[math]] \begin{eqnarray*} d|U_{ij}| &=&d\sqrt{U_{ij}\bar{U}_{ij}}\\ &=&\frac{U_{ij}d\bar{U}_{ij}+\bar{U}_{ij}dU_{ij}}{2|U_{ij}|}\\ &=&\frac{1}{2}(S_{ij}d\bar{U}_{ij}+\bar{S}_{ij}dU_{ij}) \end{eqnarray*} [[/math]]

In terms of [math]W_{ij}=sgn(U_{ij})\varphi'(|U_{ij}|)[/math], as in the statement, we obtain:

[[math]] \begin{eqnarray*} dF &=&\sum_{ij}d\left(\varphi(|U_{ij}|)\right)\\ &=&\sum_{ij}\varphi'(|U_{ij}|)d|U_{ij}|\\ &=&\frac{1}{2}\sum_{ij}W_{ij}d\bar{U}_{ij}+\bar{W}_{ij}dU_{ij} \end{eqnarray*} [[/math]]

We conclude that [math]U\in U_N[/math] is a critical point of [math]F[/math] if and only if there exists a matrix [math]M\in M_N(\mathbb C)[/math] such that the following two conditions are satisfied:

[[math]] W=2M^tU\quad,\quad \bar{W}=2M\bar{U} [[/math]]

But this means [math]WU^*=UW^*[/math], and so that [math]WU^*[/math] must be self-adjoint, as claimed.

■

12b. Balanced matrices

In order to process the above result, we proceed exactly as in chapter 3, by adding some complex conjugates where needed. We can use the following notion:

Definition

Given [math]U\in U_N[/math], we consider its “color decomposition”

[[math]] U=\sum_{r \gt 0}rU_r [[/math]]

with [math]U_r\in M_N(\mathbb T\cup\{0\})[/math] containing the phase components at [math]r \gt 0[/math], and we call [math]U[/math]:

• Semi-balanced, if [math]U_rU^*[/math] and [math]U^*U_r[/math], with [math]r \gt 0[/math], are all self-adjoint.
• Balanced, if [math]U_rU_s^*[/math] and [math]U_r^*U_s[/math], with [math]r,s \gt 0[/math], are all self-adjoint.

These conditions are quite natural, because for a unitary matrix [math]U\in U_N[/math], the relations [math]UU^*=U^*U=1[/math] translate as follows, in terms of the color decomposition:

[[math]] \sum_{r \gt 0}rU_rU^*=\sum_{r \gt 0}rU^*U_r=1 [[/math]]

[[math]] \sum_{r,s \gt 0}rsU_rU_s^*=\sum_{r,s \gt 0}rsU_r^*U_s=1 [[/math]]

Thus, our balancing conditions express the fact that the various components of the above sums all self-adjoint. Now back to our critical point questions, we have:

Theorem

For a matrix [math]U\in U_N^*[/math], the following are equivalent:

• [math]U[/math] is a critical point of [math]F(U)=\sum_{ij}\varphi(|U_{ij}|)[/math], for any [math]\varphi:[0,\infty)\to\mathbb R[/math].
• [math]U[/math] is a critical point of all the [math]p[/math]-norms, with [math]p\in[1,\infty)[/math].
• [math]U[/math] is semi-balanced, in the above sense.

Show Proof

We use Theorem 12.6. The matrix constructed there is given by:

[[math]] \begin{eqnarray*} (WU^*)_{ij} &=&\sum_k{\rm sgn}(U_{ik})\varphi'(|U_{ik}|)\bar{U}_{jk}\\ &=&\sum_{r \gt 0}\varphi'(r)\sum_{k,|U_{ik}|=r}{\rm sgn}(U_{ik})\bar{U}_{jk}\\ &=&\sum_{r \gt 0}\varphi'(r)\sum_k(U_r)_{ik}\bar{U}_{jk}\\ &=&\sum_{r \gt 0}\varphi'(r)(U_rU^*)_{ij} \end{eqnarray*} [[/math]]

We conclude that we have the following formula for this matrix:

[[math]] WU^*=\sum_{r \gt 0}\varphi'(r)U_rU^* [[/math]]

Now when [math]\varphi:[0,\infty)\to\mathbb R[/math] varies, as a differentiable function, or as a power function [math]\varphi(x)=x^p[/math] with [math]p\in[1,\infty)[/math], the individual components must be self-adjoint, as desired.

■

In practice now, most of the known examples of semi-balanced matrices are actually balanced. We have the following collection of simple facts, regarding such matrices:

Proposition

The class of balanced matrices is as follows:

• It contains the matrices [math]U=H/\sqrt{N}[/math], with [math]H\in M_N(\mathbb C)[/math] Hadamard.
• It is stable under transposition, complex conjugation, and taking adjoints.
• It is stable under taking tensor products.
• It is stable under the Hadamard equivalence relation.
• It contains the matrix [math]V_N=\frac{1}{N}(2\mathbb I_N-N1_N)[/math], where [math]\mathbb I_N[/math] is the all-[math]1[/math] matrix.

Show Proof

All these results are elementary, the proof being as follows:

(1) Here [math]U\in U_N[/math] follows from the Hadamard condition, and since there is only one color component, namely [math]U_{1/\sqrt{N}}=H[/math], the balancing condition is satisfied as well.

(2) Assuming that [math]U=\sum_{r \gt 0}rU_r[/math] is a color decomposition of a given matrix [math]U\in U_N[/math], the following are color decompositions too, and this gives the assertions:

[[math]] U^t=\sum_{r \gt 0}rU_r^t\quad,\quad \bar{U}=\sum_{r \gt 0}r\bar{U}_r\quad,\quad U^*=\sum_{r \gt 0}rU_r^* [[/math]]

(3) Assuming that [math]U=\sum_{r \gt 0}rU_r[/math] and [math]V=\sum_{s \gt 0}sV_s[/math] are the color decompositions of two given unitary matrices [math]U,V[/math], we have the following formula:

[[math]] \begin{eqnarray*} U\otimes V &=&\sum_{r,s \gt 0}rs\cdot U_r\otimes V_s\\ &=&\sum_{p \gt 0}p\sum_{p=rs}U_r\otimes V_s \end{eqnarray*} [[/math]]

Thus the color components of [math]W=U\otimes V[/math] are the following matrices:

[[math]] W_p=\sum_{p=rs}U_r\otimes V_s [[/math]]

It follows that if [math]U,V[/math] are both balanced, then so is [math]W=U\otimes V[/math].

(4) We recall that the Hadamard equivalence consists in permuting rows and columns, and switching signs on rows and columns. Since all these operations correspond to certain conjugations at the level of the matrices [math]U_rU_s^*,U_r^*U_s[/math], we obtain the result.

(5) The matrix in the statement, which goes back to , is as follows:

[[math]] V_N=\frac{1}{N} \begin{pmatrix} 2-N&2&\ldots&2\\ 2&2-N&\ldots&2\\ \ldots&\ldots&\ldots&\ldots\\ 2&2&\ldots&2-N \end{pmatrix} [[/math]]

Observe that this matrix is indeed unitary, its rows being of norm one, and pairwise orthogonal. The color components of this matrix are:

[[math]] V_{2/N-1}=1_N\quad,\quad V_{2/N}=\mathbb I_N-1_N [[/math]]

It follows that this matrix is balanced as well, as claimed.

■

Let us look now more in detail at [math]V_N[/math], and at the matrices having similar properties. Following , let us call [math](a,b,c)[/math] pattern any matrix [math]M\in M_N(0,1)[/math], with [math]N=a+2b+c[/math], such that any two rows look as follows, up to a permutation of the columns:

[[math]] \begin{matrix} 0\ldots 0&0\ldots 0&1\ldots 1&1\ldots 1\\ \underbrace{0\ldots 0}_a&\underbrace{1\ldots 1}_b&\underbrace{0\ldots 0}_b&\underbrace{1\ldots 1}_c \end{matrix} [[/math]]

As explained in , there are many interesting examples of [math](a,b,c)[/math] patterns, coming from the balanced incomplete block designs (BIBD), and all these examples can produce two-entry unitary matrices, by replacing the [math]0,1[/math] entries with suitable numbers [math]x,y[/math]. Now back to the matrix [math]V_N[/math] from Proposition 12.9 (5), observe that this matrix comes from a [math](0,1,N-2)[/math] pattern, in the above sense. And also, independently of this, this matrix has the remarkable property of being at the same time circulant and self-adjoint. We have in fact the following result, generalizing Proposition 12.9 (5):

Theorem

The following matrices are balanced:

• The orthogonal matrices coming from [math](a,b,c)[/math] patterns.
• The unitary matrices which are circulant and self-adjoint.

Show Proof

These observations basically go back to , the proofs being as follows:

(1) If we denote by [math]P,Q\in M_N(0,1)[/math] the matrices describing the positions of the [math]0,1[/math] entries inside the pattern, then we have the following formulae:

[[math]] \begin{eqnarray*} PP^t=P^tP&=&a\mathbb I_N+b1_N\\ QQ^t=Q^tQ&=&c\mathbb I_N+b1_N\\ PQ^t=P^tQ=QP^t=Q^tP&=&b\mathbb I_N-b1_N \end{eqnarray*} [[/math]]

Since all these matrices are symmetric, [math]U[/math] is balanced, as claimed.

(2) Assume that [math]U\in U_N[/math] is circulant, [math]U_{ij}=\gamma_{j-i}[/math], and in addition self-adjoint, which means [math]\bar{\gamma}_i=\gamma_{-i}[/math]. Consider the following sets, which must satisfy [math]D_r=-D_r[/math]:

[[math]] D_r=\{k:|\gamma_r|=k\} [[/math]]

In terms of these sets, we have the following formula:

[[math]] \begin{eqnarray*} (U_rU_s^*)_{ij} &=&\sum_k(U_r)_{ik}(\bar{U}_s)_{jk}\\ &=&\sum_k\delta_{|\gamma_{k-i}|,r}\,{\rm sgn}(\gamma_{k-i})\cdot\delta_{|\gamma_{k-j}|,s}\,{\rm sgn}(\bar{\gamma}_{k-j})\\ &=&\sum_{k\in(D_r+i)\cap(D_s+j)}{\rm sgn}(\gamma_{k-i})\,{\rm sgn}(\bar{\gamma}_{k-j}) \end{eqnarray*} [[/math]]

With [math]k=i+j-m[/math] we obtain, by using [math]D_r=-D_r[/math], and then [math]\bar{\gamma}_i=\gamma_{-i}[/math]:

[[math]] \begin{eqnarray*} (U_rU_s^*)_{ij} &=&\sum_{m\in(-D_r+j)\cap(-D_s+i)}{\rm sgn}(\gamma_{j-m})\,{\rm sgn}(\bar{\gamma}_{i-m})\\ &=&\sum_{m\in(D_r+i)\cap(D_r+j)}{\rm sgn}(\gamma_{j-m})\,{\rm sgn}(\bar{\gamma}_{i-m})\\ &=&\sum_{m\in(D_r+i)\cap(D_r+j)}{\rm sgn}(\bar{\gamma}_{m-j})\,{\rm sgn}(\gamma_{m-i}) \end{eqnarray*} [[/math]]

Now by interchanging [math]i\leftrightarrow j[/math], and with [math]m\to k[/math], this formula becomes:

[[math]] (U_rU_s^*)_{ji}=\sum_{k\in(D_r+i)\cap(D_r+j)}{\rm sgn}(\bar{\gamma}_{k-i})\,{\rm sgn}(\gamma_{k-j}) [[/math]]

We recognize here the complex conjugate of [math](U_rU_s^*)_{ij}[/math], as previously computed above, and we therefore deduce that [math]U_rU_s^*[/math] is self-adjoint. The proof for [math]U_r^*U_s[/math] is similar.

■

12c. Hessian computations

Let us compute now derivatives. As in Theorem 12.6, it is convenient to do the computations in a more general framework, where we have a function as follows:

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

In order to study the local extrema of these quantities, consider the following function:

[[math]] f(t) =F(Ue^{tA}) =\sum_{ij}\psi(|(Ue^{tA})_{ij}|^2) [[/math]]

Here [math]U\in U_N[/math] is a unitary matrix, and [math]A\in M_N(\mathbb C)[/math] is assumed to be anti-hermitian, [math]A^*=-A[/math], as for having [math]e^A\in U_N[/math]. Let us first compute the derivative of [math]f[/math]. We have:

Proposition

We have the following formula,

[[math]] f'(t)=2\sum_{ij}\psi'(|(Ue^{tA})_{ij}|^2)Re\left[(UAe^{tA})_{ij}\overline{(Ue^{tA})_{ij}}\right] [[/math]]

valid for any [math]U\in U_N[/math], and any [math]A\in M_N(\mathbb C)[/math] anti-hermitian.

Show Proof

The matrices [math]U,e^{tA}[/math] being both unitary, we have:

[[math]] \begin{eqnarray*} |(Ue^{tA})_{ij}|^2 &=&(Ue^{tA})_{ij}\overline{(Ue^{tA})_{ij}}\\ &=&(Ue^{tA})_{ij}((Ue^{tA})^*)_{ji}\\ &=&(Ue^{tA})_{ij}(e^{tA^*}U^*)_{ji}\\ &=&(Ue^{tA})_{ij}(e^{-tA}U^*)_{ji} \end{eqnarray*} [[/math]]

We can now differentiate our function [math]f[/math], and by using once again the unitarity of the matrices [math]U,e^{tA}[/math], along with the formula [math]A^*=-A[/math], we obtain:

[[math]] \begin{eqnarray*} f'(t) &=&\sum_{ij}\psi'(|(Ue^{tA})_{ij}|^2)\left[(UAe^{tA})_{ij}(e^{-tA}U^*)_{ji}-(Ue^{tA})_{ij}(e^{-tA}AU^*)_{ji}\right]\\ &=&\sum_{ij}\psi'(|(Ue^{tA})_{ij}|^2)\left[(UAe^{tA})_{ij}\overline{((e^{-tA}U^*)^*)_{ij}}-(Ue^{tA})_{ij}\overline{((e^{-tA}AU^*)^*)_{ij}}\right]\\ &=&\sum_{ij}\psi'(|(Ue^{tA})_{ij}|^2)\left[(UAe^{tA})_{ij}\overline{(Ue^{tA})_{ij}}+(Ue^{tA})_{ij}\overline{(UAe^{tA})_{ij}}\right] \end{eqnarray*} [[/math]]

But this gives the formula in the statement, and we are done.

■

Before computing the second derivative, let us evaluate [math]f'(0)[/math]. We have:

Proposition

We have the following formula,

[[math]] f'(0)=2\sum_{r \gt 0}r\psi'(r^2)Re\left[Tr(U_r^*UA)\right] [[/math]]

where the matrices [math]U_r\in M_N(\mathbb T\cup\{0\})[/math] are the color components of [math]U[/math].

Show Proof

We use the formula in Proposition 12.11. At [math]t=0[/math], we obtain:

[[math]] f'(0)=2\sum_{ij}\psi'(|U_{ij}|^2)Re\left[(UA)_{ij}\overline{U}_{ij}\right] [[/math]]

Consider now the color decomposition of [math]U[/math]. We have the following formulae:

[[math]] \begin{eqnarray*} U_{ij}=\sum_{r \gt 0}r(U_r)_{ij} &\implies&|U_{ij}|^2=\sum_{r \gt 0}r^2|(U_r)_{ij}|\\ &\implies&\psi'(|U_{ij}|^2)=\sum_{r \gt 0}\psi'(r^2)|(U_r)_{ij}| \end{eqnarray*} [[/math]]

Now by getting back to the above formula of [math]f'(0)[/math], we obtain:

[[math]] f'(0)=2\sum_{r \gt 0}\psi'(r^2)\sum_{ij}Re\left[(UA)_{ij}\overline{U}_{ij}|(U_r)_{ij}|\right] [[/math]]

Our claim now is that we have the following formula:

[[math]] \overline{U}_{ij}|(U_r)_{ij}|=r\overline{(U_r)}_{ij} [[/math]]

Indeed, in the case [math]|U_{ij}|\neq r[/math] this formula reads [math]\overline{U}_{ij}\cdot 0=r\cdot 0[/math], which is true, and in the case [math]|U_{ij}|=r[/math] this formula reads [math]r\bar{S}_{ij}\cdot 1=r\cdot\bar{S}_{ij}[/math], which is once again true. Thus:

[[math]] f'(0)=2\sum_{r \gt 0}r\psi'(r^2)\sum_{ij}Re\left[(UA)_{ij}\overline{(U_r)}_{ij}\right] [[/math]]

But this gives the formula in the statement, and we are done.

■

Let us compute now the second derivative. The result here is as follows:

Proposition

We have the following formula,

[[math]] \begin{eqnarray*} f''(0) &=&4\sum_{ij}\psi''(|U_{ij}|^2)Re\left[(UA)_{ij}\overline{U}_{ij}\right]^2\\ &&+2\sum_{ij}\psi'(|U_{ij}|^2)Re\left[(UA^2)_{ij}\overline{U}_{ij}\right]\\ &&+2\sum_{ij}\psi'(|U_{ij}|^2)|(UA)_{ij}|^2 \end{eqnarray*} [[/math]]

valid for any [math]U\in U_N[/math], and any [math]A\in M_N(\mathbb C)[/math] anti-hermitian.

Show Proof

We use the formula in Proposition 12.11, namely:

[[math]] f'(t)=2\sum_{ij}\psi'(|(Ue^{tA})_{ij}|^2)Re\left[(UAe^{tA})_{ij}\overline{(Ue^{tA})_{ij}}\right] [[/math]]

Since the real part on the right, or rather its double, appears as the derivative of the quantity [math]|(Ue^{tA})_{ij}|^2[/math], when differentiating a second time, we obtain:

[[math]] \begin{eqnarray*} f''(t) &=&4\sum_{ij}\psi''(|(Ue^{tA})_{ij}|^2)Re\left[(UAe^{tA})_{ij}\overline{(Ue^{tA})_{ij}}\right]^2\\ &&+2\sum_{ij}\psi'(|(Ue^{tA})_{ij}|^2)Re\left[(UAe^{tA})_{ij}\overline{(Ue^{tA})_{ij}}\right]' \end{eqnarray*} [[/math]]

In order to compute now the missing derivative, observe that we have:

[[math]] \begin{eqnarray*} \left[(UAe^{tA})_{ij}\overline{(Ue^{tA})_{ij}}\right]' &=&(UA^2e^{tA})_{ij}\overline{(Ue^{tA})_{ij}}+(UAe^{tA})_{ij}\overline{(UAe^{tA})_{ij}}\\ &=&(UA^2e^{tA})_{ij}\overline{(Ue^{tA})_{ij}}+|(UAe^{tA})_{ij}|^2 \end{eqnarray*} [[/math]]

Summing up, we have obtained the following formula:

[[math]] \begin{eqnarray*} f''(t) &=&4\sum_{ij}\psi''(|(Ue^{tA})_{ij}|^2)Re\left[(UAe^{tA})_{ij}\overline{(Ue^{tA})_{ij}}\right]^2\\ &&+2\sum_{ij}\psi'(|(Ue^{tA})_{ij}|^2)Re\left[(UA^2e^{tA})_{ij}\overline{(Ue^{tA})_{ij}}\right]\\ &&+2\sum_{ij}\psi'(|(Ue^{tA})_{ij}|^2)|(UAe^{tA})_{ij}|^2 \end{eqnarray*} [[/math]]

But at [math]t=0[/math] this gives the formula in the statement, and we are done.

■

By using the function [math]\psi(x)=\sqrt{x}[/math], corresponding to [math]F(U)=||U||_1[/math], we obtain:

Proposition

Let [math]U \in U_N^*[/math]. For the function [math]F(U)=||U||_1[/math] we have the formula

[[math]] f''(0)=Re\left[Tr(S^*UA^2)\right]+\sum_{ij}\frac{Im\left[(UA)_{ij}\overline{S}_{ij}\right]^2}{|U_{ij}|} [[/math]]

valid for any anti-hermitian matrix [math]A[/math], where [math]U_{ij}=S_{ij}|U_{ij}|[/math].

Show Proof

We use the formula in Proposition 12.13, with the following data:

[[math]] \psi(x)=\sqrt{x}\quad,\quad \psi'(x)=\frac{1}{2\sqrt{x}}\quad,\quad \psi''(x)=-\frac{1}{4x\sqrt{x}} [[/math]]

We obtain the following formula:

[[math]] \begin{eqnarray*} f''(0) &=&-\sum_{ij}\frac{Re\left[(UA)_{ij}\overline{U}_{ij}\right]^2}{|U_{ij}|^3} +\sum_{ij}\frac{Re\left[(UA^2)_{ij}\overline{U}_{ij}\right]}{|U_{ij}|} +\sum_{ij}\frac{|(UA)_{ij}|^2}{|U_{ij}|}\\ &=&-\sum_{ij}\frac{Re\left[(UA)_{ij}\overline{S}_{ij}\right]^2}{|U_{ij}|} +\sum_{ij}Re\left[(UA^2)_{ij}\overline{S}_{ij}\right] +\sum_{ij}\frac{|(UA)_{ij}|^2}{|U_{ij}|}\\ &=&Re\left[Tr(S^*UA^2)\right]+\sum_{ij}\frac{|(UA)_{ij}|^2-Re\left[(UA)_{ij}\overline{S}_{ij}\right]^2}{|U_{ij}|} \end{eqnarray*} [[/math]]

But this gives the formula in the statement, and we are done.

■

We are therefore led to the following result, regarding the 1-norm:

Theorem

A matrix [math]U\in U_N^*[/math] locally maximizes the one-norm on [math]U_N[/math] precisely when [math]S^*U[/math] is self-adjoint, where [math]S_{ij}={\rm sgn}(U_{ij})[/math], and when

[[math]] Tr(S^*UA^2)+\sum_{ij}\frac{Im\left[(UA)_{ij}\overline{S}_{ij}\right]^2}{|U_{ij}|}\leq0 [[/math]]

holds, for any anti-hermitian matrix [math]A\in M_N(\mathbb C)[/math].

Show Proof

According to Theorem 12.6 and Proposition 12.14, the local maximizer condition requires [math]X=S^*U[/math] to be self-adjoint, and the following inequality to be satisfied:

[[math]] Re\left[Tr(S^*UA^2)\right]+\sum_{ij}\frac{Im\left[(UA)_{ij}\overline{S}_{ij}\right]^2}{|U_{ij}|}\leq0 [[/math]]

Now observe that since both [math]X[/math] and [math]A^2[/math] are self-adjoint, we have:

[[math]] \begin{eqnarray*} Re\left[Tr(XA^2)\right] &=&\frac{1}{2}\left[Tr(XA^2)+Tr(A^2X)\right]\\ &=&Tr(XA^2) \end{eqnarray*} [[/math]]

Thus we can remove the real part, and we obtain the inequality in the statement.

■

As a comment here, the above computations can be of course interpreted by using more advanced differential geometric language. The unitary group [math]U_N[/math] is a Lie group, and its tangent space at [math]U\in U_N[/math] is isomorphic to the corresponding Lie algebra, which consists of the anti-hermitian matrices [math]A\in M_N(\mathbb C)[/math]. With this picture in hand, our formulae for [math]f'(0)[/math] translate into the fact that the gradient of the 1-norm is given by:

[[math]] \nabla||U||_1=\frac{1}{2}(S-US^*U) [[/math]]

Regarding now the second derivative, [math]f''(0)[/math], our computations here provide us with a formula for the Hessian of the 1-norm. Indeed, with the change of variables [math]A=iB[/math] on the tangent space, the Hessian [math]H[/math] of the 1-norm is given by the following formula, where [math]\Phi(U,iA)[/math] is the quantity appearing in Theorem 12.15:

[[math]] \lt B,H(B) \gt =-\Phi(U,B) [[/math]]

Getting back to Theorem 12.15 as stated, the story is of course not over there. In order to further improve this result, we will need the following standard fact:

Proposition

For a self-adjoint [math]X\in M_N(\mathbb C)[/math], the following are equivalent:

• [math]Tr(XA^2)\leq0[/math], for any anti-hermitian matrix [math]A\in M_N(\mathbb C)[/math].
• [math]Tr(XB^2)\geq0[/math], for any hermitian matrix [math]B\in M_N(\mathbb C)[/math].
• [math]Tr(XC)\geq0[/math], for any positive matrix [math]C\in M_N(\mathbb C)[/math].
• [math]X\geq0[/math].

Show Proof

These equivalences are well-known, the proof being as follows:

[math](1)\implies(2)[/math] follows by taking [math]B=iA[/math].

[math](2)\implies(3)[/math] follows by taking [math]C=B^2[/math].

[math](3)\implies(4)[/math] follows by diagonalizing [math]X[/math], and then taking [math]C[/math] to be diagonal.

[math](4)\implies(1)[/math] is clear as well, because with [math]Y=\sqrt{X}[/math] we have:

[[math]] \begin{eqnarray*} Tr(XA^2) &=&Tr(Y^2A^2)\\ &=&Tr(YA^2Y)\\ &=&-Tr((YA)(YA)^*)\\ &\leq&0 \end{eqnarray*} [[/math]]

Thus, the above four conditions are indeed equivalent.

■

Following , we can now formulate a final result on the subject, as follows:

Theorem

Given [math]U\in U_N[/math], set [math]S_{ij}={\rm sgn}(U_{ij})[/math], and let:

[[math]] X=S^*U [[/math]]

Then [math]U[/math] locally maximizes the [math]1[/math]-norm on [math]U_N[/math] precisely when [math]X\geq0[/math], and when

[[math]] \Phi(U,B)=Tr(XB^2)-\sum_{ij}\frac{Re\left[(UB)_{ij}\overline{S}_{ij}\right]^2}{|U_{ij}|} [[/math]]

is positive, for any hermitian matrix [math]B\in M_N(\mathbb C)[/math].

Show Proof

This follows from Theorem 12.15, by setting [math]A=iB[/math], and by using Proposition 12.16, which shows that we must have indeed [math]X\geq0[/math].

■

12d. The conjecture

In relation with the above, quite surprisingly, the basic real almost Hadamard matrix [math]K_N[/math] is not an almost Hadamard matrix in the complex sense. That is, while [math]K_N/\sqrt{N}[/math] locally maximizes the 1-norm on [math]O_N[/math], it does not do so over [math]U_N[/math]. Moreover, as we will see in a moment, the same happens for the other basic real almost Hadamard matrices discussed in chapter 3, such as the circulant ones, and the 2-entry ones studied there. Thus, the situation in the complex case is drastically different from the one in the real case, and we are led in this way to the following remarkable statement: \begin{conjecture}[Almost Hadamard conjecture (AHC)] Any local maximizer of the [math]1[/math]-norm on [math]U_N[/math],

[[math]] ||U||_1=\sum_{ij}|U_{ij}| [[/math]]

must be a global maximizer, i.e. must be a rescaled Hadamard matrix. \end{conjecture}

In other words, our conjecture is that, in the complex setting, almost Hadamard implies Hadamard. This would be something very useful, because we would have here a new approach to the complex Hadamard matrices, which is analytic and local. Which new approach, importantly, could potentially shed some new light on all the Hadamard matrix problems, be them real or complex, including the HC and CHC.

In order to explain all this, and the evidence that we have for the above conjecture, let us study more in detail the quantity [math]\Phi(U,B)[/math] from Theorem 12.17, namely:

[[math]] \Phi(U,B)=Tr(XB^2)-\sum_{ij}\frac{Re\left[(UB)_{ij}\overline{S}_{ij}\right]^2}{|U_{ij}|} [[/math]]

As a first observation here, we have the following result:

Proposition

With [math]S_{ij}=sgn(U_{ij})[/math] and [math]X=S^*U[/math] as above, we have

[[math]] \Phi(U,B)=\Phi(U,B+D) [[/math]]

for any [math]D\in M_N(\mathbb R)[/math] diagonal.

Show Proof

The matrices [math]X,B,D[/math] being all self-adjoint, we have:

[[math]] (XBD)^*=DBX [[/math]]

Thus when computing [math]\Phi(U,B+D)[/math], the trace term decomposes as follows:

[[math]] \begin{eqnarray*} Tr(X(B+D)^2) &=&Tr(XB^2)+Tr(XBD)+Tr(XDB)+Tr(XD^2)\\ &=&Tr(XB^2)+Tr(XBD)+Tr(DBX)+Tr(XD^2)\\ &=&Tr(XB^2)+2Re[Tr(XBD)]+Tr(XD^2) \end{eqnarray*} [[/math]]

Regarding now the second term, in order to compute it, observe that with the notation [math]D=diag(\lambda_1,\ldots,\lambda_N)[/math], with [math]\lambda_i\in\mathbb R[/math], we have the following formula:

[[math]] (UD)_{ij}\overline{S}_{ij} =U_{ij}\lambda_j\overline{S}_{ij} =\lambda_j|U_{ij}| [[/math]]

Thus the second term decomposes as follows:

[[math]] \begin{eqnarray*} &&\sum_{ij}\frac{Re\left[(UB+UD)_{ij}\overline{S}_{ij}\right]^2}{|U_{ij}|}\\ &=&\sum_{ij}\frac{Re\left[(UB)_{ij}\overline{S}_{ij}+\lambda_j|U_{ij}|\right]^2}{|U_{ij}|}\\ &=&\sum_{ij}\frac{\left[Re\left[(UB)_{ij}\overline{S}_{ij}\right]+\lambda_j|U_{ij}|\right]^2}{|U_{ij}|}\\ &=&\sum_{ij}\frac{Re\left[(UB)_{ij}\overline{S}_{ij}\right]^2}{|U_{ij}|}+2\sum_{ij}\lambda_jRe\left[(UB)_{ij}\overline{S}_{ij}\right]+\sum_{ij}\lambda_j^2|U_{ij}| \end{eqnarray*} [[/math]]

Now observe that the middle term in this expression is given by:

[[math]] \begin{eqnarray*} 2\sum_{ij}\lambda_jRe\left[(UB)_{ij}\overline{S}_{ij}\right] &=&2Re\left[\sum_{ij}\lambda_j(UB)_{ij}\overline{S}_{ij}\right]\\ &=&2Re\left[\sum_{ij}(S^*)_{ji}(UB)_{ij}D_{jj}\right]\\ &=&2Re[Tr(XBD)] \end{eqnarray*} [[/math]]

As for the term on the right in the above expression, this is given by:

[[math]] \begin{eqnarray*} \sum_{ij}\lambda_j^2|U_{ij}| &=&\sum_{ij}\lambda_j^2\overline{S}_{ij}U_{ij}\\ &=&\sum_{ij}\overline{S}_{ij}(UD^2)_{ij}\\ &=&Tr(XD^2) \end{eqnarray*} [[/math]]

Thus when doing the substraction we obtain [math]\Phi(U,B+D)=\Phi(U,B)[/math], as claimed.

■

Observe that with [math]B=0[/math] we obtain [math]\Phi(U,D)=0[/math], for any [math]D\in M_N(\mathbb R)[/math] diagonal, so the inequality is Theorem 12.17 is an equality, when [math]B[/math] is diagonal. Getting now to the real thing, we have the following result, providing the first piece of evidence for the AHC:

Theorem

Consider the matrix [math]U=(2\mathbb I_N-N1_N)/N[/math]. Assuming that a matrix [math]B\in M_N(\mathbb R)[/math] is symmetric and satisfies [math]UB=\lambda B[/math], we have

[[math]] \Phi(U,B)=\lambda\cdot\frac{N-4}{2}\left[Tr(B^2)+\frac{\lambda N}{N-2}\sum_iB_{ii}^2\right] [[/math]]

and in particular, [math]K_N=\sqrt{N}U[/math] is not complex AHM at [math]N\neq4[/math], because:

• For [math]B=\mathbb I_N[/math] we have the formula
  [[math]] \Phi(U,B)=\frac{N^2(N-1)(N-4)}{2(N-2)} [[/math]]
  and this quantity is negative at [math]N=3[/math].
• For [math]B\in M_N(\mathbb R)[/math] nonzero, symmetric, with [math]B\,\mathbb I_N=0[/math], [math]diag(B)=0[/math] we have
  [[math]] \Phi(U,B)=\left(2-\frac{N}{2}\right)Tr(B^2) [[/math]]
  and this quantity is negative at [math]N\geq5[/math].

Show Proof

With [math]U\in O_N[/math], [math]B\in M_N(\mathbb R)[/math], the formula in Theorem 12.17 reads:

[[math]] \Phi(U,B)=Tr(S^tUB^2)-\sum_{ij}\frac{(UB)_{ij}^2}{|U_{ij}|} [[/math]]

Asusming now [math]U=\frac{1}{N}(2\mathbb I_N-N1_N)[/math] and [math]UB=\lambda B[/math], this formula becomes:

[[math]] \Phi(U,B)=\lambda\left[Tr(S^tB^2)-\lambda N\sum_{ij}\frac{B_{ij}^2}{|2-N\delta_{ij}|}\right] [[/math]]

Now observe that in our case, we have the following formula:

[[math]] \mathbb I_NB=\frac{N}{2}(U+1_N)B=\frac{(\lambda+1)N}{2}B [[/math]]

Thus the trace term is given by the following formula:

[[math]] \begin{eqnarray*} Tr(S^tB^2) &=&Tr\left[(\mathbb I_N-21_N)B^2\right]\\ &=&\left(\frac{(\lambda+1)N}{2}-2\right)Tr(B^2) \end{eqnarray*} [[/math]]

Regarding now the sum on the right, this can be computed as follows:

[[math]] \begin{eqnarray*} \sum_{ij}\frac{B_{ij}^2}{|2-N\delta_{ij}|} &=&\sum_{ij}B_{ij}^2\left(\frac{1}{2}+\left(\frac{1}{N-2}-\frac{1}{2}\right)\delta_{ij}\right)\\ &=&\sum_{ij}B_{ij}^2\left(\frac{1}{2}-\frac{N-4}{2(N-2)}\delta_{ij}\right)\\ &=&\frac{1}{2}Tr(B^2)-\frac{N-4}{2(N-2)}\sum_iB_{ii}^2 \end{eqnarray*} [[/math]]

We obtain the following formula, which gives the one in the statement:

[[math]] \Phi(U,B)=\lambda\left[\left(\frac{(\lambda+1)N}{2}-2-\frac{\lambda N}{2}\right)Tr(B^2)+\frac{\lambda N(N-4)}{2(N-2)}\sum_iB_{ii}^2\right] [[/math]]

We can now prove our various results, as follows:

(1) For [math]B=\mathbb I_N[/math] we have [math]\lambda=1[/math], and we obtain, as claimed:

[[math]] \Phi(U,B) =\frac{N-4}{2}\left[N^2+\frac{N^2}{N-2}\right] =\frac{N^2(N-4)(N-1)}{2(N-2)} [[/math]]

(2) For [math]B\in M_N(\mathbb R)[/math] nonzero, symmetric, and satisfying [math]B\,\mathbb I_N=0[/math] and [math]diag(B)=0[/math], we have [math]\lambda=-1[/math], and we obtain, as claimed:

[[math]] \Phi(U,B)=\left(2-\frac{N}{2}\right)Tr(B^2) [[/math]]

It remains to prove that matrices [math]B[/math] as in the statement exist, at any [math]N\geq5[/math]. As a first remark, such matrices cannot exist at [math]N=2,3[/math]. At [math]N=4[/math], however, we have solutions, which are as follows, with [math]x+y+z=0[/math], not all zero:

[[math]] B=\begin{pmatrix} 0&x&y&z\\ x&0&z&y\\ y&z&0&x\\ z&y&x&0 \end{pmatrix} [[/math]]

At [math]N\geq5[/math] now, we can simply use this matrix, completed with [math]0[/math] entries, and we are led to the conclusion in the statement.

■

Let us go back now to the inequality in Theorem 12.17. When [math]U[/math] is a rescaled complex Hadamard matrix we have of course equality, and in addition, the following happens:

Proposition

For a rescaled complex Hadamard matrix, a stronger version of the inequality in Theorem 12.17, namely [math]\Phi(U,B)\geq0[/math] with

[[math]] \Phi(U,B)=Tr(XB^2)-\sum_{ij}\frac{Re\left[(UB)_{ij}\overline{S}_{ij}\right]^2}{|U_{ij}|} [[/math]]

holds, with the real part replaced by the absolute value.

Show Proof

Indeed, for a rescaled Hadamard matrix [math]U=H/\sqrt{N}[/math] we have:

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

Thus [math]X=\sqrt{N}1_N[/math]. We therefore obtain the following estimate:

[[math]] \begin{eqnarray*} \Phi(U,B) &=&\sqrt{N}\left[Tr(B^2)-\sum_{ij}Re\left[(UB)_{ij}\overline{S}_{ij}\right]^2\right]\\ &\geq&\sqrt{N}\left[Tr(B^2)-\sum_{ij}|(UB)_{ij}\overline{S}_{ij}|^2\right]\\ &=&\sqrt{N}\left[Tr(B^2)-\sum_{ij}|(UB)_{ij}|^2\right]\\ &=&\sqrt{N}\left[Tr(B^2)-Tr(UB^2U^*)\right]\\ &=&0 \end{eqnarray*} [[/math]]

But this proves our claim, and we are done.

■

In relation with the Tadej-\.Zyczkowski notion of defect , we have:

Theorem

For a rescaled complex Hadamard matrix, the space

[[math]] E_U=\left\{B\in M_N(\mathbb C)\Big|B=B^*,\Phi(U,B)=0\right\} [[/math]]

is isomorphic, via [math]B\to[(UB)_{ij}\overline{U}_{ij}]_{ij}[/math], to the following space:

[[math]] D_U=\left\{A \in M_N(\mathbb R)\Big|\sum_k\bar{U}_{ki}U_{kj}(A_{ki}-A_{kj})=0,\forall i,j\right\} [[/math]]

In particular the two “defects” [math]\dim_\mathbb RE_U[/math] and [math]\dim_\mathbb RD_U[/math] coincide.

Show Proof

Since a self-adjoint matrix [math]B\in M_N(\mathbb C)[/math] belongs to [math]E_U[/math] precisely when the only inequality in the proof of Proposition 12.21 is saturated, we have:

[[math]] E_U=\left\{B\in M_N(\mathbb C)\Big|B=B^*,Im\left[(UB)_{ij}\overline{U}_{ij}\right]=0,\forall i,j\right\} [[/math]]

The condition on the right tells us that the matrix [math]A=(UB)_{ij}\bar{U}_{ij}[/math] must be real. Now since the construction [math]B\to A[/math] is injective, we obtain an isomorphism, as follows:

[[math]] E_U\simeq\left\{A\in M_N(\mathbb R)\Big|A_{ij}=(UB)_{ij}\bar{U}_{ij}\implies B=B^*\right\} [[/math]]

Our claim is that the space on the right is [math]D_U[/math]. Indeed, let us pick [math]A\in M_N(\mathbb R)[/math]. The condition [math]A_{ij}=(UB)_{ij}\bar{U}_{ij}[/math] is then equivalent to:

[[math]] (UB)_{ij}=NU_{ij}A_{ij} [[/math]]

Thus in terms of the matrix [math]C_{ij}=U_{ij}A_{ij}[/math] we have [math](UB)_{ij}=NC_{ij}[/math], and so:

[[math]] UB=NC [[/math]]

Thus we have [math]B=NU^*C[/math], and we can now perform the study of the self-adjointness condition [math]B=B^*[/math], as follows:

[[math]] \begin{eqnarray*} B=B^* &\iff&U^*C=C^*U\\ &\iff&\sum_k\bar{U}_{ki}C_{kj}=\sum_k\bar{C}_{ki}U_{kj},\forall i,j\\ &\iff&\sum_k\bar{U}_{ki}U_{kj}A_{kj}=\sum_k\bar{U}_{ki}A_{ki}U_{kj},\forall i,j \end{eqnarray*} [[/math]]

Thus we have reached to the condition defining [math]D_U[/math], and we are done.

■

Regarding now the known verifications of the AHC, these basically concern the natural “candidates” coming from Theorem 12.10, as well as some straightforward complex generalizations of these candidates. All this is quite technical, and generally speaking, we refer here to . As a first illustration, however, which is of theoretical importance, in the circulant orthogonal case, we have the following result, from :

Proposition

If [math]U\in O_N[/math] is circulant, [math]U_{ij}=\gamma_{j-i}[/math], we have

[[math]] \Phi(U,\mathbb I_N)=Nu(Ns-uw) [[/math]]

where [math]u,s,w[/math] are the row sums of [math]U,S[/math] and [math]W_{ij}=\frac{1}{|U_{ij}|}[/math]. Thus [math]\Phi(U,\mathbb I_N) \lt 0[/math] when

[[math]] \mathbb E({\rm sgn}(\gamma_i)) \lt \mathbb E(\gamma_i)\,\mathbb E\left(\frac{1}{|\gamma_i|}\right) [[/math]]

where the symbol [math]\mathbb E[/math] stands as usual for “average”.

Show Proof

We have [math]U\mathbb I_N=u\mathbb I_N[/math], which gives the following formula:

[[math]] Tr(S^tU\mathbb I_N^2)=NuTr(S^t\mathbb I_N)=N^2us [[/math]]

Similarly, once again from [math]U\mathbb I_N=u\mathbb I_N[/math], we obtain the following formula:

[[math]] \sum_{ij}\frac{(U\mathbb I_N)_{ij}^2}{|U_{ij}|}=\sum_{ij}\frac{u^2}{|U_{ij}|}=Nu^2w [[/math]]

By substracting, we obtain the formula in the statement, which gives the result.

■

Here is another exclusion criterion, also from , which is useful as well:

Proposition

If [math]U\in U_N[/math] is circulant, [math]U_{ij}=\gamma_{i-j}[/math], and self-adjoint, we have

[[math]] \Phi(U,U)=N\left(-\frac{1}{|\gamma_0|}+\sum_i|\gamma_i|\right) [[/math]]

and so [math]\Phi(U,U) \lt 0[/math] when [math]\sum_i|\gamma_i| \lt 1/|\gamma_0|[/math].

Show Proof

Since [math]U[/math] is circulant and self-adjoint, we have [math]U=Fdiag(\beta)F^*[/math], for some vector [math]\beta\in\{\pm 1\}^N[/math]. The first term in the expression of [math]\Phi(U,U)[/math] reads:

[[math]] Tr[S^*U\cdot U^2]=\sum_{ij}|U_{ij}|=N\sum_i|\gamma_i| [[/math]]

For the second term in the formula of [math]\Phi[/math], we have the following formula:

[[math]] S_{ii}={\rm sgn}(\gamma_0)={\rm sgn}\left(\sum_i\beta_i\right)\in\{\pm1\} [[/math]]

We therefore obtain the following formula:

[[math]] \sum_{ij}\frac{Re[(U^2)_{ij}\bar S_{ij}]^2}{|U_{ij}|}=\sum_i\frac{1}{|\gamma_0|}=\frac{N}{|\gamma_0|} [[/math]]

But this leads to the conclusion in the statement.

■

Still following , here is now a more advanced result, also in the circulant self-adjoint case, making this time use of a random derivative method:

Theorem

If [math]U\in U_N[/math] is circulant, [math]U_{ij}=\gamma_{j-i}[/math], and self-adjoint, we have

[[math]] \mathbb E(\Phi(U,B))=N\sum_i|\gamma_i|-\frac{1}{2}\left(\frac{1}{|\gamma_0|}+\frac{1-e}{|\gamma_{N/2}|}+\sum_i\frac{1}{|\gamma_i|}\right) [[/math]]

where [math]e=0,1[/math] is the parity of [math]N[/math] and [math]\mathbb E[/math] denotes the expectation with respect to the uniform measure on the set of circulant self-adjoint unitary matrices [math]B[/math].

Show Proof

Since [math]B[/math] is circulant, this matrix is Fourier-diagonal. That is, we can diagonalize it with the help of the normalized Fourier matrix [math]F=F_N/\sqrt{N}[/math], as follows:

[[math]] B=Fdiag(\alpha_i) F^* [[/math]]

The requirement that [math]B[/math] is unitary and self-adjoint amounts then to [math]\alpha_i=\pm 1[/math]. The expectation is taken in the probability space where the random variables [math]\alpha_i[/math] are i.i.d., with symmetric Bernoulli distributions [math](\delta_{-1}+\delta_1)/2[/math]. In particular, we have:

[[math]] \mathbb E[\alpha_i\alpha_j]=\delta_{ij} [[/math]]

By using [math]B^2=1_N[/math], the first term in the expression of [math]\Phi(U,B)[/math] reads:

[[math]] Tr(S^*UB^2) =Tr(S^*U) =\sum_{ij}|U_{ij}| =N\sum_i|\gamma_i| [[/math]]

For the second term in the formula of [math]\Phi[/math], observe first that we have:

[[math]] Re[(UB)_{ij}\bar{S}_{ij}]^2=\frac{1}{4}\left[(UB)_{ij}^2\bar{S}_{ij}^2+ \overline{(UB)}_{ij}^2S_{ij}^2+2(UB)_{ij}\overline{(UB)}_{ij}\right] [[/math]]

We have the following computation, by using the formula [math]\mathbb E[\alpha_i\alpha_j]=\delta_{ij}[/math]:

[[math]] \begin{eqnarray*} \mathbb E\left[(UB)_{ij}^2\right] &=&\mathbb E\left[(F diag(q) diag(\alpha)F^*)^2_{ij}\right]\\ &=&\frac{1}{N^2}\sum_{kl}w^{(k+l)(i-j)}q_kq_l\mathbb E(\alpha_k\alpha_l)\\ &=&\frac{1}{N^2}\sum_{kl}w^{(k+l)(i-j)}q_kq_l\delta_{kl}\\ &=&\frac{1}{N^2}\sum_kw^{2k(i-j)} \end{eqnarray*} [[/math]]

We therefore obtain the following formula, for the above quantity:

[[math]] \mathbb E\left[(UB)_{ij}^2\right]=\begin{cases} \frac{1}{N}&\quad\ {\rm if}\ 2(i-j)=0\ ({\rm mod}\ N)\\ 0 &\quad {\rm otherwise} \end{cases} [[/math]]

Similarly, we have the following formula, for the last term:

[[math]] \begin{eqnarray*} \mathbb E\left[(UB)_{ij}\overline{(UB)}_{ij}\right] &=&\frac{1}{N^2}\sum_{kl}w^{(k-l)(i-j)}q_k\bar q_l\mathbb E(\alpha_k\alpha_l)\\ &=&\frac{1}{N^2}\sum_k|q_k|^2\\ &=&\frac{1}{N} \end{eqnarray*} [[/math]]

Since in both the cases [math]i=j[/math] and [math]i=j+N/2[/math], when [math]N[/math] is even, we have [math]S_{ij}\in\{\pm 1\}[/math], the above two formulae are all that we need, and we obtain the following formula:

[[math]] \mathbb E\left[Re[(UB)_{ij}\bar S_{ij}]^2\right]=\frac{1}{4}\left[\frac{2\delta_{ij}}{N}+\frac{2(1-e)\delta_{i,j+N/2}}{N}+\frac{2}{N}\right] [[/math]]

Now by summing over [math]i,j[/math], and taking into account as well the first term in the expression of [math]\Phi(U,B)[/math], computed above, we obtain the formula in the statement.

■

In the orthogonal case now, we have a similar result, also from , as follows:

Theorem

If [math]U\in O_N[/math] is circulant, [math]U_{ij}=\gamma_{j-i}[/math], and symmetric, we have

[[math]] \mathbb E(\Phi(U,B))=N\sum_i |\gamma_i| - \left( \frac{1}{|\gamma_0|} +\frac{1-e}{|\gamma_{N/2}|} + \frac{N-2+e}{N}\sum_i \frac{1}{|\gamma_i|}\right) [[/math]]

where [math]e=0,1[/math] is the parity of [math]N[/math] and [math]\mathbb E[/math] denotes the expectation with respect to the uniform measure on the set of circulant symmetric orthogonal matrices [math]B[/math].

Show Proof

As before, in the proof of Theorem 12.25, the expectation is taken with respect to the distribution of the eigenvalues [math]\alpha_0,\ldots,\alpha_{N-1}=\pm 1[/math] of the matrix [math]B[/math], which are now, in the present real case, subject to the following extra condition:

[[math]] \alpha_i=\alpha_{-i} [[/math]]

The first term in the expression of [math]\Phi(U,B)[/math] is then equal to [math]N \sum_i |\gamma_i|[/math]. For the second term in [math]\Phi[/math], we need the following covariance term, in the present real case:

[[math]] \mathbb E(\alpha_k\alpha_l)=\begin{cases} 1 &\quad \text{ if } k \pm l = 0\\ 0 &\quad \text{ otherwise} \end{cases} [[/math]]

Since all quantities are real in this case, we have the following formula:

[[math]] \begin{eqnarray*} \mathbb E\left[(UB)_{ij}^2\right] &=&\frac{1}{N^2}\sum_{kl}w^{(k+l)(i-j)}q_kq_l \mathbb E(\alpha_k\alpha_l)\\ &=&\frac{1}{N^2}\sum_{kl}w^{(k+l)(i-j)}q_kq_l(\delta_{kl}+\delta_{k,-l}-\delta_{2k,2l,0})\\ &=&\frac{1}{N^2}\left[\sum_kw^{2k(i-j)}q_k^2+\sum_kq_kq_{-k}-q_0^2-(1-e)q_{N/2}^2\right] \\ &=&\frac{1}{N^2}\left[N\delta_{2i,2j}+N-2+e\right] \end{eqnarray*} [[/math]]

We have then the following formula:

[[math]] \sum_{ij} N^{-1} |U_{ij}|^{-1} \delta_{2i,2j} = \sum_k |\gamma_{k}|^{-1} \delta_{2k,0} = \frac{1}{|\gamma_0|} + \frac{1-e}{|\gamma_{N/2}|} [[/math]]

On the other hand, we have as well the following formula:

[[math]] \sum_{ij} N^{-2}(N-2+e) |U_{ij}|^{-1} = \frac{N-2+e}{N} \sum_{i} \frac{1}{|\gamma_i|} [[/math]]

Now by putting everything together, gives the formula in the statement.

■

As an illustration for the above methods, we can now go back to the matrices in Theorem 12.20, and find a better proof for the fact that these matrices are not complex AHM. Indeed, we have the following result, which basically solves the problem:

Proposition

With [math]U=\frac{1}{N}(2\mathbb I_N-N1_N)[/math] we have the formula

[[math]] \mathbb E(\Phi(U,B))=\frac{4-N}{2}\left(N-4-\frac{2+e}{N-2}\right) [[/math]]

where [math]e=0,1[/math] is the parity of [math]N[/math], and where [math]B[/math] varies over the space of orthogonal circulant symmetric matrices. This quantity equals [math]-2,0,0,-\frac{3}{2},-\frac{18}{5},\ldots[/math] at [math]N=3,4,5,6,7\ldots[/math]

Show Proof

This follows indeed from the general formula in Theorem 12.26.

■

We can therefore recover Theorem 12.20, modulo a bit of extra work still needed at [math]N=5[/math]. Regarding the case [math]N=5[/math], here the above expectation vanishes, but by using Proposition 12.23 or Proposition 12.24, we conclude that the vanishing of the expectation must come from both positive and negative contributions, and we are done.

In fact, the above results can be used for excluding all the explicit examples of circulant AHM found in . All these verifications suggest the following conjecture:

\begin{conjecture} For any [math]U\in O_N[/math] which is circulant and symmetric we have

[[math]] \mathbb E(\Phi(U,B))\leq0 [[/math]]

where [math]B[/math] varies over the space of orthogonal circulant symmetric matrices. In addition, a similar result should hold in the unitary, circulant and self-adjoint case. \end{conjecture} This looks like a subtle Fourier analysis question. In fact, the main idea that emerges from the computations in , including the block design ones, is that of using a random derivative, pointing towards a suitable homogeneous space coset. However, no one really knows how to do that. And so we will have it as an exercise for you, reader.

General references

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