0

defining the inner product $<u ,v >=\sum_{i=1}^ku_iv_i (mod \ p)$ when $u,v \in GF(p)^k$ ($p$ is a prime). for any non-zero, fixed $u$ and for every $v$ how can I show that the outcome will be every element in $GF(p)$ exactly $p^{k-1}$ times.

user107761
  • 381
  • I am confused; the definition of $\langle u,v\rangle$ has $k$ in the limit of the sum but at the end you write "$n$ is vector's length." Moreover, wouldn't we have $u,v\in\sf{GF}(p)^n$ (i.e. $n$-tuples of elements of $\sf{GF}(p)$? – Math1000 Mar 30 '16 at 08:18
  • 1
    your'e right... edited. – user107761 Mar 30 '16 at 08:24

1 Answers1

0

Fix a vector $u\in GF(p)^n$. Then taking the inner product with $u$ is a linear map $\phi_u:GF(p)^n\to GF(p)$. That is, for vectors $v,w\in GF(p)^n$, $$\langle u, av+w\rangle=\sum u_i(av_i+w_i)=a\sum u_iv_i+\sum_iu_iw_i=a\langle u,v \rangle +\langle u,w \rangle.$$

Now let's show three things for non-zero $u$:

  1. The linear map $\phi_u$ is surjective.
  2. The kernel $K\subset GF(p)^n$ of this map has $p^{n-1}$ elements. (Hint: Rank-Nullity theorem)
  3. Every coset of $K$ in $GF(p)^n$ has exactly $p^{n-1}$ elements.

Conclude your result. Let me know if you need help.

Arkady
  • 9,315
  • I thought that the answer will be related to cosets, but I'm having troubles in defining it. coset (by defintion) consists of a group, which has a set of elements and an operator. the group has the closure property. and the mapping of a vector gives scalar. can you put things in order for me? – user107761 Mar 30 '16 at 09:03
  • @user107761 I see. You can think of the vector space $GF(p)^n$ as a group under addition (Or if you like it better this is the direct sum of $n$ copies of the additive group of $GF(p)$). Linear maps are clearly homomorphisms because they preserve addition. – Arkady Mar 30 '16 at 09:10
  • so, if I understand you correctly, the operator takes the two vectors,and returns a vector of size k, which each entry is the inner product? – user107761 Mar 30 '16 at 09:31
  • @user107761 No, it returns the elementwise sum. Eg $\binom {u_1} {v_1}+\binom {u_2} {v_2}=\binom {u_1+u_2} {v_1+v_2}$. – Arkady Mar 30 '16 at 09:38
  • I don't follow... – user107761 Mar 30 '16 at 09:58