{
  "id": "binary-matroid-560932-092c828e12884724",
  "slug": "binary-matroid",
  "title": "binary matroid",
  "qid": "Q4913901",
  "lead": "In matroid theory, a binary matroid is a matroid that can be represented over the finite field GF(2). That is, up to isomorphism, they are the matroids whose elements are the columns of a (0,1)-matrix and whose sets of elements are independent if and only if the corresponding columns are linearly independent in GF(2).",
  "body": "In matroid theory, a binary matroid is a matroid that can be represented over the finite field GF(2). That is, up to isomorphism, they are the matroids whose elements are the columns of a (0,1)-matrix and whose sets of elements are independent if and only if the corresponding columns are linearly independent in GF(2). ==Alternative characterizations== A matroid M is binary if and only if It is the matroid defined from a symmetric (0,1)-matrix. For every set \\mathcal{S} of circuits of the matroid, the symmetric difference of the circuits in \\mathcal{S} can be represented as a disjoint union of circuits. For every pair of circuits of the matroid, their symmetric difference contains another circuit. For every pair C,D where C is a circuit of M and D is a circuit of the dual matroid of M , |C\\cap D| is an even number. For every pair B,C where B is a basis of M and C is a circuit of M , C is the symmetric difference of the fundamental circuits induced in B by the elements of C\\setminus B . No matroid minor of M is the uniform matroid U{}^2_4 , the four-point line. In the geometric lattice associated to the matroid, every interval of height two has at most five elements. ==Related matroids== Every regular matroid, and every graphic matroid, is binary. A binary matroid is regular if and only if it does not contain the Fano plane (a seven-element non-regular binary matroid) or its dual as a minor. A binary matroid is graphic if and only if its minors do not include the dual of the graphic matroid of K_5 nor of K_{3,3} . If every circuit of a binary matroid has odd cardinality, then its circuits must all be disjoint from each other; in this case, it may be represented as the graphic matroid of a cactus graph. ==Additional properties== If M is a binary matroid, then so is its dual, and so is every minor of M . Additionally, the direct sum of binary matroids is binary. define a bipartite matroid to be a matroid in which every circuit has even cardinality, and an Eulerian matroid to be a matroid in which the elements can be partitioned into disjoint circuits. Within the class of graphic matroids, these two properties describe the matroids of bipartite graphs and Eulerian graphs (not-necessarily-connected graphs in which all vertices have even degree), respectively. For planar graphs (and therefore also for the graphic matroids of planar graphs) these two properties are dual: a planar graph or its matroid is bipartite if and only if its dual is Eulerian. The same is true for binary matroids. However, there exist non-binary matroids for which this duality breaks down. Any algorithm that tests whether a given matroid is binary, given access to the matroid via an independence oracle, must perform an exponential number of oracle queries, and therefore cannot take polynomial time. ==References==",
  "categories": [
    "23603337",
    "26220375",
    "29176491"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1256250364",
  "content_hash": "092c828e128847244e826a28df0e3e1e221f544f3a2a0c0ee696f258d6eaf2c2",
  "created_at": 1792311237.7615035,
  "updated_at": 1731107545.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "binary-matroid-560932-092c828e12884724",
    "type": "webpage",
    "title": "binary matroid",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/binary-matroid",
    "issued": {
      "date-parts": [
        [
          2026,
          10,
          18
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          19
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:binary-matroid-560932-092c828e12884724",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1256250364",
    "note": "Immutable snapshot binary-matroid-560932-092c828e12884724, content root 092c828e12884724…"
  }
}