Binary Words as Vectors
A binary word of length \(n\) is a sequence of \(n\) entries, each equal to \(0\) or \(1\). For linear algebra, we treat that sequence as a column vector in \(\mathbb{F}_2^n\), where \(\mathbb{F}_2=\{0,1\}\) is the field with addition and multiplication performed modulo \(2\). Thus \(1+1=0\), while \(1\cdot1=1\). Addition of binary words is coordinate by coordinate using this arithmetic. For instance, \(\begin{bmatrix}1\\0\\1\end{bmatrix}+\begin{bmatrix}1\\1\\0\end{bmatrix}=\begin{bmatrix}0\\1\\1\end{bmatrix}\).
So a linear code is a collection of binary words that contains the zero word and is closed under binary addition and scalar multiplication. In \(\mathbb{F}_2\), scalar multiplication has just two possibilities: multiplying by \(0\) gives the zero vector, and multiplying by \(1\) leaves a vector unchanged. Consequently, for a nonempty collection, closure under addition and scalar multiplication implies that it is a subspace: if \(\mathbf{v}\) belongs to the collection, then \(0\mathbf{v}=\mathbf{0}\) belongs as well. Requiring nonemptiness matters; the empty collection satisfies closure statements vacuously but is not a subspace.
The linear structure gives a compact way to describe a code. If \(\mathbf{g}_1,\dots,\mathbf{g}_k\) form a basis for \(C\), every codeword is a unique linear combination of those vectors. The basis vectors can be arranged as columns of a matrix. Multiplying that matrix by a vector of coefficients then generates a codeword.
Generator Matrices and Code Dimension
This column convention matches the convention that vectors are columns. If \(\mathbf{u}=(u_1,\dots,u_m)^{\top}\), then \(\mathbf{G}\mathbf{u}=u_1\mathbf{g}_1+\cdots+u_m\mathbf{g}_m\). The entries \(u_i\) are the coefficients used to form the codeword; they need not be unique if the columns of \(\mathbf{G}\) are dependent.
Why does a generator matrix produce a linear code? The set of all products \(\mathbf{G}\mathbf{u}\) contains \(\mathbf{0}\), since \(\mathbf{G}\mathbf{0}=\mathbf{0}\). If \(\mathbf{c}_1=\mathbf{G}\mathbf{u}_1\) and \(\mathbf{c}_2=\mathbf{G}\mathbf{u}_2\), then \(\mathbf{c}_1+\mathbf{c}_2=\mathbf{G}\mathbf{u}_1+\mathbf{G}\mathbf{u}_2=\mathbf{G}(\mathbf{u}_1+\mathbf{u}_2)\), which is another product of \(\mathbf{G}\). For \(a\in\mathbb{F}_2\), \(a\mathbf{c}_1=a(\mathbf{G}\mathbf{u}_1)=\mathbf{G}(a\mathbf{u}_1)\), also another product. These facts verify the subspace conditions directly.
Proof. The columns of \(\mathbf{G}\) span \(C\) by its definition. From a finite spanning list, retain a maximal linearly independent sublist. It still spans \(C\), because any omitted column must be a linear combination of the retained columns; otherwise it could be added to the independent sublist, contradicting maximality. The retained columns are therefore a basis of \(C\). Their number is the rank of \(\mathbf{G}\), so \(\dim C=\operatorname{rank}\mathbf{G}\). If all \(m\) columns are independent, they themselves are a basis. In that case, if \(\mathbf{G}\mathbf{u}=\mathbf{G}\mathbf{v}\), then \(\mathbf{G}(\mathbf{u}-\mathbf{v})=\mathbf{0}\) is a linear combination of the columns equal to zero. Independence forces every coefficient in \(\mathbf{u}-\mathbf{v}\) to be zero, so \(\mathbf{u}=\mathbf{v}\). Thus messages produce distinct codewords. Each of the \(m\) entries of a message has two choices, so there are \(2^m\) messages and, by distinctness, \(2^m\) codewords. \(\square\)
When the columns are dependent, the rank still gives the dimension, but the number of columns is not the dimension. Some messages then produce the same codeword. This distinction is useful when reading a generator matrix: its number of columns records the number of message coordinates supplied, while its rank records how many independent directions its code actually contains.
Generating a Code from Independent Columns
Worked Example: A Two-Dimensional Binary Code
Let \(\mathbf{G}\) have the following two columns in \(\mathbb{F}_2^4\):
Write its columns as \(\mathbf{g}_1=\begin{bmatrix}1\\0\\1\\1\end{bmatrix}\) and \(\mathbf{g}_2=\begin{bmatrix}0\\1\\1\\0\end{bmatrix}\). They are independent: if \(a\mathbf{g}_1+b\mathbf{g}_2=\mathbf{0}\), the first coordinate gives \(a=0\), and the second gives \(b=0\). Thus they form a basis of the code \(C=\operatorname{span}\{\mathbf{g}_1,\mathbf{g}_2\}\), so \(\dim C=2\).
There are four possible message vectors. Multiplying by \(\mathbf{G}\) gives every codeword:
For the last product, the third entry is \(1+1=0\) in \(\mathbb{F}_2\). The list is complete because it uses all four possible messages. It also contains no duplicates, as the columns are independent.
Check: The last word is the sum of the first two nonzero words: \(\begin{bmatrix}1\\0\\1\\1\end{bmatrix}+\begin{bmatrix}0\\1\\1\\0\end{bmatrix}=\begin{bmatrix}1\\1\\0\\1\end{bmatrix}\). The zero message gives the zero word, and the two columns are independent as shown, confirming the dimension and the four distinct codewords.
Redundant Generators
A generator matrix need not have independent columns. Dependent columns can be useful in a description, but they do not add new codewords or increase the dimension. In this case, row reduction over \(\mathbb{F}_2\) can help expose dependencies. The row operations use arithmetic modulo \(2\), so adding a row to another row is its own inverse: adding the same row again returns the original row because \(1+1=0\).
Worked Example: Three Generators but Dimension Two
Consider the matrix whose columns are \(\mathbf{g}_1,\mathbf{g}_2,\mathbf{g}_3\):
Adding \(R_1\) to \(R_3\), and then \(R_2\) to \(R_4\), gives the row-equivalent matrix below. Adding \(R_2\) to \(R_3\) then clears row 3.
Here the third column of the original matrix equals the sum of its first two columns: \(\mathbf{g}_3=\mathbf{g}_1+\mathbf{g}_2\). The first two columns are independent, since the first coordinate of \(a\mathbf{g}_1+b\mathbf{g}_2=\mathbf{0}\) forces \(a=0\), and the second forces \(b=0\). They therefore form a basis for the code, which has dimension \(2\), not \(3\).
The messages \(\begin{bmatrix}0\\0\\1\end{bmatrix}\) and \(\begin{bmatrix}1\\1\\0\end{bmatrix}\) give the same word, because \(\mathbf{G}\begin{bmatrix}0\\0\\1\end{bmatrix}=\mathbf{g}_3=\mathbf{g}_1+\mathbf{g}_2=\mathbf{G}\begin{bmatrix}1\\1\\0\end{bmatrix}\). The four codewords, from the combinations of the basis columns, are \(\begin{bmatrix}0\\0\\0\\0\end{bmatrix}\), \(\begin{bmatrix}1\\0\\1\\0\end{bmatrix}\), \(\begin{bmatrix}0\\1\\1\\1\end{bmatrix}\), and \(\begin{bmatrix}1\\1\\0\\1\end{bmatrix}\).
Check: Adding the two nonzero basis words gives \(\begin{bmatrix}1\\0\\1\\0\end{bmatrix}+\begin{bmatrix}0\\1\\1\\1\end{bmatrix}=\begin{bmatrix}1\\1\\0\\1\end{bmatrix}\), since the third coordinate is \(1+1=0\). This is also the third column, as required by \(\mathbf{g}_3=\mathbf{g}_1+\mathbf{g}_2\).
The row-reduction display is consistent with the two independent generators, but the direct column relation is what immediately verifies the redundancy. When checking a particular generator matrix, it is good practice to check column relations or independence using the original columns: row operations change the columns themselves, even though they preserve the rank.
Recovering a Generator Matrix from a Description
A code may be described by parameters rather than by a matrix. To convert such a description into a generator matrix, express a general codeword as a linear combination of the parameters. The coefficient vector of each parameter becomes a column of the generator matrix. If the parameter columns are independent, they form a basis and the number of parameters is the code dimension.
Worked Example: From Parameters to a Generator Matrix
Define \(C\subseteq\mathbb{F}_2^4\) by \(\mathbf{c}=\begin{bmatrix}a+b\\b\\c\\a+c\end{bmatrix}\), where \(a,b,c\in\mathbb{F}_2\). Separate the contribution from each parameter:
The three columns are independent. Indeed, if a combination with coefficients \(x,y,z\) is zero, the second coordinate gives \(y=0\), the third gives \(z=0\), and then the first gives \(x=0\). Thus the columns are a basis, \(\dim C=3\), and the eight parameter choices give eight distinct codewords.
For example, with \((a,b,c)=(1,0,1)\), the formula gives \(\mathbf{c}=\begin{bmatrix}1\\0\\1\\0\end{bmatrix}\). Listing all parameter choices gives the codewords \(\begin{bmatrix}0\\0\\0\\0\end{bmatrix}\), \(\begin{bmatrix}1\\0\\0\\1\end{bmatrix}\), \(\begin{bmatrix}1\\1\\0\\0\end{bmatrix}\), \(\begin{bmatrix}0\\1\\0\\1\end{bmatrix}\), \(\begin{bmatrix}0\\0\\1\\1\end{bmatrix}\), \(\begin{bmatrix}1\\0\\1\\0\end{bmatrix}\), \(\begin{bmatrix}1\\1\\1\\1\end{bmatrix}\), and \(\begin{bmatrix}0\\1\\1\\0\end{bmatrix}\).
Check: The example \((a,b,c)=(1,0,1)\) yields \(\begin{bmatrix}1+0\\0\\1\\1+1\end{bmatrix}=\begin{bmatrix}1\\0\\1\\0\end{bmatrix}\), matching the matrix product. The count \(8=2^3\) agrees with three independent binary parameters.
Common Pitfalls and Why the Structure Matters
Do not use ordinary real arithmetic for binary coordinates. A wrong calculation might add the third entries \(1\) and \(1\) as ordinary integers and write \(2\), or reduce the sum to \(0\) but leave other coordinates unchanged. The correction is to perform every coordinate operation in \(\mathbb{F}_2\): for example, \(\begin{bmatrix}1\\1\\0\end{bmatrix}+\begin{bmatrix}1\\0\\1\end{bmatrix}=\begin{bmatrix}0\\1\\1\end{bmatrix}\). The first coordinate is \(1+1=0\), while the other two are \(1+0=1\) and \(0+1=1\).
Closure alone is not a safe substitute for the subspace conditions. The empty collection is vacuously closed under addition and scalar multiplication, yet it contains no zero vector and is not a subspace. Specify that the collection is nonempty, or state that it contains \(\mathbf{0}\) and is closed under both operations.
Generator matrices make the linear structure computational. A message vector supplies coefficients, matrix multiplication combines the generators, and a basis identifies how many independent choices are available. In applications, this provides a systematic way to turn a short binary message into a longer binary word while keeping the set of possible words algebraically organized. At this stage, the key questions are how the code is generated, how many independent generators it has, and whether its messages produce distinct codewords.
Check Your Understanding
Use arithmetic in \(\mathbb{F}_2\) throughout. For matrix questions, treat vectors as columns.
- Compute \(\begin{bmatrix}1\\0\\1\\1\end{bmatrix}+\begin{bmatrix}1\\1\\1\\0\end{bmatrix}\).
- Let \(\mathbf{G}=\begin{bmatrix}1&0\\1&1\\0&1\end{bmatrix}\). Find all codewords generated by its columns and determine the dimension.
- For the matrix in question 2, explain why distinct message vectors give distinct codewords.
- If a generator matrix has four columns but rank \(3\), what is the dimension of its code? Can its four message coordinates all be recovered uniquely from the codeword?
- Show that a nonempty subset of \(\mathbb{F}_2^n\) closed under addition and scalar multiplication contains \(\mathbf{0}\).
