Editing Walsh matrix

[[File:Walsh 16 * Gould's-Morse.svg|thumb|300px|Hadamard matrix of order 16 multiplied with a vector]]

[[File:Natural and sequency ordered Walsh 16.svg|thumb|320px|Naturally ordered Hadamard matrix permuted into sequency-ordered Walsh matrix.
The number of sign changes per row in the naturally ordered matrix is (0, 15,&emsp;7, 8,&emsp;3, 12,&emsp;4, 11,&emsp;1, 14,&emsp;6, 9,&emsp;2, 13,&emsp;5, 10), in the sequency-ordered matrix the number of sign changes is consecutive.]]

[[File:LDU decomposition of Walsh 16.svg|thumb|320px|[[LU decomposition|LDU decomposition]] of a Hadamard matrix.
The ones in the [[triangular matrices]] form [[Sierpinski triangle]]s. The entries of the [[diagonal matrix]] are values from [[Gould's sequence]], with the minus signs distributed like the ones in [[Thue–Morse sequence]].]]

In [[mathematics]], a '''Walsh matrix''' is a specific [[square matrix]] of dimensions 2{{sup|''n''}}, where ''n'' is some particular [[natural number]]. The entries of the [[matrix (mathematics)|matrix]] are either +1 or −1 and its rows as well as columns are [[orthogonal]]. The Walsh matrix was proposed by [[Joseph L. Walsh]] in 1923.<ref name="kanjilal"/>  Each row of a Walsh matrix corresponds to a [[Walsh function]].

The Walsh matrices are a special case of ''[[Hadamard matrices]]'' where the rows are rearranged so that the number of sign changes in a row is in increasing order. In short, a Hadamard matrix  is defined by the [[Recursion|recursive]] formula below and is ''naturally ordered'', whereas a Walsh matrix is ''sequency-ordered''.<ref name="kanjilal">{{cite book |title=Adaptive Prediction and Predictive Control |first=P. P. |last=Kanjilal |page=210 |year=1995 |publisher=IET |location=Stevenage |isbn=0-86341-193-2 |url=https://books.google.com/books?id=h5H5voqjNIQC&pg=PA210}}</ref> Confusingly, different sources refer to either matrix as the Walsh matrix.

The Walsh matrix (and Walsh functions) are used in computing the [[Walsh transform]] and have applications in the efficient implementation of certain [[signal processing]] operations.

==Formula==
The Hadamard matrices of dimension <math>2^k</math> for <math>k \in \mathbb{N}</math> are given by the recursive formula (the lowest order of Hadamard matrix is 2):
 
:<math>\begin{align}
  H\left(2^1\right) &= \begin{bmatrix}
    1 &  1 \\
    1 & -1
  \end{bmatrix}, \\
  H\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{align}</math>

and in general
:<math>H\left(2^k\right) = \begin{bmatrix}
    H\left(2^{k-1}\right) &  H\left(2^{k-1}\right) \\
    H\left(2^{k-1}\right) & -H\left(2^{k-1}\right)
  \end{bmatrix} =
  H(2) \otimes H\left(2^{k-1}\right),
</math>

for 2&nbsp;&le;&nbsp;''k''&nbsp;&isin;&nbsp;'''N''', where ⊗ denotes the [[Kronecker product]].

===Permutation===
We can obtain a Walsh matrix from a Hadamard matrix. For that, we first generate the Hadamard matrix for a given dimension. Then, we count the number of sign changes of each row. Finally, we re-order the rows of the matrix according to the number of sign changes in ascending order. 

For example, let us assume that we have a Hadamard matrix of dimension <math>2^2</math> 

:<math>H(4) = \begin{bmatrix}
  1 &  1 &  1 &  1 \\
  1 & -1 &  1 & -1 \\
  1 &  1 & -1 & -1 \\
  1 & -1 & -1 &  1 \\
\end{bmatrix}</math>,

where the successive rows have 0, 3, 1, and 2 sign changes (we count the number of times we switch from a positive 1 to a negative 1, and vice versa). If we rearrange the rows in sequency ordering, we obtain:

:<math>W(4) = \begin{bmatrix}
  1 &  1 &  1 &  1 \\
  1 &  1 & -1 & -1 \\
  1 & -1 & -1 &  1 \\
  1 & -1 &  1 & -1 \\
\end{bmatrix},</math>

where the successive rows have 0, 1, 2, and 3 sign changes. 

===Alternative forms of the Walsh matrix===
====Sequency ordering====
The sequency ordering of the rows of the Walsh matrix can be derived from the ordering of the Hadamard matrix by first applying the [[bit-reversal permutation]] and then the [[Gray code|Gray-code]] [[permutation]]:<ref>{{cite journal |last=Yuen |first=C.-K. |year=1972 |title=Remarks on the Ordering of Walsh Functions |journal=IEEE Transactions on Computers |volume=21 |issue=12 |page=1452 |doi=10.1109/T-C.1972.223524 }}</ref>

:<math>W(8) = \begin{bmatrix}
  1 &  1 &  1 &  1 &  1 &  1 &  1 &  1 \\
  1 &  1 &  1 &  1 & -1 & -1 & -1 & -1 \\
  1 &  1 & -1 & -1 & -1 & -1 &  1 &  1 \\
  1 &  1 & -1 & -1 &  1 &  1 & -1 & -1 \\
  1 & -1 & -1 &  1 &  1 & -1 & -1 &  1 \\
  1 & -1 & -1 &  1 & -1 &  1 &  1 & -1 \\
  1 & -1 &  1 & -1 & -1 &  1 & -1 &  1 \\
  1 & -1 &  1 & -1 &  1 & -1 &  1 & -1 \\
\end{bmatrix},</math>

where the successive rows have 0, 1, 2, 3, 4, 5, 6, and 7 sign changes.

====Dyadic ordering====
:<math>W(8) = \begin{bmatrix}
  1 &  1 &  1 &  1 &  1 &  1 &  1 &  1 \\
  1 &  1 &  1 &  1 & -1 & -1 & -1 & -1 \\
  1 &  1 & -1 & -1 &  1 &  1 & -1 & -1 \\
  1 &  1 & -1 & -1 & -1 & -1 &  1 &  1 \\
  1 & -1 &  1 & -1 &  1 & -1 &  1 & -1 \\
  1 & -1 &  1 & -1 & -1 &  1 & -1 &  1 \\
  1 & -1 & -1 &  1 &  1 & -1 & -1 &  1 \\
  1 & -1 & -1 &  1 & -1 &  1 &  1 & -1 \\
\end{bmatrix},</math>

where the successive rows have 0, 1, 3, 2, 7, 6, 4, and 5 sign changes.

====Natural ordering====
:<math>H (8) = \begin{bmatrix}
  1 &  1 &  1 &  1 &  1 &  1 &  1 &  1 \\
  1 & -1 &  1 & -1 &  1 & -1 &  1 & -1 \\
  1 &  1 & -1 & -1 &  1 &  1 & -1 & -1 \\
  1 & -1 & -1 &  1 &  1 & -1 & -1 &  1 \\
  1 &  1 &  1 &  1 & -1 & -1 & -1 & -1 \\
  1 & -1 &  1 & -1 & -1 &  1 & -1 &  1 \\
  1 &  1 & -1 & -1 & -1 & -1 &  1 &  1 \\
  1 & -1 & -1 &  1 & -1 &  1 &  1 & -1 \\
\end{bmatrix},</math>

where the successive rows have 0, 7, 3, 4, 1, 6, 2, and 5 sign changes (Hadamard matrix).

== See also ==
{{Commons category|Walsh matrix}}
* [[Haar wavelet]]
* [[Quincunx matrix]]
* [[Hadamard transform]]
* [[Code-division multiple access]]
* {{OEIS2C|A228539}} ({{OEIS2C|A228540}}) – rows of the (negated) binary Walsh matrices read as reverse binary numbers
* {{OEIS2C|A197818}} – antidiagonals of the negated binary Walsh matrix read as binary numbers

==References==
{{reflist}}

{{Matrix classes}}

[[Category:Matrices (mathematics)]]

[[de:Hadamard-Matrix#Walsh-Matrizen]]