Complex Hermitian Toeplitz bordering yields reflection coefficients and positive pivots

Each leading block $T_k$ is positive definite: if $y\mathrm{\ne }0$ in ${\mathbb{C}}^k$, append zeros to obtain $\tilde{y}\mathrm{\ne }0$ in ${\mathbb{C}}^n$; then $y^{\ast }{T}_{k}y={\tilde{y}}^{\ast }{T}_n\tilde{y}>0$ by [F1]. Thus every nonempty $T_k$ is invertible by [F2], and $t_0>0$ by testing the first coordinate vector. The empty case has the stated empty solution.

Reversal is an involutive real permutation, so $J_k^T{J}_k=I_k$. Reversal and Hermitian symmetry give $J_k\overline{T_k}{J}_k=T_k$: its $(i,j)$ entry is $\overline{t_{(k-1-i)-(k-1-j)}}=\overline{t_{j-i}}=t_{i-j}$. Taking inverses also gives $J_k\overline{T_k^{-1}}{J}_k=T_k^{-1}$, and the same identity implies $T_k{J}_k\bar{y}=J_k\overline{T_{k}y}$ for every $y\in {\mathbb{C}}^k$.

At order $k=0$, both $T_0{\varphi }_0=g_0$ and ${\nu }_0=t_0-g_0^{\ast }{\varphi }_0$ are the empty identity and $t_0>0$ by step 1.1. This is the induction base.

For $k=0$, the formula gives ${\alpha }_1=t_1\mathrm{/}{t}_0$ and ${\varphi }_1=({\alpha }_1)$, so $T_1{\varphi }_1=g_1$ directly.

Fix $1\le k\le n-2$ and assume $T_k{\varphi }_k=g_k$, ${\nu }_k=t_0-g_k^{\ast }{\varphi }_k>0$. By step 2.1 and $T_k{\varphi }_k=g_k$, $T_k^{-1}{c}_k=J_k\overline{{\varphi }_k}$. Since $T_k$ is Hermitian and invertible, $(T_k^{-1}{)}^{\ast }=(T_k^{\ast }{)}^{-1}=T_k^{-1}$, so $g_k^{\ast }{\varphi }_k=g_k^{\ast }{T}_k^{-1}{g}_k=\overline{g_k^{\ast }{T}_k^{-1}{g}_k}$ is real. Therefore $c_k^{\ast }{T}_k^{-1}{c}_k=(J_k\overline{g_k}{)}^{\ast }(J_k\overline{{\varphi }_k})=g_k^T\overline{{\varphi }_k}=\overline{g_k^{\ast }{\varphi }_k}=g_k^{\ast }{\varphi }_k$. Thus the Schur pivot of $T_{k+1}$ after $T_k$ is ${\nu }_k$. It is positive by evaluating the positive quadratic form of $T_{k+1}$ at $(-T_k^{-1}{c}_k,1{)}^T$.

Fix $1\le k\le n-2$. The first $k$ rows of $T_{k+1}{\varphi }_{k+1}=g_{k+1}$ follow from $T_k{\varphi }_k=g_k$ and $T_k{J}_k\overline{{\varphi }_k}=c_k$ (step 2.1). The last row is $c_k^{\ast }{\varphi }_k+(t_0-c_k^{\ast }{T}_k^{-1}{c}_k){\alpha }_{k+1}=t_{k+1}$ by the definition of ${\alpha }_{k+1}$ and the pivot identity in step 3.1. Thus $T_{k+1}{\varphi }_{k+1}=g_{k+1}$.

For every update $0\le k\le n-2$, expansion gives $g_{k+1}^{\ast }{\varphi }_{k+1}=g_k^{\ast }{\varphi }_k+{\alpha }_{k+1}\overline{(t_{k+1}-c_k^{\ast }{\varphi }_k)}=g_k^{\ast }{\varphi }_k+{\nu }_k\mathrm{\mid }{\alpha }_{k+1}{\mathrm{\mid }}^2$, since ${\nu }_k$ is real; hence ${\nu }_{k+1}=t_0-g_{k+1}^{\ast }{\varphi }_{k+1}$. By step 2.3 when $k=0$ and step 4.1 when $k\ge 1$, $T_{k+1}{\varphi }_{k+1}=g_{k+1}$. Set $c_{k+1}=J_{k+1}\overline{g_{k+1}}$; step 2.1 gives $T_{k+1}^{-1}{c}_{k+1}=J_{k+1}\overline{{\varphi }_{k+1}}$, and Hermitian symmetry gives $c_{k+1}^{\ast }{T}_{k+1}^{-1}{c}_{k+1}=g_{k+1}^{\ast }{\varphi }_{k+1}$. Thus ${\nu }_{k+1}$ is the Schur complement of $T_{k+1}$ in $T_{k+2}$. This leading block is HPD by step 1.1; evaluating its quadratic form at $(-T_{k+1}^{-1}{c}_{k+1},1{)}^T$ proves ${\nu }_{k+1}>0$, including the terminal case $k+2=n$.

At stage $k$, one inner product and one vector update use $O(k+1)$ operations; summing these costs over $0\le k\le n-2$ gives $O(n^2)$. The input lags and current and next coefficient vectors require $O(n)$ storage, and no earlier coefficient vector is needed after its update.