Displacement ranks of matrices and linear equations

Thomas Kailath, Sun Yuan Kung, Martin Morf

Research output: Contribution to journalArticle

264 Scopus citations

Abstract

It takes of the order of N3 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(N2) 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(N2) and O(N3). 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 languageEnglish (US)
Pages (from-to)395-407
Number of pages13
JournalJournal of Mathematical Analysis and Applications
Volume68
Issue number2
DOIs
StatePublished - Apr 1979
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Analysis
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Displacement ranks of matrices and linear equations'. Together they form a unique fingerprint.

  • Cite this