Finite geometries, part 4: Lines in PG(n,Fq)

[Apologies about the formatting - blogger seems to have won the struggle this time.]

Last time we saw that the points in the projective geometry PG(n,Fq) are defined to be the lines (through the origin) in the vector space Fq^(n+1). What about lines in PG(n,Fq)? Well, it's simple - they are defined as the planes (through 0) in Fq^(n+1).

Let's look at an example, to try to clarify our intuitions. Here are the points of PG(2,F3) again.




> :load Math.Combinatorics.FiniteGeometry

> ptsPG 2 f3

[[0,0,1],[0,1,0],[0,1,1],[0,1,2],[1,0,0],[1,0,1],[1,0,2],[1,1,0],[1,1,1],[1,1,2],[1,2,0],[1,2,1],[1,2,2]]

(Recall that each point in PG(2,F3) represents a line through 0 in F₃³. We have chosen the representative which has 1 as its first non-zero coordinate. This has the consequence that the coordinates in the diagram are best read back-to-front - they're zyx instead of xyz.)

So the lines in PG(2,F3) correspond to the planes through 0 in F₃³. For example, the plane x = 0 (the left hand face of the cube) gives rise to a line in PG(2,F3) containing the points 010, 100, 110, 120. The plane x = z (a diagonal cut through the cube from front left to back right) gives rise to the line containing the points 010, 101, 111, 121. Just to be clear, we are only looking at the planes in F₃³ that contain 0. So for example, 012, 101, 111, 121 - the plane x+z=2 - is not a line in PG(2,F3). Also, remember that F₃ wraps around - so for example 010, 102, 112, 122 is a line in PG(2,F3).

Okay, onwards. As we did with AG(n,Fq), we can represent a line in PG(n,Fq) by any pair of points on it. We would then like to be able to do the following:

1. Given a line of PG(n,Fq), list the points of PG(n,Fq) which are on it
2. Given a line of PG(n,Fq), find a canonical representation for it
3. Find all lines of PG(n,Fq)

(These are basically just the same things that we did when we looked at AG(n,Fq) a couple of weeks back.)

Okay, so suppose that we are given two distinct points of PG(n,Fq), representing a line, and we are asked to list all the points of PG(n,Fq) that are on the line. Well, the two points are also points in F_qⁿ⁺¹, and as they are distinct in PG(n,Fq), they are linearly independent in F_qⁿ⁺¹ - hence they generate a plane through 0. We are being asked to find all lines through 0 that are contained in the plane. Well, that's easy:

1. Generate all linear combinations of the two points - all points in the plane in F_qⁿ⁺¹.
2. Each non-zero point in the plane represents a line through 0, and hence a point of PG(n,Fq)
3. However, we can filter out all except those that are in the canonical form for pts of PG(n,Fq) - having a 1 as their first non-zero coordinate - in order to avoid double counting the lines.

So we need an auxiliary function to detect whether a point is in canonical form - what I call "projective normal form" or PNF:




ispnf (0:xs) = ispnf xs

ispnf (1:xs) = True

ispnf _ = False

Then, given two distinct points, to list all points on the line they generate:

linePG [p1,p2] = toListSet $ filter ispnf [(a *> p1) <+> (b *> p2) | a <- fq, b <- fq]
    where fq = eltsFq undefined

(Recall that c *> v is scalar multiplication of a vector, and u <+> v is addition of vectors. Note that in HaskellForMaths <= 0.1.9, you must use the more general "closurePG" function instead, which has the same behaviour.)

For example, here are the two lines of PG(2,F3) that we discussed earlier:

> linePG [[0,1,0],[1,0,0]] :: [[F3]]

[[0,1,0],[1,0,0],[1,1,0],[1,2,0]]

> linePG [[0,1,0],[1,0,1]] :: [[F3]]

[[0,1,0],[1,0,1],[1,1,1],[1,2,1]]

A line in PG(n,Fq) can be represented by any pair of distinct points on the line. Is there a canonical pair to pick? Yes, there is. Given any pair of points of PG(n,Fq), we can consider them as the rows of a matrix. Any matrix which can be obtained from this matrix by elementary row operations represents the same plane in F_qⁿ⁺¹. For our canonical form, we can take the reduced row echelon form for the matrix (see wikipedia). However, I'm not going to dwell on this - use the "reducedRowEchelonForm" function if you'd like to experiment.

What I'd like to consider instead is how we can list all the lines in PG(n,Fq). The answer is simply to list all the reduced row echelon forms. We can do this in two steps:

1. List all the reduced row echelon "shapes"
2. Fill in all possible combinations of values from Fq, to get all reduced row echelon forms

An example will make this clearer. Suppose we want to find the lines in PG(3,Fq). Thus we are looking for the 2-dimensional subspaces of Fq^4. The reduced row echelon shapes are the following:

[1 0 * *]                   [1 * 0 *]                   [1 * * 0]
[0 1 * *]                   [0 0 1 *]                   [0 0 0 1]

[0 1 0 *]                   [0 1 * 0]                   [0 0 1 0]
[0 0 1 *]                   [0 0 0 1]                   [0 0 0 1]

To get the reduced row echelon forms, we take each shape in turn, and fill in the stars with the values from Fq in all possible ways.

The Haskell code finds row echelon shapes for k-dimensional subspaces of Fq^n. (For lines, set k = 2):

data ZeroOneStar = Zero | One | Star deriving (Eq)

instance Show ZeroOneStar where
   show Zero = "0"
   show One  = "1"
   show Star = "*"

rrefs n k = map (rref 1 1) (combinationsOf k [1..n]) where
   rref r c (x:xs) =
       if c == x
       then zipWith (:) (oneColumn r) (rref (r+1) (c+1) xs)
       else zipWith (:) (starColumn r) (rref r (c+1) (x:xs))
   rref _ c [] = replicate k (replicate (n+1-c) Star)
   oneColumn r = replicate (r-1) Zero ++ One : replicate (k-r) Zero
   starColumn r = replicate (r-1) Star ++ replicate (k+1-r) Zero

Thus we can calculate the shapes we saw above as follows:


> mapM_ print $ rrefs 4 2
[[1,0,*,*],[0,1,*,*]]
[[1,*,0,*],[0,0,1,*]]
[[1,*,*,0],[0,0,0,1]]
[[0,1,0,*],[0,0,1,*]]
[[0,1,*,0],[0,0,0,1]]
[[0,0,1,0],[0,0,0,1]]


Next, to find all lines in PG(n,Fq), we need to substitute values from Fq for the stars. The following code does the trick, although I suspect that there might be a better way to write it:

flatsPG n fq k = concatMap substStars $ rrefs (n+1) (k+1) where
   substStars (r:rs) = [r':rs' | r' <- substStars' r, rs' <- substStars rs]
   substStars [] = [[]]
   substStars' (Star:xs) = [x':xs' | x' <- fq, xs' <- substStars' xs]
   substStars' (Zero:xs) = map (0:) $ substStars' xs
   substStars' (One:xs) = map (1:) $ substStars' xs
   substStars' [] = [[]]

linesPG n fq = flatsPG n fq 1 

For example:


> mapM_ print $ linesPG 2 f3
[[1,0,0],[0,1,0]]
[[1,0,0],[0,1,1]]
[[1,0,0],[0,1,2]]
[[1,0,1],[0,1,0]]
[[1,0,1],[0,1,1]]
[[1,0,1],[0,1,2]]
[[1,0,2],[0,1,0]]
[[1,0,2],[0,1,1]]
[[1,0,2],[0,1,2]]
[[1,0,0],[0,0,1]]
[[1,1,0],[0,0,1]]
[[1,2,0],[0,0,1]]
[[0,1,0],[0,0,1]]


It occurs to me that I should explain why PG(n,Fq) is worth looking at. Well, I mentioned before that the symmetry groups of PG(n,Fq) are some of the "atoms of symmetry", from which all symmetry groups are composed. In addition, projective geometry is in fact more fundamental than affine geometry (at least from the point of view of algebraic geometry, although I'm not sure how you would justify that statement in general). Well, maybe you'll just have to take my word for it that PG(n,Fq) is a beautiful thing, for the moment.

Next time, symmetries of PG(n,Fq).