A full-matrix counterexample to the one-node Walsh--Hadamard branching conjecture

Source and scope. Joseph D. Lakey, Towards direct $L^2$-bounds for maximal partial sums of Walsh--Fourier series: The case of dyadic partial sums, arXiv:2602.17627v1, Definitions 4--5 and Conjecture 6. The related published paper by J. A. Hogan and J. D. Lakey, Mathematics 14 (2026), Article 829, studies approximate eigenvectors of the standard truncation and explicitly leaves optimal-truncation results to forthcoming work.

Conjecture 6 asserts that eliminating the unique branching node cannot decrease the spectral norm. We exhibit a dyadic truncation with exactly one node for which eliminating that node strictly decreases the norm, regardless of which branch is selected as primary. The counterexample uses the entire Walsh--Hadamard matrix, and all columns outside the two branches are strictly below the node, so their lengths are expressly required to remain unchanged. The construction extends to every dyadic dimension at least $16$.

1. A source-faithful full-matrix construction

Let $N=4$ and let $WH_4$ be the normalized $16\times16$ Walsh--Hadamard matrix in the source's Paley ordering. Its zeroth and fourth columns are

$$u=\frac14(1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1)^{\mathsf T}$$

and

$$w=\frac14(1,1,-1,-1,1,1,-1,-1,1,1,-1,-1,1,1,-1,-1)^{\mathsf T}.$$

Define the dyadic truncation map on every column by

$$\Phi(0)=\Phi(4)=16, \qquad \Phi(j)=1 \quad \text{for }j\notin\{0,4\}. \tag{1}$$

Take $\mathcal C$ to consist of all $16$ columns. Since every Walsh column starts with $1/4$, the other $14$ columns of $W_{\Phi,\mathcal C}$ are all equal to

$$z=\frac14e_0. \tag{2}$$

The two full-length columns agree in rows $0$ and $1$, differ in row $2$, and are orthogonal. Therefore they form exactly one branching node, at level

$$L=1, \qquad 2^L=2.$$

Each branch above this node consists of a single full-length column and is consequently complete. Every remaining column has length $1<2^L$: these columns are strictly below the node, not at the node.

Select either branch as primary. The other full-length column must then be shortened to its maximal prefix compatible with the primary branch, namely the common length-two prefix

$$h=\frac14(1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0)^{\mathsf T}. \tag{3}$$

The source explicitly requires every column of length strictly smaller than $2^L$ to remain unchanged. Thus all $14$ copies of $z$ remain fixed. The two possible node-reduced matrices are

$$[u\mid h\mid z\mid\cdots\mid z] \qquad\text{and}\qquad [h\mid w\mid z\mid\cdots\mid z]. \tag{4}$$

Their column Gram matrices coincide up to a permutation because

$$16\langle u,h\rangle =16\langle w,h\rangle =2, \qquad 16\langle u,z\rangle =16\langle w,z\rangle =16\langle h,z\rangle =1. \tag{5}$$

The failure therefore does not depend on a favorable interpretation of the primary-branch choice.

2. Exact spectral separation

Multiply the column Gram matrices by $16$ to clear the Walsh normalization. The $14$ equal short columns contribute a $13$-dimensional kernel. On the orthogonal complement, their normalized collective direction has coefficient $\sqrt{14}$.

Before eliminating the node, the resulting symmetric $3\times3$ matrix is

$$M_{ \mathrm{before} } = \begin{pmatrix} 16&0&\sqrt{14} \\ 0&16&\sqrt{14} \\ \sqrt{14}&\sqrt{14}&14 \end{pmatrix}. \tag{6}$$

Its antisymmetric branch direction has eigenvalue $16$. The remaining two eigenvalues are

$$15\pm\sqrt{29}.$$

Consequently

$$\|W_{\Phi,\mathcal C}\|_{2\to2}^2 = \frac{15+\sqrt{29}}{16} > \frac54, \tag{7}$$

because $\sqrt{29}>5$.

For either choice of the primary branch, the node-reduced matrix has compressed Gram matrix

$$M_{ \mathrm{after} } = \begin{pmatrix} 16&2&\sqrt{14} \\ 2&2&\sqrt{14} \\ \sqrt{14}&\sqrt{14}&14 \end{pmatrix}. \tag{8}$$

At the integer comparison point $20$, the three leading principal minors of $20I-M_{\mathrm{after}}$ are

$$4, \qquad 68, \qquad 44. \tag{9}$$

All are strictly positive. Sylvester's criterion therefore gives

$$20I-M_{\mathrm{after}}\succ0,$$

and hence

$$\|W_{\Phi',\mathcal C}\|_{2\to2}^2 < \frac{20}{16} = \frac54. \tag{10}$$

Combining (7) and (10) proves the strict reversal

$$\boxed{ \|W_{\Phi',\mathcal C}\|_{2\to2}^2 < \frac54 < \|W_{\Phi,\mathcal C}\|_{2\to2}^2. } \tag{11}$$

This contradicts the asserted inequality in Conjecture 6 for both permissible choices of primary branch.

3. Counterexamples in every dyadic dimension at least sixteen

More generally, let

$$N\ge4, \qquad n=2^N, \qquad r=n-2.$$

In the Paley-ordered $n\times n$ Walsh--Hadamard matrix, take

$$\Phi(0)=\Phi(2^{N-2})=n, \qquad \Phi(j)=1 \quad \text{for all other }j, \qquad \mathcal C=\{0,1,\ldots,n-1\}. \tag{12}$$

The column with index $2^{N-2}$ has sign pattern

$$(1,1,-1,-1,1,1,-1,-1,\ldots).$$

Exactly as above, there is one node at level $1$, both branches above it are complete singletons, and all $r$ remaining columns have length $1<2$. Under either permitted primary-branch choice the other long column becomes its length-two prefix, while every short column remains fixed.

After multiplying the Gram matrices by $n$, their nonzero spectra are the spectra of

$$M_n = \begin{pmatrix} n&0&\sqrt r \\ 0&n&\sqrt r \\ \sqrt r&\sqrt r&r \end{pmatrix}, \qquad M_n' = \begin{pmatrix} n&2&\sqrt r \\ 2&2&\sqrt r \\ \sqrt r&\sqrt r&r \end{pmatrix}. \tag{13}$$

The largest eigenvalue before node reduction is

$$\lambda = n-1+\sqrt{2n-3}. \tag{14}$$

The characteristic polynomial of $M_n'$ is

$$f_n(x) = x^3-2nx^2+(n^2-4)x-n^2+4n-4. \tag{15}$$

At the old top eigenvalue, direct substitution gives

$$f_n(\lambda) = n^2-8n+8-4\sqrt{2n-3}. \tag{16}$$

For $n\ge16$, the elementary inequality

$$\sqrt{2n-3}<\frac n2$$

holds because $(n-2)(n-6)>0$. Therefore

$$f_n(\lambda) > n^2-10n+8 >0. \tag{17}$$

The first two leading principal minors of $\lambda I-M_n'$ are

$$\lambda-n = \sqrt{2n-3}-1 >0$$

and

$$(\lambda-n)(\lambda-2)-4 >0. \tag{18}$$

Indeed, $\sqrt{2n-3}>5$ and $\lambda-2>18$ for $n\ge16$. The third leading principal minor is $f_n(\lambda)>0$ by (17). Another application of Sylvester's criterion gives

$$\lambda I-M_n'\succ0,$$

so

$$\boxed{ \|W_{\Phi',\mathcal C}\|_{2\to2} < \|W_{\Phi,\mathcal C}\|_{2\to2} \qquad \text{for every }N\ge4. } \tag{19}$$

Thus the one-node conjecture fails in infinitely many dimensions even for the full column set, genuinely below-node fixed columns, two complete above-node branches, and either choice of primary branch. This does not contradict the distinct Conjecture 8 about the more restricted standard two-branch matrices.