thenwe have the following factorization of an theorem diagonalization of toeplitz correlation matrix an for real-valued symmetric positive-definite toeplitz matrix an of the form ( )we have ln an > dn where ln is the lower diagonal matrix ( and dn :diag( bn- is diagonal matrix proofwe give proof by induction obviouslyl > is true nextassume that the factorization lk ak > dk holds for given observe that #lk ak pk ak lk ak lk pk ak lk+ ak+ (pk xk ) > pk (pk xk )ak > pk (pk xk )pk ak it is straightforward to verify that [(pk xk )ak > pk (pk xk )pk ak [ > bk ]yielding the recursion lk ak lk pk ak lk+ ak+ > bk secondlyobserve that #lk ak > -lk ak pk xk lk pk ak lk ak lk pk ak > -pk xk lk+ ak+ lk+ > bk > > bk by noting that ak pk xk pk pk ak pk xk pk ak xk pk ak we obtainlk ak > lk+ ak+ lk+ > bk hencethe result follows by induction example (solving an xn bn in ( timeone application of the factorization in theorem is in the fast solution of linear system an xn bn where the righthand side is an arbitrary vector bn since the solution xn can be written as - xn - bn ln dn ln bn we can compute xn in ( timeas follows algorithm solving an xn bn for general right-hand side inputfirst row [ > - of matrix an and right-hand side bn outputsolution xn - bn compute ln in ( and the numbers bn- via algorithm [ xn ln bn (computed in ( time xi xi /bi- for (computed in (ntime [ xn [ xn ln (computed in ( time return xn [ xn