Generate a Walsh Matrix

Question

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...

Your task

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 code-golf, so the shortest solution in each language wins! Happy golfing!

Answer 1

Perl 6, 63 44 40 bytes

{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.

Answer 2

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; W −W], 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)

Answer 3

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!

Answer 4

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.

Answer 5

APL (Dyalog Unicode), 12 bytes

(⍪⍨,⊢⍪-)⍣⎕⍪1

Try it online!

Output is a 2-dimensional array.

Answer 6

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.

Answer 7

R, 61 56 53 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.

Answer 8

Jelly, 14 bytes

1WW;"Ѐ,N$ẎƊ⁸¡

Try it online!

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

Answer 9

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.

Answer 10

Pari/GP, 41 bytes

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

Try it online!

Answer 11

K (ngn/k), 18 bytes

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

Try it online!

Answer 12

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.

Answer 13

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)

Answer 14

JavaScript (Node.js),100 89 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!

Answer 15

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!

Answer 16

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!

Answer 17

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.
                     d        Pop and discard
                       *    Execute block (2^n) times