Lesson 02 - Matrices, Duals, Parameters, and Local Operations¶

Prerequisites And Diagnostic Checks¶

Check the following before teaching:

Given a binary matrix \(H\), can you say what \(\ker(H)\) means?
Can you explain why \(HG^T=0\) means rows of \(G\) generate valid codewords?
Can you compute the Hamming weight of a binary vector?

If yes, move quickly through definitions and spend more time on duality and relative distance.

Concrete Motivation From The Research Map¶

Conjecture 3 eventually talks about QLDPC code families. A QLDPC family is not just a set of abstract subspaces. It is a sequence of sparse parity-check presentations. The exact presentation matters because syndrome extraction measures rows of those matrices.

This lesson teaches how the same code can be seen through:

generators, which produce valid words
parity checks, which detect invalid words
dual codes, which become the commutativity language of CSS codes
coordinate operations, which become local views in Tanner constructions

Systematic Form And Row Spaces¶

A generator matrix in systematic form looks like

\[ G=[I_k\;P]. \]

Here \(I_k\) stores the message bits directly, and \(P\) stores the parity bits. A compatible parity-check matrix is

\[ H=[P^T\;I_{n-k}] \]

over GF(2). Over other fields a minus sign appears, but in GF(2), minus and plus are the same.

The row space of \(G\) is the code:

\[ C=\operatorname{rowspan}(G). \]

The null space of \(H\) is the same code:

\[ C=\ker(H). \]

So \(G\) and \(H\) are two descriptions of the same object. \(G\) is constructive. \(H\) is diagnostic.

Dual Codes¶

The dual code of \(C\) is

\[ C^\perp=\{v : v\cdot c=0\text{ for all }c\in C\}. \]

If \(G\) generates \(C\), then

\[ C^\perp=\ker(G). \]

If \(H\) checks \(C\), then the rows of \(H\) generate \(C^\perp\).

This is the first CSS preview. In a CSS code, one classical code controls X-type checks and another controls Z-type checks. The condition that X-checks and Z-checks commute is exactly an orthogonality condition over GF(2).

Worked Example: The Even-Parity Code¶

Let \(C\) be the even-parity code of length \(4\):

\[ C=\{x\in \mathrm{GF}(2)^4 : x_1+x_2+x_3+x_4=0\}. \]

Its parity-check matrix is

\[ H=[1\;1\;1\;1]. \]

The dual code \(C^\perp\) is generated by \((1,1,1,1)\). This example will reappear as a tiny CSS code: the all-X and all-Z checks commute because their overlap has even size.

Code Parameters¶

A classical linear code has parameters [n,k,d].

\(n\) is block length.
\(k\) is dimension.
\(d\) is minimum distance.

For a linear code,

\[ d=\min_{c\in C,\;c\ne 0}\operatorname{wt}(c). \]

The same \(d\) equals the smallest number of columns of \(H\) that are linearly dependent.

Distance controls error correction:

detect up to \(d-1\) errors
correct up to \(\lfloor(d-1)/2\rfloor\) errors

The rate is \(R=k/n\). Asymptotically good classical codes have both \(R=\Theta(1)\) and \(d=\Theta(n)\).

Bounds To Remember¶

The Singleton bound says

\[ d\le n-k+1. \]

The Hamming bound says that balls of radius \(t=\lfloor(d-1)/2\rfloor\) around codewords cannot overlap:

\[ \sum_{i=0}^{t}\binom{n}{i}\le 2^{n-k}. \]

These bounds explain why rate-distance tradeoffs are real constraints, not just failures of imagination.

Puncturing And Shortening¶

Puncturing deletes one coordinate from every codeword. It reduces \(n\) by one. The dimension may stay the same or drop, and distance can decrease.

Shortening first restricts to codewords with a chosen coordinate equal to zero, then deletes that coordinate. It also reduces \(n\) by one. The dimension can drop, and distance usually does not get worse in the same naive way puncturing can.

The safe mental model is:

puncturing is projection
shortening is restriction plus projection

Why This Matters For Quantum Tanner Codes¶

Quantum Tanner codes analyze huge global codes through small local views. Those local views are often restrictions or projections of larger code data. So puncturing and shortening are not just coding-theory exercises; they are how local constraints see pieces of a global object.

What This Does And Does Not Prove¶

This lesson explains algebraic code presentations. It does not prove that a sparse presentation has good distance. For that, we need Tanner graphs and expansion.

Also, be careful with duality: \(C^\perp\subseteq C\) is a special condition, not automatic.

Active Recall¶

What is the difference between \(\operatorname{rowspan}(G)\) and \(\ker(H)\)?
Why does \(C^\perp\) swap the roles of generators and parity checks?
Why is distance the minimum dependent column count of \(H\)?
Which operation is more like projection: puncturing or shortening?

Next-Step Handoff¶

Next we translate matrices into graphs. The row-column incidence pattern of \(H\) becomes a Tanner graph, and sparsity becomes bounded degree.