# Linear algebra over GF(2)

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.

## Acceptance procedure

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.

## Complexity

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

## Common failure

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

## Extensions

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

## Instances

- KL-FCS-064: Dependent parity equations — Rank: 2; Nullity: 2
- KL-FCS-065: An invertible binary identity matrix — Rank: 3; Nullity: 0
- KL-FCS-066: One equation with four binary variables — Rank: 1; Nullity: 3

## References

- https://doc.sagemath.org/html/en/reference/matrices/sage/matrix/echelon_matrix.html