Construction, classification and parametrization of complex Hadamard matrices

Introduction

$\overline{\text{\hskip 86.0pt Leonardo da Vinci}}$

This thesis is based on our recent research contributions to the theory of complex Hadamard matrices , , , , . Some earlier results are also touched upon such as , , , as well as several new results which will be the subject of forthcoming publications.

Complex Hadamard matrices form an important family of orthogonal arrays with the additional unimodularity constraint imposed on their entries. These matrices obey the algebraic identity $HH^{\ast}=nI_{n}$ where $\ast$ stands for the Hermitian transpose, and $I_{n}$ is the identity matrix of order $n$. It is easy to see that after proper scaling the Fourier matrices are well-known examples of complex Hadamard matrices.

Complex Hadamard matrices appear frequently in various branches of mathematics, including linear algebra , coding and operator theory , and harmonic analysis , . They play an important rôle in quantum optics, high-energy physics, and they are one of the key ingredients to quantum teleportation and dense coding schemes and mutually unbiased bases (MUBs) .

The intended purpose of this work is to provide the reader with a comprehensive, state-of-the art presentation of the theory of complex Hadamard matrices, or at least report on the very recent advances. This manuscript consists of three chapters, each describing one of three distinct faces of this field whose treatment require various mathematical tools ranging from combinatorics, functional analysis to symbolic computation. Although we firmly believe that these beautiful objects are interesting on their own and worth investigating from a purely mathematical perspective we make considerable efforts to highlight some of their applications we aware of. Industrial applications can be found in the textbooks and which are warmly recommended to the interested reader.

This thesis has three main ingredients: known results from the existing literature; our contribution to the literature; and new results which are subject to a series of forthcoming publications. Each of these constitute about one third of this manuscript. We are certain that this dissertation is just the starting point of a long-term journey and in order to keep us (and hopefully others) entertained along the way we pose over $30$ research problems worth investigating in the future.

In the subsequent sections we outline, chapter by chapter, the contents of this thesis highlighting our main contributions.

In Chapter 1 we lay down the foundations of this work by recalling the relevant notions and results from the existing literature. Original interest was in real Hadamard matrices whose existence is still a mystery. The Hadamard conjecture states that for every positive integer $m$ there is a real Hadamard matrix of order $4m$. This century-old problem is currently far out of reach, despite continuous efforts. It is natural to investigate the problem in more generality and study complex Hadamard matrices of order $n$ which are formed by some $q$th roots of unity. These matrices are called Butson-Hadamard matrices and are denoted by $BH(n,q)$. Researchers are interested in these more general objects because they can lead to real Hadamard matrices and hopefully one day to the solution of the Hadamard Conjecture.

One of the fundamental differences between real and complex Hadamard matrices is that while studying and classifying real Hadamard matrices is a discrete problem which can be handled by deep algebraic methods and sophisticated computer programs, in the complex case various infinite, parametric families appear (i.e. matrices with certain degree of freedom). Therefore the complex case is not finite any longer and one cannot hope for a finite list of complex Hadamard matrices.

We investigate the parametrization properties of $BH(n,q)$ matrices focusing on the cases $q=4$ and $6$. We give a comprehensive classification of $BH(n,4)$ matrices up to order $n=8$ and highlight some key facts regarding orders $n=10$ and $12$ from a joint work with Pekka Lampio and Patric Östergård . In particular, we mention the following two results.

For $4\leq n\leq 12$ all $BH(n,4)$ matrices belong to some infinite, affine parametric family of complex Hadamard matrices.

On the other hand, there are $14\times 14$ matrices which cannot be parametrized at all. This is a fundamental difference from the real case.

There exist isolated $BH(14,4)$ matrices.

The new result regarding $BH(n,6)$ matrices were obtained during a visit to Robert Craigen. We have obtained the following

For every prime $p$ there exists a $BH(p^{2},6)$ matrix.

To distinguish essentially different complex Hadamard matrices from each other we have introduced a powerful new invariant, the fingerprint .

As an application of Butson-Hadamard matrices we give a further look at Fuglede’s conjecture and obtain new, previously unknown counterexamples.

Towards the classification of 6×6666\times 6 Hadamard matrices

It is natural to ask what a “typical” complex Hadamard matrix of order $n$ looks like, and a satisfying answer to this question can be given provided we have at our disposal a complete characterization of Hadamard matrices of order $n$. These types of problems, however, are notoriously difficult even for small $n$.

There is a complete classification of real Hadamard matrices up to order $n=28$, and recent advances indicate that there is every reason to believe that at least an enumeration of the millions of matrices of order $32$ and $36$ is possible as well . In contrast, a complete classification of complex Hadamard matrices is only available up to order $n=5$. It is easy to see that the (rescaled) Fourier matrices are the unique examples in orders $n\leq 3$. The case $n=4$ is still elementary, and it was shown by Craigen that all complex Hadamard matrices of order $4$ belong to an infinite, continuous one-parameter family . In order $5$ we have uniqueness again, a result which already is absolutely non-trivial. In particular, Lovász was the first who showed that the Fourier matrix is the only circulant complex Hadamard matrix of order $5$, and a decade later Haagerup managed to prove the uniqueness of the Fourier matrix by discovering an algebraic identity (see formula (2.16)) relating the matrix entries in a surprising way .

In order $6$ various one , , and ; two , ; and three-parameter families have been constructed recently and it was conjectured that these are part of a more general, four-parameter family of complex Hadamard matrices . This conjecture is supported by overwhelming numerical evidence , however so far only a fairly small subset of it was described by closed analytic formulae, including an isolated matrix $S_{6}^{(0)}$ and a three-parameter family of matrices $K_{6}^{(3)}$. One of the main reasons why the complex case is so difficult is the presence of infinite parametric families and the lack of understanding of vanishing sums of order $k$ for $k\geq 5$. In Chapter 2 we make substantial progress towards the classification of $6\times 6$ complex Hadamard matrices by giving a construction with four degrees of freedom. We believe that our construction captures the typical features of complex Hadamard matrices of order $6$. The main result is essentially the following

There is a four-parameter family of $6\times 6$ complex Hadamard matrices.

During Chapter 2 we propose a general framework towards the complete classification of complex Hadamard matrices of order $6$. In particular, by characterizing the orthogonal triplets of rows in complex Hadamard matrices we generalize an observation of Haagerup to obtain a new algebraic identity relating the matrix entries in an unexpected way. This is an essentially new tool to study complex Hadamard matrices of small orders, and one of the main achievements of this chapter. We apply this result to obtain complex Hadamard matrices, moreover we conjecture that the construction we present here reflects the true nature of complex Hadamard matrices of order $6$. It has the following three features: Firstly, it is general in contrast with the earlier attempts where always some additional extra structure was imposed on the matrices including self-adjointness , symmetry , circulant block structure or $H_{2}$-reducibility . Secondly, it has $4$ degrees of freedom and thirdly all the entries of the obtained matrices can be described by algebraic functions of roots of various sextic polynomials. This suggests on the one hand the existence of a four-parameter family of complex Hadamard matrices of order $6$ and reminds us on the other hand of the fact that the desired algebraical description where the entries are expressed by closed analytic formulae might not be possible at all. However, from the applicational point of view, and in particular, to utilize the computer-aided attack of to the MUB-$6$ problem we anyway only need these matrices numerically.

Finally, to illustrate the applications of MUBs we exhibit equiangular lines in real spaces. Our results slightly improve on a recent construction of de Caen .

As a consequence we obtain a new general quadratic lower bound on the number of real equiangular lines (see Corollary 2.4.40).

Complex Hadamard matrices of prime orders

The final chapter is devoted to the discussion of complex Hadamard matrices of prime orders. Constructing complex Hadamard matrices of prime orders requires considerable efforts. One of the reasons for this is that design theory fundamentally relies on “plug-in” methods and block constructions resulting in objects of composite orders. Furthermore it is known that the Fourier matrices of prime orders are isolated thus we do not have natural examples of parametric families of complex Hadamard matrices in the prime order case. Throughout Chapter 3 we recall Petrescu’s construction and obtain new interesting examples of $BH(n,q)$ matrices. On the one hand we settle the existence of $BH(19,6)$ matrices which is listed as unresolved in , on the other hand we obtain some non-existence results.

We list several new examples of $BH(n,q)$ matrices in Appendix A. Among these there is a $BH(13,30)$ matrix leading to a four-parameter family of complex Hadamard matrices of order $13$.

In the subsequent sections we investigate circulant complex Hadamard matrices. Following the influential paper we construct new examples of index $4$ type circulant complex Hadamard matrices of prime orders. In particular, we prove the following

Finally we investigate the problem of finding all complex Hadamard matrices with circulant core and solve it for $n\leq 7$ yielding a new, previously unknown complex Hadamard matrix of order $7$. To deal with this problem we utilize the full machinery of the theory of Gröbner bases and we use it to investigate some special classes of higher order matrices as well. This computer experiment turned out to be fruitful as we have discovered two infinite classes of complex Hadamard matrices as follows:

We conclude the thesis by investigating complex Hadamard matrices with few different entries, and we utilize them to construct new examples of equiangular tight frames .

Acknowledgements

I am greatly indebted to Professor Máté Matolcsi for his continuous guidance and support since my freshman year. I am grateful for his permanent influence on my mathematical outlook and for his patience and wisdom allowing me to explore the mathematics I am fascinated with. I feel fortunate that during these years I had the opportunity of learning from him and doing research with him.

My warmest thanks go to Pofessor Robert Craigen who supervised my work during my visit as a guest student at the University of Manitoba. The training he provided me with substantially improved my knowledge on the subject of this thesis.

I acknowledge financial support by Central European University grant no. DRSG-$131/2010$-$11$; Hungarian Scientific Research Fund (OTKA) grant no. K-$77748$; and National Sciences and Engineering Research Council of Canada (NSERC) grant no. $155855$-$09$.

Chapter 1 Complex Hadamard matrices of composite orders

The purpose of this introductory chapter is to describe the basic terminology and the fundamental properties of complex Hadamard matrices. We shall give various examples of infinite, parametric families as well as examples of isolated complex Hadamard matrices in the sequel. Hadamard matrices, composed from roots of unity shall be investigated in details. Our intentions were to include relevant structural results from the existing very recent literature giving this chapter a survey flavour. The reader interested in classical results concerning real and generalized Hadamard matrices should consult Agaian’s or Horadam’s book , or read the PhD thesis of Seberry or Craigen . Our contribution to this chapter is based on the papers , , and the preprint . Additionally, we briefly mention the important achievements from and . The new results in Sections 1.4.2 and 1.4.3 are subject to a possible forthcoming publication.

We begin our journey with investigating the existence of complex Hadamard matrices.

Our dissertation is entirely devoted to investigate the existence and the structure of the following concept.

A complex Hadamard matrix $H$ is an $n\times n$ matrix with complex entries of modulus $1$ such that $HH^{\ast}=nI$.

Therefore a complex Hadamard matrix is essentially a unitary matrix with unimodular entries. Of course, we obtain a unitary matrix after proper normalization. As we shall see, it is easy to exhibit a complex Hadamard matrix in every order $n$ but first let us fix some notations once and for all.

Throughout this thesis we denote by $\Re[z]$ and $\Im[z]$ the real and imaginary part of a complex number $z$, respectively. We denote by $\mathbf{i}$ the principal fourth root of unity, that is $\mathbf{i}^{2}=-1$ with the convention that $\Im[\mathbf{i}]=1$. Finally, let us denote by $\omega$ the principal cubic root of unity, namely

With these notations at our hand, we can offer our very first

For every $n\geq 1$ there exists a complex Hadamard matrix of order $n$.

is a well-known example of complex Hadamard matrices. ∎

Note that throughout this manuscript the term “Fourier matrix” is used to describe the complex Hadamard matrix $F_{n}$ under (1.1), and not the unitary matrix $\frac{1}{\sqrt{n}}F_{n}$. We offer the following

The following are complex Hadamard matrices of orders $n=1,2$ and $3$, respectively:

One immediately observes that the matrices displayed in the preceding example all have a bordering row and column of numbers $1$. This is a general feature of complex Hadamard matrices, up to the following equivalence.

The complex Hadamard matrices $H$ and $K$ are called (permutation–phasing) equivalent, if there are permutation matrices $P_{1}$ and $P_{2}$ and unitary diagonal matrices $D_{1}$ and $D_{2}$ such that $P_{1}D_{1}HD_{2}P_{2}=K$. This relation is denoted by $H\sim K$. If two Hadamard matrices are not equivalent then we say that they are inequivalent.

Definition 1.1.5 exploits the fact that the rearrangement of the rows and columns or the shift of the phase in any row or column of a complex Hadamard matrix maintains its fundamental properties: both the unitary and unimodular conditions still hold after these transformations. We recall the following

A complex Hadamard matrix $H$ of order $n$ is dephased if the first row and column of it consists of entirely of numbers $1$. The lower right $(n-1)\times(n-1)$ submatrix is called the core of $H$.

A dephased real Hadamard matrix is usually called normalized. It is immediate, that the following is true.

Every complex Hadamard matrix is equivalent to a dephased one.

Henceforth it is enough to consider dephased complex Hadamard matrices. There are other “trivial” ways to obtain new complex Hadamard matrices from what is already at our hands. In particular, we have the following

If $H$ is a complex Hadamard matrix, then so is $H^{\ast},\overline{H}$ and $H^{T}$.

Let $H$ be a complex Hadamard matrix. Then conjugate the identity $HH^{\ast}=nI$ in order to see that $\overline{H}$ is a complex Hadamard matrix as well. It is also clear that $H$ is invertible and $H^{-1}=H^{\ast}/n$. Hence, it follows that $H^{\ast}H=nI$, which shows that both $H^{\ast}$ and, after conjugating again, $H^{T}$ are complex Hadamard matrices. ∎

Another natural approach to construct new matrices from old is to lift given objects to higher orders via the Kronecker product. We use the following concept repeatedly in our manuscript.

Let $H$ be an $n\times n$, $K$ be an $m\times m$ matrix. Then their Kronecker product $H\otimes K$ is an $nm\times nm$ matrix with its $(i,j)$th block being given by $[H]_{i,j}K$, $i,j=1,\ldots,n$.

If $H$ and $K$ are complex Hadamard matrices then so is $H\otimes K$.

Clearly $H\otimes K$ is unimodular, moreover

which can be identified with $nmI_{nm}$. ∎

In $1867$ Sylvester constructed real Hadamard matrices of orders $n=2^{k}$ for every $k\geq 1$ via Lemma 1.1.10, starting from the Fourier matrix $F_{2}$ . For comparison, we give an additional

It is not immediately clear that the matrices $H_{4}$ and $F_{4}$ are inequivalent. Later we shall see several invariants easily detecting inequivalence in this, and various other cases. Here we offer the general treatment of the Kronecker product of Fourier matrices.

Let $F=F_{n_{1}}\otimes F_{n_{2}}\otimes\cdots\otimes F_{n_{r}}$ be a Kronecker product of Fourier matrices. Then $F$ is equivalent to $F_{m_{1}}\otimes F_{m_{2}}\otimes\cdots\otimes F_{m_{s}}$ if and only if the sequence $(m_{1},m_{2},\ldots,m_{s})$ is obtained from the sequence $(n_{1},n_{2},\ldots,n_{r})$ using a series of operations from the list below:

replacing a subsequence $n_{a},n_{b}$ by $n_{c}=n_{a}n_{b}$ if $n_{a}$ and $n_{b}$ are relatively prime;

replacing a sequence element $n_{c}$ by a subsequence $n_{a},n_{b}$, if $n_{c}=n_{a}n_{b}$ and $n_{a},n_{b}$ are relatively prime.

It follows from Theorem 1.1.12 that the matrices displayed in Example 1.1.11 are inequivalent. Therefore we already have a handful of examples of complex Hadamard matrices coming from purely the Fourier matrices at our disposal. Another source of examples are the real Hadamard matrices. It is natural to ask the following

Decide for which orders $n$ exists a real Hadamard matrix.

It is immediate from Lemma 1.1.7 that the order of such a matrix must be $1$ or even. However, a little more careful analysis reveals the following

It is widely believed that this is the only obstruction. In particular, we have the following long-standing

The truth of Conjecture 1.1.15 has been verified for orders $n\leq 664$; order $n=428$ has been constructed only very recently in . There are $13$ open cases below $n=2000$ for which the existence is undecided , all of them are of the form $n=4p$ where $p\equiv 3$ (mod $4$) is prime.

From Lemma 1.1.14 it follows that there is no real Hadamard matrix of orders $5,6$ or $7$. For order $8$ we have a unique (up to equivalence) example given by $F_{2}\otimes F_{2}\otimes F_{2}$, while constructing a matrix of order $12$ requires some additional terminology (see also the intriguing Example 1.4.40).

The Paley construction can be generalized to prime power orders as well using finite fields. In particular, for every prime $p$ and $k\geq 1$ there are real Hadamard matrices of order $n=p^{k}+1$ or $n=2(p^{k}+1)$, depending on whether we have $p^{k}\equiv 3$ (mod $4$) or $p^{k}\equiv 1$ (mod $4$), respectively. It is worthwhile noting that Theorem 1.1.17 leads to real Hadamard matrices with circulant core. We will return to these objects later in Appendix C.

A Hadamard matrix of order $20$ was constructed by Hadamard in $1893$ , and it took a century to have a complete classification of real Hadamard matrices of order at most $28$ , while the enumeration of Hadamard matrices of order $32$ begun just very recently, yielding over $13$ million inequivalent matrices .

Let us try to understand how good we are doing in terms of Conjecture 1.1.15. In order to measure this, let us denote by $S(x)$ the number of $n\leq x$ for which a Hadamard matrix of order $n$ exists. Now the Hadamard conjecture states that $S(x)$ is about $x/4$, and hence the set of Hadamard orders has density $1/4$. As yet, it is not even known if this set has positive density, as taking into account all major known construction methods, one obtains only the following

For all $\varepsilon>0$ there is a natural number $x_{\varepsilon}$ such that for all $x>x_{\varepsilon}$

However, from another point of view we are doing quite well, as Seberry proved that for every odd $m$ and for every large enough $t=t(m)$, there is a real Hadamard matrix of order $n=2^{t}m$ . This was subsequently improved by Craigen ; currently the best known asymptotic result of this flavour is the following

A Hadamard matrix of order $2^{t}m$ for odd $m$ exists for all

In particular, for every odd $m$ there are only finitely many numbers $t$ such that the existence of a real Hadamard matrix of order $2^{t}m$ is undecided.

A different approach is to try to guarantee a large number of pairwise orthogonal rows of $\{\pm 1\}$ entries in a given order $n$. Let us denote by $r(n)$ the largest number $r$ such that there are $r$ pairwise orthogonal $\{\pm 1\}$ rows of length $n$. Then the following is true.

Thus, for $n$ large enough we have about one half of a real Hadamard matrix of order $n$. It seems, however, that despite continuous efforts from researchers from a broad area, proving the truth of the Hadamard conjecture remains elusive, and fundamental new ideas are required for further progress.

2 Parametrizing complex Hadamard matrices

In this section we introduce the concept of parametrization, a powerful method obtaining new complex Hadamard matrices from old. The parametrization can be thought as a continuous analogue of the switching operation , a well-known technique in design-theory. These ideas were used by Craigen , Diţă , Haagerup and Nicoară (among others), who exhibited various parametric families in the last decade. It should be noted that Hadamard himself, who investigated $4\times 4$ matrices with maximum determinant, exhibited essentially the following

For every unimodular number $a$ the matrix

is complex Hadamard, forming a one-parameter family of complex Hadamard matrices, stemming from the starting point matrix $F_{4}=F_{4}^{(1)}(1)$.

The preceding example describes a family of complex Hadamard matrices as it incorporates various inequivalent matrices through the indeterminate $a$. In particular, for $a=1$ we have the Fourier matrix $F_{4}=F_{4}^{(1)}(1)$, while for $a=\mathbf{i}$ we get the real Hadamard matrix $H_{4}=F_{2}\otimes F_{2}$, which are inequivalent. We can look at this phenomenon from a different point of view. One might start with the single matrix $F_{4}$, and then try to find a way to introduce some degree of freedom into it, say, by introducing the parameter $a$ as in Example 1.2.1 in order to exhibit new, previously unknown matrices, which are inequivalent from the starting point one. This approach, as we shall see in Section 1.4.3 where we discuss spectral sets and tiles in abelian groups, can lead to some very exciting discoveries.

Consider the Fourier matrix $F_{3}$ and multiply its second row by a unimodular number $a$, and multiply its third column by a unimodular number $b$ to obtain the following

We immediately see that for any unimodular choice of $a$ and $b$ the following equivalence holds

Therefore the seemingly two degrees of freedom does not give us even a single new matrix, being inequivalent from the starting-point matrix $F_{3}$.

Now let us see how to obtain interesting affine families in composite orders. We have the following fundamental

Let $M$ be a $k\times k$ and $N_{1},N_{2},\ldots,N_{k}$ be $v\times v$ dephased complex Hadamard matrices with $m$ and $n_{1},n_{2},\ldots,n_{k}$ free parameters, respectively. Then the block matrix $M\otimes(N_{1},N_{2},\ldots,N_{k})$ with its $(i,j)$th block given by $[M]_{i,j}N_{j}$ is a complex Hadamard matrix of order $vk$ with $m+\sum_{i=1}^{k}n_{i}+(k-1)(v-1)$ free parameters.

We say that a complex Hadamard matrix is of Diţă-type, if it is equivalent to a matrix arising with Corollary 1.2.5.

Diţă-type complex Hadamard matrices can be recognized algorithmically . See also for some other useful concepts. $\square$

Not every parametric family is affine, and the treatment of non-affine families is somewhat more technical. Fortunately, as long as they are given explicitly we can detect easily how many degrees of freedom they have.

It is clear that affine families are a special case of this more general concept. The reader might wish to jump ahead to Section 2.2.2 to see an example of a non-affine family.

If we are given a complex Hadamard matrix $H$ we would like to know whether any smooth family is stemming from it. This is hard to decide in general, but we can give an upper bound on the dimension of any such potential family simply by differentiating the orthogonality relations between the rows. This leads to the following concept:

Let us note here that the defect is well-defined in the following sense.

The defect of the Fourier matrices is known explicitly, and is given by the following

Let $n=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots p_{r}^{\alpha_{r}}\geq 2$ be a natural number with the factorization into distinct prime numbers $p_{i},i=1,\ldots,r$. Then

While Theorem 1.2.4 provides access to parametric families of complex Hadamard matrices, it does not reveal how to introduce parameters into a given matrix. This question was investigated for the Fourier matrices in , where an explicit construction was given to introduce $p^{k-1}\left(k(p-1)-p\right)+1$ affine parameters into $F_{p^{k}}$ thus demonstrating that the absolute upper bound in (1.3) is sharp.

In what follows we describe various parametrization schemes.

There is a fairly general method, called “linear variation of phases” allowing one to find affine parametric families stemming from complex Hadamard matrices with certain additional symmetries; however the method becomes computationally expensive for higher order matrices, or for those lacking the required symmetries. Nevertheless the maximal affine families, stemming from the Fourier matrices has been obtained this way , and the method can also be used to introduce additional degree of freedom into existing parametric families .

We investigated real Hadamard matrices in , where the following simple way to introduce free parameters into complex Hadamard matrices of even orders $n\geq 4$ was mentioned.

Let $H$ be a dephased complex Hadamard matrix of even order $n\geq 4$ and suppose that there exists a pair of rows in $H$, say $u$ and $v$, such that for every $i=1,2,\ldots,n$ $u_{i}^{2}=v_{i}^{2}$. Then for all such $i$ for which $u_{i}+v_{i}=0$ replace $u_{i}$ with $\alpha u_{i}$ and $v_{i}$ with $\alpha v_{i}$ where $\alpha$ is a unimodular complex number to obtain a one-parameter family of complex Hadamard matrices $H(\alpha)$.

Indeed, $H(\alpha)$ is unimodular and it is easy to see that the assumptions guarantee that the columns of it are pairwise orthogonal. Note that one might need to dephase the matrix in order to obtain an affine family, but this operation does not remove the parameters from it as $n\geq 4$. ∎

Let $H$ be a dephased complex Hadamard matrix with the following block structure

where $a$ and $b$ are arbitrary unimodular numbers. Then, after replacing the vectors $y$ with $\alpha y$ and $w$ with $\overline{\alpha}w$ we obtain a one-parameter family of complex Hadamard matrices $H(\alpha)$. If, in addition, $b=a$ then we can replace $w$ one more time with $\alpha\beta w$ to obtain a two-parameter family of complex Hadamard matrices $H(\alpha,\beta)$.

We need to show that the rows of $H(\alpha,\beta)$ are pairwise orthogonal. It is immediate that

and hence the first three rows of $H(\alpha,\beta)$ are pairwise orthogonal. Similarly, it is easily seen that the rest of the rows (beyond the first three) are pairwise orthogonal within themselves. Additionally, the first row is trivially orthogonal to all further rows, as $w_{i}$ cancels out from the orthogonality equations for $i=1,\ldots,s$. Therefore it remains to be seen that the second and third rows of $H(\alpha,\beta)$ are orthogonal to all additional one. We show first that they are orthogonal to rows which are type $[1,z_{i},z_{i},A_{i},B_{i}]$, $i=1,\ldots,r$. In the original matrix $H$ (i.e. prior to parametrizing) we have

and hence $\left\langle B_{i},y\right\rangle=0$ for every $i=1,\ldots,r$. It follows that after parametrization equations (1.4)-(1.5) remain valid. We proceed by proving that rows which are type $[1,w_{i},-w_{i},C_{i},D_{i}]$, $i=1,\ldots,s$, after parametrization, are orthogonal to the second and third row of $H(\alpha,\beta)$. Again, in the original matrix $H$ we have

and hence $\left\langle C_{i},x\right\rangle=-1$ for every $i=1,\ldots,s$. It follows, that (1.6)-(1.7) are valid, provided that

and therefore (1.6)-(1.7) remains true, after parametrization. If, in addition, $b=a$, then $\left\langle D_{i},y\right\rangle=0$ for every $i=1,\ldots,s$ and hence (1.8) holds, independently of the scalar factor in $w$. ∎

If $a$ and $b$ are as in Theorem 1.2.16, then it is easy to see that the expression $2\Re[a\overline{b}]$ is an integral number and therefore $b\in\pm a\cdot\{1,\omega,\omega^{2},\mathbf{i}\}$. It follows that the parametrizing scheme described is “natural” for complex Hadamard matrices with fourth and sixth roots of unity. $\square$

Theorem 1.2.16 describes a local property of the complex Hadamard matrix $H$. Its conditions can be fairly easily checked, even by hand, and the method can be implemented as a computer program to construct infinite families automatically. This has been done in , where complex Hadamard matrices, composed of fourth roots of unity were investigated. $\square$

is a one-parameter family of complex Hadamard matrices.

Now we discuss some of the consequences of these results. From Lemma 1.2.15 it follows that every real Hadamard matrix of order $n\geq 4$ admits an $n/2-1$-parameter affine orbit. Actually, we have shown a little more in :

Every real Hadamard matrix of order $n\geq 12$ admits an $n/2+1$-parameter affine orbit.

However, if there are real Hadamard matrices of orders $n_{1}$ and $n_{2}$, then one can do way better in orders $n_{1}n_{2}$ via Diţă’s construction, improving the coefficient from $1/2$ to $1$ as follows:

Let $H$ and $K$ be real Hadamard matrices of order $n_{1}$ and $n_{2}$. Then there is a family of complex Hadamard matrices of order $n_{1}n_{2}$, with $(n_{1}-1)(n_{2}-1)$ affine parameters, stemming from a real Diţă-type Hadamard matrix.

In light of this, it is natural to pose the following

The parametrization highlighted in Proposition 1.2.23 (essentially) introduces parameters into distinct pairs of rows of a real Hadamard matrix via Lemma 1.2.15. If one could introduce parameters into the rows and columns of the matrix simultaneously, then one might reach the desired improvement and obtain similar results as described in Corollary 1.2.24. $\square$

Finally, it is natural to ask if real Hadamard matrices can be obtained from parametric families of complex Hadamard matrices. For example, one might wonder if a real Hadamard matrix of order $668$ can be obtained from the Fourier matrix $F_{668}$, which is parametrized via Diţă’s construction. Unfortunately, real Hadamard matrices of order $4p$ are not of Diţă-type and therefore they cannot be obtained this way . It is, however, unclear whether some clever parametrization scheme would yield such a matrix. We explicitly ask the following “baby case” of this

Investigate if the Fourier matrix $F_{12}$ can be parametrized in a way such that its orbit contains the real Hadamard matrix $H_{12}$.

A positive, constructive resolution of Problem 1.2.27 might lead to the construction of new, previously intractable real Hadamard matrices of higher orders.

It would be nice to connect Theorem 1.2.16 to Theorems 1.2.19 and 1.2.21 and check if it is meaningful in the more general operator algebraic context. We have the following

Investigate if Lemma 1.2.15 and Theorem 1.2.16 can be reformulated in an operator algebraic fashion similarly to Theorems 1.2.19 and 1.2.21.

There are complex Hadamard matrices which cannot be parametrized at all. The relevant concept is what follows.

A complex Hadamard matrix $H$ of order $n$ is isolated, if around a small neighborhood of $H$ all complex Hadamard matrices $K$ are equivalent to it.

One might wonder why we allow other (yet equivalent) Hadamard matrices to exist around a neighborhood of $H$. The reason is quite simple: every complex Hadamard matrix can be transformed continuously to some other via multiplication by unitary diagonal matrices, which however is uninteresting as it never leads to new, inequivalent matrices (see Example 1.2.2). It turns out, that the defect provides a useful criterion detecting isolated matrices. In particular, from Proposition 1.2.12 it follows that no smooth families can be obtained from a matrix whose defect is zero. This, however does not say anything about the existence of non-smooth families (e.g. a sequence of inequivalent matrices converging to $H$). The following stronger result excludes this possibility.

Suppose that the defect of a complex Hadamard matrix $H$ of order $n$ is zero. Then $H$ is isolated amongst all $n\times n$ complex Hadamard matrices.

If $H$ is a complex Hadamard matrix of order $n$ such that the dimension of the vector space $[\mathcal{D}_{n},H^{\ast}\mathcal{D}_{n}H]$ is $n^{2}-2n+1$ then $H$ is isolated among all complex Hadamard matrices of order $n$ $($up to equivalence$)$.

It is easy to see that the matrices $F_{1}$ and $F_{2}$ satisfy the span condition (or equivalently, their defect is ), thus from Proposition 1.2.23 it follows immediately that

A real Hadamard matrix is isolated if and only if it is equivalent to $F_{1}$ or $F_{2}$.

For results pertaining the defect of unitary matrices see e.g. , , .

3 Equivalence of complex Hadamard matrices

The existence of parametric families of complex Hadamard matrices in a given order $n$ implies the existence of infinitely many inequivalent matrices . This can be readily seen through the following invariant, introduced by Haagerup :

The Haagerup-set of a complex Hadamard matrix $H$ of order $n$ is the set

The Haagerup-set is invariant under the usual equivalence.

Informally speaking, if two Hadamard matrices $H$ and $K$ have “essentially different” set of entries, they cannot be equivalent. In particular, it follows from the Haagerup invariant that for any complex Hadamard matrix $H$ there is only a finite number of dephased complex Hadamard matrices $K$ being equivalent to it. Indeed, any entry of $K$ must be an element of $\Lambda(H)$. $\square$

We illustrate an application of this this invariant in the following

The matrices $F_{2}\otimes F_{2}$ and $F_{4}$ are inequivalent $($cf. Example 1.1.11$)$.

Indeed, as $\Lambda(F_{2}\otimes F_{2})=\{\pm 1\}$, and in particular, it does not contain the fourth root of unity $\mathbf{i}$, whereas $\Lambda(F_{4})=\{\pm 1,\pm\mathbf{i}\}$. ∎

However, it is known that there are $5$ inequivalent real Hadamard matrices of order $16$ , all of which sharing the same Haagerup set, therefore they cannot be distinguished by this concept. There are a number of invariants introduced to detect the inequivalence of real Hadamard matrices, including the $4$-profile or the Smith Normal Form , however they cannot be translated directly to the complex case due to fundamental or practical reasons. We have introduced a new invariant in to improve on this situation.

The fingerprint of a complex Hadamard matrix $H$ of order $n$ is the following ordered set

where for every $2\leq d\leq\left\lfloor n/2\right\rfloor$ $I(d)$ is an index set, and $v_{i}(d)$ and $m_{i}(d)$ are the possible values of the moduli of the $d\times d$ minors and its multiplicities, respectively.

The fingerprint of the $8\times 8$ real Hadamard matrix $H:=F_{2}\otimes F_{2}\otimes F_{2}$ reads

meaning that there are $336$ $2\times 2$ minors of value and $448$ minors of absolute value $2$ in $H$, etc.

We remark here that the distribution of the absolute values of the minors of size greater than $\left\lfloor n/2\right\rfloor$ are not considered in the fingerprint because in unitary matrices any minor and its cofactor share the same absolute value . This harmless observation lead to a surprising disproval of a natural conjecture of Koukovinos et al. on the distribution of minors of real Hadamard matrices .

Compared to the Haagerup-set which considers $2\times 2$ submatrices only, the fingerprint aims to capture some of the global properties of a complex Hadamard matrix. One of the limitations of the fingerprint is its computational complexity, however in practice one is free to use some subset of $\Phi$, say the distribution of minors up to order $3$ or just the number of $4\times 4$ vanishing minors, etc., providing limited but hopefully enough information already. Another weak point of the concept is that it cannot distinguish a matrix from its transpose, conjugate or adjoint. Separating a matrix from its transpose, however, tends to be more important in the real case where the underlying design is studied. We point out a natural way to distinguish a complex Hadamard matrix from its transpose in the following

The rectangular rank profile of a complex Hadamard matrix $H$ is the following ordered set

where for every $2\leq j,k\leq n-2$ $I(j,k)$ is an index set, and $r_{i}(j,k)$ and $m_{i}(j,k)$ are the possible values of the rank of the $j\times k$ submatrices of the matrix $H$ and their multiplicities, respectively.

The rectangular rank profile is invariant, up to equivalence.

The rank of a rectangular matrix can be calculated by considering the size of its largest nonsingular minor, which however is preserved during the equivalence operations. ∎

The rectangular rank profile of the matrices $F_{2}\otimes F_{2}$ and $F_{4}$ (see Example 1.1.11) read:

respectively, meaning that in the matrix $F_{2}\otimes F_{2}$ the number of $2\times 2$ submatrices with rank $1$ and $2$ are $12$ and $24$, respectively, while in $F_{4}$ the number of $2\times 2$ submatrices with rank $1$ is $4$ only.

We tend to believe that in a “typical” complex Hadamard matrix there are no vanishing minors at all, and as a result their rectangular rank profile is trivial. Nevertheless, when we consider highly structured matrices, such as real Hadamard matrices, it can be a valuable asset at our disposal. We shall see further applications of these invariants in the subsequent sections.

4 Butson-type complex Hadamard matrices

This section is dedicated to investigate the existence and structure of the following concept.

We say that a complex Hadamard matrix $H$ of order $n$ is of Butson-type, if $H$ is composed from some $q$th roots of unity. We denote this class of matrices by $BH(n,q)$.

We advise the reader that the notation varies from author to author, some of them permuting the argument to $BH(q,n)$, or dropping the letter $B$ resulting in the notations $H(n,q)$ and $H(q,n)$, respectively.

We primarily focus on $BH(n,4)$ and $BH(n,6)$ matrices in this section, as the cases $q=4$ and $q=6$ are the two simplest generalization of the real Hadamard matrices, i.e. when $q=2$, namely they correspond to the prime-power and composite case, respectively. Clearly, Lemma 1.1.7 applies to $BH(n,q)$ matrices as well, resulting in the following concept.

We say that a $k$-term sum $x_{1}+x_{2}+\ldots+x_{k}$ is a vanishing sum of order $k$ if its value is .

Now in order to find a pair of orthogonal rows of a $BH(n,q)$ matrix one needs to exhibit a vanishing sum of order $n$, composed from $q$th root of unity. It is natural to ask when this is possible. The following resolution of this problem is a necessary condition on the existence of $BH(n,q)$ matrices

For a more general treatment of this question see .

Theorem 1.4.3 above, however, does not say anything about the existence of orthogonal triplets of rows in complex Hadamard matrices. For example, for numbers $n\equiv 2$ (mod $4$) one easily constructs a vanishing sum of order $n$ composed from the numbers $\pm 1$, however, it follows from (the ideas behind) Lemma 1.1.14 that it is impossible to exhibit orthogonal triplets of real rows in this case.

Let us denote by $\left(\frac{p}{q}\right)$ the Legendre symbol. We collect some well-known necessary conditions and the subsequent nonexistence results in the following

For a $BH(n,q)$ matrix the following hold.

If $p$ is prime and there is a $BH(n,p^{a})$, then $n=pt$ for some positive integer $t$.

If $p$ is prime, there exists a $BH(2^{j}p^{k},p)$ for all $0\leq j\leq k$.

Butson’s basic construction yields a $BH(2p,p)$ matrix for prime $p$; it is known that there are $BH(12,3)$ and $BH(28,7)$ matrices . It is natural to ask the following

Decide for which primes $p$ are there $BH(4p,p)$ matrices.

Setting $p=3,n=q=s=5$ in Part $3$ above we arrive to the following

Observe that we cannot apply Theorem 1.4.3 directly, as $n=2+3$, and indeed, it is easy to exhibit a pair of orthogonal rows from sixth roots of unity. We shall recall a direct argument for Corollary 1.4.6, but first let us see the following

For a complex Hadamard matrix $H$ of order $n$ we have $|\det(H)|=n^{n/2}$.

Indeed, as the determinant is multiplicative, we have

It is easy to see that complex Hadamard matrices have the largest determinant amongst all matrices whose entries are at most $1$ in absolute value .

The following is attributed to de Launey (see ).

We use Lemma 1.4.7 and try to reach a contradiction. Suppose to the contrary, that there is a $BH(5,6)$ matrix $H$. Then observe that its determinant is a sum of sixth roots of unity and hence there are integral numbers $A$ and $B$, such that $\det(H)=A+B\omega$. Therefore we find that

the right hand side, however, cannot be $2$ modulo $3$, a contradiction. ∎

For a class of $BH(n,q)$ matrices some further non-existence results shall be obtained in Section 3.2. Finally we emphasize that $BH(n,q)$ matrices can be quickly recognized.

Suppose that a complex Hadamard matrix $H$ is equivalent to a $BH(n,q)$ matrix. Then the dephased form of $H$ must be composed of purely complex $q$th roots of unity.

Indeed, if the dephased form of $H$ would contain an entry which is not a root of unity, then the Haagerup invariant set would contain this entry as well. However, the Haagerup set of $BH(n,q)$ matrices can contain some subset of the $q$th roots of unity only. ∎

It follows that checking the number of inequivalent $BH(n,q)$ matrices in dephased parametric families is a finite process. We shall repeatedly use this fact in the next subsection.

The automorphism group of a $BH(n,q)$ matrix $H$ is the group of pairs of monomial matrices $(P,Q)$, such that $H=PHQ$; a monomial matrix is an $n\times n$ matrix having a single nonzero entry in each row and column, these nonzero entries being complex $q$th roots of unity.

Note that the automorphism group depends on the choice of $q$, i.e. on the ambient space in which the $BH(n,q)$ matrix is considered.

$BH(n,4)$ matrices are probably the most natural examples of complex Hadamard matrices. In fact, in various earlier literature the term “complex Hadamard matrix” was used to refer to them exclusively, and the term “unit Hadamard” was proposed for the more general objects we are concerned with . There are a vast number of papers available on $BH(n,4)$ matrices both in the mathematics and in the engineering literature, as they have many industrial applications, most notably in communications and coding theory through complex Golay sequences . For further applications we refer the reader to the manuals and .

In this brief section we investigate $BH(n,4)$ matrices of small orders, and give a full classification of them up to order $8$. We believe that this result is already known, but we were unable to find any relevant reference in this respect. Nevertheless, the presentation of these matrices in terms of infinite, affine families is indeed new, which is our contribution to this section.

The following is immediate from Theorem 1.4.3.

If a $BH(n,4)$ matrix exists then $n=1$ or $n$ is even.

Similarly to the real case, it seems that this trivial restriction is the only one, as we have the following long-standing

For every even $n$ there is a $BH(n,4)$ matrix.

It turns out that Conjecture 1.4.11 implies the Hadamard conjecture thus the existence of $BH(n,4)$ matrices is deeply entwined with the existence of real Hadamard matrices (see ). We have the following folklore

If a $BH(n,4)$ matrix exists then so does a $BH(2n,2)$, that is a real Hadamard matrix of twice the size.

We can lift the starting point $BH(n,4)$ matrix via the function $\varphi_{B}(.)$ which assigns to the entries $\pm 1$ and $\pm\mathbf{i}$ the $2\times 2$ real Hadamard matrices

where the $\pm$ signs on the left and right hand side of the maps agree. ∎

Let us stop for a moment and observe that both matrices featuring in the example above are equivalent to a circulant one. It is natural then to try to obtain circulant $BH(n,4)$ and $BH(n,2)$ matrices. However, we have the following discouraging

There is no circulant real Hadamard matrix for $n>4$.

The fact that Conjecture 1.4.14 is still open shows how little understanding we have about real Hadamard matrices. For the $BH(n,4)$ case we recall from the following

The circulant matrices, induced by the first rows

are $BH(n,4)$ matrices for order $n=2,4,8$ and $16$, respectively.

There is no circulant $BH(n,4)$ matrix for $n>16$.

The following is a strong evidence, supporting the truth of Conjecture 1.4.16:

Let $P$ be any finite set of primes. Then there are only finitely many circulant $BH(n,4)$ matrices of order $n$, where all prime divisors of $n$ are in $P$.

So it seems that “nice” circulant complex Hadamard matrices are rare. This is not quite the case if one allows higher roots of unity or not necessarily root of unity entries to appear in the matrix. We will return to circulant matrices in Section 3.3.

It turns out, however, that $BH(n,4)$ matrices with circulant core exist for infinitely many orders $n$. The following is the complex counterpart of Theorem 1.1.17.

Now we turn to the parametrization of $BH(n,4)$ matrices, and investigate whether we have an analogue, more-or-less trivial way to introduce affine parameters into them similarly to the real case (see Lemma 1.2.15) for large enough $n$. It is immediate, that Lemma 1.2.15 applies as long as a $BH(n,4)$ matrix features two purely real rows or columns. Not every $BH(n,4)$ matrix has this type of structure though, as Theorem 1.4.18 clearly shows; nevertheless members of that particular class can be parametrized, as was shown in our Master’s thesis . The following easily comes from Theorem 1.2.16.

Suppose that $H$ is a dephased $BH(n,4)$ matrix such that its core has main diagonal $-1$ and all other entries are $\pm\mathbf{i}$. Then $H$ admits an at least one-parameter affine orbit.

The reader might wish to jump ahead to Example 2.2.2 to see the one-parameter matrix $D_{6}^{(1)}(c)$ as an illustration. So far we have accounted all $BH(n,4)$ matrices up to order $6$. Indeed, it is rather easy to see that they are equivalent to $F_{1}$, $F_{2}$, either $F_{2}\otimes F_{2}$ or $F_{4}$, and $D_{6}^{(1)}(1)$, respectively. The following is a short summary.

The number of inequivalent $BH(n,4)$ matrices reads $1,1,2,1$ for $n=1,2,4,6$. The matrices of orders $1$ and $2$ are isolated, whereas the matrices of orders $4$ and $6$ are part of an infinite, one-parameter affine family of complex Hadamard matrices.

To further investigate the parametrizing capabilities of $BH(n,4)$ matrices, we have fully classified $BH(8,4)$ matrices. The results are quoted from as follows.

There are $15$ $BH(8,4)$ matrices, up to equivalence. All these matrices are members of $3$, partially overlapping family of complex Hadamard matrices. All these matrices can be distinguished by the number of $4\times 4$ vanishing minors they contain up to transposition, conjugation and adjoint.

The proof is a straightforward exhaustive computer search. ∎

We remark here that the proof is “straightforward” because the size of the problem is rather moderate. However, as the parameters $n$ and $q$ are increased, the classification problem of $BH(n,q)$ matrices becomes computationally challenging. For some advanced techniques we refer the reader to and .

It seems that all major features are shared by the matrices $H$, $H^{\ast}$, $\overline{H}$ and $H^{T}$, therefore we have introduced the following

In what follows we describe the three parametric families mentioned in Theorem 1.4.21. Our first example is essentially the Fourier family $F_{8}^{(5)}$, reported first in .

As $F_{8}^{(5)}(a,b,c,d,e)$ features two rows and columns with entries $\pm 1$ it is an infinite family of jacket matrices (see ). Note that $F_{8}^{(5)}(a\tau,b\tau^{2},c\tau^{3},d\tau^{2},e\tau^{3})$ where $\tau=\mathbf{e}^{2\pi\mathbf{i}/8}$ is an eighth root of unity coincides with the matrix listed in , and hence is of Diţă-type. The matrix corresponding to $F_{8}^{(5)}(-1/t^{2},\mathbf{i},-\mathbf{i}/t^{2},-\mathbf{i},-\mathbf{i}/t^{2})$ is equivalent to an infinite family of circulant matrices (see Theorem 3.3.4), containing in particular Horadam’s matrix $K_{4}(\mathbf{i})$ (see [67, p. $88$]).

After evaluating the matrix $F_{8}^{(5)}(a,b,c,d,e)$ at the $4^{5}=1024$ possible quintuples (see Lemma 1.4.8), we obtain the following

The family $F_{8}^{(5)}(a,b,c,d,e)$ contains $8$ inequivalent $BH(8,4)$ matrices: the symmetric matrices $F_{8}^{(5)}(1,1,1,1,1)$, $F_{8}^{(5)}(1,\mathbf{i},\mathbf{i},\mathbf{i},\mathbf{i})$, $F_{8}^{(5)}(\mathbf{i},1,\mathbf{i},1,\mathbf{i})$ and $F_{8}^{(5)}(1,1,\mathbf{i},1,\mathbf{i})$; and further the matrices $F_{8}^{(5)}(1,1,1,1,\mathbf{i})$, $F_{8}^{(5)}(1,1,\mathbf{i},\mathbf{i},\mathbf{i})$, and their transpose.

In another family of $8\times 8$ complex Hadamard matrices were obtained from translational tiles in abelian groups (see Section 1.4.3):

It was shown that the matrix $S_{8}^{(4)}(\mathbf{i},\mathbf{i},\mathbf{i},1)$ is not of Diţă-type, and as the set of Diţă-type matrices is closed it follows that a small neighborhood around it avoids the family $F_{8}^{(5)}(a,b,c,d,e)$ completely. The matrix corresponding to $S_{8}^{(4)}(1,1,\mathbf{i},\mathbf{i})$ is equivalent to the “jacket conference matrix” $J_{8}$ . By evaluating the matrix $S_{8}^{(4)}(a,b,c,d)$ at the fourth roots of unity we find the following

The family $S_{8}^{(4)}(a,b,c,d)$ and its transpose contain $8$ inequivalent $BH(8,4)$ matrices: the real Hadamard matrix $S_{8}^{(4)}(1,1,1,1)$ and $S_{8}^{(4)}(1,1,\mathbf{i},\mathbf{i})$, which are equivalent to a symmetric matrix, and further the matrices $S_{8}^{(4)}(1,1,1,\mathbf{i})$, $S_{8}^{(4)}(1,\mathbf{i},1,\mathbf{i})$, $S_{8}^{(4)}(1,1,\mathbf{i},1)$, and their transpose.

By analyzing the fingerprint of the obtained matrices, one can see that the following equivalences hold: $S_{8}^{(4)}(1,1,1,1)\sim F_{8}^{(5)}(1,1,1,1,1)$ and $\left(S_{8}^{(4)}(1,1,\mathbf{i},1)\right)^{T}\sim F_{8}^{(5)}(1,1,1,1,\mathbf{i})$, and therefore a further family is required to describe all of the $15$ $BH(8,4)$ matrices.

The family $S_{8}^{(4)}(a,b,c,d)$ is a maximal affine family (in the sense of ) and hence it cannot be part of larger, say, five-parameter affine family of complex Hadamard matrices. $\square$

The following matrix was constructed from MUBs of order $4$ (see Section 2.4) by Diţă very recently in :

We will see shortly that the family $D_{8B}^{(5)}(a,b,c,d,e)$ is essentially different from the families $F_{8}^{(5)}(a,b,c,d,e)$ and $S_{8}^{(4)}(a,b,c,d)$, as it accounts for most of the $BH(8,4)$ matrices. We remark here that the family $\left(D_{8B}^{(5)}(a,b,c,1,c)\right)^{T}$ is equivalent to the three-parameter family $P_{8}$ reported in . We have the following

The family $D_{8B}^{(5)}(a,b,c,d,e)$ together with its transpose contain $11$ inequivalent $BH(8,4)$ matrices, namely the real Hadamard matrix $D_{8B}^{(5)}(1,1,1,1,1)$, $D_{8B}^{(5)}(1,1,\mathbf{i},1,1)$ and the matrix $D_{8B}^{(5)}(1,\mathbf{i},\mathbf{i},1,\mathbf{i})$, which are all equivalent to symmetric matrices, and further $D_{8B}^{(5)}(1,1,1,1,\mathbf{i})$, $D_{8B}^{(5)}(1,1,1,\mathbf{i},\mathbf{i})$, $D_{8B}^{(5)}(1,1,\mathbf{i},\mathbf{i},1)$, $D_{8B}^{(5)}(1,\mathbf{i},\mathbf{i},\mathbf{i},\mathbf{i})$, and their transpose.

In particular, the matrix $D_{8B}^{(5)}(1,1,\mathbf{i},\mathbf{i},1)$ is not a member of any of the families $F_{8}^{(5)}(a,b,c,d,e)$, $S_{8}^{(4)}(a,b,c,d)$ or $\left(S_{8}^{(4)}(a,b,c,d)\right)^{T}$.

It is possible to separate the matrices $F_{8}^{(5)}(1,1,1,1,\mathbf{i})$, $F_{8}^{(5)}(1,1,\mathbf{i},\mathbf{i},\mathbf{i})$, $S_{8}^{(4)}(1,1,1,\mathbf{i})$, $S_{8}^{(4)}(1,\mathbf{i},1,\mathbf{i})$ and $D_{8B}^{(5)}(1,1,\mathbf{i},\mathbf{i},1)$ from their transpose by considering their rectangular rank profile. $\square$

The summary concerning $BH(8,4)$ matrices is available in Table 1.1 for which the legend is as follows:

By Definition 1.4.29 there are integral matrices $S$ and $T$ of orders $n\times r$ and $r\times n$ such that $ST\equiv L$ (mod $4$). Our goal is to modify the decomposition $S$ and $T$ by eventually showing that $T$, after proper modifications, consists of some of the rows of $L$. First observe that one can suppose that there is a number $1$ in every column of $S$. Indeed: if there is no number $1$ present in a column, but there is a number $3$, then one can multiply that column and the corresponding row of $T$ by $3$ to leave the product matrix $ST$ unchanged. If there are neither numbers $1$ nor $3$ in a column, then one can change every $2$ to $1$ and then multiply the corresponding row of $T$ by $2$ to leave the product matrix $ST$ unchanged. Let us denote the $i$th row of $S$ and $T$ by $\alpha_{i}$, $i=1,\ldots,n$ and $v_{i},i=1,\ldots,r$, respectively.

Now consider a row of $S$, say $\alpha_{j}$, of which the first coordinate is $1$. It follows that the $j$th row of $L$, $L_{j}$, can be written in the form $\alpha_{j}T\equiv L_{j}$ (mod $4$), and as the coefficient of the vector $v_{1}$ is $1$, one can express $v_{1}$ in terms of $L_{j}$ and $v_{2},\ldots,v_{r}$. Now it follows trivially that we can use the row $L_{j}$ instead of $v_{1}$ in $T$ by appropriately changing $S$. In particular, the $j$th row of $S$ can be set to $[1,0,\ldots,0]$. Now the whole argument can be repeated, mutatis mutandis until $r$ rows of $L$ are featured in $T$. ∎

So it seemed that all $BH(n,4)$ matrices admit an affine orbit for $4\leq n\leq 8$, yet a general parametrization scheme remained to be found. In order to find more examples of $BH(n,4)$ matrices the author jointly with Pekka Lampio and Patric Östergård proved the following result in :

Every $BH(n,4)$ matrix for $n=10,12$ admit an affine orbit.

This further supports the idea that all $BH(n,4)$ matrices can be parametrized in some “magical” way, perhaps through Theorem 1.2.16. As it is an ongoing work we do not give any further details regarding Theorem 1.4.32, its sole purpose is to give contrast to the following rather surprising

The following is an isolated $BH(14,4)$ matrix:

The matrix $L_{14A}^{(0)}$, described in Example 1.4.34 above, has defect and hence the statement follows from Proposition 1.2.30. ∎

Therefore Lemma 1.2.15 does not have a complex analogue working for all $BH(n,4)$ matrices. It is natural though to ask the following

Identify some large class of $BH(n,4)$ matrices admitting an infinite, affine orbit.

Once it is realized that there are isolated $BH(n,4)$ matrices one would like to understand how common they are. Isolated matrices are unique objects which cannot be obtained from parametric families due to their rigid structure. Therefore we pose the following

Find additional isolated $BH(n,q)$ matrices for $n\leq 14$.

A related, equally important problem besides the classification of $BH(n,4)$ matrices is finding new construction methods yielding $BH(n,4)$ matrices in those orders where the existence of these objects is unresolved. It seems (see ) that the smallest outstanding order is $n=70$; we pose this here as a relevant

4.2 A course on B​H​(n,6)𝐵𝐻𝑛6BH(n,6) matrices

In this section we briefly describe the simplest case of $BH(n,q)$ matrices when $q$ is composite, i.e. when $q=6$. There is a renewed interest in the existence of $BH(n,6)$ matrices, in part because of the following seminal result due to Compton, Craigen and de Launey. Recall that we have denoted by $\omega$ the principal cubic root of unity (see Definition 1.1.2).

A $BH(n,6)$ matrix with no $\pm 1$ entries is called an unreal $BH(n,6)$ matrix.

The $3\times 3$ unreal circulant complex Hadamard matrix, equivalent to $F_{3}$, induces the (unique) real Hadamard matrix of order $12$ as follows

Theorem 1.4.38 establishes a strong connection between the existence of real and a class of $BH(n,6)$ matrices. However, by Corollary 1.4.6 there is no $BH(5,6)$ matrix and therefore it is impossible to obtain a real Hadamard matrix of order $20$ with this method. Another implication of Corollary 1.4.6 is that one does not have direct access to $BH(25,6)$ matrices via the Kronecker product. In what follows we use a related approach to construct such a matrix.

We plug some unknown, unimodular matrices $X$, $Y$ and $Z$ of order $5$ into the $5\times 5$ Paley matrix in place of its entries $\{0,1,-1\}$ to obtain

and try to solve the arising orthogonality equations. As the underlying matrix is circulant, we have only three equations to deal with, namely

It remains to find some feasible matrices $X,Y$ and $Z$, composed from sixth roots of unity. It is straightforward to attack the problem with a computer search, however, to shrink the size of the search space considerably we impose the simplifying assumption that all $X,Y$ and $Z$ are circulant. In this way we have found the following solution to the system of equations (1.11)-(1.13):

Next we describe our construction method in a more sophisticated way by using the Kronecker product. Let $P$ be the Paley matrix of order $p$ and decompose it into $(0,1)$-matrices $S$ and $N$ such that $P=S-N$. The matrices $S$ and $N$ are circulant, hence they commute and their first rows are the indicator vector of the squares and nonsquares modulo $p$. Based on the example we have found of order $25$ we expect that

is a $BH(p^{2},6)$ matrix. Note that it is unimodular, as required. Let us simplify $H$ as follows

Now multiply $H$ by $-\omega^{2}$ to obtain

and check if $K$ is complex Hadamard. We have

This construction is a joint work with Professor Robert Craigen and will be included in a forthcoming publication in the near future. We summarize it in the following

Let $p$ be a prime number and $P$ be the Paley-matrix of order $p$. Then the matrix $H=P\otimes P+J\otimes I+\omega I\otimes J$ is a $BH(p^{2},6)$ matrix.

A construction, similar in spirit, can be found in the early literature (cf. , ) resulting in various real orthogonal matrices.

For every natural numbers $n$ and $k$ there is a $BH(n^{2k},6)$ matrix.

Use the binary expansion of $2k$ and the Kronecker product of square matrices from Theorem 1.4.41. ∎

Now we construct some sporadic examples of bicirculant $BH(n,6)$ matrices.

where $P=S-N$ is the Paley-matrix of order $11$, such that $S$ and $N$ are the $(0,1)$-characteristic matrices of the squares and nonsquares modulo $11$. Then, we find that