8d. Partial 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.

As a final topic now, we would like to discuss an extension of a part of our results, from here and from chapter 7, to the case of the partial Hadamard matrices (PHM). The extension, from , is quite straightforward, but there are a number of subtleties appearing. First of all, we can talk about deformations of PHM, as follows:

Definition

Let [math]H\in X_{M,N}[/math] be a partial complex Hadamard matrix.

• A deformation of [math]H[/math] is a smooth function [math]f:\mathbb T_1\to (X_{M,N})_H[/math].
• The deformation is called “affine” if [math]f_{ij}(q)=H_{ij}q^{A_{ij}}[/math], with [math]A\in M_{M\times N}(\mathbb R)[/math].
• We call “trivial” the deformations [math]f_{ij}(q)=H_{ij}q^{a_i+b_j}[/math], with [math]a\in\mathbb R^M,b\in\mathbb R^N[/math].

Observe that we have the following equality, where [math]U_{M,N}\subset M_{M\times N}(\mathbb C)[/math] is the set of matrices having all rows of norm 1, and pairwise orthogonal:

[[math]] X_{M,N}=M_{M\times N}(\mathbb T)\cap\sqrt{N}U_{M,N} [[/math]]

As in the square matrix case, this leads to the following definition:

Definition

Associated to a point [math]H\in X_{M,N}[/math] are the enveloping tangent space

[[math]] \widetilde{T}_HX_{M,N}=T_HM_{M\times N}(\mathbb T)\cap T_H\sqrt{N}U_{M,N} [[/math]]

as well as the following subcones of this enveloping tangent space:

• The tangent cone [math]T_HX_{M,N}[/math]: the set of tangent vectors to the deformations of [math]H[/math].
• The affine tangent cone [math]T_H^\circ X_{M,N}[/math]: same as above, using affine deformations only.
• The trivial tangent cone [math]T_H^\times X_{M,N}[/math]: as above, using trivial deformations only.

Observe that [math]\widetilde{T}_HX_{M,N},T_HX_{M,N}[/math] are real vector spaces, and that [math]T_HX_{M,N},T_H^\circ X_{M,N}[/math] are two-sided cones, in the sense that they satisfy the following condition:

[[math]] \lambda\in\mathbb R,A\in T\implies\lambda A\in T [[/math]]

Also, we have inclusions of cones as follows:

[[math]] T_H^\times X_{M,N}\subset T_H^\circ X_{M,N}\subset T_HX_{M,N}\subset\widetilde{T}_HX_{M,N} [[/math]]

As in the square matrix case, we can formulate the following definition:

Definition

The defect of a matrix [math]H\in X_{M,N}[/math] is the dimension

[[math]] d(H)=\dim(\widetilde{T}_HX_{M,N}) [[/math]]

of the real vector space [math]\widetilde{T}_HX_{M,N}[/math] constructed above.

The basic remarks and comments regarding the defect from the square matrix case extend then to this setting. In particular, we have the following basic result:

Theorem

The enveloping tangent space at [math]H\in X_{M,N}[/math] is given by

[[math]] \widetilde{T}_HX_{M,N}\simeq\left\{A\in M_{M\times N}(\mathbb R)\Big|\sum_kH_{ik}\bar{H}_{jk}(A_{ik}-A_{jk})=0,\forall i,j\right\} [[/math]]

and the defect of [math]H[/math] is the dimension of this real vector space.

Show Proof

In the square matrix case this was done in chapter 7, and the extension of the computations there to the rectangular case is straightforward. First, the manifold [math]M_{M\times N}(\mathbb T)[/math] is defined by the following algebraic relations:

[[math]] |H_{ij}|^2=1 [[/math]]

In terms of real and imaginary parts, [math]H_{ij}=X_{ij}+iY_{ij}[/math], we have:

[[math]] d|H_{ij}|^2 =d(X_{ij}^2+Y_{ij}^2) =2(X_{ij}\dot{X}_{ij}+Y_{ij}\dot{Y}_{ij}) [[/math]]

Consider now an arbitrary vector [math]\xi\in T_HM_{M\times N}(\mathbb C)[/math], written as follows:

[[math]] \xi=\sum_{ij}\alpha_{ij}\dot{X}_{ij}+\beta_{ij}\dot{Y}_{ij} [[/math]]

This vector belongs then to [math]T_HM_{M\times N}(\mathbb T)[/math] if and only if we have:

[[math]] \lt \xi,d|H_{ij}|^2 \gt =0 [[/math]]

We therefore obtain the following formula, for the tangent cone:

[[math]] T_HM_{M\times N}(\mathbb T)=\left\{\sum_{ij}A_{ij}(Y_{ij}\dot{X}_{ij}-X_{ij}\dot{Y}_{ij})\Big|A_{ij}\in\mathbb R\right\} [[/math]]

We also know that the manifold [math]\sqrt{N}U_{M,N}[/math] is defined by the following algebraic relations, where [math]H_1,\ldots,H_N[/math] are the rows of [math]H[/math]:

[[math]] \lt H_i,H_j \gt =N\delta_{ij} [[/math]]

The relations [math] \lt H_i,H_i \gt =N[/math] being automatic for the matrices [math]H\in M_{M\times N}(\mathbb T)[/math], if for [math]i\neq j[/math] we let [math]L_{ij}= \lt H_i,H_j \gt [/math], then we have:

[[math]] \widetilde{T}_HC_N=\left\{\xi\in T_HM_N(\mathbb T)\Big| \lt \xi,\dot{L}_{ij} \gt =0,\,\forall i\neq j\right\} [[/math]]

On the other hand, differentiating the formula of [math]L_{ij}[/math] gives:

[[math]] \dot{L}_{ij}=\sum_k(X_{ik}+iY_{ik})(\dot{X}_{jk}-i\dot{Y}_{jk})+(X_{jk}-iY_{jk})(\dot{X}_{ik}+i\dot{Y}_{ik}) [[/math]]

Now if we pick a vector [math]\xi\in T_HM_{M\times N}(\mathbb T)[/math], written as above in terms of [math]A\in M_{M\times N}(\mathbb R)[/math], we obtain the following formula:

[[math]] \lt \xi,\dot{L}_{ij} \gt =i\sum_k\bar{H}_{ik}H_{jk}(A_{ik}-A_{jk}) [[/math]]

Thus we have reached to the description of [math]\widetilde{T}_HX_{M,N}[/math] in the statement.

■

Summarizing, the extension of the basic defect theory, from the square matrix case to the rectangular matrix case, appears to be quite straightforward. By using the above defect equations, most of the general comments and remarks from chapter 7 regarding the square matrix case extend to the rectangular matrix case. See . At the level of non-trivial results now, we first have the following statement:

Theorem

Let [math]H\in X_{M,N}[/math], and pick a square matrix

[[math]] K\in\sqrt{N}U_N [[/math]]

extending [math]H[/math]. We have then the following formula,

[[math]] \widetilde{T}_HX_{M,N}\simeq\left\{E=(X\ Y)\in M_{M\times N}(\mathbb C)\Big|X=X^*,(EK)_{ij}\bar{H}_{ij}\in\mathbb R,\forall i,j\right\} [[/math]]

with the correspondence [math]A\to E[/math] being constructed as follows:

[[math]] E_{ij}=\sum_kH_{ik}\bar{K}_{jk}A_{ik}\quad,\quad A_{ij}=(EK)_{ij}\bar{H}_{ij} [[/math]]

Show Proof

Let us set indeed [math]R_{ij}=A_{ij}H_{ij}[/math] and [math]E=RK^*[/math]. The correspondence [math]A\to R\to E[/math] is then bijective, and we have the following formula:

[[math]] E_{ij}=\sum_kH_{ik}\bar{K}_{jk}A_{ik} [[/math]]

With these changes, the system of equations in Theorem 8.28 becomes [math]E_{ij}=\bar{E}_{ji}[/math] for any [math]i,j[/math] with [math]j\leq M[/math]. But this shows that we must have [math]E=(X\ Y)[/math] with [math]X=X^*[/math], and the condition [math]A_{ij}\in\mathbb R[/math] corresponds to the condition [math](EK)_{ij}\bar{H}_{ij}\in\mathbb R[/math], as claimed.

■

As an illustration, in the real case we obtain the following result:

Theorem

For an Hadamard matrix [math]H\in M_{M\times N}(\pm1)[/math] we have

[[math]] \widetilde{T}_HX_{M,N}\simeq M_M(\mathbb R)^{symm}\oplus M_{M\times(N-M)}(\mathbb R) [[/math]]

and so the defect is given by

[[math]] d(H)=\frac{N(N+1)}{2}+M(N-M) [[/math]]

independently of the precise value of [math]H[/math].

Show Proof

We use Theorem 8.29. Since [math]H[/math] is now real we can pick [math]K\in\sqrt{N}U_N[/math] extending it to be real too, and with nonzero entries, so the last condition appearing there, namely [math](EK)_{ij}\bar{H}_{ij}\in\mathbb R[/math], simply tells us that [math]E[/math] must be real. Thus we have:

[[math]] \widetilde{T}_HX_{M,N}\simeq\left\{E=(X\ Y)\in M_{M\times N}(\mathbb R)\Big|X=X^*\right\} [[/math]]

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

■

A matrix [math]H\in X_{M,N}[/math] cannot be isolated, simply because the space of its Hadamard equivalents provides a copy [math]\mathbb T^{MN}\subset X_{M,N}[/math], passing through [math]H[/math]. However, if we restrict the attention to the matrices which are dephased, the notion of isolation makes sense:

Proposition

The defect [math]d(H)=\dim(\widetilde{T}_HX_{M,N})[/math] satisfies

[[math]] d(H)\geq M+N-1 [[/math]]

and if [math]d(H)=M+N-1[/math] then [math]H[/math] is isolated inside the dephased quotient [math]X_{M,N}\to Z_{M,N}[/math].

Show Proof

Once again, the known results in the square case extend:

(1) We have indeed [math]\dim(T_H^\times X_{M,N})=M+N-1[/math], and since the tangent vectors to these trivial deformations belong to [math]\widetilde{T}_HX_{M,N}[/math], this gives the first assertion.

(2) Since [math]d(H)=M+N-1[/math], the inclusions [math]T_H^\times X_{M,N}\subset T_HX_{M,N}\subset\widetilde{T}_HX_{M,N}[/math] must be equalities, and from [math]T_HX_{M,N}=T_H^\times X_{M,N}[/math] we obtain the result.

■

Finally, still at the theoretical level, we have the following conjecture:

\begin{conjecture} An isolated partial Hadamard matrix [math]H\in Z_{M,N}[/math] must have minimal defect, namely [math]d(H)=M+N-1[/math]. \end{conjecture} In other words, the conjecture is that if [math]H\in Z_{M,N}[/math] has only trivial first order deformations, then it has only trivial deformations at any order, including at [math]\infty[/math]. In the square matrix case this statement comes with solid evidence, all known examples of complex Hadamard matrices [math]H\in X_N[/math] having non-minimal defect being known to admit one-parameter deformations. For more on this subject, see , , .

Let us discuss now some examples of isolated partial Hadamard matrices, and provide some evidence for Conjecture 8.32. We are interested in the following matrices:

Definition

The truncated Fourier matrix [math]F_{S,G}[/math], with [math]G[/math] being a finite abelian group, and with [math]S\subset G[/math] being a subset, is constructed as follows:

• Given [math]N\in\mathbb N[/math], we set [math]F_N=(w^{ij})_{ij}[/math], where [math]w=e^{2\pi i/N}[/math].
• Assuming [math]G=\mathbb Z_{N_1}\times\ldots\times\mathbb Z_{N_s}[/math], we set [math]F_G=F_{N_1}\otimes\ldots\otimes F_{N_s}[/math].
• We let [math]F_{S,G}[/math] be the submatrix of [math]F_G[/math] having [math]S\subset G[/math] as row index set.

Observe that [math]F_N[/math] is the Fourier matrix of the cyclic group [math]\mathbb Z_N[/math]. More generally, [math]F_G[/math] is the Fourier matrix of the finite abelian group [math]G[/math]. Observe also that [math]F_{G,G}=F_G[/math]. We can compute the defect of [math]F_{S,G}[/math] by using Theorem 8.28, and we obtain:

Theorem

For a truncated Fourier matrix [math]F=F_{S,G}[/math] we have the formula

[[math]] \widetilde{T}_FX_{M,N}=\left\{A\in M_{M\times N}(\mathbb R)\Big|P=AF^t\ {\rm satisfies}\ P_{ij}=P_{i+j,j}=\bar{P}_{i,-j},\forall i,j\right\} [[/math]]

where [math]M=|S|,N=|G|[/math], and with all the indices being regarded as group elements.

Show Proof

We use Theorem 8.28. The defect equations there are as follows:

[[math]] \sum_kF_{ik}\bar{F}_{jk}(A_{ik}-A_{jk})=0 [[/math]]

For [math]F=F_{S,G}[/math] we have the following formula:

[[math]] F_{ik}\bar{F}_{jk}=(F^t)_{k,i-j} [[/math]]

We therefore obtain the following formula:

[[math]] \widetilde{T}_FX_{M,N}=\left\{A\in M_{M\times N}(\mathbb R)\Big|(AF^t)_{i,i-j}=(AF^t)_{j,i-j},\forall i,j\right\} [[/math]]

Now observe that for an arbitrary matrix [math]P\in M_M(\mathbb C)[/math], we have:

[[math]] \begin{eqnarray*} P_{i,i-j}=P_{j,i-j},\forall i,j &\iff&P_{i+j,i}=P_{ji},\forall i,j\\ &\iff&P_{i+j,j}=P_{ij},\forall i,j \end{eqnarray*} [[/math]]

We therefore conclude that we have the following equality:

[[math]] \widetilde{T}_FX_{M,N}=\left\{A\in M_{M\times N}(\mathbb R)\Big| P=AF^t\ {\rm satisfies}\ P_{ij}=P_{i+j,j},\forall i,j\right\} [[/math]]

Now observe that with [math]A\in M_{M\times N}(\mathbb R)[/math] and [math]P=AF^t\in M_M(\mathbb C)[/math] as above, we have:

[[math]] \begin{eqnarray*} \bar{P}_{ij} &=&\sum_kA_{ik}(F^*)_{kj}\\ &=&\sum_kA_{ik}(F^t)_{k,-j}\\ &=&P_{i,-j} \end{eqnarray*} [[/math]]

Thus, we obtain the formula in the statement, and we are done.

■

Let us try to find some explicit examples of isolated matrices, of truncated Fourier type. For this purpose, we can use the following improved version of Theorem 8.34:

Theorem

The defect of [math]F=F_{S,G}[/math] is the number

[[math]] d(F)=\dim(K)+\dim(I) [[/math]]

where [math]K,I[/math] are the following linear spaces,

[[math]] \begin{eqnarray*} K&=&\left\{A\in M_{M\times N}(\mathbb R)\Big|AF^t=0\right\}\\ I&=&\left\{P\in L_M\Big|\exists A\in M_{M\times N}(\mathbb R),P=AF^t\right\} \end{eqnarray*} [[/math]]

with [math]L_M[/math] being the following linear space,

[[math]] L_M=\left\{P\in M_M(\mathbb C)\Big|P_{ij}=P_{i+j,j}=\bar{P}_{i,-j},\forall i,j\right\} [[/math]]

with all the indices belonging by definition to the group [math]G[/math].

Show Proof

We use the general formula in Theorem 8.34. With the notations there, and with the linear space [math]L_M[/math] being as above, we have a linear map as follows:

[[math]] \Phi:\widetilde{T}_FX_{M,N}\to L_M\quad,\quad \Phi(A)=AF^t [[/math]]

By using this map, we obtain the following equality:

[[math]] \dim(\widetilde{T}_FX_{M,N})=\dim(\ker\Phi)+\dim({\rm Im}\,\Phi) [[/math]]

Now since the spaces on the right are precisely those in the statement, we have:

[[math]] \ker\Phi=K\quad,\quad {\rm Im}\, \Phi=I [[/math]]

Thus by applying Theorem 8.34 we obtain the result.

■

In order to look now for isolated matrices, the first remark is that since a deformation of [math]F_G[/math] will produce a deformation of [math]F_{S,G}[/math] too, we must restrict the attention to the case where [math]G=\mathbb Z_p[/math], with [math]p[/math] prime. And here, we have the following conjecture:

\begin{conjecture} There exists a constant [math]\varepsilon \gt 0[/math] such that [math]F_{S,p}[/math] is isolated, for any [math]p[/math] prime, once [math]S\subset\mathbb Z_p[/math] satisfies [math]|S|\geq(1-\varepsilon)p[/math]. \end{conjecture} In principle this conjecture can be approached by using the formula in Theorem 8.35, and we have for instance evidence towards the fact that [math]F_{p-1,p}[/math] should be always isolated, that [math]F_{p-2,p}[/math] should be isolated too, provided that [math]p[/math] is big enough, and so on. However, finding a number [math]\varepsilon \gt 0[/math] as above looks like a quite difficult question. See .

General references

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