{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R817",
  "content_hash": null,
  "slug": "twnfa-claim-matrix-cell-separator",
  "type": "claim",
  "title": "Two singleton contexts isolate any Boolean-matrix entry",
  "summary": "For every \\(h\\) by \\(h\\) Boolean matrix \\(A\\), \\(E_{1i}AE_{j1}\\) is nonzero exactly when \\(A_{ij}=1\\). Thus two distinct connectivities can always be separated by one-symbol contexts.",
  "relevance": "For Polynomial determinization of two-way finite automata, record twnfa-claim-matrix-cell-separator (“Two singleton contexts isolate any Boolean-matrix entry”) records a bound, answer, status fact, or structural consequence. The record states: For every \\(h\\) by \\(h\\) Boolean matrix \\(A\\), \\(E_{1i}AE_{j1}\\) is nonzero exactly when \\(A_{ij}=1\\).",
  "relevance_source": "recorded",
  "body": "Write \\(E_{ab}\\) for the Boolean matrix with a single one in cell \\((a,b)\\). Boolean multiplication gives\n\\[\n(E_{1i}AE_{j1})_{11}=A_{ij},\n\\]\nand every other entry of the product is zero. Hence the product is nonzero exactly when \\(A_{ij}=1\\).\n\nIf \\(A\\ne B\\), choose a cell \\((i,j)\\) where they differ. Prefixing by \\(E_{1i}\\) and suffixing by \\(E_{j1}\\) makes exactly one of the two three-matrix words live. This is the concrete separator behind Lemma 1 of Adeogun and Kapoutsis. The argument also fixes the row and column order used by the replay artifact.",
  "status": "supported",
  "evidence_grade": "self_reported",
  "scope": {
    "kind": "universal",
    "statement": "every Boolean matrix dimension h at least 1 and every pair of row and column indices"
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "source_only",
    "kind": "claim",
    "citation": {
      "url": "https://arxiv.org/abs/2602.24279",
      "locator": "Adeogun and Kapoutsis, Section 2.3, Lemma 1, with an independent reconstruction recorded 2026-07-28"
    },
    "missing": [
      "source",
      "command",
      "runtime",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://arxiv.org/abs/2602.24279",
    "locator": "Adeogun and Kapoutsis, Section 2.3, Lemma 1, with an independent reconstruction recorded 2026-07-28"
  },
  "models": [],
  "relations": [
    {
      "slug": "R818",
      "title": "One-way liveness forces at least h(h+1)/4 deterministic states",
      "object_type": "claim",
      "relation": "informs",
      "direction": "outgoing"
    },
    {
      "slug": "R814",
      "title": "The separator and encoded NFAs pass 1,385,824 unique finite inputs",
      "object_type": "claim",
      "relation": "tests",
      "direction": "incoming"
    },
    {
      "slug": "two-way-nfa-polynomial-determinization",
      "title": "two way nfa polynomial determinization",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}