22
2
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!
Sandbox – Khuldraeseth na'Barya – 2018-04-14T17:48:14.673
Can the results be 1-indexed? (e.g.
W(1)
returns[[1]]
,W(2)
returns[[1,1],[1,-1]
...) – Leo – 2018-04-16T02:31:23.377@Leo Yep, they can. Edited in. – Khuldraeseth na'Barya – 2018-04-16T18:15:11.360