The Hadamard transform works similarly to the Fourier transform: it takes a vector and maps it to its frequency components, which are the Walsh functions. Instead of sine waves in the Fourier transform, the Walsh functions are discrete "square waves" so to speak. This makes it easier to compute.
The size of a Hadamard matrix is a power of two, 2^n x 2^n. We can build a Hadamard matrix for a given n recursively. $$H_1 = \begin{pmatrix}1&1\\1 & -1\end{pmatrix}$$ And then build block matrices in the same pattern to get $$H_n = \begin{pmatrix}H_{n-1}&H_{n-1}\\H_{n-1} & -H_{n-1}\end{pmatrix}$$
For instance,
$$H_3 = \begin{pmatrix}1&1&1&1&1&1&1&1\\1&-1&1&-1&1&-1&1&-1\\1&1&-1&-1&1&1&-1&-1\\1&-1&-1&1&1&-1&-1&1\\1&1&1&1&-1&-1&-1&-1\\1&-1&1&-1&-1&1&-1&1\\1&1&-1&-1&-1&-1&1&1\\1&-1&-1&1&-1&1&1&-1\end{pmatrix} = \begin{pmatrix}H_2&H_2\\H_2&-H_2\end{pmatrix}$$
Note how the entries are always 1 or -1 and symmetric! Easy! Then the Hadamard transform is simply multiplying H_n by a column vector and dividing by 2^n.
In order to apply the Hadamard transform to 2D images, we have to apply the 1D HT across every column and then every row. In short, for an input matrix X, the output will be a new matrix Y given by two matrix multiplications:
$$Y = \frac{1}{2^{2n}}H_nXH_n$$
Another way to implement this is by first applying the HT to every column in the image separately. Then apply it to every row, pretending they were column vectors. For example, to compute the 2D HT of $$\begin{pmatrix}2 & 3\\ 2 & 5\end{pmatrix}$$
we first do
$$\frac{1}{2}\begin{pmatrix}1&1\\1 & -1\end{pmatrix}\begin{pmatrix}2 \\ 2\end{pmatrix} = \begin{pmatrix}2 \\ 0\end{pmatrix} \quad\quad\quad \frac{1}{2}\begin{pmatrix}1&1\\1 & -1\end{pmatrix}\begin{pmatrix}3 \\ 5\end{pmatrix} = \begin{pmatrix}4 \\ -1\end{pmatrix} \quad\rightarrow\quad \begin{pmatrix}2&4\\0 & -1\end{pmatrix} $$
which takes care of the columns, and then we do the rows,
$$\frac{1}{2}\begin{pmatrix}1&1\\1 & -1\end{pmatrix}\begin{pmatrix}2 \\ 4\end{pmatrix} = \begin{pmatrix}3 \\ -1\end{pmatrix} \quad\quad\quad \frac{1}{2}\begin{pmatrix}1&1\\1 & -1\end{pmatrix}\begin{pmatrix}0 \\ -1\end{pmatrix} = \begin{pmatrix}-0.5 \\ 0.5\end{pmatrix} \quad\rightarrow\quad \begin{pmatrix}3&-1\\-0.5 & 0.5\end{pmatrix} $$
Finally, one can also compute this recursively using the fast Hadamard transform. It's up to you to find out if this is shorter or not.
Challenge
Your challenge is to perform the 2D Hadamard transform on a 2D array of arbitrary size 2^n x 2^n, where n > 0. Your code must accept the array as input (2D array or a flattened 1D array). Then perform the 2D HT and output the result.
In the spirit of flexibility, you have a choice for the output. Before multiplying by the prefactor 1/(2^(2n)), the output array is all integers. You may either multiply by the prefactor and output the answer as floats (no formatting necessary), or you may output a string "1/X*" followed by the array of integers, where X is whatever the factor should be. The last test case shows this as an example.
You may not import the Hadamard matrices from some convenient file that already contains them; you must build them inside the program.
Test Cases
Input:
2,3
2,5
Output:
3,-1
-0.5,0.5
Input:
1,1,1,1
1,1,1,1
1,1,1,1
1,1,1,1
Output:
1,0,0,0
0,0,0,0
0,0,0,0
0,0,0,0
Input:
1,0,0,0
1,1,0,0
1,1,1,0
1,1,1,1
Output:
0.6250,0.1250,0.2500,0
-0.1250,0.1250,0,0
-0.2500,0,0.1250,0.1250
0,0,-0.1250,0.1250
Input:
0,0,0,0,0,0,0,1
0,0,0,0,0,0,2,0
0,0,0,0,0,3,0,0
0,0,0,0,4,0,0,0
0,0,0,5,0,0,0,0
0,0,6,0,0,0,0,0
0,7,0,0,0,0,0,0
8,0,0,0,0,0,0,0
Output:
1/64*
36,4,8,0,16,0,0,0
-4,-36,0,-8,0,-16,0,0
-8,0,-36,-4,0,0,-16,0
0,8,4,36,0,0,0,16
-16,0,0,0,-36,-4,-8,0
0,16,0,0,4,36,0,8
0,0,16,0,8,0,36,4
0,0,0,-16,0,-8,-4,-36
Scoring
This is code golf, so the smallest program in bytes wins.
