22
\$\begingroup\$

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

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

17 Answers 17

7
\$\begingroup\$

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.

\$\endgroup\$
10
\$\begingroup\$

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)
\$\endgroup\$
  • 2
    \$\begingroup\$ Ugh... and here I am trying to use kron. ;) \$\endgroup\$ – beaker Apr 14 '18 at 18:06
6
\$\begingroup\$

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!

\$\endgroup\$
  • 2
    \$\begingroup\$ You can save a byte with (iterate(\m->zipWith(++)(m++m)$m++(map(0-)<$>m))[[1]]!!). \$\endgroup\$ – Ørjan Johansen Apr 15 '18 at 3:14
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – Luis Mendo Apr 15 '18 at 22:55
4
\$\begingroup\$

APL (Dyalog Unicode), 12 bytes

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

Try it online!

Output is a 2-dimensional array.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Lynn Apr 15 '18 at 0:24
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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! \$\endgroup\$ – Giuseppe Apr 15 '18 at 11:23
  • \$\begingroup\$ I am also unsure about the format for n=0 case, most other answers wrap it in [[1]], but not all... \$\endgroup\$ – Kirill L. Apr 15 '18 at 11:39
  • 1
    \$\begingroup\$ You can replace matrix(1) with t(1). \$\endgroup\$ – JAD Apr 16 '18 at 6:33
  • 1
    \$\begingroup\$ Question has been edited. You can return an integer rather than a matrix. \$\endgroup\$ – Khuldraeseth na'Barya Apr 16 '18 at 18:16
  • 1
    \$\begingroup\$ 1-2*!3:0 is shorter than c(1,1,1,-1) by three bytes. \$\endgroup\$ – Giuseppe May 9 '18 at 19:02
2
\$\begingroup\$

Jelly, 14 bytes

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

Try it online!

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

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

Pari/GP, 41 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

K (ngn/k), 18 bytes

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

Try it online!

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

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.

\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ 0**n*[[1]] for -1 byte \$\endgroup\$ – ovs Apr 14 '18 at 21:38
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.