## Thursday, 8 October 2009

### Symmetries of PG(n,Fq)

Previously in this blog we looked at the affine geometries AG(n,Fq), and their symmetries. Following that, we looked at the points and lines in the projective geometries PG(n,Fq). This week I want to look at the symmetries of PG(n,Fq).

However, first, something I forgot to mention last week. When we looked at the points in PG(n,Fq), we saw that they can be thought of as the points of AG(n,Fq), plus some additional points "at infinity". What I forgot to do last week was to discuss how the lines in PG(n,Fq) relate to the lines in AG(n,Fq).

Here's PG(2,F3) again:

Recall that the points in PG(2,F3) are (by definition) the lines through the origin in F3^3, each of which can be represented, as here, by one of the non-zero points on it. (Note that for technical reasons, the coordinates are shown as zyx instead of xyz.) We see that these "points" of PG(2,F3) consist of something looking very much like AG(2,F3) - the blue points - together with some additional points, which are said to be "at infinity".

Then, the lines of PG(2,F3) are (by definition) the planes through 0 in F3^3. What is the relationship between lines in AG(2,F3) and "lines" in PG(2,F3)? Well, any line in (the copy of) AG(2,F3) (embedded in PG(2,F3)) is contained in a plane through 0 in F3^3. So each line in AG(2,F3) gives rise to a line in PG(2,F3). In PG(2,F3), however, the line will have an additional point "at infinity".

For example, there is a line in AG(2,F3) consisting of the points {(0,0),(1,0),(2,0)}. These embed into PG(2,F3) as {(1:0:0), (1:1:0), (1:2:0)}. We can ask what is the closure in PG(2,F3) of these points - the least "flat" (point, line, plane, etc) that contains them:

`> closurePG [ [1,0,0],[1,1,0],[1,2,0] ] :: [[F3]]`
`[[0,1,0],[1,0,0],[1,1,0],[1,2,0]]`

So in PG(2,F3), the line gains a point at infinity, (0:1:0).

Similarly, there is a line in AG(2,F3) consisting of the points {(0,1),(1,1),(2,1)}. These embed into PG(2,F3) as {(1:0:1), (1:1:1), (1:2:1)}.

`> closurePG [ [1,0,1],[1,1,1],[1,2,1] ] :: [[F3]]`
`[[0,1,0],[1,0,1],[1,1,1],[1,2,1]]`

Notice that both lines from AG(2,F3) gained the same point at infinity. This is because the two lines were parallel. In PG(2,F3), "parallel lines meet at infinity".

So each line in AG(2,F3) extends to a line in PG(2,F3), gaining an extra point at infinity. In addition to these lines, there is one more line in PG(2,F3) - a line at infinity consisting of the points {(0:0:1), (0:1:0), (0:1:1), (0:1:2)}, corresponding to the plane z = 0 in F3^3.

So, that was all stuff that I should really have talked about last time, but I forgot.

--*--

Okay, so back to the symmetries of PG(n,Fq). So we consider PG(n,Fq) as an incidence structure between points and lines, and we ask which permutations of the points preserve collinearity. That is, given a permutation g of the points of PG(n,Fq), we say that it is a symmetry (or automorphism, or collineation) of PG(n,Fq) if, whenever a and b are collinear points, then so are a^g and b^g, and vice versa.

We can find the symmetries of PG(n,Fq) by forming its incidence graph. This is the bipartite graph having as vertices: the points of PG(n,Fq) on the left (or in blue), the lines of PG(n,Fq) on the right (or in red), with an edge joining a point vertex to a line vertex if the point is incident with the line.

Here's the code:

`incidenceGraphPG n fq = G vs es where`
` points = ptsPG n fq`
` lines = linesPG n fq`
` vs = L.sort \$ map Left points ++ map Right lines`
` es = L.sort [ [Left x, Right b] | b <- lines, x <- closurePG b]`

Let's look at an example. Here's PG(2,F2):

The lines in PG(2,F2), corresponding to planes through 0 in F2^3, are:

`> mapM_ (print . closurePG) \$ linesPG 2 f2`
`[[0,1,0],[1,0,0],[1,1,0]]`
`[[0,1,1],[1,0,0],[1,1,1]]`
`[[0,1,0],[1,0,1],[1,1,1]]`
`[[0,1,1],[1,0,1],[1,1,0]]`
`[[0,0,1],[1,0,0],[1,0,1]]`
`[[0,0,1],[1,1,0],[1,1,1]]`
`[[0,0,1],[0,1,0],[0,1,1]]`

PG(2,F2) is called the Fano plane, and is often represented by the picture below:

You can easily check that this is right. Notice the embedded AG(2,F2) in the bottom left, with parallel lines meeting "at infinity" as expected.

The incidence graph of the Fano plane is called the Heawood graph, and it is often represented like this:

The blue vertices are the points of the Fano plane, the red vertices are the lines. For each red vertex, you can check that the three blue vertices it is connected to are indeed a line of the Fano plane.

Then we can find the automorphisms of the Fano plane as follows:

`> let heawood = incidenceGraphPG 2 f2`
`> let auts = incidenceAuts heawood`
`> mapM_ print auts`
`[[[0,0,1],[0,1,0]],[[1,0,1],[1,1,0]]]`
`[[[0,0,1],[0,1,1],[0,1,0]],[[1,0,1],[1,1,1],[1,1,0]]]`
`[[[0,0,1],[1,0,0],[0,1,0]],[[0,1,1],[1,0,1],[1,1,0]]]`
`[[[0,1,0],[0,1,1]],[[1,1,0],[1,1,1]]]`
`[[[0,1,0],[1,0,0]],[[0,1,1],[1,0,1]]]`
`[[[0,1,0],[1,1,0],[1,0,0]],[[0,1,1],[1,1,1],[1,0,1]]]`
`[[[1,0,0],[1,0,1]],[[1,1,0],[1,1,1]]]`
`[[[1,0,0],[1,1,0]],[[1,0,1],[1,1,1]]]`
`> orderSGS auts`
`168`

Now the symmetries of PG(n,Fq) actually have a very simple description in terms of matrices. Consider the invertible matrices of degree n+1 over Fq - the general linear group GL(n+1,Fq). These matrices act on vectors in Fq^(n+1) by multiplication, and in doing so, they permute the lines and planes through 0 in Fq^(n+1), whilst preserving containment of lines within planes. In other words, they permute the points and lines of PG(n,Fq) and preserve collinearity. However, any scalar matrix within GL(n+1,Fq) - that is, kI, where k is in Fq\{0} and I is the identity - acts as the identity on PG(n,Fq) - since if (x0:x1:...:xn) is a "point" of PG(n,Fq), then (kx0:kx1:...:kxn) represents the same point. So the group of projective transformations of PG(n,Fq) is actually GL(n+1,Fq) factored out by scalar multiplications. This group is called the projective general linear group, PGL(n+1,Fq).

If we are given a symmetry of PG(n,Fq), expressed as a permutation, then we can express it as a matrix by looking at what it does to the basis vectors. For example, consider the symmetry [[[0,0,1],[0,1,0]],[[1,0,1],[1,1,0]]] of PG(2,F2) from above. It sends [1,0,0] to [1,0,0], [0,1,0] to [0,0,1], and [0,0,1] to [0,1,0]. So it can be represented by the matrix
`[1 0 0]`
`[0 0 1]`
`[0 1 0]`

We already worked out the order of GL(n,Fq) in the orderGL function. There are q-1 non-zero scalars to factor out by. So the order of PGL(n,Fq) will be given by the following:

`orderPGL n q = orderGL n q `div` (q-1)`

Let's test it (remembering that we want PGL(n+1,Fq) for PG(n,Fq)):

`> orderPGL 3 2`
`168`
`> orderSGS \$ incidenceAuts \$ incidenceGraphPG 2 f3`
`5616`
`> orderPGL 3 3`
`5616`
`> orderSGS \$ incidenceAuts \$ incidenceGraphPG 2 f4`
`120960`
`> orderPGL 3 4`
`60480`

With F4, we get twice as many automorphisms as we might have expected. If you've been paying attention, you'll remember that this is because F4 has a field automorphism (the Frobenius automorphism) of order 2. The extended group, PGL(n,Fq) plus field automorphisms, is called PGammaL(n,Fq) (or better - but I'm not sure this will work for everybody - PΓL(n,Fq)).

Now, this is kind of a trivial point, but I think it's significant: PG(n,Fq) has more symmetries than AG(n,Fq). Somehow, by adding the points at infinity, PG(n,Fq) has made AG(n,Fq) "whole", making it more symmetrical.

Anyway, that'll do for now. Next week, just a few more odds and ends about finite geometries.