Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

all!

I need to compute the sign table for a generic $2^k$ factorial design. For $k$ factors we compute $2^k$ experiments and need to compute a $2^k \times 2^k$ matrix, as the following example for $k=3$: \begin{matrix} & I & A & B & C & AB & AC & BC & ABC\\ 1 & +1 & -1 & -1 & -1 & +1 & +1 & +1 & -1\\ 2 & +1 & +1 & -1 & -1 & -1 & -1 & +1 & +1\\ 3 & +1 & -1 & +1 & -1 & -1 & +1 & -1 & +1\\ 4 & +1 & +1 & +1 & -1 & +1 & -1 & -1 & -1\\ 5 & +1 & -1 & -1 & +1 & +1 & -1 & -1 & +1\\ 6 & +1 & +1 & -1 & +1 & -1 & +1 & -1 & -1\\ 7 & +1 & -1 & +1 & +1 & -1 & -1 & +1 & -1\\ 8 & +1 & +1 & +1 & +1 & +1 & +1 & +1 & +1\\ \end{matrix}

It is easy to compute the symbol's ($A$, $B$, $C$) columns seeing the experiment number as a bit array, where a bit zero maps to $-1$ and a bit one to $+1$. The following columns are calculated as the product of the combined symbols.

I want to compute the matrix directly, looping through $i$ and $j$, for any generic $k$. How can I find to which combination (and thus, which symbol's signs to multiply) a given $j$ corresponds to?

I hope it is clear enough; if not, please ask. Thanks for any attention!

share|improve this question

1 Answer 1

up vote 2 down vote accepted

It's hard to see the bit structure in the table the way you've ordered it. If you write it like this:

$$ \begin{matrix} & I & A & B & AB & C & AC & BC & ABC\\ 8 & +1 & +1 & +1 & +1 & +1 & +1 & +1 & +1\\ 7 & +1 & -1 & +1 & -1 & +1 & -1 & +1 & -1\\ 6 & +1 & +1 & -1 & -1 & +1 & +1 & -1 & -1\\ 5 & +1 & -1 & -1 & +1 & +1 & -1 & -1 & +1\\ 4 & +1 & +1 & +1 & +1 & -1 & -1 & -1 & -1\\ 3 & +1 & -1 & +1 & -1 & -1 & +1 & -1 & +1\\ 2 & +1 & +1 & -1 & -1 & -1 & -1 & +1 & +1\\ 1 & +1 & -1 & -1 & +1 & -1 & +1 & +1 & -1\\ \end{matrix} $$

then the entries are just the parity of the AND of the row and column indices from $0$ to $2^k-1$, which you can most efficiently get by precomputing a lookup table of size $2^k$ for the parities and indexing it with the AND.

If you want the table in the order you showed it in, the reversal of the rows is trivial (the index is $2^k$ minus your row label), but the rearrangement of the columns isn't – you've got the columns sorted by first subset size and then lexicographical order; you can get that either by sorting the columns in the end, or by making another lookup table of size $2^k$ beforehand that translates between the two column indexing schemes.

share|improve this answer
    
Thanks! Your answer gave me some insight, but reordering is starting to look like the hard combinatory problem now... –  Bruno Kim Aug 11 '12 at 22:31
    
Just as an addendum, check out the image this matrix becomes for higher $k$. –  Bruno Kim Aug 12 '12 at 3:29
    
@Bruno: The reordering shouldn't cause that much trouble; you can just pad the column labels at the front with a character that sorts first, and then sort them alphabetically. –  joriki Aug 12 '12 at 9:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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