Ch.6: Representable matroids
Chapter 6 of the book "Matroids: A Geometric Introduction" by Gary Gordon and Jennifer McNulty (2012) 6.1. Matrices are matroids 6.2. Representing representable matroids 6.3. How representations depend on the field 6.4. Non-representable matroids 6.5. Representations and geometry
115 flashcards · Mathematics · by lakesare
Part of Textbooks › Matroids: A Geometric Introduction (Gordon, McNulty) · 9 courses
[Matrices are matroids] Gordon and McNulty open the chapter on representable matroids with three questions about matrices and matroids. What are the three questions, and their answers?
Q1: do the linearly independent subsets of columns of a matrix always satisfy the independent set axioms? Yes. Example: the columns (1,0),(0,1),(1,1)(1,0), (0,1), (1,1)(1,0),(0,1),(1,1) give the uniform matroid U2,3U_{2,3}U2,3 . Q2: when do two different matrices give the same matroid? Sometimes, e.g. when one matrix is obtained from the other by row operations and nonzero column scalings. Example: [101011]\begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix}[100111] and [102012]\begin{bmatr…
[Matrices are matroids] Theorem 6.1 Let EEE be the set of columns of a matrix AAA with entries in a field F\mathbb{F}F , and let I\mathcal{I}I be the family of linearly independent subsets of EEE . Then … ?
I\mathcal{I}I is the family of independent sets of a matroid on EEE . Example: for the columns a=(1,0)a = (1,0)a=(1,0) , b=(2,0)b = (2,0)b=(2,0) , c=(0,1)c = (0,1)c=(0,1) over Q\mathbb{Q}Q , I={∅,a,b,c,ac,bc}\mathcal{I} = \{\emptyset, a, b, c, ac, bc\}I={∅,a,b,c,ac,bc} , a rank 2 matroid in which aaa and bbb are parallel.
[Matrices are matroids] Proposition 6.2 Let AAA be an r×nr \times nr×n matrix and A′A'A′ the reduced row echelon form of AAA . When is a subset of columns of AAA linearly independent?
Exactly when the corresponding columns of A′A'A′ are linearly independent. Row operations do not change the column dependences, so M[A]=M[A′]M[A] = M[A']M[A]=M[A′] .Example: [1212]\begin{bmatrix} 1 & 2 \\ 1 & 2 \end{bmatrix}[1122] reduces to [1200]\begin{bmatrix} 1 & 2 \\ 0 & 0 \end{bmatrix}[1020] ; in both, column 2 is twice column 1.
[Matrices are matroids] Theorem: the linearly independent subsets of columns of a matrix are the independent sets of a matroid.Why do the linearly independent sets satisfy (I1) ∅∈I\emptyset \in \mathcal{I}∅∈I and (I2) closure under subsets?
∅\emptyset∅ is linearly independent, and a subset of a linearly independent set is linearly independent. A nontrivial dependence ∑civi=0\sum c_i v_i = 0∑civi=0 among the vectors of a subset is also a nontrivial dependence of the whole set.
[Matrices are matroids] Theorem: the linearly independent subsets of columns of a matrix are the independent sets of a matroid.Let I,JI, JI,J be linearly independent sets of columns with ∣I∣=s<t=∣J∣|I| = s < t = |J|∣I∣=s<t=∣J∣ . How does the proof find x∈J−Ix \in J - Ix∈J−I with I∪xI \cup xI∪x linearly independent (axiom (I3))?
Row reduce the matrix of I∪JI \cup JI∪J (columns of III first) to [Is×sB10B2]\begin{bmatrix} I_{s \times s} & B_1 \\ 0 & B_2 \end{bmatrix}[Is×s0B1B2] ; the matrix has rank ≥t>s\ge t > s≥t>s , so B2B_2B2 has a nonzero entry. A column of J−IJ - IJ−I with a nonzero entry in B2B_2B2 is not in the span of the first sss columns, so adding it to III keeps independence. Row reduction keeps column dependences, so this holds in the original matrix too.Example: I={(1,0,0)}I = \{(1,0,0)\}I={(1,0,0)}…
[Matrices are matroids] Does the proof that linearly independent columns form a matroid depend on the field F\mathbb{F}F ?
No: subsets of vectors of Fm\mathbb{F}^mFm form a matroid for every field F\mathbb{F}F , finite fields included. The fact used (row reduction keeps column dependences) holds over every field.Example: over GF(2)GF(2)GF(2) , the columns (1,0),(0,1),(1,1)(1,0), (0,1), (1,1)(1,0),(0,1),(1,1) give U2,3U_{2,3}U2,3 .
[Matrices are matroids] When is a matroid MMM representable over the field F\mathbb{F}F ?
When there is a matrix AAA with entries in F\mathbb{F}F whose column dependences are exactly the dependences of MMM . The columns of AAA are the ground set, and the sets of columns that are linearly independent over F\mathbb{F}F are the independent sets of MMM . Notation: M=MF[A]M = M_{\mathbb{F}}[A]M=MF[A] , or M[A]M[A]M[A] when the field needs no mention.Example: U2,3=M[A]U_{2,3} = M[A]U2,3=M[A] for A=[101011]A = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix}A=[100111] , over every…
[Matrices are matroids] M[A]M[A]M[A] is the matroid on the columns of a matrix AAA . What are the following in M[A]M[A]M[A] ?
Rank of a set SSS of columns The matrix rank of the submatrix formed by SSS . Example: (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) have rank 2. Closure of SSS The columns in the linear span of SSS . Example: the closure of {(1,0),(0,1)}\{(1,0), (0,1)\}{(1,0),(0,1)} is every column of AAA . Flats Sets of columns containing every column in their linear span. Example: the columns with last coordinate 0 form a flat. Hyperplanes Flats of corank 1 (rank one less than the r…
[Matrices are matroids] Which theorem of linear algebra corresponds to each of these matroid axioms?
(B2), bases Every basis of a finite-dimensional vector space has the same size. Example: {(1,0),(0,1)}\{(1,0), (0,1)\}{(1,0),(0,1)} and {(1,1),(1,−1)}\{(1,1), (1,-1)\}{(1,1),(1,−1)} are bases of R2\mathbb{R}^2R2 , both of size 2. (I3), independent sets Every linearly independent set can be extended to a basis. Example: {(1,1,0)}\{(1,1,0)\}{(1,1,0)} extends to the basis {(1,1,0),(0,1,0),(0,0,1)}\{(1,1,0), (0,1,0), (0,0,1)\}{(1,1,0),(0,1,0),(0,0,1)} of R3\mathbb{R}^3R3 . (F2), flats The intersect…
[Matrices are matroids] Linear algebra version of the flat axiom (F3): if WWW is a kkk -dimensional subspace of VVV , the (k+1)(k+1)(k+1) -dimensional subspaces containing WWW partition V−WV - WV−W .Does this also hold when WWW is a translate of a kkk -dimensional subspace?
Yes. The translates of kkk -dimensional subspaces are the kkk -dimensional flats of the affine geometry AG(n,q)AG(n, q)AG(n,q) , and this partition property shows that the flats of AG(n,q)AG(n, q)AG(n,q) satisfy (F3).Example: in R2\mathbb{R}^2R2 , the lines through a point W={w}W = \{w\}W={w} partition R2−W\mathbb{R}^2 - WR2−W .
[Matrices are matroids] Over Q\mathbb{Q}Q , A=[1a0b0c1d1e0f0g1h0101−1111001001−11]A = \begin{bmatrix}\overset{a}{1} & \overset{b}{0} & \overset{c}{0} & \overset{d}{1} & \overset{e}{1} & \overset{f}{0} & \overset{g}{0} & \overset{h}{1} \\ 0 & 1 & 0 & 1 & -1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & -1 & 1\end{bmatrix}A=⎣⎡1a000b100c011d101e−100f110g1−11h11⎦⎤ Which point-line configuration does M[A]M[A]M[A] have?
Two 4-point lines abdeabdeabde and bcfgbcfgbcfg , two 3-point lines afhafhafh and cdhcdhcdh , rank 3. a,b,d,ea, b, d, ea,b,d,e all have last coordinate 0; b,c,f,gb, c, f, gb,c,f,g all have first coordinate 0; h=a+f=c+dh = a + f = c + dh=a+f=c+d .
[Matrices are matroids] Over Q\mathbb{Q}Q , A=[1a0b0c1d1e0f0g1h0101−1111001001−11]A = \begin{bmatrix}\overset{a}{1} & \overset{b}{0} & \overset{c}{0} & \overset{d}{1} & \overset{e}{1} & \overset{f}{0} & \overset{g}{0} & \overset{h}{1} \\ 0 & 1 & 0 & 1 & -1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & -1 & 1\end{bmatrix}A=⎣⎡1a000b100c011d101e−100f110g1−11h11⎦⎤ Why is M[A]M[A]M[A] a simple matroid?
No column is 000 (no loops), and no two columns are scalar multiples of each other (no parallel pairs).
[Matrices are matroids] Over Q\mathbb{Q}Q , A=[1a0b0c1d1e0f0g1h0101−1111001001−11]A = \begin{bmatrix}\overset{a}{1} & \overset{b}{0} & \overset{c}{0} & \overset{d}{1} & \overset{e}{1} & \overset{f}{0} & \overset{g}{0} & \overset{h}{1} \\ 0 & 1 & 0 & 1 & -1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & -1 & 1\end{bmatrix}A=⎣⎡1a000b100c011d101e−100f110g1−11h11⎦⎤ I={d,e}I = \{d, e\}I={d,e} and J={a,b,c}J = \{a, b, c\}J={a,b,c} are independent. Which elements x∈Jx \in Jx∈J give an independent I∪…
Only ccc . a,b,d,ea, b, d, ea,b,d,e all have last coordinate 0, so {a,d,e}\{a, d, e\}{a,d,e} and {b,d,e}\{b, d, e\}{b,d,e} have rank 2; c=(0,0,1)c = (0,0,1)c=(0,0,1) does not.
[Matrices are matroids] Over Q\mathbb{Q}Q , A=[1a0b0c1d1e0f0g1h0101−1111001001−11]A = \begin{bmatrix}\overset{a}{1} & \overset{b}{0} & \overset{c}{0} & \overset{d}{1} & \overset{e}{1} & \overset{f}{0} & \overset{g}{0} & \overset{h}{1} \\ 0 & 1 & 0 & 1 & -1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & -1 & 1\end{bmatrix}A=⎣⎡1a000b100c011d101e−100f110g1−11h11⎦⎤ Is {d,e,g}\{d, e, g\}{d,e,g} a basis of M[A]M[A]M[A] ?
Yes: the 3×33 \times 33×3 submatrix has determinant 2≠0\boldsymbol{2 \ne 0}2=0 . det[1101−1100−1]=1⋅1−1⋅(−1)+0=2\det \begin{bmatrix} 1 & 1 & 0 \\ 1 & -1 & 1 \\ 0 & 0 & -1 \end{bmatrix} = 1 \cdot 1 - 1 \cdot (-1) + 0 = 2det⎣⎡1101−1001−1⎦⎤=1⋅1−1⋅(−1)+0=2
[Matrices are matroids] Over Q\mathbb{Q}Q , A=[1a0b0c1d1e0f0g1h0101−1111001001−11]A = \begin{bmatrix}\overset{a}{1} & \overset{b}{0} & \overset{c}{0} & \overset{d}{1} & \overset{e}{1} & \overset{f}{0} & \overset{g}{0} & \overset{h}{1} \\ 0 & 1 & 0 & 1 & -1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & -1 & 1\end{bmatrix}A=⎣⎡1a000b100c011d101e−100f110g1−11h11⎦⎤ What is the closure of S={c,f}S = \{c, f\}S={c,f} ?
S‾=\overline{S} = S= {b,c,f,g}\{b, c, f, g\}{b,c,f,g} The linear span of c=(0,0,1)c = (0,0,1)c=(0,0,1) and f=(0,1,1)f = (0,1,1)f=(0,1,1) is the vectors with first coordinate 0: b=f−cb = f - cb=f−c , g=2c−fg = 2c - fg=2c−f .
[Matrices are matroids] Over Q\mathbb{Q}Q , A=[1a0b0c1d1e0f0g1h0101−1111001001−11]A = \begin{bmatrix}\overset{a}{1} & \overset{b}{0} & \overset{c}{0} & \overset{d}{1} & \overset{e}{1} & \overset{f}{0} & \overset{g}{0} & \overset{h}{1} \\ 0 & 1 & 0 & 1 & -1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & -1 & 1\end{bmatrix}A=⎣⎡1a000b100c011d101e−100f110g1−11h11⎦⎤ Check the semimodular law r(F1)+r(F2)≥r(F1∪F2)+r(F1∩F2)r(F_1) + r(F_2) \ge r(F_1 \cup F_2) + r(F_1 \cap F_2)r(F1)+r(F2)≥r(F1∪F2)+…
2+2≥3+02 + 2 \ge 3 + 02+2≥3+0 F1F_1F1 is a 3-point line, F2F_2F2 a 2-point line, F1∪F2F_1 \cup F_2F1∪F2 spans the plane and F1∩F2=∅F_1 \cap F_2 = \emptysetF1∩F2=∅ .
[Matrices are matroids] Over Q\mathbb{Q}Q , A=[1a0b0c1d1e0f0g1h0101−1111001001−11]A = \begin{bmatrix}\overset{a}{1} & \overset{b}{0} & \overset{c}{0} & \overset{d}{1} & \overset{e}{1} & \overset{f}{0} & \overset{g}{0} & \overset{h}{1} \\ 0 & 1 & 0 & 1 & -1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & -1 & 1\end{bmatrix}A=⎣⎡1a000b100c011d101e−100f110g1−11h11⎦⎤ Why is {a,d,f,g}\{a, d, f, g\}{a,d,f,g} a circuit of M[A]M[A]M[A] ?
2a−2d+f+g=02a - 2d + f + g = 02a−2d+f+g=0 is a dependence, and every 3-subset has nonzero determinant. 2(1,0,0)−2(1,1,0)+(0,1,1)+(0,1,−1)=(0,0,0)2(1,0,0) - 2(1,1,0) + (0,1,1) + (0,1,-1) = (0,0,0)2(1,0,0)−2(1,1,0)+(0,1,1)+(0,1,−1)=(0,0,0) . No three of a,d,f,ga, d, f, ga,d,f,g are on a line of the drawing.
[Matrices are matroids] Over Q\mathbb{Q}Q , A=[1a0b0c1d1e0f0g1h0101−1111001001−11]A = \begin{bmatrix}\overset{a}{1} & \overset{b}{0} & \overset{c}{0} & \overset{d}{1} & \overset{e}{1} & \overset{f}{0} & \overset{g}{0} & \overset{h}{1} \\ 0 & 1 & 0 & 1 & -1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & -1 & 1\end{bmatrix}A=⎣⎡1a000b100c011d101e−100f110g1−11h11⎦⎤ How many bases, independent sets and flats does M[A]M[A]M[A] have?
46 bases, 83 independent sets, 24 flats. Bases: (83)=56\binom{8}{3} = 56(38)=56 triples, minus 4+44 + 44+4 on the two 4-point lines and 1+11 + 11+1 on the two 3-point lines. Independent sets: 46+(82)+(81)+(80)=46+3746 + \binom{8}{2} + \binom{8}{1} + \binom{8}{0} = 46 + 3746+(28)+(18)+(08)=46+37 .Flats: ∅\emptyset∅ , 8 points, 14 lines (2 four-point, 2 three-point, 10 two-point), and EEE . (The book counts 9 two-point lines and 23 flats; the two-point lines are ac,ag,bh,ce,df,dg,ef,eg,eh,gha…
[Matrices are matroids] Over Q\mathbb{Q}Q , A=[1a0b0c1d1e0f0g1h0101−1111001001−11]A = \begin{bmatrix}\overset{a}{1} & \overset{b}{0} & \overset{c}{0} & \overset{d}{1} & \overset{e}{1} & \overset{f}{0} & \overset{g}{0} & \overset{h}{1} \\ 0 & 1 & 0 & 1 & -1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & -1 & 1\end{bmatrix}A=⎣⎡1a000b100c011d101e−100f110g1−11h11⎦⎤ The 3×33 \times 33×3 determinants of AAA take the values 0,±1,±2,30, \pm 1, \pm 2, 30,±1,±2,3 . Over which fields does AAA give the s…
Over fields of characteristic 0 or greater than 3. Characteristic 3: det(e,g,h)=3=0\det(e, g, h) = 3 = 0det(e,g,h)=3=0 , so {e,g,h}\{e, g, h\}{e,g,h} becomes dependent.Characteristic 2: determinants ±2\pm 2±2 vanish; e.g. d=e=(1,1,0)d = e = (1,1,0)d=e=(1,1,0) and f=g=(0,1,1)f = g = (0,1,1)f=g=(0,1,1) , so d,ed, ed,e and f,gf, gf,g become parallel pairs.
[Matrices are matroids] Theorem 6.4 (Linear Algebra Theorem) III is a linearly independent set and SSS a spanning set of a vector space VVV , with I⊆SI \subseteq SI⊆S . Then … ?
There is a basis BBB with I⊆B⊆SI \subseteq B \subseteq SI⊆B⊆S . Example: in R2\mathbb{R}^2R2 , I={(1,1)}I = \{(1,1)\}I={(1,1)} , S={(1,1),(1,0),(2,2)}S = \{(1,1), (1,0), (2,2)\}S={(1,1),(1,0),(2,2)} : B={(1,1),(1,0)}B = \{(1,1), (1,0)\}B={(1,1),(1,0)} .
[Matrices are matroids] In a vector space, if III is linearly independent, SSS is spanning and I⊆SI \subseteq SI⊆S , then there is a basis BBB with I⊆B⊆SI \subseteq B \subseteq SI⊆B⊆S .Does the matroid version (independent III ⊆\subseteq⊆ spanning SSS ) hold in every matroid?
Yes. Extend III to a maximal independent subset BBB of SSS ; then r(B)=r(S)=r(M)r(B) = r(S) = r(M)r(B)=r(S)=r(M) , so BBB is a basis.Example: U2,3U_{2,3}U2,3 on {a,b,c}\{a, b, c\}{a,b,c} , I={a}I = \{a\}I={a} , S={a,b}S = \{a, b\}S={a,b} : B={a,b}B = \{a, b\}B={a,b} .
[Matrices are matroids] eee is a column of a matrix AAA , and A−eA - eA−e is AAA with column eee removed. Which matroid does A−eA - eA−e represent?
M[A]−e=M[A−e]M[A] - e = M[A - e]M[A]−e=M[A−e] : deletion is removing the column. Example: removing (1,1)(1,1)(1,1) from the columns (1,0),(0,1),(1,1)(1,0), (0,1), (1,1)(1,0),(0,1),(1,1) of U2,3U_{2,3}U2,3 leaves U2,2U_{2,2}U2,2 .
[Matrices are matroids] eee is a column of a matrix AAA and not a loop of M[A]M[A]M[A] . How is the matrix A/eA/eA/e representing the contraction M[A]/eM[A]/eM[A]/e built?
Row reduce AAA so that column eee becomes (1,0,…,0)(1, 0, \dots, 0)(1,0,…,0) ; then remove column eee and the first row. Example: A=[101011]A = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix}A=[100111] (columns a,b,ea, b, ea,b,e ). R2→R2−R1R_2 \to R_2 - R_1R2→R2−R1 gives e=(1,0)e = (1, 0)e=(1,0) and b=(0,1)b = (0, 1)b=(0,1) , a=(1,−1)a = (1, -1)a=(1,−1) ; then A/e=[−11]A/e = \begin{bmatrix} -1 & 1 \end{bmatrix}A/e=[−11] , which represents U1,2=U2,3/eU_{1,2} = U_{2,3}/eU1,2=U2,3/e…
[Matrices are matroids] Proposition 6.5 eee is a column of a matrix AAA , neither a loop nor an isthmus of M[A]M[A]M[A] ; A−eA - eA−e removes column eee , and A/eA/eA/e removes column eee and row 1 after row reducing eee to (1,0,…,0)(1, 0, \dots, 0)(1,0,…,0) . Then … ?
M[A]−e=M[A−e]M[A] - e = M[A - e]M[A]−e=M[A−e] and M[A]/e=M[A/e]M[A]/e = M[A/e]M[A]/e=M[A/e] .
[Matrices are matroids] BBB is AAA row reduced so that column eee is (1,0,…,0)(1, 0, \dots, 0)(1,0,…,0) ; A/eA/eA/e is BBB without column eee and row 1. Recall: III is independent in M/eM/eM/e iff I∪eI \cup eI∪e is independent in MMM .Why is I∪eI \cup eI∪e independent in M[A]M[A]M[A] when III is linearly independent in A/eA/eA/e ?
From ∑aici+aee=0\sum a_i c_i + a_e e = 0∑aici+aee=0 in BBB , rows 2,3,…2, 3, \dots2,3,… give ∑aici=0\sum a_i c_i = 0∑aici=0 in A/eA/eA/e , so all ai=0a_i = 0ai=0 ; then aee=0a_e e = 0aee=0 forces ae=0a_e = 0ae=0 . eee has 0 in every row except row 1, so eee does not appear in rows 2,3,…2, 3, \dots2,3,… . AAA and BBB have the same column dependences.
[Matrices are matroids] BBB is AAA row reduced so that column eee is (1,0,…,0)(1, 0, \dots, 0)(1,0,…,0) ; A/eA/eA/e is BBB without column eee and row 1.A set D={c1,…,ck}D = \{c_1, \dots, c_k\}D={c1,…,ck} of columns has a nontrivial dependence ∑aici=0\sum a_i c_i = 0∑aici=0 in A/eA/eA/e . How does the proof turn it into a dependence of D∪eD \cup eD∪e in AAA ?
Choose the coefficient of eee to cancel row 1: ae=−∑airia_e = -\sum a_i r_iae=−∑airi , where rir_iri is the row 1 entry of cic_ici in BBB . Then ∑aici+aee=0\sum a_i c_i + a_e e = 0∑aici+aee=0 in all rows of BBB , hence in AAA (same column dependences), so D∪eD \cup eD∪e is dependent in M[A]M[A]M[A] .
[Matrices are matroids] A=[1a0b0c1d1e0102−100101]A = \begin{bmatrix}\overset{a}{1} & \overset{b}{0} & \overset{c}{0} & \overset{d}{1} & \overset{e}{1} \\ 0 & 1 & 0 & 2 & -1 \\ 0 & 0 & 1 & 0 & 1\end{bmatrix}A=⎣⎡1a000b100c011d201e−11⎦⎤ , and row reducing column eee to (1,0,0)(1,0,0)(1,0,0) and removing it with row 1 gives A/e=[1a1b0c3d−101−1]A/e = \begin{bmatrix}\overset{a}{1} & \overset{b}{1} & \overset{c}{0} & \overset{d}{3} \\ -1 & 0 & 1 & -1\end{bmatrix}A/e=[1a−11b00c13d−1] (row 1…
−3b+c+d−e=0\boldsymbol{-3b + c + d - e = 0}−3b+c+d−e=0 Row 1 entries of b,c,db, c, db,c,d are 0,0,10, 0, 10,0,1 , so ae=−(0+0+1)=−1a_e = -(0 + 0 + 1) = -1ae=−(0+0+1)=−1 . Check: −3(0,1,0)+(0,0,1)+(1,2,0)−(1,−1,1)=(0,0,0)-3(0,1,0) + (0,0,1) + (1,2,0) - (1,-1,1) = (0,0,0)−3(0,1,0)+(0,0,1)+(1,2,0)−(1,−1,1)=(0,0,0) .
[Matrices are matroids] How do you recognise a loop and an isthmus eee of M[A]M[A]M[A] in the matrix AAA ?
Loop: column eee is all zeros. Isthmus: after row reducing so that column eee has exactly one nonzero entry, that entry is the only nonzero entry of its row. Example: in [101010]\begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}[100110] the middle column is an isthmus: no other column uses row 2, so the middle column is in every basis.
[Matrices are matroids] Theorem 6.6 DDD is an r×(n−r)r \times (n - r)r×(n−r) matrix over a field F\mathbb{F}F . The matrix A=[Ir×r∣D]A = [I_{r \times r} \mid D]A=[Ir×r∣D] represents MMM exactly when which matrix represents the dual M∗M^*M∗ ?
A∗=[−DT∣I(n−r)×(n−r)]\boldsymbol{A^* = [-D^T \mid I_{(n-r) \times (n-r)}]}A∗=[−DT∣I(n−r)×(n−r)] , over the same field. So the dual of an F\mathbb{F}F -representable matroid is F\mathbb{F}F -representable.Example: A=[101011]A = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix}A=[100111] gives U2,3U_{2,3}U2,3 ; A∗=[−1−11]A^* = \begin{bmatrix} -1 & -1 & 1 \end{bmatrix}A∗=[−1−11] gives U1,3=U2,3∗U_{1,3} = U_{2,3}^*U1,3=U2,3∗ .
[Matrices are matroids] Which three linear algebra facts about the null space N(A)N(A)N(A) of an r×nr \times nr×n matrix AAA does the proof that duals are representable use?
Null vectors are dependences of the columns Ax=∑i=1nxiciAx = \sum_{i=1}^n x_i c_iAx=∑i=1nxici , where cic_ici are the columns, so x∈N(A)x \in N(A)x∈N(A) iff ∑xici=0\sum x_i c_i = 0∑xici=0 . Example: A=[101011]A = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix}A=[100111] , x=(1,1,−1)x = (1, 1, -1)x=(1,1,−1) : c1+c2−c3=0c_1 + c_2 - c_3 = 0c1+c2−c3=0 . Rank–Nullity Theorem If AAA has rank rrr , then N(A)N(A)N(A) is an (n−r)(n - r)(n−r) -dimensional subspace of Fn\mathbb{F}^nFn . E…
[Matrices are matroids] Lemma 6.8 AAA is an r×nr \times nr×n matrix of rank rrr , {v1,…,vk}\{v_1, \dots, v_k\}{v1,…,vk} is a basis of the null space N(A)N(A)N(A) , and A∗A^*A∗ is the matrix with rows v1,…,vkv_1, \dots, v_kv1,…,vk . Then … ?
M[A∗]=M[A]∗\boldsymbol{M[A^*] = M[A]^*}M[A∗]=M[A]∗ : a set SSS of columns of A∗A^*A∗ is a basis iff the complementary columns E−SE - SE−S of AAA are a basis of M[A]M[A]M[A] . Example: A=[101011]A = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix}A=[100111] , N(A)N(A)N(A) has basis {(1,1,−1)}\{(1, 1, -1)\}{(1,1,−1)} , and A∗=[11−1]A^* = \begin{bmatrix} 1 & 1 & -1 \end{bmatrix}A∗=[11−1] represents U1,3=U2,3∗U_{1,3} = U_{2,3}^*U1,3=U2,3∗ .
[Matrices are matroids] Lemma: if the rows of A∗A^*A∗ are a basis of the null space N(A)N(A)N(A) of a rank rrr matrix AAA , then M[A∗]=M[A]∗M[A^*] = M[A]^*M[A∗]=M[A]∗ . B={c1,…,cr}B = \{c_1, \dots, c_r\}B={c1,…,cr} is a basis of M[A]M[A]M[A] and cr+i=∑j=1rai,jcjc_{r+i} = \sum_{j=1}^r a_{i,j} c_jcr+i=∑j=1rai,jcj for i=1,…,n−ri = 1, \dots, n - ri=1,…,n−r . Which basis of N(A)N(A)N(A) does the proof build?
vi=(ai,1,…,ai,r,0,…,−1,…,0)v_i = (a_{i,1}, \dots, a_{i,r}, 0, \dots, -1, \dots, 0)vi=(ai,1,…,ai,r,0,…,−1,…,0) , with −1-1−1 in position r+ir + ir+i . Avi=∑jai,jcj−cr+i=0A v_i = \sum_j a_{i,j} c_j - c_{r+i} = 0Avi=∑jai,jcj−cr+i=0 ; the last n−rn - rn−r coordinates show the viv_ivi are independent; there are n−r=dimN(A)n - r = \dim N(A)n−r=dimN(A) of them (Rank–Nullity).Example: c1=(1,0)c_1 = (1,0)c1=(1,0) , c2=(0,1)c_2 = (0,1)c2=(0,1) , c3=(2,3)=2c1+3c2c_3 = (2,3) = 2c_1 + 3c_2c3=(2…
[Matrices are matroids] Lemma: if the rows of A∗A^*A∗ are a basis of the null space N(A)N(A)N(A) of a rank rrr matrix AAA , then M[A∗]=M[A]∗M[A^*] = M[A]^*M[A∗]=M[A]∗ . Proof setup: for a basis B={c1,…,cr}B = \{c_1, \dots, c_r\}B={c1,…,cr} of M[A]M[A]M[A] , the rows vi=(ai,1,…,ai,r,0,…,−1,…,0)v_i = (a_{i,1}, \dots, a_{i,r}, 0, \dots, -1, \dots, 0)vi=(ai,1,…,ai,r,0,…,−1,…,0) come from cr+i=∑jai,jcjc_{r+i} = \sum_j a_{i,j} c_jcr+i=∑jai,jcj .How does the proof finish?
In A∗A^*A∗ , the columns cr+1,…,cnc_{r+1}, \dots, c_ncr+1,…,cn form −I-I−I , so E−BE - BE−B is a basis of M[A∗]M[A^*]M[A∗] . Any other basis of N(A)N(A)N(A) gives a row-equivalent matrix, hence the same matroid.So for every basis BBB of M[A]M[A]M[A] , E−BE - BE−B is a basis of M[A∗]M[A^*]M[A∗] , whichever basis of N(A)N(A)N(A) was chosen.
[Matrices are matroids] A=[1a−1b1c0d2e−3f0g1−10111−12−2211−10]A = \begin{bmatrix}\overset{a}{1} & \overset{b}{-1} & \overset{c}{1} & \overset{d}{0} & \overset{e}{2} & \overset{f}{-3} & \overset{g}{0} \\ 1 & -1 & 0 & 1 & 1 & 1 & -1 \\ 2 & -2 & 2 & 1 & 1 & -1 & 0\end{bmatrix}A=⎣⎡1a12−1b−1−21c020d112e11−3f1−10g−10⎦⎤ row reduces to A′=[1a−1b0c0d4e−4f−1g0010−2110001−350]A' = \begin{bmatrix}\overset{a}{1} & \overset{b}{-1} & \overset{c}{0} & \overset{d}{0} & \overset{e}{4} & \overset{…
Columns b,e,f,gb, e, f, gb,e,f,g , so {b,e,f,g}\{b, e, f, g\}{b,e,f,g} is a basis of M[(A′)∗]M[(A')^*]M[(A′)∗] , the complement of the basis {a,c,d}\{a, c, d\}{a,c,d} of M[A]M[A]M[A] . (A′)∗=[1a1b0c0d0e0f0g−402310040−1−501010−10001](A')^* = \begin{bmatrix}\overset{a}{1} & \overset{b}{1} & \overset{c}{0} & \overset{d}{0} & \overset{e}{0} & \overset{f}{0} & \overset{g}{0} \\ -4 & 0 & 2 & 3 & 1 & 0 & 0 \\ 4 & 0 & -1 & -5 & 0 & 1 & 0 \\ 1 & 0 & -1 & 0 & 0 & 0 & 1\end{bmatrix}(A′)∗=⎣⎡1a−4…
[Matrices are matroids] The rows of (A′)∗(A')^*(A′)∗ and of (A′′)∗(A'')^*(A′′)∗ are two different bases of the null space N(A)N(A)N(A) of a matrix AAA .Why do (A′)∗(A')^*(A′)∗ and (A′′)∗(A'')^*(A′′)∗ represent the same matroid?
Both have row space N(A)N(A)N(A) , so they are row equivalent, and row equivalent matrices have the same column dependences. Example: [11−1]\begin{bmatrix} 1 & 1 & -1 \end{bmatrix}[11−1] and [22−2]\begin{bmatrix} 2 & 2 & -2 \end{bmatrix}[22−2] both give U1,3U_{1,3}U1,3 .
[Representing representable matroids] For graphs, Whitney's 2-isomorphism theorem says when two graphs give the same cycle matroid. What is the corresponding question for matrices, and how good is its answer?
When do two matrices A,BA, BA,B give M[A]=M[B]M[A] = M[B]M[A]=M[B] ? There is no equally clean answer, but some operations are known to keep the matroid. Row operations and nonzero column scalings keep the matroid, so a representing matrix can be simplified.
[Representing representable matroids] Proposition 6.9 AAA is an r×nr \times nr×n matrix over F\mathbb{F}F , BBB an r×rr \times rr×r invertible matrix, DDD an n×nn \times nn×n invertible diagonal matrix. Which matrices have the same column dependences as AAA ?
BA\boldsymbol{BA}BA (row operations) and AD\boldsymbol{AD}AD (multiplying each column by a nonzero scalar). Example: A=[1100]A = \begin{bmatrix} 1 & 1 \\ 0 & 0 \end{bmatrix}A=[1010] , D=diag(1,5)D = \operatorname{diag}(1, 5)D=diag(1,5) : AD=[1500]AD = \begin{bmatrix} 1 & 5 \\ 0 & 0 \end{bmatrix}AD=[1050] ; in both, the two columns are parallel.
[Representing representable matroids] BBB is an invertible r×rr \times rr×r matrix, D=diag(d1,…,dn)D = \operatorname{diag}(d_1, \dots, d_n)D=diag(d1,…,dn) invertible, and c1,…,cnc_1, \dots, c_nc1,…,cn are the columns of AAA .Why do BABABA and ADADAD have the same column dependences as AAA ?
∑xiBci=B∑xici\sum x_i B c_i = B \sum x_i c_i∑xiBci=B∑xici is 0 iff ∑xici=0\sum x_i c_i = 0∑xici=0 ; and ∑xi(dici)=0\sum x_i (d_i c_i) = 0∑xi(dici)=0 iff ∑(xidi)ci=0\sum (x_i d_i) c_i = 0∑(xidi)ci=0 , with xidi≠0x_i d_i \ne 0xidi=0 iff xi≠0x_i \ne 0xi=0 . BBB invertible means Bv=0Bv = 0Bv=0 only for v=0v = 0v=0 .
[Representing representable matroids] MMM is a rank rrr matroid on nnn points, represented by some m×nm \times nm×n matrix. Which three simplifications of the representing matrix AAA follow from row operations and column scaling?
AAA is r×nr \times nr×n Row reducing gives m−rm - rm−r zero rows, which can be removed. Example: a 5×75 \times 75×7 matrix of rank 3 becomes 3×73 \times 73×7 . The first rrr columns form an identity matrix After ordering the columns so that the first rrr are a basis of MMM , row reduce. Example: A=[I3∣… ]A = [I_3 \mid \dots]A=[I3∣…] when abcabcabc is a basis. The first nonzero entry of each column is 1 Multiply column cic_ici by ai−1a_i^{-1}ai−1 , where aia_iai is the first nonzero entry of…
[Representing representable matroids] Over Q\mathbb{Q}Q , row reducing a representing matrix of a rank 3 matroid MMM and dropping the zero rows gives A3=[1a0b0c2d2e3f1g01044050016090]A_3 = \begin{bmatrix}\overset{a}{1} & \overset{b}{0} & \overset{c}{0} & \overset{d}{2} & \overset{e}{2} & \overset{f}{3} & \overset{g}{1} \\ 0 & 1 & 0 & 4 & 4 & 0 & 5 \\ 0 & 0 & 1 & 6 & 0 & 9 & 0\end{bmatrix}A3=⎣⎡1a000b100c012d462e403f091g50⎦⎤ .Which matrix do you get by making the first nonzero entry of…
Divide columns d,e,fd, e, fd,e,f by 2,2,32, 2, 32,2,3 : A4=[1a0b0c1d1e1f1g01022050013030]A_4 = \begin{bmatrix}\overset{a}{1} & \overset{b}{0} & \overset{c}{0} & \overset{d}{1} & \overset{e}{1} & \overset{f}{1} & \overset{g}{1} \\ 0 & 1 & 0 & 2 & 2 & 0 & 5 \\ 0 & 0 & 1 & 3 & 0 & 3 & 0\end{bmatrix}A4=⎣⎡1a000b100c011d231e201f031g50⎦⎤
[Representing representable matroids] A4=[1a0b0c1d1e1f1g01022050013030]A_4 = \begin{bmatrix}\overset{a}{1} & \overset{b}{0} & \overset{c}{0} & \overset{d}{1} & \overset{e}{1} & \overset{f}{1} & \overset{g}{1} \\ 0 & 1 & 0 & 2 & 2 & 0 & 5 \\ 0 & 0 & 1 & 3 & 0 & 3 & 0\end{bmatrix}A4=⎣⎡1a000b100c011d231e201f031g50⎦⎤ over Q\mathbb{Q}Q .How can the entry 2 of column ddd in row 2 become 1 without changing the identity in columns a,b,ca, b, ca,b,c or the matroid?
Multiply row 2 by 12\frac{1}{2}21 , then multiply column bbb by 2. The row operation turns column bbb into (0,12,0)(0, \frac{1}{2}, 0)(0,21,0) ; the column scaling restores (0,1,0)(0, 1, 0)(0,1,0) . Similarly row 3 times 13\frac{1}{3}31 and column ccc times 3 turn the 3 of column ddd into 1.
[Representing representable matroids] MMM has lines abegabegabeg , acfacfacf , bdfbdfbdf , cdecdecde , and over Q\mathbb{Q}Q , A5=[1a0b0c1d1e1f1g010110520011010]A_5 = \begin{bmatrix}\overset{a}{1} & \overset{b}{0} & \overset{c}{0} & \overset{d}{1} & \overset{e}{1} & \overset{f}{1} & \overset{g}{1} \\ 0 & 1 & 0 & 1 & 1 & 0 & \tfrac{5}{2} \\ 0 & 0 & 1 & 1 & 0 & 1 & 0\end{bmatrix}A5=⎣⎡1a000b100c011d111e101f011g250⎦⎤ represents MMM .Can the entry 52\frac{5}{2}25 be changed to 1 by more…
No: making it 1 (row 2 times 25\frac{2}{5}52 ) changes columns ddd and eee , and those changes can not all be undone. So A5A_5A5 is as simple as the representation of MMM gets.
[Representing representable matroids] MMM has lines abegabegabeg , acfacfacf , bdfbdfbdf , cdecdecde , represented over Q\mathbb{Q}Q by A5A_5A5 with column g=(1,x,0)g = (1, x, 0)g=(1,x,0) and x=52x = \frac{5}{2}x=25 ; the other columns are a,b,ca, b, ca,b,c (identity), d=(1,1,1)d = (1,1,1)d=(1,1,1) , e=(1,1,0)e = (1,1,0)e=(1,1,0) , f=(1,0,1)f = (1,0,1)f=(1,0,1) .For which xxx does the matrix still represent MMM , and why?
Every x≠0,1x \ne 0, 1x=0,1 . ggg lies on only one line ( ababab ), so ggg can be any other point of that line: a geometric degree of freedom. x=0x = 0x=0 makes g=ag = ag=a and x=1x = 1x=1 makes g=eg = eg=e (parallel pairs).
[Representing representable matroids] This matroid is M−3M_{\sqrt{-3}}M−3 . How many points and how many 3-point lines does M−3M_{\sqrt{-3}}M−3 have?
8 points, 8 three-point lines: abf,ace,bcg,bde,dfg,agh,cdh,efhabf, ace, bcg, bde, dfg, agh, cdh, efhabf,ace,bcg,bde,dfg,agh,cdh,efh . Rank 3; the line efhefhefh is drawn curved.
[Representing representable matroids] M−3M_{\sqrt{-3}}M−3 is a rank 3 matroid on a,…,ha, \dots, ha,…,h with 3-point lines abf,ace,bcg,bde,dfg,agh,cdh,efhabf, ace, bcg, bde, dfg, agh, cdh, efhabf,ace,bcg,bde,dfg,agh,cdh,efh .To build a 3×83 \times 83×8 representing matrix, why may a,b,c,da, b, c, da,b,c,d be taken as (1,0,0),(0,1,0),(0,0,1),(1,1,1)(1,0,0), (0,1,0), (0,0,1), (1,1,1)(1,0,0),(0,1,0),(0,0,1),(1,1,1) ?
Row reduce so that a,b,ca, b, ca,b,c form III ; then scale the rows, and rescale columns a,b,ca, b, ca,b,c , to make d=(1,1,1)d = (1,1,1)d=(1,1,1) . abcabcabc is a basis. ddd is on none of the lines ab,ac,bcab, ac, bcab,ac,bc , so no coordinate of ddd is 0.
[Representing representable matroids] In M−3M_{\sqrt{-3}}M−3 , a=(1,0,0)a = (1,0,0)a=(1,0,0) , b=(0,1,0)b = (0,1,0)b=(0,1,0) , c=(0,0,1)c = (0,0,1)c=(0,0,1) , d=(1,1,1)d = (1,1,1)d=(1,1,1) , and eee lies on the lines aceaceace and bdebdebde . First nonzero entries are 1.What are the coordinates of eee ?
e=(1,0,1)\boldsymbol{e = (1, 0, 1)}e=(1,0,1) On line acacac : second coordinate 0. On line bdbdbd : first coordinate = last coordinate.
[Representing representable matroids] In M−3M_{\sqrt{-3}}M−3 , a,b,ca, b, ca,b,c are the identity columns, d=(1,1,1)d = (1,1,1)d=(1,1,1) , and the lines include abfabfabf , bcgbcgbcg and dfgdfgdfg .What do fff and ggg look like?
f=(1,x,0)\boldsymbol{f = (1, x, 0)}f=(1,x,0) and g=(0,1,11−x)\boldsymbol{g = (0, 1, \frac{1}{1-x})}g=(0,1,1−x1) , with xxx not yet determined. fff on ababab , g=(0,1,y)g = (0, 1, y)g=(0,1,y) on bcbcbc ; dfgdfgdfg collinear: det[1101x110y]=xy+1−y=0\det \begin{bmatrix} 1 & 1 & 0 \\ 1 & x & 1 \\ 1 & 0 & y \end{bmatrix} = xy + 1 - y = 0det⎣⎡1111x001y⎦⎤=xy+1−y=0 .
[Representing representable matroids] In M−3M_{\sqrt{-3}}M−3 : a,b,ca, b, ca,b,c identity, d=(1,1,1)d = (1,1,1)d=(1,1,1) , e=(1,0,1)e = (1,0,1)e=(1,0,1) , f=(1,x,0)f = (1,x,0)f=(1,x,0) , g=(0,1,11−x)g = (0,1,\frac{1}{1-x})g=(0,1,1−x1) , h=(1,1,z)h = (1,1,z)h=(1,1,z) (from line cdhcdhcdh ). The remaining lines through hhh are aghaghagh and efhefhefh .What do aghaghagh and efhefhefh force?
aghaghagh forces z=11−xz = \frac{1}{1-x}z=1−x1 ; efhefhefh forces x2−x+1=0x^2 - x + 1 = 0x2−x+1=0 . efhefhefh : det[1110x11011−x]=x1−x+1−x=0\det \begin{bmatrix} 1 & 1 & 1 \\ 0 & x & 1 \\ 1 & 0 & \frac{1}{1-x} \end{bmatrix} = \frac{x}{1-x} + 1 - x = 0det⎣⎡1011x0111−x1⎦⎤=1−xx+1−x=0 ; multiply by 1−x1 - x1−x .
[Representing representable matroids] Proposition 6.12 Over which fields F\mathbb{F}F is the matroid M−3M_{\sqrt{-3}}M−3 (8 points, lines abf,ace,bcg,bde,dfg,agh,cdh,efhabf, ace, bcg, bde, dfg, agh, cdh, efhabf,ace,bcg,bde,dfg,agh,cdh,efh ) representable?
Exactly when F\mathbb{F}F contains a root of x2−x+1x^2 - x + 1x2−x+1 . The roots are 1±−32\frac{1 \pm \sqrt{-3}}{2}21±−3 , which gives the name.Example: not over R\mathbb{R}R (discriminant −3<0-3 < 0−3<0 ); over C\mathbb{C}C yes; over GF(3)GF(3)GF(3) yes, x=2x = 2x=2 since 4−2+1=3=04 - 2 + 1 = 3 = 04−2+1=3=0 .
[Representing representable matroids] Both the matroid of the matrix [100110010101−1111001001−11]\begin{bmatrix} 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & -1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & -1 & 1 \end{bmatrix}⎣⎡1000100011101−1001101−1111⎦⎤ and M−3M_{\sqrt{-3}}M−3 depend on the field. What is the fundamental difference?
For the matrix, the fixed matrix gives different matroids over different fields; for M−3M_{\sqrt{-3}}M−3 , the matroid itself restricts which fields can represent it. The matrix changes in characteristic 2 and 3, but its matroid may still have other representations there. M−3M_{\sqrt{-3}}M−3 has no representation at all over a field without a root of x2−x+1x^2 - x + 1x2−x+1 .
[Representing representable matroids] BBB is a basis of a matroid MMM and x∉Bx \notin Bx∈/B .What is the basic circuit of xxx with respect to BBB ?
The unique circuit CxC_xCx contained in B∪xB \cup xB∪x . Example: in U2,3U_{2,3}U2,3 on {a,b,c}\{a, b, c\}{a,b,c} with B={a,b}B = \{a, b\}B={a,b} , Cc={a,b,c}C_c = \{a, b, c\}Cc={a,b,c} .
[Representing representable matroids] In M−3M_{\sqrt{-3}}M−3 , with basis B={a,b,c}B = \{a, b, c\}B={a,b,c} , what are the basic circuits of d,e,f,g,hd, e, f, g, hd,e,f,g,h ?
d:abcd, e:ace, f:abf, g:bcg, h:abch\boldsymbol{d: abcd, \ e: ace, \ f: abf, \ g: bcg, \ h: abch}d:abcd, e:ace, f:abf, g:bcg, h:abch e,f,ge, f, ge,f,g are on lines through two of a,b,ca, b, ca,b,c ; ddd and hhh are on no such line, so their basic circuits are 4-sets.
[Representing representable matroids] B={b1,…,br}B = \{b_1, \dots, b_r\}B={b1,…,br} is a basis of a matroid MMM on nnn points, and CxC_xCx is the basic circuit of x∉Bx \notin Bx∈/B .What are the basic-circuit incidence matrix A′A'A′ and its bipartite graph GGG ?
A′A'A′ : rows b1,…,brb_1, \dots, b_rb1,…,br , columns x∉Bx \notin Bx∈/B , entry (bi,x)(b_i, x)(bi,x) is ∗*∗ (nonzero) if bi∈Cxb_i \in C_xbi∈Cx and 000 otherwise. GGG : vertices EEE , edge bixb_i xbix for each ∗*∗ . Example ( M−3M_{\sqrt{-3}}M−3 , B=abcB = abcB=abc ): A′=defgha∗∗∗0∗b∗0∗∗∗c∗∗0∗∗A' = \begin{array}{c|ccccc} & d & e & f & g & h \\ \hline a & * & * & * & 0 & * \\ b & * & 0 & * & * & * \\ c & * & * & 0 & * & * \end{array}A′=abcd∗∗∗e∗0∗f∗∗0g0∗∗h∗∗∗
[Representing representable matroids] Representing matrix A=[I∣A′]A = [I \mid A']A=[I∣A′] , where column xxx of A′A'A′ gives the coordinates of xxx in the basis B={b1,…,br}B = \{b_1, \dots, b_r\}B={b1,…,br} .Why is entry iii of column xxx zero exactly when bi∉Cxb_i \notin C_xbi∈/Cx (the basic circuit of xxx )?
x=∑iaibix = \sum_i a_i b_ix=∑iaibi , and the circuit in B∪xB \cup xB∪x is xxx together with the bib_ibi with ai≠0a_i \ne 0ai=0 . So the zero pattern of A′A'A′ is fixed by MMM , and the ∗*∗ entries are never 0.Example: in M−3M_{\sqrt{-3}}M−3 , e=a+ce = a + ce=a+c and Ce=aceC_e = aceCe=ace , so the bbb -entry of eee is 0.
[Representing representable matroids] What are the steps of the coordinatizing path algorithm for a representable matroid MMM ?
Pick a basis BBB Example ( M−3M_{\sqrt{-3}}M−3 ): B=abcB = abcB=abc . Find the basic circuits For each x∉Bx \notin Bx∈/B , the unique circuit Cx⊆B∪xC_x \subseteq B \cup xCx⊆B∪x . Example: d: abcdd{:}\ abcdd: abcd , e: acee{:}\ acee: ace , f: abff{:}\ abff: abf , g: bcgg{:}\ bcgg: bcg , h: abchh{:}\ abchh: abch . Record the incidences In the basic-circuit incidence matrix A′A'A′ (entry ∗*∗ if bi∈Cxb_i \in C_xbi∈Cx , else 0) and the bipartite graph GGG . Example: A′=defgha∗∗∗0∗b∗0∗∗∗c∗∗…
[Representing representable matroids] In the coordinatizing path algorithm, the bipartite graph GGG has the nnn points of a rank rrr matroid as vertices ( rrr basis points, n−rn - rn−r others).How many entries of A′A'A′ are set to 1?
n−1\boldsymbol{n - 1}n−1 (if GGG is connected) A spanning tree on r+(n−r)=nr + (n - r) = nr+(n−r)=n vertices has n−1n - 1n−1 edges.Example: M−3M_{\sqrt{-3}}M−3 has n=8n = 8n=8 , so 7 entries become 1.
[Representing representable matroids] In the coordinatizing path algorithm, what replaces the spanning tree when the bipartite graph GGG is disconnected, and how is it said in matroid terms?
A spanning forest of GGG , i.e. a basis of the cycle matroid M(G)M(G)M(G) . Example: if GGG has two components with 555 and 333 vertices, a spanning forest has 4+2=64 + 2 = 64+2=6 edges.
[Representing representable matroids] The entries of the basic-circuit incidence matrix that correspond to the edges of a spanning tree of its bipartite graph form a coordinatizing path.
Example: for M−3M_{\sqrt{-3}}M−3 with basis abcabcabc , the 7 entries (a,f),(a,h),(b,d),(b,g),(c,e),(c,g),(c,h)(a,f), (a,h), (b,d), (b,g), (c,e), (c,g), (c,h)(a,f),(a,h),(b,d),(b,g),(c,e),(c,g),(c,h) .
[Representing representable matroids] Coordinatizing path for M−3M_{\sqrt{-3}}M−3 (lines abf,ace,bcg,bde,dfg,agh,cdh,efhabf, ace, bcg, bde, dfg, agh, cdh, efhabf,ace,bcg,bde,dfg,agh,cdh,efh ) gives A=[1a0b0cx1dx2e1f0g1h01010x31x4001x51011]A = \begin{bmatrix}\overset{a}{1} & \overset{b}{0} & \overset{c}{0} & \overset{d}{x_1} & \overset{e}{x_2} & \overset{f}{1} & \overset{g}{0} & \overset{h}{1} \\ 0 & 1 & 0 & 1 & 0 & x_3 & 1 & x_4 \\ 0 & 0 & 1 & x_5 & 1 & 0 & 1 & 1\end{bmatrix}A=⎣⎡1a000b100c…
x1=x4=1\boldsymbol{x_1 = x_4 = 1}x1=x4=1 , x2=x3=x\boldsymbol{x_2 = x_3 = x}x2=x3=x , x5=1−x\boldsymbol{x_5 = 1 - x}x5=1−x , with x2−x+1=0x^2 - x + 1 = 0x2−x+1=0 . Lines: agh: x4=1agh{:}\ x_4 = 1agh: x4=1 ; cdh: x1x4=1cdh{:}\ x_1 x_4 = 1cdh: x1x4=1 ; bde: x1=x2x5bde{:}\ x_1 = x_2 x_5bde: x1=x2x5 ; efh: x3(x2−1)=−x4efh{:}\ x_3(x_2 - 1) = -x_4efh: x3(x2−1)=−x4 ; dfg: x1x3+x5=1dfg{:}\ x_1 x_3 + x_5 = 1dfg: x1x3+x5=1 . A=[1a0b0c1dxe1f0g1h01010x110011−x1011]A = \begin{bmatrix}\overs…
[Representing representable matroids] Theorem 6.14 MMM is a rank rrr matroid on nnn points, representable over F\mathbb{F}F . Then MMM is represented by which kind of r×nr \times nr×n matrix?
A=[I∣A′]A = [I \mid A']A=[I∣A′] , where the entries of A′A'A′ on a coordinatizing path are all 1. Example: M−3M_{\sqrt{-3}}M−3 with basis abcabcabc : the 7 path entries (a,f),(a,h),(b,d),(b,g),(c,e),(c,g),(c,h)(a,f), (a,h), (b,d), (b,g), (c,e), (c,g), (c,h)(a,f),(a,h),(b,d),(b,g),(c,e),(c,g),(c,h) of A′A'A′ are 1.
[Representing representable matroids] Theorem: a representable matroid has a representation [I∣A′][I \mid A'][I∣A′] whose entries on a coordinatizing path (the entries of A′A'A′ that are the edges of a spanning tree of the basic-circuit bipartite graph GGG ) are all 1.What is the idea of the inductive proof?
Induction on leaves: scale the row or column of a leaf's entry to make that entry 1, then delete that row or column. A leaf of the spanning tree is the only path entry in its row or column of A′A'A′ . After deleting the leaf vvv , the rest of the tree is a spanning tree of G−vG - vG−v .Scaling a row uses row operations (then rescaling a basis column restores III ); scaling a column uses a diagonal matrix.
[How representations depend on the field] The rank 3 matroid M−3M_{\sqrt{-3}}M−3 is representable over a field F\mathbb{F}F exactly when F\mathbb{F}F contains a root of x2−x+1=0x^2 - x + 1 = 0x2−x+1=0 . Why is this called an indirect restriction on the field?
It asks for a solution of an equation, not for a particular characteristic. The Fano plane gives a direct restriction: it is representable exactly over the fields of characteristic 2.Example: x2−x+1x^2 - x + 1x2−x+1 has the root 222 in F3\mathbb{F}_3F3 ( 4−2+1=3=04 - 2 + 1 = 3 = 04−2+1=3=0 ) but no root in R\mathbb{R}R (discriminant −3-3−3 ).
[How representations depend on the field] Represent the Fano plane F7F_7F7 by a 3×73 \times 73×7 matrix whose first three columns a,b,ca, b, ca,b,c form the identity. Which matrix do the lines force?
The columns d,e,f,gd, e, f, gd,e,f,g are (1,1,1),(1,1,0),(1,0,1),(0,1,1)(1,1,1), (1,1,0), (1,0,1), (0,1,1)(1,1,1),(1,1,0),(1,0,1),(0,1,1) : abcdefg100111001011010011011\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 ddd is on no line through two of a,b,ca, b, ca,b,c , so all its entries are nonzero and can be scaled to 1. Then e∈ab∩cde \in ab \cap cde∈ab…
[How representations depend on the field] Proposition 6.16 The Fano plane F7F_7F7 is representable over a field F\mathbb{F}F if and only if … ?
The characteristic of F\mathbb{F}F is 2. Example: F7F_7F7 is represented over F2\mathbb{F}_2F2 , but over no field of characteristic 0, 3, 5, …
[How representations depend on the field] Every representation of F7F_7F7 can be brought (by row operations and column scaling) to the matrix with columns a,…,ga, \dots, ga,…,g : abcdefg100111001011010011011\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 Why does F7F_7F7 force the characteristic to be 2?
{e,f,g}\{e, f, g\}{e,f,g} is a line of F7F_7F7 , and det[e f g]=−2\det[e\ f\ g] = -2det[e f g]=−2 , so the line needs 2=02 = 02=0 . det[110101011]=1(0−1)−1(1−0)+0=−2\det \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix} = 1(0 - 1) - 1(1 - 0) + 0 = -2det⎣⎡110101011⎦⎤=1(0−1)−1(1−0)+0=−2 . {e,f,g}\{e, f, g\}{e,f,g} is the circle.
[How representations depend on the field] Proposition 6.17. Over which fields is the non-Fano plane F7−F_7^-F7− (the Fano plane without the line {e,f,g}\{e, f, g\}{e,f,g} ) representable?
Over the fields whose characteristic is not 2. F7−F_7^-F7− has all the lines that force the Fano matrix, so it has the same matrix; now {e,f,g}\{e, f, g\}{e,f,g} must be independent, i.e. det[e f g]=−2≠0\det[e\ f\ g] = -2 \ne 0det[e f g]=−2=0 .Example: F7−F_7^-F7− is representable over Q\mathbb{Q}Q and F3\mathbb{F}_3F3 , not over F2\mathbb{F}_2F2 .
[How representations depend on the field] When is a matroid binary, and when is it ternary?
Binary: representable over F2\mathbb{F}_2F2 . Ternary: representable over F3\mathbb{F}_3F3 . Example: the Fano plane F7F_7F7 is binary but not ternary; the non-Fano plane F7−F_7^-F7− is ternary but not binary.
[How representations depend on the field] When is a matroid regular (also called unimodular)?
When it is representable over every field. Example: graphic matroids are regular (the vertex-edge incidence matrix, with signs, represents M(G)M(G)M(G) over every field).
[How representations depend on the field] In this "add 1" matroid M5M_5M5 , take a,b,ca, b, ca,b,c as the identity columns and d=(1,1,1)d = (1,1,1)d=(1,1,1) . Which matrix represents M5M_5M5 ?
The third coordinate of the points on line bcbcbc goes up by 1 from point to point: abcdefghijklm100111010101001011011111110011011223344\begin{array}{ccccccccccccc} a & b & c & d & e & f & g & h & i & j & k & l & m \\ \hline 1 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 1 & 1 & 2 & 2 & 3 & 3 & 4 & 4 \end{array}a100b010c001d111e110f101g011h112i012j113k013l114m014 Every point from eee on is the intersect…
[How representations depend on the field] In M5M_5M5 , c=(0,0,1)c = (0,0,1)c=(0,0,1) , d=(1,1,1)d = (1,1,1)d=(1,1,1) , f=(1,0,1)f = (1,0,1)f=(1,0,1) , g=(0,1,1)g = (0,1,1)g=(0,1,1) , and hhh is on the lines cdcdcd and fgfgfg .Why is h=(1,1,2)h = (1, 1, 2)h=(1,1,2) ?
On cdcdcd , hhh has equal first two entries (scaled to 1); on fgfgfg , h=f+g=(1,1,2)h = f + g = (1, 1, 2)h=f+g=(1,1,2) . The next points repeat the step: i=h−a=(0,1,2)i = h - a = (0,1,2)i=h−a=(0,1,2) , j=f+i=(1,1,3)j = f + i = (1,1,3)j=f+i=(1,1,3) , and so on.
[How representations depend on the field] In the representation of M5M_5M5 : e=(1,1,0)e = (1,1,0)e=(1,1,0) , f=(1,0,1)f = (1,0,1)f=(1,0,1) , m=(0,1,4)m = (0,1,4)m=(0,1,4) .What does the line {e,f,m}\{e, f, m\}{e,f,m} of M5M_5M5 force, and why is the matroid called M5M_5M5 ?
5=05 = 05=0 : M5M_5M5 is representable only over fields of characteristic 5. det[110101014]=1(0−1)−1(4−0)=−5\det \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 4 \end{bmatrix} = 1(0 - 1) - 1(4 - 0) = -5det⎣⎡110101014⎦⎤=1(0−1)−1(4−0)=−5 , which must be 0. {e,f,m}\{e, f, m\}{e,f,m} is the curved line.
[How representations depend on the field] What does it mean that a representation of a matroid is projectively unique?
Every entry of the matrix is forced (up to row operations and column scaling). Geometrically: each point beyond a starting frame is the intersection of two lines, so its position is determined.Example: the representations of F7F_7F7 and of M5M_5M5 are projectively unique.
[How representations depend on the field] For a prime ppp , what is the "add 1" matroid MpM_pMp , and over which fields is it representable?
The construction of M5M_5M5 with 5 replaced by ppp ; it is representable only over fields of characteristic ppp . The points on the line bcbcbc get third coordinates 1,2,…,p−11, 2, \dots, p - 11,2,…,p−1 , and the final line {e,f,m}\{e, f, m\}{e,f,m} forces p=0p = 0p=0 . M5M_5M5 .Example: M2M_2M2 is the Fano plane ( m=gm = gm=g , and the line {e,f,g}\{e, f, g\}{e,f,g} forces 2=02 = 02=0 ); M3M_3M3 has 9 points and M5M_5M5 has 13.
[How representations depend on the field] MMM is this rank 4 matroid, and ppp lies on the plane F={a,b,c,d,g}F = \{a, b, c, d, g\}F={a,b,c,d,g} with no other dependences. Over which fields does this matrix (with z≠0,1z \ne 0, 1z=0,1 ) represent M−pM - pM−p ? abcdefg101001101100z100010010000110\begin{array}{ccccccc} a & b & c & d & e & f & g \\ \hline 1 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & z & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 \end{array}a1000b0100c1100d00…
Over every field except F2\mathbb{F}_2F2 , since it needs an element z≠0,1z \ne 0, 1z=0,1 . If z=0z = 0z=0 , then f=a+ef = a + ef=a+e , so a,e,fa, e, fa,e,f are collinear. If z=1z = 1z=1 , then {c,d,e,f}\{c, d, e, f\}{c,d,e,f} is dependent.
[How representations depend on the field] MMM is a rank 4 matroid and ppp is a point placed freely on the plane F={a,b,c,d,g}F = \{a, b, c, d, g\}F={a,b,c,d,g} of MMM ; {a,b,d,e}\{a, b, d, e\}{a,b,d,e} is a basis and eee is not on FFF .To extend a representation of M−pM - pM−p to MMM , why must the column of ppp be (1,x,y,0)(1, x, y, 0)(1,x,y,0) ?
ppp is in the span of a,b,da, b, da,b,d (last coordinate 0), and nothing else is forced; a coordinatizing path through ppp scales its first entry to 1. {a,b,d,p}\{a, b, d, p\}{a,b,d,p} is the basic circuit of ppp . The two indeterminates x,yx, yx,y express " ppp is freely placed on a plane".
[How representations depend on the field] A representation of M−pM - pM−p was extended to MMM by a new column ppp with indeterminate entries x,yx, yx,y : abcdefgp1010011101100z1x0001001y00001100\begin{array}{cccccccc} a & b & c & d & e & f & g & p \\ \hline 1 & 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & z & 1 & x \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & y \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \end{array}a1000b0100c1100d0010e0001f1z01g1110p1xy0 How do you find the conditions xxx and yyy must sat…
Every 4×44 \times 44×4 minor that must be nonzero gives an inequality: x≠0,1,zx \ne 0, 1, zx=0,1,z ; y≠0,1\ y \ne 0, 1 y=0,1 ; x≠y\ x \ne y x=y ; x−z−y+zy≠0\ x - z - y + zy \ne 0 x−z−y+zy=0 . They prevent accidental dependences. Example: {a,g,p}\{a, g, p\}{a,g,p} is dependent exactly when x=yx = yx=y .Example: the columns e,f,g,pe, f, g, pe,f,g,p give det=x−y+zy−z\det = x - y + zy - zdet=x−y+zy−z .
[How representations depend on the field] A matroid MMM is represented by a matrix whose entries x,yx, yx,y must avoid finitely many polynomial relations ( x≠0,1,zx \ne 0, 1, zx=0,1,z , y≠0,1y \ne 0, 1y=0,1 , x≠yx \ne yx=y , x−z−y+zy≠0x - z - y + zy \ne 0x−z−y+zy=0 ).Why is MMM representable in every characteristic?
Over F(x,y)\mathbb{F}(x, y)F(x,y) , the transcendental extension of F\mathbb{F}F , xxx and yyy satisfy no nontrivial polynomial relation. So for each p∈{0,2,3,5,… }p \in \{0, 2, 3, 5, \dots\}p∈{0,2,3,5,…} , take a field F\mathbb{F}F of characteristic ppp and use F(x,y)\mathbb{F}(x, y)F(x,y) . (A large enough finite field works too.)
[How representations depend on the field] What is the free extension M+FpM +_F pM+Fp of a matroid MMM by a flat FFF ?
MMM with a new point ppp added freely to FFF : ppp is in the closure of FFF and in no other dependence that is not forced by this. It reverses deletion: (M+Fp)−p=M(M +_F p) - p = M(M+Fp)−p=M . Example: ppp added freely to the plane {a,b,c,d,g}\{a, b, c, d, g\}{a,b,c,d,g} .
[Non-representable matroids] Does every matroid arise from the linear dependences of some vectors over some field?
No. If every matroid were representable, matroid theory would be a branch of linear algebra.Example: the non-Pappus matroid and the Vámos cube are representable over no field.
[Non-representable matroids] What is the largest nnn such that every matroid on nnn elements is representable over some field?
n=7\boldsymbol{n = 7}n=7 : every matroid on at most 7 elements is representable over some field. This made the early search for non-representable matroids hard. The Vámos cube has 8 points, the non-Pappus matroid 9.
[Non-representable matroids] Pappus configuration. Start with two three-point lines abcabcabc and defdefdef , and set g=ae∩bdg = ae \cap bdg=ae∩bd , h=af∩cdh = af \cap cdh=af∩cd , i=bf∩cei = bf \cap cei=bf∩ce . What does Pappus's theorem say?
ggg , hhh and iii are collinear.
[Non-representable matroids] What is the non-Pappus matroid?
The Pappus configuration with g,h,ig, h, ig,h,i not collinear: 9 points, the 8 lines abcabcabc , defdefdef , aegaegaeg , bdgbdgbdg , afhafhafh , cdhcdhcdh , bfibfibfi , ceiceicei .
[Non-representable matroids] Theorem 6.21. Over which fields is the non-Pappus matroid representable?
Over no field. In any representation over a field, g,h,ig, h, ig,h,i come out collinear, as in Pappus's theorem.
[Non-representable matroids] Row operations (multiplying AAA on the left by an invertible matrix) and scaling columns by nonzero scalars do not change the column dependences of a matrix AAA .To represent the non-Pappus matroid, why may you take these columns? acdfhbegi10010111101011x1xz001110yxyy\begin{array}{ccccccccc} a & c & d & f & h & b & e & g & i \\ \hline 1 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & x & 1 & x & z \\ 0 & 0 & 1 & 1 & 1 & 0 & y & xy & y \end{array}a100c010d00…
a,c,da, c, da,c,d is a basis and fff is on none of its lines (identity plus (1,1,1)(1,1,1)(1,1,1) ); h=af∩cdh = af \cap cdh=af∩cd is (0,1,1)(0,1,1)(0,1,1) ; bbb on acacac and eee on dfdfdf leave one unknown each, xxx and yyy . ggg and iii are then determined, zzz still to be computed.
[Non-representable matroids] In a representation of the non-Pappus matroid: a=(1,0,0)a = (1,0,0)a=(1,0,0) , b=(1,x,0)b = (1,x,0)b=(1,x,0) , d=(0,0,1)d = (0,0,1)d=(0,0,1) , e=(1,1,y)e = (1,1,y)e=(1,1,y) , and g=ae∩bdg = ae \cap bdg=ae∩bd .Why is g=(1,x,xy)g = (1, x, xy)g=(1,x,xy) ?
On bdbdbd , g=(1,x,w)g = (1, x, w)g=(1,x,w) ; on aeaeae , α(1,0,0)+β(1,1,y)=(1,x,w)\alpha(1,0,0) + \beta(1,1,y) = (1,x,w)α(1,0,0)+β(1,1,y)=(1,x,w) gives β=x\beta = xβ=x , α=1−x\alpha = 1 - xα=1−x , so w=xyw = xyw=xy . Similarly i=bf∩ce=(1,z,y)i = bf \cap ce = (1, z, y)i=bf∩ce=(1,z,y) with y(1,1,1)+(1−y)(1,x,0)=(1,z,y)y(1,1,1) + (1 - y)(1,x,0) = (1, z, y)y(1,1,1)+(1−y)(1,x,0)=(1,z,y) , so z=x+y−yxz = x + y - yxz=x+y−yx .
[Non-representable matroids] In a representation of the non-Pappus matroid: h=(0,1,1)h = (0,1,1)h=(0,1,1) , g=(1,x,xy)g = (1, x, xy)g=(1,x,xy) , i=(1,x+y−yx,y)i = (1, x + y - yx, y)i=(1,x+y−yx,y) , where scalars were always multiplied on the left.Why must g,h,ig, h, ig,h,i be collinear over a field?
det[h g i]=xy−yx\det[h\ g\ i] = xy - yxdet[h g i]=xy−yx , which is 0 because multiplication in a field is commutative. det[0111xx+y−yx1xyy]=−(y−(x+y−yx))+(xy−x)=xy−yx\det \begin{bmatrix} 0 & 1 & 1 \\ 1 & x & x + y - yx \\ 1 & xy & y \end{bmatrix} = -(y - (x + y - yx)) + (xy - x) = xy - yxdet⎣⎡0111xxy1x+y−yxy⎦⎤=−(y−(x+y−yx))+(xy−x)=xy−yx .So the non-Pappus matroid, where g,h,ig, h, ig,h,i are not collinear, is representable over no field.
[Non-representable matroids] In the proof that the non-Pappus matroid is representable over no field, why are scalars always multiplied on the left, and determinants used only at the last step?
So that commutativity xy=yxxy = yxxy=yx is used only once, in the last determinant. The proof then shows: over a ring where xy≠yxxy \ne yxxy=yx is possible, the coordinates work and g,h,ig, h, ig,h,i stay independent.
[Non-representable matroids] What is a division ring (skew-field), and is the non-Pappus matroid representable over one?
Like a field, but multiplication need not be commutative. Yes, the non-Pappus matroid is representable over a division ring. Choose x,yx, yx,y with xy≠yxxy \ne yxxy=yx ; then det[h g i]=xy−yx≠0\det[h\ g\ i] = xy - yx \ne 0det[h g i]=xy−yx=0 .Adding the dependence {b,h,e}\{b, h, e\}{b,h,e} to the non-Pappus matroid gives a matroid representable over no field and no division ring.Example: the quaternions H\mathbb{H}H , where ij=−jiij = -jiij=−ji .
[Non-representable matroids] A result that follows from the proof of another result (rather than from its statement) is called a scholium.
Example: "the non-Pappus matroid is representable over a division ring" follows from the proof that it is representable over no field.
[Non-representable matroids] Desargues' configuration: triangles bfhbfhbfh and egiegiegi are in perspective from the point aaa . What does Desargues' theorem force, and what does it give for matroids?
ccc , ddd and jjj are collinear (in any PG(n,q)PG(n, q)PG(n,q) ); making them not collinear gives a matroid that cannot be represented, as with Pappus.
[Non-representable matroids] Lemma 6.22 MMM is representable over the field F\mathbb{F}F , and NNN is obtained from MMM by a sequence of deletions and contractions. Then … ?
NNN is also representable over F\mathbb{F}F . A representing matrix of MMM gives one for M−xM - xM−x (delete the column) and for M/xM/xM/x (pivot on xxx , then delete its row and column).Example: F7F_7F7 is binary, so F7−gF_7 - gF7−g and F7/gF_7/gF7/g are binary.
[Non-representable matroids] Proposition 6.23 M1M_1M1 and M2M_2M2 are on disjoint ground sets; M1M_1M1 is representable only over characteristics in A1A_1A1 and M2M_2M2 only over characteristics in A2A_2A2 , with A1∩A2=∅A_1 \cap A_2 = \emptysetA1∩A2=∅ . Then … ?
The direct sum M1⊕M2M_1 \oplus M_2M1⊕M2 is representable over no field. Example: M1=F7M_1 = F_7M1=F7 (characteristic 2 only) and M2=F7−M_2 = F_7^-M2=F7− (characteristic not 2).
[Non-representable matroids] If MMM is representable over a field F\mathbb{F}F , then every matroid obtained from MMM by deletions and contractions is representable over F\mathbb{F}F . M1M_1M1 , M2M_2M2 are representable over disjoint sets of characteristics. Why is M1⊕M2M_1 \oplus M_2M1⊕M2 representable over no field?
M1M_1M1 and M2M_2M2 are deletions of M1⊕M2M_1 \oplus M_2M1⊕M2 , so a field representing M1⊕M2M_1 \oplus M_2M1⊕M2 would represent both, and its characteristic would be in A1∩A2=∅A_1 \cap A_2 = \emptysetA1∩A2=∅ .
[Non-representable matroids] What is the characteristic set χ(M)\chi(M)χ(M) of a matroid MMM ?
The set of field characteristics over which MMM is representable, a subset of P={0,2,3,5,7,… }\mathcal{P} = \{0, 2, 3, 5, 7, \dots\}P={0,2,3,5,7,…} . Example: χ(F7)={2}\chi(F_7) = \{2\}χ(F7)={2} .Example: χ(M)=∅\chi(M) = \emptysetχ(M)=∅ exactly when MMM is representable over no field.
[Non-representable matroids] χ(M)\chi(M)χ(M) is the set of field characteristics (among 0,2,3,5,7,…0, 2, 3, 5, 7, \dots0,2,3,5,7,… ) over which MMM is representable.What are χ(F7)\chi(F_7)χ(F7) , χ(F7−)\chi(F_7^-)χ(F7−) and χ(F7⊕F7−)\chi(F_7 \oplus F_7^-)χ(F7⊕F7−) ?
χ(F7)={2}\chi(F_7) = \boldsymbol{\{2\}}χ(F7)={2} , χ(F7−)={0,3,5,7,… }\ \chi(F_7^-) = \boldsymbol{\{0, 3, 5, 7, \dots\}} χ(F7−)={0,3,5,7,…} , χ(F7⊕F7−)=∅\ \chi(F_7 \oplus F_7^-) = \boldsymbol{\emptyset} χ(F7⊕F7−)=∅ F7⊕F7−F_7 \oplus F_7^-F7⊕F7− is a rank 6 non-representable matroid ( 3+33 + 33+3 ).
[Non-representable matroids] F7F_7F7 (left plane) and F7−F_7^-F7− (right plane) are glued along a three-point line. What is the rank of this matroid MMM , and why is it representable over no field?
Rank 4; deleting the points of one plane leaves F7F_7F7 or F7−F_7^-F7− , so a field representing MMM would have characteristic 2 and not 2. Two planes meeting in a line: 3+3−2=43 + 3 - 2 = 43+3−2=4 . Smaller rank than F7⊕F7−F_7 \oplus F_7^-F7⊕F7− (rank 6).
[Non-representable matroids] Mp′M_p'Mp′ is the "add 1" matroid MpM_pMp without the line {e,f,m}\{e, f, m\}{e,f,m} (here p=5p = 5p=5 ). Over which characteristics is Mp′M_p'Mp′ representable?
Characteristic larger than ppp (and characteristic 0). In characteristic q≤pq \le pq≤p some of the coordinates 1,2,…,p−11, 2, \dots, p - 11,2,…,p−1 become 0 or the points e,f,me, f, me,f,m become collinear.
[Non-representable matroids] Proposition 6.25. Why is Mp⊕Mp′M_p \oplus M_p'Mp⊕Mp′ representable over no field? The "add 1" matroid MpM_pMp ( ppp prime) is representable only over fields of characteristic ppp . Mp′M_p'Mp′ ( MpM_pMp without the line {e,f,m}\{e, f, m\}{e,f,m} ) is representable only over characteristics larger than ppp .
χ(Mp)={p}\chi(M_p) = \{p\}χ(Mp)={p} and χ(Mp′)\chi(M_p')χ(Mp′) are disjoint, so the direct sum has empty characteristic set. This gives infinitely many non-representable matroids of rank 6; gluing MpM_pMp and Mp′M_p'Mp′ along a three-point line gives infinitely many of rank 4.
[Representations and geometry] Every simple graph is a subgraph of a complete graph. What plays this role ("universal embedding object") for simple matroids representable over a field F\mathbb{F}F ?
The projective geometries PG(r−1,F)PG(r - 1, \mathbb{F})PG(r−1,F) . There is no single universal object for all matroids.
[Representations and geometry] Theorem 6.26 MMM is a simple rank rrr matroid representable over the field F\mathbb{F}F . Then … ?
MMM is a submatroid of the projective geometry PG(r−1,F)PG(r - 1, \mathbb{F})PG(r−1,F) . The columns are nonzero vectors in Fr\mathbb{F}^rFr (no loops), pairwise non-parallel (no multiple points), so each one is a different point of PG(r−1,F)PG(r - 1, \mathbb{F})PG(r−1,F) .Example: F7F_7F7 is simple, rank 3, binary, so it is a submatroid of PG(2,2)PG(2, 2)PG(2,2) ; both have 7 points, so F7=PG(2,2)F_7 = PG(2, 2)F7=PG(2,2) .