Structure and arithmetic complexity of products and inverses of Toeplitz matrices

We derive a formula for the product of two Toeplitz matrices that is similar to the Trench formula for the inverse of a Toeplitz matrix. We then derive upper and lower bounds for number of multiplications required to compute the inverse or the product of Toeplitz matrices and consider several special cases, e.g., symmetry, as well. The lower bounds for the general cases are in agreement with earlier results, but the specialized lower bounds and all the upper bounds are new. Both upper and lower bounds are O(n2) and differ only in lower order terms.