2

I am working through Oxley's Matroid Theory book. An exercise in the first section asks for representations of the cycle matroid of $(K_{5}\setminus\text{ two non-adjacent edges})$ over $GF[2]$ and over $GF[3]$. I could easily get at an answer for the former, but can't get an answer for the latter even after spending a few hours playing with it. I do not think that this question (which is unstarred) could be so very complicated. What could I be missing?

Math Noob
  • 95

1 Answers1

1

Assign arbitrary directions to the edges and construct the incidence matrix corresponding to this directed graph (with entries $0$, $1$ and $-1$). You can show that for any graph, this gives a representation of its cycle matroid, over any field (just replace $-1$ by the corresponding element in the field. For example, in $GF[3]$, you just replace $-1$ in the incidence matrix by $2$). This will mostly be explained later in the book, but it is not that difficult to prove yourself. Try proving it over $\mathbb{R}$ first and you can easily extend it to any field after that.

polkjh
  • 1,432
  • Thank you! Let me try that out. – Math Noob Jan 16 '13 at 11:53
  • I think I see why this works. To construct this representation we just take the incidence matrix of the undirected graph, and flip exactly one $1$ in each column to $-1$ ($=2$ for $GF[3])$. This gives a cycle matroid of the graph for the following reason: Given any set of arcs whose underlying edges form a cycle, one can flip some subset of the arcs to get a directed cycle. Flipping an arc corresponds to multiplying its column by $-1$, and so every cycle in the graph corresponds to a circuit in the matroid, and conversely. Thank you, once again! – Math Noob Jan 16 '13 at 12:19