DiscMat assignment 11

exercise

11.2 A new linear code

1)

Let $c=(c_1,\dots ,c_n)$ where $c_i\in F$ for $i\in [n]$ Take any $x,y\in \mathcal{C}$, for each coordinate $i$: If $(x+y{)}_i\ne 0$, then $x_i\ne 0$ or $y_i\ne 0$ (If both are $0$, then $(x+y{)}_i=x_i+y_i=0$) Let $s(c)$ denotes the set of coordinates $i$ where $c_i\ne 0$, with $hw(c)=|s(c)|$ So all $i\in s(x+y)$, we have $i\in s(x)$ or $i\in s(y)$ Therefore, we must have $s(x+y)\subseteq s(x)\cup s(y)$ $⟹|s(x+y)|\le |s(x)\cup s(y)|\le |s(x)|+|s(y)|$ (inequality for finite set) $⟹hw(x+y)\le hw(x)+hw(y)$

2)

Let $c_1,c_2\in \mathcal{C}$ such that $c_1\ne c_2$ and $d(c_1,c_2)=d_{min}(\mathcal{C})$ Let $c_3\in \mathcal{C}$ such that $hw(c_3)=mi{n}_{c\in \mathcal{C}\setminus \{0^n\}}hw(c)$ we know that $hw(c_3)=d(c_3,0_n)$ according to the definition of $hw$

We first prove that $d_{min}(\mathcal{C})\le mi{n}_{c\in \mathcal{C}\setminus \{0^n\}}hw(c)$: We prove this by using contradiction. Suppose $d_{min}(\mathcal{C})>mi{n}_{c\in \mathcal{C}\setminus \{0^n\}}hw(c)$, and we have $hw(c_3)=d(c_3,0_n)<d(c_1,c_2)$ We have $\forall x,y\in \mathcal{C}(d(c_1,c_2)\le d(x,y))$ according to the definition of $d_{min}(\mathcal{C})$ Let $x=c_3,y=0_n$, we get $d(c_1,c_2)\le d(c_3,0_n)$ This contradicts to our assumption. Therefore, we proved $d_{min}(\mathcal{C})\le mi{n}_{c\in \mathcal{C}\setminus \{0^n\}}hw(c)$

Then, we prove that $d_{min}(\mathcal{C})\ge mi{n}_{c\in \mathcal{C}\setminus \{0^n\}}hw(c)$: Since $\mathcal{C}$ is linear, $c_1-c_2$ must still be in $\mathcal{C}$ We have $hw(c_3)\le hw(c_1-c_2)$ (there is no such $c\in \mathcal{C}\setminus \{0^n\}$ such that $hw(c)<hw(c_3)$) We now prove that $hw(c_1-c_2)=d(c_1,c_2)$ By definition $d(c_1,c_2)=|\{i\in [n]|c_{1i}\ne c_{2i}\}|$ $hw(c_1-c_2)=|\{i\in [n]|(c_1-c_2{)}_i\ne 0\}|$ For each coordinate $i$:

• If $c_{1i}=c_{2i}$, then $(c_1-c_2{)}_i=c_{1i}-c_{2i}=0$
• Conversely, If $(c_1-c_2{)}_i=0$, then $c_{1i}-c_{2i}=0$
  • $⟹c_{1i}=c_{2i}$
• Thus, $c_{1i}\ne c_{2i}⟺(c_1-c_2{)}_i\ne 0$
• $⟹hw(c_1-c_2)=d(c_1,c_2)$

$⟹hw(c_3)\le d(c_1,c_2)$ $⟹d_{min}(\mathcal{C})\ge mi{n}_{c\in \mathcal{C}\setminus \{0^n\}}hw(c)$

Conclusion: Since we proved both inequalities in opposite directions, we must have $d_{min}(\mathcal{C})=mi{n}_{c\in \mathcal{C}\setminus \{0^n\}}hw(c)$ The claim is proved.

3)

Let $u_3\in U$ with $hw(u_3)=d_{min}(U)$ and $v_3\in V$ with $hw(v_3)=d_{min}(V)$ (using the result from previous question)

We first prove that $d_{min}(\mathcal{D})\le min(2d_{min}(U),d_{min}(V))$

• Take $v=0^n$, then $u_3||u_3\in \mathcal{D}$
  • $hw(u_3||u_3)=hw(u_3)+hw(u_3)$ (because concatenation just sums the weights of the two halves)
  • $=2hw(u_3)=2d_{min}(U)$ (using result from previous question)
  • Therefore, $d_{min}(\mathcal{D})\le 2d_{min}(U)$
• Take $u=0^n$, then $0^n||v_3\in \mathcal{D}$
  • and $hw(0^n||v_3)=hw(v_3)=d_{min}(V)$ (using result from previous question)
  • Therefore, $d_{min}(\mathcal{D})\le d_{min}(V)$
• Hence $d_{min}(\mathcal{D})\le min(2d_{min}(U),d_{min}(V))$

Then, we prove that $d_{min}(\mathcal{D})\ge min(2d_{min}(U),d_{min}(V))$ Take any non zero pair $(u,v)\in U\times V$ Case 1 $v=0^n$

• Then $u\ne 0^n$
• $hw(u||u)=hw(u)+hw(u)=2hw(u)\ge 2d_{min}(U)$ Case 2 $v\ne 0^n$
• $hw(u||(u+v))=hw(u)+hw(u+v)$
• By using the result from question 1 we get
• $hw(u)+hw(u+v)\ge 2hw(u)+hw(v)\ge hw(v)\ge d_{min}(V)$

In all cases, $hw(u||(u+v))\ge min(2d_{min}(U),d_{min}(V))$ $u||(u+v)\in \mathcal{D}$ Therefore $d_{min}(\mathcal{D})\ge min(2d_{min}(U),d_{min}(V))$ (using result from previous question)

Conclusion: Since we proved both inequalities in opposite directions, we must have $d_{min}(\mathcal{D})=min(2d_{min}(U),d_{min}(V))$ The claim is proved.