# An invertible binary identity matrix

KL-FCS-065 · Linear algebra over GF(2) · version 1.0.0

## Problem

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

## Context

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

## Definitions

- **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.

## 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.

## Checker reasoning

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

## Dataset construction

{
  "family": "linear-algebra",
  "task": "Compute rank, nullity, reduced row-echelon form, and the complete binary kernel.",
  "input_encoding": "Structured JSON; field meanings are stated in the specification.",
  "coverage": "Elimination + complete kernel · 8 vectors",
  "acceptance": [
    "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."
  ],
  "generation": "Deterministic finite fixture; full enumeration or witness replay as stated.",
  "split_policy": "Reference corpus for exposition and reproduction; no train/test evaluation split is claimed."
}

## Formal payload

```json
{
  "specification": {
    "matrix": [
      [
        1,
        0,
        0
      ],
      [
        0,
        1,
        0
      ],
      [
        0,
        0,
        1
      ]
    ],
    "field": "GF(2); column vectors; all dot products modulo two."
  },
  "claim": {
    "rank": 3,
    "nullity": 0
  },
  "witness": {
    "rref": [
      [
        1,
        0,
        0
      ],
      [
        0,
        1,
        0
      ],
      [
        0,
        0,
        1
      ]
    ],
    "kernel": [
      [
        0,
        0,
        0
      ]
    ]
  }
}
```

## Complexity

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

## Limits

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

## Common error and further work

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

Elimination + complete kernel · 8 vectors. 8 checker units.
Replay with `python3 tools/verify.py`. Mechanical status: checked; human review
has not yet been recorded. Custom Python verification, not a proof-assistant
claim. Checker 1.0.0 and exact source hashes are in `verification.json`.

## Provenance and references

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

- [Conceptual reference](https://doc.sagemath.org/html/en/reference/matrices/sage/matrix/echelon_matrix.html)