1. Building New Codes from Old.
Let \(C_1\) and \(C_2\) be linear codes of the same length \(n\) over the finite field \(\mathbb{F}_q\) and let \(G_1\) and \(G_2\) be generator matrices for \(C_1\) and \(C_2\text{,}\) respectively. Define the following codes:
-
\(\displaystyle C_3=C_1\cup C_2\)
-
\(\displaystyle C_4=C_1\cap C_2\)
-
\(\displaystyle C_5=C_1+C_2=\{c_1+c_2 \mid c_1\in C_1, c_2 \in C_2\}\)
-
\(\displaystyle C_6=\{(c_1 \mid c_2 ) \mid c_1 \in C_1, c_2 \in C_2\}\)
Here \((\cdot\mid\cdot)\) denotes concatenation of vectors. For \(i=1,2,\ldots,6\) denote by \(k_i\) the dimension and \(d_i>\) the minimum distance of the code \(C_i\text{.}\) Assume that \(k_1,k_2\) are both greater than zero.
(a)
Show that \(C_3\) is linear if and only if either \(C_1\subseteq C_2\) or \(C_2\subseteq C_1\text{.}\)
Solution.
First, suppose that \(C_3\) is linear. Then, for any \(c_1 \in C_1\) and \(c_2 \in C_2\text{,}\) their sum \(c_1 + c_2\) must also be in \(C_3\text{.}\) Since \(C_3 = C_1 \cup C_2\text{,}\) this means that \(c_1 + c_2\) must be in either \(C_1\) or \(C_2\text{.}\) Without loss of generality, assume \(c_1 + c_2 \in C_1\text{.}\) Since \(C_1\) is linear, it follows that \(c_2 = (c_1 + c_2) - c_1 \in C_1\text{.}\) Therefore, \(C_2 \subseteq C_1\) since \(c_2\) was arbitrary.
Now suppose that either \(C_1 \subseteq C_2\) or \(C_2 \subseteq C_1\text{.}\) Then either \(C_3=C_2\) or \(C_3=C_1\text{,}\) both of which are linear codes. Thus, \(C_3\) is linear.
(b)
Solution.
\(C_4\) is linear. We need to show that \(C_4\) is closed under addition and scalar multiplication. So let \(x,y\in C_4\) and \(a,b\in\mathbb{F}_q\text{.}\) Because \(C_4=C_1\cap C_2\text{,}\) we have \(x,y\in C_1\) and \(x,y \in C_2\text{.}\) Since both are linear it follows that \(ax+by\in C_1\) and \(ax+by\in C_2\text{,}\) so \(ax+by\in C_1\cap C_2=C_4\text{.}\) Thus, \(C_4\) is linear.
\(C_5\) is linear. We need to show that \(C_5\) is closed under addition and scalar multiplication. So let \(x,y\in C_5\) and \(a,b\in\mathbb{F}_q\text{.}\) Then we have elements \(x_1,y_1\in C_1\) and \(x_2,y_2\in C_2\) such that \(x=x_1+x_2\) and \(y=y_1+y_2\text{.}\) Therefore,
\begin{equation*}
ax+by = a(x_1+x_2)+b(y_1+y_2) = (ax_1+by_1)+(ax_2+by_2) \in C_1 + C_2 = C_5
\end{equation*}
since both \(C_1\) and \(C_2\) are linear. Thus, \(C_5\) is linear.
\(C_6\) is linear. We need to show that \(C_6\) is closed under addition and scalar multiplication. So let \(x,y\in C_6\) and \(a,b\in\mathbb{F}_q\text{.}\) Now we have elements \(x_1,y_1\in C_1\) and \(x_2,y_2\in C_2\) such that \(x=(x_1\mid x_2)\) and \(y=(y_1\mid y_2)\text{.}\) Therefore,
\begin{equation*}
ax+by = a(x_1\mid x_2)+b(y_1\mid y_2) = (ax_1+by_1 \mid ax_2+by_2) \in C_6
\end{equation*}
since both \(C_1\) and \(C_2\) are linear. Thus, \(C_6\) is linear.
(c)
Solution.
Suppose \(k_4\gt 0\text{.}\) Then there exist at least two codewords in \(C_4=C_1\cap C_2\) it has size \(q^k\geq 2^1\text{.}\) So let \(c_1,c_2 \in C_4\text{.}\) Now we also have \(c_1,c_2 \in C_1\) which means \(d(c_1,c_2)\geq d_1\) and similarly \(c_1,c_2 \in C_2\) so that \(d(c_2,c_2)\geq d_2\text{.}\) Thus \(d(c_1,c_2)\geq \max\{d_1,d_2\}\) and since \(c_1,c_2\) were arbitrary, it follows that \(d_4\geq \max\{d_1,d_2\}\text{.}\)
(d)
Solution.
First, let \(B_1\) and \(B_2\) be bases for \(C_1\) and \(C_2\) respectively. Then \(B_5=B_1\cup B_2\) is a spanning set for \(C_5=C_1+C_2\text{,}\) so
\begin{equation*}
k_5 \leq |B_5| \leq |B_1|+|B_2| = k_1+k_2\text{.}
\end{equation*}
Now, suppose we have \(k_5=k_1+k_2\text{.}\) Then both inequalities above must be strict, so that \(B_5\) is a basis and not just a spanning set for \(C_5\) and \(B_1\) and \(B_2\) are disjoint. Now let \(x\in C_1\cap C_2\text{.}\) Then we may write \(x\) as a linear combination of the vectors in \(B_1\) and also as a linear combination of the vectors in \(B_2\text{.}\) Equating these two expressions for \(x\) and rearranging gives a linear combination of the vectors in \(B_5\) which is \(0\text{,}\) which means we must have all coefficients equal to \(0\) since \(B_5\) is a basis. Thus, \(x=0\) and so \(C_1\cap C_2=\{0\}\) and \(k_4=0\text{.}\)
On the other hand, suppose \(k_4=0\) and so \(C_1\cap C_2=\{0\}\text{.}\) We now need to show that \(B_5\) is a basis for \(C_5\text{.}\) We already know it is a spanning set, so we just need to show it is linearly independent. Suppose we have a linear combination of the vectors in \(B_5\) that equals \(0\text{:}\)
\begin{equation*}
\sum_{i=0}^{k_1} \lambda_i b_{1i} + \sum_{j=0}^{k_2} \mu_j b_{2j} = 0\text{,}
\end{equation*}
where the \(b_{1i}\) are the vectors in \(B_1\) and the \(b_{2j}\) are the vectors in \(B_2\text{.}\) Rearranging gives
\begin{equation*}
\sum_{i=0}^{k_1} \lambda_i b_{1i} = -\sum_{j=0}^{k_2} \mu_j b_{2j}
\end{equation*}
so this vector is in both \(C_1\) and \(C_2\text{.}\) Since the only vector in both is \(0\text{,}\) we get that both sums are equal to \(0\text{.}\) Since \(B_1\) and \(B_2\) are bases, it follows that all the coefficients must be zero, so the linear combination is trivial and \(B_5\) is linearly independent. Thus, \(B_5\) is a basis for \(C_5\) and so \(k_5=k_1+k_2\text{.}\)
(e)
Show that \(d_5\leq \min\{d_1,d_2\}\text{.}\)
(f)
[Optional]. Show that
\begin{equation*}
\left(\begin{array}{c|c}
G_1 \amp 0 \\
\hline 0 \amp G_2
\end{array}\right)
\end{equation*}
is a generator matrix of \(C_6\) and so \(k_6 = k_1 + k_2\text{.}\)
(g)
[Optional]. Show that \(d_6 = \min\{d_1,d_2\}\text{.}\)
