Displacement ranks of matrices and linear equations

It takes of the order of N³ operations to solve a set of N linear equations in N unknowns or to invert the corresponding coefficient matrix. When the underlying physical problem has some time- or shift-invariance properties, the coefficient matrix is of Toeplitz (or difference or convolution) type and it is known that it can be inverted with O(N²) operations. However non-Toeplitz matrices often arise even in problems with some underlying time-invariance, e.g., as inverses or products or sums of products of possibly rectangular Toeplitz matrices. These non-Toeplitz matrices should be invertible with a complexity between O(N²) and O(N³). In this paper we provide some content for this feeling by introducing the concept of displacement ranks, which serve as a measure of how ‘close’ to Toeplitz a given matrix is.