Matrices with higher order displacement structure (Q1307296)

In this short paper, the author considers two extensions of the concept of displacement structure of a matrix, a well-established concept which helps to unify in a certain way the notion of structured matrices, such as the classes of Toeplitz, Hankel, Vandermonde or Cauchy matrices and their various generalizations. For the first extension, called higher order displacement structure, the author formulates two questions, which have an affirmative answer for many classes of structured matrices: the existence of formulas representing the inverse of a matrix with higher order displacement structure involving only \({\mathcal O}(n)\) parameters (the matrix being square of order \(n)\), and the existence of fast algorithms for solving linear systems with these matrices. For the second extension, called the omega-structured matrices, the problem is to describe the structure of the inverse of an omega-structured matrix and to construct this inverse. The paper is a survey-type one, with a good introduction and several good references containing previous results which constitute solutions to different special cases of the questions presented in the paper.