{
  "id": "enwiki-001374703766",
  "slug": "birkhoff-algorithm",
  "title": "Birkhoff algorithm",
  "qid": "",
  "lead": "Birkhoff's algorithm (also called Birkhoff-von-Neumann algorithm) is an algorithm for decomposing a bistochastic matrix into a convex combination of permutation matrices. It was published by Garrett Birkhoff in 1946. It has many applications. One such application is for the problem of fair random assignment: given a randomized allocation of items, Birkhoff's algorithm can decompose it into a lottery on deterministic allocations.",
  "body": "Birkhoff's algorithm (also called Birkhoff-von-Neumann algorithm) is an algorithm for decomposing a bistochastic matrix into a convex combination of permutation matrices. It was published by Garrett Birkhoff in 1946. It has many applications. One such application is for the problem of fair random assignment: given a randomized allocation of items, Birkhoff's algorithm can decompose it into a lottery on deterministic allocations. \\begin{pmatrix} 0.2 & 0.3 & 0.5 \\\\ 0.6 & 0.2 & 0.2 \\\\ 0.2 & 0.5 & 0.3 \\end{pmatrix} A permutation matrix is a special case of a bistochastic matrix, in which each element is either 0 or 1 (so there is exactly one \"1\" in each row and each column). An example is the following 3-by-3 matrix: \\begin{pmatrix} 0 & 1 & 0 \\\\ 0 & 0 & 1 \\\\ 1 & 0 & 0 \\end{pmatrix} A Birkhoff decomposition (also called: Birkhoff-von-Neumann decomposition) of a bistochastic matrix is a presentation of it as a sum of permutation matrices with non-negative weights. For example, the above matrix can be presented as the following sum: 0.2 \\begin{pmatrix} 0 & 1 & 0 \\\\ 0 & 0 & 1 \\\\ 1 & 0 & 0 \\end{pmatrix} + 0.2 \\begin{pmatrix} 1 & 0 & 0 \\\\ 0 & 1 & 0 \\\\ 0 & 0 & 1 \\end{pmatrix} + 0.1 \\begin{pmatrix} 0 & 1 & 0 \\\\ 1 & 0 & 0 \\\\ 0 & 0 & 1 \\end{pmatrix} + 0.5 \\begin{pmatrix} 0 & 0 & 1 \\\\ 1 & 0 & 0 \\\\ 0 & 1 & 0 \\end{pmatrix} Birkhoff's algorithm receives as input a bistochastic matrix and returns as output a Birkhoff decomposition. Let i = 1. Construct the positivity graph G X of X. Find a perfect matching in G X , corresponding to a positive permutation set in X. Let z[i] > 0 be the smallest entry in the permutation set. Let P[i] be a permutation matrix with 1 in the positive permutation set. Let X := X − z[i] P[i]. If X contains nonzero elements, Let i = i + 1 and go back to step 2. Otherwise, return the sum: z[1] P[1] + ... + z[2] P[2] + ... + z[i] P[i]. The algorithm is correct because, after step 6, the sum in each row and each column drops by z[i]. Therefore, the matrix X remains scaled-bistochastic. Therefore, in step 3, a perfect matching always exists.",
  "categories": [
    "20476448",
    "23603337",
    "26220375",
    "60066624"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1374703766",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1789311058.0,
  "claims": [
    {
      "id": 33338078,
      "subject_qid": "",
      "subject_slug": "birkhoff-algorithm",
      "predicate": "publication date",
      "object_text": "1946",
      "object_num": 19460000.0,
      "object_unit": null,
      "polarity": 1,
      "qualifier": "",
      "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1374703766",
      "source_name": "Wikipedia",
      "source_tier": 3,
      "retrieved_at": 1792533063.2627394,
      "confidence": 0.95,
      "article_slug": "birkhoff-algorithm",
      "span_start": 7,
      "span_end": 45
    }
  ],
  "contradictions": [],
  "confidence": 0.95,
  "csl": {
    "id": "enwiki-001374703766",
    "type": "webpage",
    "title": "Birkhoff algorithm",
    "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/birkhoff-algorithm",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          15
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          15
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001374703766",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1374703766",
    "note": "Immutable snapshot enwiki-001374703766"
  }
}