April 16: The Hadamard matrix of order 12 and its automorphism group (which we'll identify with M_12, or rather 2.M_12) Recall (Feb.5): A _Hadamard matrix of order n_ is an nxn matrix H all of whose entries are +1 or -1 whose rows are pairwise orthogonal (whence its columns are too, since the condition is equivalent to H\T H = n I). Permuting rows or columns, and multiplying row or column by -1, produces and isomorphic design. Such an operation is H --> P H Q for signed permutation matrices P (for rows), Q (for columns). If P H Q = H then (P,Q) is an automorphism of H; the map (P,Q) --> P from Aut(H) to signed permutation matrices is an isomorphism because P determines Q (and because acting by (P,Q) and then (P',Q') yields P'P H QQ'). Ignoring the signs then gives a homomorphism to S_n whose kernel is {I,-I} (if P,Q are diagonal then PHQ=H implies P = Q = \pm I). Diagonal matrices (changing signs without permuting) let us put H in a standard form where the first row and column consists entirely of +1's. Then the remaining n-1 columns of each row but the first contain n/2 entries of -1 and (n/2)-1 entries of +1 (by orthogonality with the first row), and the collection of n-1 subsets of size (n/2)-1 form a square 2-(n-1, (n/2)-1, (n/4)-1) design D_H (using the orthogonality of the other rows and columns). Hence 4|n once n>2 (how does the n=2 Hadamard matrix [1,1;1,-1] escape?). It is conjectured that this necessary condition on n is also sufficient. For n=4 the Hadamard design has trivial parameters 2-(3,1,0), so it's certainly unique up to isomorphism, whence H is as well. For n=8 the Hadamard design has parameters 2-(7,3,1), so we now know it is the unique Pi_2. Thus there's a unique 8*8 Hadamard matrix. Its automorphisms are the same group AGL_3(F_2) of its 3-(8,4,1) Steiner system. Today we consider n=12. Then D_H has parameters 2-(11,5,2), so is again unique. Hence so is H. We just saw that D_H has automorphisms by PSL_2(F_11), so Aut(H) contains that group in its row and column stabilizer. It is also transitive on ordered pairs (row, column), because moving and row and column to (1,1) and normalizing it to +1's yields an isomorphic Hadamard matrix. Moreover, Aut(D_H) is 2-transitive so Aut(H) is at least 3-transitive. We show that in fact it is sharply 5-transitive! Start from scratch: 1) Normalize the first row to +1's (but not the first column). 2) Now any further row has six +1's and six -1's. Permute the columns of row 2 so that the six +1's are columns 1-6. 3) Now suppose row 3 has x of its +1's in columns 1-6 and the remaining 6-x in 7-12. Then (row 2) . (row 3) = x - (6-x) - (6-x) + x = 4x-12. Since that's zero, x=3. (That's of course the simple proof that 4|n once n>2.) Permute the columns to put each triplet of +1's as early as possible. So far our matrix is: + + + + + + + + + + + + + + + + + + - - - - - - + + + - - - + + + - - - Note that the triplets are equivalent: any double transposition yields the same matrix with row 2 and/or 3 multiplied by -1. 4) Any further row has a,b,c,d +1's among columns 1-3, 4-6, 7-9, 10-12 satisfying a+b+c+d = 6, a+b+(3-c)+(3-d)=6, a+(3-b)+c+(3-d)=6. The last two equations give a+b=c+d and a+c=b+d, which means a=d, b=c. So one of (3,0,0,3), (2,1,1,2), (1,2,2,1), (0,3,3,0). I claim that the first and last are impossible. Indeed if we had (3,0,0,3) then it would have to be + + + + + + + + + + + + + + + + + + - - - - - - + + + - - - + + + - - - + + + - - - - - - + + + and (0,3,3,0) would be the same thing after multiplying row 4 by -1. But then the fifth and further rows would also have to satisfy a+d=b+c, and then a=b=c=d=3/2 which is impossible. (The analogous behavior *does* happen for n=8.) So we're left with (2,1,1,2) and (1,2,2,1). We multiply each row by -1 if necessary to assure it is (1,2,2,1). It is then determined by the choice of the +1 in columns 1-3, the -1 in columns 4-6, the -1 in columns 7-9, and the +1 in columns 10-12. This is still consistent with the triplet equivalence described at the end of (3), with the proviso that the double transpositions (12)(34) and (13)(24) change (1,2,2,1) to (2,1,1,2) and so require multiplying the row by -1. 5) Consider now the requirement that any two of rows 4-12 must be orthogonal. Each triplet of columns contributes +3 if its odd-sign-out columns match for the two rows, and -1 if not. To get zero we must then have 3-1-1-1. So any two rows match once and mismatch the other three times. Applying triplet equivalence, we assume rows 4 and 5 match in the first triplet; then applying equivalence of the three columns within each triplet we assume they match in column 1, while the odd-signs-out in the remaining columns are 4,7,10 and 5,8,12. So far we have: + + + + + + + + + + + + + + + + + + - - - - - - + + + - - - + + + - - - + - - + + - - + and all the columns have been fixed except that we can still switch columns 2 and 3. 6) We now show this determines the remaining 7 rows uniquely up to unique permutation. For starters, there's never a match in both columns 1-3 and columns 4-6. But there are only 3*3=9 choices and 12-3=9 rows, so each choice must occur. Permuting rows 5-12 to put them in lexicographic order gives + + + + + + + + + + + + + + + + + + - - - - - - + + + - - - + + + - - - + - - + + - - + + - ? ? ? ? ? ? + - ? ? ? ? ? ? + - ? ? ? ? ? ? + - ? ? ? ? ? ? + - ? ? ? ? ? ? + - ? ? ? ? ? ? + - ? ? ? ? ? ? Of course the same is true of any other pair of columns. That immediately determines row 6: + + + + + + + + + + + + + + + + + + - - - - - - + + + - - - + + + - - - + - - + + - - + + - - + + - ? ? ? ? ? ? + - ? ? ? ? ? ? + - ? ? ? ? ? ? + - ? ? ? ? ? ? + - ? ? ? ? ? ? + - ? ? ? ? ? ? Consider rows 4, 7, and 10. They match in triplet 2, so they must differ in each other column. Switching them if necessary (by switching columns 2 and 3) we may assume that row 7 singles out column 8, and row 10 singles out column 9: + + + + + + + + + + + + + + + + + + - - - - - - + + + - - - + + + - - - + - - + + - - + + - - + + - - ? ? ? + - ? ? ? ? ? ? + - ? ? ? ? ? ? + - - ? ? ? + - ? ? ? ? ? ? + - ? ? ? ? ? ? Now rows 5 and 7 use column 8. There must be one more such row, which matches neither 5 nor 7 elsewhere. So it must be row 12. Likewise column 9, used by rows 6 and 10, must also be used in 8; and the remaining rows (9,11) must use column 7: + + + + + + + + + + + + + + + + + + - - - - - - + + + - - - + + + - - - + - - + + - - + + - - + + - - ? ? ? + - - ? ? ? + - - ? ? ? + - - ? ? ? + - - ? ? ? + - - ? ? ? Finally: the row triplets {4, 8, 12}, {5, 9, 10}, {6, 7, 11} have not been matched yet, so they must each share columns 10-12: + + + + + + + + + + + + + + + + + + - - - - - - + + + - - - + + + - - - + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + which spelled out in full is + + + + + + + + + + + + + + + + + + - - - - - - + + + - - - + + + - - - + - - - + + - + + + - - + - - + - + + - + - + - + - - + + - + + - - - + - + - - + + + - + - - + - + - + - + + + - + - - - + - + + - - + + - + - - - + - + + + + - - + - - - + + - + - + + - - + - - + + + - + - + + - - Since we could start with any five rows, put them at 1,2,3,4,5 in order, and then choose the columns uniquely to get this matrix, it follows that the image of Aut(H) in S_{12} is simply 5-transitive as promised (and hence simple as shown in late March, since that depended only on 5-transitivity and the group size). We're guessing that this group is M_{12}. We could prove it by finding a construction of 2*66 hexads from H that is intrinsic and thus automatically invariant under the group; then these will automatically be the blocks of a 5-design, which will thus be the unique (5,6,12) Steiner system. Can you find such a construction?