8c. Isolated matrices

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

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

Let us discuss now yet another interesting construction of complex Hadamard matrices, due to McNulty and Weigert . The matrices constructed there generalize the Tao matrix [math]T_6[/math], and usually have the interesting feature of being isolated. The construction in uses the theory of MUB, as developed in , , but we will follow here a more direct approach, from . The starting observation from is as follows:

Theorem

Assuming that [math]K\in M_N(\mathbb C)[/math] is Hadamard, so is the matrix

[[math]] H_{ia,jb}=\frac{1}{\sqrt{Q}}K_{ij}(L_i^*R_j)_{ab} [[/math]]

provided that [math]\{L_1,\ldots,L_N\}\subset\sqrt{Q}U_Q[/math] and [math]\{R_1,\ldots,R_N\}\subset\sqrt{Q}U_Q[/math] are such that

[[math]] \frac{1}{\sqrt{Q}}L_i^*R_j\in\sqrt{Q}U_Q [[/math]]

with [math]i,j=1,\ldots,N[/math], are complex Hadamard.

Show Proof

The check of the unitarity of the matrix in the statement can be done as follows, by using our various assumptions on the various matrices involved:

[[math]] \begin{eqnarray*} \lt H_{ia},H_{kc} \gt &=&\frac{1}{Q}\sum_{jb}K_{ij}(L_i^*R_j)_{ab}\bar{K}_{kj}\overline{(L_k^*R_j)}_{cb}\\ &=&\sum_jK_{ij}\bar{K}_{kj}(L_i^*L_k)_{ac}\\ &=&N\delta_{ik}(L_i^*L_k)_{ac}\\ &=&NQ\delta_{ik}\delta_{ac} \end{eqnarray*} [[/math]]

The entries of our matrix being in addition on the unit circle, we are done.

■

The above construction is of course something quite abstract, but as a very concrete input for it, we can use the following well-known Fourier analysis construction:

Proposition

For [math]q\geq3[/math] prime, the matrices

[[math]] \{F_q,DF_q,\ldots,D^{q-1}F_q\} [[/math]]

where [math]F_q[/math] is the Fourier matrix, and where

[[math]] D=diag\left(1,1,w,w^3,w^6,w^{10},\ldots,w^{\frac{q^2-1}{8}},\ldots,w^{10},w^6,w^3,w\right) [[/math]]

with [math]w=e^{2\pi i/q}[/math], are such that [math]\frac{1}{\sqrt{q}}E_i^*E_j[/math] is complex Hadamard, for any [math]i\neq j[/math].

Show Proof

With by definition [math]0,1,\ldots,q-1[/math] as indices for our matrices, as usual in a Fourier analysis context, the formula of the above matrix [math]D[/math] is:

[[math]] D_c =w^{0+1+\ldots+(c-1)} =w^{\frac{c(c-1)}{2}} [[/math]]

Since we have [math]\frac{1}{\sqrt{q}}E_i^*E_j\in\sqrt{q}U_q[/math], we just need to check that these matrices have entries belonging to [math]\mathbb T[/math], for any [math]i\neq j[/math]. With [math]k=j-i[/math], these entries are given by:

[[math]] \begin{eqnarray*} \frac{1}{\sqrt{q}}(E_i^*E_j)_{ab} &=&\frac{1}{\sqrt{q}}(F_q^*D^kF_q)_{ab}\\ &=&\frac{1}{\sqrt{q}}\sum_cw^{c(b-a)}D_c^k \end{eqnarray*} [[/math]]

Now observe that with [math]s=b-a[/math], we have the following formula:

[[math]] \begin{eqnarray*} \left|\sum_cw^{cs}D_c^k\right|^2 &=&\sum_{cd}w^{cs-ds}w^{\frac{c(c-1)}{2}\cdot k-\frac{d(d-1)}{2}\cdot k}\\ &=&\sum_{cd}w^{(c-d)\left(\frac{c+d-1}{2}\cdot k+s\right)}\\ &=&\sum_{de}w^{e\left(\frac{2d+e-1}{2}\cdot k+s\right)}\\ &=&\sum_e\left(w^{\frac{e(e-1)}{2}\cdot k+es}\sum_dw^{edk}\right)\\ &=&\sum_ew^{\frac{e(e-1)}{2}\cdot k+es}\cdot q\delta_{e0}\\ &=&q \end{eqnarray*} [[/math]]

Thus the entries are on the unit circle, and we are done.

■

We recall that the Legendre symbol is defined as follows:

[[math]] \left(\frac{s}{q}\right)=\begin{cases} 0&{\rm if}\ s=0\\ 1&{\rm if}\ \exists\,\alpha,s=\alpha^2\\ -1&{\rm if}\not\!\exists\,\alpha,s=\alpha^2 \end{cases} [[/math]]

With this convention, we have the following result, following :

Proposition

The following matrices,

[[math]] G_k=\frac{1}{\sqrt{q}}F_q^*D^kF_q [[/math]]

with the matrix [math]D[/math] being as above,

[[math]] D=diag\left(w^{\frac{c(c-1)}{2}}\right) [[/math]]

and with [math]k\neq0[/math] are circulant, their first row vectors [math]V^k[/math] being given by

[[math]] V^k_i=\delta_q\left(\frac{k/2}{q}\right)w^{\frac{q^2-1}{8}\cdot k}\cdot w^{-\frac{\frac{i}{k}(\frac{i}{k}-1)}{2}} [[/math]]

where [math]\delta_q=1[/math] if [math]q=1(4)[/math] and [math]\delta_q=i[/math] if [math]q=3(4)[/math], and with all inverses being taken in [math]\mathbb Z_q[/math].

Show Proof

This is a standard exercice on quadratic Gauss sums. First of all, the matrices [math]G_k[/math] in the statement are indeed circulant, their first vectors being given by:

[[math]] V^k_i=\frac{1}{\sqrt{q}}\sum_cw^{\frac{c(c-1)}{2}\cdot k+ic} [[/math]]

Let us first compute the square of this quantity. We have:

[[math]] (V_i^k)^2=\frac{1}{q}\sum_{cd}w^{\left[\frac{c(c-1)}{2}+\frac{d(d-1)}{2}\right]k+i(c+d)} [[/math]]

The point now is that the sum [math]S[/math] on the right, which has [math]q^2[/math] terms, decomposes as follows, where [math]x[/math] is a certain exponent, depending on [math]q,i,k[/math]:

[[math]] S=\begin{cases} (q-1)(1+w+\ldots+w^{q-1})+qw^x&{\rm if}\ q=1(4)\\ (q+1)(1+w+\ldots+w^{q-1})-qw^x&{\rm if}\ q=3(4) \end{cases} [[/math]]

We conclude that we have a formula as follows, where [math]\delta_q\in\{1,i\}[/math] is as in the statement, so that [math]\delta_q^2\in\{1,-1\}[/math] is given by [math]\delta_q^2=1[/math] if [math]q=1(4)[/math] and [math]\delta_q^2=-1[/math] if [math]q=3(4)[/math]:

[[math]] (V_i^k)^2=\delta_q^2\,w^x [[/math]]

In order to compute now the exponent [math]x[/math], we must go back to the above calculation of the sum [math]S[/math]. We succesively have:

-- First of all, at [math]k=1,i=0[/math] we have [math]x=\frac{q^2-1}{4}[/math].

-- By translation we obtain [math]x=\frac{q^2-1}{4}-i(i-1)[/math], at [math]k=1[/math] and any [math]i[/math].

-- By replacing [math]w\to w^k[/math] we obtain [math]x=\frac{q^2-1}{4}\cdot k-\frac{i}{k}(\frac{i}{k}-1)[/math], at any [math]k\neq0[/math] and any [math]i[/math].

Summarizing, we have computed the square of the quantity that we are interested in, the formula being as follows, with [math]\delta_q[/math] being as in the statement:

[[math]] (V^k_i)^2=\delta_q^2\cdot w^{\frac{q^2-1}{4}\cdot k}\cdot w^{-\frac{i}{k}(\frac{i}{k}-1)} [[/math]]

By extracting now the square root, we obtain a formula as follows:

[[math]] V^k_i=\pm\delta_q\cdot w^{\frac{q^2-1}{8}\cdot k}\cdot w^{-\frac{\frac{i}{k}(\frac{i}{k}-1)}{2}} [[/math]]

The computation of the missing sign is non-trivial, but by using the theory of quadratic Gauss sums, and more specifically a result of Gauss, computing precisely this kind of sign, we conclude that we have indeed a Legendre symbol, [math]\pm=\left(\frac{k/2}{q}\right)[/math], as claimed.

■

Let us combine now all the above results. We obtain the following statement:

Theorem

Let [math]q\geq3[/math] be prime, consider two subsets

[[math]] S,T\subset\{0,1,\ldots,q-1\} [[/math]]

satisfying the conditions [math]|S|=|T|[/math] and [math]S\cap T=\emptyset[/math], and write:

[[math]] S=\{s_1,\ldots,s_N\}\quad,\quad T=\{t_1,\ldots,t_N\} [[/math]]

Then, with the matrix [math]V[/math] being as above, the matrix

[[math]] H_{ia,jb}=K_{ij}V^{t_j-s_i}_{b-a} [[/math]]

is complex Hadamard, provided that the matrix [math]K\in M_N(\mathbb C)[/math] is complex Hadamard.

Show Proof

This follows indeed by using the general construction in Theorem 8.20, with input coming from Proposition 8.21 and Proposition 8.22.

■

As explained by McNulty-Weigert in , the above construction covers many interesting examples of Hadamard matrices, previously known from Tadej-\.Zyczkowski , to be isolated, such as the Tao matrix, which is as follows, with [math]w=e^{2\pi i/3}[/math]:

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

In general, in order to find isolated matrices, the idea from is that of starting with an isolated matrix, and then use suitable sets [math]S,T[/math]. The defect computations are, however, quite difficult. As a concrete statement, however, we have the following conjecture: \begin{conjecture} The complex Hadamard matrix constructed in Theorem 8.23 is isolated, provided that:

• [math]K[/math] is an isolated Fourier matrix, of prime order.
• [math]S,T[/math] consist of consecutive odd numbers, and consecutive even numbers.

\end{conjecture} This statement is supported by the isolation result for [math]T_6[/math], and by several computer simulations from . For further details on all this, we refer to , .

General references

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