if a code C has generator matrix G and parity matrix H then the dual of C has generator matrix H and parity check matrix G

Question

I'm trying to understand a proof with dual code (the proof is in the link below)

https://i.gyazo.com/2bbf210710a51d7ae138419948a14a99.png

There are several things I do not understand about this proof

(1) why does $(xG)Y=0$ imply that $(xG)Y^{T}=0$ ?

x is a 1xk matrix and G is a kxn matrix so xG is 1xn so y has to be nx(something matrix) for the multiplication to be defined, but if $(xG)Y^{T}=0$ is correct y has to be an nxn matrix

(2) is my reasoning above correct?

(3) why does that rank(G)=k imply that $(G)Y^{T}=0$?

(4) what does it mean that every row of H lives in $C^{\perp}$

Answer 1

(1) it says $$(xG)~\cdot~y$$ and then $$(xG)y^{T}$$

the first one is Dot product of 2 vectors, $xG$ and $y$. So if u look at them as $[1,n]$ matixes you can write it down as Matrix product of matrix $xG$ (size $[1,n]$) and matrix $y^{T}$ (size $[n,1])$ which is the second one.

(2) No.

(3) You're forgetting $\forall x \in \Bbb F_{q}^{k}$.

this part is more about Linear Algebra then EC Codes.

$\Bbb F_{q}^{k}$ is a $k$-dimensional linear space.

$G$ is a [n,k] Matrix so you can think about it as a linear transformation $G: \Bbb F_{q}^{n} \rightarrow \Bbb F_{q}^{k}$ defined as follow: $$G(y) = G y^T$$

$y$ is a vector from $n$-dimensional space but $Gy^T$ (as well as $x$) are from same $k$-dimensional subspace.

now this line $$xGy^T=0,\forall x \in \Bbb F_{q}^{k}$$

says: "vector $z = Gy^T$ is a vector that is perpendicular to all $x$-es for $\Bbb F_{q}^{k}$"

you can visual it like this:

if we consider instead a $\Bbb R^3$ with regular $(x,y,z)$ vectors, then if $G$ would be a transformation such that $\{Gx | x \in \Bbb R^3\}$ is a 2 dimensional plane then you could find vectors that sitck out perpendicular from that plane. However rank of such $G$ would be $2$.

If that rank had been $3$ then $\{Gx | x \in \Bbb R^3\}$ would fill it all and there would be no space left for such vector (pan intended).

However there is always that one $0-vector$ perpendicular to everything.

So to sum things up: If $rank(G)$ is equal to the dimension of the subspace ($k$) then the only vector that is perpendicular to the hole subspace (to all its elements) is zero-vector.

If you'd like to see a formal proof of that you need to search in Algebra not Computer Sience.

(4) they mean that every row that matrix is an element of that set.

Maybe it was suppose to be "every row of $H$ lies in $C^⊥$" ?