## Abstract

It takes of the order of N^{3} 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^{2}) 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^{2}) and O(N^{3}). 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.

Original language | English (US) |
---|---|

Pages (from-to) | 395-407 |

Number of pages | 13 |

Journal | Journal of Mathematical Analysis and Applications |

Volume | 68 |

Issue number | 2 |

DOIs | |

State | Published - Apr 1979 |

## All Science Journal Classification (ASJC) codes

- Analysis
- Applied Mathematics