Skip to main content

Algebraic Coding Theory MATH 4012 Spring 2026

Dr. Hunter Lehmann

Print preview

Paper size
Additional printing options
Print headers
Print footers

Worksheet Problem Set M3

Instructions: You may type up or handwrite your work, but it must be neat, professional, and organized and it must be saved as a PDF file and uploaded to the appropriate Gradescope assignment. Use a scanner or scanning app to convert handwritten work on paper to PDF. I encourage you to type your work using the provided template.
🔗
All tasks below must have a complete solution that represents a good-faith attempt at being right to receive engagement credits. If your submission is complete and turned in on time, you will receive full engagement credits for the assignment. All other submissions will receive zero engagement credit. Read the guidelines at Grading Specifications carefully.
🔗
To abide by the class’ academic honesty policy, your work should represent your own understanding in your own words. If you work with other students, you must clearly indicate who you worked with in your submission. The same is true for using tools like generative AI although I strongly discourage you from using such tools since you need to build your own understanding here to do well on exams.
🔗

1. MDS Codes.

Let \(C\) be a linear \([n,k,d]\) code over \(F=GF(q)\text{.}\)
🔗

(a)

Show that \(C\) is MDS if and only if every set of \(k\) columns in its generator matrix is linearly independent.
🔗
Solution.
Remember that \(C\) is MDS if and only if its minimum distance is equal to \(n-k+1\text{.}\) So \(C\) is not MDS if and only if its minimum distance is at most \(n-k\text{.}\) We will prove the contrapositive of both sides of this statement.
🔗
First, suppose we have a linear combination of \(k\) columns of a generator matrix of \(C\) that is zero., i.e. some set of \(k\) columns of the generator matrix is linearly dependent. Without loss of generality we can assume these are the first \(k\) columns, since reordering the columns gives an equivalent code to \(C\text{.}\) Then the \(k\times k\) submatrix of \(G\) consisting of these columns, \(G'\text{,}\) has a nontrivial linear dependence among its columns and is thus not full rank. Since it does not have full rank, there is a combination \(\bm\in F^k\) such that
\begin{equation*} \bm G' = \bzero \text{.} \end{equation*}
Now write \(G=\left[\begin{array}{c|c}G'\amp A\end{array}\right]\) and consider the codeword
\begin{equation*} \bc=\bm G = \bm \left[\begin{array}{c|c}G'\amp A\end{array}\right] = \left[\begin{array}{c|c}\bm G'\amp \bm A\end{array}\right]=\left[\begin{array}{c|c}0\, \ldots\, 0\amp \bm A\end{array}\right]\text{.} \end{equation*}
This codeword has zeros in at least its first \(k\) positions and so has Hamming weight at most \(n-k\text{.}\) So the minimum distance of \(C\) is at most \(n-k\) and \(C\) is not MDS.
🔗
Now suppose that \(C\) is not MDS. Then the minimum distance of \(C\) is at most \(n-k\text{.}\) So there is a nonzero codeword \(\bc\in C\) with Hamming weight at most \(n-k\text{,}\) i.e. there are at least \(k\) positions in which \(\bc\) is zero. Let \(\bm\in F^k\) be such that
\begin{equation*} \bc=\bm G\text{.} \end{equation*}
Now let \(G'\) be the \(k\times k\) submatrix of \(G\) consisting of the columns of \(G\) corresponding to the positions in which \(\bc\) is zero. Then we have also
\begin{equation*} \bm G'=\bzero\text{.} \end{equation*}
So \(G'\) is not full rank and there is a linear dependence among the columns of \(G'\text{.}\) So there is a set of \(k\) columns of \(G\) that is linearly dependent.
🔗
🔗
🔗

(b)

Show that \(C\) is MDS if and only if its dual code is (assuming \(k\lt n\text{.}\))
🔗
Solution.
Suppose \(C\) is MDS, i.e. \(d=n-k+1\text{.}\) Then every \(n-k\) columns of its parity check matrix are linearly independent. Now, a parity check matrix for \(C\) is a generator matrix for the dual code \(C^{\perp}\) which is an \([n,n-k]_q\) code, so by the previous part \(C^{\perp}\) is MDS.
🔗
Suppose \(C^{\perp}\) is MDS. Then \(C^{\perp}\) is an \([n,n-k]_q\) code with minimum distance \(n-(n-k)+1=k+1\text{.}\) So every \(k\) columns of a parity check matrix for \(C^{\perp}\) are linearly independent. But a parity check matrix for \(C^{\perp}\) is a generator matrix for \(C\text{,}\) so again by the previous part \(C\) is MDS.
🔗
Note that also the second part of the implication follows by the first part and the fact that the dual of the dual code is the original code.
🔗
🔗
🔗
🔗

2. An Interesting Code.

Let \(C\) be a \([q+1,2,q]\) linear code over \(F=GF(q)\text{.}\)
🔗

(a)

Determine whether or not \(C\) is perfect.
🔗
Solution.
When \(q\) is even \(C\) is not perfect because it has an even minimum distance and all perfect codes have odd minimum distance. When \(q\) is odd, the sphere-packing bound for a code of length \(q+1\) and minimum distance \(q\) is
\begin{equation*} \frac{q^{q+1}}{\sum_{i=0}^{\lfloor (q-1)/2\rfloor} \binom{q+1}{i}(q-1)^i} \text{.} \end{equation*}
This is equal to \(q^2\) when \(q=3\text{.}\) So when \(q=3\text{,}\) \(C\) is perfect.
🔗
If \(q\gt 3\text{,}\) \(C\) is not perfect by Classification of Perfect Codes since it is not any of the codes on that list.
🔗
🔗
🔗

(b)

Determine whether or not \(C\) is MDS.
🔗
Solution.
A code is MDS if it satisfies \(d=n-k+1\text{.}\) Here we have
\begin{equation*} d=q=(q+1)-2+1=n-k+1 \end{equation*}
so such a code \(C\) is always MDS.
🔗
🔗
🔗

(c)

Give example generator matrices for such codes for \(q=2,3,5\text{.}\)
🔗
Solution.
By the first part of the first problem, we can construct such a code by giving a \(2\times q+1\) generator matrix such that every pair of columns is linearly independent. For \(q=2\text{,}\) the unique such matrix is
\begin{equation*} \begin{bmatrix} 1 \amp 0 \amp 1 \\ 0 \amp 1 \amp 1 \end{bmatrix}\text{.} \end{equation*}
For \(q=3\text{,}\) one such matrix is
\begin{equation*} \begin{bmatrix} 1 \amp 0 \amp 1 \amp 1 \\ 0 \amp 1 \amp 1 \amp 2 \end{bmatrix}\text{.} \end{equation*}
For \(q=5\text{,}\) one such matrix is
\begin{equation*} \begin{bmatrix} 1 \amp 0 \amp 1 \amp 1 \amp 1 \amp 1 \\ 0 \amp 1 \amp 1 \amp 2 \amp 3 \amp 4 \end{bmatrix}\text{.} \end{equation*}
🔗
🔗
🔗

(d)

Show that there is exactly one codeword of \(C\) which contains \(\alpha \in F\) in positions \(i\) and \(j\) for each pair of distinct positions \(i,j\) and each non-zero element \(\alpha\in F\text{.}\)
🔗
Solution.
Let \(\alpha\in F\setminus\{0\}\) and let \(1\leq i\lt j \leq n\) be distinct positions. By the first part of the first problem, the \(i\) and \(j\) columns of a generator matrix form an invertible \(2\times 2\) matrix over \(F\text{.}\) So there exists a unique vector \(\bm \in F^2\) so that
\begin{equation*} \bm \begin{pmatrix} G^i \amp G^j \end{pmatrix} = \begin{pmatrix} \alpha \amp \alpha \end{pmatrix} \in F^2\text{.} \end{equation*}
Then the codeword \(\bm G\) contains \(\alpha\) in positions \(i\) and \(j\text{.}\)
🔗
Suppose that we have \(\bm,\bm'\) such that \(\bm G\) and \(\bm' G\) contain \(\alpha\) in positions \(i\) and \(j\text{.}\) Then
\begin{align*} (\bm -\bm')\begin{pmatrix} G^i \amp G^j \end{pmatrix}\amp=\bm \begin{pmatrix} G^i \amp G^j \end{pmatrix}-\bm'\begin{pmatrix} G^i \amp G^j \end{pmatrix}\\ \amp= \begin{pmatrix} \alpha \amp \alpha \end{pmatrix}-\begin{pmatrix} \alpha \amp \alpha \end{pmatrix}\\ \amp= \bzero\text{.} \end{align*}
Since \(\begin{pmatrix} G^i \amp G^j \end{pmatrix}\) is invertible this means \(\bm-\bm'=\bzero\) and so the codeword containing \(\alpha\) in positions \(i\) and \(j\) is unique.
🔗
🔗
🔗

(e)

Show that each non-zero codeword contains precisely one zero coordinate.
🔗
Solution.
Each non-zero codeword of \(C\) contains either no zero coordinates or one zero coordinate, since it must have weight at least \(d=q\) and has length \(n=q+1\text{.}\) So among all \(q^2-1\) non-zero codewords there are at most \(q^2-1\) zero coordinates.
🔗
On the other hand, by the first part of the problem below, in each of the \(q+1\) coordinate positions there are either \(q^{2-1}=q\) zeroes or all \(q^2\) codewords in the code have a zero in that position. The fewest number of zeros is attained by having \(q\) zeroes in each position. Since the zero codeword contributes one zero in each coordinate, the non-zero codewords must therefore contribute \(q-1\) zeros to each of the \(q+1\) positions in this minimal case. Since there are both at most \(q^2-1\) and at least \(q^2-1\) zeros total, there are exactly this many, and so each non-zero codeword has precisely one zero coordinate.
🔗
🔗
🔗
🔗

3. The Plotkin Bound for Linear Codes.

This series of exercises will guide you through a proof of the Plotkin bound.
🔗

(a)

Let \(C\) be a linear \([n, k, d]\) code over \(F=GF(q)\) and let \(T\) be a \(q^k\times n\) array whose rows are the codewords of \(C\text{.}\) Show that each element of \(F\) appears in every nonzero column in \(T\) exactly \(q^{k-1}\) times.
🔗
Solution.
Fix a column \(i\) of \(T\) and define the projection map \(\pi_i: C \to F\) by \(\pi_i(c)=c_i\text{.}\) This map is \(F\)-linear because for any \(c,\hat{c} \in C, \alpha \in F\) we have
\begin{gather*} \pi_i(c+\hat{c}) = c_i +\hat{c}_i=\pi_i(c)+\pi_i(\hat{c}) \\ \pi_i(\alpha c)= \alpha c_i = \alpha (\pi_i(c) ) \text{.} \end{gather*}
🔗
Now either the \(i\)th column of \(C\) is a zero column, or else \(\pi_i(C)\) is a non-zero subspace of \(F\) and therefore is all of \(F\text{.}\) Then we have
\begin{equation*} \dim(\ker(\pi_i))+\dim(\im(\pi_i))=k \end{equation*}
so \(\dim(\ker(\pi_i)=k-1\text{.}\) The statement follows at once because \(c+\ker(\pi_i)=\hat{c}+\ker(\pi_i)\) if and only if \(c_i=\hat{c}_i\text{,}\) so the \(q\) cosets of \(\ker(\pi_i)\) in \(C\) are exactly the sets of codewords the same \(i\)th coordinate.
🔗
Note that this is essentially the same idea as Words Beginning with Zero in a Binary Linear Code.
🔗
🔗
🔗

(b)

Show that the total Hamming weight of the \(q^k-1\) nonzero codewords in a linear \([n,k,d]\) code over \(F=GF(q)\) is at most \(n(q-1)q^{k-1}\text{.}\)
🔗
Solution.
The total Hamming weight of the nonzero codewords is the count of nonzero entries of the array \(T\text{.}\) In each of the \(n\) columns, either all entries are zero or each of the \(q-1\) nonzero elements of \(F\) occurs exactly \(q^{k-1}\) times. So the greatest count in each column is \((q-1)q^{k-1}\) and so the greatest possible count for all \(n\) columns is \(n(q-1)q^{k-1}\) as desired.
🔗
🔗
🔗

(c) The Plotkin Bound.

Show that every linear \([n,k,d]\) code over \(F=GF(q)\) satisfies the inequality
\begin{equation*} d\leq \frac{n(q-1)q^{k-1}}{q^k-1}\text{.} \end{equation*}
🔗
Solution.
This follows immediately from the previous part and the fact that the total Hamming weight is certainly at least the minimum weight of any non-zero word times the number of non-zero words.
🔗
🔗
🔗
🔗

4. The Griesmer Bound for Linear Codes [Optional].

This series of exercises will guide you through a proof of the Griesmer bound. Throughout, denote by \(N_q(k,d)\) the length of a shortest linear code of dimension \(k\) and minimum distance \(d\) over \(F=GF(q)\text{.}\)
🔗

(a)

Let \(C\) be a linear \([n,k,d]\) code over \(F=GF(q)\) with \(k>1\) and a generator matrix of the form
\begin{equation*} G=\left(\begin{array}{c|c} 0\,0\,\ldots\,0 \amp 1\, 1\, \ldots\, 1 \\ \hline G_1 \amp G_2 \end{array}\right) \end{equation*}
where the number of 1’s in the first row is equal to the minimum distance \(d\) of the code. Let \(C_1\) be the linear \([n_1=n-d,k_1,d_1]\) code over \(F\) spanned by the rows of the \((k-1)\times(n-d)\) matrix \(G_1\text{.}\)
🔗
(i)
Show that \(\rank(G_1)=k-1\) and so \(k_1=k-1\) by showing that otherwise you could find a nonzero codeword in \(C\) with the first \(n-d\) entries zero which is a linear combination of the last \(k-1\) rows of \(G\) and considering linear combinations of this codeword with the first row of \(G\text{.}\)
🔗
Solution.
Suppose \(\rank(G_1) \lt k-1\text{.}\) Then the rows of \(G_1\) are linearly dependent, so there is a vector \(\bm\in F^{k-1}\) such that \(\bm G_1=\bzero\text{.}\) Then we have
\begin{equation*} \bc = (0\, \bm) G = (0\, \ldots\, 0 \, \bm G_2)\text{.} \end{equation*}
Now \(\bc\) is not the zero vector because \(G\) has full row rank. Since it has zeros in the first \(n-d\) positions and must have weight \(d\) or higher, all of its last \(d\) digits are nonzero. Then the vector \(\bc-\bc_{n} \begin{pmatrix} 0 \amp \ldots \amp 0 \amp 1 \amp \ldots \amp 1\end{pmatrix}\) has at least \(n-d+1\) zeros: the first \(n-d\) positions and the last position. But then either this vector is the zero vector, contradicting that \(G\) has full row-rank, or it is a nonzero vector of weight strictly less than \(d\) contradicting the fact that the minimum distance is \(d\text{.}\)
🔗
🔗
🔗
(ii)
Let \(\bc_1\) be a codeword of \(C_1\text{.}\) Show that there are exactly \(q\) words \(\bc_2 \in F^d\) such that the concatenation \((\bc_1\mid \bc_2)\) is a codeword of \(C\text{.}\)
🔗
Solution.
Let \(\bc_1\) be a codeword of \(C_1\text{.}\) Then there is a corresponding \(\bm_1 \in F^{k-1} \) so that \(\bm_1 C_1 = \bc_1\text{.}\) Then the \(q\) words \((a \mid \bm_1)\) for \(a \in F\) are words of \(C\) that begin with \(\bc_1\text{.}\) Suppose we have two words \(\bc_2, \bc_2^*\) such that \((\bc_1\mid\bc_2), (\bc_1\mid\bc_2^*)\) are codewords. Then the difference
\begin{equation*} (\bc_1\mid\bc_2)- (\bc_1\mid\bc_2^*)= (\bzero \mid \bc_2-\bc_2^*) \end{equation*}
is a codeword with first \(n-d\) entries zero. By the first part, this means that it is in the span of the first row of \(G\text{.}\) So every word \(\bc_2\) with this property lies in the same coset of the one dimensional subspace spanned by the first row of \(G\) and thus there are only \(q\) such words.
🔗
🔗
🔗
(iii)
Let \(\bc_1\) be a nonzero codeword of \(C_1\text{.}\) Show that there is a word \(\bc_2 \in F^d\) of Hamming weight at most \(d-\lceil d/q\rceil\) such that \((\bc_1\mid \bc_2)\) is a codeword of \(C\text{.}\)
🔗
Solution.
As in the previous part, let \(\bm\in F^{k-1}\) be such that \(\bm G_1 = \bc_1\text{.}\) Then the argument of the previous part shows that the words \(\bc_2\in F^d\) that satisfy \((\bc_1\mid\bc_2)\in C\) are precisely the set
\begin{equation*} \{ \bm G_2 + a \mathbf{1}\mid a \in F \}\text{,} \end{equation*}
where \(\mathbf{1}\) is the vector of all ones in \(F^d\text{.}\)
🔗
Now we are interested in what the Hamming weight of these words can be. For each \(a\in F\) the corresponding \(\bc_2\) has zeros in exactly the positions where \(\bm G_2\) has a value of \(-a\text{.}\) By the Pigeonhole Principle, there is one value \(-a\) of the \(q\) possible values of the \(d\) positions in \(\bm G_2\) that occurs in at least \(\lceil d/q \rceil\) positions. Then the corresponding \(\bc_2\) has weight at most \(d-\lceil d/q\rceil\text{.}\)
🔗
🔗
🔗
(iv)
Show that \(d_1\geq \lceil d/q\rceil\) by selecting in the previous part a codeword \(\bc_1\) of Hamming weight \(d_1\text{.}\)
🔗
Solution.
Let \(\bc_1\) be a codeword of minimum Hamming weight \(d_1\) in \(C_1\text{.}\) By the previous part, there exists a word \(\bc_2\in F^d\) with weight at most \(d-\lceil d/q\rceil\) such that \((\bc_1\mid\bc_2)\) is a codeword of \(C\text{.}\) Then we have
\begin{align*} d \amp \leq \wt(\bc_1\mid\bc_2) \\ \amp = \wt(\bc_1)+\wt(\bc_2)\\ \amp \leq d_1 + d -\lceil d/q \rceil\text{.} \end{align*}
Solving for \(d_1\) yields the desired inequality.
🔗
🔗
🔗
🔗

(b)

Use the previous problem to show that
\begin{equation*} N_q(k,d) \geq d + N_q(k-1,\lceil d/q \rceil) \end{equation*}
for every \(k>1\text{.}\)
🔗
Solution.
Let \(k\gt 1, d \geq 1\) and suppose that \(G\) generates an \([N_q(k,d),k,d]_q\) code. We may assume that the first row of \(G\) is of the form given in the previous problem because although an arbitrary linear code of these parameters does not have to contain a codeword of the form of the first row, it must be equivalent to one that does. To see this, if \(\bc\) is a codeword of minimum weight \(d\) then we can use column operations to move the \(d\) nonzero entries of \(\bc\) to the last \(d\) positions and then scale them all to be one. Neither of these changes the distances between codewords, so the parameters of the code are preserved, and thus there is always a code of this form, hence the smallest code with these parameters is at least as big as that one.
🔗
Now, the previous problem shows that when \(C\) is an \([N_q(k,d),k,d]\) code of this form then we can construct a code of length \(N_q(k,d)-d\text{,}\) dimension \(k-1\text{,}\) and distance at least \(\lceil d/q\rceil\text{.}\) So we must have
\begin{align*} N_q(k,d)-d \amp \geq N_q(k-1,\lceil d/q\rceil) \end{align*}
and the result follows.
🔗
🔗
🔗

(c) The Griesmer Bound.

Show by induction on \(k\) that
\begin{equation*} N_q(k,d) \geq \sum_{i=0}^{k-1} \left\lceil \frac{d}{q^i}\right\rceil\text{.} \end{equation*}
🔗
Solution.
When \(k=1\) the statement becomes
\begin{equation*} N_q(1,d) \geq d\text{,} \end{equation*}
which is trivially true. Now suppose that the statement holds for some \(k\text{.}\) By the previous part since \(k+1\gt 1\text{,}\) we have
\begin{align*} N_q(k+1,d) \amp \geq d+ N_q(k,\lceil d/q\rceil) \\ \amp \geq d + \sum_{i=0}^{k-1} \left\lceil \frac{\lceil d/q\rceil}{q^i} \right\rceil\\ \amp \geq d+ \sum_{i=0}^{k-1} \left\lceil \frac{d}{q^{i+1}} \right\rceil\\ \amp = d+ \sum_{i=1}^{k} \left\lceil \frac{d}{q^{i}} \right\rceil\\ \amp = \sum_{i=0}^{k} \left\lceil \frac{d}{q^{i}} \right\rceil\text{.} \end{align*}
So by induction we have
\begin{equation*} N_q(k,d) \geq \sum_{i=0}^{k-1} \left\lceil \frac{d}{q^i}\right\rceil \end{equation*}
for all \(k>1\text{.}\)
🔗
🔗
🔗
🔗
🔗
PrevTopNext