Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Walsh matrix
open-in-new
<h2 id="formula">Formula</h2> <p>The Hadamard matrices of dimension 2 k {\displaystyle 2^{k}} for k ∈ N {\displaystyle k\in \mathbb {N} } are given by the recursive formula (the lowest order of Hadamard matrix is 2): </p> H ( 2 1 ) = [ 1 1 1 − 1 ] , H ( 2 2 ) = [ 1 1 1 1 1 − 1 1 − 1 1 1 − 1 − 1 1 − 1 − 1 1 ] , {\displaystyle {\begin{aligned}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{aligned}}} <p>and in general </p> H ( 2 k ) = [ H ( 2 k − 1 ) H ( 2 k − 1 ) H ( 2 k − 1 ) − H ( 2 k − 1 ) ] = H ( 2 ) ⊗ H ( 2 k − 1 ) , {\displaystyle 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),} <p>for 2 ≤ <i>k</i> ∈ N, where ⊗ denotes the <a href="/facts/Kronecker_product/gABGx6I6">Kronecker product</a>. </p> <h3>Permutation</h3> <p>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. </p><p>For example, let us assume that we have a Hadamard matrix of dimension 2 2 {\displaystyle 2^{2}} </p> H ( 4 ) = [ 1 1 1 1 1 − 1 1 − 1 1 1 − 1 − 1 1 − 1 − 1 1 ] {\displaystyle H(4)={\begin{bmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\\\end{bmatrix}}} , <p>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: </p> W ( 4 ) = [ 1 1 1 1 1 1 − 1 − 1 1 − 1 − 1 1 1 − 1 1 − 1 ] , {\displaystyle W(4)={\begin{bmatrix}1&1&1&1\\1&1&-1&-1\\1&-1&-1&1\\1&-1&1&-1\\\end{bmatrix}},} <p>where the successive rows have 0, 1, 2, and 3 sign changes. </p> <h3>Alternative forms of the Walsh matrix</h3> <h4>Sequency ordering</h4> <p>The sequency ordering of the rows of the Walsh matrix can be derived from the ordering of the Hadamard matrix by first applying the <a href="/facts/Bit-reversal_permutation/Mf1I2Vk9">bit-reversal permutation</a> and then the <a href="/facts/Gray_code/HtbVlM7T">Gray-code</a> <a href="/facts/Permutation/JSw9ukmv">permutation</a>:<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> </p> W ( 8 ) = [ 1 1 1 1 1 1 1 1 1 1 1 1 − 1 − 1 − 1 − 1 1 1 − 1 − 1 − 1 − 1 1 1 1 1 − 1 − 1 1 1 − 1 − 1 1 − 1 − 1 1 1 − 1 − 1 1 1 − 1 − 1 1 − 1 1 1 − 1 1 − 1 1 − 1 − 1 1 − 1 1 1 − 1 1 − 1 1 − 1 1 − 1 ] , {\displaystyle 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}},} <p>where the successive rows have 0, 1, 2, 3, 4, 5, 6, and 7 sign changes. </p> <h4>Dyadic ordering</h4> W ( 8 ) = [ 1 1 1 1 1 1 1 1 1 1 1 1 − 1 − 1 − 1 − 1 1 1 − 1 − 1 1 1 − 1 − 1 1 1 − 1 − 1 − 1 − 1 1 1 1 − 1 1 − 1 1 − 1 1 − 1 1 − 1 1 − 1 − 1 1 − 1 1 1 − 1 − 1 1 1 − 1 − 1 1 1 − 1 − 1 1 − 1 1 1 − 1 ] , {\displaystyle 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}},} <p>where the successive rows have 0, 1, 3, 2, 7, 6, 4, and 5 sign changes. </p> <h4>Natural ordering</h4> H ( 8 ) = [ 1 1 1 1 1 1 1 1 1 − 1 1 − 1 1 − 1 1 − 1 1 1 − 1 − 1 1 1 − 1 − 1 1 − 1 − 1 1 1 − 1 − 1 1 1 1 1 1 − 1 − 1 − 1 − 1 1 − 1 1 − 1 − 1 1 − 1 1 1 1 − 1 − 1 − 1 − 1 1 1 1 − 1 − 1 1 − 1 1 1 − 1 ] , {\displaystyle 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}},} <p>where the successive rows have 0, 7, 3, 4, 1, 6, 2, and 5 sign changes (Hadamard matrix). </p> <h2 id="see-also">See also</h2> Wikimedia Commons has media related to Walsh matrix. <ul><li><a href="/facts/Haar_wavelet/F2XIo6yq">Haar wavelet</a></li> <li><a href="/facts/Quincunx_matrix/AHNVQUD6">Quincunx matrix</a></li> <li><a href="/facts/Hadamard_transform/JFD5uojA">Hadamard transform</a></li> <li><a href="/facts/Code-division_multiple_access/o2RLKE4M">Code-division multiple access</a></li> <li><a href="/facts/On-Line_Encyclopedia_of_Integer_Sequences/yow6cVsU">OEIS</a>: A228539 (<a href="/facts/On-Line_Encyclopedia_of_Integer_Sequences/yow6cVsU">OEIS</a>: A228540) – rows of the (negated) binary Walsh matrices read as reverse binary numbers</li> <li><a href="/facts/On-Line_Encyclopedia_of_Integer_Sequences/yow6cVsU">OEIS</a>: A197818 – antidiagonals of the negated binary Walsh matrix read as binary numbers</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Kanjilal, P. P. (1995). Adaptive Prediction and Predictive Control. Stevenage: IET. p. 210. ISBN 0-86341-193-2. <a href="0-86341-193-2" target="_blank">0-86341-193-2</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Kanjilal, P. P. (1995). Adaptive Prediction and Predictive Control. Stevenage: IET. p. 210. ISBN 0-86341-193-2. <a href="0-86341-193-2" target="_blank">0-86341-193-2</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Yuen, C.-K. (1972). "Remarks on the Ordering of Walsh Functions". IEEE Transactions on Computers. 21 (12): 1452. doi:10.1109/T-C.1972.223524. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> </ol>