# Computing sign table for $2^k$ factorial experiment design

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!

-

$$\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.
Just as an addendum, check out the image this matrix becomes for higher $k$. –  Bruno Kim Aug 12 '12 at 3:29