Block Matrix Multiplication

Example usage leads us to rederiving Hamming Codes^[3]:

Suppose we have a linear map $\alpha: V \to W$.

We can create $\beta: V \to (V \times W)$ defined by $\vec{v} \mapsto (\text{id}_{V}(\vec{v}), \alpha(\vec{v}))$.

We can create $\gamma: (V \times W) \to W$ defined by $(\vec{v}, \vec{w}) \mapsto \alpha(\vec{v}) - \text{id}_{W}(\vec{w})$.

Then $\gamma \circ \beta: V \to W = \underline{\underline{0}}$ because $\vec{v} \mapsto_{\beta} (\text{id}_{V}(\vec{v}), \alpha(\vec{v})) \mapsto_{\gamma} \alpha(\text{id}_{V}(\vec{v})) - \text{id}_{W}(\alpha(\vec{v})) = \alpha(\vec{v}) - \alpha(\vec{v}) = \vec{0}$.

In other words: we can apply the identity map in $V$ then apply $\alpha$, or we can apply $\alpha$ then apply the identity map in $W$, and subtracting one from another we always end up with $\vec{0}$.

And also $\ker(\gamma) = \lbrace (\vec{v}, \vec{w}) \mid \alpha(\vec{v}) - \text{id}_{W}(\vec{w}) = \vec{0} \rbrace = \lbrace (\vec{v}, \vec{w}) \mid \alpha(\vec{v}) = \vec{w} \rbrace = \lbrace (\vec{v}, \alpha(\vec{v})) \rbrace = \im(\beta)$. I think category theorists call this an exact sequence^[4] but we don't need to delve so deeply...

Using our matrix notation, with $\alpha$'s matrix $\b{A}$, this tells us $\begin{bmatrix} \b{A} | \b{-I}_{W} \end{bmatrix} \begin{bmatrix} \b{I}_{V} \\ \hline \b{A} \end{bmatrix} = \b{A} \b{I}_{V} - \b{I}_{W} \b{A} = \b{A} - \b{A} = \b{0}$.

Now let us use this to construct Hamming Codes:

Consider vector spaces over $\mathbb{F}_2$, with which $\b{M}$ and $\b{-M}$ are the same for any matrix $\b{M}$. Choose $r = \dim(W)$ to be $\ge 2$.

The $\b{I}_{W} = \b{-I}_{W}$ in $\begin{bmatrix} \b{A} | \b{-I}_{W} \end{bmatrix}$ contains all columns with a single bit set to 1. Let $\b{A}$ be the matrix containing all of the other possible non-zero columns, each column appearing exactly once. $\b{I}_W$ has width $r$ and $\b{A}$ has width $2^r - 1 - r$.

The matrix $\b{P} = \begin{bmatrix} \b{I} \\ \hline \b{A} \end{bmatrix}$ forms a linear code^[5] that encodes binary messages of length $2^r - 1 - r$ as binary codewords of length $2^r - 1$ (ie adding $r$ bits of padding).

The matrix $\b{Q} = \begin{bmatrix} \b{A} | \b{I} \end{bmatrix}$ is known as the syndrome matrix of $\b{P}$. From our work above we know that $\b{u} \in \im(\b{P}) \iff \b{u} \in \ker(\b{Q})$. In other words $\b{u}$ is a codeword of $\b{P}$ if and only if $\b{u}$ is annihilated by the syndrome $\b{Q}$.

This strict checking of ($\b{u} \text{ is a codeword} \iff \b{Q}\b{u} = \b{0}$) allows us to show that $\b{P}$ is an error detecting code, and even an error correcting code:

Consider us receiving binary codewords over a noisy channel, where there is a non-zero probability of bits being corrupted.

In particular consider if a single bit is corrupted. We receive the vector $\b{r} = \b{u} + \b{e}_i$, where $\b{u} \in \im(\b{P})$ and $\b{e}_i$ has only its $i$th bit set. Then $\b{Q}\b{r} = \b{Q}(\b{u} + \b{e}_i) = \b{Q}\b{u} + \b{Q}\b{e}_i = \b{0} + \b{Q}\b{e}_i = \b{Q}\b{e}_i$ by linearity of linear algebra and matrices (hence why we called these linear codes). $\b{Q}\b{e}_i$ picks out the $i$th column of $\b{Q}$, which we know will always be non-zero by how we constructed $\b{A}$ to contain only non-zero columns, as does $\b{I}$. Hence $\b{Q}\b{r} = \b{Q}\b{e}_i \ne \b{0}$ and so $\b{r} \notin \im(\b{P})$. In other words mutating a codeword by any of its bits will never yield another codeword, meaning there is some good distance between the codewords. More precisely the Hamming distance^[6] of our code $\b{P}$ (the minimum number of bits that any two codewords differ by) is greater than 1. This allows us to detect single-bit errors; keep reading for how we can correct them!

What if two bits are corrupted? We receive the vector $\b{r} = \b{u} + \b{e}_i + \b{e}_j$. Then $\b{Q}\b{r} = \b{Q}\b{e}_i + \b{Q}\b{e}_j$. This is picking out two columns from $\b{Q}$ and adding them together. Can this ever be $\b{0}$ so that $\b{r} \in \im(\b{P})$? No. That would require two columns of $\b{Q}$ to be the same to sum to $\b{0}$ modulo 2, but we chose $\b{A}$'s columns to be unique. Thus the Hamming distance of $\b{P}$ is greater than 2.

As we have proven that the Hamming distance of our code $\b{P}$ is greater than or equal to 3, we can now prove that we can comfortably allocate a closed ball^[7] of radius 1 around each codeword $\b{u}$ in ${\mathbb{F}_2}^{2^{r} - 1}$, $\bar B(\b{u}, 1)$, whose vectors $\b{r} \in \bar B(\b{u}, 1)$ should be corrected to $\b{u}$ if they are received from a noisy channel. In other words if $\b{r}$ differs from $\b{u}$ by 1 bit then error-correct $\b{r}$ to $\b{u}$. Let us prove this:

• Hamming distance $d(\b{x}, \b{y})$ is a metric function satisfying the triangle inequality^[8], that is $d(\b{x}, \b{y}) \le d(\b{x}, \b{z}) + d(\b{z}, \b{y})$ for any $\b{z}$.
• Let $\b{u'} \in \im(\b{P})$ be another legitimate codeword. The triangle inequality tells us that $d(\b{u}, \b{u'}) \le d(\b{u}, \b{r}) + d(\b{r}, \b{u'})$.
• We know that $d(\b{u}, \b{r}) = 1$ as $\b{r} \in \bar B(\b{u}, 1)$, thus $d(\b{u}, \b{u'}) \le 1 + d(\b{r}, \b{u'})$.
• We have shown that $3 \le d(\b{u}, \b{u'})$ by the clever construction of the matrix $\b{A}$, thus $3 \le d(\b{u}, \b{u'}) \le 1 + d(\b{r}, \b{u'})$.
• Thus $2 \le d(\b{r}, \b{u'}).$

As $\b{r}$ is at least distance 2 away from every other codeword $\b{u'}$ whenever it is distance 1 away from $\b{u}$, and because we expect the error rate of a noisy channel to be reasonably small, we feel comfortable in justifying this error correction method. More formally, minimum-distance decoding and maximum-likelihood decoding are coincident when the error rate is small. See section 7.1 of Codes and Cryptography^[9] if you want the full details.

Computationally determining which bit to correct is very efficient. The syndrome columns (the columns of $\b{Q}$) are all unique, and the nth syndrome column corresponds to the nth bit being flipped. This correspondence means that we don't even have to look up in a table of closed balls which ball the received vector $\b{r}$ belongs to. Instead we just look at the syndrome vector $\b{Q}\b{r}$: if $\b{Q}\b{r} = \b{0}$ then $\b{r}$ is a codeword $\b{u}$, and if $\b{Q}\b{r} \ne \b{0}$ then flip the nth bit of $\b{r}$, where $\b{Q}\b{r}$ is the nth syndrome column of $\b{Q}$.

This means that just the $r$ padding bits of each codeword $\b{u} \in \im(\b{P})$ of length $2^r - 1$ sufficiently space out the codewords to permit unambiguous single-bit error correction. How cool is that!

If we had constructed $\b{A}$ differently, to contain less than all of the non-zero non-identity columns, the code would still work, but it would be less efficient than Hamming codes; we maximise the opportunity to include all possible non-zero columns in $\b{P}$. Hamming codes give us bang for our buck with an efficiency rate of $(2^r - 1 - r) / (2^r - 1) = 1 - r / (2^r - 1)$.

Compare that to eg another primitive way of error correction being to encode each message by tripling each of its digits so that each triplet is decoded as a best-of-three: 111000101000 corrects to 111000111000 and decodes to 1010. This code has efficiency 1/3 which is pretty bad in comparison.