Open MathsAll courses

Fourier smoothing of matrix squares

Written by Claude Opus 5.5 (Anthropic), October 2026. Self-checked by the writing AI. Public domain (CC0).

Let a positive semidefinite matrix-valued function be averaged, coordinate by coordinate, through random channels whose averages have small variance, as in Averaging within a cell. This lesson shows that the average can be written as a sum of squares \(\sum_qH_q^{\mathsf T}H_q\) in which the Fourier coefficients of each \(H_q\) concentrate near their own frequency \(q\): frequencies that differ from \(q\) in many coordinate blocks carry exponentially little weight [OpenAI-PSD, Section 4]. The proof processes the coordinates one at a time. Each new average is realized by stacking matrices, and the splitting lemma of Splitting positive semidefinite matrices separates the new frequencies into branches. A fourth-order quantity, the squared Frobenius norm of a weighted Gram matrix, at most doubles at each step.

1. Characters of Boolean blocks

Fix an integer \(a\ge1\) and put \(L=2^a\). Let \(Y_1,\ldots,Y_t\) be copies of the group \(\mathbb F_2^a\), and let \(\Lambda=\mathbb F_2^a\) be a further copy, used to index characters. For \(p=(p_1,\ldots,p_t)\in\Lambda^t\) and \(y=(y_1,\ldots,y_t)\in\prod_iY_i\) put \[ \chi_p(y)=(-1)^{\sum_{i=1}^tp_i\cdot y_i}, \] where \(p_i\cdot y_i\) is the dot product modulo two. The functions on \(\prod_iY_i\) carry the uniform probability measure, and \(\mathbb E_y\) denotes the average.

Lemma 1.1. The characters \(\chi_p\), \(p\in\Lambda^t\), form an orthonormal basis of the real functions on \(\prod_iY_i\). Hence every function \(H\) with values in real matrices of a fixed size satisfies \[ \begin{gathered}H(y)=\sum_{p\in\Lambda^t}\widehat H_p\,\chi_p(y),\\ \widehat H_p=\mathbb E_y\bigl[\chi_p(y)H(y)\bigr],\end{gathered} \] and \(\mathbb E_y\|H(y)\|_{\mathrm F}^2=\sum_p\|\widehat H_p\|_{\mathrm F}^2\).

Proof. We have \(\chi_p\chi_{p'}=\chi_{p+p'}\) and \(\chi_p^2=1\). If \(p\ne0\), say \(p_i\) has a nonzero coordinate \(\ell\), then changing the \(\ell\)-th bit of \(y_i\) is a bijection of \(\prod_iY_i\) that reverses the sign of \(\chi_p\), so \(\mathbb E_y\chi_p=0\). Thus \(\mathbb E_y\chi_p\chi_{p'}=1\) if \(p=p'\) and \(0\) otherwise. There are \(L^t\) characters, the dimension of the space, so they form an orthonormal basis. The expansion holds entrywise, and the last identity is Parseval's identity for each entry. \(\square\)

The block degree of \(\chi_p\) is \(|p|_{\mathrm{blk}}=|\{i:p_i\ne0\}|\). A function has block degree at most \(D\) if its Fourier coefficients vanish at every \(p\) with \(|p|_{\mathrm{blk}}>D\); the zero function qualifies. Put \[ \operatorname{dist}(p,q)=|\{i:p_i\ne q_i\}|=|p+q|_{\mathrm{blk}} . \]

Lemma 1.2 (translation by a character). Let \(q\in\Lambda^t\) and let \(H\) be a matrix-valued function whose coefficients \(\widehat H_p\) vanish whenever \(\operatorname{dist}(p,q)>D\). Then every entry of \(\chi_qH\) has block degree at most \(D\), and \((\chi_qH)^{\mathsf T}(\chi_qH)=H^{\mathsf T}H\).

Proof. \(\chi_qH=\sum_p\widehat H_p\chi_{p+q}\), so the coefficient of \(\chi_qH\) at \(p'\) is \(\widehat H_{p'+q}\), which vanishes unless \(|p'|_{\mathrm{blk}}=\operatorname{dist}(p'+q,q)\le D\). The second statement holds because \(\chi_q^2=1\). \(\square\)

The same translation of Fourier supports, which keeps squares unchanged, appears in the construction of sparse sums of squares on finite abelian groups by Fawzi, Saunderson and Parrilo [FSP 2016].

2. The theorem

For \(1\le i\le t\), let \(X_i\) and \(\mathcal M_i\) be nonempty finite sets with the uniform probability measures, and let \(Y_i\) be a copy of \(\mathbb F_2^a\) as above. For \(m\in\mathcal M_i\) and \(y\in Y_i\), let \(\pi^m_{i,y}\) be a probability measure on \(X_i\), and for a function \(Z\) on \(X_i\) put \[ (T_{i,y}Z)(m)=\sum_{x\in X_i}\pi^m_{i,y}(x)Z(x). \] Suppose that for some \(\theta\ge0\), for every \(i\), every \(y\in Y_i\) and every real function \(g\) on \(X_i\), with \(m\) uniform in \(\mathcal M_i\), \[ \begin{gathered}\mathbb E_m\pi^m_{i,y}(x)=\frac1{|X_i|}\\ (x\in X_i),\end{gathered}\tag{2.1} \] \[ \begin{aligned}&\mathbb E_m\Bigl((T_{i,y}g)(m)-\mathbb E_xg\Bigr)^2\\&\quad\le\theta\,\mathbb E_xg(x)^2 .\end{aligned}\tag{2.2} \] Let \(C_L=2^{L-1}\) be the constant of Theorem 2.1 of Splitting positive semidefinite matrices.

Theorem 2.1 (Fourier smoothing of matrix squares; [OpenAI-PSD, Theorem 4.1]). Let \(r\ge1\) and \(B>0\), and let \(F\colon\prod_iX_i\to\mathbb S^r_+\) satisfy \(\operatorname{tr}F(x)\le B\) for all \(x\). Let \(\lambda>1\) satisfy \[ L\lambda^2C_L\theta\le1 . \tag{2.3} \] For \(m=(m_1,\ldots,m_t)\in\prod_i\mathcal M_i\) and \(y\in\prod_iY_i\) put \[ \overline F_m(y)=\sum_{x\in\prod_iX_i}\Bigl(\prod_{i=1}^t\pi^{m_i}_{i,y_i}(x_i)\Bigr)F(x). \] There are an integer \(R\) and functions \(H^m_q\colon\prod_iY_i\to\mathbb R^{R\times r}\), for \(m\in\prod_i\mathcal M_i\) and \(q\in\Lambda^t\), such that \[ \begin{aligned}&\overline F_m(y)\\&\quad=\sum_{q\in\Lambda^t}H^m_q(y)^{\mathsf T}H^m_q(y),\end{aligned}\tag{2.4} \] and such that the matrices \[ \begin{gathered} U^m_q=\Bigl[\lambda^{\operatorname{dist}(q,p)/2}\,\widehat H^m_{q,p}\Bigr]_{p\in\Lambda^t},\\ C^m_q=U^m_q(U^m_q)^{\mathsf T}, \end{gathered} \] where \(\widehat H^m_{q,p}\) is the Fourier coefficient of \(H^m_q\) at \(p\) and the brackets denote the horizontal concatenation over \(p\), satisfy, for independent uniform \(m_i\), \[ \mathbb E_m\sum_{q\in\Lambda^t}\|C^m_q\|_{\mathrm F}^2\le2^tB^2 . \tag{2.5} \] Consequently, some \(m\) satisfies \[ \begin{aligned}&\sum_{q,p\in\Lambda^t}\lambda^{\operatorname{dist}(q,p)}\,\|\widehat H^m_{q,p}\|_{\mathrm F}^2\\&\quad\le L^t\sqrt r\,B\,2^{t/2}.\end{aligned}\tag{2.6} \]

The weights in (2.6) penalize the frequencies of the branch \(H^m_q\) that are far from its center \(q\). To see what (2.5) controls, fix \(m\) and \(q\), suppress them, and put \(w_p=\lambda^{\operatorname{dist}(q,p)}\). Then \[ \begin{gathered}\operatorname{tr}C=\sum_pw_p\|\widehat H_p\|_{\mathrm F}^2,\\ \|C\|_{\mathrm F}^2=\|U^{\mathsf T}U\|_{\mathrm F}^2\\=\sum_{p,p'}w_pw_{p'}\|\widehat H_p^{\mathsf T}\widehat H_{p'}\|_{\mathrm F}^2 .\end{gathered} \] The trace is the weighted Fourier mass to be bounded; the squared Frobenius norm measures the overlaps of the coefficient matrices, and it is this fourth-order quantity that the variance condition (2.2) controls.

3. The proof

Lemma 3.1. Under (2.2), every function \(Z\) on \(X_i\) with values in real matrices of any fixed size satisfies \[ \begin{aligned}&\mathbb E_m\bigl\|(T_{i,y}Z)(m)-\mathbb E_xZ\bigr\|_{\mathrm F}^2\\&\quad\le\theta\,\mathbb E_x\|Z(x)\|_{\mathrm F}^2 .\end{aligned} \]

Proof. Apply (2.2) to each entry and sum over the entries. \(\square\)

Partial averages and the potential. For \(0\le i\le t\) write \(m_{\le i}=(m_1,\ldots,m_i)\), \(y_{\le i}=(y_1,\ldots,y_i)\) and \(x_{>i}=(x_{i+1},\ldots,x_t)\). At stage \(i\) we construct, for every \(m_{\le i}\) and every \(q\in\Lambda^i\), functions \[ H^{(i)}_q(y_{\le i};x_{>i})\in\mathbb R^{R_i\times r} \] with a common number \(R_i\) of rows, such that \[ \begin{gathered}\sum_{q\in\Lambda^i}\bigl(H^{(i)}_q\bigr)^{\mathsf T}H^{(i)}_q\\=\sum_{x_{\le i}}\Bigl(\prod_{j=1}^i\pi^{m_j}_{j,y_j}(x_j)\Bigr)F(x).\end{gathered}\tag{3.1} \] Their Fourier coefficients \(\widehat H^{(i)}_{q,p}(x_{>i})\), \(p\in\Lambda^i\), are taken in the variables \(y_{\le i}\) only. Put \[ \begin{gathered} U^{(i)}_q=\Bigl[\lambda^{\operatorname{dist}(q,p)/2}\,\widehat H^{(i)}_{q,p}\Bigr]_{p\in\Lambda^i},\\ C^{(i)}_q=U^{(i)}_q\bigl(U^{(i)}_q\bigr)^{\mathsf T}, \end{gathered} \] functions of \(x_{>i}\) (and of \(m_{\le i}\)); \(U^{(i)}_q\) has \(rL^i\) columns. The potential is \[ \Phi_i=\mathbb E_{m_{\le i}}\mathbb E_{x_{>i}}\sum_{q\in\Lambda^i}\bigl\|C^{(i)}_q(x_{>i})\bigr\|_{\mathrm F}^2 , \] with all listed variables independent and uniform. At stage zero, \(\Lambda^0\) has one element \(\varnothing\); take \(R_0=r\) and \(H^{(0)}_\varnothing(x)=F(x)^{1/2}\). Then (3.1) holds, \(C^{(0)}_\varnothing=F\), and by Lemma 1.1(3) of PSD factorizations and semidefinite lifts, \[ \Phi_0=\mathbb E_x\|F(x)\|_{\mathrm F}^2\le\mathbb E_x(\operatorname{tr}F(x))^2\le B^2 . \] We show how to pass from stage \(i\) to stage \(i+1\) preserving (3.1) with \(\Phi_{i+1}\le2\Phi_i\).

The tagged stack. Fix \(m_{\le i}\), a branch \(q\in\Lambda^i\), and \(x_{>i+1}\). Abbreviate \(X=X_{i+1}\), \(Y=Y_{i+1}\), \(T_y=T_{i+1,y}\), write \(x\in X\) for the new input and \(y\in Y\) for the new character variable, and put \[ \begin{gathered}U(x)=U^{(i)}_q(x,x_{>i+1}),\\ Z(x)=U(x)^{\mathsf T}U(x).\end{gathered} \] Then \(Z(x)\) has size \(rL^i\), and \(\|Z(x)\|_{\mathrm F}=\|C^{(i)}_q(x,x_{>i+1})\|_{\mathrm F}\), since \(\|U^{\mathsf T}U\|_{\mathrm F}=\|UU^{\mathsf T}\|_{\mathrm F}\). The fixed data determine the whole function \(x\mapsto Z(x)\) before \(m_{i+1}\) is chosen.

Write \(H_x(y_{\le i})=H^{(i)}_q(y_{\le i};x,x_{>i+1})\) for \(x\in X\). For \(m\in\mathcal M_{i+1}\), define \(H'\) with \(R_{i+1}=L|X|R_i\) rows, divided into blocks indexed by \((y',x)\in Y\times X\): \[ \begin{aligned}&H'(y_{\le i},y)_{(y',x)}\\&\quad=\mathbf 1_{\{y'=y\}}\sqrt{\pi^m_y(x)}\\&\qquad\cdot H_x(y_{\le i}).\end{aligned}\tag{3.2} \] Different values of \(y\) occupy disjoint blocks, and \[ \begin{aligned}&H'^{\mathsf T}H'=\sum_{x\in X}\pi^m_y(x)\\&\qquad\cdot H_x(y_{\le i})^{\mathsf T}H_x(y_{\le i}).\end{aligned}\tag{3.3} \] For \(z\in\Lambda\), concatenate the Fourier coefficients of \(H'\) at the frequencies \((p,z)\), with the old weights: \[ \begin{gathered}V_z=\Bigl[\lambda^{\operatorname{dist}(q,p)/2}\,\widehat{H'}_{p,z}\Bigr]_{p\in\Lambda^i},\\ A_z=V_zV_z^{\mathsf T}.\end{gathered} \] Since \(\mathbb E_y[\chi_z(y)\mathbf 1_{\{y'=y\}}]=L^{-1}\chi_z(y')\), the \((y',x)\) block of \(V_z\) is \(L^{-1}\chi_z(y')\sqrt{\pi^m_{y'}(x)}\,U(x)\). Multiplying blocks, \[ \begin{aligned}&V_z^{\mathsf T}V_{z'}\\&\quad=\frac1{L^2}\sum_{y\in Y}\chi_z(y)\chi_{z'}(y)\\&\qquad\cdot(T_yZ)(m),\end{aligned}\tag{3.4} \] and \(\langle A_z,A_{z'}\rangle=\operatorname{tr}(V_zV_z^{\mathsf T}V_{z'}V_{z'}^{\mathsf T})=\|V_z^{\mathsf T}V_{z'}\|_{\mathrm F}^2\).

Lemma 3.2 (overlaps). With \(m=m_{i+1}\) uniform, \[ \begin{aligned}\mathbb E_m\langle A_z,A_{z'}\rangle&\le\frac1{L^2}\,\mathbb E_x\|Z(x)\|_{\mathrm F}^2\\&\quad\cdot\begin{cases}1,&z=z',\\ \theta,&z\ne z'.\end{cases}\end{aligned} \]

Proof. For \(z=z'\), (3.4) gives \(V_z^{\mathsf T}V_z=L^{-1}\mathbb E_y(T_yZ)(m)\). The convexity of \(\|\cdot\|_{\mathrm F}^2\), first over \(y\) and then over the probability measure \(\pi^m_y\), gives \[ \|V_z^{\mathsf T}V_z\|_{\mathrm F}^2\le\frac1{L^2}\,\mathbb E_y\sum_x\pi^m_y(x)\|Z(x)\|_{\mathrm F}^2 , \] and (2.1) turns the average over \(m\) of the right side into \(L^{-2}\mathbb E_x\|Z(x)\|_{\mathrm F}^2\). For \(z\ne z'\), the character \(\chi_z\chi_{z'}=\chi_{z+z'}\) is nontrivial, so \(\sum_y\chi_z(y)\chi_{z'}(y)=0\), and \(\mu=\mathbb E_xZ(x)\) may be subtracted from every summand in (3.4). Convexity and Lemma 3.1 give \[ \begin{aligned}&\mathbb E_m\|V_z^{\mathsf T}V_{z'}\|_{\mathrm F}^2\\&\quad\le\frac1{L^2}\,\mathbb E_y\mathbb E_m\|(T_yZ)(m)-\mu\|_{\mathrm F}^2\\&\quad\le\frac\theta{L^2}\,\mathbb E_x\|Z(x)\|_{\mathrm F}^2 .\end{aligned} \] Here Lemma 3.1 applies because \(Z\) was fixed before \(m\) was chosen. \(\square\)

Splitting the stack. For each \(m\), apply Theorem 2.1 of Splitting positive semidefinite matrices to the \(L\) operators \(A_z\), \(z\in\Lambda\), on \(\mathbb R^{R_{i+1}}\). It gives mutually orthogonal projections \(P_s\), \(s\in\Lambda\), with \(\sum_sP_s=I\). Define the branches of stage \(i+1\) by \[ H^{(i+1)}_{(q,s)}=P_sH'\qquad(s\in\Lambda), \] where \((q,s)\in\Lambda^{i+1}\). Since \(P_s^{\mathsf T}P_s=P_s\) and \(\sum_sP_s=I\), we get \(\sum_s(P_sH')^{\mathsf T}P_sH'=H'^{\mathsf T}H'\). By (3.3) and (3.1) at stage \(i\), summing over \(q\) gives (3.1) at stage \(i+1\).

The projections depend on \(m_{\le i+1}\), \(q\) and \(x_{>i+1}\), but not on \(y_{\le i+1}\). So they commute with taking Fourier coefficients: the coefficient of \(P_sH'\) at \((p,z)\) is \(P_s\widehat{H'}_{p,z}\). All \(R_{i+1}\) rows are kept, whatever the ranks of the projections, so all branches use the same number of rows. As all sets are finite, a choice of projections can be made for every value of the fixed data.

Lemma 3.3 (one step). \(\Phi_{i+1}\le2\Phi_i\).

Proof. Since \(\operatorname{dist}((q,s),(p,z))=\operatorname{dist}(q,p)+\mathbf 1_{\{s\ne z\}}\), the matrix \(U^{(i+1)}_{(q,s)}\) is the concatenation over \(z\) of the blocks \(\lambda^{\mathbf 1_{\{s\ne z\}}/2}P_sV_z\), and \[ C^{(i+1)}_{(q,s)}=\sum_{z\in\Lambda}\lambda^{\mathbf 1_{\{s\ne z\}}}P_sA_zP_s . \] By the Cauchy–Schwarz inequality for this sum of \(L\) terms, then \(\|P_zA_zP_z\|_{\mathrm F}\le\|A_z\|_{\mathrm F}\) and the inequality of Theorem 2.1 of Splitting positive semidefinite matrices, \[ \begin{aligned}&\sum_s\bigl\|C^{(i+1)}_{(q,s)}\bigr\|_{\mathrm F}^2\\&\quad\le L\sum_s\sum_z\lambda^{2\cdot\mathbf 1_{\{s\ne z\}}}\|P_sA_zP_s\|_{\mathrm F}^2\\&\quad\le L\Bigl(\sum_z\|A_z\|_{\mathrm F}^2\\&\qquad+\lambda^2C_L\sum_{z\ne z'}\langle A_z,A_{z'}\rangle\Bigr).\end{aligned} \] There are \(L\) diagonal and \(L(L-1)\) ordered off-diagonal pairs, so Lemma 3.2 and (2.3) give \[ \begin{aligned}&\mathbb E_{m_{i+1}}\sum_s\bigl\|C^{(i+1)}_{(q,s)}\bigr\|_{\mathrm F}^2\\&\quad\le\bigl(1+(L-1)\lambda^2C_L\theta\bigr)\,\mathbb E_x\|Z(x)\|_{\mathrm F}^2\\&\quad\le2\,\mathbb E_{x_{i+1}}\bigl\|C^{(i)}_q(x_{i+1},x_{>i+1})\bigr\|_{\mathrm F}^2 .\end{aligned} \] This holds for every \(m_{\le i}\), \(q\) and \(x_{>i+1}\). Under the product measure, \(m_{i+1}\) and \(x_{i+1}\) are uniform and independent of these data. Summing over \(q\) and averaging over \(m_{\le i}\) and \(x_{>i+1}\) gives \(\Phi_{i+1}\le2\Phi_i\). \(\square\)

Proof of Theorem 2.1. Starting from stage zero and applying the step \(t\) times gives, at stage \(t\), functions \(H^m_q=H^{(t)}_q\) of \(y\) alone (no inputs \(x_{>t}\) remain) with \(R=R_t\) rows, for which (3.1) is (2.4) and \(\Phi_t\le2^t\Phi_0\le2^tB^2\) is (2.5). Choose \(m\) with \(\sum_q\|C^m_q\|_{\mathrm F}^2\le2^tB^2\). Each \(U^m_q\) has \(rL^t\) columns, so \(\operatorname{rank}C^m_q\le rL^t\) whatever its number of rows. By Lemma 1.1(3) of PSD factorizations and semidefinite lifts and the Cauchy–Schwarz inequality over the \(L^t\) branches, \[ \begin{aligned}&\sum_{q,p}\lambda^{\operatorname{dist}(q,p)}\|\widehat H^m_{q,p}\|_{\mathrm F}^2=\sum_q\operatorname{tr}C^m_q\\&\quad\le\sqrt{rL^t}\sum_q\|C^m_q\|_{\mathrm F}\\&\quad\le\sqrt{rL^t}\,\sqrt{L^t}\Bigl(\sum_q\|C^m_q\|_{\mathrm F}^2\Bigr)^{1/2}\\&\quad\le L^t\sqrt r\,B\,2^{t/2}. \qquad\square\end{aligned} \]

The bound (2.6) has the factor \(L^t\) from the number of branches and \(2^{t/2}\) from the potential. In The lower bound for perfect matching these are absorbed by the weight \(\lambda^{\operatorname{dist}(q,p)}\), with \(\lambda\) a large constant, at all frequencies far from the center.

4. Exercises

4.1. Show that \(\|C\|_{\mathrm F}^2=\sum_{p,p'}w_pw_{p'}\|\widehat H_p^{\mathsf T}\widehat H_{p'}\|_{\mathrm F}^2\) and \(\operatorname{tr}C=\sum_pw_p\|\widehat H_p\|_{\mathrm F}^2\) for \(C=UU^{\mathsf T}\) and \(U=[w_p^{1/2}\widehat H_p]_p\).

4.2. Show that a positive semidefinite \(F\) satisfies \(\|F\|_{\mathrm F}\le\operatorname{tr}F\), and that \(F=I_r\) has \(\|F\|_{\mathrm{op}}=1\) and \(\|F\|_{\mathrm F}=\sqrt r\). Why does the proof of Theorem 2.1 use a bound on the trace rather than on the operator norm?

4.3. Let \(t=1\), and suppose that \(\pi^m_{1,y}\) does not depend on \(m\). Show that (2.1) forces \(\pi^m_{1,y}\) to be uniform, that (2.2) then holds with \(\theta=0\), and that \(\overline F_m(y)=\mathbb E_xF(x)\) for every \(y\). Find a representation (2.4) with \(\widehat H^m_{q,p}=0\) for \(p\ne q\).

4.4. Verify (3.4) from the description of the blocks of \(V_z\).

4.5. Show that the number of rows \(R_t\) in the proof equals \(r\,L^t\prod_i|X_i|\).

5. Solutions

4.1. \(\operatorname{tr}C=\|U\|_{\mathrm F}^2\) is the sum of the squared norms of the blocks \(w_p^{1/2}\widehat H_p\). Also \(\|UU^{\mathsf T}\|_{\mathrm F}^2=\operatorname{tr}(UU^{\mathsf T}UU^{\mathsf T})=\|U^{\mathsf T}U\|_{\mathrm F}^2\), and \(U^{\mathsf T}U\) has the blocks \((w_pw_{p'})^{1/2}\widehat H_p^{\mathsf T}\widehat H_{p'}\).

4.2. By Lemma 1.1(3) of PSD factorizations and semidefinite lifts, \(\|F\|_{\mathrm F}\le\operatorname{tr}F\). For \(F=I_r\) the eigenvalues are all one. The potential \(\Phi_0=\mathbb E_x\|F(x)\|_{\mathrm F}^2\) must be bounded independently of \(r\); a bound on the operator norm would only give \(\Phi_0\le rB^2\), and the factor \(r\) would enter (2.6).

4.3. If \(\pi^m_{1,y}=\pi_y\) does not depend on \(m\), then (2.1) says \(\pi_y(x)=1/|X_1|\). Then \(T_{1,y}g=\mathbb E_xg\) for every \(m\), the left side of (2.2) vanishes, and \(\overline F_m(y)=\mathbb E_xF(x)\) for every \(y\). Then \(H_0=(\mathbb E_xF)^{1/2}\), constant in \(y\), and \(H_q=0\) for \(q\ne0\) give (2.4); the only nonzero coefficient is \(\widehat H_{0,0}\).

4.4. The \((y',x)\) block of \(V_z\) is \(L^{-1}\chi_z(y')\sqrt{\pi^m_{y'}(x)}\,U(x)\). Hence \[ \begin{aligned}V_z^{\mathsf T}V_{z'}&=\frac1{L^2}\sum_{y',x}\chi_z(y')\chi_{z'}(y')\\&\quad\cdot\pi^m_{y'}(x)\,U(x)^{\mathsf T}U(x),\end{aligned} \] and summing over \(x\) first gives \((T_{y'}Z)(m)\).

4.5. \(R_0=r\) and \(R_{i+1}=L|X_{i+1}|R_i\).

References