Matrices mod p, The Order of G

The Order of G

Build n linearly independent rows, one at a time, starting at the top. The first row can be anything but 0, hence there are pn-1 possibilities. Once selected, the second row can be anything other than a scale multiple of the first. That leaves pn-p possibilities. The third row can be anything other than the space spanned by the first two rows. This space has size p2, hence there are pn-p2 possibilities. continue down to the bottom row, which can be filled in pn - pn-1 ways. Multiply these expressions together to get the size of G. Of course we want the determinant to be 1, so the bottom row has to be scaled by something to make this work. That will remove a factor of p-1, but let's not worry about that right now.

Pull the powers of p out of each expression, and find p raised to the (n2-n)/2. That leaves (p-1) × (p2-1) × (p3-1) × … (pn-1). Throw away the first factor of p-1 to make the determinant 1. This gives the order of G. For instance, p = 5 and n = 3 has order 372000.

for a larger finite field, replace each p with w, where w is a power of p. The reasoning is the same.

Sylow Subgroup

The standard p sylow subgroup S has ones down the main diagonal and arbitrary entries below. Verify that S is a subgroup, closed under multiplication, and the determinant is always 1. The size is correct: p raised to the (n2-n)/2. So S is a sylow subgroup, and all other sylow subgroups are conjugate to S.

Write any matrix in S as 1+y, where 1 is the main diagonal and y is everything below. Since 1 and y commute, evaluate (1+y)p via the frobenius homomorphism. Multiply y by itself again and again, and the nonzero entries are pushed down and to the left. Since p is at least n, (a postulate that I set forth in the introduction), the lower entries go away, and we are left with 1. This means every element of S has order p.

At first this seems like a contradiction. Every finite group can be represented with matrices, including the cyclic group of order p2. However, such a representation has large matrices, with n comparable to p2. This contradicts n ≤ p. So we're all right. Within our constraints, each p group has multiplicative order p. Everything raised to the p is 1. This because each p group belongs to a p sylow subgroup by the first sylow theorem, and each sylow subgroup is isomorphic to S, and everything in S has order p.

Replace p with w, and S is still a sylow subgroup of the correct size for our finite field. Once again every p group has multiplicative order p. Note that we only need assume n is bounded by p, not w, which could be quite a bit larger than p.

don't assume the sylow subgroup is abelian. Let n = 3, and let A have ones on and below the main diagonal. Let B = A, except for 2 in the second row first column. Verify that AB ≠ BA.

Reflection

The upper triangular matrices, with ones down the main diagonal, is the same sylow subgroup as S, up to isomorphism. In fact they must be conjugate to each other. The transformation is accomplished by a matrix T with ones down the antidiagonal, and a -1 at the lower left to make the determinant 1. Multiply by T on the left, and you reflect the rows top to bottom, negating the (new) bottom row. Note that T2 is the identity matrix with -1 in the upper left and lower right. Thus T4 = 1. The inverse of T, or T3, looks like T, but -1 is now at the upper right. Multiply by T inverse on the right, and you reflect the columns left to right, negating the (new) rightmost column. Conjugation by T spins the lower triangular matrix around, making it upper triangular; with the side effect of negating the entries in the rightmost column above the main diagonal. Do this again and you are lower triangular, with the left row and bottom column negated, save the corners. Two more times and you are back where you started. Thus T has order 4 in the group of automorphisms of G, and T2 is an automorphism of order 2 on S and on G.

If n is odd, place -1 in the middle of T, and T has order 2. T also has order 2 if p = n = 2. Finally, if n = 2 and p > 2, T2 = -1, which commutes with everything, So T still has order 4, but T induces an automorphism of order 2. You can build a comparable matrix whenever n is even.

0001
0010
0-100
-1000

Normalizer

Let S be the standard lower triangular sylow subgroup, and assume ZS/Z = S. Suppoze Z has a nonzero entry above the main diagonal, in row i column j. Select the least i for which this is the case. Let Z conjugate the matrix with ones on the main diagonal and 1 in row j column i. Consider the identity and the extra 1 separately. The conjugate of the identity is the identity, so concentrate on the extra 1. Z times this matrix moves column j over to column i. Then multiply this by Z inverse and get various scale multiples of row i in Z inverse. In particular, the ith row is multiplied by Zi,j, which is nonzero. So Z inverse has to be 0 on the ith row to the right of the main diagonal. Remember that Z is 0 above row i and to the right of the main diagonal. Set Z times Z inverse = 1, and verify that Z inverse is also 0 above row i and to the right of the main diagonal. Therefore Z inverse is 0 on and above row i, and to the right of the main diagonal. apply the same reasoning in reverse, and the same must be true of Z. Yet Zi,j is nonzero. We have reached a contradiction. Any matrix that moves S onto itself is lower triangular.

Conversely, let Z be lower triangular. Separate Z, and Z inverse, and a matrix from S, into a diagonal piece and a lower piece. Expand the product to get 8 terms. Most wind up in the lower triangle. Only the product of the three diagonals lives in the main diagonal. Since diagonal entries in Z and Z inverse are inverses of each other, this product comes out all ones. The result is in S. The normalizer is lower triangular, with diagonal elements adjusted in any way you like, provided the determinant is 1. The size of the normalizer is the size of the sylow subgroup times (p-1)n-1.

If D is the abelian group of diagonal matrices, then S and D belong to the normalizer, and their sizes are relatively prime, with the product equal to the size of the normalizer; hence they generate the normalizer. In fact D represents the normalizer mod S, giving a semidirect product.

How Many Sylow Subgroups

The number of sylow subgroups is the index of the normalizer in G. We found the order of G at the top of this page. Divide out by the normalizer, and the number of sylow subbgroups is (p+1) × (p2+p+1) × (p3+p2+p+1) × … (pn-1+…+p2+p+1). This is 1 mod p, as it should be.

This generalizes to finite fields by replacing p with w. It also extends to G*, having the same sylow subgroup S, and a normalizer N of all invertible lower triangular matrices.

Eigen Values of 1

Let matrices have entries in a finite field F of size w, where w = pd. (You can let F be the integers mod p if you like.)

Let M be a matrix in G, build the characteristic polynomial c(x), and extend F up to K, where c(x) splits. Apply Schur's Theorem, and M is similar to a lower triangular matrix T with the eigen values on the diagonal. If these eigen values are all 1, Tp is the identity matrix. Thus Mp = 1. Conversely, let one of the eigen values be e, where e ≠ 1. Note that p is relatively prime to the order of the multiplicative group of K. Raising to the p power permutes the elements of K. Everything has a unique pth root, and only 1p = 1. Thus ep is something else. In other words, Mp is not 1. Therefore M is a pth root of 1 iff its eigen values are all 1.

In fact, the order of any matrix M is the least common multiple of its eigen values, or p times as much. Raise M to the lcm to get eigen values of 1; and no lesser exponent will do. This is then the identity matrix, or else it becomes so when raised to the p.

If the order is to be a prime q, then each eigen value has to have order q or 1. Conversely, if the eigen values have order q or 1, then M has order q or qp.

Power of q

Let the order of M be a power of q, where q is a prime other than p. Note that q could be 2. Each eigen value has an order of a power of q, and some eigen value has the same order as M. This eigen value is the root of a characteristic polynomial over p having degree n. It lives in a field extension of degree at most n. Our power of q divides p-1, or p2-1, or p3-1, or p4-1, etc up to pn-1. The size of G might have more powers of q, but the order of M is bounded by pn-1. Adjust this to wn-1 for a larger finite field F.

The q Sylow Subgroup

If q is a prime other than p, and q divides w-1, and q > n, the standard q sylow subgroup is particularly easy. It consists of diagonal matrices. If qe divides w-1, each diagonal entry, save the last one, can be any qe root of 1, independently of the others. Note that the size of the sylow subgroup is correct, relative to the order of G. (This is where we need q to be larger than n, so it doesn't divide any of the "other" factors. Divide w3+w2+w+1 by w-1, for instance, and get a remainder of 4; so q would have to divide 4.) This is an abelian group.

Step up to G*, and the last entry can take on any of the qe roots of 1. The q sylow subgroup is still diagonal, and still abelian.

What is the normalizer of this q sylow group? Let Z be in the normalizer, where Y is Z inverse. The dot product of the ith row of Z and the jth column of Y, where j ≠ i, is 0. It must remain 0 even if one of our diagonal matrices is placed in between. This scales the columns of Z. Suppose there are two nonzero terms in the dot product. Call them s and t. Use the diagonal matrix to scale s by u and t by v, where uv = 1. The result is still 0. Thus (u-1)s + (v-1)t = 0. The ratio s/t is -(v-1)/(u-1). Since u = 1/v, this simplifies to v. As long as there are two different values of v to choose from, besides 1, we have established a contradiction. This is no problem, unless qe = 2; but we are assuming q is larger than n. Thus the dot product of the row and column cannot contain two nonzero terms. One nonzero term produces a nonzero dot product, hence there are no nonzero terms. The nonzero entries in the row of Z completely miss the nonzero entries in the column of Y.

Suppose any row of Z, say the first row, has two nonzero entries. These must completely miss the nonzero entries in columns 2 through n of Y. We have cleared out two rows of Y, except for column 1. These two rows are not linearly independent, and Y is not invertible. This is a contradiction. Each row of Z can have only one nonzero entry.

If a column of Z has two nonzero entries, then the two rows, containing these two entries, are not linearly independent, and Z is not invertible. At this point Z is prescribed. Each row and each column has exactly one nonzero entry. This is the group I called E, for extended unit vectors, in an earlier section.

Select Z in E, and let Y be Z inverse. Note that Y is Z transpose, with the nonzero entries inverted. Multiply Z by a diagonal matrix, and the columns are scaled by the diagonal values. Multiply this by Y and you get the identity with its ones scaled by various values. This is a permutation of the original diagonal matrix, and a member of our q sylow subgroup. Therefore E is the normalizer. This works in G and in G*.

And how many q sylow subgroups are there? Find the index of E in G. all the factors of w-1 go away, leaving the powers of w times w+1 times w2+w+1 times w3+w2+w+1 etc, divided by n!.

Sylow Subgroups Intersect

Let n = 5, and start with the standard q sylow subgroup down the diagonal. Conjugate by Z, a matrix that is nontrivial in its first 3 rows and columns, (i.e. not in the normalizer), but is the identity matrix on 4 and 5. This carries our q sylow subgroup to some other q sylow subgroup. Yet both contain the q cycle generated by 1,1,1,u,1/u.

A similar construction applies to p cycles. Conjugate the upper left block, and let a p cycle be the identity matrix with 1 in position 5,4.

No p cycle belongs to all the sylow subgroups however. This is clear, since no p cycle is both lower triangular and upper triangular.

A Different q Sylow Subgroup

Let q be a prime, greater than n, and not equal to p, such that q divides one of the other factors: w+1 or w2+w+1 or w3+w2+w+1 etc. (We showed earlier that q will not divide w-1 in this case.) Extend the base field F up to a larger field K, so that the qth roots of 1 belong to K. Choose the smallest extension that will do the trick. Since q divides one of our outside factors, the dimension of K/F is no larger than n. Now q divides |K|-1. It won't divide |K|+1, or |K|2+|K|+1, or any of the extended factors, since q is still larger than n. apply the earlier result and build the standard q sylow subgroup over K. Call this group QS. Call the original sylow subgroup, over the field F, QF, and extend QF up to a subgroup QK over the field K. Naturally QK and QS are conjugate. We know that QF is abelian, because it is part of QK, which is conjugate to QS, which is abelian.

Recall from the above that QS is diagonal, and abelian, and if qe divides |K|-1, its size is qe(n-1). However, the size of QF cannot be determined in advance. Certainly q does not divide w, and with q > n, q does not divide w-1 either. But q could divide some of the other factors. For instance, 307 divides 172+17+1 and 175+174+173+172+17+1. There is a pattern here. With q and w-1 coprime, q divides w2+w+1 iff it divides w3-1. So ask when q divides wd-1. Exactly when the order of w, mod q, divides d. In our example, the order of 17, mod 307, is 3, so 3 and 6 work.

Even if q divides w-1, q2 might not. (Some power of q doesn't.) Now w has a certain order mod q2, and that tells you which of the other factors are divisible by q.