$\text{1}$

## Generalized inversion of Toeplitz-plus-Hankel matrices

### November 27, 2006

$\text{}*\text{}$  avm@susu.ac.ru, oli@susu.ac.ruSouth Ural State University, Chelyabinsk, Russia. $\text{}*\text{}$  avm@susu.ac.ru, oli@susu.ac.ruSouth Ural State University, Chelyabinsk, Russia. A generalized inversion of block $T+H$  matrix is obtained for the first time.
In a particular case when $T+H$  matrix is invertible, the method allows to obtain its inverse matrix without an additional condition of invertibility of the corresponding $T-H$  matrix.
Keywords: Toeplitz-plus-Hankel matrices, generalized inversion.

1. Introduction

In many applications, e.g. digital signal processing, discrete inverse scattering, linear prediction etc., Toeplitz-plus-Hankel ( $T+H$  ) matrices need to be inverted.
(For further applications see [1and references therein).
Firstly the $T+H$  matrix inversion problem has been solved in [2where it was reduced to the inversion problem of the block Toeplitz matrix (the so-called mosaic matrix). The drawback of the method is that it does not work for any invertible $T+H$  matrix since it requires also invertibility of the corresponding $T-H$  matrix. This drawback appeared also in [3, [4. Later on the drawback was put out (see, e.g. [4, [5), moreover, the inversion problem was solved for the block $T+H$  matrix [6,[7.
The generalized inversion of Toeplitz-plus-Hankel matrices is of great interest to, e.g., Pade-Chebyshev approximations. The generalized inversion for matrix $A$  is meant to be the matrix ${A}^{†}$  such that $A{A}^{†}A=A.$  Our goal is to obtain the generalized inversion of block $T+H$  matrices with help of the well-known method of reducing the block-diagonal matrix formed from the $T+H$  and $T-H$  matrices to the mosaic matrix (as in the work [2).
We will need the generalized inversion for the block Toeplitz matrix which has been already found in, e.g. [8. It is shown in the present paper that there is no need for $T-H$  matrix to be inverted: if the $T+H$  matrix is invertible than the obtained generalized inverse matrix proves to be its inverse matrix.
The paper is organized as follows. At first the basic definitions and the main results of the paper [8are given, then our main theorem is formulated and proved. This theorem is demonstrated with an example in the end of the paper.
This work was supported by Russian Foundation for Basic Research (RFFI), grant N 04-04-96006.

2. The basic definitions and notations

We are going to find a generalized inversion for the block Toeplitz-plus-Hankel matrix $T+H=\left(\begin{array}{cccc}{a}_{0}& {a}_{-1}& ...& {a}_{-m}\\ {a}_{1}& {a}_{0}& ...& {a}_{-m+1}\\ ...& ...& ...& ...\\ {a}_{n}& {a}_{n-1}& ...& {a}_{n-m}\end{array}\right)+\left(\begin{array}{cccc}{b}_{0}& {b}_{1}& ...& {b}_{m}\\ {b}_{1}& {b}_{2}& ...& {b}_{m+1}\\ ...& ...& ...& ...\\ {b}_{n}& {b}_{n+1}& ...& {b}_{n+m}\end{array}\right),$  with ${a}_{j},{b}_{j}\in {\mathbb{C}}^{p×q}$  .
We denote ${a}_{-m}^{n}\left(z\right)={a}_{-m}{z}^{-m}+\dots +{a}_{0}+\dots +{a}_{n}{z}^{n},$  ${b}_{0}^{n+m}\left(z\right)={b}_{0}+{b}_{1}z+\dots +{b}_{n+m}{z}^{n+m}$  and introduce an auxilary matrix function $A\left(z\right)=\left(\begin{array}{cc}{z}^{n}{b}_{0}^{n+m}\left({z}^{-1}\right)& {z}^{n-m}{a}_{-m}^{n}\left({z}^{-1}\right)\\ {a}_{-m}^{n}\left(z\right)& {z}^{-m}{b}_{0}^{n+m}\left(z\right)\end{array}\right).$  Obviously, $A\left(z\right)={\sum }_{j=-m}^{n}{A}_{j}{z}^{j},$  with ${A}_{j}\in {\mathbb{C}}^{2p×2q}$  and
 $\begin{array}{c}{A}_{j}=\left(\begin{array}{cc}{b}_{n-j}& {a}_{n-m-j}\\ {a}_{j}& {b}_{j+m}\end{array}\right).\end{array}$ (2.1)
Thus, $A\left(z\right)$  is the generating function for the sequence of matrices ${A}_{-m},\dots ,{A}_{0},$  $\dots ,{A}_{n}$  .
Later on we will need a generalized inversion for the block Toeplitz matrix ${T}_{A}=\left(\begin{array}{cccc}{A}_{0}& {A}_{-1}& ...& {A}_{-m}\\ {A}_{1}& {A}_{0}& ...& {A}_{-m+1}\\ ...& ...& ...& ...\\ {A}_{n}& {A}_{n-1}& ...& {A}_{n-m}\end{array}\right).$  It has been already found in [8. In order to use this result we should introduce the notations of the essential indices and polynomials of the sequence ${A}_{-m},\dots ,{A}_{0},\dots ,{A}_{n}$  .
We include the matrix ${T}_{A}\equiv {T}_{0}$  into the family of the block Toeplitz matrices ${T}_{k}=\left(\begin{array}{cccc}{A}_{k}& {A}_{k-1}& ...& {A}_{-m}\\ {A}_{k+1}& {A}_{k}& ...& {A}_{-m+1}\\ ...& ...& ...& ...\\ {A}_{n}& {A}_{n-1}& ...& {A}_{n-m-k}\end{array}\right),-m\le k\le n.$  The matrices ${T}_{k}$  are of the same structure and it is reasonable that they should be examined together.
We are interested in right kernels of ${T}_{k}$  . For the sake of convenience let us pass from the spaces $kerR{T}_{k}$  to the isomorphic spaces ${\mathcal{N}}_{k}^{R}$  of generating polynomials.
To do this we define the operator ${\sigma }_{R}$  acting from the space of rational matrix functions $R\left(z\right)={\sum }_{j=-n}^{m}{r}_{j}{z}^{j},{r}_{j}\in {\mathbb{C}}^{2q×l}$  to the space ${\mathbb{C}}^{2p×l}$  according to ${\sigma }_{R}\left\{R\left(z\right)\right\}={\sum }_{j=-n}^{m}{A}_{-j}{r}_{j}.$  By ${\mathcal{N}}_{k}^{R},k=-m,\dots ,n$  , we denote the space of vector polynomials $R\left(z\right)={\sum }_{j=0}^{k+m}{r}_{j}{z}^{j},{r}_{j}\in {\mathbb{C}}^{2q×1}$  , such that ${\sigma }_{R}\left\{{z}^{-i}R\left(z\right)\right\}=0,i=k,k+1,\dots ,n.$  ${\mathcal{N}}_{k}^{R}$  is evident to be isomorphic to $kerR{T}_{k}.$  It is convenient to put ${\mathcal{N}}_{-m-1}^{R}=0$  and denote by ${\mathcal{N}}_{n+1}^{R}$  the $2\left(n+m+2\right)q$  -dimensional space of all vector polynomials in $z$  with formal degree $n+m+1$  .
Similarly, one may define spaces ${\mathcal{N}}_{k}^{L}$  which are isomorphic to $kerL{T}_{k}.$  We denote ${ker}_{L}A=\left\{y|yA=0\right\}.$  Let us put also $\alpha =dim{\mathcal{N}}_{-m}^{R}$  and $\omega =dim{\mathcal{N}}_{n}^{L}.$  We will say that the sequence ${A}_{-m},\dots ,{A}_{n}$  is left (right) regular if $\alpha =0\left(\omega =0\right).$  Otherwise, the sequence is not regular and $\alpha \left(\omega \right)$  is its left (right) defect. The sequence is called regular if $\alpha =\omega =0$  . It is evident that $\alpha <2q,\omega <2p$  for the nonzero sequence.
We will denote ${d}_{k}^{R}=dim{\mathcal{N}}_{k}^{R},$  ${\Delta }_{k}^{R}={d}_{k}^{R}-{d}_{k-1}^{R},k=-m,\dots ,n+1$  .
As it is proved in [8, for any sequence ${A}_{-m},\dots ,{A}_{n}$  the following inequalities hold: $\alpha ={\Delta }_{-m}^{R}\le {\Delta }_{-m+1}^{R}\le \dots \le {\Delta }_{n}^{R}\le {\Delta }_{n+1}^{R}=2\left(p+q\right)-\omega .$  It means that there are $2\left(p+q\right)-\alpha -\omega$  integers ${\mu }_{\alpha }\le {\mu }_{\alpha +1}\le \dots \le {\mu }_{2\left(p+q\right)-\alpha -\omega }$  , satisfying equations
 $\begin{array}{c}\begin{array}{ccccccc}{\Delta }_{-m}^{R}& =& ...& =& {\Delta }_{{\mu }_{\alpha +1}}^{R}& =& \alpha ,\\ & & \cdot \cdot \cdot & & & & \\ {\Delta }_{{\mu }_{i}+1}^{R}& =& ...& =& {\Delta }_{{\mu }_{i+1}}^{R}& =& i,\\ & & \cdot \cdot \cdot & & & & \\ {\Delta }_{{\mu }_{2\left(p+q\right)-\omega }+1}^{R}& =& ...& =& {\Delta }_{n+1}^{R}& =& 2\left(p+q\right)-\omega .\end{array}\end{array}$ (2.2)
If the $i$  th row in ( 2.2 ) is absent, we assume ${\mu }_{i}={\mu }_{i+1}.$  Let us put also ${\mu }_{1}=\dots ={\mu }_{\alpha }=-m-1$  if $\alpha \ne 0$  and ${\mu }_{2\left(p+q\right)-\omega +1}=\dots ={\mu }_{2\left(p+q\right)}$  if $\omega \ne 0.$  Thus there is a set of $2\left(p+q\right)$  integers, satisfying ( 2.2 ), for any sequence ${A}_{-m},\dots ,{A}_{n}$  . We will call these integers as indices of the sequence.
Now we will define the right essential polynomials of the sequence.
It follows from the definition of ${\mathcal{N}}_{k}^{R}$  that ${\mathcal{N}}_{k}^{R}$  and $z{\mathcal{N}}_{k}^{R}$  are the subspaces of ${\mathcal{N}}_{k+1}^{R}$  , $k=-m-1,\dots ,n$  , moreover, ${\mathcal{N}}_{k}^{R}\cap z{\mathcal{N}}_{k}^{R}={\mathcal{N}}_{k-1}^{R}$  . Then ${\mathcal{N}}_{k+1}^{R}=\left({\mathcal{N}}_{k}^{R}+z{\mathcal{N}}_{k}^{R}\right)\oplus {\mathcal{ℋ}}_{k+1}^{R},$  where ${\mathcal{ℋ}}_{k+1}^{R}$  is the complement of ${\mathcal{N}}_{k}^{R}+z{\mathcal{N}}_{k}^{R}$  to the whole ${\mathcal{N}}_{k+1}^{R}.$  Obviously, $dim{\mathcal{ℋ}}_{k+1}^{R}={\Delta }_{k+1}^{R}-{\Delta }_{k}^{R}.$  Hence $dim{\mathcal{ℋ}}_{k+1}^{R}\ne 0$  iff $k={\mu }_{i}.$  In this case $dim{\mathcal{ℋ}}_{k+1}^{R}$  is equal to the multiplicity ${k}_{i}$  of the index ${\mu }_{i}.$
Definition 2.1. If $\alpha \ne 0$  then any column polynomials ${R}_{1}\left(z\right),\dots ,$  ${R}_{\alpha }\left(z\right)$  forming the basis of ${\mathcal{N}}_{-m}^{R}$  will be called right essential polynomials of the sequence ${A}_{-m},\dots ,$  ${A}_{0},$  $\dots ,{A}_{n}$  . They correspond to the index ${\mu }_{1}=-m-1$  with the multiplicity $\alpha$  .
Any vector polynomials ${R}_{j}\left(z\right),\dots ,{R}_{j+{k}_{j}-1}\left(z\right)$  forming the basis for ${\mathcal{ℋ}}_{{\mu }_{j}+1}^{R}$  will be called right essential polynomials of the sequence ${A}_{-m},\dots ,$  ${A}_{0},$  $\dots ,{A}_{n}$  .
They correspond to the index ${\mu }_{j}$  with the multiplicity ${k}_{j}$  , $\alpha +1\le j\le 2\left(p+q\right)-\omega .$
Similarly, one may define the left essential polynomials.
There are $2\left(p+q\right)-\omega$  right and $2\left(p+q\right)-\alpha$  left essential polynomials of the sequence ${A}_{-m},\dots ,{A}_{n}$  .
If $\alpha \ne 0$  or $\omega \ne 0$  then there is a lack of essential polynomials. But actually we can always complement the number of right (when $p\le q$  ) or left (when $p\ge q$  ) essential polynomials to $2\left(p+q\right).$  (The complement procedure was described in [8).
Henceforth, for definiteness sake, we will suppose that we have got the full set of $2\left(p+q\right)$  right essential polinomials, i.e. either $\omega =0$  or $p\le q$  .
The set of the left essential polynomials could always be recovered with the help of the so-called conformation procedure of the right and left essential polynomials. Let us describe how for the given set of the right essential polynomials ${R}_{1}\left(z\right),$  $\dots ,{R}_{2\left(p+q\right)}\left(z\right)$  , ${R}_{j}\left(z\right)\in {\mathbb{C}}^{2q×1}\left[z\right]$  one can construct the conforming left essential polynomials ${L}_{1}\left(z\right),\dots ,{L}_{2\left(p+q\right)}\left(z\right)$  , ${L}_{j}\left(z\right)\in {\mathbb{C}}^{1×2p}\left[z\right]$  .
We introduce the matrix of the right essential polynomials $\mathcal{ℛ}\left(z\right)=\left({R}_{1}\left(z\right)\dots {R}_{2\left(p+q\right)}\left(z\right)\right)$  and find the matrix polynomial ${\alpha }_{-}\left(z\right)$  from the next decomposition $A\left(z\right)\mathcal{ℛ}\left(z\right)={\alpha }_{-}\left(z\right)d\left(z\right)-{z}^{n+1}{\beta }_{+}\left(z\right).$  Here $d\left(z\right)=diag\left[{z}^{{\mu }_{1}},\dots ,{z}^{{\mu }_{2\left(p+q\right)}}\right],$  ${\beta }_{+}\left(z\right)$  is the matrix polynomial in $z$  , ${\alpha }_{-}\left(z\right)$  is the matrix polynomial in ${z}^{-1}$  . Both of them have sizes $2p×2\left(p+q\right)$  .
Let ${U}_{-}\left(z\right)$  be the matrix polynomial in ${z}^{-1}$  such that:
${U}_{-}\left(z\right)=\left(\begin{array}{c}{\mathcal{ℛ}}_{-}\left(z\right)\\ {\alpha }_{-}\left(z\right)\end{array}\right),$  with ${\mathcal{ℛ}}_{-}\left(z\right)={z}^{-m-1}\mathcal{ℛ}\left(z\right){d}^{-1}\left(z\right).$  The matrix polynomial ${U}_{-}\left(z\right)$  is shown in [8to be unimodular, i.e. its determinant is equal to a constant.
We pick the $2\left(p+q\right)×2p$  block $\mathcal{ℒ}\left(z\right)$  out ${U}_{-}^{-1}\left(z\right)$  :
${U}_{-}^{-1}\left(z\right)=\left(\begin{array}{cc}*& \mathcal{ℒ}\left(z\right)\end{array}\right).$  The matrix polynomial $\mathcal{ℒ}\left(z\right)=\left(\begin{array}{c}{L}_{1}\left(z\right)\\ ...\\ {L}_{2\left(p+q\right)}\left(z\right)\end{array}\right)$  turns out to be the matrix of the conforming left essential polynomials.
The case when $\alpha =0$  or $p\ge q$  may be considered in a similar manner with help of the left essential polynomials.
Now we may present the formula (5.13) from [8for the generalized inverse of ${T}_{A}$  :
 $\begin{array}{c}{T}_{A}^{†}=\left(\begin{array}{ccc}{\mathcal{ℛ}}_{0}& ...& 0\\ ...& ...& ...\\ {\mathcal{ℛ}}_{m}& ...& {\mathcal{ℛ}}_{0}\end{array}\right)\Pi \left(\begin{array}{ccc}{\mathcal{ℒ}}_{0}& ...& {\mathcal{ℒ}}_{-n}\\ ...& ...& ...\\ 0& ...& {\mathcal{ℒ}}_{0}\end{array}\right).\end{array}$ (2.3)
Here ${\mathcal{ℛ}}_{j}\in {\mathbb{C}}^{2q×2\left(p+q\right)},$  ${\mathcal{ℒ}}_{j}\in {\mathbb{C}}^{2\left(p+q\right)×2p}$  are the coefficients of the matrix polynomials $\mathcal{ℛ}\left(z\right)$  , $\mathcal{ℒ}\left(z\right)$  , respectively, and ${R}_{j}\left(z\right),{L}_{j}\left(z\right)$  are the conforming right and left essential polynomials of the sequence ${A}_{-m},\dots ,{A}_{0},$  $\dots ,{A}_{n}$  . The generalized inversion for matrix $A$  is meant to be the matrix ${A}^{†}$  such that $A{A}^{†}A=A.$  The matrix $\Pi$  is constructed as follows. Let ${\lambda }_{1},\dots ,{\lambda }_{r}$  be the distinct essential indices of the sequence ${A}_{-m},\dots ,{A}_{0},\dots ,{A}_{n}$  and let ${\nu }_{1},\dots ,{\nu }_{r}$  be their multiplicities ( ${\nu }_{1}+\dots +{\nu }_{r}=2\left(p+q\right)$  ).
Then $\Pi =\left(\begin{array}{cccc}{\Pi }_{0}& {\Pi }_{-1}& ...& {\Pi }_{-n}\\ {\Pi }_{1}& {\Pi }_{0}& ...& {\Pi }_{-n+1}\\ ...& ...& ...& ...\\ {\Pi }_{m}& {\Pi }_{m-1}& ...& {\Pi }_{m-n}\end{array}\right).$  Here ${\Pi }_{k}=0$  for $-n\le k\le m,k\ne -{\lambda }_{1},\dots ,-{\lambda }_{r}$  , ${\Pi }_{-{\lambda }_{j}}=\parallel {\varepsilon }_{i}^{j}{\delta }_{ik}{\parallel }_{i,k=1}^{2\left(p+q\right)}$  , ${\varepsilon }_{i}^{j}=\left\{\begin{array}{cc}1,& i={\nu }_{1}+\cdots +{\nu }_{j-1}+1,\dots ,{\nu }_{1}+\cdots +{\nu }_{j},\\ 0,& otherwise.\end{array}$  The following partition of the right essential polynomials ${R}_{j}\left(z\right)$  will be useful for the generalized inversion of the $T+H$  matrix:
${R}_{j}\left(z\right)=\left(\begin{array}{c}{R}_{j}^{1}\left(z\right)\\ \\ {R}_{j}^{2}\left(z\right)\end{array}\right).$  Here ${R}_{j}^{1,2}\in {\mathbb{C}}^{q×1}\left[z\right].$  In similar way we partition the left essential polynomials:
${L}_{j}\left(z\right)=\left(\begin{array}{cc}{L}_{j}^{1}\left(z\right)& {L}_{j}^{2}\left(z\right)\end{array}\right),$  with ${L}_{j}^{1,2}\in {\mathbb{C}}^{1×p}\left[z\right].$  Then the matrix of these essential polynomials may be represented as:
 $\begin{array}{c}\mathcal{ℛ}\left(z\right)=\left(\begin{array}{c}{\mathcal{ℛ}}^{1}\left(z\right)\\ {\mathcal{ℛ}}^{2}\left(z\right)\end{array}\right),\mathcal{ℒ}\left(z\right)=\left(\begin{array}{cc}{\mathcal{ℒ}}^{1}\left(z\right)& {\mathcal{ℒ}}^{2}\left(z\right)\end{array}\right),\end{array}$ (2.4)
with ${\mathcal{ℛ}}^{1,2}\left(z\right)\in {\mathbb{C}}^{q×2\left(p+q\right)},$  ${\mathcal{ℒ}}^{1,2}\left(z\right)\in {\mathbb{C}}^{2\left(p+q\right)×p}.$

3. Generalized inversion

In the section we will present our main result.
Let us denote ${T}_{{\mathcal{ℛ}}_{j}}=\left(\begin{array}{ccc}{\mathcal{ℛ}}_{0}^{j}& ...& 0\\ ...& ...& ...\\ {\mathcal{ℛ}}_{m}^{j}& ...& {\mathcal{ℛ}}_{0}^{j}\end{array}\right),{T}_{{\mathcal{ℒ}}_{j}}=\left(\begin{array}{ccc}{\mathcal{ℒ}}_{0}^{j}& ...& {\mathcal{ℒ}}_{-n}^{j}\\ ...& ...& ...\\ 0& ...& {\mathcal{ℒ}}_{0}^{j}\end{array}\right),j=1,2,$  where ${\mathcal{ℛ}}_{k}^{j}\left({\mathcal{ℒ}}_{k}^{j}\right)$  are the coefficients of the polynomials ${\mathcal{ℛ}}^{j}\left({\mathcal{ℒ}}^{j}\right)$  . We also put ${H}_{{\mathcal{ℛ}}_{2}}=J{T}_{{\mathcal{ℛ}}_{2}},$  ${H}_{{\mathcal{ℒ}}_{1}}={T}_{{\mathcal{ℒ}}_{1}}J$  .
Theorem 3.1. Generalized inverses of the $T+H$  and $T-H$  matrices are found by the formulas:
 $\begin{array}{c}{\left(T±H\right)}^{†}=\frac{1}{2}\left({T}_{{\mathcal{ℛ}}_{1}}±{H}_{{\mathcal{ℛ}}_{2}}\right)\Pi \left({T}_{{\mathcal{ℒ}}_{2}}±{H}_{{\mathcal{ℒ}}_{1}}\right).\end{array}$ (3.1)
If $T±H$  is invertible (one-sided invertible), then ${\left(T±H\right)}^{†}$  is its inverse (one-sided inverse) matrix.
Proof. Let us construct a generalized inversion to ${T}_{A}\equiv {T}_{0}$  according to formula ( 2.3 ).
We are going to pass from block Toeplitz matrix ${T}_{A}$  to the mosaic matrix ${M}_{A}=\left(\begin{array}{ccccccc}{b}_{n}& ...& {b}_{n+m}& & {a}_{n-m}& ...& {a}_{n}\\ {b}_{n-1}& ...& {b}_{n+m-1}& & {a}_{n-m-1}& ...& {a}_{n-1}\\ ...& ...& ...& & ...& ...& ...\\ {b}_{0}& ...& {b}_{m}& & {a}_{-m}& ...& {a}_{0}\\ {a}_{0}& ...& {a}_{-m}& & {b}_{m}& ...& {b}_{0}\\ {a}_{1}& ...& {a}_{-m+1}& & {b}_{m+1}& ...& {b}_{1}\\ ...& ...& ...& & ...& ...& ...\\ {a}_{n}& ...& {a}_{n-m}& & {b}_{n+m}& ...& {b}_{n}\end{array}\right).$  At first, according to the block structure of ${A}_{j}$  ( 2.1 ), we partition each block column ${X}_{j}$  of the matrix ${T}_{A}$  into two block columns ${X}_{j}^{1},{X}_{j}^{2}$  with sizes $2p\left(n+1\right)×q$  :
${X}_{j}=\left(\begin{array}{cc}{X}_{j}^{1}& {X}_{j}^{2}\end{array}\right).$  Then permute new block columns in ${T}_{A}$  and construct the matrix $\left(\begin{array}{cccccc}{X}_{1}^{1}& ...& {X}_{m}^{1}& {X}_{1}^{2}& ...& {X}_{m}^{2}\end{array}\right)=$  $\left(\begin{array}{ccccccccc}{b}_{n}& {b}_{n+1}& ...& {b}_{n+m}& & {a}_{n-m}& {a}_{n-m+1}& ...& {a}_{n}\\ {a}_{0}& {a}_{-1}& ...& {a}_{-m}& & {b}_{m}& {b}_{m-1}& ...& {b}_{0}\\ {b}_{n-1}& {b}_{n}& ...& {b}_{n+m-1}& & {a}_{n-m-1}& {a}_{n-m}& ...& {a}_{n-1}\\ {a}_{1}& {a}_{0}& ...& {a}_{-m+1}& & {b}_{m+1}& {b}_{m}& ...& {b}_{1}\\ ...& ...& ...& ...& & ...& ...& ...& ...\\ {b}_{0}& {b}_{1}& ...& {b}_{m}& & {a}_{-m}& {a}_{-m+1}& ...& {a}_{0}\\ {a}_{n}& {a}_{n-1}& ...& {a}_{n-m}& & {b}_{n+m}& {b}_{n+m-1}& ...& {b}_{n}\end{array}\right).$  This matrix is evident to be obtained by multiplying ${T}_{A}$  on a permutation matrix ${P}_{2}$  . Then we will do the analogous permutation with block rows in ${T}_{A}{P}_{2}$  .
As a result, we will get the matrix ${P}_{1}{T}_{A}{P}_{2}$  , where ${P}_{1}$  is a permutation matrix.
The matrix ${P}_{1}{T}_{A}{P}_{2}$  coincides with ${M}_{A}:$  ${M}_{A}={P}_{1}{T}_{A}{P}_{2}.$  Thus we have passed from the block Toeplitz matrix ${T}_{A}$  to the mosaic matrix ${M}_{A}$  .
Taking into account that for a permutation matrix $P$  the equality ${P}^{-1}={P}^{t}$  holds, we get the generalized inversion for ${M}_{A}:$  ${M}_{A}^{†}={P}_{2}^{t}{T}_{A}^{†}{P}_{1}^{t}.$  Let us specify the structure of factors in ${M}_{A}^{†}={P}_{2}^{t}{T}_{A}^{†}{P}_{1}^{t}$  . The operations which ${P}_{2}$  has done with the block columns of ${T}_{A}$  , the matrix ${P}_{2}^{t}$  now will carry out with the block rows of the matrix $\left(\begin{array}{ccc}{\mathcal{ℛ}}_{0}& ...& 0\\ ...& ...& ...\\ {\mathcal{ℛ}}_{m}& ...& {\mathcal{ℛ}}_{0}\end{array}\right).$  Thus ${P}_{2}^{t}\left(\begin{array}{ccc}{\mathcal{ℛ}}_{0}& ...& 0\\ ...& ...& ...\\ {\mathcal{ℛ}}_{m}& ...& {\mathcal{ℛ}}_{0}\end{array}\right)=\left(\begin{array}{ccc}{\mathcal{ℛ}}_{0}^{1}& ...& 0\\ ...& ...& ...\\ {\mathcal{ℛ}}_{m}^{1}& ...& {\mathcal{ℛ}}_{0}^{1}\\ {\mathcal{ℛ}}_{0}^{2}& ...& 0\\ ...& ...& ...\\ {\mathcal{ℛ}}_{m}^{2}& ...& {\mathcal{ℛ}}_{0}^{2}\end{array}\right)\equiv \left(\begin{array}{c}{T}_{{\mathcal{ℛ}}_{1}}\\ {T}_{{\mathcal{ℛ}}_{2}}\end{array}\right),$  where ${\mathcal{ℛ}}_{j}^{1,2}$  are the coefficients of the matrix polynomials ${\mathcal{ℛ}}^{1,2}\left(z\right)$  , presented in ( 2.4 ).
Similarly, we have $\left(\begin{array}{ccc}{\mathcal{ℒ}}_{0}& ...& {\mathcal{ℒ}}_{-n}\\ ...& ...& ...\\ 0& ...& {\mathcal{ℒ}}_{0}\end{array}\right){P}_{1}^{t}=$  $=\left(\begin{array}{cccccc}{\mathcal{ℒ}}_{0}^{1}& ...& {\mathcal{ℒ}}_{-n}^{1}& {\mathcal{ℒ}}_{0}^{2}& ...& {\mathcal{ℒ}}_{-n}^{2}\\ ...& ...& ...& ...& ...& ...\\ 0& ...& {\mathcal{ℒ}}_{0}^{1}& 0& ...& {\mathcal{ℒ}}_{0}^{2}\end{array}\right)\equiv \left(\begin{array}{cc}{T}_{{\mathcal{ℒ}}_{1}}& {T}_{{\mathcal{ℒ}}_{2}}\end{array}\right).$  Then ${M}_{A}^{†}=\left(\begin{array}{c}{T}_{{\mathcal{ℛ}}_{1}}\\ {T}_{{\mathcal{ℛ}}_{2}}\end{array}\right)\Pi \left(\begin{array}{cc}{T}_{{\mathcal{ℒ}}_{1}}& {T}_{{\mathcal{ℒ}}_{2}}\end{array}\right).$  Let us apply now the well-known method [2of reducing the mosaic matrix ${M}_{A}$  to the block-diagonal matrix formed from the Toeplitz-plus-Hankel and Toeplitz-minus-Hankel matrices:
${M}_{A}=\frac{1}{2}\left(\begin{array}{cc}J& J\\ I& -I\end{array}\right)\left(\begin{array}{cc}T+H& 0\\ 0& T-H\end{array}\right)\left(\begin{array}{cc}I& J\\ -I& J\end{array}\right).$  We obtain that the matrix $G=\frac{1}{2}\left(\begin{array}{cc}I& J\\ -I& J\end{array}\right){M}_{A}^{†}\left(\begin{array}{cc}J& J\\ I& -I\end{array}\right)=$  $=\frac{1}{2}\left(\begin{array}{c}{T}_{{\mathcal{ℛ}}_{1}}+J{T}_{{\mathcal{ℛ}}_{2}}\\ -{T}_{{\mathcal{ℛ}}_{1}}+J{T}_{{\mathcal{ℛ}}_{2}}\end{array}\right)\Pi \left(\begin{array}{cc}{T}_{{\mathcal{ℒ}}_{1}}J+{T}_{{\mathcal{ℒ}}_{2}}& {T}_{{\mathcal{ℒ}}_{1}}J-{T}_{{\mathcal{ℒ}}_{2}}\end{array}\right)$  is the generalized inversion for the matrix $\left(\begin{array}{cc}T+H& 0\\ 0& T-H\end{array}\right)$  .
Let us present $G$  in the block form $G=\left(\begin{array}{cc}{G}_{11}& {G}_{12}\\ {G}_{21}& {G}_{22}\end{array}\right),$  with ${G}_{ij}\in {\mathbb{C}}^{\left(m+1\right)q×\left(n+1\right)p}.$  It is easy to get that ${G}_{11}=\frac{1}{2}\left({T}_{{\mathcal{ℛ}}_{1}}+{H}_{{\mathcal{ℛ}}_{2}}\right)\Pi \left({T}_{{\mathcal{ℒ}}_{2}}+{H}_{{\mathcal{ℒ}}_{1}}\right),$  ${G}_{22}=\frac{1}{2}\left({T}_{{\mathcal{ℛ}}_{1}}-{H}_{{\mathcal{ℛ}}_{2}}\right)\Pi \left({T}_{{\mathcal{ℒ}}_{2}}-{H}_{{\mathcal{ℒ}}_{1}}\right)$  are generalized inverses to $T+H$  $\left(T-H\right)$  .
The theorem statement concerning the invertibility (one-sided invertibility) is evident. The theorem has been proved.
Given $T±H$  matrices are block matrices with the sizes of their blocks $p×q.$  The factors in the inverse formulas ( 3.1 ) have blocks with sizes $q×2\left(p+q\right)$  , $2\left(p+q\right)×p$  . The compact form of the generalized inversion is in many respects because of such factors sizes. Sometimes it is convenient to have a formula for a generilized inversion where factors have blocks with sizes $q×q,q×p,p×p$  .
In order to obtain it we partition $\mathcal{ℛ}\left(z\right)=\left({R}_{1}\left(z\right)\dots {R}_{2\left(p+q\right)}\left(z\right)\right)$  into blocks:
$\mathcal{ℛ}\left(z\right)=\left(\begin{array}{cccc}{\mathcal{ℛ}}_{11}& {\mathcal{ℛ}}_{12}& {\mathcal{ℛ}}_{13}& {\mathcal{ℛ}}_{14}\\ {\mathcal{ℛ}}_{21}& {\mathcal{ℛ}}_{22}& {\mathcal{ℛ}}_{23}& {\mathcal{ℛ}}_{24}\end{array}\right).$  Here ${\mathcal{ℛ}}_{ij}$  have the sizes $q×q$  for $i,j=1,2,$  and $q×p$  for $i=1,2,$  $j=3,4.$  Then we will do the analogous partition with the matrix of the left essential polynomials:
$\mathcal{ℒ}\left(z\right)=\left(\begin{array}{cc}{\mathcal{ℒ}}_{11}& {\mathcal{ℒ}}_{12}\\ {\mathcal{ℒ}}_{21}& {\mathcal{ℒ}}_{22}\\ {\mathcal{ℒ}}_{31}& {\mathcal{ℒ}}_{32}\\ {\mathcal{ℒ}}_{41}& {\mathcal{ℒ}}_{42}\end{array}\right),$  here ${\mathcal{ℒ}}_{ij}$  have the sizes $q×p$  for $i,j=1,2,$  and $p×p$  for $i=3,4,j=1,2.$  Let us also partition $D=diag\left[{z}^{{\mu }_{1}}\dots {z}^{{\mu }_{2\left(p+q\right)}}\right]=\left({d}_{1}{d}_{2}{d}_{3}{d}_{4}\right),$  where ${d}_{1,2}$  are diagonal matrices with the sizes $q×q$  and ${d}_{3,4}$  are ones with the sizes $p×p.$  We denote for $i,j=1,\dots ,4$  ${T}_{{\mathcal{ℛ}}_{ij}}=\left(\begin{array}{ccc}{\mathcal{ℛ}}_{0}^{ij}& ...& 0\\ ...& ...& ...\\ {\mathcal{ℛ}}_{m}^{ij}& ...& {\mathcal{ℛ}}_{0}^{j}\end{array}\right),{T}_{{\mathcal{ℒ}}_{ij}}=\left(\begin{array}{ccc}{\mathcal{ℒ}}_{0}^{ij}& ...& {\mathcal{ℒ}}_{-n}^{ij}\\ ...& ...& ...\\ 0& ...& {\mathcal{ℒ}}_{0}^{ij}\end{array}\right).$  Then it is easy to see that ${\left(T±H\right)}^{†}=\frac{1}{2}\left[{\sum }_{j=1}^{4}{T}_{{\mathcal{ℛ}}_{1j}}{\pi }_{j}{T}_{{\mathcal{ℒ}}_{j2}}+{\sum }_{j=1}^{4}{H}_{{\mathcal{ℛ}}_{2j}}{\pi }_{j}{H}_{{\mathcal{ℒ}}_{j1}}±$  $±\left({\sum }_{j=1}^{4}{T}_{{\mathcal{ℛ}}_{1j}}{\pi }_{j}{H}_{{\mathcal{ℒ}}_{j1}}+{\sum }_{j=1}^{4}{H}_{{\mathcal{ℛ}}_{2j}}{\pi }_{j}{T}_{{\mathcal{ℒ}}_{j2}}\right)\right],$  where we denote ${T}_{\mathcal{ℒ},\mathcal{ℛ}}J={H}_{\mathcal{ℒ},\mathcal{ℛ}}$  and ${\pi }_{j}$  are the matrices constructed by ${d}_{j}$  with the same manner as $\Pi$  by $d$  .

4. An example

Let us demonstrate the theorem with an example. We will find generalized inversions of the following $T+H$  and $T-H$  matrices:
$T±H=\left(\begin{array}{cccc}1& 0& -1& 1\\ 1& 1& 0& -1\\ 1& 1& 1& 0\\ -1& 1& 1& 1\end{array}\right)±\left(\begin{array}{cccc}1& 0& -1& 1\\ 0& -1& 1& 0\\ -1& 1& 0& 0\\ 1& 0& 0& 1\end{array}\right).$  Our calculations show that the indices of the sequence ${A}_{-3},\dots ,{A}_{3}$  are equal to ${\mu }_{1}=-1,{\mu }_{2}=0,{\mu }_{3}=0,{\mu }_{4}=1$  . The matrix $\mathcal{ℛ}\left(z\right)$  of the right essential polynomials and the matrix $\mathcal{ℒ}\left(z\right)$  of the conforming left essential polynomials are:
$\mathcal{ℛ}\left(z\right)=\left(\begin{array}{c}{\mathcal{ℛ}}^{1}\left(z\right)\\ {\mathcal{ℛ}}^{2}\left(z\right)\end{array}\right),\mathcal{ℒ}\left(z\right)=\left(\begin{array}{cc}{\mathcal{ℒ}}^{1}\left(z\right)& {\mathcal{ℒ}}^{2}\left(z\right)\end{array}\right),$  where ${\mathcal{ℛ}}^{1}\left(z\right)=-\left(\begin{array}{cccc}1& 2& 2& 0\end{array}\right)+\left(\begin{array}{cccc}-4& 5& 3& -1\end{array}\right)z+\left(\begin{array}{cccc}2& 1& 0& 0\end{array}\right){z}^{2}-$  $-\left(\begin{array}{cccc}11& 4& 2& 0\end{array}\right){z}^{3}+\left(\begin{array}{cccc}0& 4& 1& 0\end{array}\right){z}^{4}+\left(\begin{array}{cccc}0& 0& 0& 1\end{array}\right){z}^{5},$  ${\mathcal{ℛ}}^{2}\left(z\right)=\left(\begin{array}{cccc}11& -4& -2& 2\end{array}\right)-\left(\begin{array}{cccc}2& 11& 5& -2\end{array}\right)z+\left(\begin{array}{cccc}4& 0& 0& 0\end{array}\right){z}^{2}+$  $+\left(\begin{array}{cccc}1& 0& 0& 0\end{array}\right){z}^{3}+\left(\begin{array}{cccc}0& 0& 1& 0\end{array}\right){z}^{4},$  ${\mathcal{ℒ}}^{1}\left(z\right)=\frac{1}{180}\left[\left(\begin{array}{c}-4\\ -12\\ 4\\ 0\end{array}\right)+\left(\begin{array}{c}4\\ 0\\ 12\\ 0\end{array}\right){z}^{-1}+\left(\begin{array}{c}-1\\ 6\\ -23\\ 0\end{array}\right){z}^{-2}-$  $-\left(\begin{array}{c}21\\ -6\\ 35\\ 180\end{array}\right){z}^{-3}+\left(\begin{array}{c}-18\\ -84\\ 76\\ 0\end{array}\right){z}^{-4}+\left(\begin{array}{c}16\\ 0\\ 0\\ 0\end{array}\right){z}^{-5}\right],$  ${\mathcal{ℒ}}^{2}\left(z\right)=\frac{1}{180}\left[\left(\begin{array}{c}25\\ 30\\ -25\\ 180\end{array}\right)+\left(\begin{array}{c}26\\ 108\\ -126\\ 0\end{array}\right){z}^{-1}+\left(\begin{array}{c}-11\\ 30\\ -43\\ 0\end{array}\right){z}^{-2}+$  $+\left(\begin{array}{c}-6\\ -24\\ 32\\ 0\end{array}\right){z}^{-3}-\left(\begin{array}{c}10\\ 24\\ 26\\ 0\end{array}\right){z}^{-4}-\left(\begin{array}{c}4\\ 0\\ 0\\ 0\end{array}\right){z}^{-5}\right].$  We construct the matrix $\Pi =\left(\begin{array}{cccc}{\Pi }_{0}& {\Pi }_{-1}& {\Pi }_{-2}& {\Pi }_{-3}\\ {\Pi }_{1}& {\Pi }_{0}& {\Pi }_{-1}& {\Pi }_{-2}\\ {\Pi }_{2}& {\Pi }_{1}& {\Pi }_{0}& {\Pi }_{-1}\\ {\Pi }_{3}& {\Pi }_{2}& {\Pi }_{1}& {\Pi }_{0}\end{array}\right),$  where ${\Pi }_{0}=\left(\begin{array}{cccc}0& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 0\end{array}\right),{\Pi }_{-1}=\left(\begin{array}{cccc}0& 0& 0& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 1\end{array}\right),$  ${\Pi }_{1}=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 0\end{array}\right),$  and the matrices ${\Pi }_{±2},{\Pi }_{±3}$  are zero matrices.
Then we construct the matrices ${T}_{{\mathcal{ℛ}}_{1}}$  , ${T}_{{\mathcal{ℛ}}_{2}}$  with help of the coefficients of ${\mathcal{ℛ}}^{1},{\mathcal{ℛ}}^{2}$  and matrices ${T}_{{\mathcal{ℒ}}_{1}},$  ${T}_{{\mathcal{ℒ}}_{2}}$  with help of the coefficients of ${\mathcal{ℒ}}^{1},{\mathcal{ℒ}}^{2}$  .
We use the formulas ( 3.1 ) for generalized inverses of the $T±H$  matrices and have ${\left(T+H\right)}^{†}=\frac{1}{20}\left(\begin{array}{cccc}5& 10& 0& 0\\ 2& -4& 12& -4\\ -4& 8& -4& 8\\ 1& -2& -4& 8\end{array}\right),$  ${\left(T-H\right)}^{†}=\frac{1}{180}\left(\begin{array}{cccc}-113& 2& 50& -32\\ 88& 8& 20& 52\\ -134& -4& 80& 64\\ 17& -158& 10& 16\end{array}\right).$  One may conclude that ${\left(T+H\right)}^{†}$  is the inverse matrix for the $T+H$  matrix and ${\left(T-H\right)}^{†}$  is the generalized inverse for $T-H.$  References

1. A. H. Sayed, H. Lev-Ari, and T. Kailath, Fast Triangular Factorization of the Sum of Quasi-Toeplitz and Quasi-Hankel Matrices, Linear Algebra Appl. 191 : 77 106, 1993.
2. G. A. Merchant and T. W. Parks, Efficient solution of a Toeplitz-plus-Hankel coefficient system of equations, IEEE Transactions on Acoustics, Speech and Signal Processing, 30(1): 40 44, February, 1982.
3. A. B. Nersesian, A. A. Papoyan, Construction of matrix inversed to the sum of Toeplitz and Hankel matrices (Russian),Izv. AN Arm. SSR. Matematika, 8, N2 (1983), 441-463.
4. G. Heinig, K. Rost, Algebraic Methods for Toeplitz-like Matrices and Operators, Academie-Verlag, Berlin, 1984.
5. G. Heinig, K. Rost, On the Inverses of Toeplitz-plus-Hankel matrices, Linear Algebra Appl. 106 : 39 52, 1988.
6. I. Gohberg, T. Shalom, On inversion of square matrices partitioned into non-square blocks, Integral Equations and Operator Theory, 12 (1989), 539–566.
7. V. M. Adukov, O. L. Ibryaeva, On the kernel structure of the Toeplitz-plus-Hankel matrices (Russian), Vestnik Jujno-Uralskogo gosudarstvennogo universiteta, 7, 3-12, 2001.
8. V. M. Adukov, Generalized inversion of block Toeplitz matrices, Linear Algebra Appl. 274 : 85 124, 1998.