Why do simplex codes have constant weight?

289 Views Asked by At

I was reading a proof in Algorithms and Computation in Mathematics, Vol 18 by Anton Betton, where in Chapter 2. Bounds and Modifications, page 84, Theorem 2.1.7, they've explained why in a simplex code, every word has constant weight $q^{m-1}$.

Consider the matrix ∆ from the proof of 2.1.6. This time, regard ∆ as a generator matrix. ... For this, we consider the encoding map $v \rightarrow \Delta.v$. Write $$\Delta = (u^{(0)^T}| ... | u^{(n−1)^T})$$ with $u^{(i)} \in \mathbb{F}^m_q$. Then, using the standard bilinear form, we have for $v \in \mathbb{F}^m_q$, $v·\Delta= (〈v,u^{(0)}〉,...,〈v,u^{(n−1)}〉)$. Fix an element $v \in \mathbb{F}^m_q \setminus \{0\}$. The mapping $u \mapsto〈v,u$〉for $u \in \mathbb{F}^m_q$ is a surjective linear form, as already pointed out in the proof of 1.6.8. It takes on each value of $\mathbb{F}_q$ exactly $q^{m−1}$ times. Thus, for exactly $q^{m−1}(q−1)$ vectors $u\in \mathbb{F}^m_q$ the value of $〈v,u〉$ is nonzero. By linearity, we have $\langle v, \lambda u \rangle = \lambda \langle v,u \rangle$ for all $\lambda \in \mathbb{F}_q$. In particular, the value of $\langle v,u \rangle$ is either always zero or always nonzero for elements of the form $w= \lambda u$, where $\lambda \in \mathbb{F}^*_q$. This means that the fact that $\langle v,u \rangle$ is zero or nonzero only depends on the one-dimensional subspace containing $u \neq 0$. Now recall that the $u^{(i)}$ form a transversal of the one-dimensional subspaces (disregarding the zero vector, which is in every subspace). This means that the products $\lambda\cdot u^{(i)}$ where $\lambda \in \mathbb{F}^*_q$ and $0≤i< \frac{q^m−1}{q−1}$ take on every nonzero vector $u \in \mathbb{F}^m_q$ exactly once. The previous remark implies that the $q^{m-1}(q−1)$ vectors $u \in \mathbb{F}^m_q$ with$\langle v,u \rangle =0$ ($u=0$ is not one of them!) are contained in exactly $q^{m-1}$ one-dimensional subspaces.

For clarity, they have defined the matrix $\Delta$ to be the following:

Let $\Delta$ be any matrix whose columns form a system of nonzero representatives of the one-dimensional sub-spaces of $\mathbb{F}^m_q$. The dual code of a Hamming-code, i.e.the code which is generated by the matrix $\Delta$ is called an $m-th$ order q-ary simplex-code

I understand that why for every $q^{m-1}(q-1)$ vectors $u \in \mathbb{F}^m_q$, $\langle v,u \rangle$ is nonzero, and that it being zero or non zero only depends on what $u$ is. However, I can't understand why $\lambda\cdot u^{(i)}$ takes every non zero vector $u \in \mathbb{F}^m_q$ exactly once. If someone could help me, I'd really be grateful!

1

There are 1 best solutions below

0
On BEST ANSWER

I can't understand why $\lambda\cdot u^{(i)}$ takes every non zero vector u\in\mathbb{F}_q^m$ exactly once.

In other words: For each $u\in\mathbb{F}_q^m\setminus\{0\}$ there is a unique column $u^{(i)}$ of $\Delta$ and a unique unit $\lambda\in\mathbb{F}_q^*$ with $u = \lambda\cdot u^{(i)}$.

This statement follows right from the definition of $\Delta$ (as the non-zero vector $u$ is contained in the unique one-dimensional subspace $\langle u\rangle$ of $\mathbb{F}_q^m$).