TheoremStatement: AI-adaptedProof: AI-generatedPipeline-generatedjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Every finite-field linear code has generator and parity-check matrices

Statement

Let $C \leq F^{n}$ have dimension $k$ . There are matrices $G \in M_{n \times k} (F)$ and $H \in M_{(n - k) \times n} (F)$ such that the columns of $G$ form a basis of $C$ , the rows of $H$ form a basis of $C^{⊥}$ after transpose identification, $\ker H = C$ , and $H G = 0$ . This includes $k = 0$ and $k = n$ .

Facts & Assumptions

Given: A finite field $F$ , $n \in N$ , a code $C \leq F^{n}$ of dimension $k$ , and the matrix conventions of Generator and parity-check matrices over a finite field.

[L1]

Classical linear code over a finite field: $C$ is a finite-dimensional linear subspace of $F^{n}$ with $k = \dim_{F} C$ .

[L2]

Bilinear dual of a finite-field linear code: $C^{⊥}$ is defined using the bilinear dot product $x \cdot y = \sum_{j} x_{j} y_{j}$ .

[L3]

Dimension and double-dual identity for finite-field code duals: $C^{⊥}$ is a subspace of dimension $n - k$ and $(C^{⊥})^{⊥} = C$ .

[F1]

Finite-dimensional vector space, and its dimension $\dim_{F} V$ ; infinite-dimensional means having no finite basis: A finite-dimensional vector space has a finite basis whose size is its dimension.

[F2]

The vector space $M_{m \times n} (F) : = F^{m \times n}$ of $m$ by $n$ matrices over a field, with entrywise operations: An $m \times n$ matrix is a function on the row-column index set, with rows and columns given by its coordinates.

[F3]

Rectangular matrix multiplication and the identity matrix $I_{n}$ , including zero-sized shapes: Matrix multiplication uses the finite coordinate sum; zero-sized shapes use the empty sum.

[F4]

Row space, column space, nullspace, row rank, column rank and matrix rank: The row space is the span of the rows and the nullspace is ${x : H x = 0}$ .

Proof

1.1L1F1F2choose

By [F1], choose a basis $c_{0}, \dots, c_{k - 1}$ of $C$ ; making these vectors the columns of $G$ gives shape $n \times k$ , independent columns, and column span exactly $C$ . If $k = 0$ , the basis and column list are empty and $G$ is the unique $n \times 0$ matrix.

1.2F1L3F2choose

By [L3], $C^{⊥}$ has dimension $n - k$ ; [F1] supplies a basis $d_{0}, \dots, d_{n - k - 1}$ . Place their transposes as the rows of $H$ . These rows are independent and span the row space corresponding to $C^{⊥}$ . If $k = n$ , this is the empty row list and $H$ has shape $0 \times n$ .

2.1L2L3F3step 1.1step 1.2

Every row of $H$ is orthogonal to every column of $G$ , by [L2] and [L3]. Hence every entry of $H G$ is zero by [F3], so $H G = 0$ with shape $(n - k) \times k$ , including when a dimension is zero.

3.1F4L3step 1.2step 2.1∎

By [F4], $H x = 0$ exactly when every row of $H$ has zero dot product with $x$ . The transposed rows span $C^{⊥}$ by step 1.2, so $\ker H = (C^{⊥})^{⊥} = C$ by [L3]. Thus $H$ is a parity-check matrix and $G$ is a generator matrix.

Remarks

The choices in steps 1.1 and 1.2 are choices of one finite basis at a time; the finite-dimensional basis theorem used here is choice-free. For $k = 0$ , $H$ can be chosen as the identity matrix of size $n$ ; for $k = n$ , $G$ can be chosen as the identity and $H$ is the unique $0 \times n$ matrix.

Depends on

Used by

Dependency tree · two levels

35 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Richard Cleve, Quantum Information Processing course notes, §37.1.2 (standard reference, not scraped)
John Preskill, Quantum Computation, Chapter 7, §7.6 (standard reference, not scraped)