Ch.5: Finite geometry
Chapter 5 of the book "Matroids: A Geometric Introduction" by Gary Gordon and Jennifer McNulty (2012) 5.1. Finite geometry 5.2. Affine geometry and affine dependence 5.3. Affine dependence 5.4. The projective plane PG(2, q) 5.5. Projective geometry 5.6. Counting k-flats and q-binomials 5.7. Abstract projective planes
125 flashcards · Mathematics · by lakesare
Part of Textbooks › Matroids: A Geometric Introduction (Gordon, McNulty) · 9 courses
[Finite geometry] Which two properties of points and lines in the Euclidean plane motivate affine geometry?
Two points determine a line Every pair of points determines a unique line. Example: (0,0)(0, 0)(0,0) and (1,1)(1, 1)(1,1) lie on exactly one line, y=xy = xy=x . Parallel postulate Given a point PPP and a line lll not containing PPP , there is a unique line through PPP parallel to lll . Example: through (0,1)(0, 1)(0,1) , the only line parallel to y=0y = 0y=0 is y=1y = 1y=1 .
[Finite geometry] Why is this drawing not a matroid?
The two points a,ba, ba,b lie on two different lines ( abcabcabc and abdabdabd ), but in a matroid two non-parallel points determine a unique rank 2 flat. In rank terms: r(abc)=2r(abc) = 2r(abc)=2 and r(abd)=2r(abd) = 2r(abd)=2 force r(abcd)=2r(abcd) = 2r(abcd)=2 , so a,b,c,da, b, c, da,b,c,d would have to lie on one line.
[Finite geometry] In a matroid, r(abc)=2r(abc) = 2r(abc)=2 and r(abd)=2r(abd) = 2r(abd)=2 , with {a,b}\{a, b\}{a,b} independent.Why does r(abcd)≥3r(abcd) \ge 3r(abcd)≥3 give a contradiction?
Augmentation (I3): augmenting I={a,b}I = \{a, b\}I={a,b} from an independent 3-set J⊆abcdJ \subseteq abcdJ⊆abcd adds ccc or ddd , so abcabcabc or abdabdabd would be independent. The book takes J={a,c,d}J = \{a, c, d\}J={a,c,d} . Both abcabcabc and abdabdabd have rank 2, so neither is independent.
[Finite geometry] What is the history of the parallel postulate?
Euclid stated it as an axiom (his fifth); all attempts to prove it from his other four axioms failed. The failed proofs led to valid geometries in which the parallel postulate does not hold, such as the projective plane.
[Finite geometry] Why do affine and projective geometry matter for matroid theory?
They are the setting for all representable matroids, i.e. matroids defined on the columns of a matrix. Also, projective planes are themselves matroids.
[Affine geometry and affine dependence] In the affine plane over {0,1,2}\{0, 1, 2\}{0,1,2} (arithmetic mod 3), what are the points and what are the lines?
Points: the 9 ordered pairs (x,y)(x, y)(x,y) with x,y∈{0,1,2}x, y \in \{0, 1, 2\}x,y∈{0,1,2} . Lines: the solution sets of ax+by=cax + by = cax+by=c , with a,b,c∈{0,1,2}a, b, c \in \{0, 1, 2\}a,b,c∈{0,1,2} and a,ba, ba,b not both 0. P1=(0,0)P_1 = (0, 0)P1=(0,0) , P2=(0,1)P_2 = (0, 1)P2=(0,1) , ..., P9=(2,2)P_9 = (2, 2)P9=(2,2) .
[Affine geometry and affine dependence] Working mod 3, which points (x,y)(x, y)(x,y) with x,y∈{0,1,2}x, y \in \{0, 1, 2\}x,y∈{0,1,2} lie on the line x+2y=1x + 2y = 1x+2y=1 ?
(1,0), (0,2), (2,1)\boldsymbol{(1, 0), \ (0, 2), \ (2, 1)}(1,0), (0,2), (2,1) 1+0=11 + 0 = 11+0=1 , 0+4≡1\ 0 + 4 \equiv 1 0+4≡1 , 2+2=4≡1(mod3)\ 2 + 2 = 4 \equiv 1 \pmod 3 2+2=4≡1(mod3) .
[Affine geometry and affine dependence] The lines of the affine plane over {0,1,2}\{0, 1, 2\}{0,1,2} (mod 3) are the solution sets of ax+by=cax + by = cax+by=c . How many lines are there, and how do you count them?
12 lines: 9 with a≠0a \ne 0a=0 (divide by aaa : x+b′y=c′x + b'y = c'x+b′y=c′ , 3 choices each for b′b'b′ , c′c'c′ ) and 3 with a=0a = 0a=0 (divide by bbb : y=c′y = c'y=c′ ). The 9 points and 12 lines of AG(2,3)AG(2, 3)AG(2,3) .
[Affine geometry and affine dependence] What do the parts of the notation AG(2,3)AG(2, 3)AG(2,3) mean?
AGAGAG = affine geometry, 2 = dimension (a plane), 3 = the field F3\mathbb{F}_3F3 (computations mod 3). AG(2,3)AG(2, 3)AG(2,3) is the 9 points of {0,1,2}2\{0, 1, 2\}^2{0,1,2}2 with the 12 lines ax+by=cax + by = cax+by=c . In it, two points determine a unique line, and the parallel postulate holds.
[Affine geometry and affine dependence] What is a field?
A set closed under commutative addition and multiplication, obeying the distributive law, in which every element except 0 has a multiplicative inverse. Example: Q\mathbb{Q}Q , R\mathbb{R}R , C\mathbb{C}C are fields; the integers Z\mathbb{Z}Z are not, since 222 has no inverse in Z\mathbb{Z}Z .
[Affine geometry and affine dependence] For which nnn is {0,1,…,n−1}\{0, 1, \dots, n - 1\}{0,1,…,n−1} with addition and multiplication mod nnn a field?
Exactly when nnn is prime; this field is written Fp\mathbb{F}_pFp . Example: in Z4\mathbb{Z}_4Z4 , 2⋅1=22 \cdot 1 = 22⋅1=2 , 2⋅2=02 \cdot 2 = 02⋅2=0 , 2⋅3=22 \cdot 3 = 22⋅3=2 , so 2 has no multiplicative inverse.
[Affine geometry and affine dependence] Which sizes can a finite field have, and how many fields of each size exist?
∣F∣=pn|\mathbb{F}| = p^n∣F∣=pn for a prime ppp and n≥1n \ge 1n≥1 , and there is exactly one field (up to isomorphism) of each such size. It is written Fq\mathbb{F}_qFq , q=pnq = p^nq=pn .Example: fields with 2, 3, 4, 5, 7, 8, 9 elements exist; none with 6 or 10.
[Affine geometry and affine dependence] q=pnq = p^nq=pn with ppp prime and n>1n > 1n>1 . Is Fq\mathbb{F}_qFq the same as Zq\mathbb{Z}_qZq (arithmetic mod qqq )?
No. Zq\mathbb{Z}_qZq is not a field; Fq\mathbb{F}_qFq needs a different construction. Example: Z4\mathbb{Z}_4Z4 is not a field (2 has no inverse), but the field F4\mathbb{F}_4F4 exists.
[Affine geometry and affine dependence] How is the field Fq\mathbb{F}_qFq , q=pnq = p^nq=pn ( ppp prime, n>1n > 1n>1 ), constructed?
Fq=Fp[x]/⟨f(x)⟩\mathbb{F}_q = \mathbb{F}_p[x] / \langle f(x) \rangleFq=Fp[x]/⟨f(x)⟩ for an irreducible polynomial f(x)∈Fp[x]f(x) \in \mathbb{F}_p[x]f(x)∈Fp[x] of degree nnn . ⟨f(x)⟩\langle f(x) \rangle⟨f(x)⟩ is a maximal ideal, so the quotient is a field. It is an nnn -dimensional vector space over Fp\mathbb{F}_pFp .Example: x2+x+1x^2 + x + 1x2+x+1 has no root in F2\mathbb{F}_2F2 , so F4=F2[x]/⟨x2+x+1⟩={0,1,x,x+1}\mathbb{F}_4 = \mathbb{F}_2[x] / \langle x^2 + x + 1 \rangle = \{0, 1, x, x +…
[Affine geometry and affine dependence] What is the characteristic of a field F\mathbb{F}F ?
The smallest m≥1m \ge 1m≥1 with 1+1+⋯+1undefinedm=0\underbrace{1 + 1 + \dots + 1}_{m} = 0m1+1+⋯+1=0 in F\mathbb{F}F ; it is 0 if no such mmm exists. Example: in F3\mathbb{F}_3F3 , 1+1+1=01 + 1 + 1 = 01+1+1=0 , so the characteristic is 3.Example: Q\mathbb{Q}Q , R\mathbb{R}R , C\mathbb{C}C have characteristic 0.
[Affine geometry and affine dependence] Which numbers occur as the characteristic of a field? What is the characteristic of Fq\mathbb{F}_qFq , q=pkq = p^kq=pk ?
Every prime, and 0: {0,2,3,5,7,11,… }\{0, 2, 3, 5, 7, 11, \dots\}{0,2,3,5,7,11,…} . Fpk\mathbb{F}_{p^k}Fpk has characteristic ppp . If m=abm = abm=ab with 1<a,b<m1 < a, b < m1<a,b<m , then (a⋅1)(b⋅1)=0(a \cdot 1)(b \cdot 1) = 0(a⋅1)(b⋅1)=0 , so a⋅1=0a \cdot 1 = 0a⋅1=0 or b⋅1=0b \cdot 1 = 0b⋅1=0 , contradicting minimality of mmm .Example: F4\mathbb{F}_4F4 and F8\mathbb{F}_8F8 have characteristic 2.
[Affine geometry and affine dependence] What is a vector space VVV over a field F\mathbb{F}F ?
A set of vectors closed under addition and under multiplication by scalars from F\mathbb{F}F , satisfying the usual axioms. Addition is commutative and associative, there is a zero vector and additive inverses, 1v=v1v = v1v=v , (ab)v=a(bv)(ab)v = a(bv)(ab)v=a(bv) , a(u+v)=au+ava(u + v) = au + ava(u+v)=au+av , (a+b)v=av+bv(a + b)v = av + bv(a+b)v=av+bv .Example: Fn\mathbb{F}^nFn , the nnn -tuples over any field F\mathbb{F}F , including finite fields; F23\mathbb{F}_2^3F23 has 8 vectors.
[Affine geometry and affine dependence] When is a subset WWW of a vector space VVV a subspace, and what is the subspace generated by S={v1,…,vk}S = \{v_1, \dots, v_k\}S={v1,…,vk} ?
WWW is a subspace iff W≠∅W \ne \emptysetW=∅ and WWW is closed under addition and scalar multiplication. SSS generates {∑i=1kaivi∣ai∈F}\{\sum_{i=1}^k a_i v_i \mid a_i \in \mathbb{F}\}{∑i=1kaivi∣ai∈F} . Every subspace contains 000 .Example: over F2\mathbb{F}_2F2 , {(1,1,0)}\{(1, 1, 0)\}{(1,1,0)} generates {(0,0,0),(1,1,0)}\{(0, 0, 0), (1, 1, 0)\}{(0,0,0),(1,1,0)} .
[Affine geometry and affine dependence] What do linearly independent, spanning, basis and dimension mean for vectors in a vector space VVV ?
Linearly independent ∑aivi=0\sum a_i v_i = 0∑aivi=0 only when all ai=0a_i = 0ai=0 . Spanning SSS spans a subspace WWW if every vector of WWW is a linear combination of vectors in SSS . Basis A linearly independent spanning set. All bases of VVV have the same number of vectors. Dimension The number of vectors in a basis of VVV . Example: (1,0,0),(0,1,0),(0,0,1)(1, 0, 0), (0, 1, 0), (0, 0, 1)(1,0,0),(0,1,0),(0,0,1) is a basis of Fq3\mathbb{F}_q^3Fq3 , so dimFq3=3\dim \mathbb{F}_q^3 = 3dimFq3…
[Affine geometry and affine dependence] W1W_1W1 , W2W_2W2 are subspaces of VVV and W1+W2={u+v∣u∈W1,v∈W2}W_1 + W_2 = \{u + v \mid u \in W_1, v \in W_2\}W1+W2={u+v∣u∈W1,v∈W2} . How are dimW1\dim W_1dimW1 , dimW2\dim W_2dimW2 , dim(W1+W2)\dim(W_1 + W_2)dim(W1+W2) and dim(W1∩W2)\dim(W_1 \cap W_2)dim(W1∩W2) related?
dimW1+dimW2=dim(W1+W2)+dim(W1∩W2)\boldsymbol{\dim W_1 + \dim W_2 = \dim(W_1 + W_2) + \dim(W_1 \cap W_2)}dimW1+dimW2=dim(W1+W2)+dim(W1∩W2) W1∩W2W_1 \cap W_2W1∩W2 and W1+W2W_1 + W_2W1+W2 are subspaces too.Example: in F23\mathbb{F}_2^3F23 , W1={z=0}W_1 = \{z = 0\}W1={z=0} , W2={y=0}W_2 = \{y = 0\}W2={y=0} : 2+2=3+12 + 2 = 3 + 12+2=3+1 , since W1∩W2W_1 \cap W_2W1∩W2 is generated by (1,0,0)(1, 0, 0)(1,0,0) .
[Affine geometry and affine dependence] WWW is a subspace of V=FnV = \mathbb{F}^nV=Fn . What is W⊥W^\perpW⊥ , and what are dimW+dimW⊥\dim W + \dim W^\perpdimW+dimW⊥ and (W⊥)⊥(W^\perp)^\perp(W⊥)⊥ ?
W⊥={v∣w⋅v=0W^\perp = \{v \mid w \cdot v = 0W⊥={v∣w⋅v=0 for all w∈W}w \in W\}w∈W} ; dimW+dimW⊥=dimV\dim W + \dim W^\perp = \dim VdimW+dimW⊥=dimV , and (W⊥)⊥=W(W^\perp)^\perp = W(W⊥)⊥=W . w⋅v=w1v1+⋯+wnvnw \cdot v = w_1 v_1 + \dots + w_n v_nw⋅v=w1v1+⋯+wnvn , the usual dot product.Example: in F23\mathbb{F}_2^3F23 , WWW generated by (1,1,0)(1, 1, 0)(1,1,0) gives W⊥={x+y=0}={000,110,001,111}W^\perp = \{x + y = 0\} = \{000, 110, 001, 111\}W⊥={x+y=0}={000,110,001,111} ; 1+2=31 + 2 = 31+2=3 .
[Affine geometry and affine dependence] Which three subspaces belong to an m×nm \times nm×n matrix AAA over F\mathbb{F}F ?
Row space R(A)R(A)R(A) The subspace of Fn\mathbb{F}^nFn generated by the rows of AAA . Column space C(A)C(A)C(A) The subspace of Fm\mathbb{F}^mFm generated by the columns of AAA . Null space (kernel) N(A)N(A)N(A) N(A)={v∈Fn∣Av=0}N(A) = \{v \in \mathbb{F}^n \mid Av = 0\}N(A)={v∈Fn∣Av=0} , a subspace of Fn\mathbb{F}^nFn . Example: over F2\mathbb{F}_2F2 , A=[110011]A = \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \end{bmatrix}A=[101101] has N(A)={(0,0,0),(1,1,1)}N(A) = \{(0, 0, 0), (1, 1, 1)\}N(A)={…
[Affine geometry and affine dependence] AAA is an m×nm \times nm×n matrix with row space R(A)R(A)R(A) , column space C(A)C(A)C(A) and null space N(A)N(A)N(A) . Which three facts relate these?
Null space = orthogonal complement of row space N(A)=R(A)⊥N(A) = R(A)^\perpN(A)=R(A)⊥ , since Av=0Av = 0Av=0 says exactly that every row of AAA has dot product 0 with vvv . Row rank = column rank dimR(A)=dimC(A)\dim R(A) = \dim C(A)dimR(A)=dimC(A) . Rank–Nullity Theorem dimR(A)+dimN(A)=n\dim R(A) + \dim N(A) = ndimR(A)+dimN(A)=n . Example: over F2\mathbb{F}_2F2 , A=[110011]A = \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \end{bmatrix}A=[101101] : dimR(A)=2\dim R(A) = 2dimR(A)=2 , N(A)={000,1…
[Affine geometry and affine dependence] Definition 5.2. Let q=pkq = p^kq=pk , ppp prime. What are the points and lines of the affine plane AG(2,q)AG(2, q)AG(2,q) ?
Points: the q2q^2q2 ordered pairs (x,y)(x, y)(x,y) , x,y∈Fqx, y \in \mathbb{F}_qx,y∈Fq . Lines: the sets of points satisfying ax+by=cax + by = cax+by=c , a,b,c∈Fqa, b, c \in \mathbb{F}_qa,b,c∈Fq ( a,ba, ba,b not both 0). The coordinates must come from a field, so qqq is a prime power.
[Affine geometry and affine dependence] How many lines does AG(2,q)AG(2, q)AG(2,q) (the affine plane over Fq\mathbb{F}_qFq ) have, and how many points are on each line?
q2+qq^2 + qq2+q lines, each with exactly qqq points. q2q^2q2 lines x+b′y=c′x + b'y = c'x+b′y=c′ and qqq lines y=c′y = c'y=c′ .Example: AG(2,3)AG(2, 3)AG(2,3) has 9+3=129 + 3 = 129+3=12 lines of 3 points.
[Affine geometry and affine dependence] What are the points of nnn -dimensional affine space AG(n,q)AG(n, q)AG(n,q) ?
The qnq^nqn ordered nnn -tuples (a1,…,an)(a_1, \dots, a_n)(a1,…,an) with ai∈Fqa_i \in \mathbb{F}_qai∈Fq , i.e. the vectors of Fqn\mathbb{F}_q^nFqn . Example: AG(3,2)AG(3, 2)AG(3,2) has the 23=82^3 = 823=8 points of {0,1}3\{0, 1\}^3{0,1}3 .
[Affine geometry and affine dependence] The 8 points of AG(3,2)AG(3, 2)AG(3,2) are the columns P0P1P2P3P4P5P6P7010011100010110100011011\begin{array}{cccccccc} P_0 & P_1 & P_2 & P_3 & P_4 & P_5 & P_6 & P_7 \\ \hline 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \end{array}P0000P1100P2010P3001P4111P5110P6101P7011 Which points lie on the plane x+y+z=0x + y + z = 0x+y+z=0 (mod 2)?
P0,P5,P6,P7\boldsymbol{P_0, P_5, P_6, P_7}P0,P5,P6,P7 These are the points with an even number of 1's. AG(3,2)AG(3, 2)AG(3,2) drawn as a cube.
[Affine geometry and affine dependence] How many planes does AG(3,2)AG(3, 2)AG(3,2) (the 8 points of {0,1}3\{0, 1\}^3{0,1}3 ) have, and what are they in the matroid?
14 planes, each a 4-point circuit. Each of the 7 two-dimensional subspaces of F23\mathbb{F}_2^3F23 and its one other translate: 7⋅2=147 \cdot 2 = 147⋅2=14 . Every line has only 2 points, so no 3 points are dependent.
[Affine geometry and affine dependence] Definition 5.3. When is F⊆FqnF \subseteq \mathbb{F}_q^nF⊆Fqn a flat of AG(n,q)AG(n, q)AG(n,q) ?
When F=u+W={u+w∣w∈W}F = u + W = \{u + w \mid w \in W\}F=u+W={u+w∣w∈W} for a subspace WWW and a vector uuu ; also F=∅F = \emptysetF=∅ is a flat. Flats are translates of subspaces. Its dimension is dim(u+W)=dimW\dim(u + W) = \dim Wdim(u+W)=dimW .Example: in AG(2,3)AG(2, 3)AG(2,3) the flats are ∅\emptyset∅ , the 9 points (dimension 0), the 12 lines (dimension 1) and the whole plane (dimension 2).
[Affine geometry and affine dependence] Theorem 5.4. EEE is the set of the qnq^nqn points of AG(n,q)AG(n, q)AG(n,q) , and F\mathcal{F}F is the family of all flats u+Wu + Wu+W of Fqn\mathbb{F}_q^nFqn together with ∅\emptyset∅ . What is F\mathcal{F}F ?
The family of flats of a matroid on EEE . So AG(n,q)AG(n, q)AG(n,q) is a matroid, and its affine flats coincide with its matroid flats.
[Affine geometry and affine dependence] Flat axioms: (F1) E∈FE \in \mathcal{F}E∈F ; (F2) F1,F2∈F⇒F1∩F2∈FF_1, F_2 \in \mathcal{F} \Rightarrow F_1 \cap F_2 \in \mathcal{F}F1,F2∈F⇒F1∩F2∈F ; (F3) if F∈FF \in \mathcal{F}F∈F and F1,…,FkF_1, \dots, F_kF1,…,Fk are the flats covering FFF , then F1−F,…,Fk−FF_1 - F, \dots, F_k - FF1−F,…,Fk−F partition E−FE - FE−F .The flats of AG(n,q)AG(n, q)AG(n,q) are ∅\emptyset∅ and the translates u+Wu + Wu+W of subspaces of Fqn\mathbb{F}_q^nFqn . Why do they…
If u∈F1∩F2u \in F_1 \cap F_2u∈F1∩F2 , then F1=u+W1F_1 = u + W_1F1=u+W1 , F2=u+W2F_2 = u + W_2F2=u+W2 , so F1∩F2=u+(W1∩W2)F_1 \cap F_2 = u + (W_1 \cap W_2)F1∩F2=u+(W1∩W2) , a flat because W1∩W2W_1 \cap W_2W1∩W2 is a subspace. If F1∩F2=∅F_1 \cap F_2 = \emptysetF1∩F2=∅ , it is a flat by definition.
[Affine geometry and affine dependence] (F3): if FFF is a flat and F1,…,FkF_1, \dots, F_kF1,…,Fk are the flats covering FFF , then F1−F,…,Fk−FF_1 - F, \dots, F_k - FF1−F,…,Fk−F partition E−FE - FE−F .How does the proof show that the flats of AG(n,q)AG(n, q)AG(n,q) (translates u+Wu + Wu+W of subspaces) satisfy (F3)?
Translate by −u-u−u : F=u+WF = u + WF=u+W and each Fi=u+WiF_i = u + W_iFi=u+Wi become subspaces, with W1,…,WkW_1, \dots, W_kW1,…,Wk the subspaces covering WWW ( dimWi=dimW+1\dim W_i = \dim W + 1dimWi=dimW+1 ). These partition Fqn−W\mathbb{F}_q^n - WFqn−W ; translate back. Each v∉Wv \notin Wv∈/W lies in exactly one covering subspace, the one generated by WWW and vvv .
[Affine geometry and affine dependence] Proposition 5.5 (flat–matrix correspondence). FFF is a flat of AG(n,q)AG(n, q)AG(n,q) of dimension ddd . How can FFF be described by a matrix?
F={y∈Fqn∣Ay=Au}F = \{y \in \mathbb{F}_q^n \mid Ay = Au\}F={y∈Fqn∣Ay=Au} for an (n−d)×n(n - d) \times n(n−d)×n matrix AAA and a vector uuu . As a matroid flat, FFF has rank d+1d + 1d+1 .Example: a line in AG(3,5)AG(3, 5)AG(3,5) ( d=1d = 1d=1 ) is described by a 2×32 \times 32×3 matrix, i.e. two equations.
[Affine geometry and affine dependence] F=u+WF = u + WF=u+W is a flat of AG(n,q)AG(n, q)AG(n,q) with dimW=d\dim W = ddimW=d . What are the steps to find a matrix AAA with F={y∣Ay=Au}F = \{y \mid Ay = Au\}F={y∣Ay=Au} ?
Take a basis of W⊥W^\perpW⊥ (it has n−dn - dn−d vectors) as the rows of AAA . Then N(A)=WN(A) = WN(A)=W , so y∈F ⟺ y−u∈N(A) ⟺ Ay=Auy \in F \iff y - u \in N(A) \iff Ay = Auy∈F⟺y−u∈N(A)⟺Ay=Au . N(A)=R(A)⊥=(W⊥)⊥=WN(A) = R(A)^\perp = (W^\perp)^\perp = WN(A)=R(A)⊥=(W⊥)⊥=W . The process is reversible.
[Affine dependence] In the matroid AG(n,q)AG(n, q)AG(n,q) , which sets of 1, 2, 3, 4 and 5 points are dependent?
No set of 1 or 2 points; 3 points iff collinear; 4 points iff coplanar; 5 points iff they lie in one 3-dimensional flat. This is how matroids are drawn throughout the book ("affine drawings").
[Affine dependence] A set of points of AG(n,q)AG(n, q)AG(n,q) that is dependent in the matroid on Fqn\mathbb{F}_q^nFqn is called affinely dependent.
Example: three collinear points of AG(2,3)AG(2, 3)AG(2,3) , such as (0,0),(1,2),(2,1)(0, 0), (1, 2), (2, 1)(0,0),(1,2),(2,1) .
[Affine dependence] Proposition 5.6. When is S={P0,P1,…,Pk}⊆AG(n,q)S = \{P_0, P_1, \dots, P_k\} \subseteq AG(n, q)S={P0,P1,…,Pk}⊆AG(n,q) affinely dependent?
Iff there are scalars a0,…,ak∈Fqa_0, \dots, a_k \in \mathbb{F}_qa0,…,ak∈Fq , not all 0, with ∑i=0kai=0\displaystyle\sum_{i=0}^k a_i = 0i=0∑kai=0 and ∑i=0kaiPi=0\displaystyle\sum_{i=0}^k a_i P_i = 0i=0∑kaiPi=0 . Example: in AG(2,3)AG(2, 3)AG(2,3) , 1⋅(0,0)+1⋅(1,2)+1⋅(2,1)=(3,3)=(0,0)1 \cdot (0, 0) + 1 \cdot (1, 2) + 1 \cdot (2, 1) = (3, 3) = (0, 0)1⋅(0,0)+1⋅(1,2)+1⋅(2,1)=(3,3)=(0,0) and 1+1+1=01 + 1 + 1 = 01+1+1=0 .
[Affine dependence] Points P0,…,PkP_0, \dots, P_kP0,…,Pk of AG(n,q)AG(n, q)AG(n,q) are given. Which vectors are linearly dependent exactly when the points are affinely dependent?
The kkk vectors vi=Pi−P0v_i = P_i - P_0vi=Pi−P0 , i=1,…,ki = 1, \dots, ki=1,…,k . Four coplanar points give three linearly dependent vectors.
[Affine dependence] P0,…,PkP_0, \dots, P_kP0,…,Pk are affinely dependent iff vi=Pi−P0v_i = P_i - P_0vi=Pi−P0 ( 1≤i≤k1 \le i \le k1≤i≤k ) are linearly dependent.How does this give scalars aia_iai , not all 0, with ∑i=0kai=0\sum_{i=0}^k a_i = 0∑i=0kai=0 and ∑i=0kaiPi=0\sum_{i=0}^k a_i P_i = 0∑i=0kaiPi=0 ?
Expand ∑i=1kbi(Pi−P0)=0\sum_{i=1}^k b_i (P_i - P_0) = 0∑i=1kbi(Pi−P0)=0 and set a0=−(b1+⋯+bk)a_0 = -(b_1 + \dots + b_k)a0=−(b1+⋯+bk) , ai=bia_i = b_iai=bi . ∑bi(Pi−P0)=(−b1−⋯−bk)P0+b1P1+⋯+bkPk\sum b_i (P_i - P_0) = (-b_1 - \dots - b_k) P_0 + b_1 P_1 + \dots + b_k P_k∑bi(Pi−P0)=(−b1−⋯−bk)P0+b1P1+⋯+bkPk . The converse reverses this, using a0=−(a1+⋯+ak)a_0 = -(a_1 + \dots + a_k)a0=−(a1+⋯+ak) .
[Affine dependence] Are (0,0)(0, 0)(0,0) , (1,2)(1, 2)(1,2) , (2,1)(2, 1)(2,1) affinely dependent in AG(2,3)AG(2, 3)AG(2,3) ?
Yes: 1⋅(0,0)+1⋅(1,2)+1⋅(2,1)=(0,0)1 \cdot (0, 0) + 1 \cdot (1, 2) + 1 \cdot (2, 1) = (0, 0)1⋅(0,0)+1⋅(1,2)+1⋅(2,1)=(0,0) and 1+1+1=01 + 1 + 1 = 01+1+1=0 in F3\mathbb{F}_3F3 . They form the line x+y=0x + y = 0x+y=0 .
[Affine dependence] Are Q0=(0,0)Q_0 = (0, 0)Q0=(0,0) , Q1=(1,0)Q_1 = (1, 0)Q1=(1,0) , Q2=(1,2)Q_2 = (1, 2)Q2=(1,2) affinely dependent in AG(2,3)AG(2, 3)AG(2,3) ?
No. aQ0+bQ1+cQ2=(0,0)aQ_0 + bQ_1 + cQ_2 = (0, 0)aQ0+bQ1+cQ2=(0,0) with a+b+c=0a + b + c = 0a+b+c=0 forces a=b=c=0a = b = c = 0a=b=c=0 . The conditions are a+b+c=0a + b + c = 0a+b+c=0 , b+c=0b + c = 0b+c=0 , 2c=02c = 02c=0 .
[Affine dependence] In AG(2,5)AG(2, 5)AG(2,5) , are P=(1,0)P = (1, 0)P=(1,0) , Q=(0,2)Q = (0, 2)Q=(0,2) , R=(3,1)R = (3, 1)R=(3,1) affinely dependent?
Yes: 3P+3Q+4R=(0,0)3P + 3Q + 4R = (0, 0)3P+3Q+4R=(0,0) and 3+3+4≡0(mod5)3 + 3 + 4 \equiv 0 \pmod 53+3+4≡0(mod5) . 3P+3Q+4R=(3+0+12, 0+6+4)=(15,10)≡(0,0)3P + 3Q + 4R = (3 + 0 + 12, \ 0 + 6 + 4) = (15, 10) \equiv (0, 0)3P+3Q+4R=(3+0+12, 0+6+4)=(15,10)≡(0,0) .
[Affine dependence] Proposition 5.8 (bookkeeping trick). For x∈Fqnx \in \mathbb{F}_q^nx∈Fqn let x′=(1,x1,…,xn)∈Fqn+1x' = (1, x_1, \dots, x_n) \in \mathbb{F}_q^{n+1}x′=(1,x1,…,xn)∈Fqn+1 . When are v1,…,vmv_1, \dots, v_mv1,…,vm affinely dependent in Fqn\mathbb{F}_q^nFqn ?
Iff v1′,…,vm′v_1', \dots, v_m'v1′,…,vm′ are linearly dependent in Fqn+1\mathbb{F}_q^{n+1}Fqn+1 . Example: P=(1,0)P = (1, 0)P=(1,0) , Q=(0,2)Q = (0, 2)Q=(0,2) , R=(3,1)R = (3, 1)R=(3,1) over F5\mathbb{F}_5F5 become (1,1,0)(1, 1, 0)(1,1,0) , (1,0,2)(1, 0, 2)(1,0,2) , (1,3,1)(1, 3, 1)(1,3,1) , and 3P′+3Q′+4R′=(0,0,0)3P' + 3Q' + 4R' = (0, 0, 0)3P′+3Q′+4R′=(0,0,0) .
[Affine dependence] For x∈Fqnx \in \mathbb{F}_q^nx∈Fqn , x′=(1,x1,…,xn)x' = (1, x_1, \dots, x_n)x′=(1,x1,…,xn) . Claim: v1,…,vmv_1, \dots, v_mv1,…,vm are affinely dependent iff v1′,…,vm′v_1', \dots, v_m'v1′,…,vm′ are linearly dependent.Why does the claim hold?
The first coordinate of ∑aivi′\sum a_i v_i'∑aivi′ is ∑ai\sum a_i∑ai and the others are ∑aivi\sum a_i v_i∑aivi , so ∑aivi′=0\sum a_i v_i' = 0∑aivi′=0 says exactly ∑ai=0\sum a_i = 0∑ai=0 and ∑aivi=0\sum a_i v_i = 0∑aivi=0 . The row of 1's encodes the condition on the sum of the coefficients.
[Affine dependence] By the bookkeeping trick (prepend a 1 to each point), the matroid AG(2,3)AG(2, 3)AG(2,3) is the matroid of linear dependence of the columns of which matrix?
[111111111000111222012012012]\boldsymbol{\begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 2 & 2 & 2 \\ 0 & 1 & 2 & 0 & 1 & 2 & 0 & 1 & 2 \end{bmatrix}}⎣⎡100101102110111112120121122⎦⎤ over F3\mathbb{F}_3F3 In general, AG(n,q)AG(n, q)AG(n,q) is the matroid of the columns of an (n+1)×qn(n + 1) \times q^n(n+1)×qn matrix, which gives a second proof that AG(n,q)AG(n, q)AG(n,q) is a matroid, of rank n+1n + 1n+1 .
[Affine dependence] Proposition 5.9 (1). SSS is a set of points of AG(n,q)AG(n, q)AG(n,q) and FFF the smallest flat containing SSS . What is the rank r(S)r(S)r(S) ?
r(S)=dim(F)+1\boldsymbol{r(S) = \dim(F) + 1}r(S)=dim(F)+1 Example: in AG(2,3)AG(2, 3)AG(2,3) , three collinear points span a line (dimension 1), rank 2; three non-collinear points span the plane (dimension 2), rank 3.Example: r(AG(n,q))=n+1r(AG(n, q)) = n + 1r(AG(n,q))=n+1 .
[Affine dependence] Definition 5.11. When is P∈FqnP \in \mathbb{F}_q^nP∈Fqn an affine combination of S={P1,…,Pm}S = \{P_1, \dots, P_m\}S={P1,…,Pm} ?
When P=∑i=1maiPiP = \displaystyle\sum_{i=1}^m a_i P_iP=i=1∑maiPi with ∑i=1mai=1\displaystyle\sum_{i=1}^m a_i = 1i=1∑mai=1 . Example: over F5\mathbb{F}_5F5 , (4,3,3)=2⋅(1,2,4)+4⋅(3,1,0)(4, 3, 3) = 2 \cdot (1, 2, 4) + 4 \cdot (3, 1, 0)(4,3,3)=2⋅(1,2,4)+4⋅(3,1,0) and 2+4≡12 + 4 \equiv 12+4≡1 .
[Affine dependence] Proposition 5.9 (2). S={P1,…,Pm}S = \{P_1, \dots, P_m\}S={P1,…,Pm} is a set of points of AG(n,q)AG(n, q)AG(n,q) . When is PPP in the closure S‾\overline{S}S ?
Iff PPP is an affine combination of SSS : P=∑aiPiP = \sum a_i P_iP=∑aiPi with ∑ai=1\sum a_i = 1∑ai=1 . Example: in AG(2,3)AG(2, 3)AG(2,3) , 2⋅(0,0)+2⋅(1,2)=(2,1)2 \cdot (0, 0) + 2 \cdot (1, 2) = (2, 1)2⋅(0,0)+2⋅(1,2)=(2,1) with 2+2≡12 + 2 \equiv 12+2≡1 , so (2,1)(2, 1)(2,1) is on the line through (0,0)(0, 0)(0,0) and (1,2)(1, 2)(1,2) .
[Affine dependence] Proposition 5.9 (3). Which sets of points are the hyperplanes of the matroid AG(n,q)AG(n, q)AG(n,q) ?
The solution sets of one equation a1x1+⋯+anxn=ba_1 x_1 + \dots + a_n x_n = ba1x1+⋯+anxn=b ( ai,b∈Fqa_i, b \in \mathbb{F}_qai,b∈Fq , the aia_iai not all 0). Example: in AG(2,q)AG(2, q)AG(2,q) the hyperplanes are the lines ax+by=cax + by = cax+by=c .
[Affine dependence] In AG(3,5)AG(3, 5)AG(3,5) , is P=(4,3,3)P = (4, 3, 3)P=(4,3,3) on the line through Q=(1,2,4)Q = (1, 2, 4)Q=(1,2,4) and R=(3,1,0)R = (3, 1, 0)R=(3,1,0) ?
Yes: P=2Q+4RP = 2Q + 4RP=2Q+4R and 2+4≡1(mod5)2 + 4 \equiv 1 \pmod 52+4≡1(mod5) , so PPP is an affine combination of Q,RQ, RQ,R . 2Q+4R=(2+12, 4+4, 8+0)=(14,8,8)≡(4,3,3)2Q + 4R = (2 + 12, \ 4 + 4, \ 8 + 0) = (14, 8, 8) \equiv (4, 3, 3)2Q+4R=(2+12, 4+4, 8+0)=(14,8,8)≡(4,3,3) .
[Affine dependence] In AG(3,5)AG(3, 5)AG(3,5) , the line FFF through P=(4,3,3)P = (4, 3, 3)P=(4,3,3) and Q=(1,2,4)Q = (1, 2, 4)Q=(1,2,4) is u+Wu + Wu+W with u=Pu = Pu=P , W={t(2,4,1)}W = \{t(2, 4, 1)\}W={t(2,4,1)} . Which two equations describe FFF ?
3x+y=0\boldsymbol{3x + y = 0}3x+y=0 and 2x+z=1\boldsymbol{2x + z = 1}2x+z=1 W⊥W^\perpW⊥ = solutions of 2x+4y+z=02x + 4y + z = 02x+4y+z=0 , with basis (3,1,0),(2,0,1)(3, 1, 0), (2, 0, 1)(3,1,0),(2,0,1) . With A=[310201]A = \begin{bmatrix} 3 & 1 & 0 \\ 2 & 0 & 1 \end{bmatrix}A=[321001] , Au=(15,11)≡(0,1)Au = (15, 11) \equiv (0, 1)Au=(15,11)≡(0,1) , and F={v∣Av=Au}F = \{v \mid Av = Au\}F={v∣Av=Au} .So the line is the intersection of two hyperplanes.Example: QQQ : 3+2=5≡03 + 2 = 5 \equiv 03+2=5≡…
[Affine dependence] Proposition 5.12. For x∈Fqnx \in \mathbb{F}_q^nx∈Fqn let x′=(1,x1,…,xn)x' = (1, x_1, \dots, x_n)x′=(1,x1,…,xn) . When is uuu an affine combination of v1,…,vmv_1, \dots, v_mv1,…,vm ?
Iff u′u'u′ is a linear combination of v1′,…,vm′v_1', \dots, v_m'v1′,…,vm′ in Fqn+1\mathbb{F}_q^{n+1}Fqn+1 . The first coordinate encodes ∑ai=1\sum a_i = 1∑ai=1 .Example: over F5\mathbb{F}_5F5 , 2⋅(1,1,2,4)+4⋅(1,3,1,0)=(1,4,3,3)2 \cdot (1, 1, 2, 4) + 4 \cdot (1, 3, 1, 0) = (1, 4, 3, 3)2⋅(1,1,2,4)+4⋅(1,3,1,0)=(1,4,3,3) , from 2⋅(1,2,4)+4⋅(3,1,0)=(4,3,3)2 \cdot (1, 2, 4) + 4 \cdot (3, 1, 0) = (4, 3, 3)2⋅(1,2,4)+4⋅(3,1,0)=(4,3,3) .
[Affine dependence] In AG(3,3)AG(3, 3)AG(3,3) , how many points satisfy x+2y+z=1x + 2y + z = 1x+2y+z=1 , and what do they form?
9 points, forming a hyperplane that is a copy of AG(2,3)AG(2, 3)AG(2,3) . (1,0,0),(0,2,0),(0,0,1),(2,1,0),(2,0,2),(0,1,2),(1,1,1),(2,2,1),(1,2,2)(1,0,0), (0,2,0), (0,0,1), (2,1,0), (2,0,2), (0,1,2), (1,1,1), (2,2,1), (1,2,2)(1,0,0),(0,2,0),(0,0,1),(2,1,0),(2,0,2),(0,1,2),(1,1,1),(2,2,1),(1,2,2) .Each of these points is an affine combination of any three non-collinear ones, e.g. (2,0,2)=2⋅(1,2,2)+1⋅(2,1,0)+1⋅(1,1,1)(2, 0, 2) = 2 \cdot (1, 2, 2) + 1 \cdot (2, 1, 0) + 1 \cdot (1, 1, 1)(2,0,2)=2⋅(1…
[The projective plane PG(2, q)] Definition 5.13. What is a projective plane (P,L,I)(\mathcal{P}, \mathcal{L}, I)(P,L,I) (points, lines, incidence)?
P1 Every pair of points determines a unique line. P2 Every pair of lines intersects in a unique point. Four-point There are at least four points, no three on a line. The four-point rules out trivial examples, e.g. a triangle (3 points, 3 lines) satisfies P1 and P2.
[The projective plane PG(2, q)] What is the duality principle for projective planes?
Interchanging "point" and "line" in a theorem about projective planes gives another theorem (its dual). This works because interchanging the two words turns P1 (two points determine a unique line) into P2 (two lines meet in a unique point) and back.
[The projective plane PG(2, q)] Does the parallel postulate hold in a projective plane?
No, it is completely false: there are no parallel lines, since every two lines intersect.
[The projective plane PG(2, q)] What is the order of a projective plane?
qqq , if every line has q+1q + 1q+1 points. Every line of a projective plane has the same number of points (this follows from the axioms).Example: the Fano plane has 3 points per line, so order 2.
[The projective plane PG(2, q)] How is a projective plane constructed from the vector space Fq3\mathbb{F}_q^3Fq3 ?
Points = the one-dimensional subspaces (lines through (0,0,0)(0, 0, 0)(0,0,0) ); lines = the two-dimensional subspaces (planes through (0,0,0)(0, 0, 0)(0,0,0) ). This is PG(2,q)PG(2, q)PG(2,q) : PGPGPG = projective geometry, 2 = dimension, qqq = the field Fq\mathbb{F}_qFq .
[The projective plane PG(2, q)] What are the 7 points of PG(2,2)PG(2, 2)PG(2,2) (one-dimensional subspaces of F23\mathbb{F}_2^3F23 ), written as column vectors?
abcdefg100111001011010011011\boldsymbol{\begin{array}{ccccccc} a & b & c & d & e & f & g \\ \hline 1 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 & 1 & 1 \end{array}}a100b010c001d111e110f101g011 Each of the 7 lines through (0,0,0)(0, 0, 0)(0,0,0) in AG(3,2)AG(3, 2)AG(3,2) has 2 points; it is represented by its one non-zero vector. The seven lines through (0,0,0)(0, 0, 0)(0,0,0) in AG(3,2)AG(3, 2)AG(3,2) .
[The projective plane PG(2, q)] Why does PG(2,2)PG(2, 2)PG(2,2) (lines = planes through (0,0,0)(0, 0, 0)(0,0,0) in F23\mathbb{F}_2^3F23 ) have exactly 7 lines?
(72)=21\binom{7}{2} = 21(27)=21 pairs of non-zero vectors, and each plane is counted (32)=3\binom{3}{2} = 3(23)=3 times: 21/3=721 / 3 = 721/3=7 . Each plane through (0,0,0)(0, 0, 0)(0,0,0) contains 3 non-zero vectors, and any two of them generate it.
[The projective plane PG(2, q)] In PG(2,2)PG(2, 2)PG(2,2) , why are (1,1,0)(1, 1, 0)(1,1,0) , (1,0,1)(1, 0, 1)(1,0,1) , (0,1,1)(0, 1, 1)(0,1,1) collinear?
They are linearly dependent over F2\mathbb{F}_2F2 : their sum is (0,0,0)(0, 0, 0)(0,0,0) . So with (0,0,0)(0, 0, 0)(0,0,0) they form a plane of AG(3,2)AG(3, 2)AG(3,2) . In the drawing this is the "circular" line.
[The projective plane PG(2, q)] Which matroid is PG(2,2)PG(2, 2)PG(2,2) , and when are three of its points collinear?
The Fano plane F7F_7F7 ; three points are collinear iff the vectors are linearly dependent over F2\mathbb{F}_2F2 . Example: a=(1,0,0)a = (1, 0, 0)a=(1,0,0) , d=(1,1,1)d = (1, 1, 1)d=(1,1,1) , g=(0,1,1)g = (0, 1, 1)g=(0,1,1) are collinear since a+g=da + g = da+g=d .
[The projective plane PG(2, q)] What do you get by contracting any point xxx of AG(3,2)AG(3, 2)AG(3,2) (the cube {0,1}3\{0, 1\}^3{0,1}3 )?
AG(3,2)/x=PG(2,2)\boldsymbol{AG(3, 2) / x = PG(2, 2)}AG(3,2)/x=PG(2,2) , the Fano plane. Translate xxx to (0,0,0)(0, 0, 0)(0,0,0) : each of the 7 other points is the only non-zero point of its line through xxx , because F2\mathbb{F}_2F2 has only one non-zero element.
[The projective plane PG(2, q)] How many points does PG(2,3)PG(2, 3)PG(2,3) have, and why?
13: the lines through (0,0,0)(0, 0, 0)(0,0,0) in AG(3,3)AG(3, 3)AG(3,3) partition the 26 non-zero vectors into 13 sets of size 2. Example: {(1,0,0),(2,0,0)}\{(1, 0, 0), (2, 0, 0)\}{(1,0,0),(2,0,0)} is one point of PG(2,3)PG(2, 3)PG(2,3) .
[The projective plane PG(2, q)] How many points are on each line of PG(2,3)PG(2, 3)PG(2,3) , and how many lines are there?
4 points per line, 13 lines. A plane through (0,0,0)(0, 0, 0)(0,0,0) in AG(3,3)AG(3, 3)AG(3,3) has 9 points, so (9−1)/2=4(9 - 1) / 2 = 4(9−1)/2=4 lines through (0,0,0)(0, 0, 0)(0,0,0) . The 13 lines follow from point–line symmetry. PG(2,3)PG(2, 3)PG(2,3) with 7 of its 13 lines drawn.
[The projective plane PG(2, q)] PG(2,3)PG(2, 3)PG(2,3) is represented by the 13 columns of A3=abcdefghijklm111111111000000011122211100120120120121A_3 = \begin{array}{ccccccccccccc} a & b & c & d & e & f & g & h & i & j & k & l & m \\ \hline 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 2 & 2 & 2 & 1 & 1 & 1 & 0 \\ 0 & 1 & 2 & 0 & 1 & 2 & 0 & 1 & 2 & 0 & 1 & 2 & 1 \end{array}A3=a100b101c102d110e111f112g120h121i122j010k011l012m001 What three things do…
Every pair is independent Only one vector is taken from each line through (0,0,0)(0, 0, 0)(0,0,0) ; the first non-zero entry of each column is 1. Example: (1,0,0)(1, 0, 0)(1,0,0) is taken, (2,0,0)(2, 0, 0)(2,0,0) is not. The first nine columns are AG(2,3)AG(2, 3)AG(2,3) They have first coordinate 1, and their other two coordinates are the 9 pairs (x,y)∈F32(x, y) \in \mathbb{F}_3^2(x,y)∈F32 . j,k,l,mj, k, l, mj,k,l,m form a line They have first coordinate 0, so any three of them are linearly de…
[The projective plane PG(2, q)] Definition 5.16 (formal). What are the points of PG(2,q)PG(2, q)PG(2,q) , and when are three points collinear?
Points: the classes [v][v][v] of non-zero v∈Fq3v \in \mathbb{F}_q^3v∈Fq3 under u∼v ⟺ u=kvu \sim v \iff u = kvu∼v⟺u=kv for a non-zero k∈Fqk \in \mathbb{F}_qk∈Fq . Three points are collinear iff representatives can be chosen linearly dependent. So PG(2,q)=(AG(3,q)−(0,0,0))/∼PG(2, q) = (AG(3, q) - (0, 0, 0)) / \simPG(2,q)=(AG(3,q)−(0,0,0))/∼ .
[The projective plane PG(2, q)] Which vector is the canonical representative of a point of PG(2,q)PG(2, q)PG(2,q) ?
The one whose first non-zero coordinate is 1. Example: in PG(2,3)PG(2, 3)PG(2,3) , (2,1,1)=2⋅(1,2,2)(2, 1, 1) = 2 \cdot (1, 2, 2)(2,1,1)=2⋅(1,2,2) , so the point is written (1,2,2)(1, 2, 2)(1,2,2) .
[The projective plane PG(2, q)] Proposition 5.17. Is PG(2,q)PG(2, q)PG(2,q) a projective plane? Is every projective plane a PG(2,q)PG(2, q)PG(2,q) ?
Yes, PG(2,q)PG(2, q)PG(2,q) satisfies P1 and P2 and contains a four-point. No, not every projective plane arises this way.
[The projective plane PG(2, q)] How is PG(2,q)PG(2, q)PG(2,q) a matroid?
Ground set: its points (vectors of Fq3\mathbb{F}_q^3Fq3 ); a set is independent iff its vectors are linearly independent. It has rank 3: three points are dependent iff they are collinear.
[The projective plane PG(2, q)] How many points and lines does PG(2,q)PG(2, q)PG(2,q) have, and why?
q2+q+1\boldsymbol{q^2 + q + 1}q2+q+1 points and q2+q+1\boldsymbol{q^2 + q + 1}q2+q+1 lines. Fq3\mathbb{F}_q^3Fq3 has q3−1q^3 - 1q3−1 non-zero vectors, q−1q - 1q−1 on each line through (0,0,0)(0, 0, 0)(0,0,0) : q3−1q−1=q2+q+1\frac{q^3 - 1}{q - 1} = q^2 + q + 1q−1q3−1=q2+q+1 . Lines by symmetry.Example: PG(2,2)PG(2, 2)PG(2,2) : 7, PG(2,3)\ PG(2, 3) PG(2,3) : 13, PG(2,5)\ PG(2, 5) PG(2,5) : 31.
[The projective plane PG(2, q)] In PG(2,q)PG(2, q)PG(2,q) , what does the equation ax+by+cz=0ax + by + cz = 0ax+by+cz=0 ( a,b,c∈Fqa, b, c \in \mathbb{F}_qa,b,c∈Fq not all 0) define?
A line. Example: in PG(2,2)PG(2, 2)PG(2,2) , z=0z = 0z=0 gives the line {(1,0,0),(0,1,0),(1,1,0)}\{(1, 0, 0), (0, 1, 0), (1, 1, 0)\}{(1,0,0),(0,1,0),(1,1,0)} .
[The projective plane PG(2, q)] What is left when any line is removed from PG(2,q)PG(2, q)PG(2,q) ?
The affine plane AG(2,q)AG(2, q)AG(2,q) . Example: removing a line from the Fano plane leaves 4 points, no three collinear: AG(2,2)AG(2, 2)AG(2,2) .
[The projective plane PG(2, q)] AG(2,2)AG(2, 2)AG(2,2) has points a=(0,0)a = (0, 0)a=(0,0) , b=(1,0)b = (1, 0)b=(1,0) , c=(0,1)c = (0, 1)c=(0,1) , d=(1,1)d = (1, 1)d=(1,1) . How many lines does it have, and what are its parallel classes?
6 lines in 3 parallel classes of 2 lines: {ab,cd}\{ab, cd\}{ab,cd} , {ac,bd}\{ac, bd\}{ac,bd} , {ad,bc}\{ad, bc\}{ad,bc} . A parallel class is a set of pairwise parallel lines.
[The projective plane PG(2, q)] How is PG(2,q)PG(2, q)PG(2,q) built from the affine plane AG(2,q)AG(2, q)AG(2,q) ?
Add a line at infinity with one new point for each parallel class; the lines of that class are extended through that point. Parallel lines now meet on the line at infinity. From AG(2,2)AG(2, 2)AG(2,2) (a) to the Fano plane (d).
[The projective plane PG(2, q)] How are the points a,b,c,da, b, c, da,b,c,d of AG(2,2)AG(2, 2)AG(2,2) and the line at infinity written as vectors of PG(2,2)PG(2, 2)PG(2,2) ?
Prepend a 1 to each point (bookkeeping trick); the line at infinity is x=0x = 0x=0 , the points e,f,ge, f, ge,f,g with first coordinate 0. abcdefg111100001011010011011\begin{array}{ccccccc} a & b & c & d & e & f & g \\ \hline 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 & 1 & 1 \end{array}a100b110c101d111e010f001g011
[The projective plane PG(2, q)] In PG(2,2)PG(2, 2)PG(2,2) with a=(1,0,0)a = (1, 0, 0)a=(1,0,0) , b=(1,1,0)b = (1, 1, 0)b=(1,1,0) , c=(1,0,1)c = (1, 0, 1)c=(1,0,1) , d=(1,1,1)d = (1, 1, 1)d=(1,1,1) and line at infinity e=(0,1,0)e = (0, 1, 0)e=(0,1,0) , f=(0,0,1)f = (0, 0, 1)f=(0,0,1) , g=(0,1,1)g = (0, 1, 1)g=(0,1,1) : where does the parallel class {ab,cd}\{ab, cd\}{ab,cd} meet the line at infinity?
At eee , since {a,b,e}\{a, b, e\}{a,b,e} and {c,d,e}\{c, d, e\}{c,d,e} are linearly dependent over F2\mathbb{F}_2F2 . a+b=(0,1,0)=ea + b = (0, 1, 0) = ea+b=(0,1,0)=e and c+d=(0,1,0)=ec + d = (0, 1, 0) = ec+d=(0,1,0)=e . Likewise {ac,bd}\{ac, bd\}{ac,bd} meets fff and {ad,bc}\{ad, bc\}{ad,bc} meets ggg .
[The projective plane PG(2, q)] How many points does the line at infinity get when PG(2,3)PG(2, 3)PG(2,3) is built from AG(2,3)AG(2, 3)AG(2,3) ?
4, one for each of the 4 parallel classes of AG(2,3)AG(2, 3)AG(2,3) . Each parallel class of 3 lines meets the line jklmjklmjklm in one point.
[The projective plane PG(2, q)] What does a matrix whose columns are the points of PG(2,q)PG(2, q)PG(2,q) look like?
Size 3 rows and q2+q+1q^2 + q + 1q2+q+1 columns. Example: PG(2,5)PG(2, 5)PG(2,5) gives a 3×313 \times 313×31 matrix. Normalized columns The first non-zero entry of each column can be taken to be 1. Affine part and line at infinity The first q2q^2q2 columns have first coordinate 1 (a copy of AG(2,q)AG(2, q)AG(2,q) ), the remaining q+1q + 1q+1 have first coordinate 0. Collinearity Three points are collinear iff their columns are linearly dependent.
[The projective plane PG(2, q)] How is the real projective plane obtained from R3\mathbb{R}^3R3 ?
Remove the origin, map each ray from the origin to its point on the unit sphere, and identify antipodal points. The result is a non-orientable surface, called a cross-cap by topologists.
[Projective geometry] What are the two constructions of the projective plane PG(2,q)PG(2,q)PG(2,q) over the finite field Fq\mathbb{F}_qFq ?
From affine 3-space The points of PG(2,q)PG(2,q)PG(2,q) are the lines through the origin of AG(3,q)AG(3,q)AG(3,q) , i.e. the nonzero vectors of Fq3\mathbb{F}_q^3Fq3 up to nonzero scalar multiples. The lines of PG(2,q)PG(2,q)PG(2,q) are the planes through the origin. Example ( q=2q = 2q=2 ): the 7 nonzero vectors of F23\mathbb{F}_2^3F23 are the 7 points of the Fano plane. From the affine plane Take the affine plane AG(2,q)AG(2,q)AG(2,q) and add a line at infinity, with one new point for each o…
[Projective geometry] Why does PG(2,q)PG(2,q)PG(2,q) , built from the lines through the origin of AG(3,q)AG(3,q)AG(3,q) , have q3−1q−1\frac{q^3-1}{q-1}q−1q3−1 points?
Fq3\mathbb{F}_q^3Fq3 has q3−1q^3 - 1q3−1 nonzero vectors, and each line through the origin contains exactly q−1q - 1q−1 of them. A line through the origin is {tv:t∈Fq}\{t v : t \in \mathbb{F}_q\}{tv:t∈Fq} for a nonzero vvv : qqq vectors, one of them 000 .Example: PG(2,3)PG(2,3)PG(2,3) has 27−12=13\frac{27-1}{2} = 13227−1=13 points.
[Projective geometry] How are the points, the lines and the kkk -dimensional planes of the projective geometry PG(n,q)PG(n,q)PG(n,q) defined?
Points The lines through the origin in AG(n+1,q)AG(n+1,q)AG(n+1,q) , i.e. the 1-dimensional subspaces of Fqn+1\mathbb{F}_q^{n+1}Fqn+1 . Example: the points of PG(3,2)PG(3,2)PG(3,2) are the 15 nonzero vectors of F24\mathbb{F}_2^4F24 . Lines The planes through the origin in AG(n+1,q)AG(n+1,q)AG(n+1,q) , i.e. the 2-dimensional subspaces of Fqn+1\mathbb{F}_q^{n+1}Fqn+1 . Example: in PG(2,2)PG(2,2)PG(2,2) , the subspace spanned by (1,0,0)(1,0,0)(1,0,0) and (0,1,0)(0,1,0)(0,1,0) gives the line {(1…
[Projective geometry] How many points does the projective geometry PG(n,q)PG(n,q)PG(n,q) have?
qn+1−1q−1=qn+qn−1+⋯+q+1\boldsymbol{\frac{q^{n+1}-1}{q-1} = q^n + q^{n-1} + \dots + q + 1}q−1qn+1−1=qn+qn−1+⋯+q+1 qn+1−1q^{n+1} - 1qn+1−1 nonzero vectors in Fqn+1\mathbb{F}_q^{n+1}Fqn+1 , q−1q - 1q−1 on each line through the origin.Example: PG(3,2)PG(3,2)PG(3,2) has 8+4+2+1=158 + 4 + 2 + 1 = 158+4+2+1=15 points.
[Projective geometry] Proposition 5.21 Let EEE be the set of points of PG(n,q)PG(n,q)PG(n,q) , and let F\mathcal{F}F consist of all planes of all dimensions of PG(n,q)PG(n,q)PG(n,q) , together with ∅\emptyset∅ and EEE . Then F\mathcal{F}F is … ?
The family of flats of a matroid on EEE (the matroid PG(n,q)PG(n,q)PG(n,q) ). So the flats of PG(n,q)PG(n,q)PG(n,q) are exactly the subspaces of Fqn+1\mathbb{F}_q^{n+1}Fqn+1 .Example: the flats of PG(2,2)PG(2,2)PG(2,2) are ∅\emptyset∅ , the 7 points, the 7 lines and EEE .
[Projective geometry] The flats of PG(n,q)PG(n,q)PG(n,q) (with ground set the 1-dimensional subspaces of Fqn+1\mathbb{F}_q^{n+1}Fqn+1 ) are the subspaces of Fqn+1\mathbb{F}_q^{n+1}Fqn+1 of all dimensions.What is the idea of the proof that these sets are the flats of a matroid?
Linear independence satisfies (I1), (I2), (I3), and its closed sets (closed under linear combinations) are the subspaces. Example: in PG(2,2)PG(2,2)PG(2,2) , the closure of {(1,0,0),(0,1,0)}\{(1,0,0), (0,1,0)\}{(1,0,0),(0,1,0)} adds (1,1,0)(1,1,0)(1,1,0) , the only other nonzero vector of their span.
[Projective geometry] Which matroid is the projective line PG(1,q)PG(1,q)PG(1,q) ?
The (q+1)(q+1)(q+1) -point line U2,q+1U_{2,q+1}U2,q+1 . Its points are the q+1q + 1q+1 lines through (0,0)(0,0)(0,0) in AG(2,q)AG(2,q)AG(2,q) , as columns: [111⋯10012⋯q−11]\begin{bmatrix} 1 & 1 & 1 & \cdots & 1 & 0 \\ 0 & 1 & 2 & \cdots & q-1 & 1 \end{bmatrix}[101112⋯⋯1q−101] ( qqq prime). No column is a multiple of another, so every 2 points are independent.Equivalently: the qqq -point line AG(1,q)AG(1,q)AG(1,q) plus one point at infinity.Example: PG(1,2)=U2,3PG(1,2) = U_{2,3}PG(1,2)=U2…
[Projective geometry] Proposition 5.23 Let HHH be a hyperplane of PG(n,q)PG(n,q)PG(n,q) . Then HHH is isomorphic to … ? and PG(n,q)−HPG(n,q) - HPG(n,q)−H is isomorphic to … ?
H≅H \congH≅ PG(n−1,q)PG(n-1,q)PG(n−1,q) , and PG(n,q)−H≅PG(n,q) - H \congPG(n,q)−H≅ AG(n,q)AG(n,q)AG(n,q) . The isomorphisms preserve all point, line, plane, … incidences (they are matroid isomorphisms). Example: in PG(2,3)PG(2,3)PG(2,3) (13 points, 7 of its 13 lines drawn), removing the line {j,k,l,m}≅PG(1,3)\{j, k, l, m\} \cong PG(1,3){j,k,l,m}≅PG(1,3) leaves the 9 points a,…,ia, \dots, ia,…,i of AG(2,3)AG(2,3)AG(2,3) .
[Projective geometry] How is PG(n,q)PG(n,q)PG(n,q) built from the affine geometry AG(n,q)AG(n,q)AG(n,q) ?
Add a hyperplane at infinity, isomorphic to PG(n−1,q)PG(n-1,q)PG(n−1,q) . Parallel lines of AG(n,q)AG(n,q)AG(n,q) meet in that hyperplane. Number of points: qn+qn−1q−1=qn+1−1q−1q^n + \frac{q^n - 1}{q-1} = \frac{q^{n+1}-1}{q-1}qn+q−1qn−1=q−1qn+1−1 .Example: n=2n = 2n=2 : AG(2,q)AG(2,q)AG(2,q) plus a line at infinity with q+1q + 1q+1 points, one per parallel class.
[Projective geometry] A flat FFF of PG(n,q)PG(n,q)PG(n,q) has rank kkk . Which projective geometry is FFF isomorphic to?
PG(k−1,q)PG(k-1,q)PG(k−1,q) FFF comes from a kkk -dimensional subspace of Fqn+1\mathbb{F}_q^{n+1}Fqn+1 , i.e. a copy of Fqk\mathbb{F}_q^kFqk .Example: every rank 3 flat of PG(n,q)PG(n,q)PG(n,q) is a projective plane PG(2,q)PG(2,q)PG(2,q) .
[Projective geometry] Theorem 5.24 The lattice of subspaces of Fqn+1\mathbb{F}_q^{n+1}Fqn+1 , ordered by inclusion, is … ?
A geometric lattice: the lattice of flats of the matroid PG(n,q)PG(n,q)PG(n,q) . Rank kkk flats of PG(n,q)PG(n,q)PG(n,q) are the kkk -dimensional subspaces.Example: n=1n = 1n=1 : {0}\{0\}{0} , the q+1q + 1q+1 lines through 000 , and Fq2\mathbb{F}_q^2Fq2 ; this is the lattice of flats of U2,q+1U_{2,q+1}U2,q+1 .
[Projective geometry] FFF is a flat of rank kkk in PG(n,q)PG(n,q)PG(n,q) (points are vectors in Fqn+1\mathbb{F}_q^{n+1}Fqn+1 ). How can FFF be described by a matrix?
F={v:Av=0}F = \{v : Av = 0\}F={v:Av=0} for some (n+1−k)×(n+1)(n+1-k) \times (n+1)(n+1−k)×(n+1) matrix AAA (of rank n+1−kn+1-kn+1−k ). The null space of AAA then has dimension (n+1)−(n+1−k)=k(n+1) - (n+1-k) = k(n+1)−(n+1−k)=k , matching rank kkk .Example: a line ( k=2k = 2k=2 ) of PG(4,3)PG(4,3)PG(4,3) is the null space of a 3×53 \times 53×5 matrix.
[Projective geometry] In PG(4,3)PG(4,3)PG(4,3) , take P=(1,2,0,0,1)P = (1,2,0,0,1)P=(1,2,0,0,1) and Q=(0,1,1,2,0)Q = (0,1,1,2,0)Q=(0,1,1,2,0) . How do you find a matrix AAA such that the line PQPQPQ is {v:Av=0}\{v : Av = 0\}{v:Av=0} ?
Put PPP and QQQ as the rows of a matrix BBB , and take as rows of AAA a basis of the null space of BBB . B=[1200101120]B = \begin{bmatrix} 1 & 2 & 0 & 0 & 1 \\ 0 & 1 & 1 & 2 & 0 \end{bmatrix}B=[1021010210] , A=[100021101011200]\quad A = \begin{bmatrix} 1 & 0 & 0 & 0 & 2 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 2 & 0 & 0 \end{bmatrix}A=⎣⎡111011002010200⎦⎤ Then AP=AQ=0AP = AQ = 0AP=AQ=0 (mod 3), and AAA has rank 3, so its null space has dimension 2: a rank 2 flat, the line PQPQPQ .
[Projective geometry] In PG(4,3)PG(4,3)PG(4,3) , the line through P=(1,2,0,0,1)P = (1,2,0,0,1)P=(1,2,0,0,1) and Q=(0,1,1,2,0)Q = (0,1,1,2,0)Q=(0,1,1,2,0) is the solution set of x1+2x5=0x_1 + 2x_5 = 0x1+2x5=0 , x1+x2+x4=0\ x_1 + x_2 + x_4 = 0 x1+x2+x4=0 , x1+x2+2x3=0\ x_1 + x_2 + 2x_3 = 0 x1+x2+2x3=0 (mod 3).What does this system say geometrically, and which points does the line have?
The line PQPQPQ (rank 2) is the intersection of three hyperplanes (rank 4). Its 4 points are PPP , QQQ , P+QP + QP+Q , P+2QP + 2QP+2Q . A line of PG(n,3)PG(n,3)PG(n,3) has q+1=4q + 1 = 4q+1=4 points.Example: P+Q=(1,0,1,2,1)P + Q = (1,0,1,2,1)P+Q=(1,0,1,2,1) : 1+2=31 + 2 = 31+2=3 , 1+0+2=31 + 0 + 2 = 31+0+2=3 , 1+0+2=31 + 0 + 2 = 31+0+2=3 , all ≡0\equiv 0≡0 . P+2Q=(1,1,2,1,1)P + 2Q = (1,1,2,1,1)P+2Q=(1,1,2,1,1) : 1+2=31 + 2 = 31+2=3 , 1+1+1=31 + 1 + 1 = 31+1+1=3 , 1+1+4=61 + 1 + 4 = 61+1+4=6 , a…
[Projective geometry] How are independent sets, closure, hyperplanes and rank interpreted in the matroid PG(n,q)PG(n,q)PG(n,q) (points = nonzero vectors of Fqn+1\mathbb{F}_q^{n+1}Fqn+1 up to scalar multiples)?
Independent sets {P1,…,Pk}\{P_1, \dots, P_k\}{P1,…,Pk} is independent if the vectors are linearly independent: no nontrivial aia_iai with ∑aiPi=0\sum a_i P_i = 0∑aiPi=0 . Example: in PG(2,2)PG(2,2)PG(2,2) , (1,0,0)+(0,1,0)+(1,1,0)=0(1,0,0) + (0,1,0) + (1,1,0) = 0(1,0,0)+(0,1,0)+(1,1,0)=0 , so these 3 points are dependent (a 3-point line). Closure Q∈S‾Q \in \overline{S}Q∈S if QQQ is a linear combination of the points of SSS . Example: in PG(2,2)PG(2,2)PG(2,2) , {(1,0,0),(0,1,0)}‾={(1,0,0),(…
[Projective geometry] How does the equation of a hyperplane in the affine geometry AG(n,q)AG(n,q)AG(n,q) differ from one in the projective geometry PG(n,q)PG(n,q)PG(n,q) ?
AG(n,q)AG(n,q)AG(n,q) : a linear equation ∑aixi=b\sum a_i x_i = b∑aixi=b ; PG(n,q)\ PG(n,q) PG(n,q) : a homogeneous linear equation ∑aixi=0\sum a_i x_i = 0∑aixi=0 . Example: in AG(2,3)AG(2,3)AG(2,3) , x+y=1x + y = 1x+y=1 is a line (3 points); in PG(2,3)PG(2,3)PG(2,3) , x0+x1+x2=0x_0 + x_1 + x_2 = 0x0+x1+x2=0 is a line (4 points).
[Counting k-flats and q-binomials] What is the qqq -binomial coefficient [nk]q {n \brack k}_q[kn]q ?
The number of kkk -dimensional subspaces of the nnn -dimensional vector space Fqn\mathbb{F}_q^nFqn . Example: [21]2=3 {2 \brack 1}_2 = 3[12]2=3 : the subspaces spanned by (1,0)(1,0)(1,0) , by (0,1)(0,1)(0,1) and by (1,1)(1,1)(1,1) .
[Counting k-flats and q-binomials] The q-binomial coefficients are also called Gaussian coefficients.
The book prefers "q-binomial", which stresses the connection with ordinary binomial coefficients.
[Counting k-flats and q-binomials] N(n,k)N(n,k)N(n,k) is the number of ordered kkk -tuples (v1,…,vk)(v_1, \dots, v_k)(v1,…,vk) of linearly independent vectors in Fqn\mathbb{F}_q^nFqn . Count N(n,k)N(n,k)N(n,k) vector by vector.
N(n,k)=(qn−1)(qn−q)(qn−q2)⋯(qn−qk−1)\boldsymbol{N(n,k) = (q^n - 1)(q^n - q)(q^n - q^2) \cdots (q^n - q^{k-1})}N(n,k)=(qn−1)(qn−q)(qn−q2)⋯(qn−qk−1) v1v_1v1 : any of the qn−1q^n - 1qn−1 nonzero vectors. vi+1v_{i+1}vi+1 : any vector outside the span of v1,…,viv_1, \dots, v_iv1,…,vi , which has qiq^iqi vectors.Example: N(2,2)N(2,2)N(2,2) over F2\mathbb{F}_2F2 : (4−1)(4−2)=6(4 - 1)(4 - 2) = 6(4−1)(4−2)=6 .
[Counting k-flats and q-binomials] N(n,k)N(n,k)N(n,k) is the number of ordered kkk -tuples of linearly independent vectors in Fqn\mathbb{F}_q^nFqn , and [nk]q {n \brack k}_q[kn]q is the number of kkk -dimensional subspaces of Fqn\mathbb{F}_q^nFqn .Count N(n,k)N(n,k)N(n,k) by first choosing the subspace the vectors span.
N(n,k)=[nk]q(qk−1)(qk−q)⋯(qk−qk−1)\boldsymbol{N(n,k) = {n \brack k}_q (q^k - 1)(q^k - q) \cdots (q^k - q^{k-1})}N(n,k)=[kn]q(qk−1)(qk−q)⋯(qk−qk−1) Choose a kkk -dimensional subspace WWW , then an ordered basis of WWW : the vector-by-vector count applied to the qkq^kqk vectors of WWW .Example: n=k=2n = k = 2n=k=2 , q=2q = 2q=2 : 1⋅(4−1)(4−2)=61 \cdot (4 - 1)(4 - 2) = 61⋅(4−1)(4−2)=6 .