# Generate a Walsh Matrix

A Walsh matrix is a special kind of square matrix with applications in quantum computing (and probably elsewhere, but I only care about quantum computing).

### Properties of Walsh matrices

The dimensions are the same power of 2. Therefore, we can refer to these matrices by two's exponent here, calling themW(0), W(1), W(2)...

W(0) is defined as [[1]].

For n>0, W(n) looks like:

[[W(n-1)  W(n-1)]
[W(n-1) -W(n-1)]]


So W(1) is:

[[1  1]
[1 -1]]


And W(2) is:

[[1  1  1  1]
[1 -1  1 -1]
[1  1 -1 -1]
[1 -1 -1  1]]


The pattern continues...

Write a program or function that takes as input an integer n and prints/returns W(n) in any convenient format. This can be an array of arrays, a flattened array of booleans, a .svg image, you name it, as long as it's correct.

Standard loopholes are forbidden.

### A couple things:

For W(0), the 1 need not be wrapped even once. It can be a mere integer.

You are allowed to 1-index results—W(1) would then be [[1]].

### Test cases

0 -> [[1]]
1 -> [[1  1]
[1 -1]]
2 -> [[1  1  1  1]
[1 -1  1 -1]
[1  1 -1 -1]
[1 -1 -1  1]]
3 -> [[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]]


8 -> Pastebin

This is , so the shortest solution in each language wins! Happy golfing!

• Sandbox Apr 14, 2018 at 17:48
• Can the results be 1-indexed? (e.g. W(1) returns [[1]], W(2) returns [[1,1],[1,-1]...)
– Leo
Apr 16, 2018 at 2:31
• @Leo Yep, they can. Edited in. Apr 16, 2018 at 18:15

# MATL, 4 bytes

W4YL


Try it online!

How it works:

W       % Push 2 raised to (implicit) input
4YL     % (Walsh-)Hadamard matrix of that size. Display (implicit)


Without the built-in: 11 bytes

1i:"th1M_hv


Try it online!

How it works:

For each Walsh matrix W, the next matrix is computed as [W W; WW], as is described in the challenge. The code does that n times, starting from the 1×1 matrix [1].

1       % Push 1. This is equivalent to the 1×1 matrix [1]
i:"     % Input n. Do the following n times
t     %   Duplicate
h     %   Concatenate horizontally
1M    %   Push the inputs of the latest function call
_     %   Negate
h     %   Concatenate horizontally
v     %   Concatenate vertically
% End (implicit). Display (implicit)

• Ugh... and here I am trying to use kron. ;) Apr 14, 2018 at 18:06

{map {:3(.base(2))%2},[X+&] ^2**$_ xx 2}  Try it online! Non-recursive approach, exploiting the fact that the value at coordinates x,y is (-1)**popcount(x&y). Returns a flattened array of Booleans. -4 bytes thanks to xnor's bit parity trick. # Haskell, 57 56 bytes (iterate(\m->zipWith(++)(m++m)$m++(map(0-)<$>m))[[1]]!!)  Try it online! This implements the given recursive construction. -1 byte thanks to Ørjan Johansen! • You can save a byte with (iterate(\m->zipWith(++)(m++m)$m++(map(0-)<$>m))[[1]]!!). Apr 15, 2018 at 3:14 # Octave with builtin, 18 17 bytes @(x)hadamard(2^x)  Try it online! # Octave without builtin, 56 51 47 bytes function r=f(x)r=1;if x,r=[x=f(x-1) x;x -x];end  Try it online! Thanks to @Luis Mendo for -4. # Octave with recursive lambda, 54 53 52 48 bytes f(f=@(f)@(x){@()[x=f(f)(x-1) x;x -x],1}{1+~x}())  Try it online! Thanks to this answer and this question for inspiration. • If the function is defined in a file the second end is not needed. So you can move it to TIO's header and thus remove it from the byte count Apr 15, 2018 at 22:55 # APL (Dyalog Unicode), 12 bytes (⍪⍨,⊢⍪-)⍣⎕⍪1  Try it online! Output is a 2-dimensional array. # Python 2, 75 71 bytes r=range(2**input()) print[[int(bin(x&y),13)%2or-1for x in r]for y in r]  Try it online! The Walsh Matrix seems to be related to the evil numbers. If x&y (bitwise and, 0-based coordinates) is an evil number, the value in the matrix is 1, -1 for odious numbers. The bit parity calculation int(bin(n),13)%2 is taken from Noodle9's comment on this answer. • Intuitively, the sign at (x, y) is flipped as many times as there are levels of recursion on which (x, y) is in the lower-right quadrant of the (2^k × 2^k) matrix, which occurs when x and y both have a 1 in the k-th bit. Using this fact, we can simply count the 1-bits in x&y to determine how many times to flip the sign. – Lynn Apr 15, 2018 at 0:24 # R, 615653 50 bytes w=function(n)"if"(n,w(n-1)%x%matrix(1-2*!3:0,2),1)  Try it online! Recursively calculates the matrix by Kronecker product, and returns 1 for n=0 case (thanks to Giuseppe for pointing this out, and also to JAD for helping to golf the initial version). Additional -3 bytes again thanks to Giuseppe. • Dunno if returning 1 rather than matrix(1) is valid, but if it is you can golf this down, and there's a 61 byte Reduce approach as well: try it! Apr 15, 2018 at 11:23 • I am also unsure about the format for n=0 case, most other answers wrap it in [[1]], but not all... Apr 15, 2018 at 11:39 • You can replace matrix(1) with t(1). – JAD Apr 16, 2018 at 6:33 • Question has been edited. You can return an integer rather than a matrix. Apr 16, 2018 at 18:16 • 1-2*!3:0 is shorter than c(1,1,1,-1) by three bytes. May 9, 2018 at 19:02 # Haskell, 41 bytes (iterate([id<>id,id<>map(0-)]<*>)[[1]]!!)  Try it online! The version of Haskell on TIO doesn't yet have (<>) in Prelude so I import it in the header. # Jelly, 14 bytes 1WW;"Ð€,N$ẎƊ⁸¡


Try it online!

Change the G to ŒṘ in the footer to see the actual output.

## JavaScript (ES6), 77 bytes

n=>[...Array(1<<n)].map((_,i,a)=>a.map((_,j)=>1|-f(i&j)),f=n=>n&&n%2^f(n>>1))


The naive calculation starts by taking 0 <= X, Y <= 2**N in W[N]. The simple case is when either X or Y is less than 2**(N-1), in which case we recurse on X%2**(N-1) and Y%2**(N-1). In the case of both X and Y being at least 2**(N-1) the recursive call needs to be negated.

If rather than comparing X or Y less than 2**(N-1) a bitmask X&Y&2**(N-1) is taken then this is non-zero when the recursive call needs to be negated and zero when it does not. This also avoids having to reduce modulo 2**(N-1).

The bits can of course be tested in reverse order for the same result. Then rather than doubling the bitmask each time we he coordinates can be halved instead, allowing the results to be XORed, whereby a final result of 0 means no negation and 1 means negation.

# Pari/GP, 41 bytes

f(n)=if(n,matconcat([m=f(n-1),m;m,-m]),1)


Try it online!

# K (ngn/k), 18 bytes

{x{(x,x),'x,-x}/1}


Try it online!

• Um, why is the interpreter not on GitHub? Apr 15, 2018 at 8:51
• @EriktheOutgolfer I prefer not to publish the code too widely at this time.
– ngn
Apr 15, 2018 at 15:56
• Hm, then how did you add it to TIO? Apr 15, 2018 at 17:44
• @EriktheOutgolfer I asked politely :) There are other proprietary languages on TIO - Mathematica, Dyalog.
– ngn
Apr 15, 2018 at 17:52

# Husk, 13 bytes

!¡§z+DS+†_;;1


Try it online!

1-indexed.

### Explanation

!¡§z+DS+†_;;1
¡        ;;1    Iterate the following function starting from the matrix [[1]]
§z+              Concatenate horizontally
D               The matrix with its lines doubled
S+†_           and the matrix concatenated vertically with its negation
!                Finally, return the result after as many iterations as specified
by the input (where the original matrix [[1]] is at index 1)


# Wolfram Language (Mathematica), 39 bytes

Nest[ArrayFlatten@{{#,#},{#,-#}}&,1,#]&


Try it online!

Almost directly copied from this answer of mine.

# Jelly, 8 bytes

Ø+ṗ&P¥þ


Try it online!

Ø+ṗ         Take the Cartesian product of [1, -1] with itself n times.
þ    Table that with itself by:
&        vectorizing bitwise AND (i.e. logical AND of sign bits!)
P¥      then multiply the results.


A cell is -1 iff it has an odd number of 1 bits in the bitwise AND of its 0-indices. This effectively computes [0 .. 2^n), tables that with itself by bitwise-AND-then-popcount, and raises -1 to each resulting power, but shortcuts all of those steps by representing 0 bits as 1 and 1 bits as -1 to begin with: ṗ provides the desired range without having to explicitly compute 2^n, and the product is -1 iff there are an odd number of -1s, while thanks to the magic of zipwith-vectorization and two's complement representation the bitwise AND of two sign-list integers is still their bitwise AND as sign-list integers.

# Nibbles, 10 bytes

.;,^2\$.@^-1+@&


Attempt This Online!

Uses the formula $$\W_{i,j} = \left(-1\right)^{\operatorname{popcount}(\operatorname{bitand}(i,j))}\$$.

# JavaScript (Node.js),10089 79 bytes

f=n=>n?[...(m=F=>r.map(x=>[...x,...x.map(y=>y*F)]))(1,r=f(n-1)),...m(-1)]:[[1]]


Try it online!

# 05AB1E, 16 bytes

oFoL<N&b0м€g®smˆ


Try it online!

Explanation

oF                 # for N in 2**input do:
oL<              # push range [1..2**input]-1
N&            # bitwise AND with N
b           # convert to binary
0м         # remove zeroes
€g       # length of each
®sm    # raise -1 to the power of each
ˆ   # add to global array


I wish I knew a shorter way to compute the Hamming Weight.
1δ¢˜ is the same length as 0м€g.

# Stax, 20 bytes

àΩ2┤â#╣_ê|ª⌐╦è│╞►═∞H


Run and debug it at staxlang.xyz!

Thought I'd give my own challenge a try after some time. Non-recursive approach. Not too competitive against other golfing languages...

### Unpacked (24 bytes) and explanation

|2c{ci{ci|&:B|+|1p}a*d}*
|2                          Power of 2
c                         Copy on the stack.
{                  }     Block:
c                         Copy on stack.
i                        Push iteration index (starts at 0).
{           }           Block:
ci                       Copy top of stack. Push iteration index.
|&                     Bitwise and
:B                   To binary digits
|+                 Sum
|1               Power of -1
p              Pop and print
a          Move third element (2^n) to top...
*         And execute block that many times.
*    Execute block (2^n) times


# Python 2, 80 79 bytes

f=lambda n:n<1and[[1]]or[r*2for r in f(n-1)]+[r+[-x for x in r]for r in f(n-1)]


Try it online!

• 0**n*[[1]] for -1 byte
– ovs
Apr 14, 2018 at 21:38

# Python 2, 49 bytes

Showcasing a couple of approaches using additional libraries. This one relies on a built-in in Scipy:

lambda n:hadamard(2**n)
from scipy.linalg import*


Try it online!

# Python 2, 65 bytes

And this one only uses Numpy, and solves by Kronecker product, analogously to my R answer:

from numpy import*
w=lambda n:0**n or kron(w(n-1),[[1,1],[1,-1]])


Try it online!