Kenton Labs / Mathematical structures

Linear algebra over GF(2)

Perform elimination and solve parity equations in a field where addition is XOR, keeping the entire kernel inspectable.

The vocabulary.

These definitions state the objects and properties used by the dataset. The complete instance specification remains the authority for each result.

GF(2): The field with elements 0 and 1; addition and subtraction are XOR.
Rank: The number of pivot columns after elimination.
Nullspace: Every vector x with Ax=0, under arithmetic modulo two.

How the dataset works.

Three deterministic instances define this family. Each includes its input model, a checked result, evidence, and an acceptance procedure. Download the complete dataset JSON ↘ or the area’s readable source ↘.

Acceptance procedure

Reduce the binary matrix by row swapping and XOR elimination.
Identify pivot columns and compute rank and nullity.
Enumerate every binary vector of the declared column dimension.
Compare the full kernel list and verify its size against rank-nullity.

Cost and scope

For m rows and n columns, elimination is polynomial; full kernel enumeration checks 2ⁿ vectors.

A common failure

Ordinary real-number arithmetic gives different answers. A few null vectors need not span the kernel.

Explore the mechanics.

Change a local input or follow the steps. The stored result and its scope remain attached to the downloadable record.

Worked records.

Three instances expose concrete claims and the artifacts that establish or refute them. Expand a record for the problem, checker reasoning, formal payload, and verification metadata.

KL-FCS-064
Linear algebra over GF(2)Dependent parity equationsElimination + complete kernel · 16 vectors

The problem

Compute rank, nullity, reduced row-echelon form, and the complete binary kernel.

The checked result

Rank: 2; Nullity: 2.

XOR row operations preserve the solution space. Free columns account for the kernel’s degrees of freedom, and full enumeration checks every binary candidate.

Why the checker accepts it

Reduce the binary matrix by row swapping and XOR elimination.
Identify pivot columns and compute rank and nullity.
Enumerate every binary vector of the declared column dimension.
Compare the full kernel list and verify its size against rank-nullity.

Formal specification

{
  "matrix": [
    [
      1,
      1,
      0,
      1
    ],
    [
      0,
      1,
      1,
      0
    ],
    [
      1,
      0,
      1,
      1
    ]
  ],
  "field": "GF(2); column vectors; all dot products modulo two."
}

Claim and evidence

{
  "claim": {
    "rank": 2,
    "nullity": 2
  },
  "witness": {
    "rref": [
      [
        1,
        0,
        1,
        1
      ],
      [
        0,
        1,
        1,
        0
      ],
      [
        0,
        0,
        0,
        0
      ]
    ],
    "kernel": [
      [
        0,
        0,
        0,
        0
      ],
      [
        0,
        1,
        1,
        1
      ],
      [
        1,
        0,
        0,
        1
      ],
      [
        1,
        1,
        1,
        0
      ]
    ]
  }
}

Dataset construction

Deterministic finite fixture; full enumeration or witness replay as stated. Structured JSON; field meanings are stated in the specification. Acceptance covers 16 checker units for this record; the unit type is stated in its verification scope.

Complexity and limits

For m rows and n columns, elimination is polynomial; full kernel enumeration checks 2ⁿ vectors.

Only these exact matrices are certified; the witness is a complete kernel list rather than a scalable basis certificate.

A boundary to investigate

Ordinary real-number arithmetic gives different answers. A few null vectors need not span the kernel. Add row-operation certificates, nullspace bases, and inconsistency witnesses.

Verification and provenance metadata

Mechanical status: checked. Human review: not yet recorded. Checker version 1.0.0, Python 3.9.6. The report contains source hashes. The trust boundary includes Python and the custom checker implementations; no proof-assistant validation is claimed.

Original Kenton Labs reference instance, authored with Codex assistance on 2026-10-11. No external dataset import or model-generation evaluation. Reuse-license selection remains pending.

Replay from the source bundle: python3 tools/verify.py.

Readable source ↘Record JSON ↘Full area ↗Related KL-FCS-065 ↘Related KL-FCS-066 ↘

KL-FCS-065
Linear algebra over GF(2)An invertible binary identity matrixElimination + complete kernel · 8 vectors

The problem

Compute rank, nullity, reduced row-echelon form, and the complete binary kernel.

The checked result

Rank: 3; Nullity: 0.

XOR row operations preserve the solution space. Free columns account for the kernel’s degrees of freedom, and full enumeration checks every binary candidate.

Why the checker accepts it

Reduce the binary matrix by row swapping and XOR elimination.
Identify pivot columns and compute rank and nullity.
Enumerate every binary vector of the declared column dimension.
Compare the full kernel list and verify its size against rank-nullity.

Formal specification

{
  "matrix": [
    [
      1,
      0,
      0
    ],
    [
      0,
      1,
      0
    ],
    [
      0,
      0,
      1
    ]
  ],
  "field": "GF(2); column vectors; all dot products modulo two."
}

Claim and evidence

{
  "claim": {
    "rank": 3,
    "nullity": 0
  },
  "witness": {
    "rref": [
      [
        1,
        0,
        0
      ],
      [
        0,
        1,
        0
      ],
      [
        0,
        0,
        1
      ]
    ],
    "kernel": [
      [
        0,
        0,
        0
      ]
    ]
  }
}

Dataset construction

Deterministic finite fixture; full enumeration or witness replay as stated. Structured JSON; field meanings are stated in the specification. Acceptance covers 8 checker units for this record; the unit type is stated in its verification scope.

Complexity and limits

For m rows and n columns, elimination is polynomial; full kernel enumeration checks 2ⁿ vectors.

Only these exact matrices are certified; the witness is a complete kernel list rather than a scalable basis certificate.

A boundary to investigate

Ordinary real-number arithmetic gives different answers. A few null vectors need not span the kernel. Add row-operation certificates, nullspace bases, and inconsistency witnesses.

Verification and provenance metadata

Original Kenton Labs reference instance, authored with Codex assistance on 2026-10-11. No external dataset import or model-generation evaluation. Reuse-license selection remains pending.

Replay from the source bundle: python3 tools/verify.py.

Readable source ↘Record JSON ↘Full area ↗Related KL-FCS-064 ↘Related KL-FCS-066 ↘

KL-FCS-066
Linear algebra over GF(2)One equation with four binary variablesElimination + complete kernel · 16 vectors

The problem

Compute rank, nullity, reduced row-echelon form, and the complete binary kernel.

The checked result

Rank: 1; Nullity: 3.

XOR row operations preserve the solution space. Free columns account for the kernel’s degrees of freedom, and full enumeration checks every binary candidate.

Why the checker accepts it

Reduce the binary matrix by row swapping and XOR elimination.
Identify pivot columns and compute rank and nullity.
Enumerate every binary vector of the declared column dimension.
Compare the full kernel list and verify its size against rank-nullity.

Formal specification

{
  "matrix": [
    [
      1,
      1,
      1,
      1
    ],
    [
      1,
      1,
      1,
      1
    ]
  ],
  "field": "GF(2); column vectors; all dot products modulo two."
}

Claim and evidence

{
  "claim": {
    "rank": 1,
    "nullity": 3
  },
  "witness": {
    "rref": [
      [
        1,
        1,
        1,
        1
      ],
      [
        0,
        0,
        0,
        0
      ]
    ],
    "kernel": [
      [
        0,
        0,
        0,
        0
      ],
      [
        0,
        0,
        1,
        1
      ],
      [
        0,
        1,
        0,
        1
      ],
      [
        0,
        1,
        1,
        0
      ],
      [
        1,
        0,
        0,
        1
      ],
      [
        1,
        0,
        1,
        0
      ],
      [
        1,
        1,
        0,
        0
      ],
      [
        1,
        1,
        1,
        1
      ]
    ]
  }
}

Dataset construction

Complexity and limits

For m rows and n columns, elimination is polynomial; full kernel enumeration checks 2ⁿ vectors.

Only these exact matrices are certified; the witness is a complete kernel list rather than a scalable basis certificate.

A boundary to investigate

Ordinary real-number arithmetic gives different answers. A few null vectors need not span the kernel. Add row-operation certificates, nullspace bases, and inconsistency witnesses.

Verification and provenance metadata

Original Kenton Labs reference instance, authored with Codex assistance on 2026-10-11. No external dataset import or model-generation evaluation. Reuse-license selection remains pending.

Replay from the source bundle: python3 tools/verify.py.

Readable source ↘Record JSON ↘Full area ↗Related KL-FCS-064 ↘Related KL-FCS-065 ↘

Go further.

Add row-operation certificates, nullspace bases, and inconsistency witnesses.

Questions to investigate

Ordinary real-number arithmetic gives different answers. A few null vectors need not span the kernel.
Which assumption in the specification can be changed to make the current evidence insufficient?
Add row-operation certificates, nullspace bases, and inconsistency witnesses.

Conceptual references

These sources explain the surrounding theory. The linked material was not imported as a dataset, and these records do not claim checking by the source’s software.

Primary conceptual reference ↗

Related areas

Information theory Finite probability