Solving systems of linear equations with quasi-Toeplitz coefficient matrices

A matrix $A$ is said to be quasi-Toeplitz if its entries in positions $(i,j)$, $(i-1,j)$, $(i,j-1)$, and $(i-1,j-1)$ obey a linear relation with coefficients that are independent of $i$ and $j$. It is shown that a system of linear equations with a quasi-Toeplitz $n\times n$ coefficient matrix can be solved in $O(n^2)$ arithmetic operations.