user
|  |
| --- |
| This page uses content from **Wikipedia**. The original article was at Walsh matrix. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance) |

A **Walsh matrix** is a specific square matrix of dimensions 2*n*, where *n* is some particular natural number. The elements of the matrix are either **+1** or **−1** and its rows as well as columns are orthogonal, *i.e. dot product is zero*. Each row of a Walsh matrix corresponds to a Walsh function.

Walsh matrices are a special case of Hadamard matrices. The *naturally ordered* Hadamard (Walsh) matrix is defined by the recursive formula below, and the *sequency-ordered* Hadamard (Walsh) matrix is formed by rearranging the rows so that the number of sign changes in a row is in increasing order.

To generate a naturally ordered Walsh matrix

Matrices of dimension 2*k* for *k* ∈ *N* are given by the recursive formula:

:   W

    (

    2

    1
    )


    =


    [

    1

    1


    1

    −
    1
    ]
    ,


    W

    (

    2

    2
    )


    =


    [

    1

    1

    1

    1


    1

    −
    1

    1

    −
    1


    1

    1

    −
    1

    −
    1


    1

    −
    1

    −
    1

    1
    ]
    ,
    {\displaystyle {\displaystyle {\begin{aligned}W\left(2^{1}\right)&={\begin{bmatrix}1&1\\1&-1\end{bmatrix}},\\W\left(2^{2}\right)&={\begin{bmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\\\end{bmatrix}},\end{aligned}}}}

and in general

:   W

    (

    2

    k
    )
    =


    [

    W

    (

    2

    k
    −
    1
    )

    W

    (

    2

    k
    −
    1
    )


    W

    (

    2

    k
    −
    1
    )

    −
    W

    (

    2

    k
    −
    1
    )
    ]
    =
    W
    (
    2
    )
    ⊗
    W

    (

    2

    k
    −
    1
    )
    ,
    {\displaystyle {\displaystyle W\left(2^{k}\right)={\begin{bmatrix}W\left(2^{k-1}\right)&W\left(2^{k-1}\right)\\W\left(2^{k-1}\right)&-W\left(2^{k-1}\right)\end{bmatrix}}=W(2)\otimes W\left(2^{k-1}\right),}}

for 2 ≤ *k* ∈ *N*, where ⊗ denotes the Kronecker product.

Task

* Write a routine that, given a natural number **k**, returns a **naturally ordered** Walsh matrix of order 2*k*. * Display a few sample generated matrices.
:   :   *Traditionally, Walsh matrices use **1** & **-1** to denote the different cell values in text mode, or **green** and **red** blocks in image mode. You may use whichever display mode is most convenient for your particular language.*

Stretch

* Also, optionally generate **sequency ordered** Walsh matrices.
:   :   *A sequency ordered Walsh matrix has the rows sorted by number of sign changes.*

See also

* Wikipedia: Walsh matrix * Related task: Kronecker product
assistant
```
sub walsh (\m) { (map {$_?? -1 !! ' 1'}, map { :3(.base: 2) % 2 }, [X+&] ^2**m xx 2 ).batch: 2**m }

sub natural (@row) { Same }

sub sign-changes (@row) { sum (1..^@row).map: { 1 if @row[$_] !== @row[$_ - 1] } }

use SVG;

for &natural, 'natural', &sign-changes, 'sequency' -> &sort, $sort {
    for 2,4,5 -> $order {
        # ASCII text
        .put for "\nWalsh matrix - order $order ({exp($order,2)} x {exp($order,2)}), $sort order:", |walsh($order).sort: &sort;

        # SVG image
        my $side = 600;
        my $scale = $side / 2**$order;
        my $row = 0;
        my @blocks;
        my %C = ' 1' => '#0F0', '-1' => '#F00';

        for walsh($order).sort: &sort -> @row {
            my \x = $row++ * $scale;
            for @row.kv {
                my \y = $^k * $scale;
                @blocks.push: (:rect[:x(x),:y(y),:width($scale),:height($scale),:fill(%C{$^v})]);
            }
        }

        "walsh-matrix--order-{$order}--{$sort}-sort-order--raku.svg".IO.spurt:
          SVG.serialize(:svg[:width($side),:height($side),:stroke<black>,:stroke-width<1>,|@blocks])
    }
}

```

Output:

```
Walsh matrix - order 2 (4 x 4), natural order:
 1  1  1  1
 1 -1  1 -1
 1  1 -1 -1
 1 -1 -1  1

Walsh matrix - order 4 (16 x 16), natural order:
 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
 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
 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
 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

Walsh matrix - order 5 (32 x 32), natural order:
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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

Walsh matrix - order 2 (4 x 4), sequency order:
 1  1  1  1
 1  1 -1 -1
 1 -1 -1  1
 1 -1  1 -1

Walsh matrix - order 4 (16 x 16), sequency order:
 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
 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
 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
 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

Walsh matrix - order 5 (32 x 32), sequency order:
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
```

| Natural order | Sequency order |
| --- | --- |
| File:Walsh-matrix--order-2--natural-sort-order--raku.svg | File:Walsh-matrix--order-2--sign-changes-sort-order--raku.svg |
| File:Walsh-matrix--order-4--natural-sort-order--raku.svg | File:Walsh-matrix--order-4--sign-changes-sort-order--raku.svg |
| File:Walsh-matrix--order-5--natural-sort-order--raku.svg | File:Walsh-matrix--order-5--sign-changes-sort-order--raku.svg |