<span>FAMILIES OF COMPLEX HADAMARD MATRICES</span> <span>Nuno Barros e Sá</span>[^1] <span>*DCTD, Universidade dos Açores,*</span> <span>*9500-801 Ponta Delgada, Portugal*</span> <span>Ingemar Bengtsson</span>[^2] <span>*Fysikum, Stockholms Universitet,*</span> <span>*S-106 91 Stockholm, Sweden*</span> <span>**Abstract:**</span> What is the dimension of a smooth family of complex Hadamard matrices including the Fourier matrix? We address this problem with a power series expansion. Studying all dimensions up to 100 we find that the first order result is misleading unless the dimension is 6, or a power of a prime. In general the answer depends critically on the prime number decomposition of the dimension. Our results suggest that a general theory is possible. We discuss the case of dimension 12 in detail, and argue that the solution consists of two 13-dimensional families intersecting in a previously known 9-dimensional family. A precise conjecture for all dimensions equal to a prime times another prime squared is formulated. <span>**1. Introduction**</span> A type of mathematical problem that arises very often is that one has a set of $M$ algebraic equations in $N$ variables, $$f_m(x_1, \dots , x_N) = 0 \ , \hspace{8mm} m = 1, \dots , M \ . \label{1}$$ One solution is known, and one asks whether this is an isolated solution, and if not one asks for the dimension of the solution space around that special solution. The problem to be discussed here is of that type, and our aim is to perform a perturbative expansion around the special solution, in order to learn something about the possible answers to the above questions. We will outline a systematic and completely general method to do so. The particular problem that we will study concerns complex Hadamard matrices. By definition a complex Hadamard matrix is a unitary $N\times N$ matrix all of whose entries have the same modulus. The classification of such matrices has a long history @Sylvester. It has been completed for $N \leq 5$ @Haagerup, and much partial information is available in higher dimensions @TZ [@Horadam; @Feriphd]. This classification problem is of interest for many reasons. In quantum theory it is equivalent to the problem of classifying all complementary pairs of bases @Kraus—now known as Mutually Unbiased Bases @Durt—and it can be used to give quantitative content to Bohr's principle of complementarity @Berge. It also forms part of the problem of classifying unitary operator bases @Werner, which is of importance in quantum information theory, and it arises in operator algebra @Popa, quantum groups @Banica, and elsewhere. A complex Hadamard matrix that exists for any $N$ is the Fourier matrix, whose entries are $$F_{ij} = \frac{\omega^{ij}}{\sqrt{N}} \ , \hspace{8mm} 0 \leq i,j \leq N-1 \ , \hspace{8mm} \omega = e^{\frac{2\pi i}{N}} \ .$$ This is the special solution that we are going to expand around. Although we will proceed somewhat differently, in principle one can proceed with this problem by modifying all the matrix elements according to $$\omega^{ij} \rightarrow \omega^{ij}e^{i\tau_{ij}} \ ,$$ expanding the phase factors in powers of $\tau_{ij}$, and then solving the unitarity equations order by order in $\tau_{ij}$. To first order in the perturbation this has been done by Tadej and Życzkowski @ZT, who found that the number of free parameters that survive to first order is $$D_1 = \sum_{n=0}^{N-1} \mbox{gcd}(n,N) \ , \label{TaZy}$$ where gcd denotes the greatest common divisor. If $N$ is prime this means that the number of free parameters is $2N-1$. This is the number one would naively expect by counting the number of equations and the number of parameters in the matrix. However, for non-prime values of $N$ the number $D_1$ is larger than that. We can multiply the rows and columns of a complex Hadamard matrix with $2N-1$ overall phase factors, while still preserving the Hadamard property. Hence $2N-1$ parameters are trivial, and it is customary to remove them by presenting complex Hadamard matrices in dephased form, such that the first row and the first column have real and positive entries. The number $$d_1 = D_1 - (2N-1) = \sum_{n=1}^{N-1} (\mbox{gcd}(n,N) - 1) \label{defect}$$ has been called the defect of the Fourier matrix @TZ, and gives an upper bound on the dimension of any smooth family of dephased complex Hadamard matrices passing through the Fourier matrix. Here we shall call it the linear defect since we found a way of defining order by order a number that is a natural generalization to higher orders of the defect and that coincides with it to first order; we shall then speak of the nth order defect. If $N = p^k$ is a prime power the situation is very satisfactory since explicit solutions for dephased Hadamard matrices with $d_1$ free parameters are known. These solutions are of an especially simple kind, known as affine families @TZ. We are concerned with other values of $N$, for which very little is known. An exception is the special case $N = 6$, for which $d_1 = 4$, a 3-dimensional family has been constructed explicitly @Karlsson, and a 4-dimensional family has been shown to exist @Szollosi [@Feriphd]. What is missing so far is a proof that the 4-dimensional family includes the Fourier matrix, and that it is smooth there. Numerical arguments for the truth of this have been presented @Skinner, and we will confirm this conclusion in a perturbative expansion that we carried to order 100. But it appears that the first order result is misleading in all other cases. Indeed for all values of $N$ less than 101 and not equal to 6 or to a prime power, we will prove that the dimension of the largest smooth family is strictly less than the linear defect. What we really want to know is by how much the dimension of the solution space differs from $d_1$. For $N = 12$, which is of some special interest @TZ, we find that the largest smooth family has dimension 13, while the linear defect is 17 and the largest explicitly known families have dimension 9. The solution in fact consists of two 13-dimensional families intersecting in a 9-dimensional affine family. Our evidence suggests that the situation is similar whenever $N$ is a product of three primes, two of them equal, and we are able to formulate an appealing conjecture of what the final picture is likely to be in this case. While these results fall short of providing a general solution to our problem they do make us feel that a general solution of a reasonably simple sort does exist. Most of the paper is devoted to explaining the procedure that leads to the results we have. In section 2 we give a bird's eyes view of the general method. A linear system of equations has to be solved at each order of the expansion, but the problem is non-trivial because it can happen that a solution exists only if non-linear consistency conditions are imposed on the lower order solutions. In section 3 we begin our discussion of complex Hadamard matrices, and set up the equations that are to be solved perturbatively. In sections 4, 5, and 6 we describe how the general method applies to the pattonwilliam@example.org. In section 7 we investigate all $N \leq 100$, and find out when the dimension of any smooth family is indeed less than $d_1$. In section 8 we discuss the case of $N = 12$ in full detail, and in section 9 we discuss the cases $N = 18, 20$, ending with a conjecture for all $N = p_1p_2^2$, where $p_1, p_2$ are prime numbers. The calculations were partly numerical, partly symbolical, and were performed using Mathematica. We warn the reader at the outset that our results rely on a considerable amount of calculational detail. Depending on interests the reader may therefore want to just glance at section 2—and perhaps at the toy model in Appendix D—and then go directly to section 10 where our conclusions are summarised (and where we offer some speculations concerning the final picture). In Appendix A we give some background information concerning complex Hadamard matrices, we define the notion of affine families, and we prove some results concerning them that we need in the main text. Appendix B gives an explicit construction of affine families for $N$ equal to a prime power. Appendix C contains an exact second order calculation, valid for all $N$. For ease of expression we refer to complex Hadamard matrices simply as "Hadamard matrices" from now on, and when we talk of "the dimension of the solution space" we refer to the dimension of the set of dephased Hadamard matrices connected to the Fourier matrix. <span>**2. The method**</span> Let us return to eqs. (\[1\]). It is assumed that we know one solution for the $N$ variables. By shifting the variables if necessary, we can arrange that $x_n = 0$ is a solution of the equations. When we expand the system around this solution the equations take the form $$f_m = A_{m;n}x_n + A_{m;n_1n_2}x_{n_1}x_{n_2} + ... = 0 \ . \label{2}$$ Summation over repeated indices is understood. Assume that the solution $x_n = 0$ belongs to a family of solutions $x_n(\tau_1, \dots , \tau_D)$ with $D$ unknown parameters. If the variables are expanded in these parameters we will obtain an expansion of the form $$x_n = x^{(1)}_n + x^{(2)}_n + x^{(3)}_n + ... \ . \label{expand}$$ We do not explicitly write out the dependence on the parameters. Inserting this into eqs. (\[2\]) we obtain $$f_m = A_{m;n}x^{(1)}_n + A_{m;n}x^{(2)}_n + A_{m;n_1n_2} x^{(1)}_{n_1}x^{(1)}_{n_2} + ... = 0 \ .$$ This equation is now to be solved order by order in the hidden parameters. Thus we obtain $$\begin{aligned} A_{m;n}x_n^{(1)} = 0 \hspace{90mm} \\ \nonumber \\ A_{m;n}x_n^{(2)} = - A_{m;n_1n_2}x_{n_1}^{(1)}x_{n_2}^{(1)} \hspace{63mm} \\ \nonumber \\ A_{m;n}x_n^{(3)} = - A_{m;n_1n_2}(x^{(2)}_{n_1}x^{(1)}_{n_2} + x^{(1)}_{n_1}x^{(2)}_{n_2}) %\hspace{42mm} \\ - A_{m;n_1n_2n_3}x^{(1)}_{n_1}x^{(1)}_{n_2}x^{(1)}_{n_3} \hspace{2mm} \end{aligned}$$ $$\begin{aligned} A_{m;n}x^{(4)}_n = - A_{m;n_1n_2}(x^{(3)}_{n_1}x^{(1)}_{n_2} + x^{(1)}_{n_1}x^{(3)}_{n_2} + x_{n_1}^{(2)}x_{n_2}^{(2)}) \hspace{25mm} \nonumber \\ \nonumber \\ -A_{m;n_1n_2n_3}(x_{n_1}^{(2)}x_{n_2}^{(1)}x_{n_3}^{(1)} + x_{n_1}^{(1)}x_{n_2}^{(2)}x_{n_3}^{(1)} + x_{n_1}^{(1)}x_{n_2}^{(1)}x_{n_3}^{(2)}) \hspace{3mm} \\ \nonumber \\ -A_{m;n_1n_2n_3n_4}x_{n_1}^{(1)}x_{n_2}^{(1)}x_{n_3}^{(1)}x_{n_4}^{(1)} \ , \hspace{43mm} \nonumber \end{aligned}$$ and so on to higher orders. At each order then we are faced with a linear system; homogeneous to first order and heterogeneous to the higher orders. At each order higher than the first this linear system may or may not—depending on the form of the original equations—impose restrictions on the solutions obtained in lower orders. To deal with these linear systems we introduce a pseudo-inverse of the $M\times N$ matrix $A_{m;n}$. This is a matrix $\hat{A}$ obeying $A\hat{A}A = A$. For this general discussion it is natural to choose the Moore-Penrose inverse for this purpose, since—due to some extra conditions—it is uniquely defined and easily computed @Penrose. The relevant theorem is that the linear system $$AX = B$$ admits a solution if and only if $$({\bf 1} - A\hat{A})B = 0 \ .$$ When this consistency condition is obeyed the general solution is $$X = \hat{A}B + ({\bf 1} - \hat{A}A)Z \ ,$$ where the $N$ components of the column vector $Z$ are arbitrary. The matrix $ {\bf 1} - \hat{A}A$ typically has rank less than $N$, so the number of free parameters in the homogeneous solution is typically less than $N$. The first order equations are homogeneous, and admit the homogeneous solution $$x_n^{(1)} = (\delta_{nn_1}-\hat{A}_{n;m}A_{m;n_1})z^{(1)}_{n_1} \equiv h_n^{(1)} \ .$$ The number of free parameters in the solution gives an upper bound on the dimension of the solution space. To second order the solution is a sum of a homogeneous and a heterogeneous part, $$x_n^{(2)} = h_n^{(2)} - \hat{A}_{n;m}A_{m;n_1n_2}h_{n_1}^{(1)} h_{n_2}^{(1)} \ ,$$ provided that the consistency condition $$(\delta_{mm_1}- A_{m;n}\hat{A}_{n;m_1})A_{m_1;n_1n_2}h_{n_1}^{(1)} h_{n_2}^{(1)} = 0$$ holds. Assume for the sake of the argument that it does, and write the solution as $$x_n^{(2)} = h_n^{(2)} + H_n^{(2)} \ ,$$ where the heterogeneous part is a known second order polynomial in $h_n^{(1)}$ (obeying $h_n^{(1)} \rightarrow \lambda h_n^{(1)} \Rightarrow H_n^{(2)} \rightarrow \lambda^2H_n^{(2)}$). To third order the heterogeneous part of the solution is $$H_n^{(3)} = - \hat{A}_{n;m}A_{m;n_1n_2}(x^{(2)}_{n_1}x^{(1)}_{n_2} + x_{n_1}^{(1)}x_{n_2}^{(2)}) - \hat{A}_{n;m}A_{m;n_1n_2n_3}x^{(1)}_{n_1}x_{n_2}^{(1)} x_{n_3}^{(1)} \ ,$$ provided that $$\begin{aligned} ({\bf 1} - A\hat{A})_{m,m_1}A_{m_1;n_1n_2}(x^{(2)}_{n_1}x^{(1)}_{n_2} + x_{n_1}^{(1)}x_{n_2}^{(2)}) + \nonumber \\ \ \\ + ({\bf 1} - A\hat{A})_{m,m_1}A_{m_1;n_1n_2n_3}x^{(1)}_{n_1}x^{(1)}_{n_2}x_{n_3}^{(1)} = 0 \ . \nonumber \end{aligned}$$ Due to the symmetrisation, and the second order consistency condition, this condition can be written as $$({\bf 1} - A\hat{A})_{m,m_1}\left( A_{m_1;n_1n_2}(H^{(2)}_{n_1} h^{(1)}_{n_2} + h_{n_1}^{(1)}H_{n_2}^{(2)}) + A_{m_1;n_1n_2n_3}h^{(1)}_{n_1}h^{(1)}_{n_2}h_{n_3}^{(1)} \right) = 0 \ .$$ This is a third order polynomial in $h_n^{(1)}$. As long as the consistency conditions continue to hold to order $s-1$, the consistency condition at order $s$ will always be a set of polynomial equations of order $s$ in $h_n^{(1)}$. If they hold to all orders the homogeneous solutions of order higher than one can be set to zero by means of a redefinition of the first order solution, and we are done. Assume for the sake of the argument that the consistency conditions do break down at third order. Then one must solve a set of third order polynomial equations that will restrict the first order homogeneous solution. We cannot say by how much the upper bound on the dimension of the solution space drops until these equations have been solved. When we continue to the next order we can still write $$x_n^{(4)} = h_n^{(4)} + H_n^{(4)} \ ,$$ where the heterogeneous part is a polynomial of fourth order in the parameters and depending on $h_n^{(1)}$, $h_n^{(2)}$, and $h_n^{(3)}$. The consistency condition at fourth order is $$\begin{aligned} ({\bf 1} - A\hat{A})_{mm_1}\big( A_{m_1;n_1n_2}(H^{(3)}_{n_1} h^{(1)}_{n_2} + h^{(1)}_{n_1}H^{(3)}_{n_2} + \hspace{30mm} \nonumber \\ \nonumber \\ + h^{(2)}_{n_1}H^{(2)}_{n_2} + H^{(2)}_{n_1}h^{(2)}_{n_2} + H^{(2)}_{n_1}H^{(2)}_{n_2}) + \hspace{15mm} \nonumber \\ \nonumber \\ + A_{m_1;n_1n_2n_3}(h^{(2)}_{n_1}h^{(1)}_{n_2}h^{(1)}_{n_3} + h^{(1)}_{n_1} h^{(2)}_{n_2}h^{(1)}_{n_3} + h^{(1)}_{n_1}h^{(1)}_{n_2}h^{(2)}_{n_3} + \nonumber \\ \ \\ + H^{(2)}_{n_1}h^{(1)}_{n_2}h^{(1)}_{n_3} + h^{(1)}_{n_1}H^{(2)}_{n_2} h^{(1)}_{n_3} + h^{(1)}_{n_1}h^{(1)}_{n_2}H^{(2)}_{n_3}) \hspace{5mm} \nonumber \\ \nonumber \\ + A_{m_1;n_1n_2n_3n_4}h^{(1)}_{n_1}h^{(1)}_{n_2}h^{(1)}_{n_3}h^{(1)}_{n_4}\big) = 0 \ . \hspace{15mm} \nonumber \end{aligned}$$ Note that $h^{(3)}_n$ does not appear because the consistency condition is fullfilled at order two. This is a set of linear equations for the $h^{(2)}_n$, briefly $Uh^{(2)}_n=V$. The solution will be a quotient of two polynomials in $h^{(1)}_n$ which is homogeneous of order two in that variable. If the rank of the matrix $U$ is equal to the number $u$ of variables $h^{(1)}_n$ fixed by the third order consistency equations then the corresponding variables are fixed once and for all (it is easy to check that to fifth order one gets consistency equations of the type $Uh^{(3)}_n=W$, where $U$ is the same matrix). However these linear systems come with their own consistency conditions which, if not automatically satisfied, will further fix the $h^{(1)}_n$ and further lower the defect. We have not investigated in any systematic manner what happens if these higher order consistency conditions break down at some higher order–although this does happen in some of the concrete cases that we study below. If the rank of $U$ is lower than $u$ then the remaining $h^{(2)}_n$ must be fixed at higher order by non-linear equations (as would be the case for systems having sets of solutions which are tangent at the point around which we are expanding). This did not happen in the particular cases under study; also the toy model in Appendix D provides a reassuring consistency check. It is time to turn to the subject we want to deal with. We will then be able to adapt our method to the special form of the equations we encounter. In particular the Moore-Penrose inverse will not be needed. <span>**3. The Hadamard equations**</span> The equations ensuring that a matrix is a Hadamard matrix define an algebraic variety of some sort @Dita. Since our aim is to solve these equations order by order in an expansion around the Fourier matrix $F$ we begin by performing a discrete Fourier transformation of all our matrices, that is $$H \rightarrow M = HF^\dagger \ ,$$ where the dagger denotes hermitian conjugation. This means that the Fourier matrix itself is represented by the unit matrix. We prefer to represent the Fourier matrix with the zero matrix, so we shift the matrix to $$X = {\bf 1} - M \ .$$ We must now formulate the condition that $H$ be a Hadamard matrix as a set of equations for the matrix $X$. In order to be able to address the equations in an efficient way we aim for a subset of equations in which the complex conjugates of the matrix elements do not occur. For this purpose we introduce the permutation matrix $P$ with matrix elements $$P_{ij} = \delta_{i+1,j} \ .$$ This matrix generates the cyclic group of order $N$, and has the columns of the Fourier matrix as its eigenvectors. We denote the commutator of two matrices by $[A,B]$, and the vector of diagonal elements of a matrix by diag$(A)$. : <span>*$H$ is a Hadamard matrix if and only if $M = HF^\dagger$ obeys*</span> $$MM^\dagger = {\bf 1}$$ $$\mbox{diag}(MP^nM^\dagger) = 0 \ , \hspace{8mm} n \neq 0 \ \mbox{mod} \ N \ , \label{cond2}$$ <span>*where $P$ is the permutation matrix defined above. For the matrix $X = {\bf 1} - M$ these equations read*</span> $$X + X^\dagger = XX^\dagger \label{ETT}$$ $$\mbox{diag} \left( \sum_{p=0}^\infty [P^n,X]X^p \right) = 0 \ , \hspace{8mm} n \neq 0 \ \mbox{mod} \ N \ , \label{TVA}$$ <span>*at least in a neighbourhood of the Fourier matrix.*</span> : Direct calculation shows that $$(MP^nM^\dagger )_{ii} = \sum_j\omega^{nj}|H_{ij}|^2 \ ,$$ and elementary properties of the discrete Fourier transform now establish that eq. (\[cond2\]) is necessary and sufficient, given that $M$ is unitary. Since unitarity is imposed separately we may replace the matrix $M^\dagger$ by the matrix $M^{-1}$ in eq. (\[cond2\]). Expanding $M^{-1} = ({\bf 1}-X)^{-1}$ in a geometric series and using the property that $$\mbox{diag}\left( P^n\sum_{p=0}^\infty X^p\right) = \mbox{diag} \left( P^n\sum_{p=0}^\infty X^{p+1} \right)$$ we pattonwilliam@example.org. (\[TVA\]). The unitarity condition on $M$ is clearly equivalent to eq. (\[ETT\]). $\Box$ The plan now is to first solve eq. (\[TVA\]) order by order in a perturbative expansion, using complex entries with no complex conjugates appearing, and to impose the unitarity condition at the end. The alternative, to impose unitarity at each order from the beginning, is less convenient for symbolic calculations using Mathematica. To deal with eq. (\[TVA\]) following the method outlined in section 2 the first step is to expand $X$ order by order in the unknown parameters. To follow the letter of the method we should reshape the matrix $X$ into a vector, but we will not actually do so since it will turn out that we can solve directly for the matrix $X$. Thus we write $$X = \sum_{s=1}^\infty X^{(s)} \ . \label{expansion}$$ Inserting this into eq. (\[TVA\]), which itself contains an infinite sum to be expanded, we find that the equations at each order $s$ form the inhomogeneous linear system $$\mbox{diag}\left( [P^n,X^{(s)}] + B^{(s,n)} \right) = 0 \ , \label{higher}$$ where $B^{(s,n)}$ can be computed in terms of quantities determined at lower orders. The first few orders are $$\mbox{diag}\left( [P^n,X^{(1)}]\right) = 0 \hspace{82mm}$$ $$\mbox{diag}\left( [P^n,X^{(2)}] + [P^n,X^{(1)}]X^{(1)} \right) = 0 \hspace{54mm} \label{second}$$ $$\mbox{diag}\left( [P^n,X^{(3)}] + [P^n,X^{(2)}]X^{(1)} + [P^n,X^{(1)}](X^{(2)} + X^{(1)}X^{(1)}) \right) = 0 \ .$$ At each order $s$ this is a linear inhomogeneous equation in the unknown $X^{(s)}$. We record that $$B^{(s,n)} = \sum_{p=1}^{s-1} \sum_{\substack{s_i\geq 1 \\ s_0 + \dots + s_p = s}} [P^n,X^{(s_0)}]X^{(s_1)} \dots X^{(s_p)} \ . \label{Bsn}$$ We will need this result in the proofs of Theorems 4 and 5 below. We end this section with two comments. The first concerns transposition of Hadamard matrices: If $H$ is a Hadamard matrix so is its transpose $H^{\rm T}$, a fact that will play a role when we discuss explicit solutions later on. It is easy to show that $$H \rightarrow H^{\rm T} \hspace{5mm} \Leftrightarrow \hspace{5mm} X \rightarrow FX^{\rm T}F^\dagger \ . \label{transpose}$$ Hence transposition is slightly obscured by the discrete Fourier transform. The second comment concerns dephasing: In the introduction we observed that any Hadamard matrix admits $2N-1$ free parameters that are in a sense trivial, and that these trivial parameters can be removed by insisting that the first row and the first column of the matrix has entries equal to $1/\sqrt{N}$ only. If we dephase the first row of the matrix $H$ we will obtain a matrix $X$ whose first row contains zero entries only. If we also dephase the first column of $H$ we find that $X$ takes the form $$X = \left[ \begin{array}{cccc} 0 & 0 & \dots & 0 \\ 0 & \ & \ & \ \\ \vdots & \ & \tilde{X} & \\ 0 & \ & \ & \ \end{array} \right] \ , \hspace{12mm} \sum_{j=1}^{N-1}\tilde{X}_{ij} = 0 \ . \label{dephasing}$$ In our calculations we did not impose this condition, but we will state our results in terms of the dimension of the set of dephased matrices. <span>**4. The homogeneous system**</span> We begin by solving the linear first order system ($n \neq 0$ mod $N$) $$\mbox{diag}[P^n, X^{(1)}] = 0 \hspace{5mm} \Leftrightarrow \hspace{5mm} X^{(1)}_{i+n,i} - X^{(1)}_{i,i-n} = 0 \ .$$ We observe that there is no condition on the diagonal elements of $X$, and that the equalities that do arise connect only elements on some given displaced diagonal. On the $n$th displaced diagonal we obtain the string of equalities $$X_{i,i-n} = X_{i+n,i} = X_{i+2n,i+n} = ... \ .$$ It pays to think of the matrix as built up from displaced diagonals rather than columns, so we introduce the parametrisation $$X_{i,j} = x_{i,j-i} \ .$$ Recall that all matrix indices obey modulo $N$ arithmetic. Our string of equalities becomes $$x_{i,-n} = x_{i+n,-n} = x_{i+2n,-n} = ... \ .$$ Now let the greatest common divisor of $n$ and $N$ be denoted by $g$, so that $$N = gr \ , \hspace{8mm} n = gs \ .$$ Taking the modulo $N$ arithmetic into account we see that the string of equalities ends with an identity after $r$ steps, $$x_{i,-n} = ... = x_{i+rn,-n} \equiv x_{i+sN,-n} \equiv x_{i,-n} \ . \label{string1}$$ There are $r-1$ non-trivial equalities here. Written in a more transparent fashion they are $$x_{i,-n} = x_{i+g,-n} = x_{i+2g,-n} = ... = x_{i+(r-1)g,-n} \ . \label{string2}$$ See Fig. \[fig:defect1b\]. This means that the $n$th displaced diagonal consists of $g$ sets of $r$ identical elements. Recalling that the elements on the main diagonal are unrestricted it follows that the number of free parameters at first order is $$\sum_{n=0}^{N-1} \mbox{gcd}(n,N) = N + \sum_{n=1}^{N-1}\mbox{gcd}(n,N) \ .$$ This agrees with the result (\[TaZy\]) due to Tadej and Życzkowski @ZT, except that at this stage our parameters are complex since we have not yet imposed condition (\[ETT\]). To linear order condition (\[ETT\]) evidently means that we end up with exactly this number of real parameters, so the agreement is in fact complete. If $N = p$ is a prime number all elements on each displaced diagonal are set equal. In this case then there are exactly $2N-1$ free parameters in the solution, $N$ of them coming from the unrestricted main diagonal, which means that the dephased Fourier matrix is isolated, not belonging to a continuous family of dephased Hadamard matrices. In effect we have proved : <span>*At any order, the homogeneous solution to our linear system can be written as*</span> $$X^{(s)}_{i,j} = x^{(s)}_{i \ {\rm mod \ gcd}(j-i,N),j-i \ {\rm mod} \ N} \ . \label{losning}$$ An illustration of the proof is given in Fig. 1. If $N = p$ is a prime number $X$ is a circulant matrix, except that its main diagonal is unrestricted. Its dephased form is zero. A more interesting example is that of $N = 6$, for which the first order solution is $$X^{(1)} = \left( \begin{array}{cccccc} x_{0,0} & x_{0,1} & x_{0,2} & x_{0,3} & x_{0,4} & x_{0,5} \\ x_{0,5} & x_{1,0} & x_{0,1} & x_{1,2} & x_{1,3} & x_{1,4} \\ x_{0,4} & x_{0,5} & x_{2,0} & x_{0,1} & x_{0,2} & x_{2,3} \\ x_{0,3} & x_{1,4} & x_{0,5} & x_{3,0} & x_{0,1} & x_{1,2} \\ x_{0,2} & x_{1,3} & x_{0,4} & x_{0,5} & x_{4,0} & x_{0,1} \\ x_{0,1} & x_{1,2} & x_{2,3} & x_{1,4} & x_{0,5} & x_{5,0} \end{array} \right) \ . \label{6=N}$$ When we remove the trivial parameters by dephasing the Hadamard matrix this is $$X^{(1)} = \left( \begin{array}{cccccc} 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & d_1 & 0 & x_{1,2} & x_{1,3} & x_{1,4} \\ 0 & 0 & d_2 & 0 & 0 & x_{2,3} \\ 0 & x_{1,4} & 0 & d_3 & 0 & x_{1,2} \\ 0 & x_{1,3} & 0 & 0 & d_4 & 0 \\ 0 & x_{1,2} & x_{2,3} & x_{1,4} & 0 & d_5 \end{array} \right) \ . \label{N=6}$$ Now the diagonal elements $d_i$ are dependent parameters since dephasing the Hadamard matrix means that the column sums of $X$ vanish, so the number of free parameters equals $4$. The affine Fourier family (see Appendix A) is obtained by setting $x_{1,3} = x_{2,3} = 0$, and its transpose by setting $x_{1,2} = x_{1,4} = 0$; to see what eq. (\[transpose\]) implies for $X$ when $H$ is transposed it is helpful to begin with the observation that circulant matrices are diagonalised by the Fourier matrix. <span>**5. The heterogeneous systems**</span> The question now is whether there are non-trivial consistency conditions on the linear systems that appear when we insert the expansion (\[expansion\]) in eq. (\[TVA\]). If so the first order result is misleading, and the true dimension of the solution space is lower than the linear result suggests it should be. If $N$ is a prime or a power of a prime we know—see section 1—that this cannot happen, but for all other choices of $N$ we move on unknown ground. The equations that we are faced with take the form (\[higher\]). Our aim is to bring their solution to a form precise enough to enable us to implement it in Mathematica. This is achieved in the following two theorems. : <span>*The general solution to the heterogeneous linear system (\[higher\]) is*</span> $$X^{(s)}_{i,j} = x^{(s)}_{i \ {\rm mod} \ {\rm gcd}(j-i,N),j-i} + \sum_{q=0}^{m[i,j,N]-1}B^{(s,i-j)}_{i+q(i-j),i+q(i-j)} \ , \label{solution}$$ <span>*subject to the consistency conditions*</span> $$\sum_{q=0}^{N/{\rm gcd}(n,N) - 1}B^{(s,n)}_{i + q \ {\rm gcd}(n,N),i+q \ {\rm gcd}(n,N)} = 0 \ , \label{cons}$$ <span>*where $n \in \{ 1, \dots , N-1 \}$, $i \in \{ 0, \dots , \mbox{gcd}(n,N) - 1\}$ in the consistency conditions, and the $x_{i,j-i}$ are free parameters. The integer $m = m[i,j,N]$ is given by*</span> $$m = \frac{i \ \mbox{mod gcd}(i-j,N)-i}{\mbox{gcd}(i-j,N)} \left( \frac{i-j}{\mbox{gcd}(i-j,N)}\right)^{-1} \ \mbox{mod} \ \frac{N}{\mbox{gcd}(i-j,N)} \ , \label{modinverse}$$ <span>*where the inverse is the multiplicative inverse modulo $N/\mbox{gcd}(i-j,N)$.*</span> In words, the consistency conditions at order $s$ say that for each displaced diagonal labelled by $n$ the $B^{(s,n)}$ sum to zero when summed over a set of positions with equal values of the parameters in the homogeneous solution. : Using explicit matrix indices, always taken modulo $N$, eq. (\[higher\]) becomes $$X^{(s)}_{i,i-n} = X^{(s)}_{i+n,i} + B^{(s,n)}_{ii} \ .$$ Setting $n = i-j$ we find by iterating in $m$ steps that $$X^{(s)}_{i,j} = X^{(s)}_{i+m(i-j),j+m(i-j)} + \sum_{q=0}^{m-1} B^{(s,i-j)}_{i+q(i-j),i+q(i-j)} \ . \label{alongdiag}$$ When $$m(i-j) = 0 \ \ \mbox{mod} \ N \hspace{5mm} \Leftrightarrow \hspace{5mm} m = \frac{kN}{\mbox{gcd}(i-j,N)} \ , \ \ k \in {\bf Z}$$ we obtain a consistency condition which—after a slight reordering of the sum—is exactly eq. (\[cons\]). This is the same reordering that was used to go from (\[string1\]) to (\[string2\]). Now we must find a particular solution of the heterogeneous system. We begin by choosing all matrix elements corresponding to independent parameters in the homogeneous solution to zero, beginning with all elements in the upmost row and continuing downwards until the independent elements are exhausted. For this particular solution $$i \mbox{\ mod gcd}(i-j,N) = i \hspace{5mm} \Rightarrow \hspace{5mm} X^{(s)}_{i,j} = 0 %X^{(s)}_{i \mbox{\small \ mod gcd}(j-i,N), j %\mbox{\small \ mod gcd}(j-i,N)} = 0 \ . \label{villkor}$$ Coming back to eq. (\[alongdiag\]), which relates elements along the $(i-j)$th diagonal in steps of gcd$(i-j,N)$, we see that we obtain a particular solution fully determined by the lower order solution provided that the first term on the right hand side vanishes. Given the conditions (\[villkor\]) that we already imposed this will be ensured if we can find (for each $i,j,N$) an integer $m$ such that $$i + m(i-j) = i + m(i-j) \ \mbox{mod gcd}(i-j,N) = i \ \mbox{mod gcd}(i-j,N) \ .$$ This is equivalent to $$\left\{ m\frac{i-j}{\mbox{gcd}(i-j,N)} = \frac{i \ \mbox{mod gcd}(i-j,N) - i}{\mbox{gcd}(i-j,N)}\right\} \ \mbox{mod} \frac{N}{\mbox{gcd} (i-j,N)} \ .$$ The solution in the range $\{ 0, ... , N/\mbox{gcd}(i-j,N)\}$ is given in eq. (\[modinverse\]). The modular multiplicative inverse used there exists since the numbers $(i-j)/\mbox{gcd}(i-j,N)$ and $N/\mbox{gcd}(i-j,N)$ are coprime. Using this value of $m$ in eq. (\[alongdiag\]) gives the particular solution, and we arrive at the general solution (\[solution\]) by adding the general solution of the homogeneous equations. $\Box$ To illustrate the proof we give the particular solution for $N = 6$: $$\left( \begin{array}{cccccc} 0 & 0 & 0 & 0 & 0 & 0 \\ \\ \sum_{0}^4B_{1+q}^{(1)} & 0 & B_{1}^{(5)} & 0 & 0 & 0 \\ \\ \sum_{0}^1B_{2+2q}^{(2)} & \sum_{0}^3B_{2+q}^{(1)} & 0 & \sum_{0}^1B_{2-q}^{(5)} & B_{2}^{(4)} & 0 \\ \\ B_{3}^{(3)} & \sum_{0}^1B_{3+2q}^{(2)} & \sum_{0}^2B_{3+q}^{(1)} & 0 & \sum_{0}^2B_{3-q}^{(5)} & B_{3}^{(4)} \\ \\ \sum_{0}^1B_{4-2q}^{(4)} & B_4^{(3)} & B_4^{(2)} & \sum_{0}^1B_{4+4q}^{(1)} & 0 & \sum_{0}^3B_{4-q}^{(5)} \\ \\ \sum_0^4B_{5-q}^{(5)} & \sum_0^1B_{5-2q}^{(4)} & B_{5}^{(3)} & B_{5}^{(2)} & B_5^{(1)} & 0 \end{array} \right)$$ where (for typographical reasons) we let $B^{(s,n)}_{i,i}$ be denoted by $B_i^{(n)}$. To make use of theorem 3 we must compute the inhomogeneous term $B^{(s,n)}_{i,i}$. This is achieved in the next theorem. : <span>*The inhomogeneous part $B^{(s,n)}$ is given iteratively by*</span> $$B^{(1,n)} = 0$$ $$B^{(s,n)} = \sum_{r=1}^{s-1}\left( [P^n,X^{(r)}] + B^{(r,n)}\right) X^{(s-r)} \ .$$ The proof is straightforward, using expression (\[Bsn\]). It is hard to continue the discussion with any generality, but we have been able to prove that the consistency conditions arising at second order, eqs. (\[second\]), are identically satisfied for all $N$. We give a brief sketch of a proof in Appendix C. At third order the consistency conditions do break down for some values of $N$, as will be discussed in section 7. <span>**6. The unitarity equations**</span> We must now impose the unitarity condition (\[ETT\]) on the solutions obtained in section 5. When $X$ is expanded in a power series the unitarity condition at order $s$ reads $$X^{(s)} + \left( X^{(s)}\right)^\dagger = \sum_{r=1}^{s-1}X^{(s-r)} \left( X^{(r)}\right)^\dagger \ . \label{Xdagger}$$ We insert the solution $$X^{(s)}_{i,j} = x_{i,j-i}^{(s)} + H^{(s)}_{i,j}(X^{(1)}, \dots , X^{(s-1)}) \ ,$$ where $H_{i,j}^{(s)}$ is the heterogeneous part as given in theorem 3, and $x^{(s)}_{i,j-i}$ is short for $x^{(s)}_{i \ {\rm mod \ gcd}(j-i,N),j-i \ {\rm mod} \ N}$. The equations to be solved are now $$x^{(s)}_{i,j-i} + \bar{x}^{(s)}_{i,i-j} = F_{i,j}^{(s)} \ ,$$ where complex conjugation is denoted by an overbar. We used $i \ {\rm mod \ gcd}(j-i,N) = j \ {\rm mod \ gcd}(j-i,N)$, and we also defined $$F^{(s)} = \sum_{r=1}^{s-1}X^{(s-r)} \left( X^{(r)}\right)^\dagger - H^{(s)} - \left( H^{(s)}\right)^\dagger \ .$$ Note that this depends on the solution only to orders less than $s$. : <span>*The matrix $H = ({\bf 1}-X)F$ is unitary order by order in the perturbative expansion provided that the following conditions are imposed on its matrix elements:*</span> $$\mbox{Re}\left[ x_{i,0}^{(s)}\right] = \frac{1}{2}F_{i,i}^{(s)}$$ $$\mbox{Re}\left[ x_{i \mbox{{\small \ mod}}\ N/2,N/2}^{(s)}\right] = \frac{1}{2}F_{i,i+N/2}^{(s)} \hspace{5mm} \mbox{\sl if} \ N \ \mbox{\sl is even} \label{ditt}$$ $$x^{(s)}_{i \mbox{{\small \ mod gcd}}(n,N),-n} = F_{i,j}^{(s)} - \bar{x}^{(s)}_{i \mbox{{\small \ mod gcd}}(n,N),n} \hspace{5mm} \mbox{\sl for} \ 0 < n < N/2 \ . \label{datt}$$ : Most of the calculation is already done, but in eqs. (\[ditt\]-\[datt\]) some equations are repeated as $i$ runs through its $N$ values and we must prove consistency, namely that $F^{(s)}$ solves the same linear system as does the homogeneous solution. Thus we require $$\mbox{diag}[P^n,F^{(s)}] = 0 \ .$$ Using the fact that diag$\{ [P^n,H^{(s)}]\} = - \mbox{diag}\{ B^{(s,n)}\}$ and recalling that $(P^n)^\dagger = P^{-n}$, a calculation shows that $$\begin{aligned} \mbox{diag}[P^n,F^{(s)}] = \mbox{diag}\left( \sum_{r=1}^{s-1} [P^n,X^{(s-r)}]X^{(r)\dagger} + B^{(s,n)} \right) - \ \ \ \nonumber \\ \ \label{noll} \\ \hspace{35mm} - \mbox{diag}\left( \sum_{r=1}^{s-1} [P^{-n},X^{(s-r)}]X^{(r)\dagger} + B^{(s,-n)} \right)^\dagger \ . \nonumber \end{aligned}$$ Next we show directly from eq. (\[Xdagger\]) that $$X^{(s)\dagger} = - \sum_{p=1}^s \sum_{\substack{s_i\geq 1 \\ s_1 + \dots + s_p = s}} X^{(s_1)}\dots X^{(s_p)} \ .$$ Using this result, and using eq. (\[Bsn\]) to substitute for $B^{(s,n)}$, we see that the right hand side of eq. (\[noll\]) vanishes, as was to be shown. $\Box$ We illustrate this by imposing unitarity on the first order result for $N = 6$ given in eq. (\[6=N\]). It now reads $$X^{(1)} = \left( \begin{array}{rrrrrr} y_{0,0} & x_{0,1} & x_{0,2} & y_{0,3} & -\bar{x}_{0,2} & -\bar{x}_{0,1} \\ -\bar{x}_{0,1} & y_{1,0} & x_{0,1} & x_{1,2} & y_{1,3} & -\bar{x}_{1,2} \\ -\bar{x}_{0,2} & -\bar{x}_{0,1} & y_{2,0} & x_{0,1} & x_{0,2} & y_{2,3} \\ y_{0,3} & -\bar{x}_{1,2} & -\bar{x}_{0,1} & y_{3,0} & x_{0,1} & x_{1,2} \\ x_{0,2} & y_{1,3} & -\bar{x}_{0,2} & -\bar{x}_{0,1} & y_{4,0} & x_{0,1} \\ x_{0,1} & x_{1,2} & y_{2,3} & -\bar{x}_{1,2} & -\bar{x}_{0,1} & y_{5,0} \end{array} \right) \ . \label{unitary}$$ The matrix elements denoted $y_{i,j}$ are purely imaginary. The others are complex and related in pairs by complex conjugation. The important point is that the unitarity condition simply cuts the number of free parameters in half; in other words if there were $d$ complex parameters in the perturbative solution of eq. (\[TVA\]) then we end up with $d$ real parameters after imposing unitarity. The difficult consistency conditions appear only in the solution of eq. (\[TVA\]). We are unable to show in general that unitarity also cuts the number of variables fixed by a non-trivial consistency condition in half. Still, in section 8 we prove that this indeed happens for the particular case of $N = 12$. We believe that the issue must be dealt with on a case-by-case basis. <span>**7. When do the consistency conditions break down?**</span> As was mentioned at the end of section 5 the consistency conditions always hold to second order. For third order and higher we have used Mathematica to perform the calculation numerically, using random values for the free parameters. For some dimensions to be discussed below the calculation was also performed symbolically. When $N$ is a power of a prime we found no breakdown in the consistency conditions to the orders we checked. This had to be so because in this case there do exist affine families of Hadamard matrices with their dimension given by the linear defect $d_1$. For $N = 2\cdot 3 = 6$ we computed (numerically) the higher order contributions to order 100 in the perturbation series, without encountering any breakdown of the consistency conditions. There seemed to be no point in going further. The calculation clearly supports the extant conjecture that the $N = 6$ Fourier matrix belongs to a smooth 4-parameter family of dephased Hadamard matrices. For all other choices of $N \leq 100$ we found that the consistency conditions do break down at some order $s$, according to a definite pattern. Let $p_1, p_2, p_3, \dots$ be different prime numbers. Then the consistency conditions - <span>hold to all orders if $N$ is a power of a prime (and to order 100 if $N = 6)$</span> - <span>break at order 11 if $N = 10$</span> - <span>break at order 7 if $N= 2p_1$ and $p_1 > 5$ is odd</span> - <span>break at order 5 if $N = p_1p_2$ is odd</span> - <span>break at order 4 if $N = p_1^{k_1}p_2^{k_2}$ and $k_1k_2 > 1$</span> - <span>break at order 3 if $N = p_1^{k_1}p_2^{k_2}p_3^{k_3}$.</span> For $N \leq 100$ there are no examples of an integer that is a product of four different primes, but we did check that the consistency conditions break at order 3 for $N = 2\cdot 3\cdot 5 \cdot 7 = 210$. Again, Appendix C contains a proof that the consistency conditions always hold to second order. It is very encouraging that an orderly pattern emerges. <span>**8. The $N = 12$ case**</span> What we really want to know is the dimension of the solution space to all orders. We will discuss the case $N = 12$ in detail. The defect at linear order is $d_1 =17$, and it is also known that the Fourier matrix belongs to seven distinct affine families of dimension $d_A = 9$ @TZ. Therefore we know at the outset that the dimension of the dephased solution space lies between these bounds. When the calculation is continued beyond linear order we find that the consistency conditions for the linear system break down at fourth order in the perturbation, resulting in a set of fourth order polynomials to be solved. There are 40 variables in the first order solution. 23 of those are trivial (since they determine the $2N-1$ free phases) so we expect the consistency conditions to depend on 17 variables. There are only 13 conditions that do not vanish automatically, and close inspection shows that only 13 linear combinations of the variables enter these equations. To be precise, the consistency conditions are fourth order polynomials in the 13 variables $$\begin{array}{ll} x_2 = x_{0,2}-x_{1,2} \\ x_{10} = x_{0,10} - x_{1,10} \\ x_{4a} = x_{0,4} - x_{2,4} \\ x_{4b} = x_{1,4} - x_{3,4} \\ x_{8a} = x_{0,8} - x_{2,8} \\ x_{8b} = x_{1,8} - x_{3,8} \\ x_{6a} = x_{0,6} - x_{3,6} \\ x_{6b} = x_{4,6} - x_{1,6} \\ x_{6c} = x_{2,6} - x_{5,6} \end{array} \hspace{10mm} \begin{array}{ll} x_{3a} = 2x_{0,3} - x_{1,3} - x_{2,3} \\ x_{3b} = 2x_{1,3} - x_{0,3} - x_{2,3} \\ x_{3c} = 2x_{2,3} - x_{0,3} - x_{1,3} \\ x_{9a} = 2x_{0,9} - x_{1,9} - x_{2,9} \\ x_{9b} = 2x_{1,9} - x_{0,9} - x_{2,9} \\ x_{9c} = 2x_{2,9} - x_{0,9} - x_{1,9} & \ . \end{array} \label{variables}$$ Note that there are only 13 independent variables, because $x_{3a} + x_{3b} + x_{3c} = x_{9a} + x_{9b} + x_{9c} = 0$. We next define the auxiliary polynomials $$p_1 = x_{3a}^2 + x_{9a}^2 \hspace{8mm} p_2 = x_{3b}^2 + x_{9b}^2 \hspace{8mm} p_3 = x_{3c}^2 + x_{9c}^2$$ $$p_4 = x_{4a}^2 - x_{4b}^2 \hspace{6mm} p_5 = x_{8a}^2 - x_{8b}^2 \hspace{6mm} p_6 = x_{4a}x_{8a} - x_{4b}x_{8b} \ .$$ The complete set of consistency conditions now takes the form $$p_1p_6 = p_2p_6 = p_3p_6 = 0$$ $$(p_1+p_2+p_3)p_4 = (p_1+p_2+p_3)p_5 = 0$$ $$x_{4a}x_{10}(p_1+p_2+p_3) + x_{8a}(x_{6a}p_1 + x_{6b}p_2 + x_{6c}p_3) = 0$$ $$x_{4b}x_{10}(p_1+p_2+p_3) + x_{8b}(x_{6a}p_1 + x_{6b}p_2 + x_{6c}p_3) = 0$$ $$x_{8a}x_{2}(p_1+p_2+p_3) + x_{4a}(x_{6a}p_1 + x_{6b}p_2 + x_{6c}p_3) = 0$$ $$x_{8b}x_{2}(p_1+p_2+p_3) + x_{4b}(x_{6a}p_1 + x_{6b}p_2 + x_{6c}p_3) = 0$$ $$3x_{3a}(x_{10}p_4+x_2p_5) + 2p_6\left( x_{3a}(2x_{6a} + x_{6c}) + x_{3b} (x_{6c} - x_{6b})\right) = 0 \ \$$ $$3x_{3b}(x_{10}p_4+x_2p_5) + 2p_6\left( x_{3b}(2x_{6b} + x_{6c}) + x_{3a} (x_{6c} - x_{6a})\right) = 0 \ \$$ $$3x_{9a}(x_{10}p_4+x_2p_5) + 2p_6\left( x_{9a}(2x_{6a} + x_{6c}) + x_{9b} (x_{6c} - x_{6b})\right) = 0 \ \$$ $$3x_{9b}(x_{10}p_4+x_2p_5) + 2p_6\left( x_{9b}(2x_{6b} + x_{6c}) + x_{9a} (x_{6c} - x_{6a})\right) = 0 \ .$$ There are three ways of satisfying these equations. Solutions of type 1 are obtained if $p_4 = p_5 = p_6 =0$. This implies that $$\begin{array}{l} x_{4a} = x_{4b} \\ x_{8a} = x_{8b} \end{array} \hspace{7mm} \mbox{or} \hspace{7mm} \begin{array}{ll} x_{4a} = - x_{4b} \\ x_{8a} = - x_{8b} & \ . \end{array}$$ Two polynomial equations remain, so the dimension drops by 4. Note that the four conditions $$x_{4a} = x_{4b} = x_{8a} = x_{8b} = 0 \label{typI}$$ solves the entire system. Call this special case the type I solution. Solutions of type 2 are obtained if $p_1 = p_2 = p_3 = 0$. This implies that $$\begin{array}{l} x_{3a} = ix_{9a} \\ x_{3b} = ix_{9b} \end{array} \hspace{7mm} \mbox{or} \hspace{7mm} \begin{array}{ll} x_{3a} = - ix_{9a} \\ x_{3b} = - ix_{9b} & \ . \end{array}$$ Two polynomial equations remain, so the dimension again drops by 4. Note that the four conditions $$x_{3a} = x_{3b} = x_{9a} = x_{9b} = 0 \label{typII}$$ solves the entire system. Call this special case the type II solution. When neither $p_1,p_2,p_3$ nor $p_4,p_5$ are all zero the equations imply $$\begin{aligned} \left\{ \begin{array}{ll} p_1+p_2+p_3 = 0 \\ \\ p_6 = 0 \end{array} \right. \hspace{21mm} \label{L} \\ \left\{ \begin{array}{ll} x_{6a}p_1 + x_{6b}p_2 + x_{6c}p_3 = 0 \\ \\ x_{10}p_4 + x_2p_5 = 0 & \ . \end{array} \right. \label{R}\end{aligned}$$ Hence the consistency conditions impose 4 independent conditions on our variables, meaning that the defect again drops from 17 to 13. Call these solutions type 3. Solutions of type 2 are obtained by transposition from solutions of type 1, and similarly for types II and I. Some work is needed to verify this since transposing the Hadamard matrix leads to a slightly unobvious operation on the matrix $X$; see (\[transpose\]). Solutions of type 3 on the other hand form a self-cognate family (at least when considered as an algebraic variety), since transposition interchanges eqs. (\[L\]) and eqs. (\[R\]). Let us now impose unitarity, following section 6. The consistency conditions we have encountered are quartic polynomials in the first order matrix elements, and we begin by imposing unitarity to first order. Then $x_{i,6}$ become purely imaginary, and the remaining parameters become related by complex conjugation ($x_{0,2} + \bar{x}_{0,10} = 0$, …, $x_{0,3} + \bar{x}_{0,9} = 0$, …, $x_{0,4} + \bar{x}_{0,8} = 0$, …). Compare the simpler example given in eq. (\[unitary\]). This means that $p_1,p_2,p_3,p_6$ are real, while $p_5 = \bar{p}_4$. There are 8 polynomial equations remaining. Solving them one ends up with the same solutions as one obtains by imposing unitarity on the solutions of the complex equations. Thus the possible difficulty mentioned at the end of section 6 does not arise in this case. Having solved the consistency conditions that arise at fourth order, we must now address the question whether the 13-dimensional dephased solutions found at fourth order are truly 13-dimensional, or whether their dimensions drop due to consistency conditions appearing in higher orders. To this end we continued the calculation numerically to order 11 for the solutions of type I and II. No further breakdown of any consistency condition was observed. For solutions of type 1 on the other hand a further breakdown of the consistency conditions occurs at order 6, which means that the dimension of this family of solutions drops below 13. Type 2 must behave similarly. For type 3 there is a further breakdown of the consistency conditions already at order 5. Thus the conclusion from these calculations is that the solutions of types 1, 2, and 3 have dimension smaller than 13. They may be entirely spurious. For types I and II no such conclusion can be drawn, the calculation simply shows that their dimension is at most 13. Fortunately we can bound the dimension of the solutions from below as well. As noted by Karlsson @Karlsson2 the Diţă construction @Dita (see Appendix A) allows us to construct a 13-dimensional family of $N = 12$ dephased Hadamard matrices once a 4-dimensional family of $N = 6$ dephased Hadamard matrices is known. Indeed, for any Hadamard matrices $H_1$ and $H_2$ and any diagonal unitary matrix $D$ of order $N$ the matrix $$H = \left( \begin{array}{cr} H_1 & DH_2 \\ H_1 & - DH_2 \end{array} \right) \label{Ditaigen}$$ is a Hadamard matrix of order $2N$. If $H_1$ and $H_2$ include the Fourier matrix of order $N$ this family includes a matrix which is permutation equivalent to the Fourier matrix of order $2N$. Given that the diagonal unitary $D$ contributes 5 free phases to the dephased matrix $H$, and that the existence of a 4 dimensional family for $N = 6$ ensures that $H_1$ and $H_2$ can contribute 4 phases each, this implies that there exists at least one 13-dimensional family for $N = 12$. The only candidates for such a family are the type I and II solutions. (Since they are related by transposition the existence of one implies the existence of the other.) Therefore it is only the slight uncertainty concerning $N = 6$ that prevents us from stating as a theorem that these 13-dimensional solutions must exist to all orders. This conclusion receives strong support from a different direction. For $N = 12$ it is known that there exist exactly 7 affine families of dimension 9 @TZ. Our perturbative solutions contain these families. The two 13-dimensional solutions of types I and II intersect in a 9-dimensional affine family called $F_{12A}$ @TZ, and each type contains one representative of each of three pairs of affine families related by transposition. For the self-cognate family $F_{12A}$ the parameters introduced by Tadej and Życzkowski @TZ are explicitly given by $$\begin{array}{ll} a = x_{1,2}(\omega^5 + \omega^9) + x_{1,4}(\omega^7 + \omega^9) + c.c. + 2\alpha_1 \\ b = x_{1,2}(\omega^7 + \omega^9) + x_{1,4}(\omega^9 + \omega^{11}) + c.c. \\ c = 2x_{1,2}\omega^9 + c.c. + 2\alpha_1 \\ d = x_{1,2}(\omega^9 + \omega^{11}) + x_{1,4}(\omega^7 + \omega^9) + c.c. \\ e = x_{1,2}(\omega + \omega^9) + x_{1,4}(\omega^9 + \omega^{11}) + c.c. + 2\alpha_1 \\ f = 2\alpha_2 \\ g = x_{1,2}(\omega^5 + \omega^9) + x_{1,4}(\omega^7 + \omega^9) + c.c. + 2\alpha_3 \\ h = 2\alpha_4 \\ i = x_{1,2}(\omega^5 + \omega^9) + x_{1,4}(\omega^7 + \omega^9) + c.c. + 2\alpha_5 & \ , \end{array}$$ where $\alpha_i = -ix_{i,6}$ is real and $c.c.$ denotes the complex conjugate of the preceding terms. We do not give the choices that reproduce the remaining affine families here. The picture that emerges is that of Fig. 2. Now we have computed the linear defect $d_1$ for a few randomly chosen members of each affine family. For the self-cognate family we find $d_1 = 17$. We observe that $13 + 13 - 9 = 17$, which means that the dimension of the linear span of the tangent vectors of the intersecting solutions of type I and II is equal to the linear defect $d_1=17$ of the self-cognate family in which they intersect. For the remaining affine families we find by sampling a large number of members that $d_1 = 13$ (except at the Fourier matrix itself), which is consistent with the fact that these families sit within a 13-dimensional family. It also provides some evidence that the solutions of types I and II exist also far away from the Fourier matrix. <span>**9. $N = p_1p_2^2$, and other choices of $N$**</span> Let us assume that $N = p_1p_2^2$, where $p_1$ and $p_2$ are prime numbers. We are then able to formulate a precise conjecture concerning how the type I and II solutions found for $N = 12$ generalise. Thus we suggest that when $N = p_1p_2^2$ there are always two types of solutions, giving rise to families of Hadamard matrices related to each other by transposition. The conjectured solutions are given by $$\mbox{Type I :} \hspace{9mm} x_{i,j} = x_{i+p_2,j} \hspace{5mm} \mbox{if} \hspace{5mm} \mbox{gcd}(j,N) = p_2^2 \ \label{Ia}$$ $$\mbox{Type II :} \hspace{8mm} x_{i,j} = x_{i+1,j} \hspace{5mm} \mbox{if} \hspace{5mm} \mbox{gcd}(j,N) = p_1 \ . \label{IIa}$$ The evidence for this conjecture is primarily that these conditions solve all consistency conditions up to fourth order not only for $N = 12$—where they are equivalent to eqs. (\[typI\]) and (\[typII\]), respectively—but for all such $N \leq 50$ (namely for $N = 3\cdot 2^2, 5\cdot 2^2, 7\cdot 2^2, 11\cdot 2^2, 2\cdot 3^2, 5\cdot 3^2$, and $2\cdot 5^2$). But we can add some additional evidence. First of all, although we have continued the calculation to higher orders only for the case $N = 12$, we note that the existence of a four parameter family for $N = 6$ implies the existence of 22-dimensional family for $N = 18$, via the Diţă construction. Compare eq. (\[Ditaigen\]). This is precisely the dimension implied by our conjecture in this case. Moreover the overall picture gained in the $N = 12$ case seems to repeat itself. In general, eqs. (\[Ia\]) or (\[IIa\]) impose $(p_1-1)p_2(p_2-1)$ conditions on the first order solution. If the conjecture is true it implies that the type I and II solutions have dimension $$d = d_1 - N\left( 1 - \frac{1}{p_1}\right) \left( 1 - \frac{1}{p_2}\right) \ ,$$ where $d_1$ is the linear defect of the Fourier matrix. Using the expression for $d_1$ that we quote in eq. (\[Slom\]), the dimension $d$ can alternatively be expressed as $$d = d_A + N\left( 1 - \frac{1}{p_1}\right) \left( 1 - \frac{1}{p_2}\right) \ , \label{dimension?}$$ where $d_A$ is the dimension of the largest affine family obtainable from the Diţă construction in these dimensions. See eq. (\[dA\]) in Appendix A for this. It follows that $$d = \frac{d_1+d_A}{2} \hspace{5mm} \Leftrightarrow \hspace{5mm} d_1 = 2d - d_A \ .$$ What this equation says is that the conjectured dimension $d$ is just right for the two solutions to intersect in a self-cognate affine family of dimension $d_A$, in such a way that the linear span of their tangent vectors equals the linear defect at their intersection. Using the Diţă construction we obtained one self-cognate family and three pairs of affine families related by transposition, all of dimension $d_A$, for all $N = p_1p_2^2$. The details are in Appendix A. For $N = 12$ it is known that these are all affine families of maximal dimension stemming from the Fourier matrix @TZ. For our seven examples with $N = p_1p_2^2 \leq 50$ we checked that the self-cognate family sits in the intersection of the two solutions of type I and II, while the other affine families are contained in a single such solution. We also computed the defect along all these affine families for some randomly chosen matrices, and found that their linear defect equals $2d - d_A$ for the self-cognate family, and it equals $d$ for the other families (except at the Fourier matrix itself). This clearly supports the conjecture that the solutions of type I and II survive to higher orders. Finally, a word about the equations that we actually encounter. As in the case of $N =
{'source': 'arXiv_out/1202'}