6
$\begingroup$

Let $V$ be a k-dimensional subspace of $(\mathbb{F}_2)^n$, such that vector $\vec{j}=(1,1,...,1) \in V$.

Standard linear algebra shows that it is possible to find a $(k-1)$-dimensional space $W$ such that $\langle \vec{j},W\rangle=V$. However, this choice is not unique.

Is there any "canonical" choice for $W$, i.e. one that does not depend on making certain positions special, like there is the orthogonal complement in the $\mathbb{R}$-case?

In case it matters, my parameters are $n=2058$, $k=52$ and all vectors in $V$ have even weight (so orthogonal complement is pointless).

Edit: clarification of what I mean with "without making certain positions special". Consider the action of $S_n$ as a permutation group on the positions of the vector space, and let $G\le S_n$ be the stabilizer of $V$ in that action. Then $G$ should also stabilize $W$, as in the orthogonal complement case. (Note that $G$ automatically stabilizes $\vec{j}$.) I'm unsure if such spaces exist in general, so a feasible algorithm to find one is also appreciated.

$\endgroup$
  • $\begingroup$ Sorry, I'm not familiar with the notation. What's $\mathbb{F}_{\color{red}2}$? Also, how do you calculate weight of vectors in your space? $\endgroup$ – Vedran Šego Jun 23 '13 at 23:29
  • $\begingroup$ @Vedran Šego : $\mathbb{F}_2$ is the finite field with two elements - essentially the integers mod $2.$ The weight of a vector is the number of non-zero coordinates. Since all vectors have even weight, they are all orthogonal to the all-ones vector. $\endgroup$ – Will Orrick Jun 23 '13 at 23:31
  • $\begingroup$ In the real case, the orthogonal complement makes orthogonal bases special. $\endgroup$ – Ewan Delanoy Jun 24 '13 at 5:45
2
$\begingroup$

I found an answer for my particular code. I will tell here about my story in case other people post it here for if other people would read it, but I'll leave the bounty open for if other interesting answers may come.

Exhaustively generating all $2^{52}$ code words (actually $2^{51}$ with the $\vec{j}\in V$ optimization), I found that the smallest nonzero number of $1$s that appear is $562$, and the set $S$ of all $562$-words has $\langle S\rangle = V$, and of course the stabilizer of $V$ must also stabilize $S$ (as permuting positions doesn't change the total number of ones).

Now, let $S'=\{v+v'|v,v'\in S\}$. Then $W:=\langle S'\rangle$ is either $k$-dimensional or $(k-1)$-dimensional. In my case it is $(k-1)$-dimensional, so it yields the desired construction.

$\endgroup$
  • 1
    $\begingroup$ Well done. Hopefully $\vec{j}\notin W$ :-). In general I would think there would be counterexamples from coding theory, but I won't bet on it! At least not yet :-) $\endgroup$ – Jyrki Lahtonen Jun 24 '13 at 11:48
  • $\begingroup$ No, you are right, this doesn't work for every code. It luckily worked for this one, since it turns out that the only way to form the all-one vector from these minimum-weight code words is by summing up an odd number of them. Not exactly generally applicable thus. But more such possibilities are welcomed! $\endgroup$ – user1111929 Jun 24 '13 at 16:04
0
$\begingroup$

We denote $j = \begin{bmatrix} 1 & 1 & \dots & 1 \end{bmatrix}^T \in V$, where $V$ is a $k$-dimensional subspace of $\{0,1\}^n$.

Let us observe the case $2n = k$ (since $j \in V$, we know that $n$ is even) and $V = \mathop{\rm span}\{v_1,\dots,v_k\}$, where $v_i = e_{2i-1} + e_{2i}$. Here, vectors $e_i$ denote the vectors of the standard canonical base in $\mathbb{R}^n$, i.e., the columns of the identity matrix.

We define $W_i := \mathop{\rm span}\left(\{v_1,\dots,v_k\} \setminus \{v_i\}\right)$ and get $k$ candidates for the space $W$ (these are obviously not the only ones; just the ones simplest to define). Honestly, I see no reason why to pick any one of them (or any of those not among $W_i$) over the others, so I'd say the answer to your question is "no".

A similar example could be coined for your $n$ and $k$, with $v_i$ being sums of $38$ or $40$ canonical vectors $e_l$.

Orthogonality is a powerful property, making such subspaces a very interesting choice. Taking that advantage away, your special pick may only depend on some other desirable property, so you might want to check if you have any.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.