Algebras of higher dimension for displacement decomposition and computation with Toeplitz plus Hankel matrices

Using the concept of displacement rank, we suggest new formulas for the representation of a matrix in the form of a sum of products of matrices belonging to two particular matrix algebras having dimension about 2n and being noncommutative. So far, only n-dimensional commutative matrix algebras have been used in this kind of applications. We exploit the higher dimension of these algebras in order to reduce, with respect to other decompositions, the number of matrix products that have to be added for representing certain matrices. Interesting results are obtained in particular for Toeplitz-plus-Hankel-like matrices, a class that includes, for example, the inverses of Toeplitz plus Hankel matrices. Actually, the new representation allows us to improve the complexity bounds for the product, with preprocessing, of these matrices by a vector.