The unnormalized Walsh matrix satisfies \(H_1=[1]\) and
Apply the three add/subtract stages to \((1,2,3,4,5,6,7,8)^T\). The full intermediate ledger is displayed below.
Reading the drawing
Successive butterfly stages retain all intermediate coordinates. The diagram describes the supplied finite transform and its arithmetic structure.
Drawing labels and data 37 labels
Read the original labels as selectable text. Tables preserve grid relationships; other short labels are grouped compactly.
- input
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- stage 1
- 3
- -1
- 7
- -1
- 11
- -1
- 15
- -1
- stage 2
- 10
- -2
- -4
- 0
- 26
- -2
- -4
- 0
- stage 3
- 36
- -4
- -8
- 0
- -16
- 0
- 0
- 0
\(8\log_2 8=24\) additions/subtractions; \(H_8H_8^T=8I\).
Arithmetic can be counted exactly
Each stage visits eight coordinates, producing one sum or difference per coordinate. Three stages therefore use exactly 24 additions or subtractions. No multiplication by a dense \(8\times8\) matrix is necessary.
The result \((36,-4,-8,0,-16,0,0,0)^T\) still reconstructs the input: the inverse is \(H_8^T/8\). Because the displayed transform is unnormalized, its squared output norm is eight times the squared input norm. The normalized transform \(H_8/\sqrt8\) would instead be orthogonal.
What the zeros mean
The zero coefficients arise from exact cancellation among the input values. They do not imply that the transform's defining matrix is sparse. The butterfly structure, not the final coefficient support, explains the arithmetic reduction.
The checker verifies the recursion, orthogonality, dense-versus-butterfly output, and operation count for sizes one, two, four, eight, and sixteen. These bounded tests exercise the implementation and boundary cases. The general recursion theorem remains the manuscript's mathematical statement.
Read this as
Factorization can turn a dense matrix into a short exact arithmetic circuit. Keep its normalization separate from its recursive evaluation rule.