[Question]
  [
A [**Walsh matrix**](https://en.wikipedia.org/wiki/Walsh_matrix) is a special kind of square matrix with [applications in quantum computing](https://en.wikipedia.org/wiki/Quantum_logic_gate#Hadamard_gate) (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 them`W(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](https://codegolf.meta.stackexchange.com/q/1061/73884) 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](https://pastebin.com/aYkjxk7w)
This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), so the shortest solution in each language wins! Happy golfing!
  
[Answer]
# [MATL](https://github.com/lmendo/MATL), 4 bytes
```
W4YL
```
[Try it online!](https://tio.run/##y00syfn/P9wk0uf/f2MA "MATL – 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!](https://tio.run/##y00syfn/3zDTSqkkw9A3PqPs/39jAA)
**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]
# [Perl 6](https://github.com/nxadm/rakudo-pkg), ~~63~~ ~~44~~ 40 bytes
```
{map {:3(.base(2))%2},[X+&] ^2**$_ xx 2}
```
[Try it online!](https://tio.run/##K0gtyjH7n1upoJamYPu/OjexQKHaylhDLymxOFXDSFNT1ahWJzpCWy1WIc5IS0slXqGiQsGo9n9afpFCmoaxpl5Rfkl@kQZQylhToZqLs6AoM69EAajM3l5BXddQQV1BURFIgBggLSrx1jA1SjF5StZctf8B "Perl 6 – 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](https://codegolf.stackexchange.com/users/20260/xnor)'s [bit parity trick](https://codegolf.stackexchange.com/a/144027/64121).
[Answer]
# [Haskell](https://www.haskell.org/), ~~57~~ 56 bytes
```
(iterate(\m->zipWith(++)(m++m)$m++(map(0-)<$>m))[[1]]!!)
```
[Try it online!](https://tio.run/##y0gszk7NyflfbhvzXyOzJLUosSRVIyZX164qsyA8syRDQ1tbUyNXWztXUwVIauQmFmgY6GraqNjlampGRxvGxioqav7PTczMU7BVAEr6KhQUZeaVKKgolCsY//@XnJaTmF78XzfCOSAAAA "Haskell – Try It Online") This implements the given recursive construction.
*-1 byte thanks to [Ørjan Johansen](https://codegolf.stackexchange.com/users/66041/%c3%98rjan-johansen)!*
[Answer]
# [Octave](https://www.gnu.org/software/octave/) with builtin, ~~18~~ 17 bytes
```
@(x)hadamard(2^x)
```
[Try it online!](https://tio.run/##y08uSSxL/Z9mq6en999Bo0IzIzElMTexKEXDKK5C83@ahoEmV5qGIYgwAhHGmv8B "Octave – Try It Online")
# [Octave](https://www.gnu.org/software/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!](https://tio.run/##y08uSSxL/f8/rTQvuSQzP0@hyDZNo0KzyNbQOjNNoUKnyDa6AiSia6ipUGFdoaBbEWudmpfyH4i5uNI0DDSBhCGIMAIRxpr/AQ "Octave – Try It Online") Thanks to [@Luis Mendo](https://codegolf.stackexchange.com/users/36398/luis-mendo) for -4.
# [Octave](https://www.gnu.org/software/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!](https://tio.run/##y08uSSxL/Z9mq6en9z9NI83WQSNN00GjQrPaQUMzusIWKKSpUaFrqKlQYV2hoFsRq2NYW22oXVdRq6GpCdRgoMmVpmEIIoxAhLHmfwA "Octave – Try It Online") Thanks to [this answer](https://codegolf.stackexchange.com/a/137547/32352) and [this question](https://codegolf.stackexchange.com/questions/164454/whats-the-shortest-way-to-define-an-anonymous-recursive-function-in-octave) for inspiration.
[Answer]
# [APL (Dyalog Unicode)](https://www.dyalog.com/), 12 bytes
```
(⍪⍨,⊢⍪-)⍣⎕⍪1
```
[Try it online!](https://tio.run/##jY49DsIwDEb3nMJMbSUqUbgDJ@ACaWK1kfJTNc7ABRiQglgYWWBBHCsXKQH2qoOtJ33Pn8wHXcsj166bphTvcOgRhJN5cVsQtAhDIOhxRJABgRwQit4qwTVoZRRxUs761f96H7SGYXTdyA2UPrRGeZ/zCkrhjEFLKGd7KpZrvgNliu8UX@t0fmSqqxSf6XLL2LBffkBP@UmPnrEZd5PtjKdrUcx6zUJvu9DbfQA "APL (Dyalog Unicode) – Try It Online")
Output is a 2-dimensional array.
[Answer]
# [Python 2](https://docs.python.org/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!](https://tio.run/##K6gsycjPM/r/v8i2KDEvPVXDSEsrM6@gtERDU5OroCgzryQ6GkhoJGXmaVSoVWrqGBprqhrlF@kapuUXKVQoZOYpFMWCmJUQ5v//JgA "Python 2 – 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](https://codegolf.stackexchange.com/users/9481/noodle9) comment on [this answer](https://codegolf.stackexchange.com/a/144027/64121).
[Answer]
# [R](https://www.r-project.org/), ~~61~~ ~~56~~ ~~53~~ 50 bytes
```
w=function(n)"if"(n,w(n-1)%x%matrix(1-2*!3:0,2),1)
```
[Try it online!](https://tio.run/##K/r/v9w2rTQvuSQzP08jT1MpM01JI0@nXCNP11BTtUI1N7GkKLNCw1DXSEvR2MpAx0hTx1Dzf7mGseZ/AA "R – 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]
# [Haskell](https://www.haskell.org/), 41 bytes
```
(iterate([id<>id,id<>map(0-)]<*>)[[1]]!!)
```
[Try it online!](https://tio.run/##Fcm9DsIgEADg3ae4Jg5grNG4UhZdm3Q0QYaLgF7kL5Tn99TpG74Xrm8fI1OqpXW4YsfDXHIhB0IoLeUmTHcW1H3D7oUhpzS5/Z@EVRxHadVOS2NO1g6D5ISUYYLfzVAb5Q5bCHDmzyNEfK483i7L8gU "Haskell – Try It Online")
The version of Haskell on TIO doesn't yet have `(<>)` in Prelude so I import it in the header.
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 14 bytes
```
1WW;"Ð€,N$ẎƊ⁸¡
```
[Try it online!](https://tio.run/##ASUA2v9qZWxsef//MVdXOyLDkOKCrCxOJOG6jsaK4oG4wqH/w4dH//8z "Jelly – Try It Online")
Change the `G` to `ŒṘ` in the footer to see the actual output.
[Answer]
## 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]
# [Pari/GP](http://pari.math.u-bordeaux.fr/), 41 bytes
```
f(n)=if(n,matconcat([m=f(n-1),m;m,-m]),1)
```
[Try it online!](https://tio.run/##FYwxCsAgDAC/EjoZSKBCt2I/UjqIYHFIFPH/aboc3A038mz8DrMaFFNzkuRVupa8wi3JA0ckOYVYHqSIVvsMCgl2goNgzKbLfQO@HP8G0T4 "Pari/GP – Try It Online")
[Answer]
# [K (ngn/k)](https://github.com/ngn/k), 18 bytes
```
{x{(x,x),'x,-x}/1}
```
[Try it online!](https://tio.run/##y9bNS8/7/z/NqrqiWqNCp0JTR71CR7eiVt@w9n@aggFXmoIhEBsBsfF/AA "K (ngn/k) – Try It Online")
[Answer]
# [Husk](https://github.com/barbuz/Husk), 13 bytes
```
!¡§z+DS+†_;;1
```
[Try it online!](https://tio.run/##yygtzv7/X/HQwkPLq7RdgrUfNSyIt7Y2/P//vzEA "Husk – 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]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 39 bytes
```
Nest[ArrayFlatten@{{#,#},{#,-#}}&,1,#]&
```
[Try it online!](https://tio.run/##y00syUjNTSzJTE78n2b73y@1uCTasagosdItJ7GkJDXPobpaWUe5VgdI6irX1qrpGOoox6r9T4s2jv3/X7egKDOvBAA "Wolfram Language (Mathematica) – Try It Online")
Almost directly copied from [this answer of mine](https://codegolf.stackexchange.com/a/259635/110698).
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 8 bytes
```
Ø+ṗ&P¥þ`
```
[Try it online!](https://tio.run/##ASIA3f9qZWxsef//w5gr4bmXJlDCpcO@YP/Dh0cpauKBvgoK//8z "Jelly – 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.
[Answer]
# [Nibbles](http://golfscript.com/nibbles/index.html), 10 bytes
```
.;`,^2$.@^-1+``@`&
```
[Attempt This Online!](https://ato.pxeger.com/run?1=m708LzMpKSe1eMGCpaUlaboWm_SsE3TijFT0HOJ0DbUTEhwS1CASUPkFC40hDAA)
Uses the formula \$W\_{i,j} = \left(-1\right)^{\operatorname{popcount}(\operatorname{bitand}(i,j))}\$.
[Answer]
# [JavaScript (Node.js)](https://nodejs.org),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!](https://tio.run/##XZDBboMwDIbvPIVV7ZBMDlq226awWx9g2o1FgtGwUbUBEVpRVTx754S2wAQK9vf/tmO2@TF3RVs1nbD1xlxKRa9ViX1P4zhme7VWSRvv84b1KvGoR38EclLJ6XHNNedMYqtKZoXk3Ot7RpF@TVOp9SWKOuM6UMAq2yCYvuEqOUcAx7yF1jhSSi/xeFtXNvuy2dtVJOtH0ClYiFXJqFCpq4MTKmrr6p2Jd/UPW33@Vg781CJ3BprcObNZeZfZOeNHL/0ZtTFFZzbwcB47Dgjfhw7K@mA9pGFD5uuHaAjbsGek5QBBIkD4aozAEyEBkKi4Ewh0TsSVUJXmYz956zd5vBaWYE8Y/uQtffEpLh4dISHh4/kx4pCK0Skm/A/i3T2hpXsqmbtnzsVNpnvIcZnLHw "JavaScript (Node.js) – Try It Online")
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), 16 bytes
```
oFoL<N&b0м€g®smˆ
```
[Try it online!](https://tio.run/##MzBNTDJM/f8/3y3fx8ZPLcngwp5HTWvSD60rzj3d9v@/MQA "05AB1E – 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]
# [Stax](https://github.com/tomtheisen/stax), 20 [bytes](https://github.com/tomtheisen/stax/blob/master/docs/packed.md#packed-stax)
```
àΩ2┤â#╣_ê|ª⌐╦è│╞►═∞H
```
[Run and debug it at staxlang.xyz!](https://staxlang.xyz/#p=85ea32b48323b95f887ca6a9cb8ab3c610cdec48&i=0%0A%0A1%0A%0A2%0A%0A3%0A%0A4%0A%0A5&a=1&m=1)
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
```
[Answer]
# [Python 2](https://docs.python.org/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!](https://tio.run/##XYxBCsIwFAWv8ndJLC0k7kRP8g00UoIp@lJ@I8TTR4pdiLthGGZ5l3uGay1eHuF5mwLhhLMNmJit91lYDi5mIaEEihq9Nb5j6bivtPm6efH/SVskoZC6Qg1zTtCKdhjrOMj8Wot25ufw5X1xNKZ9AA "Python 2 – Try It Online")
[Answer]
# [Python 2](https://docs.python.org/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!](https://tio.run/##BcFLCoAgEADQfacYXKlEi2gldBM3U/YZ0FEmQTy9vVd6fTOvo@1@RExHQGD3YsCEEvRqLZvplpzgO6n0JRJjfIBSyVLtuLMAATEI8nPpzTgoQlyhaTKz8qzGDw "Python 2 – Try It Online")
# [Python 2](https://docs.python.org/2/), 65 bytes
And this one only uses Numpy, and solves by Kronecker product, analogously to my [R answer](https://codegolf.stackexchange.com/a/162303/78274):
```
from numpy import*
w=lambda n:0**n or kron(w(n-1),[[1,1],[1,-1]])
```
[Try it online!](https://tio.run/##DclBCsIwEAXQvacYukpCCo24KniSNosUrQ6aP2GIhJ4@dvM2rxz1Lbj2vqtkwi@XgzgX0eou7f5NeXskwjw5BxKljwpMMxiD9csSfIj@dAwx2r6fz8QgTXg9zc3OVJRRqRm2flgx9D8 "Python 2 – Try It Online")
]