How Large is your Penis?

Wednesday, October 6, 2010

Sizes of Linear Groups

Let F be a finite field with q elements. In fact given q (a power of a prime) there is just one such field (up to isomorphism of course, but algebraists are blind to isomorphic structures). Thus, it is well-defined (up to isomorphism, but again algebraists are supposed to be being to isomorphic structures) to define GL(n,q) to be the set of all $n\times n$ matrices over the field $\mathbb{F}_q$ that are invertible. It is easy to see that GL(n,q) is a group under matrix multiplication. This group is referred to as "the general linear group".

We can also define SL(n,q) to be the set all those elements in GL(n,q) which have determinant 1. Clearly, this is a subgroup of GL(n,q) because it contains the identity elements, which has determinant one. And if A,B are matrices with determinant 1 then AB is a matrix with determinant one by the formula $\det (AB) = \det (A) \det (B)$. This subgroup is referred to as the "special linear group".

We can define the following map $\phi : \text{GL}(n,q) \to \mathbb{F}_q^{\times}$ by $A \mapsto \det A$. By the property of determinants it follows that $\phi$ is indeed a group homomorphism (here we are treating $\mathbb{F}_q^{\times}$ as the multiplicate group of the field of the non-zero elements). This map is clearly onto, because for any $a\in \mathbb{F}_q^{\times}$ let A be an $n\times n$ diagnol matrix with 1's everywhere on the diagnol except for one entry which is replaced with $a$, such a matrix has determinant $a$. By definition $\ker (\phi) = \{ A \in \text{GL}(n,q) | \det (A) = 1\}$, but this is precisely the special linear group.

By the first isomorphism theorem (refer to here) the above group homomorphism gives us the isomorphism $\text{GL}(n,q)/\text{SL}(n,q)\simeq \mathbb{F}_q^{\times}$. For our present discussion this isomorphism will not be important for us. What will be important is that because the field, the general linear group, and the special linear group are finite, we get the following combinatorical statement $|\text{GL}(n,q)| = |\text{SL}(n,q)|\cdot (q-1)$.

What we would like to do is determine the sizes of the general and special linear groups. The above formula tells us that if we can determine the size of the general linear group then the size of the special linear group is immediate.

Let A be an $n\times n$ matrix over a field $\mathbb{F}_q$. This matrix A is invertible if and only if $A\bold{x}=\bold{0}$ has only the trivial solution where $\bold{x},\bold{0}$ are vectors in $\mathbb{F}_q^n$, by basic linear algebra. Let $\bold{c}_i$ be the i-th column of the matrix as a vector, and let $x_i$ be the i-th coordinate of $\bold{x}$. Then $A\bold{x}=\Sigma_i x_i\bold{c}_i$. Thus, the condition that $A\bold{x}=\bold{0}$ has a trivial solution is equivalent to saying $\Sigma_i x_i\bold{c}_i=\bold{0}$ has only a trivial solution for $x_i$. Thus, $A$ is invertible if and only if the columns of A are linearly independent when viewed as vectors.

Now we will determine the size of GL(n,q). Let A be an $n\times n$ matrix. For it to be invertible its first coloumn cannot consist of zeros. Because a zero vector in any set of vectors makes the set linearly dependent (unless the vectors belong to the zero-vector space, which is trivial and uninteresting). So we have any choice we want for the first n coordinates in the first coloumn except all zeros. This is $q^n-1$ choices. Consider the second coloumn. It can be anything except a multiple of the first coloum - because remember two non-zero vectors are linearly dependent iff they are multiples of one another. There are $q$ multiples of the first coloumn and $q^n$ choices for the second coloumn which means there are $q^n-q$ choices for the second coloumn such that the matrix still stays invertible. Now consider the third coloumn. It cannot lie in the spam by the first two coloumns. The spam formed by the first two coloumns is $\alpha \bold{c}_1+\beta\bold{c}_2$ where $\alpha,\beta$ vary over $\mathbb{F}_q$, and by linear independence distinct values for these constants determine distinct vectors. Thus, there are a total of $q\times q=q^2$ vectors that lie in the spam of the first two coloumns. The third coloumn must be linearly independent from this one, and there are $q^n$ choices which means the are $q^n-q^2$ choices for the third coloumn to be chosen so that the matrix stays invertible. Continuing in this manner we arrive at $|\text{GL}(n,q)| = (q^n-1)(q^n-q)...(q^n-q^{n-1})$. To make the formula more convenient we can pull out $q^k$ from $(q^n - q^k)$ to get $q^k(q^{n-k}-1)$. So that $|\text{GL}(n,q)|=q^{n(n-1)/2}(q-1)(q^2-1)...(q^n-1)$. This immediately tells us that $|\text{SL}(n,q)| = q^{n(n-1)/2}(q^2-1)...(q^n-1)$.

Actually there are two more linear groups that are worth considering. Those are the "projective general linear group" and the "projective special linear group". Recall that the "center" $\text{Z}(G)$ of a group $G$ is the subgroup $\{z : zg = gz\}$. The center of a group is always a normal subgroup. So we can consider the general linear group modulo its center. This is the projective general linear group $\text{PGL}(n,q)$. Its order will be the order of the general linear group divided by the order of the center. But we know what the center is, we determined the center back here. So the center is the non-zero multiples of the identiy matrix. There are $(q-1)$. Now we just need to divide the order of the general linear group by (q-1). Dividing by $(q-1)$ we get the number, $|\text{PGL}(n,q)| = q^{n(n-1)/2}(q^2-1)...(q^n-1)$.

Finally we need to determine the size of the projective special linear group. By a similar argument we can show that the center of the special linear group is $kI$. But $k$ cannot vary of any element of $\mathbb{F}_q^{\times}$. Because we require $\det (kI) =1$. Notice that $\det(kI)=k^n\det (I) = k^n=1$. Therefore, $k$ must be an n-th root of unity in the finite field $\mathbb{F}_q$. The number of roots of unity will depend on $n$. From basic field theory we know that $\mathbb{F}_q^{\times}$ is a cyclic group. Therefore, the number of solutions to $x^n=1$ is $\gcd(n,q-1)$. Therefore, if we set $d=(n,q-1)$ then $|\text{PSL}(n,q)| = \frac{1}{d}q^{n(n-1)/2}(q^2-1)...(q^n-1)$. So in the special special case when $n$ is relatively prime to $q-1$ we get that $|\text{PSL}(n,q)| = q^{(n-1)/2}(q^2-1)...(q^n-1)$.


  1. Is the blindness point really true? I recall one instance of an algebraicist differentiating isomorphic structures from identical structures - when talking about isomorphisms of short exact sequences, it matters if the maps from A to A' and C to C' are isomorphisms or identity maps.

  2. The blindness point is true as long as we care about structure and not about the actual elements themselves. Which is what algebra really cares about, the structure, not the name of the elements. Just like topologists are blind under homoemorphisms, because topology only cares about topological (geometric) properties.

    Let me illustrate how short-exact sequences are unaffected when isomorphic groups are used. Say for example:

    $0\to A\to_{i} B\to_{j} C\to 0$

    If this is a short-exact sequence then i is injective and j is surjective, we also have the condition that im(i) = ker(j).

    Let B' be an isomorphic group to B with isomorphism $f:B\to B^{\prime}$. Imagine the following diagram. Under B put B' and extend a morphism from B to B' to be your f. Now extend arrows from A to B' (called i') and from B' to C (called j') in such a way such that the resulting diagram is commutative. Because this diagram is assumed to be commutative we have that i'=fi and j'=jf* (where f* is the inverse mapping $f^{-1}$). The resulting sequence:

    0 --> A --> B' --> C --> 0

    Is short-exact. The fact that i' is injective follows from the fact that it is a composition of injective functions and the fact that j' is surjective follows from the fact that it is a composition of surjective functions. So it just remains to show that im(i')=ker(j'). But this is also easy, just follow the definitions. For example, if you want to show im(i') is contained in ker(j') just notice that j'i'=0, because j'=jf*, i'=fi, so that j'i'=jf*fi=ji=0 - because ji=0 for the original one was short-exact. In a similar way one can show im(i) contains ker(j').

    In fact, one can generalize this. If:
    0 -> A -> B -> C -> 0
    Is short-exact and A',B',C' are isomorphic groups, respectively.
    Then we can look at the diagram:

    0 --> A --> B --> C --> 0
    | ... | ... | ... | .... |
    0 --> A' -> B' -> C' --> 0

    Where the arrows from A to A', B to B', C to C' are defined by the isomorphisms. Then we can define the arrow from A' to B' to C' by making the whole diagram commutative. In such a way the resulting sequence will stay short-exact.
    Isomorphisms do not affect properties of these exact-sequences.

  3. Never thought of it that way, thanks. I can't think of what I'm blind to as a logician, except of course social sense.

  4. "Never thought of it that way, thanks. I can't think of what I'm blind to as a logician, except of course social sense.":

    As a logician you are probably blind to equipotent sets. If two sets A and B are equipotent, i.e. there is a bijective map f from A onto B then for all set-theoretic properties these sets are the same. So for example, if you want to put a well-ordering on B given that you have a well-ordering on A. If < is a well-ordering on A then we can define a < b iff f(a) <' f(b). Then it is easy to see that <', the obtained relation from < under f, is a well-ordering of B.

    Here is a good intuitive way of thinking of isomorphisms. Consider the US and Soviet Russia. In the US kids learn to count to ten using English. In Soviet Russia, kids learn to count to ten using Russian. But the arithmetic that results from English and Russian is identical. The names are different, that is all, but the structure is identical.