April 19: The Hadamard matrix H_12 and the Mathieu group M_12 (and the action of PSL_2(F_q) on Paley's Hadamard matrices in general) Theorem: the image in S_12 of the automorphism group of an order-12 Hadamard matrix H_12 is isomorphic with the Mathieus group M_12. Proof: For each of Bin(12,2)=66 pairs of columns there are six rows where they match and six where they do not. So we get a design D of 2*66 = 132 six-element subsets of the 12 rows -- or rather a structure because we haven't yet shown there are no repeats. We claim it is a Steiner (5,6,12) design with an action of Aut(H_12). Any automorphism (P,Q) of Aut(H_12) preserves D -- even the columns that are multiplied by -1 yield the same 6+6 split, only with the matched and unmatched rows switched. Since Aut(H_12) acts 5-transitively on rows, D is a 5-structure. But then its lambda is 132 / (Bin(12,5)/Bin(6,5)) = 1 so there can be no repeated blocks and we have a 5-(12,6,1) design as desired. We've already shown that this design is unique up to isomorphism and the automorphism group is M_12. We now see that Aut(H_12) acts on D, and of course -1 acts trivially and the action of Aut(H_12)/{1,-1} is faithful. Hence Aut(H_12)/{1,-1} is contained in M_12, and since both groups are simply 5-transitive -- and thus have the same size -- the map Aut(H_12) --> M_12 is an isomorphism, QED. It follows too that transposition of H_12 gives an _outer_ automorphism of M_12: as with S_6 it has two inequivalent actions, with the point stabilizer in one acting transitively on the other. This is because our construction of D from H_12 shows that the column-pair stabilizer M_10.2 acts on the rows as the block-pair stabilizer S6.2 . Hence M_10 has no fixed rows -- at worst its row orbits would have size 6 (though in fact it's transitive, as we'll explain) -- so the column M_11 acts transitively on rows. Proof: M_11 is simple, whence any orbit of a permutation representation must have size at least 11 if it is not a singleton (we already proved this for any simple group: the size of any nontrivial orbit is at least as large as the biggest prime factor of the group order). But even the M_10 orbits have size at least 6, so M_11 must be transitive as claimed. The simultaneous stabilizer in Aut(H_12) of both a row and a column is Aut(Paley) which we already identified with SL_2(F_11) in its 11-point permutation representation. Remarkably there's also a copy of SL_2(F_11) in M_12 that acts on both the rows and columns by its standard action on the 12 points of P^1(F_11). We already observed the analogous fact for SL_2(F_7) and H_8 in the course of our proof of the isomorphism between SL_2(F_7) and (P)SL_3(F_2). In fact this (unlike the 7- and 11-point representations) works for the Paley Hadamard matrix of order q+1 for any prime power q congruent to 3 mod 4. Recall that Paley makes such a matrix by labeling both the rows and the columns by P^1(F_q) and setting the (x,y) entry equal 1 iff either (a) x or y is infinity or (b) both are finite and x-y is a nonzero square. By construction the a^2 x + b group acts on both rows and columns without even resorting to sign changes. This is the point stabilizer of the action of PSL_2(F_q) on P^1; you shouldn't be too surprised then that allowing sign changes lets us extend the action to PSL_2(F_q), still acting the same way on rows and columns. Now the a^2 x + b group is a maximal proper subgroup of PSL_2(F_q), so once we show that any element of PSL_2(F_q) acts it will prove that all of PSL_2(F_q) does. For instance we can use z <--> -1/z, corresponding to the matrix [0, -1; 1, 0]. (It's also not too hard to show directly that this involution together with PSL_2(F_q) generates PSL_2(F_q), and even possible to show in the same way that any element of PSL_2(F_q) acts on the Paley matrix.) So permute both the rows and columns according to z <--> -1/z. We proceed to give a computational construction of an action of this permutation; a more conceptual one, without so much case analysis, appears later. The involution x <--> -1/z puts the 0 row and 0 column at infinity, and we must then multiply some rows and columns by -1 to make the new infinity row and column all +1. The (0,0) entry was -1, so (i) multiply row (inf,*) by -1. Now (inf,0) is what used to be (0,inf) so was +1, but we multiplied it by -1, so we must (ii) multiply column (*,0) by -1. For nonzero y in F_q, entry (inf,y) is what used to be (0,-1/y) so it's now +1 unless 0-(-1/y) = 1/y is a nonzero square, i.e. y is a square. So (iii) multiply column (*,y) by -1 if y is a nonzero square. Similarly for the finite-index rows, except that we didn't multiply (*,inf) by -1 to start, so (0,inf) is still +1 and we don't negate row (0,*). For nonzero x, entry (x,inf) used to be (-1/x,0) so was -1 unless -1/x was a square, i.e. x was a non-square (remember -1 is not a square because q is 3 mod 4). So, (iv) multiply row (x,*) by -1 if x is a nonzero square. So we've now made the (x,y) entries +1 if x or y is infinite. For the remaining cases: If x=y=0, the (x,y) entry was at (inf,inf) so was +1. We multiplied it by -1 in (ii) so it is now -1, as desired. If x=0 but y is not zero, the (x,y) entry was at (inf,-1/y) so +1. We multiplied it by -1 in (iii) iff y was a square. Hence it's -1 iff y is square, i.e. iff -y = x-y is not a square, again as desired. If y=0 but x is not zero, the (x,y) entry was at (-1/x,inf) so +1. We multiplied it by -1 in (ii), and again in (iv) if x is a square. So it's +1 iff x is square, again as desired because x = x-y here. If x=y and is not zero, the same is true for (-1/x,-1/y) so that entry was -1. It has been multiplied by -1 either twice, in (iii) and (iv), or not at all. So it's still -1 as desired. Finally suppose x and y are distinct nonzero elements of F. Then the x,y entry was 1 or -1 according as (-1/x) - (-1/y) = (x-y)/xy was a square or not. In (iii) and (iv) we multiplied it by -1 once iff just one of x or y is a square, i.e. iff xy is not a square. Hence it is now 1 iff x-y is a square, again as desired. QED! Corollary: M_12 contains PSL_2(11), acting transitively on rows and transitively on columns. Proof: Since H_12 is unique, the Paley matrix is isomorphic with it, so PSL_2(11) is contained in Aut(H_12) / {1,-1} = M_12. If you feel the derivation of the PSL_2(F_q) action has way too many cases -- that there should be a simpler explanation -- then you should prefer the following approach. Let k=F_q. Since we want to think of the all-(+1) row and column as having index infinity, we should really index the rows and columns by representatives of the lines in k^2. Use (x,1) and (y,1) for the finite-index rows and columns, and (a,0) and (b,0) for the ones at infinity, with a,b to be chosen soon. Observe that x-y is the determinant (x,1) ^ (y,1). So we aim to use the quadratic character of that determinant should to re-define the matrix. Since (a,0) ^ (y,1) = a while (x,1) ^ (b,0) = -b, we'll choose a=1 and b=-1 to maintain the pattern. Finally on the diagonal we have two representatives of the same line; let c be their ratio, and make the diagonal entry +1 iff c is not a square. Note that this works for our choice of row and column representatives: (x,1) = (x,1) [c=1, a square], while (1,0) = - (-1,0) [c=-1, not a square]. Now observe that if we change a row or column representative v to some other representative bv then that row or column is multiplied by +1 or -1 according as b is a square or not (on the diagonal as well as off it). Any SL_2(F_q) transformation, applied simultaneously to rows and columns, then yields an equivalent matrix because it preserves the determinant and permutes the q+1 lines: we need only multiply some rows and columns by -1 (namely those whose representative has been multiplied by a non-square) to recover the same matrix. We can also check directly that this construction yields a Hadamard matrix: given any two columns, we may as well choose coordinates so they're indexed by (1,0) and (0,1) and scale the corresponding rows to the same vectors, so their pattern is + + + - and then any other row (x,y) matches iff -y/x is a square which happens for exactly (q-1)/2 ratios y/x, so indeed we have the same number (q-1)/2 + 1 = (q+1)/2 of matches and mismatches. This approach also shows that before forming the quotient by {I,-I} we already had an action of PSL_2(F_q), because -1 acts by multiplying all the row and column representatives by -1 and that yields the same matrix.