1
$\begingroup$

We can "travel" on all the vector space $V =GF(2)^n$ by doing the following

(a) choose a primitive polynomial $P(t)$ of degree $n$ over $GF(2)$.

(b) change vector $ X = (x_1, \ldots,x_{n-1}) \in V$ into vector $Y = (y_1, \ldots, y_{n-1}) \in V$.

(c) repeat until $V$ is exhausted (2^n times)

where

$y_1+y_2z+ \cdots + y_nz^{n-1} = z(x_1+x_2z+ \cdots + x_nz^{n-1})$

and $z$ is a zero of $P$, i.e., $P(z)=0.$

I want to do the same with integral vectors containing only 1 and -1

I.e.: "travel" on all possible vectors $(r_1, \ldots, r_{n-1})$

with $r_i^2=1$

How to do that ???

I do some trys without success...

reason of the question: I have only limited time on a computer ((five days per job, two jobs allowed)) and I need to try some computations on all such vectors with moderately large $n$

the loop:

from r_1=-1 to 1 by 2 do;

from r_2=-1 to 1 by 2 do

$\cdots$

from r_{n-1}=-1 to 1 by 2 do;

do not "fit" in my allowed time.

following suggestion (thanks) let consider the following:

I need to examine each of the $2^n$ vectors.

To fit time allowed suffices to break the $2^n$ in smaller parts and apply to each of them the method I am asking for here !

I tried:

(a) $r_i \in \{−1,1\}$ go to $si=(r_i+1)/2$ in $\{0,1\}$

(b) apply idea with primitive polynomial, to the $s_i$'s

(So forced to take some reduction modulo $2$ in some coordinates)

(c) recover $R_j$ the new $r_j$, by $R_j=2s_j−1$

so that from vector

$(r_1,…,r_n)$ we get new vector $(R_1,…,R_n)$

and applying this $2^n$ times we should (hopefully) get all the $2^n$ vectors

but this does NOT work since I ended, e.g. to the cycle

$(−1,−1,…,−1)$ going to itself indefinitely

In other words: Can I write these $2^n$ vectors as a sequence

$v_1,…,v_{2^n}$ in such a manner

that I can with some simple algebraic computation,

(similar to the use of the primitive polynomial in case the vectors are in $GF(2)^n$))

get the vector

$v_k$ from the vector $v_{k−1}$

beginning with any fixed vector

$v_1$

???

$\endgroup$
9
  • 2
    $\begingroup$ Well, if you want to test ALL the vectors, you cannot do better than the method you suggest in your posting, and if you want to sample vectors, you can just throw a coin $n$ times (where $n$ is the dimension of your space) to generate a vector, so I am not sure what you are asking. The polynomial method you are suggesting for GF(2) does not appear to have any particular advantage... $\endgroup$
    – Igor Rivin
    Dec 27, 2010 at 23:55
  • 1
    $\begingroup$ I think Igor is right. Possibly Gray codes could be of some use to you. $\endgroup$ Dec 28, 2010 at 0:14
  • 2
    $\begingroup$ Use the loop to generate a list of all vectors you want to examine, then split the list in parts such that each part can be processed in a separate job in your allotted time. That being said, the question is hardly appropriate for this site. $\endgroup$
    – Guntram
    Dec 28, 2010 at 9:16
  • $\begingroup$ Depending on the computations a binary Gray code may have computational advantages (one bit changes each time) $\endgroup$ Dec 28, 2010 at 14:05
  • $\begingroup$ I googled Gray code, but I do not see how apply it to my problem Can you give more details ? $\endgroup$ Dec 28, 2010 at 14:33

3 Answers 3

0
$\begingroup$

Simply represent each vector as a binary integer:

$v_0 = "0 0 0 ... 0 0 0" = b_{n-1} b_{n-2}... b_2 b_1 b_0 = 0$

so the binary digit sequence representing $i$ is a decimal number $d$

$$d = \sum_{j=0}^{j=n-1} b_j \cdot 2^{j}$$

Given such a binary representation, you can transform the binary digits into the coefficients by mapping $0 \to -1$ and $1 \to 1$

$b_j = 0 \to r_j = (-1)$ and

$b_j = 1 \to r_j = (+1)$

Then, given a $v_j$ as a binary digit, generate $v_{j+1}$ by adding $1$ to the binary representation.

There is no shortcut around having to test each of the $2^n$ possibilities, so this does not make your overall calculations faster. It just makes it easier to generate the binary digits.

A simpler way is to iterate your index as an integer (call it $z$) from $0$ to $n-1$ and generate the binary representation of each $z$. There are many ways to do that quickly which you can find with simple searches on the internet or by asking at stackexchange.com

$\endgroup$
0
$\begingroup$

There are like $2^n$ of these vectors. If you "need to try some computations on all such vectors" then, unless you can factor something out of your computation, you will need an amount of time roughly proportional to $(2^n) \times $ (time it takes to do each computation).

$\endgroup$
0
$\begingroup$

see new edited version of the question

$\endgroup$
4
  • 3
    $\begingroup$ You should delete this answer and instead edit the question with your clarification. $\endgroup$
    – JBL
    Dec 28, 2010 at 14:24
  • $\begingroup$ If you're happy with your way of travelling V=GF($2^n$), why not transform a vector of 1s and -1s into an element of V by turning each -1 into a zero, travel through V to the next element, then turn that element of V back into a vector by turning each zero into -1? or why not transform your 1s and -1s into a binary number and add 1 and transform back? Alternatively, you've been pointed toward Gray codes a couple of times now, have you had a look at them? $\endgroup$ Dec 28, 2010 at 14:32
  • $\begingroup$ should try to think a little... $\endgroup$ Dec 28, 2010 at 14:43
  • $\begingroup$ I tracked the problem: The "primitive" polynomial method does exactly a permutation of the \it{nonzero} elements of the finite field so $0$ is not allowed, indeed $0$ goes to $(-1, \ldots, -1)$ that cycles indefinitely. In other words we cannot "travel" around all $2^n$ vectors in $GF(2)^n$ using the primitive polynomial method, but we can do "travel" around all $2^n-1$ nonzero vectors. Thus, I can apply your 1st idea Gerry to the $2^n-1$ nonzero vectors and manage the $0$ vector independently. So, putting away $0$ your tip works ! $\endgroup$ Dec 28, 2010 at 19:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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