On Fourier and Hadamard matrices of prime order

Introduction

The Fourier matrix $F_N$ of the cyclic group $\mathbb{Z}_N$ has one row for each character and one column for each element of the group, and couples these. With $w=e^{2\pi i/N}$, the pairing is $(i,j)\mapsto w^{ij}$ for $i,j=0,\ldots,N-1$. In matrix form we have

The quotient of two distinct rows is a nontrivial character, whose values sum to zero. Thus $F_NF_N^*=NI_N$, and $F_N$ is the basic example of a complex Hadamard matrix, a square matrix with entries in the unit circle $\mathbb{T}$ and mutually orthogonal rows.

As explained in [1], associated to every complex Hadamard matrix $H$ is a quantum permutation group $G$, and $H$ can be thought of as being the Fourier matrix of $G$. The construction uses the projections onto the lines spanned by the row quotients of $H$. For $H=F_N$ we recover $G=\mathbb{Z}_N$. In prime order $p$, the group $G$ is classical exactly when $H$ is equivalent to $F_p$.

There is arithmetic even in the diagonal of $F_N$. Its trace is the quadratic Gauss sum $\sum_{j=0}^{N-1} w^{j^2}$. For an odd prime $p$, the value is $\sqrt{p}$ if $p \equiv1 \pmod{4}$ and $i\sqrt{p}$ if $p \equiv3 \pmod{4}$. The sign in these formulas occupied Gauss for more than four years. He conjectured it in May 1801 and found his proof in August 1805 [3]. One can also read the sign from the Fourier matrix. The square of $F_p/\sqrt{p}$ sends the coordinate indexed by $x$ to the one indexed by $-x$, so the eigenvalues are among $1$, $-1$, $i$, $-i$. The determinant of $F_p$ is a Vandermonde determinant. Its phase resolves the ambiguity in the trace, as in Schur’s proof [3].

We ask how much of the character table one must see in a Hadamard matrix of prime order to recognize $F_p$. Three problems led us to this question.

• A. From orders 7 and 8 to order 11. In [9] we studied regular Hadamard matrices at orders 7 and 8. Regularity means that each quotient of distinct rows splits into rotated copies of $\mu_q$, the group of $q$th roots of unity, for primes $q$. At order 11, if one such quotient visits each vertex of a regular 11-gon once, the whole matrix is equivalent to $F_{11}$. On the classification of regular matrices of order 11 we hope to report later.

• B. The circulant theorem of Hiranandani and Schlenker. A circulant Hadamard matrix of prime order $p$ with entries in $\mu_p$ is equivalent to $F_p$ [11]. For odd $p$ the circulant matrix $(w^{(i-j)^2})$ gives $F_p$ after rescaling rows and columns and permuting columns. We ask about another symmetry of $F_p$. If $g$ generates the nonzero squares, $(a,x) \mapsto(ga,g^{-1}x)$ fixes the entry $w^{ax}$ and permutes the squares and nonsquares in two cycles on each side.

• C. Szöllősi’s observation on complementary blocks. Complementary square blocks of a unitary matrix have the same singular values, apart from extra copies of 1 in the larger block [2, 22]. This leads to formulas for the polar part of a complementary block [2]. For real Hadamard matrices, Koukouvinos, Mitrouli and Seberry used complementation to study minors [13, 14]. Here it relates the exponent differences in opposite blocks of a matrix with the two-orbit symmetry.

Write $H \sim H'$ for equivalence under permutations and unit scalings of rows and columns. Dephasing makes the first row and column all ones. A Butson matrix of level $k$ is a Hadamard matrix with entries in $\mu_k$. We write $B(N,k)$ for the set of such matrices of order $N$. Our first result explains how level $p$ arises.

A single $p$-cycle among the row quotients forces the entrywise power to have rank one. Thus $H \sim F_p$ for $p \le17$ by [12]. At level $p$ we can put any two rows in Fourier form. Each further Fourier row in that column ordering rules out a slope for the graph of the exponents of a missing row.

Can a symmetry force the Fourier rows when none is prescribed? Let $Q$ be the nonzero squares in $F_p$. A simultaneous symmetry is a pair of row and column permutations preserving every entry.

Comparing the four circulant blocks gives recognition at every odd prime through 109 (Corollary 7.14). Without assuming any symmetry, we can also recognize $F_p$ from a single block.

The rows and columns of the block may be permuted and rescaled independently. Theorem 10.4 allows up to $\lfloor|Q|/32\rfloor$ unspecified entries in each row and each column. For the dephased corner with one square row and one square column deleted, we prove recognition through $10^3$ (Proposition 9.4). At every odd prime, agreement with the missing Fourier column on more than $2\sqrt{p}+6$ surviving rows suffices (Proposition 10.5).

The paper is organized as follows. Sections 1–2 prove the power dichotomy of Theorem I and illustrate it with sixth-root matrices. In Sections 3–4 we use directions in the affine plane to prove Theorem II, then determine which regular triples with an 11-cycle extend. Sections 5–7 study the four circulant blocks by complementation and polar decomposition. Their cyclic orderings give Theorem III and the recognition tests through $10^9$. Sections 8–10 treat the inverse ordering, corner deletions and reconstruction from two strips. Theorem IV recovers the missing border.

Entrywise powers at prime order

Raising each entry of $F_p$ to its $p$th power gives the all-ones matrix. In a regular or Butson matrix of order $p$, two rows whose quotient is a $p$-cycle become proportional on taking $p$th powers. To see why this forces rank one, we begin with a lemma on flat matrices, whose entries have modulus one.

Proof. The number of row classes and the number of column classes both equal the rank, say $k$. Remove the proportionality phases and retain one row and column from each class to obtain a flat invertible $k\times k$ matrix $B$. Let $R=\operatorname{diag}(r_i)$ and $C=\operatorname{diag}(c_j)$ record the row and column class sizes. Orthogonality of distinct classes gives

Thus $CB^*=B^*R$, or $RB=BC$. Since all entries of $B$ are nonzero, $r_i=c_j$ for every $i,j$. Their common value is $d$, and $n=kd$. □

Proof. Work in a cyclotomic field $K$ containing the $z_j$. In its ring of integers, reduction modulo $p$ gives

Thus $a=(z_1^p+\cdots+z_p^p)/p$ is an algebraic integer. Every conjugate of $a$ is an average of roots of unity and has absolute value at most one. If $a\ne0$, the product over all embeddings of $K$ is a nonzero integer. Its absolute value is therefore one, and so is $|a|$. Equality in the triangle inequality forces all $z_j^p$ to coincide. □

Proof. Suppose first that $H$ is Butson, of any level. Apply Lemma 1.2 to the entries of each quotient of distinct rows of $H$. The corresponding rows of $K$ are orthogonal in the first case and proportional in the second. Since $H$ is square, its columns are orthogonal as well, and the same argument applies to each pair of columns. Lemma 1.1 now gives $\operatorname{rank}(K) \mid p$. In rank $p$ the rows are pairwise orthogonal, so $K$ is Hadamard. The only other possibility is rank one.

For regular $H$, fix a cycle decomposition of each row quotient. Let $G \subset\mathbb{T}$ be generated by the entries of $H$ and the groups $\mu_q$ for the cycle lengths $q$ used. This finitely generated abelian group splits as its torsion subgroup times a free abelian group. Fix the torsion subgroup pointwise and send each free generator to roots of unity tending to that generator. The resulting homomorphisms send each $t\mu_q$ to a rotated $q$-cycle, so applying them entrywise gives Butson matrices converging to $H$. Taking entrywise powers is continuous. The Hadamard condition and the vanishing of all $2 \times2$ minors are closed conditions. Thus $K$ is again either Hadamard or of rank one, since its entries have modulus one.

Finally, dephasing commutes with taking entrywise powers. A dephased matrix of rank one has all entries equal to one. Hence $K$ has rank one exactly when the entries of the dephased $H$ belong to $\mu_p$, as claimed.

Proof. The given pair becomes proportional after taking entrywise $p$th powers. Theorem 1.3 therefore gives rank one and puts the dephased $H$ in $B(p,p)$. In this form, every quotient of distinct rows or columns is a vanishing sum of $p$ elements of $\mu_p$. Its multiplicities are the coefficients of a polynomial of degree at most $p-1$ vanishing at $e^{2\pi i/p}$. This polynomial is a multiple of $1 + x + \cdots+ x^{p-1}$ and its coefficients sum to $p$, so each is one. Undoing the dephasing only rotates these cycles. The final assertion follows from Hirasaka, Kim and Mizoguchi [12 Theorem 1.1].