Levinson recursion

Remarks

The key fact is that both the leading and the trailing $n \times n$ blocks of $T^{n+1}$ equal $T^n$. So $T^{n+1} (f^n, 0)^T = (1, 0, \dots, 0, \varepsilon_f^n)^T$ and $T^{n+1} (0, b^n)^T = (\varepsilon_b^n, 0, \dots, 0, 1)^T$, and the stated combinations give $e_1$ and $e_{n+1}$. Similarly $T^{n+1} (x^n, 0)^T = (y_1, \dots, y_n, \varepsilon_x^n)^T$, and adding $(y_{n+1} - \varepsilon_x^n) b^{n+1}$ fixes the last entry. If $1 - \varepsilon_f^n \varepsilon_b^n$ were $0$, the nonzero vector $(f^n, 0)^T - \varepsilon_f^n (0, b^n)^T$ would lie in the kernel of $T^{n+1}$. This vector is nonzero because its last entry is $-\varepsilon_f^n b^n_n$, with $\varepsilon_f^n \ne 0$ and $b^n_n = \det T^{n-1} / \det T^n \ne 0$ by Cramer's rule. Each step costs $O(n)$ operations, which gives the total $O(N^2)$, against $O(N^3)$ for Gaussian elimination. The hypothesis on all leading minors is needed: for $T = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ the matrix is invertible but $t_0 = 0$, and the recursion cannot start. For symmetric positive definite $T$ every leading submatrix is invertible, and the special case of the Yule–Walker equations is the Levinson–Durbin recursion.

Going deeper

For a student

Toeplitz systems arise from stationary time series, in linear prediction, and in signal processing, where $T$ is a matrix of autocovariances. The recursion solves them in $O(N^2)$ time and $O(N)$ memory, which made it a standard tool in speech coding. It can be unstable when some leading submatrix is nearly singular, even if $T$ itself is well conditioned; superfast $O(N \log^2 N)$ algorithms also exist.