Circulant Hadamard Matrices

Circulant Hadamard Matrices An n × n matrix H is a Hadamard matrix if its entries are ±1 and its rows are orthogonal. Equivalently, its entries are ±1 and HH t = nI. In particular, det H = ±nn/2 . (1) It is easy to see that if H is an n × n Hadamard matrix then n = 1, n = 2, or n = 4m for some integer m. It is conjectured that the converse is true, i.e., for every such n there exists an n × n Hadamard matrix. An n × n matrix A = (bij ) is a circulant if it has the form bij = ai−j for some a0 , a1 , . . . , an−1 , where the subscript i − j is taken modulo n. For instance, ⎡ � a b c d � d a b c ⎢ ⎢ A=� � c d a b ⎣ b c d a is a circulant. Let A = (ai−j ) be an n × n circulant, and let � = e2�i/n , a primitive nth root of unity. It is straightforward to compute that for 0 � j < n the column vector [1, � j , � 2j , . . . , � (n−1)j ]t is an eigenvector of A with eigenvalue a0 + � j a1 + � 2j a2 + · · · + � (n−1)j an−1 . Hence det(A) = n−1 � j=0 (a0 + � j a1 + � 2j a2 + · · · + � (n−1)j an−1 ). (2) Note. The determinant of a circulant matrix is an example of a group determinant, where the group is the cyclic group of order n. In 1880 Dedekind suggested generalizing the case of circulants (and more generally group de­ terminants for abelian groups) to arbitrary groups. It was this suggestion that led Frobenius to the creation group of representation theory. See [1] and the references therein. Note that the matrix ⎡ −1 1 1 1 � 1 −1 1 1 ⎢ ⎢ � � 1 1 −1 1 ⎣ 1 1 1 −1 � is both a Hadamard matrix and a circulant. Conjecture (source?). Let H be an n × n circulant Hadamard matrix. Then n = 1 or n = 4. The main work on this conjecture is due to Richard Turyn [2]. He showed that there does not exist a circulant Hadamard matrix of order 8m, and he also excluded certain other orders of the form 4(2m + 1). Turyn’s proofs use the machinery of algebraic number theory. Here we will give a proof for the special case n = 2k , k ≡ 3, where the algebraic number theory can be “dumbed down” to elementary commutative algebra and field theory. It would be interesting to find similar proofs for other values of n. Theorem 1. There does not exist a circulant Hadamard matrix H of order 2k , k ≡ 3. k From now on we assume n = 2k and � = e2�i/2 . Clearly � is a zero of k−1 the polynomial pk (x) = x2 + 1. We will be working in the ring Z[�], the smallest subring of C containing Q and �. Write Q(�) for the quotient field of Z[�], i.e., the field obtained by adjoining � to Q. Lemma 2. The polynomial pk (x) is irreducible over Q. Proof. If pk (x) is reducible then so is pk (x+1). Recall that by Gauss’ lemma, an integral polynomial that factors over Q also factors over Z. If p(x), q(x) ≤ Z[x], write p(x) � q(x) (mod 2) to mean that the coefficients of p(x) − q(x) are even. Now pk (x + 1) � (x + 1)2 k−1 + 1 � x2 k−1 (mod 2). Hence any factorization of pk (x + 1) over Z into two factors of degree at least one has the form pk (x + 1) = (xr + 2a)(xs + 2b), where r + s = 2k−1 and a, b are polynomial of degrees less than r and s, respectively. Hence the constant term of pk (x + 1) is divisible by 4, a contradiction. It follows by elementary field theory that every element u ≤ Z[�] can be uniquely written in the form u = b0 + b1 � + b2 � 2 + · · · + bn/2−1 � n/2−1 , bi ≤ Z. The basis for our proof of Theorem 1 is the two different ways to compute det H given by equations (1) and (2), yielding the formula n−1 � j=0 (a0 + � j a1 + � 2j a2 + · · · + � (n−1)j an−1 ) = ±nn/2 = ±22 k−1 . (3) k−1 Thus we have a factorization in Z[�] of 22 . Algebraic number theory is concerned with factorization of algebraic integers (and ideals) in algebraic number fields, so we have a vast amount of machinery available to show that no factorization (3) is possible (under the assumption that each aj = ±1). Compare Kummer’s famous approach toward Fermat’s Last Theorem (which led to his creation of algebraic number theory), in which he considered the ⎦ n n n equation x + y = z as � n =1 (x + ζ y) = z n . We are continuing to assume that H = (aj−i ) is an n × n circulant Hadamard matrix. We will denote the eigenvalues of H by βj = a0 + a1 � j + a2 � 2j + · · · + an−1 � (n−1)j . Lemma 3. For 0 � j � n − 1 we have |βj | = ∼ n. Thus all the factors appearing on the left-hand side of (3) have absolute value ∼ n. First proof (naive). Let Hi denote the ith row of H, and let · denote the usual dot product. Then βj β¯j = (a0 + a1 � j + · · · + an−1 � (n−1)j )(a0 + a1 � −j + · · · + an−1 � −(n−1)j ) = H1 · H1 + (H1 · H2 )� j + (H2 · H3 )� 2j + · · · + (H1 · Hn )� (n−1)j . By the Hadamard property we have H1 · H1 = n, while H1 · Hk = 0 for 2 � k � n, and the proof follows. Second proof (algebraic). The matrix �1n H is a real orthogonal matrix. By linear algebra, all its eigenvalues∼have absolute value 1. Hence all eigen­ values βj of H have absolute value n. Lemma 4. We have 2 = (1 − �)n/2 u, where u is a unit in Z[�]. (4) Proof. Put x = 1 in xn/2 + 1 = n−1 � j=0 j odd to get 2 = ⎦ j (1 (x − � j ) − � j ). Since 1 − � j = (1 − �)(1 + � + · · · + � j−1 ), it suffices to show that 1 + � + · · · + � j−1 is a unit when j is odd. Let j j̄ � 1 (mod n). Then 1−� 1 − �j 1 − (� j )j̄ ≤ Z[�], = 1 − �j (1 + � + · · · + � j−1 )−1 = as desired. Lemma 5. We have Z[�]/(1 − �) � = F2 . Proof. Let R = Z[�]/(1 − �). The integer 2 is not a unit in Z[�], e.g., because 1/2 is not an algebraic integer. Thus by Lemma 4, 1 − � is also not a unit. Hence R ≥= 0. For all j we have � j = 1 in R since � j − 1 = (� − 1)(� j−1 + · · · + 1). Hence all elements of R can be written as ordinary integers m. But 0 = 2 in R by Lemma 4, so the only elements of R are 0 and 1. Lemma 6. For all 0 � j � n − 1 there is an integer hj ≡ 0 such that a0 + a1 � j + a2 � 2j + · · · + an−1 � (n−1)j = vj (1 − �)hj , where vj is a unit in Z[�]. Proof. Since 2 is a multiple of 1 − � by Lemma 4, we have by (3) that n−1 � j=0 (a0 + a1 � j + a2 � 2j + · · · + an−1 � (n−1)j ) = 0 in Z[�]/(1 − �). Since Z[�]/(1 − �) is a domain by Lemma 6, some factor a0 + a1 � j + · · · + an−1 � (n−1)j is divisible by 1 − �. Divide this factor and the right-hand side of (4) by 1 − �, and iterate the procedure. We continue to divide a factor of the left-hand side and the right-hand side by 1 − � until the right-hand side becomes the unit u. Hence each factor of the original product has the form v(1 − �)h , where v is a unit. Corollary 7. Either β0 /β1 ≤ Z[�] or β1 /β0 ≤ Z[�]. (In fact, both β0 /β1 ≤ Z[�] and β1 /β0 ≤ Z[�], as will soon become apparent, but we don’t need this fact here.) Proof. By the previous lemma, each βj has the form vj (1 − �)hj . If h0 ≡ h1 then β0 /β1 ≤ Z[�]; otherwise β1 /β0 ≤ Z[�]. We now need to appeal to a result of Kronecker on elements of Z[�] of absolute value one. For completeness we include a proof of this result, beginning with a lemma. Lemma 8. Let α be an algebraic integer such that α and all its conjugates have absolute value one. Then α is a root of unity. Proof. Suppose the contrary. Let deg(α) = d, i.e., [Q(α) : Q] = d. Now α, α 2 , α 3 , . . . are all distinct and hence infinitely many of them have the property that no two are conjugate. Each α j ≤ Q[α] and so is the root of a monic integral polynomial of degree at most d. If α1 , α2 , . . . , αd are the conjugates of α, then all the conjugates of α j are among α1j , α2j , . . . , αdj . Hence each α j satisfies the hypothesis that all its conjugates have absolute value 1 (and α j is an algebraic integer). Thus the rth ⎤ ⎥ elementary symmetric function er in α j and its conjugates has at most dr terms, each of absolute value 1, so ⎤⎥ |er | � dr . Moreover, er ≤ Z since α j is an algebraic integer. It follows that there are only finitely many possible polynomials that can be the irreducible monic polynomials with roots one of the α j ’s, contradicting the fact that there are infinitely many α j ’s for which no two are conjugate. Theorem 9 (Kronecker). Let ζ be any root of unity and � ≤ Q[ζ ] with |�| = 1. Then � is a root of unity. Proof. We use the basic fact from Galois theory that the Galois group of the extension field Q(ζ )/Q is abelian. Let � be a conjugate of �, so � = w(�) for some automorphism w of Q(ζ ). Apply w to the equation �� ¯ = 1. Since complex conjugation is an automorphism of Q(ζ ) it commutes with w, so we obtain ��¯ = 1. Hence all the conjugates of � have absolute value one, so � is a root of unity by the previous lemma. We now have all the ingredients to complete the proof of Theorem 1. Note that we have yet to use the hypothesis that ai = ±1. By Lemma 3 we have |β1 /β0 | = |β0 /β1 | = 1. Hence by Corollary 7 and Theorem 9 we have β0 = � −r β1 for some r. Expand n β0 and � −r β1 uniquely as integer linear combinations of 1, �, � 2, . . . , � 2 −1 : β0 = a0 + a1 + · · · + an−1 = ±n/2 � −r β1 = � −r ((a0 − an/2 ) + (a1 − an/2+1 )� + · · · ) = (ar − an/2+r ) + (ar+1 − an/2+r+1 )� + · · · . Equating coefficients of � 0 yields ±n/2 = ar − an/2+r . Since each ai = ±1, we must have n � 4, completing the proof. References [1] T. Y. Lam, Representations of finite groups: A hundred years, Part I, Notices Amer. Math. Soc. 45 (1998), 361–372; www.ams.org/notices/199803/lam.pdf. [2] R. Turyn, Character sums and difference sets, Pacific J. Math. 15 (1965), 319–346.