Bistochastic form

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

10a. Basic theory

In this chapter and in the next one we discuss some further analytic aspects of the complex Hadamard matrices, which this time are brand new or almost, going back to the mid 10s and onwards, and are very exciting too. The general idea is that any Hadamard matrix, real or complex, can be put in bistochastic form over the complex numbers [math]\mathbb C[/math], and with this bistochastic form looking much better than the original form.

Thus, we have here a potentially far-reaching idea, consisting in reformulating everything that we know, including our favorite questions from the real case, the HC and CHC, in complex bistochastic form. But, and here comes the second point, putting an Hadamard matrix in bistochastic form is something non-trivial, in general done by a non-explicit result of Idel-Wolf , based on some non-trivial symplectic geometry results of Biran-Entov-Polterovich and Cho , motivated by a deep conjecture of Arnold.

And isn't this exciting. We have been commenting in the last chapter on open questions in mathematics, our point being that the closer you get to classical mechanics, the better that is, for the fate of your open problem. And since in classical mechanics all roads lead to Arnold, we are probably on the right track here. Perhaps for the first time, since the beginning of this book. That is, plenty of reasons to be optimistic.

All this is however very new, and our presentation here will be quite modest. Lots of further work are needed, and it is a pity that nothing much is going on here, so far. Young reader, if I have an excellent question to recommend to you, this is the one, continuation of what will be said here. Get to know and love classical mechanics, which is the mother of everything, in mathematics and physics, than read some books of Arnold, starting with , which are a must-read anyway, no matter what mathematics or physics you want to do, and then start solving some Hadamard matrix questions, using this technology.

In order to get started now, we have already talked about bistochastic Hadamard matrices, in the real case, on several occasions, in chapters 1-4. Our first purpose will be that of carefully reviewing and extending that material, in the complex Hadamard matrix case. Let us start our discussion with the following definition:

Definition

A complex Hadamard matrix [math]H\in M_N(\mathbb C)[/math] is called bistochastic when the sums on all rows and all columns are equal,

[[math]] \sum_iH_{ij}=\sum_jH_{ij}=\lambda [[/math]]

for a certain number [math]\lambda\in\mathbb C[/math]. We denote by

[[math]] X_N^{bis}=\left\{H\in X_N\Big|\,H={\rm bistochastic}\right\} [[/math]]

the real algebraic manifold formed by such matrices.

The bistochastic Hadamard matrices are quite interesting objects, and include for instance all the circulant Hadamard matrices, that we discussed in chapter 9. Indeed, assuming that [math]H_{ij}=\xi_{j-i}[/math] is circulant, all rows and columns sum up to [math]\lambda=\sum_i\xi_i[/math]:

[[math]] \sum_i\xi_{j-i}=\sum_j\xi_{j-i}=\sum_i\xi_i [[/math]]

We will be back to this, in a moment. Let us begin, however, with some considerations regarding the real case. Our point here is that the real Hadamard matrices often “look better” in complex bistochastic form, and that there is some potentially interesting mathematics behind all this. As a first and trivial remark, the first Walsh matrix [math]W_2=F_2[/math] looks better in complex bistochastic form, modulo the standard equivalence relation:

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

To be more precise, the matrix on the right, while having the slight disadvantage of being complex instead of real, is something very nice, circulant and symmetric. Regarding the second Walsh matrix [math]W_4=W_2\otimes W_2[/math], this looks as well better in bistochastic form, because it becomes in this way equivalent to [math]K_4[/math], the most beautiful matrix ever:

[[math]] \begin{eqnarray*} W_4&=&\begin{pmatrix}1&1&1&1\\ 1&-1&1&-1\\ 1&1&-1&-1\\ 1&-1&-1&1\end{pmatrix} \sim\begin{pmatrix} 1&1&1&1\\ 1&1&-1&-1\\ 1&-1&1&-1\\ 1&-1&-1&1 \end{pmatrix}\\ &\sim&\begin{pmatrix} 1&-1&-1&-1\\ 1&-1&1&1\\ 1&1&-1&1\\ 1&1&1&-1 \end{pmatrix} \sim\begin{pmatrix} -1&1&1&1\\ 1&-1&1&1\\ 1&1&-1&1\\ 1&1&1&-1 \end{pmatrix} \end{eqnarray*} [[/math]]

As before, the matrix on the right looks better than the one on the left, because it is circulant and symmetric. And all this is quite interesting, philosophically speaking. Indeed, we have here a new idea, in connection with the various questions explained in chapters 1-4, namely that of studying the real Hadamard matrices [math]H\in M_N(\pm1)[/math] by putting them in complex bistochastic form, [math]H'\in M_N(\mathbb T)[/math], and then studying these latter matrices. Let us record here, as a partial conclusion, the following simple fact:

Theorem

All Walsh matrices can be put in bistocastic form, as follows:

• The matrices [math]W_N[/math] with [math]N=4^n[/math] admit a real bistochastic form, namely:
  [[math]] W_N\sim\begin{pmatrix} -1&1&1&1\\ 1&-1&1&1\\ 1&1&-1&1\\ 1&1&1&-1 \end{pmatrix}^{\otimes n} [[/math]]
• The matrices [math]W_N[/math] with [math]N=2\times4^n[/math] admit a complex bistochastic form, namely:
  [[math]] W_N\sim\begin{pmatrix}i&1\\1&i\end{pmatrix}\otimes\begin{pmatrix} -1&1&1&1\\ 1&-1&1&1\\ 1&1&-1&1\\ 1&1&1&-1 \end{pmatrix}^{\otimes n} [[/math]]

Show Proof

This follows indeed from the above discussion.

■

Let us review now the material in chapter 9. According to the results there, and to the above-mentioned fact that circulant implies bistochastic, we have:

Theorem

The class of bistochastic Hadamard matrices is stable under permuting rows and columns, and under taking tensor products. As examples, we have:

• The circulant and symmetric forms [math]F_N'[/math] of the Fourier matrices [math]F_N[/math].
• The bistochastic and symmetric forms [math]F_G'[/math] of the Fourier matrices [math]F_G[/math].
• The circulant and symmetric Backelin matrices, having size [math]MN[/math] with [math]M|N[/math].

Show Proof

In this statement the claim regarding permutations of rows and columns is clear. Assuming now that [math]H,K[/math] are bistochastic, with sums [math]\lambda,\mu[/math], we have:

[[math]] \begin{eqnarray*} \sum_{ia}(H\otimes K)_{ia,jb} &=&\sum_{ia}H_{ij}K_{ab}\\ &=&\sum_iH_{ij}\sum_aK_{ab}\\ &=&\lambda\mu \end{eqnarray*} [[/math]]

We have as well the following computation:

[[math]] \begin{eqnarray*} \sum_{jb}(H\otimes K)_{ia,jb} &=&\sum_{jb}H_{ij}K_{ab}\\ &=&\sum_jH_{ij}\sum_bK_{ab}\\ &=&\lambda\mu \end{eqnarray*} [[/math]]

Thus, the matrix [math]H\otimes K[/math] is bistochastic as well. As for the assertions (1,2,3), we already know all this, coming from our study from from chapter 9.

■

In the above list of examples, those in (2), which are not necessarily circulant, are the key ones. Indeed, while many interesting complex Hadamard matrices, such as the usual Fourier ones [math]F_N[/math], can be put in circulant form, this is something quite exceptional, which does not work any longer when looking for instance at the general Fourier matrices [math]F_G[/math]. To be more precise, consider a finite abelian group, written as follows:

[[math]] G=\mathbb Z_{N_1}\times\ldots\times\mathbb Z_{N_k} [[/math]]

We can then consider the following matrix, with [math]F_N'[/math] standing as before for the circulant and symmetric form of the Fourier matrix [math]F_N[/math], which is equivalent to [math]F_G[/math]:

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

Now since the tensor product of circulant matrices is bistochastic, but not necessarily circulant, we can only say that this matrix [math]F_G'[/math] is bistochastic, as stated in (2) above.

As a conclusion to all this, the bistochastic complex Hadamard matrices are interesting objects, covering all the generalized Fourier matrices, up to equivalence, and which are definitely worth some study. So, let us develop now some general theory, for such matrices. As a first result, regarding the unitary bistochastic matrices in general, we have:

Proposition

The real and complex bistochastic groups, which are the sets

[[math]] B_N\subset O_N\quad,\quad C_N\subset U_N [[/math]]

consisting of matrices which are bistochastic, are isomorphic to [math]O_{N-1}[/math], [math]U_{N-1}[/math].

Show Proof

Let us pick a unitary matrix [math]F\in U_N[/math] satisfying the following condition, where [math]e_0,\ldots,e_{N-1}[/math] is the standard basis of [math]\mathbb C^N[/math], and where [math]\xi[/math] is the all-one vector:

[[math]] Fe_0=\frac{1}{\sqrt{N}}\xi [[/math]]

Observe that such matrices [math]F\in U_N[/math] exist indeed, the basic example being the normalized Fourier matrix [math]F_N/\sqrt{N}[/math]. We have then, by using the above property of [math]F[/math]:

[[math]] \begin{eqnarray*} u\xi=\xi &\iff&uFe_0=Fe_0\\ &\iff&F^*uFe_0=e_0\\ &\iff&F^*uF=diag(1,w) \end{eqnarray*} [[/math]]

Thus we have isomorphisms as in the statement, given by:

[[math]] w_{ij}\to(F^*uF)_{ij} [[/math]]

But this gives both the assertions.

■

Now back to the Hadamard matrices, we first have the following elementary result:

Proposition

For a complex Hadamard matrix [math]H\in M_N(\mathbb C)[/math], the following conditions 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].

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\mathbb T^N[/math] the rows of [math]H[/math], we have indeed:

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

[math](2)\implies(1)[/math] Consider the all-one vector [math]\xi=(1)_i\in\mathbb C^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^*H\xi=\lambda H^*\xi\\ &\implies&N^2\xi=\lambda H^*\xi\\ &\implies&N^2\xi=\bar{\lambda}H^t\xi\\ &\implies&H^t\xi=\lambda\xi \end{eqnarray*} [[/math]]

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

■

Here is another basic result, that we will need as well in what follows:

Proposition

For a complex Hadamard matrix [math]H\in M_N(\mathbb C)[/math], and a number [math]\lambda\in\mathbb C[/math] satisfying [math]|\lambda|^2=N[/math], the following are equivalent:

• We have [math]H\sim H'[/math], with [math]H'[/math] being bistochastic, with sums [math]\lambda[/math].
• [math]K_{ij}=a_ib_jH_{ij}[/math] is bistochastic with sums [math]\lambda[/math], for some [math]a,b\in\mathbb T^N[/math].
• The equation [math]Hb=\lambda\bar{a}[/math] has solutions [math]a,b\in\mathbb T^N[/math].

Show Proof

Once again, this is an elementary result, the proof being as follows:

[math](1)\iff(2)[/math] Since the permutations of the rows and columns preserve the bistochasticity condition, the equivalence [math]H\sim H'[/math] that we are looking for can be assumed to come only from multiplying the rows and columns by numbers in [math]\mathbb T[/math]. Thus, we are looking for scalars [math]a_i,b_j\in\mathbb T[/math] such that the following matrix is bistochastic with sums [math]\lambda[/math]:

[[math]] K_{ij}=a_ib_jH_{ij} [[/math]]

Thus, we are led to the conclusion that (1) and (2) are equivalent, as claimed.

[math](2)\iff(3)[/math] The row sums of the matrix [math]K_{ij}=a_ib_jH_{ij}[/math] are given by:

[[math]] \sum_jK_{ij} =\sum_ja_ib_jH_{ij} =a_i(Hb)_i [[/math]]

Thus [math]K[/math] is row-stochastic with sums [math]\lambda[/math] precisely when [math]Hb=\lambda\bar{a}[/math], and by using the equivalence in Proposition 10.5, we obtain the result.

■

Finally, here is an extension of the excess inequality from chapter 2:

Theorem

For a complex Hadamard matrix [math]H\in M_N(\mathbb C)[/math], the excess,

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

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

Show Proof

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

[[math]] \begin{eqnarray*} E(H) &=&\sum_{ij}H_{ij}\\ &=&\sum_{ij}H_{ij}\xi_j\bar{\xi}_i\\ &=&\sum_i(H\xi)_i\bar{\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 unitary, 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. Now, let us assume:

[[math]] H\xi=\lambda\xi [[/math]]

We have then [math]|\lambda|^2=N[/math], and by Proposition 10.5 we obtain the result.

■

The above result was just an introduction to what can be said about the excess, and we refer to Kharaghani-Seberry for more on all this. In what concerns us, we will be back to the excess in chapter 11 below, with some probabilistic computations.

Let us go back now to the fundamental question of putting an arbitrary Hadamard matrix in bistochastic form. As already explained in the above, we are interested in solving this question in general, and in particular in the real case, with potential complex reformulations of the HC and CHC, and other real Hadamard questions, at stake. What we know so far on this subject can be summarized as follows:

Proposition

An Hadamard matrix [math]H\in M_N(\mathbb C)[/math] can be put in bistochastic form when one of the following conditions is satisfied:

• The equations [math]|Ha|_i=\sqrt{N}[/math], with [math]i=1,\ldots,N[/math], have solutions [math]a\in\mathbb T^N[/math].
• The quantity [math]|E|[/math] attains its maximum [math]N\sqrt{N}[/math] over the equivalence class of [math]H[/math].

Show Proof

This follows indeed from Proposition 10.5 and Proposition 10.6, which altogether gives the equivalence between the two conditions in the statement.

■

Thus, we have two approaches to the problem, one algebraic, and one analytic.

10b. Idel-Wolf theorem

Let us first discuss the algebraic approach, coming from Proposition 10.8 (1). What we have there is a certain system of [math]N[/math] equations, having as unknowns [math]N[/math] real variables, namely the phases of [math]a_1,\ldots,a_N[/math]. This system is highly non-linear, but can be solved, however, via a certain non-explicit method, as explained by Idel-Wolf in . In order to discuss this material, which is quite advanced, let us begin with some preliminaries. The complex projective space appears by definition as follows:

[[math]] P^{N-1}_\mathbb C=(\mathbb C^N-\{0\})\big/ \lt x=\lambda y \gt [[/math]]

Inside this projective space, we have the Clifford torus, constructed as follows:

[[math]] \mathbb T^{N-1}=\left\{(z_1,\ldots,z_N)\in P^{N-1}_\mathbb C\Big||z_1|=\ldots=|z_N|\right\} [[/math]]

With these conventions, we have the following result, from :

Proposition

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

• There exist [math]L,R\in U_N[/math] diagonal such that the following matrix is bistochastic:
  [[math]] U'=LUR [[/math]]
• The standard torus [math]\mathbb T^N\subset\mathbb C^N[/math] satisfies:
  [[math]] \mathbb T^N\cap U\mathbb T^N\neq\emptyset [[/math]]
• The Clifford torus [math]\mathbb T^{N-1}\subset P^{N-1}_\mathbb C[/math] satisfies:
  [[math]] \mathbb T^{N-1}\cap U\mathbb T^{N-1}\neq\emptyset [[/math]]

Show Proof

These equivalences are all elementary, as follows:

[math](1)\implies(2)[/math] Assuming that [math]U'=LUR[/math] is bistochastic, which in terms of the all-1 vector [math]\xi[/math] means [math]U'\xi=\xi[/math], if we set [math]f=R\xi\in\mathbb T^N[/math] we have:

[[math]] Uf =\bar{L}U'\bar{R}f =\bar{L}U'\xi =\bar{L}\xi\in\mathbb T^N [[/math]]

Thus we have [math]Uf\in\mathbb T^N\cap U\mathbb T^N[/math], which gives the conclusion.

[math](2)\implies(1)[/math] Given [math]g\in\mathbb T^N\cap U\mathbb T^N[/math], we can define [math]R,L[/math] as follows:

[[math]] R=\begin{pmatrix}g_1\\&\ddots\\&&g_N\end{pmatrix}\quad,\quad \bar{L}=\begin{pmatrix}(Ug)_1\\&\ddots\\&&(Ug)_N\end{pmatrix} [[/math]]

With these values for [math]L,R[/math], we have then the following formulae:

[[math]] R\xi=g\quad,\quad \bar{L}\xi=Ug [[/math]]

Thus the matrix [math]U'=LUR[/math] is bistochastic, because:

[[math]] U'\xi =LUR\xi =LUg =\xi [[/math]]

[math](2)\implies(3)[/math] This is clear, because [math]\mathbb T^{N-1}\subset P^{N-1}_\mathbb C[/math] appears as the projective image of [math]\mathbb T^N\subset\mathbb C^N[/math], and so [math]\mathbb T^{N-1}\cap U\mathbb T^{N-1}[/math] appears as the projective image of [math]\mathbb T^N\cap U\mathbb T^N[/math].

[math](3)\implies(2)[/math] We have indeed the following equivalence:

[[math]] \mathbb T^{N-1}\cap U\mathbb T^{N-1}\neq\emptyset \iff\exists\lambda\neq 0,\lambda\mathbb T^N\cap U\mathbb T^N\neq\emptyset [[/math]]

But [math]U\in U_N[/math] implies [math]|\lambda|=1[/math], and this gives the result.

■

The point now is that the condition (3) above is something familiar in symplectic geometry, and known to hold for any [math]U\in U_N[/math]. Thus, following , we have:

Theorem

Any unitary matrix [math]U\in U_N[/math] can be put in bistochastic form,

[[math]] U'=LUR [[/math]]

with [math]L,R\in U_N[/math] being both diagonal, via a certain non-explicit method.

Show Proof

As already mentioned, the condition [math]\mathbb T^{N-1}\cap U\mathbb T^{N-1}\neq\emptyset[/math] in Proposition 10.9 (3) is something quite natural in symplectic geometry. To be more precise:

-- The Clifford torus [math]\mathbb T^{N-1}\subset P^{N-1}_\mathbb C[/math] is a Lagrangian submanifold.

-- The map [math]\mathbb T^{N-1}\to U\mathbb T^{N-1}[/math] is a Hamiltonian isotopy.

-- A non-trivial result of Biran-Entov-Polterovich and Cho states that [math]\mathbb T^{N-1}[/math] cannot be displaced from itself via a Hamiltonian isotopy.

Thus, the results in , tells us that [math]\mathbb T^{N-1}\cap U\mathbb T^{N-1}\neq\emptyset[/math] holds indeed, for any [math]U\in U_N[/math]. We therefore obtain the result, via Proposition 10.9. See Idel-Wolf .

■

In relation now with our Hadamard matrix questions, we have:

Theorem

Any complex Hadamard matrix can be put in bistochastic form, up to the standard equivalence relations for such matrices.

Show Proof

This follows indeed from Theorem 10.10, because if [math]H=\sqrt{N}U[/math] is Hadamard then so is [math]H'=\sqrt{N}U'[/math], and with the remark that, in what regards the equivalence relation, we just need the multiplication of the rows and columns by scalars in [math]\mathbb T[/math].

■

There are many further things that can be said here. As explained in , the various technical results from , show that in the generic, “transverse” situation, there are at least [math]2^{N-1}[/math] ways of putting a unitary matrix [math]U\in U_N[/math] in bistochastic form, and this modulo the obvious transformation [math]U\to zU[/math], with [math]|z|=1[/math].

Thus, the question of explicitely putting the Hadamard matrices [math]H\in M_N(\mathbb C)[/math] in bistochastic form remains open, and open as well is the question of finding a simpler proof for the fact that this can be done indeed, without using , .

10c. Complex glow

Regarding the above questions, a possible approach comes from the excess result from Theorem 10.7. Indeed, we know from there that the excess [math]E(H)=\sum_{ij}H_{ij}[/math] satisfies the following inequality, with equality precisely when [math]H[/math] is bistochastic:

[[math]] |E(H)|\leq N\sqrt{N} [[/math]]

Thus, in order to put a complex Hadamard matrix [math]H\in M_N(\mathbb T)[/math] in bistochastic form, it is enough to show that the law of [math]|E|[/math] over the equivalence class of [math]H[/math] has [math]N\sqrt{N}[/math] as upper support bound. In order to comment on this, let us first formulate:

Definition

The glow of [math]H\in M_N(\mathbb C)[/math] is the measure [math]\mu\in\mathcal P(\mathbb C)[/math] given by:

[[math]] \int_\mathbb C\varphi(x)d\mu(x)=\int_{\mathbb T^N\times\mathbb T^N}\varphi\left(\sum_{ij}a_ib_jH_{ij}\right)d(a,b) [[/math]]

That is, the glow is the law of the following quantity, called excess

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

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

Here [math]H[/math] can be any complex matrix, but the equivalence relation is the one for the complex Hadamard matrices. To be more precise, let us call two complex matrices [math]H,K\in M_N(\mathbb C)[/math] Hadamard equivalent if one can pass from one to the other by permuting rows and columns, or by multiplying the rows and columns by numbers in [math]\mathbb T[/math]. Now since permuting rows and columns does not change the quantity [math]E=\sum_{ij}H_{ij}[/math], we can restrict attention from the full equivalence group [math]G=(S_N\rtimes\mathbb T^N)\times(S_N\rtimes\mathbb T^N)[/math] to the smaller group [math]G'=\mathbb T^N\times\mathbb T^N[/math], and we obtain in this way the measure [math]\mu[/math] in Definition 10.12.

As in the real case, the terminology comes from a picture of the following type, with the stars [math]*[/math] representing the entries of our matrix, and with the switches being supposed now to be continuous, randomly changing the phases of the concerned entries:

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

In short, what we have here is a complex generalization of the Gale-Berlekamp game , , and this is where a main motivation for studying the glow comes from.

As a first remark, simplifying our study, exactly as in the real case, we are in fact interested in computing a real measure, due to the following simple fact:

Proposition

With [math]E=\sum_{ij}H_{ij}[/math], the laws [math]\mu,\mu^+[/math] of the variables

[[math]] E,|E| [[/math]]

over the torus [math]\mathbb T^N\times\mathbb T^N[/math] are related by the formula

[[math]] \mu=\varepsilon\times\mu^+ [[/math]]

where [math]\times[/math] is the multiplicative convolution, and [math]\varepsilon[/math] is the uniform measure on [math]\mathbb T[/math].

Show Proof

By definition of the excess [math]E[/math], as being the total sum of the entries of the matrix, we have the following equality, valid for any [math]\lambda\in\mathbb T[/math]:

[[math]] E(\lambda H)=\lambda E(H) [[/math]]

We conclude from this that [math]\mu=law(E)[/math] is invariant under the action of [math]\mathbb T[/math]. Thus [math]\mu[/math] must decompose as follows, with [math]\mu^+[/math] being a certain probability measure on [math][0,\infty)[/math]:

[[math]] \mu=\varepsilon\times\mu^+ [[/math]]

But, according to our definitions, this measure [math]\mu^+[/math] is precisely the measure in the statement, that of variable [math]|E|[/math], and this gives the result.

■

In particular, we can see from the above result that the glow is invariant under rotations. With this observation made, we can formulate the following result:

Theorem

The glow of any Hadamard matrix [math]H\in M_N(\mathbb C)[/math], or more generally of any [math]H\in\sqrt{N}U_N[/math], satisfies the following conditions, where [math]\mathbb D[/math] is the unit disk,

[[math]] N\sqrt{N}\,\mathbb T\subset supp(\mu)\subset N\sqrt{N}\,\mathbb D [[/math]]

with the inclusion on the right coming from Cauchy-Schwarz, and with the inclusion on the left corresponding to the fact that [math]H[/math] can be put in bistochastic form.

Show Proof

We have two inclusions to be proved, the idea being as follows:

(1) The inclusion on the right comes indeed from Cauchy-Schwarz, as explained in the proof of Theorem 10.7, with the remark that the computation there only uses the fact that the rescaled matrix [math]U=H/\sqrt{N}[/math] is unitary.

(2) Regarding now the inclusion on the left, we know from Theorem 10.10 that [math]H[/math] can be put in bistochastic form. According to Proposition 10.8, this tells us that we have:

[[math]] N\sqrt{N}\,\mathbb T\cap supp(\mu)\neq\emptyset [[/math]]

Now by using the rotational invariance of the glow, and hence of its support, coming from Proposition 10.13, we obtain from this:

[[math]] N\sqrt{N}\,\mathbb T\subset supp(\mu) [[/math]]

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

■

The challenging question now is that of proving the above result, which comes from heavy symplectic geometry, by using standard probabilistic techniques. Indeed, as explained in chapter 9, in the context of the questions investigated there, the support of a real measure can be recaptured from the moments, by computing a limit. Thus, knowing the moments of the glow well enough would solve the problem.

Regarding these moments, the general formula is as follows:

Proposition

For [math]H\in M_N(\mathbb T)[/math] the even moments of [math]|E|[/math] are given by

[[math]] \int_{\mathbb T^N\times\mathbb T^N}|E|^{2p}=\sum_{[i]=[k],[j]=[l]}\frac{H_{i_1j_1}\ldots H_{i_pj_p}}{H_{k_1l_1}\ldots H_{k_pl_p}} [[/math]]

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

Show Proof

We have indeed the following computation:

[[math]] \begin{eqnarray*} \int_{\mathbb T^N\times\mathbb T^N}|E|^{2p} &=&\int_{\mathbb T^N\times\mathbb T^N}\Big|\sum_{ij}H_{ij}a_ib_j\Big|^{2p}\\ &=&\int_{\mathbb T^N\times\mathbb T^N}\left(\sum_{ijkl}\frac{H_{ij}}{H_{kl}}\cdot\frac{a_ib_j}{a_kb_l}\right)^p\\ &=&\sum_{ijkl}\frac{H_{i_1j_1}\ldots H_{i_pj_p}}{H_{k_1l_1}\ldots H_{k_pl_p}}\int_{\mathbb T^N}\frac{a_{i_1}\ldots a_{i_p}}{a_{k_1}\ldots a_{k_p}}\int_{\mathbb T^N}\frac{b_{j_1}\ldots b_{j_p}}{b_{l_1}\ldots b_{l_p}} \end{eqnarray*} [[/math]]

Now since the integrals at right equal respectively the Kronecker symbols [math]\delta_{[i],[k]}[/math] and [math]\delta_{[j],[l]}[/math], we are led to the formula in the statement.

■

With this formula in hand, the main result, regarding the fact that the complex Hadamard matrices can be put in bistochastic form, reformulates as follows:

Theorem

For a complex Hadamard matrix [math]H\in M_N(\mathbb T)[/math] we have

[[math]] \lim_{p\to\infty}\left(\sum_{[i]=[k],[j]=[l]}\frac{H_{i_1j_1}\ldots H_{i_pj_p}}{H_{k_1l_1}\ldots H_{k_pl_p}}\right)^{1/p}=N^3 [[/math]]

coming from the fact that [math]H[/math] can be put in bistochastic form.

Show Proof

This follows from the well-known fact that the maximum of a bounded function [math]\Theta:X\to[0,\infty)[/math] can be recaptured via following formula:

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

We can use this estimate for the following function, over [math]X=\mathbb T^N\times\mathbb T^N[/math]:

[[math]] \Theta=|E|^2 [[/math]]

We conclude that the limit in the statement is the square of the upper bound of the glow. But, according to Theorem 10.14, this upper bound is known to be [math]\leq N^3[/math] by Cauchy-Schwarz, and the equality holds by the results in .

■

To conclude now, the challenging question is that of finding a direct proof for Theorem 10.16. All this would provide an alternative aproach to the results in , which would be of course still not explicit, but which would use at least some more familiar tools. We will discuss such questions in chapter 11 below, with the remark however that the problems at [math]N\in\mathbb N[/math] fixed being quite difficult, we will do a [math]N\to\infty[/math] study only.

10d. Fourier matrices

Getting away now from these difficult questions, we have nothing concrete so far, besides the list of examples from Theorem 10.3, coming from the circulant matrix considerations in chapter 9. So, our purpose will be that of extending that list. A first natural question is that of looking at the Butson matrix case. To start with, we have:

Proposition

Assuming that the Butson class [math]H_N(l)[/math] contains a bistochastic matrix, the equations

[[math]] \begin{eqnarray*} a_0+a_1+\ldots+a_{l-1}&=&N\\ |a_0+a_1w+\ldots+a_{l-1}w^{l-1}|^2&=&N \end{eqnarray*} [[/math]]

must have solutions, over the positive integers.

Show Proof

This is a reformulation of the following equality, from Proposition 10.5, regarding the row sums of a bistochastic Hadamard matrix:

[[math]] |\lambda|^2=N [[/math]]

Indeed, if we set [math]w=e^{2\pi i/l}[/math], and we denote by [math]a_i\in\mathbb N[/math] the number of [math]w^i[/math] entries appearing in the first row of our matrix, then the row sum of the matrix is given by:

[[math]] \lambda=a_0+a_1w+\ldots+a_{l-1}w^{l-1} [[/math]]

Thus, we obtain the system of equations in the statement.

■

The point now is that, in practice, we are led precisely to the Turyn obstructions from chapter 9. At small values of [math]l[/math], the obstructions are as follows:

Theorem

Assuming that [math]H_N(l)[/math] contains a bistochastic matrix, the following equations must have solutions, over the integers:

• [math]l=2[/math]: [math]4n^2=N[/math].
• [math]l=3[/math]: [math]x^2+y^2+z^2=2N[/math], with [math]x+y+z=0[/math].
• [math]l=4[/math]: [math]a^2+b^2=N[/math].

Show Proof

This follows indeed from the results that we have:

(1) This is something well-known, which follows from Proposition 10.17.

(2) This is best viewed by using Proposition 10.17, and the following formula, that we already know, from chapter 5 above:

[[math]] \left|a+bw+cw^2\right|^2=\frac{1}{2}[(a-b)^2+(b-c)^2+(c-a)^2] [[/math]]

At the level of the concrete obstructions, we must have for instance [math]5\!\!\not|N[/math]. Indeed, this follows as in the proof of the de Launey obstruction for [math]H_N(3)[/math] with [math]5|N[/math].

(3) This follows again from Proposition 10.17, and from [math]|a+ib|^2=a^2+b^2[/math].

■

As a conclusion, nothing much interesting is going on in the Butson matrix case, with various arithmetic obstructions, that we partly already met, appearing here. In order to reach, however, to a number of positive results, beyond those in Theorem 10.3, we can investigate various special classes of matrices, such as the Di\c t\u a products. In order to formulate our results, we will use the following notion:

Definition

We say that a complex Hadamard matrix [math]H\in M_N(\mathbb C)[/math] is in “almost bistochastic form” when all the row sums belong to [math]\sqrt{N}\cdot\mathbb T[/math].

Observe that, assuming that this condition holds, the matrix [math]H[/math] can be put in bistochastic form, just by multiplying its rows by suitable numbers from [math]\mathbb T[/math]. We will be particularly interested here in the special situation where the affine deformations [math]H^q\in M_N(\mathbb C)[/math] of a given complex Hadamard matrix [math]H\in M_N(\mathbb C)[/math] can be put in almost bistochastic form, independently of the value of the parameter [math]q[/math]. For the simplest deformations, namely those of [math]F_2\otimes F_2[/math], this is indeed the case, as shown by the following result:

Proposition

The deformations of [math]F_2\otimes F_2[/math], with parameter matrix [math]Q=(^p_r{\ }^q_s)[/math],

[[math]] F_2\otimes_QF_2= \begin{pmatrix} p&q&p&q\\ p&-q&p&-q\\ r&s&-r&-s\\ r&-s&-r&s \end{pmatrix} [[/math]]

can be put in almost bistochastic form, independently of the value of [math]Q[/math].

Show Proof

By multiplying the columns of the matrix in the statement with [math]1,1,-1,1[/math] respectively, we obtain the following matrix:

[[math]] F_2\otimes''_QF_2= \begin{pmatrix} p&q&-p&q\\ p&-q&-p&-q\\ r&s&r&-s\\ r&-s&r&s \end{pmatrix} [[/math]]

The row sums of this matrix are as follows:

[[math]] 2q,-2q,2r,2r\in2\mathbb T [[/math]]

Thus, by multiplying by suitable scalars, namely the complex conjugates of these numbers, we can put our matrix in bistochastic form, as desired.

■

We will see later that [math]F_2\otimes''_QF_2[/math] is equivalent to a certain matrix [math]F_2\otimes'F_2[/math], which is part of a series [math]F_N\otimes'F_N[/math]. Now back to the general case, we have:

Theorem

A deformed tensor product [math]H\otimes_QK[/math] can be put in bistochastic form when there exist numbers [math]x^i_a\in\mathbb T[/math] such that with

[[math]] G_{ib}=\frac{(K^*x^i)_b}{Q_{ib}} [[/math]]

we have [math]|(H^*G)_{ib}|=\sqrt{MN}[/math], for any [math]i,b[/math].

Show Proof

According to our tensor product conventions, the deformed tensor product [math]L=H\otimes_QK[/math] is given by the following formula:

[[math]] L_{ia,jb}=Q_{ib}H_{ij}K_{ab} [[/math]]

By multiplying the columns by scalars [math]R_{jb}\in\mathbb T[/math], this matrix becomes:

[[math]] L'_{ia,jb}=R_{jb}Q_{ib}H_{ij}K_{ab} [[/math]]

The row sums of this matrix are given by:

[[math]] \begin{eqnarray*} S_{ia}' &=&\sum_{jb}R_{jb}Q_{ib}H_{ij}K_{ab}\\ &=&\sum_bK_{ab}Q_{ib}\sum_jH_{ij}R_{jb}\\ &=&\sum_bK_{ab}Q_{ib}(HR)_{ib} \end{eqnarray*} [[/math]]

Consider now the following variables:

[[math]] C^i_b=Q_{ib}(HR)_{ib} [[/math]]

In terms of these variables, the rows sums are given by:

[[math]] S_{ia}' =\sum_bK_{ab}C^i_b =(KC^i)_a [[/math]]

Thus [math]H\otimes_QK[/math] can be put in bistochastic form when we can find scalars [math]R_{jb}\in\mathbb T[/math] and [math]x^i_a\in\mathbb T[/math] such that, with [math]C^i_b=Q_{ib}(HR)_{ib}[/math], the following condition is satisfied:

[[math]] (KC^i)_a=\sqrt{MN}x^i_a\quad,\quad\forall i,a [[/math]]

But this condition is equivalent to the following condition:

[[math]] KC^i=\sqrt{MN}x^i\quad,\quad\forall i [[/math]]

Now by multiplying to the left by [math]K^*[/math], we are led to the following condition:

[[math]] \sqrt{N}C^i=\sqrt{M}K^*x^i\quad,\quad\forall i [[/math]]

Now by recalling that [math]C^i_b=Q_{ib}(HR)_{ib}[/math], this condition is equivalent to:

[[math]] \sqrt{N}Q_{ib}(HR)_{ib}=\sqrt{M}(K^*x^i)_b\quad,\quad\forall i,b [[/math]]

Consider now the variables in the statement, namely:

[[math]] G_{ib}=\frac{(K^*x^i)_b}{Q_{ib}} [[/math]]

In terms of these variables, the above condition reads:

[[math]] \sqrt{N}(HR)_{ib}=\sqrt{M}G_{ib}\quad,\quad\forall i,b [[/math]]

But this condition is equivalent to:

[[math]] \sqrt{N}HR=\sqrt{M}G [[/math]]

Now by multiplying to the left by [math]H^*[/math], we are led to the following condition:

[[math]] \sqrt{MN}R=H^*G [[/math]]

Thus, we have obtained the condition in the statement.

■

As an illustration for the above result, assume that [math]H,K[/math] can be put in bistochastic form, by using vectors [math]y\in\mathbb T^M,z\in\mathbb T^N[/math], and let us set:

[[math]] x^i_a=y_iz_a [[/math]]

Then with the choice [math]Q=1[/math] for our parameter matrix, we have:

[[math]] \begin{eqnarray*} G_{ib} &=&(K^*x^i)_b\\ &=&[K^*(y_iz)]_b\\ &=&y_i(K^*z)_b \end{eqnarray*} [[/math]]

We therefore obtain the following formula:

[[math]] \begin{eqnarray*} (H^*G)_{ib} &=&\sum_j(H^*)_{ij}G_{jb}\\ &=&\sum_j(H^*)_{ij}y_j(K^*z)_b\\ &=&(H^*y)_i(K^*z)_b \end{eqnarray*} [[/math]]

Thus the usual tensor product [math]H\otimes K[/math] can be put in bistochastic form as well, which is of course something that we already know, from the above. Now back to the general case, that of the arbitrary Di\c t\u a deformations in Theorem 10.21, the point is that in the particular case [math]H=F_M[/math] the equations simplify, and we have the following result:

Proposition

A deformed tensor product [math]F_M\otimes_QK[/math] can be put in bistochastic form when there exist numbers [math]x^i_a\in\mathbb T[/math] such that with

[[math]] G_{ib}=\frac{(K^*x^i)_b}{Q_{ib}} [[/math]]

we have the following formulae, with [math]l[/math] being taken modulo [math]M[/math]:

[[math]] \sum_jG_{jb}\bar{G}_{j+l,b}=MN\delta_{l,0}\quad,\quad\forall l,b [[/math]]

Moreover, the [math]M\times N[/math] matrix [math]|G_{jb}|^2[/math] is row-stochastic with sums [math]N^2[/math], and the [math]l=0[/math] equations state that this matrix must be column-stochastic, with sums [math]MN[/math].

Show Proof

With notations from Theorem 10.21, and with [math]w=e^{2\pi i/M}[/math], we have:

[[math]] (H^*G)_{ib}=\sum_jw^{-ij}G_{jb} [[/math]]

The absolute value of this number can be computed as follows:

[[math]] \begin{eqnarray*} |(H^*G)_{ib}|^2 &=&\sum_{jk}w^{i(k-j)}G_{jb}\bar{G}_{kb}\\ &=&\sum_{jl}w^{il}G_{jb}\bar{G}_{j+l,b}\\ &=&\sum_lw^{il}\sum_jG_{jb}\bar{G}_{j+l,b} \end{eqnarray*} [[/math]]

If we denote by [math]v^b_l[/math] the sum on the right, we obtain:

[[math]] |(H^*G)_{ib}|^2 =\sum_lw^{il}v^b_l =(F_Mv^b)_i [[/math]]

Now if we denote by [math]\xi[/math] the all-one vector in [math]\mathbb C^M[/math], the condition [math]|(H^*G)_{ib}|=\sqrt{MN}[/math] for any [math]i,b[/math] found in Theorem 10.21 reformulates as follows:

[[math]] F^Mv^b=MN\xi\quad,\quad\forall b [[/math]]

By multiplying to the left by [math]F_M^*/M[/math], this condition is equivalent to:

[[math]] v^b =NF_M^*\xi =\begin{pmatrix}MN\\0\\ \vdots\\0\end{pmatrix} [[/math]]

Let us examine the first equation, [math]v^b_0=MN[/math]. By definition of [math]v^b_l[/math], we have:

[[math]] v^b_0 =\sum_jG_{jb}\bar{G}_{jb} =\sum_j|G_{jb}|^2 [[/math]]

Now recall from Theorem 10.21 that we have, for certain numbers [math]x^j_b\in\mathbb T[/math]:

[[math]] G_{jb}=\frac{(K^*x^j)_b}{Q_{jb}} [[/math]]

Since we have [math]Q_{jb}\in\mathbb T[/math] and [math]K^*/\sqrt{N}\in U_N[/math], we obtain:

[[math]] \begin{eqnarray*} \sum_b|G_{jb}|^2 &=&\sum_b|(K^*x^j)_b|^2\\ &=&||K^*x^j||_2^2\\ &=&N||x^j||_2^2\\ &=&N^2 \end{eqnarray*} [[/math]]

Thus the [math]M\times N[/math] matrix [math]|G_{jb}|^2[/math] is row-stochastic, with sums [math]N^2[/math], and our equations [math]v^b_0=MN[/math] for any [math]b[/math] state that this matrix must be column-stochastic, with sums [math]MN[/math]. Regarding now the other equations that we found, namely [math]v^b_l=0[/math] for [math]l\neq0[/math], by definition of [math]v^b_l[/math] and of the variables [math]G_{jb}[/math], these state that we must have:

[[math]] \sum_jG_{jb}\bar{G}_{j+l,b}=0\quad,\quad\forall l\neq0,\forall b [[/math]]

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

■

As an illustration for this result, let us go back to the [math]Q=1[/math] situation, explained after Theorem 10.21. By using the formula [math]G_{ib}=y_i(K^*z)_b[/math] there, we have:

[[math]] \begin{eqnarray*} \sum_jG_{jb}\bar{G}_{j+l,b} &=&\sum_jy_j(K^*z)_b\,\overline{y}_{j+l}\overline{(K^*z)_b}\\ &=&|(K^*z)_b|^2\sum_j\frac{y_j}{y_{j+l}}\\ &=&M\cdot N\delta_{l,0} \end{eqnarray*} [[/math]]

Thus, if [math]K[/math] can be put in bistochastic form, then so can be put [math]F_M\otimes K[/math]. As a second illustration now, let us go back to the matrices [math]F_2\otimes'_QF_2[/math] from the proof of Proposition 10.20. For these matrices, the vector of the row sums is as follows:

[[math]] S=(2q,-2q,2r,2r) [[/math]]

Thus, with the above notations, we have the following formula:

[[math]] x=(q,-q,r,r) [[/math]]

We therefore obtain the following formulae for the upper entries of [math]G[/math]:

[[math]] G_{0b} =\frac{\left[\begin{pmatrix}1&1\\1&-1\end{pmatrix}\begin{pmatrix}q\\-q\end{pmatrix}\right]_b}{Q_{0b}} =\frac{\begin{pmatrix}0\\2q\end{pmatrix}_b}{Q_{0b}} [[/math]]

As for the lower entries of [math]G[/math], these are as follows:

[[math]] G_{1b} =\frac{\left[\begin{pmatrix}1&1\\1&-1\end{pmatrix}\begin{pmatrix}r\\r\end{pmatrix}\right]_b}{Q_{1b}} =\frac{\begin{pmatrix}2r\\0\end{pmatrix}_b}{Q_{1b}} [[/math]]

Thus, in this case the matrix [math]G[/math] is as follows, independently of [math]Q[/math]:

[[math]] G=\begin{pmatrix}0&2\\2&0\end{pmatrix} [[/math]]

In particular, we see that the conditions in Proposition 10.22 are satisfied. Now back to the general case, as a main application of our results so far, we have:

Theorem

The Di\c t\u a deformations of tensor squares of Fourier matrices,

[[math]] F_N\otimes_QF_N [[/math]]

can be put in almost bistochastic form, independently of the value of [math]Q\in M_N(\mathbb T)[/math].

Show Proof

We use Proposition 10.22, with [math]M=N[/math], and with [math]K=F_N[/math]. Let [math]w=e^{2\pi i/N}[/math], and consider the vectors [math]x^i\in\mathbb T^N[/math] given by:

[[math]] x^i=(w^{(i-1)a})_a [[/math]]

Since [math]K^*K=N1_N[/math], and [math]x^i[/math] are the column vectors of [math]K[/math], shifted by 1, we have:

[[math]] K^*x^0=\begin{pmatrix}0\\0\\ \vdots\\0\\N\end{pmatrix}\quad,\quad K^*x^1=\begin{pmatrix}N\\0\\ \vdots\\0\\0\end{pmatrix}\quad,\ \ldots\ ,\quad K^*x^{N-1}=\begin{pmatrix}0\\0\\ \vdots\\N\\0\end{pmatrix} [[/math]]

We conclude that we have the following formula:

[[math]] (K^*x^i)_b=N\delta_{i-1,b} [[/math]]

Thus the matrix [math]G[/math] is given by the following formula:

[[math]] G_{ib}=\frac{N\delta_{i-1,b}}{Q_{ib}} [[/math]]

With this formula in hand, the sums in Proposition 10.22 are given by:

[[math]] \sum_jG_{jb}\bar{G}_{j+l,b}=\sum_j\frac{N\delta_{j-1,b}}{Q_{jb}}\cdot\frac{N\delta_{j+l-1,b}}{Q_{j+l,b}} [[/math]]

In the case [math]l\neq0[/math] we clearly get [math]0[/math], because the products of Kronecker symbols are [math]0[/math]. In the case [math]l=0[/math] the denominators are [math]|Q_{jb}|^2=1[/math], and we obtain:

[[math]] \sum_jG_{jb}\bar{G}_{jb} =N^2\sum_j\delta_{j-1,b} =N^2 [[/math]]

Thus, the conditions in Proposition 10.21 are satisfied, and we obtain the result.

■

In relation with the various questions raised above, regarding the Di\c t\u a deformations of the Fourier matrices, this is best result that we have, so far. Here is an equivalent formulation of the above result, which is quite useful, in practice:

Theorem

The matrix [math]F_N\otimes'_QF_N[/math], with [math]Q\in M_N(\mathbb T)[/math], defined by

[[math]] (F_N\otimes'_QF_N)_{ia,jb}=\frac{w^{ij+ab}}{w^{bj+j}}\cdot\frac{Q_{ib}}{Q_{b+1,b}} [[/math]]

where [math]w=e^{2\pi i/N}[/math] is almost bistochastic, and equivalent to [math]F_N\otimes_QF_N[/math].

Show Proof

Our claim is that this is the matrix constructed in the proof of Theorem 10.23. Indeed, let us first go back to the proof of Theorem 10.21. In the case [math]M=N[/math] and [math]H=K=F_N[/math], the Di\c t\u a deformation [math]L=H\otimes_QK[/math] studied there is given by:

[[math]] L_{ia,jb} =Q_{ib}H_{ij}K_{ab} =w^{ij+ab}Q_{ib} [[/math]]

As explained in the proof of Theorem 10.23, if the conditions in the statement there are satisfied, then the matrix [math]L_{ia,jb}'=R_{jb}L_{ia,jb}[/math] is almost bistochastic, where:

[[math]] \sqrt{MN}\cdot R=H^*G [[/math]]

In our case now, [math]M=N[/math] and [math]H=K=F_N[/math], we know from the proof of Proposition 10.22 that the choice of [math]G[/math] which makes work Theorem 10.23 is as follows:

[[math]] G_{ib}=\frac{N\delta_{i-1,b}}{Q_{ib}} [[/math]]

With this formula in hand, we can compute the matrix [math]R[/math], as follows:

[[math]] \begin{eqnarray*} R_{jb} &=&\frac{1}{N}(H^*G)_{jb}\\ &=&\frac{1}{N}\sum_iw^{-ij}G_{ib}\\ &=&\sum_iw^{ij}\cdot\frac{\delta_{i-1,b}}{Q_{ib}}\\ &=&\frac{w^{-(b+1)j}}{Q_{b+1,b}} \end{eqnarray*} [[/math]]

Thus, the modified version of [math]F_N\otimes_QF_N[/math] which is almost bistochastic is given by:

[[math]] \begin{eqnarray*} L_{ia,jb}' &=&R_{jb}L_{ia,jb}\\ &=&\frac{w^{-(b+1)j}}{Q_{b+1,b}}\cdot w^{ij+ab}Q_{ib}\\ &=&\frac{w^{ij+ab}}{w^{bj+j}}\cdot\frac{Q_{ib}}{Q_{b+1,b}} \end{eqnarray*} [[/math]]

Thus we have obtained the formula in the statement, and we are done.

■

As an illustration, let us work out the case [math]N=2[/math]. Here the root of unity is [math]w=-1[/math]. Let us denote the deformation matrix as follows:

[[math]] Q=\begin{pmatrix}p&q\\ r&s\end{pmatrix} [[/math]]

With the notations [math]u=p/r[/math], [math]v=s/q[/math], we obtain the following matrix:

[[math]] \begin{eqnarray*} F_2\otimes_QF_2 &=&\begin{pmatrix} \frac{p}{r}&\frac{q}{q}&-\frac{p}{r}&\frac{q}{q}\\ \frac{p}{r}&-\frac{q}{q}&-\frac{p}{r}&-\frac{q}{q}\\ \frac{r}{r}&\frac{s}{q}&\frac{r}{r}&-\frac{s}{q}\\ \frac{r}{r}&-\frac{s}{q}&\frac{r}{r}&\frac{s}{q} \end{pmatrix}\\ &=&\begin{pmatrix} u&1&-u&1\\ u&-1&-u&-1\\ 1&v&1&-v\\ 1&-v&1&v \end{pmatrix} \end{eqnarray*} [[/math]]

In general, the question of putting the Di\c t\u a deformations of the tensor products in explicit bistochastic form remains open. Open as well is the question of putting the arbitrary affine deformations of the Fourier matrices in explicit bistochastic form.

We would like to end this chapter by discussing a related interesting question, which can serve as a very good motivation for all this, namely the question on whether the real Hadamard matrices, [math]H\in M_N(\pm1)[/math], can be put or not in bistochastic form, in an explicit way. This is certainly true for the Walsh matrices, as explained before, but for the other basic examples, such as the Paley or the Williamson matrices, no results seem to be known so far. Having such a theory would be potentially very interesting, with a complex reformulation of the HC and of the other real Hadamard questions at stake.

We already know that we are done with the case [math]N\leq8[/math]. The next problem regards the Paley matrix at [math]N=12[/math], which is the unique real Hadamard matrix there:

[[math]] P_{12}\sim P_{12}^1\sim P_{12}^2 [[/math]]

This matrix is as follows, with the [math]\pm[/math] signs standing for [math]\pm1[/math] entries:

[[math]] P_{12}=\left( \begin{array}{ccccccccccccccc} +&+&+&+&&-&+&+&+&&-&+&+&+\\ +&-&+&-&&+&-&+&+&&+&-&+&+\\ +&+&-&-&&+&+&-&+&&+&+&-&+\\ +&-&-&+&&+&+&+&-&&+&+&+&-\\ \\ -&+&-&-&&+&-&+&+&&-&+&+&-\\ -&+&+&+&&+&+&-&+&&+&-&+&-\\ -&-&-&+&&+&+&+&+&&-&-&-&+\\ +&+&+&-&&+&+&+&-&&-&-&-&-\\ \\ -&+&+&+&&+&-&+&-&&+&+&-&+\\ +&+&-&+&&+&-&-&-&&-&-&+&+\\ +&-&+&+&&+&-&-&+&&-&+&-&-\\ -&-&+&-&&+&+&-&-&&-&+&+&+ \end{array}\right) [[/math]]

This matrix cannot be put of course in real bistochastic form, its size being not of the form [math]N=4n^2[/math]. Nor can it be put in bistochastic form over [math]\{\pm1,\pm i\}[/math], because the Turyn obstruction for matrices over [math]\{\pm1,\pm i\}[/math] is [math]N=a^2+b^2[/math], and we have:

[[math]] 12\neq a^2+b^2 [[/math]]

However, the question of putting [math]P_{12}[/math] in bistochastic form over the 3-roots of unity makes sense, because the Turyn obstruction here is:

[[math]] x+y+z=0\quad,\quad x^2+y^2+z^2=2N [[/math]]

And, we do have solutions to these equations at [math]N=12[/math], as follows:

[[math]] 4^2+(-2)^2+(-2)^2=24 [[/math]]

Another question is whether [math]P_{12}[/math] can be put in bistochastic form over the 8-roots of unity. In order to comment on this, let us first work out the Turyn obstruction, for the bistochastic matrices having as entries the 8-roots of unity. The result is as follows:

Proposition

The Turyn obstruction for the bistochastic matrices having as entries the [math]8[/math]-roots of unity is

[[math]] x^2+y^2+z^2+t^2=N\quad,\quad xy+yz+zt=xt [[/math]]

which must hold for certain numbers [math]x,y,z,t\in\mathbb Z[/math].

Show Proof

The 8-roots of unity are as follows, with [math]w=e^{\pi i/4}[/math]:

[[math]] 1,w,i,iw,-1,-w,-i,-iw [[/math]]

Thus, we are led to an equation as follows, with [math]x,y,z,t\in\mathbb Z[/math]:

[[math]] \left|x+wy+iz+iwt\right|^2=N [[/math]]

We have the following computation:

[[math]] \begin{eqnarray*} \left|x+wy+iz+iwt\right|^2 &=&(x+wy+iz+iwt)(x-iwy-iz-wt)\\ &=&x^2+y^2+z^2+t^2+w(1-i)(xy+yz+zt-xt)\\ &=&x^2+y^2+z^2+t^2-\sqrt{2}(xy+yz+zt-xt) \end{eqnarray*} [[/math]]

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

■

In relation with the above, the point now is that the equations in Proposition 10.25 do have solutions at [math]N=12[/math], namely:

[[math]] x=0,y=2,z=-2,t=\pm2 [[/math]]

Summarizing, the Paley matrix [math]P_{12}[/math] cannot be put in bistochastic form over the 4-roots, but the question makes sense over the 3-roots, and over the 8-roots. However, the computations here are not exactly trivial, and the answer is not known.

There are many interesting questions here, and as already mentioned above, the interest in this subject comes from the fact that all this can potentially lead to a complex reformulation of the HC and of the other real Hadamard matrix questions.

General references

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