1
$\begingroup$

Let $V=\mathbb{F}^n$, for a finite field $\mathbb{F}$. Prove the equivalence of the following statements:

  1. There is a linear subspace $C$ of $V$ with the property that every vector $v$ of $C\setminus\{0\}$ has at least $t$ nonzero entries, and $\dim(C)=n-k$.
  2. There are $k$ vectors $\phi_1, \ldots, \phi_k$ of $V^*$ such that, for any nonzero vector $v \in V$ with fewer than $t$ nonzero entries, $v \not \in \ker(\phi_i)$ for some $1 \leq i \leq k$.

My (first attempt) solution:

$i \implies ii$: Suppose that there is a linear subspace $C$ of $V$ with the property that every vector $v$ of $C\setminus\{0\}$ has at least $t$ nonzero entries, and $\dim(C)=n-k$. Let $\{\phi_1,\dots,\phi_k\}$ be a basis for $Ann(C)$. (The annihilator has dimension k, since this is the dimension of $C^\perp$). Suppose that $v\not\in C$ is a vector with fewer than t non-zero entries. Since $v\not\in C$ we must have $v\not\in \ker(\phi_i)$ for some $i$. Thus, there are $k$ vectors $\phi_1, \ldots, \phi_k$ of $V^*$ such that, for any nonzero vector $v \in V$ with fewer than $t$ nonzero entries, $v \not \in \ker(\phi_i)$ for some $1 \leq i \leq k$.

$ii \implies i$: Suppose that there are $k$ vectors $\phi_1, \ldots, \phi_k$ of $V^*$ such that, for any nonzero vector $v \in V$ with fewer than $t$ nonzero entries, $v \not \in \ker(\phi_i)$ for some $1 \leq i \leq k$. Let $C=\{v\ |\ v\in\ker(\phi_i)\ \forall\ i\}$. Then for all $v\in C$, $v$ has at least $t$ nonzero entries. Further, $\{\phi_1,\dots,\phi_k\}=Ann^*(C)$, so $dim(C)=dim(V)-dim(Ann^*(C))=n-k$.

$\endgroup$
  • 2
    $\begingroup$ Presently, working some examples in (Z_3)^3 to get a sense of why these statements should be connected. $\endgroup$ – reluctant mathematician Oct 21 '14 at 9:31
  • 1
    $\begingroup$ It might be fruitful to think about orthogonal complements (or, more precisely for this problem, annihilators). $\endgroup$ – Christopher A. Wong Oct 21 '14 at 9:34
  • 1
    $\begingroup$ (1)->(2). Let $E$ be a maximal subspace consisting of vectors having at least $t$ non-zero components (and the zero vector). This maximal exist because the collection of subspaces with that property is non-empty ($C$ is one of them) and union of a chain (one included in the other) of subspaces is a subspace. Let $\phi_1,...\phi_r$ be a basis of its annihilator. We have $r\leq k$. Assume that $w$ is a vector with fewer than $t$ non-zero entries. Since $w\notin E$ we must have $w\notin\text{Ker}(\phi_i)$ for some $i$. Now complete $\phi_1,...,\phi_k$ in any way you want. $\endgroup$ – user152732 Oct 21 '14 at 13:17
  • $\begingroup$ (2)->(1). Let $E=\bigcup_{i=1}^{k}\text{Ker}(\phi_i)$. We have $\dim(E)\geq n-k$. Every non-zero vector of $E$ satisfies that it has at least $t$ non-zero components. Let $C$ be any $n-k$-dimensional subspace of $E$. $\endgroup$ – user152732 Oct 21 '14 at 13:20
  • $\begingroup$ Why do I get the feeling that somewhere there is a teacher about to explain how we can describe a linear code using check equations? $\endgroup$ – Jyrki Lahtonen Oct 21 '14 at 18:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.