Optimality of the standard truncation among two-branch matrices

Strict optimality among the standard two-branch Walsh--Hadamard truncations

Source and precise 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, Definition 4(ii), equation (2), and Conjecture 8. The related paper of J. A. Hogan and J. D. Lakey, An Eigenvector Problem Arising in the Study of Convergence of Walsh--Fourier Series, Mathematics 14 (2026), Article 829, studies the standard matrix's approximate eigenvectors; it explicitly leaves the optimal-truncation result to forthcoming work.

The source writes $0\le K\le N$ in Conjecture 8, but its defining equation (2) gives the last block exactly $2^{N-1}-2^K$ columns. Consequently $B_{N-1,K}$ exists precisely when

$$N\ge1, \qquad 0\le K\le N-1.$$

The source itself subsequently uses $K=N-1$ as the endpoint. We prove the conjecture for its entire well-defined range, with strict inequality throughout:

$$\boxed{ \|B_{N-1,K}\|_{2\to2} < \|W_N^{\mathrm{opt}}\|_{2\to2} \qquad (N\ge1,\ 0\le K\le N-1). } \tag{1}$$

This resolves the specific two-branch conjecture. The separate, more general one-node Conjecture 6 is not claimed here.

1. The standard truncation and its Gram matrices

Write $W_j=W_j^{\mathrm{opt}}$ and

$$G_j=W_jW_j^{\mathsf T}, \qquad \lambda_j=\lambda_{\max}(G_j)=\|W_j\|_{2\to2}^2.$$

Rows and columns are indexed starting at zero. Every nonzero entry of $W_j$ equals $2^{-j/2}$. Its zeroth column has length $2^j$, and the column with index $s\ge1$ has length

$$2^{j-1-\lfloor\log_2s\rfloor}.$$

Counting the columns which are nonzero in both rows $u$ and $v$ therefore gives

$$(G_j)_{uv} = 2^{-\lceil\log_2(\max\{u,v\}+1)\rceil}, \qquad 0\le u,v<2^j. \tag{2}$$

In particular, $G_i$ is the leading principal $2^i\times2^i$ submatrix of $G_j$ whenever $i\le j$. All the entries in (2) are strictly positive. Perron--Frobenius, applied to a positive matrix and its proper principal submatrices, thus gives

$$1=\lambda_0<\lambda_1<\cdots<\lambda_N. \tag{3}$$

For $z>\lambda_j$, introduce the positive root resolvent

$$r_j(z) = e_0^{\mathsf T}(zI-G_j)^{-1}e_0. \tag{4}$$

The principal-submatrix relationship and the entrywise positivity of $G_j$ imply

$$r_i(z)\le r_j(z) \qquad (0\le i\le j,\ z>\lambda_j). \tag{5}$$

Indeed, the convergent Neumann expansions are

$$r_j(z) = \sum_{m=0}^{\infty} \frac{(G_j^m)_{00}}{z^{m+1}}.$$

Every walk contributing to $(G_i^m)_{00}$ also occurs among the nonnegative walks contributing to $(G_j^m)_{00}$.

2. Two orthogonal branches and their common root

Let

$$v=\frac1{\sqrt2}\binom11, \qquad a=2^{-(N-K)/2}(1,-1,1,-1,\ldots,1,-1)^{\mathsf T}, \qquad e=e_0\in\mathbb R^{2^N}.$$

Set

$$A=G_{N-1}\otimes vv^{\mathsf T}, \qquad D=G_K\otimes aa^{\mathsf T}, \qquad d=2^{K-N}, \qquad c=\frac12-d. \tag{6}$$

The range of $A$ consists of vectors constant on each adjacent pair. Every vector in the range of $D$ alternates within each adjacent pair. Therefore

$$AD=DA=0. \tag{7}$$

The first block of the source's equation (2) contributes $A$ to the row Gram matrix, the second contributes $D$, and the $2^{N-1}-2^K$ identical root columns contribute $cee^{\mathsf T}$. Consequently

$$B_{N-1,K}B_{N-1,K}^{\mathsf T} =A+D+cee^{\mathsf T}. \tag{8}$$

By contrast, in the standard truncation the first $2^{N-1}$ columns contribute $A$, and all the other $2^{N-1}$ columns are root columns. Hence

$$G_N=A+\frac12ee^{\mathsf T}. \tag{9}$$

The space splits orthogonally as

$$\mathbb R^{2^N} = \left(\mathbb R^{2^{N-1}}\otimes\operatorname{span}\{v\}\right) \oplus \left(\mathbb R^{2^K}\otimes\operatorname{span}\{a\}\right) \oplus U_0. \tag{10}$$

Here $A$ acts as $G_{N-1}$ on the first summand, $D$ acts as $G_K$ on the second summand, and both vanish on $U_0$. The squared lengths of the projections of $e$ onto these three summands are, respectively,

$$\frac12, \qquad d, \qquad \frac12-d=c. \tag{11}$$

The corresponding projected vectors point toward the zeroth-coordinate vectors for $G_{N-1}$ and $G_K$. Thus for $z>\lambda_{N-1}$,

$$e^{\mathsf T}(zI-A)^{-1}e = \frac12r_{N-1}(z)+\frac1{2z}, \tag{12}$$

and

$$R_K(z) := e^{\mathsf T}(zI-A-D)^{-1}e = \frac12r_{N-1}(z)+d\,r_K(z)+\frac{c}{z}. \tag{13}$$

No eigenvector approximation or limiting argument is involved.

3. The exact secular identity at the standard norm

Let

$$\lambda=\lambda_N.$$

By (3),

$$\lambda> \lambda_{\max}(A+D) = \max\{\lambda_{N-1},\lambda_K\} =\lambda_{N-1}. \tag{14}$$

The rank-one eigenvalue equation for (9), together with (12), gives

$$1 = \frac12e^{\mathsf T}(\lambda I-A)^{-1}e = \frac14 \left(r_{N-1}(\lambda)+\frac1\lambda\right).$$

Equivalently,

$$r_{N-1}(\lambda)+\frac1\lambda=4. \tag{15}$$

This identity is exact for every $N\ge1$.

4. A strictly positive universal secular gap

First suppose $K<N-1$, so $0<d<1/2$ and $c>0$. Equations (5), (13), and (15) yield

$$\begin{aligned} R_K(\lambda) &\le \left(\frac12+d\right)r_{N-1}(\lambda) +\frac{1/2-d}{\lambda} \\ &= \left(\frac12+d\right) \left(4-\frac1\lambda\right) +\frac{1/2-d}{\lambda} \\ &= 2+4d-\frac{2d}{\lambda}. \end{aligned} \tag{16}$$

It follows that

$$\begin{aligned} 1-cR_K(\lambda) &\ge 1- \left(\frac12-d\right) \left(2+4d-\frac{2d}{\lambda}\right) \\ &= 4d^2+\frac{d(1-2d)}{\lambda} >0. \end{aligned} \tag{17}$$

Because $\lambda I-A-D$ is positive definite by (14), equation (17) and the rank-one Schur-complement criterion imply

$$\lambda I- \left(A+D+cee^{\mathsf T}\right) \succ0.$$

Using (8), we obtain

$$\lambda_{\max} \left(B_{N-1,K}B_{N-1,K}^{\mathsf T}\right) <\lambda_N. \tag{18}$$

At the remaining endpoint $K=N-1$, one has $d=1/2$ and $c=0$. The two branches are orthogonal and both have squared norm $\lambda_{N-1}$. Therefore (3) gives

$$\left\|B_{N-1,N-1}\right\|_{2\to2}^2 =\lambda_{N-1} <\lambda_N. \tag{19}$$

Taking positive square roots in (18) and (19) proves (1) for every admissible dimension and every admissible secondary-branch width. In particular, (17) supplies the explicit strictly positive secular-gap certificate

$$1-cR_K(\lambda_N) \ge 4\left(2^{K-N}\right)^2 + \frac{2^{K-N}\left(1-2^{K-N+1}\right)}{\lambda_N} >0$$

whenever $0\le K<N-1$.