p-Ary Hamming Codes from Projective Columns

From Projective Columns to a Code

A parity-check matrix defines a linear code as the set of vectors it sends to zero. The columns determine which coordinate combinations can cancel in that matrix product. For a p-ary Hamming code, the aim is to choose columns so that no one column is zero, no two columns are scalar multiples, and some three columns satisfy a nontrivial relation. These features rule out codewords of weights one and two while ensuring that a codeword of weight three exists.

Let \(p\) be a prime and let \(r\ge 2\). The field \(\mathbb{F}_p\) consists of the residues modulo \(p\), with addition and multiplication performed modulo \(p\). Work in the finite-dimensional vector space \(\mathbb{F}_p^r\). A one-dimensional subspace is a subspace of the form \(\operatorname{span}\{\mathbf{v}\}\) for some nonzero \(\mathbf{v}\in\mathbb{F}_p^r\). Its nonzero vectors are precisely the nonzero scalar multiples of \(\mathbf{v}\).

The convention gives exactly one representative from each one-dimensional subspace. Indeed, multiplying a nonzero vector by the inverse of its first nonzero coordinate makes that coordinate \(1\). If two such normalized vectors are nonzero scalar multiples of one another, their first nonzero coordinates occur in the same position, and both equal \(1\); the scalar must therefore be \(1\). Thus the normalized vectors are equal.

The one-dimensional subspaces partition the nonzero vectors of \(\mathbb{F}_p^r\): every nonzero vector belongs to the subspace it spans, and two such subspaces either coincide or share no nonzero vector. Each one-dimensional subspace has \(p-1\) nonzero vectors, one for each nonzero scalar in \(\mathbb{F}_p\). Since \(\mathbb{F}_p^r\) has \(p^r-1\) nonzero vectors, the number of columns is

Parameters of the Construction

A vector \(\mathbf{x}\in\mathbb{F}_p^n\) is a codeword exactly when its coordinates give a linear combination of the columns of \(\mathbf{H}\) equal to \(\mathbf{0}\). The rank of \(\mathbf{H}\) is \(r\): every column is in \(\mathbb{F}_p^r\), and the columns include all standard basis vectors \(\mathbf{e}_1,\dots,\mathbf{e}_r\), which are normalized representatives of their own one-dimensional subspaces. Those vectors span \(\mathbb{F}_p^r\).

Proof. The count of one-dimensional subspaces gives \(n=(p^r-1)/(p-1)\). Regard \(\mathbf{H}\) as the matrix of the linear map \(T:\mathbb{F}_p^n\to\mathbb{F}_p^r\) given by \(T(\mathbf{x})=\mathbf{H}\mathbf{x}\). Its image is all of \(\mathbb{F}_p^r\), since the columns include \(\mathbf{e}_1,\dots,\mathbf{e}_r\). Hence \(\operatorname{rank}\mathbf{H}=r\). By the Rank-Nullity Theorem, which states that the dimension of the domain of a linear map between finite-dimensional spaces equals the sum of its kernel dimension and image dimension, \(\dim\mathbf{C}=n-r\).

Define the Hamming weight \(\operatorname{wt}(\mathbf{x})\) to be the number of nonzero coordinates of \(\mathbf{x}\). The Hamming distance between two vectors is the number of coordinates in which they differ, so their distance is \(\operatorname{wt}(\mathbf{x}-\mathbf{y})\). In a linear code, the minimum distance between distinct codewords equals the least weight of a nonzero codeword: a difference of distinct codewords is a nonzero codeword, and each nonzero codeword is its difference from \(\mathbf{0}\).

No column of \(\mathbf{H}\) is zero, so a vector with just one nonzero coordinate cannot satisfy \(\mathbf{H}\mathbf{x}=\mathbf{0}\). Also, two distinct columns are not scalar multiples, because they represent different one-dimensional subspaces. A codeword with exactly two nonzero coordinates would give \(a\mathbf{h}_i+b\mathbf{h}_j=\mathbf{0}\) for distinct columns \(\mathbf{h}_i,\mathbf{h}_j\) and nonzero scalars \(a,b\). Rearranging gives \(\mathbf{h}_i=-b a^{-1}\mathbf{h}_j\), contradicting that the columns are not scalar multiples. Thus every nonzero codeword has weight at least three.

Finally, the columns include \(\mathbf{e}_1,\mathbf{e}_2,\mathbf{e}_1+\mathbf{e}_2\), each normalized as written. They are distinct representatives, and \(\mathbf{e}_1+\mathbf{e}_2-(\mathbf{e}_1+\mathbf{e}_2)=\mathbf{0}\) gives a codeword supported on those three columns, with coefficients \(1,1,-1\). All three coefficients are nonzero in \(\mathbb{F}_p\), including when \(p=2\), where \(-1=1\). Therefore a weight-three codeword exists, and the minimum distance is exactly \(3\). \(\square\)

Worked Constructions

Why One Representative Matters

The construction uses projective columns because scalar multiples point in the same one-dimensional direction. Including more than one vector from that direction would create proportional columns, and proportional columns yield a codeword of weight two. For example, over \(\mathbb{F}_3\), the columns \((1,0)^{\top}\) and \((2,0)^{\top}\) are proportional. The tempting two-coordinate vector \((1,1)^{\top}\) then gives

This is a weight-two codeword, so that column choice cannot give the minimum distance claimed for a Hamming code. The correction is to keep exactly one representative from each one-dimensional subspace. In \(\mathbb{F}_3^2\), this means four representatives, not three: there are eight nonzero vectors, divided into groups of two nonzero scalar multiples.

The resulting structure explains each parameter. Counting projective directions determines the length; the presence of every standard basis column forces full row rank and therefore determines the dimension; and the absence of zero or proportional columns rules out weights one and two. The three-column relation guarantees that the lower bound is attained. These arguments apply for every prime \(p\) and every \(r\ge2\), without requiring the parity-check matrix to be written out in full.