I am trying to come up with an invertable 1 or 2 dimensional transformation that is not unlike the fast fourier transform. Given a prior sequence $A_0 .. A_{n-1}$, we can generate a new sequence of length $ 4 \times n $ as follows: $A_0, A_0, A_1, A_1 .. A_{n-1}, A_{n-1}, A_0, \sim A_0 , A_1, \sim A_1, .. A_{n-1}, \sim A_{n-1}$
Each element is copied twice, then again, but this time each second copy is inverted. (Tilde [~] means a bit or sign flip depending on if you define it as a bit or as + or - 1.)
As an example: "1, -1" will become "1, 1; -1, -1; 1, -1; -1, 1"
To make the 2D array, the top row is equivalent to the 1d case, and the whole array has Traspose symmetry ($M_{i,j} = M_{j,i}$) other elements may be determined by taking the product or bitwise xor of the topmost and leftmost elements of the corresponding row/column. Here is a screenshot of a spreadsheet to demonstrate:
The idea here is to take the signs of each element in the $4^n$ by $4^n$ Array, and segregate evenly it into $2^n$ by $2^n$ sub arrays, and add each pixel in a $2^n$ square image after multiplying by that matrix. I have empirically determined that taking this "transform" twice does indeed lead to a scaled copy of the original image.
Is there a quick way of generating each kernel sign at $A_k(i, j)$ (where k is the number of iterations to get to a $4^k$ sign matrix) directly, without having to go through the whole duplication process?
Here I will just consider at the top row $A_k(i) := A_k(0,i)$, where $k$ is the number of iterations to get to a $4^k$-sequence. The sequence is from $i=0$ to $i=4^k-1$ inclusive. Each term is either $0$ or $1$.
Define or recall some boolean operations, for $p,q\in\{0,1\}$:
$$\begin{align*} &\text{XOR:}& p\oplus q &= (p+q)\bmod 2\\ &\text{AND:}& p\cdot q &= pq = p\times q\\ &\text{NOT:}& \neg p &= 1\oplus p \end{align*}$$
Denote a particular bit of non-negative $i$ by function $b(i,j) \in \{0,1\}$:
$$\begin{align*} b(i,j) &= \text{the $\left(2^{j}\right)$s-bit of $i$}\\ &= \left\lfloor \frac{i}{2^{j}}\right\rfloor\bmod 2\\ \text{e.g. }b(10_2, 1) &= 1 \end{align*}$$
Consider the duplication step from $A_{k-1}(\cdot)$ to $A_k(\cdot)$. The sequences have lengths $4^{k-1}$ and $4^k$ respectively. For the entry $A_k(i)$:
If $0\le i < 4^k/2 = 2^{2k-1}$, then $A_k(i)$ copies $A_{k-1}\left(\lfloor i/2\rfloor\right)$;
If $i$ is even, then $A_k(i)$ copies $A_{k-1}\left(\lfloor i/2\rfloor\bmod 4^{k-1}\right)$;
Otherwise if both $2^{2k-1}\le i < 4^k$ AND $i$ is odd, then $A_k(i)$ is $\neg A_{k-1}\left(\lfloor i/2\rfloor\bmod 4^{k-1}\right)$.
Recursively, that means to consider the $\left(2^{2k-1}\right)$s-bit AND the $1$s bit, to conditionally flip $A_{k-1}\left(\lfloor i/2\rfloor\bmod 4^{k-1}\right)$.
Represent $i$ in binary, then the following calculation may be easy to understand and calculate.
$$\begin{align*} A_k(i) &= \left[\left(2^{2k-1}\text{s-bit}\right) \cdot \left(1\text{s-bit}\right)\right] \oplus \left[A_{k-1}\left(\text{"middle" bits of }i\right)\right]\\ &= \left[b\left(i,2k-1\right)\cdot b\left(i,0\right)\right] \oplus \left[A_{k-1}\left(\text{"middle" bits of }i\right)\right]\\ &= \vdots\\ &= \left[b\left(i, 2k-1\right)\cdot b\left(i,0\right)\right] \oplus \cdots \oplus \left[b\left(i, k\right)\cdot b\left(i, k-1\right)\right] \oplus \left[A_{0}\left(0\right)\right]\\ &= \left[b\left(i, 2k-1\right)\cdot b\left(i,0\right)\right] \oplus \cdots \oplus \left[b\left(i, k\right)\cdot b\left(i, k-1\right)\right]\\ &= \bigoplus_{j=0}^{k-1} \left[b\left(i, 2k-1-j\right)\cdot b\left(i, j\right)\right] \end{align*}$$
In terms of mod 2 and floored division,
$$\begin{align*} A_k(i) &= \left[\sum_{j=0}^{k-1} \left(\left\lfloor \frac{i}{2^{2k-1-j}}\right\rfloor \bmod 2\right)\cdot\left(\left\lfloor \frac{i}{2^{j}}\right\rfloor\bmod 2\right)\right] \bmod 2\\ &= \left(\sum_{j=0}^{k-1} \left\lfloor \frac{i}{2^{2k-1-j}}\right\rfloor \cdot\left\lfloor \frac{i}{2^{j}}\right\rfloor\right) \bmod 2\\ \end{align*}$$
For example, in the $4^2\times 4^2$ square ($k=2$), the term with index $13$ (counting from $0$) is
$$\begin{align*} A_2(0,13) &= \left(\left\lfloor \frac{13}{2^{2\cdot2-1}}\right\rfloor \cdot\left\lfloor \frac{13}{2^{0}}\right\rfloor + \left\lfloor \frac{13}{2^{2\cdot2-2}}\right\rfloor \cdot\left\lfloor \frac{13}{2^{1}}\right\rfloor\right)\bmod 2\\ &= \left(\left\lfloor \frac{13}{8}\right\rfloor \cdot\left\lfloor \frac{13}{1}\right\rfloor + \left\lfloor \frac{13}{4}\right\rfloor \cdot\left\lfloor \frac{13}{2}\right\rfloor\right)\bmod 2\\ &= \left(1 \cdot 13 + 3 \cdot 6\right)\bmod 2\\ &= 1\\ & \text{(represented as $(-1)^{A_2(0,13)} = -1$ in the image)} \end{align*}$$