The Hermitian positive-definite Gohberg–Semencul formula is exact and quadratic

If $n=1$, then $T_1=[t_0]$ with $t_0>0$, ${\varphi }_0$ is empty, ${\nu }_0=t_0$, and $u=v=(1\mathrm{/}{t}_0)$. Also $Z_{1}v=0$ and $L(u)=[1\mathrm{/}{t}_0]$, so the algorithm returns $b\mathrm{/}{t}_0=T_1^{-1}b$. Hence assume $n\ge 2$.

Put $g=(t_1,\dots ,t_{n-1}{)}^T$, $c=J_{n-1}\bar{g}$, and $\varphi ={\varphi }_{n-1}$. Then $T_n=\left(\begin{array}{cc}{T}_{n-1}& c\\ c^{\ast }& t_0\end{array}\right)$ and $T_{n-1}\varphi =g$ by [F1]–[F2]. The reversal identity gives $T_{n-1}^{-1}c=J_{n-1}\bar{\varphi }$. Moreover, $c^{\ast }{T}_{n-1}^{-1}c=g^T\bar{\varphi }=\overline{g^{\ast }\varphi }=g^{\ast }\varphi$, because $T_{n-1}^{\ast }=T_{n-1}$ implies $(T_{n-1}^{-1}{)}^{\ast }=(T_{n-1}^{\ast }{)}^{-1}=T_{n-1}^{-1}$. Thus the Schur complement is $t_0-c^{\ast }{T}_{n-1}^{-1}c={\nu }_{n-1}>0$. In $T_{n}v=e_{n-1}$, the top block equation gives $v_{0:n-2}=-T_{n-1}^{-1}c{v}_{n-1}=-J_{n-1}\bar{\varphi }{v}_{n-1}$; substituting this in the last equation gives ${\nu }_{n-1}{v}_{n-1}=1$. Hence $v=\left(\genfrac{}{}{0px}{}{-J_{n-1}\bar{\varphi }\mathrm{/}{\nu }_{n-1}}{1\mathrm{/}{\nu }_{n-1}}\right)$. Thus $v=T_n^{-1}{e}_{n-1}$.

Entrywise, $J_n\overline{T_n}{J}_n=T_n$ because $\overline{t_{j-i}}=t_{i-j}$. Also $X^{\ast }=(T_n^{-1}{)}^{\ast }=(T_n^{\ast }{)}^{-1}=T_n^{-1}=X$. Taking inverses in the reversal identity gives $X=J_n\bar{X}{J}_n$, so $u=J_n\bar{v}=T_n^{-1}{e}_0$. Since $v_{n-1}=1\mathrm{/}{\nu }_{n-1}$ is positive real, $u_0=v_{n-1}=1\mathrm{/}{\nu }_{n-1}>0$. The first-column block equation $g{u}_0+T_{n-1}{u}_{1:n-1}=0$ gives $u_{1:n-1}=-u_0\varphi$, and step 2.1 gives $v_{0:n-2}=-u_0{J}_{n-1}\bar{\varphi }$.

Set $X=T_n^{-1}$ and $D=X-Z_{n}X{Z}_n^{\ast }$. By step 3.1, $X$ is Hermitian and $T_{n}X=I_n$. Since the first row and column of $Z_n$ and $Z_n^{\ast }$ vanish, $D_{0j}=X_{0j}=\overline{u_j}$ and $D_{i0}=X_{i0}=u_i$; these are the corresponding first row and column of $(u{u}^{\ast }-(Z_{n}v)(Z_{n}v{)}^{\ast })\mathrm{/}{u}_0$. For $1\le i,j<n$, subtract $(T_{n}X{)}_{i-1,j-1}=I_{i-1,j-1}$ from $(T_{n}X{)}_{ij}=I_{ij}$. The identity entries agree because $i=j$ exactly when $i-1=j-1$. Reindexing the second finite sum gives ${\sum }_{k=1}^{n-1}{t}_{i-k}(X_{k,j}-X_{k-1,j-1})=-t_i{X}_{0j}+t_{i-n}{X}_{n-1,j-1}\mathrm{.}$ The coefficient matrix is $T_{n-1}$, while $X_{0j}=\overline{u_j}$ and $X_{n-1,j-1}=\overline{v_{j-1}}$.

The right side in step 4.1 is $-g\overline{u_j}+(J_{n-1}\bar{g})\overline{v_{j-1}}$. Applying $T_{n-1}^{-1}$ and using [F2] and the reversal identity gives $D_{ij}=-{\varphi }_{i-1}\overline{u_j}+(J_{n-1}\bar{\varphi }{)}_{i-1}\overline{v_{j-1}}$. By step 3.1, $u_i=-u_0{\varphi }_{i-1}$ and $v_{i-1}=-u_0(J_{n-1}\bar{\varphi }{)}_{i-1}$. Therefore, for every $i,j\ge 1$, $D_{ij}=(u_i\overline{u_j}-v_{i-1}\overline{v_{j-1}})\mathrm{/}{u}_0$. Together with the boundary entries in step 4.1, this proves $D=\frac{u{u}^{\ast }-(Z_{n}v)(Z_{n}v{)}^{\ast }}{u_0}\mathrm{.}$

The shift is nilpotent, $Z_n^n=0$. Summing $Z_n^{q}D(Z_n^{\ast }{)}^q$ for $q=0,\dots ,n-1$ telescopes to $X-Z_n^{n}X(Z_n^{\ast }{)}^n=X$. The columns of $L(u)$ are $Z_n^{q}u$, and the columns of $L(Z_{n}v)$ are $Z_n^q(Z_{n}v)$, so substituting the identity of step 5.1 into the telescoping sum yields the stated Gohberg–Semencul formula. The algorithm’s output is therefore $Xb=T_n^{-1}b$.

The reflection recursion costs $O(n^2)$ operations and $O(n)$ workspace by [F2]. Each triangular Toeplitz product in step 6.1 evaluates at most $n(n+1)\mathrm{/}2$ products and a comparable number of additions; the four products therefore cost $O(n^2)$. The two generator vectors and intermediate vectors require $O(n)$ storage, and the algorithm never materializes an $n\times n$ triangular factor.