Feb.5 and 8 Important examples of designs, II: Hadamard matrices, particularly Sylvester and Paley NB Problems 6 and 7 of the present problem set are postponed till the next week: we won't get to intersection triangles or to the relevant use of inclusion/exclusion. Hadamard matrices These can be viewed as another generalization of Pi_2, from a different viewpoint. Take its intersection matrix and replace each 0 with a -1 (I.e. 2M-J). All rows (or columns) now have norm [self-inner-product] 7, and any two have inner product -1. So if we extend with a row and columns of +1's (and abbreviate +1 and -1 by just + and -): + + + + + + + + + + + - + - - - + + - + - - - + + - + - - - + + + + - - - + + - + - - - + + - + + - - + + - + - + - + + - + - - we get an 8x8 matrix H with (i) all entries +1 or -1, (ii) any two columns' inner products equal 0. (iii) any two rows' inner products equal 0, An nxn matrix with these properties is said to be a _Hadamard matrix_ or _H-matrix_ for short (see 1.27 on p.9) [though Sylvester already gave some examples ~25 years earlier]. We already know (ii) means H\T H = nI, so (as with M, but easier because no J's) readily deduce that either (ii) or (iii) may be omitted because they are equivalent given (i). Since the rows (or columns) of H are orthogonal, and all with the same norm n, we see that H/sqrt(n) is an orthogonal matrix. It follows that (as with M) we can find det(H) up to sign: it's a square root of det(nI) = n^n. That was the origin of Hadamard's interest in such matrices: Thm. (1.26, p.9) [Hadamard 1893]: If A is a real nxn matrix with entries of absolute value at most 1 then |det(A)| <= n^(n/2), with equality iff A is an H-matrix. Pf. This follows from: Thm. The absolute value of the determinant of any real matrix is at most the product of the lengths of its row vectors, with equality iff those vectors are pairwise orthogonal. This might be geometrically intuitive, but requires proof, especially as we shouldn't trust our geometric intuition of really high dimensions. Pf. Let v_1, v_2, ..., v_n be the rows of the matrix. Assume they are linearly independent, else the determinant vanishes and the inequality is vacuous. Define u_1, u_2, ..., u_n as follows (cf. Gram-Schmidt): u_1=v_1, and for each k the vector u_k is the projection of v_k to the orthogonal span of the complement of {u_j | j=1,2,...,k-1}. Then: (a) u_k = v_k + linear combination of u_j with j2. Go to equivalent H-matrix with top row J. In rows 2,3 let a,b,c,d be the number of columns of type ++, +-, -+, --. Then: a + b + c + d = n (there are n columns) a + b = c + d = n/2 (2nd row orthogonal to 1st) a + c = b + d = n/2 (3nd row orthogonal to 1st) a + d = b + c = n/2 (2nd row orthogonal to 3rd) Equivalently, a = b = c = d = n/4, QED. Now our construction of an 8x8 H-matrix from Pi_2 worked because it was a square 2-design with (k,v,\lam) = (4m-1, 2m-1, m-1) with m=2. Indeed, the above analysis shows: Prop. 1.28 (p.10) there is a Hadamard design of order n=4m iff there is a square 2-design with (k,v,\lam) = (4m-1, 2m-1, m-1) with m=2. Pf. <== extend 2M-J with a row and column of +1's as before. ==> go to an equivalent H-matrix with first row _and column_ of +1's, delete them, and use a=b=c=d=m. Definition: a square 2-(4m-1,2m-1,m-1) design is called a _Hadamard design_. Warning (Remark 1.29) isomorphic designs yield equivalent H, but not (always) conversely [because of the extra choice of which row and column to remove; we'll see that what H *does* uniquely determine is a 3-design]. Example (1.31) [Sylvester 1867] The points and hyperplanes of P^r(F_2) form a Hadamard design and thus yield a Hadamard matrix of order 2^(r+1). Equivalently, if d=r+1 and V is a d-dimensional vector space over F_2, the rows and columns of H are labeled by vectors of V (including zero!), and the i,j entry is 1 or -1 according as the inner product of the i-th and j-th vector is 0 or 1. [We're exploiting the fact that q=2 so there's no k* ambiguity in identifying a point or hyperplane with a nonzero vector in V or V*. Oh, sorry about the inevitable double use of "*" for both "multiplicative group of k" and "dual vector space of V".] See also Problem 4 on the current problem set (= CvL p.25 Ex.2). The next important example is presented in the text but not proved. We'll supply the proof. Example (1.30, still on p.10) [Paley 1933] If n=4m=q+1 for some prime power q, and k is a finite field of order q, then the set S of nonzero squares in k has size (q-1)/2 = 2m and is a "perfect difference set" (in a sense naturally extending what you saw in the first problem set): any nonzero c in k can be written as s-s' for m-1 choices of s,s' in S. Hence the collection of translates {S+x | x in k} of S is the set of blocks of a Hadamard design. The implication is proved as before: given distinct a,b in k, the number of x such that S+x contains both a and b is the number of s,s' in S s.t. s+x=a and s'+x=b. Necessarily s-s'=a-b, and given such s,s' we solve uniquely for x=a-s=b-s'. To prove that S is a perfect difference set, recall the following properties of squares in finite fields (generalizing familiar results of Legendre etc.): Proposition: Let k be a finite field of odd order q=2r+1. Then: (i) Every nonzero square s=x^2 in k is the square of exactly two elements of k, namely x and -x. (ii) The r-th power of any s in k* is either 1 or -1. s is a square iff s^r = 1. Proof: (i) Certainly f s=x^2 then s=(-x)^2 also, and -x is distinct from x because x is nonzero (this is where we use that q is odd); and if y is any square root then x^2=y^2, so (x-y)(x+y)=0, which in a field implies x-y or x+y vanishes so y is one of the known square roots x and -x. (ii) (s^r)^2 = s^(q-1) = 1 because s^q=s and s is nonzero. So s^r is a root of X^2-1 = (X-1)(X+1), so equal to 1 or -1. If s = x^2 then s^r = x^2r = x^(q-1) = 1 by the same argument. This gives r solutions of the degree-r polynomial equation x^r=1, so the squares in k are the only solutions of that equation. Corollary: (i) r of the 2r=q-1 nonzero elements of k are squares of elements of k. [Proof: the squaring map k* --> k* is 2:1 onto its image.] (ii) -1 is a square iff r is even. [Proof: that's the condition on r for (-1)^r to equal 1; note that, since q is odd, 1 and -1 are distinct.] (iii) If -1 is not a square then for any nonzero c either c or -c is a square but not both. Remark: if q is even then every element of k has a unique square root in k. Proof: the map k --> k taking x to x^2 is injective because x^2-y^2 = (x-y)^2 so x^2=y^2 iff x=y; since k is finite it follows that the map is surjective. Now to prove that the Paley construction actually gives a Hadamard design. In our setting q=4m-1 so r=2m-1 is odd and -1 is not a square. Part (i) of the Corollary says |S|=2m-1 so our blocks are of the right size. To prove it's a 2-design, we've seen already that we must show that if a,b are distinct elements of k we must count solutions s,s' in S of s-s'=a-b. Let c be the nonzero field element a-b. By part (i) of the Proposition the count is 1/4 the number of solutions in k* of x^2-y^2=c. Now there are q-1 solutions in k, because we have x^2-y^2=(x-y)(x+y) and there are q-1 factorizations, each of which yields unique (x,y) because 2 is invertible in k. Of those we must throw out solutions with x=0 or y=0. The number of x=0 solutions is 2 or 0 according as -c is or is not a square; for y=0 the count is 2 or 0 according as +c is or is not a square. But by (ii) exactly one of these two happens. Hence the number of solutions of x^2-y^2=c in (k*)^2 is (q-1)-2 = q-3 = 4(m-1) and we're done. QED So for n other than 1 and 2 we have Hadamard matrices of order n if @ n is a power of 2, or @ n = q+1 for some prime power q congruent to -1 mod 4. We shall see (Problem 4 = CvL p.25 again) that we also have Hadamard matrices of order n = n_1 n_2 for any known n_1, n_2 for which we've constructed a Hadamard matrix (including 2). This gives n=4m for m=1,2,4,8,16,... and powers of 2 times 1,2,3,5,6,7,8,11,12,15,17,18,... so up to m we're missing only 9 and 13. That's misleading: asymptotically 0% of m that are not multiples of 4 arise, because either m is a power of 2 (very rare) or 4m-1 or 2m-1 must be a prime power and that happens with probability asymptotic to 1/log(m). For n=4,8,31,128,... we get two constructions (even without taking Kronecker products) since n is both 2^e and q+1. The resulting Hadamard matrices are the same for n=4 and 8 (somewhat remarkably -- we'll return to this) but not for higher n [CvL Ex.15 on p.27], nor is Paley_128 isomorphic with H_4 x Paley_32. So Hadamard matrices of order n need not be unique when they exist. They _are_ unique at least for n=1,2,4,8,12, and this will be important to us when we study their automorphism groups.