Binary linear code size of pre-image

24 Views Asked by At

Let $(a_1, \ldots, a_k) \neq \mathbf{0}$ over $F=GF(q)$ be given.

Define the function $f(x_1, \ldots, x_k)=\sum_{j=1}^k a_j x_j$ that maps from $F^k$ to $F$. Prove that, for any $z \in F$, exactly $q^{k-1}$ vectors are mapped by $f$ onto z.

My attempts: $$ f(x_1,\ldots,x_k) = \sum_{j=1}^k a_j x_j = (x_1 \ldots x_k) \begin{bmatrix} a_1 \\ \vdots \\ a_k \end{bmatrix} $$ I would now create a matrix $X$ of dimensions $q^k \times x$ containing the elements of $GF^k(q)$. Then every column contains $q^{k-1}$ times a specific $l \in GF(q)$. But I can't take it from there unfortunately.

1

There are 1 best solutions below

0
On

After some thought I found a solution: One uses the property that every column contains every integer to an equal extent and shows that multiplying/adding with another column preservers the property. Finally, we know that this this holds for the image as well.