27
\$\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!

Improve this question
\$\endgroup\$
3
  • \$\begingroup\$ Sandbox \$\endgroup\$
    – Khuldraeseth na'Barya
    Apr 14, 2018 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, 2018 at 2:31
  • \$\begingroup\$ @Leo Yep, they can. Edited in. \$\endgroup\$
    – Khuldraeseth na'Barya
    Apr 16, 2018 at 18:15

21 Answers 21

Reset to default
11
\$\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; 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)
Improve this answer
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Ugh... and here I am trying to use kron. ;) \$\endgroup\$
    – beaker
    Apr 14, 2018 at 18:06
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.

Improve this answer
\$\endgroup\$
7
\$\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!

Improve this answer
\$\endgroup\$
1
  • 2
    \$\begingroup\$ You can save a byte with (iterate(\m->zipWith(++)(m++m)$m++(map(0-)<$>m))[[1]]!!). \$\endgroup\$
    – Ørjan Johansen
    Apr 15, 2018 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.

Improve this answer
\$\endgroup\$
1
  • \$\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, 2018 at 22:55
4
\$\begingroup\$

APL (Dyalog Unicode), 12 bytes

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

Try it online!

Output is a 2-dimensional array.

Improve this answer
\$\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.

Improve this answer
\$\endgroup\$
1
  • 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, 2018 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.

Improve this answer
\$\endgroup\$
6
  • \$\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, 2018 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, 2018 at 11:39
  • 1
    \$\begingroup\$ You can replace matrix(1) with t(1). \$\endgroup\$
    – JAD
    Apr 16, 2018 at 6:33
  • 1
    \$\begingroup\$ Question has been edited. You can return an integer rather than a matrix. \$\endgroup\$
    – Khuldraeseth na'Barya
    Apr 16, 2018 at 18:16
  • 1
    \$\begingroup\$ 1-2*!3:0 is shorter than c(1,1,1,-1) by three bytes. \$\endgroup\$
    – Giuseppe
    May 9, 2018 at 19:02
3
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Jelly, 14 bytes

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

Try it online!

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

Improve this answer
\$\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.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Pari/GP, 41 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

K (ngn/k), 18 bytes

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

Try it online!

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

Wolfram Language (Mathematica), 39 bytes

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

Try it online!

Almost directly copied from this answer of mine.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Nibbles, 10 bytes

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

Attempt This Online!

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

Improve this answer
\$\endgroup\$
1
\$\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!

Improve this answer
\$\endgroup\$
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.

Improve this answer
\$\endgroup\$
1
\$\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
Improve this answer
\$\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!

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ 0**n*[[1]] for -1 byte \$\endgroup\$
    – ovs
    Apr 14, 2018 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!

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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