# The Inverses of Block Toeplitz Matrices

Authors: Xiao-Guang Lv; Ting-Zhu Huang
Journal: Journal of Mathematics
 (2013)

---

## Abstract

We study the inverses of block Toeplitz matrices based on the analysis of the block cyclic displacement. New formulas for the inverses of block Toeplitz matrices are proposed. We show that the inverses of block Toeplitz matrices can be decomposed as a sum of products of block circulant matrices. In the scalar case, the inverse formulas are proved to be numerically forward stable, if the Toeplitz matrix is nonsingular and well conditioned.


---

## Body

## 1. Introduction

Let(1)T=[T0T-1⋯T1-nT1T0⋱T2-n⋮⋱⋱⋮Tn-1Tn-2⋯T0]
be an n×n block Toeplitz matrix with blocks of size m×m. We use the shorthand T=(Ti-j)i,j=1n for a block Toeplitz matrix. The block Toeplitz systems Tx=b arise in a variety of applications in mathematics, scientific computing, and engineering, for instance, image restoration problems in image processing, numerical differential equations and integral equations, time series analysis, and control theory [1–3]. If we want to solve more than one block Toeplitz linear system with the same coefficient matrix, then we usually solve four or so special block linear systems in order to determine the block Toeplitz inverse formula that expresses T-1 as the sum of products of block upper and block lower Toeplitz matrices. For example, Van Barel and Bultheel [4] gave an inverse formula for a block Toeplitz matrix and then derived a weakly stable algorithm to solve a block Toeplitz system of linear equations. The special structure of block Toeplitz matrices has resulted in some closed formulas for their inverses.In the scalar case, Gohberg and Semencul [5] have shown that if the (1,1)st entry of the inverse of a Toeplitz matrix T is nonzero, then the first and the last columns of the inverse of the Toeplitz matrix are sufficient to reconstruct T-1. In [6], an inverse formula can be obtained by the solutions of two equations (the so-called fundamental equations), where each right-hand side of them is a shifted column of the Toeplitz matrix. Later, Ben-Artzi and Shalom [7], Labahn and Shalom [8], Huckle [9], Ng et al. [10], and Heinig [11] have studied the Toeplitz matrix inverse formulas when the (1,1)st entry of the inverse of a Toeplitz matrix is zero. In [12], Cabay and Meleshko presented an efficient algorithm (NPADE) for numerically computing Padé approximants in a weakly stable fashion. As an application of NPADE, it has been shown that it can be used to compute stably, in a weak sense, the inverse of a Hankel or Toeplitz matrix.Whenm>1, additional problems are encountered in obtaining the inverse formula of a block Toeplitz matrix. A well-known formula of Gohberg and Heinig can construct T-1, provided that the first and last columns together with the first and last rows of the inverse are known [13]. In [14], a set of new formulas for the inverse of a block Hankel or block Toeplitz matrix is given by Labahn et al. The formulas are expressed in terms of certain matrix Padé forms, which approximate a matrix power series associated with the block Hankel matrix. We refer the reader to [15, 16] for the computation of Padé-Hermite and simultaneous Padé systems in detail. In [7], Ben-Artzi and Shalom have proved that each inverse of a Toeplitz matrix can be constructed via three of its columns, and thus, a parametrization of the set of inverses of Toeplitz matrices is obtained. Then they generalized these results to block Toeplitz matrices; see [17]. In [18], Gemignani has shown that the representation of T-1 relies upon a strong structure-preserving property of the Schur complements of the nonsingular leading principal submatrices of a certain generalized Bezoutian of matrix polynomials.In this paper, we focus our attention to the inverses of block Toeplitz matrices with the help of the block cyclic displacement. In [19], Ammar and Gader have shown that the inverse of a Toeplitz matrix can be represented as sums of products of lower triangular Toeplitz matrices and circulant matrices. The derivation of their results is based on the idea of cyclic displacement structure. In [20], Gohberg and Olshevsky also obtained new formulas for representation of matrices and their inverses in the form of sums of products of factor circulant, which are based on the analysis of the factor cyclic displacement of matrices. The results in applications to Toeplitz matrices generalized the Gohberg-Semencul, Ben-Artzi-Shalom, and Heinig-Rost formulas. Motivated by a number of related results on Toepltiz inverse formulas, we study the representation of the inverses of block Toeplitz matrices. Since block Toeplitz matrices have similar displacement structure as Toeplitz matrices, all results about Toeplitz matrices extend quite naturally to block Toeplitz matrices.At first, for purposes of presentation, we adopt some notations that will be used throughout the paper. We denote them×m identity matrix by Im. Ei(i=0,1,…,n-1) means a matrix of dimension mn×m in which the (i+1)-th block is the identity matrix Im, and the remaining blocks are all zeros. J is called an n×n block reverse identity matrix, if J has the identity matrices on the block antidiagonal and zero elsewhere. Let A=(Aij) be a block matrix or a block vector with block size of m×m. A′=(Aji) is said to be the block transpose of A. By C(r,φ) we denote the block φ-circulant with the first column r=[r0,…,rn-1]′ with a block size of m×m; that is, the matrix of form is defined by
(2)[r0φrn-1⋯⋯φr1r1r0φrn-1⋱⋮⋮r1⋱⋱⋮⋮⋱⋱⋱φrn-1rn-1⋯⋯r1r0].In this work, new formulas for the inverses of block Toeplitz matrices are proposed. As is well known, any block Toeplitz matrixT has a property of block persymmetry, that is, JT′J=T, where J is the block reverse identity matrix. Unfortunately, the matrix inverse does not hold this property. This can explain why the Gohberg-Heĭnig formula [13] needs the first and last columns together with the first and last rows of the inverse for constructing the inverse. For a block Toeplitz matrix T, let Tc and Ts be its block circulant and block skew-circulant parts, respectively. The representation T=Tc·I+Ts·I shows that there will exist block circulant matrices Ai(i=1,2) and Bi(i=1,2) such that T-1=A1B1+A2B2. In this paper, by solving four linear equations with the same coefficient matrix T, we decompose the inverses of block Toeplitz matrices as a sum of products of block circulant matrices. From the point of view of the computation, the formulas involving block circulants instead of block upper or lower Toeplitz matrices are more attractive. For example, in the scalar case, matrix-vector product by a circulant matrix is roughly twice as fast as matrix-vector product by a triangular Toeplitz matrix of the same size. In fact, the efficient multiplication of a Toeplitz matrix and a vector is achieved by embedding the Toeplitz matrix in a circulant matrix of twice the size. The derivation of the formulas we present is based on the factor cyclic displacement of block matrices. Later on, we give some corollaries about the representations of the inverse matrices. The results generalize the Gohberg-Olshevsky, Heinig-Rost, and Ben-Artzi-Shalom formulas. In the scalar case, we consider the stability of the Toeplitz matrix inverse formulas. We show that if the Toeplitz matrix is nonsingular and well conditioned, the inverse formulas are numerically forward stable.We summarize briefly the content of our paper. Section2 reviews some fundamental concepts such as the factor cyclic displacement structure of a block matrix and every square block matrix can be written as a sum of products of block circulant matrices. In Section 3, we decompose the inverses of block Toeplitz matrices as a sum of products of block circulant matrices by solving four equations with the same coefficient matrix T. Some corollaries are also obtained in this section. We discuss the stability of the inverse formulas of scalar Toeplitz matrices in Section 4. Some remarks are given in Section 5.


## 2. The Factor Block Cyclic Displacement

The inverse formulas derived in the next section depend on some results of the factor block cyclic displacement of a block matrix. The focus of this section lies upon the definitions and the properties of the factor block cyclic displacement of a block matrix. We start with the definition of the factor block cyclic displacement.LetZφ be the block φ-cyclic lower shift matrix defined by
(3)[0⋯⋯0φII0⋱⋱00I⋱⋱⋮⋮⋱⋱⋱⋮0⋯0I0].
The block φ-cyclic displacement of an n×n block matrix A with blocks size of m×m is defined as
(4)∇φ(A)=A-ZφAZ1/φ′,φ≠0.
The number α=rank∇1(A) is referred to as block φ-cyclic displacement rank of the block matrix A. Since all block Toeplitz matrices have a special structure, it is not difficult to obtain that
(5)∇φ(T)=[OT-1-φTn-1⋯T1-n-φT1T1-1φT1-nO⋯O⋮⋮⋮Tn-1-1φT-1O⋯O]=E0·[-TnT-1-φTn-1⋮T1-n-φT1]′+[TnT1-1φT1-n⋮Tn-1-1φT-1]·E0′,
where Tn may be an arbitrary m×m matrix. Therefore, the φ-cyclic displacement rank of a block Toeplitz matrix is at most 2m.By straightforward computations, it is easy to see that the equality∇φ(A)=0 holds if and only if A is a block φ-circulant matrix. For any invertible block matrix A there exists a simple interrelation between the block φ-cyclic displacement of the inverse matrix A-1 and the block φ-cyclic displacement of A. This connection is given by
(6)∇φ(A-1)=A-1∇φ(A)ZφA-1Z1/φ′.
From the previous equation, we know that the block φ-cyclic displacement rank of the inverse matrix A-1 is the same as that of A. Moreover, the previous equation also allows us to make use of the block φ-cyclic displacement technique for the calculation of the inverse matrix. We will study the inverses of block Toeplitz matrices with the help of the block cyclic displacement. We need the following result.Theorem 1.
If the blockφ-cyclic displacement of A is given as the sum
(7)A-ZφAZ1/φ′=∑m=1α‍gmhm′,
where gi and hi(i=1,…,m) are n×1 block vectors with blocks of size m×m, then
(8)A=C(lr,φ)+φφ-ψ(∑m=1α‍C(gm,ψ)·C(hm,1φ)′)
or
(9)A=C(lc,φ)+ψψ-φ(∑m=1α‍C(gm,φ)·C(hm,1ψ)′),
where C(lr,φ) is a block φ-circulant matrix with the same last block row as that of A and C(lc,φ) is the block φ-circulant matrix with the same last block column as that of A.Proof.
From computing the blockφ-cyclic displacement of matrix A defined by (4), it then follows that
(10)∇φ(A)=∇φ(C(lr,φ))+φφ-ψ∇φ(∑m=1α‍C(gm,ψ)·C(hm,1φ)′)=φφ-ψ∑m=1α‍∇φ(C(gm,ψ)·C(hm,1φ)′).
Note that the φ-cyclic displacement of any block matrix A is a linear operator and two block φ-circulant matrices can commute; we obtain
(11)∇φ(A)=φφ-ψ∑m=1α‍∇φ(C(gm,ψ))·C(hm,1φ)′.
By computing the block φ-cyclic displacement of block ψ-cyclic matrix C(gm,ψ) for all m, we have
(12)∇φ(A)=φφ-ψ∑m=1α‍∇φ(C(gm,ψ))·C(hm,1φ)′=∑m=1α‍gm·E0′·C(hm,1φ)′-∑m=1α‍E0·g~m′·C(hm,1φ)′,
where g~m′ for m=1,…,α are the first row of the block φ-circulant matrices C(gm,φ), respectively. Since E0′·C(hm,1/φ)′=hm′, it is easy to observe that the sum of the first α terms in the previous equality is equal to ∑m=1α‍gmhm′.
In the following, we need to show that the sum of the lastα terms in the previous equality is equal to the zero matrix. Using the fact that Zφn=φI and Zφ-1=Z1/φ′, we check
(13)∑k=0n-1‍Zφk(T-1-ZφT-1Zφ-1)Zφ-k=0.
Thus we obtain
(14)∑k=0n-1‍Zφk(T-1-ZφT-1Zφ-1)Zφ-k=∑k=0n-1‍∑m=1α‍Zφkgmhm′Zφ-k=∑m=1α‍C(gm,φ)·C(hm,1φ)′=0.
By comparing ∑m=1α‍E0·g~m′·C(hm,1/φ)′ with ∑m=1α‍C(gm,φ)·C(hm,1/φ)′, we obtain ∑m=1α‍E0·g~m′·C(hm,1/φ)′=0.
Finally, we discuss whyC(lr,φ) is the block φ-circulant with the same last block rows as the matrix A. We know that the last block row of the matrix C(gm,ψ) is independent of the number ψ. In view of ∑m=1α‍C(gm,φ)·C(hm,1/φ)=0, the last block rows of the matrix A and C(lr,φ) are the same.
Equation (8) is now completely proved. A similar argument shows that (9) can be obtained from (7).


## 3. Inverses of Block Toeplitz Matrices

In this section, we focus our attention to new formulas on the inverses of block Toeplitz matrices. It is easy to find that any block Toeplitz matrix has a property of block persymmetry, that is,JT′J=T, where J is the block reverse identity matrix. Unfortunately, the matrix inverse does not have this property. This can explain why the Gohberg-Heĭnig formula [13] needs the first and last block columns together with the first and last block rows of the inverse to construct it. Unlike the Gohberg-Semencul formula [5], it only needs the first and the last columns of the inverse if the (1,1)st entry of the inverse is nonzero.Let(15)T(x0,x1,…,xn-1)′=E0,(16)(x~0,x~1,…,x~n-1)T=En-1′,(17)T(u0,u1,…,un-1)′=(Tn,T1-1φT1-n,…,Tn-1-1φT-1)′,(18)(u~0,u~1,…,u~n-1)T=(Tn-1-1φT-1,…,T1-1φT1-n,Tn).For convenience, we will writex,x~,u and u~ as
(19)x=(x0,x1,…,xn-1)′,x~=(x~0,x~1,…,x~n-1)′,u=(u0,u1,…,un-1)′,u~=(u~0,u~1,…,u~n-1)′.
From (5), (6), (15), and (17), by simple computations we obtain the following equality:
(20)∇φ(T-1)=-T-1∇φ(T)ZφT-1Z1/φ′=-[x0x1⋮xn-1]·(-Tn,T-1-φTn-1,…,T1-n-φT1)·ZφT-1Z1/φ′-[u0u1⋮un-1]·(Im,0,…,0)·ZφT-1Z1/φ′.
Substituting (16) and (18) into the previous equality and computing, we obtain
(21)∇φ(T-1)=φ[x0x1⋮xn-1]·(Tn-1-1φT-1,…,T1-1φT1-n,Tn)T-1Z1/φ′-φ[u0u1⋮un-1]·(0,…,0,Im)·T-1Z1/φ′=[x0x1⋮xn-1](u~n-1,φu~0,…,φu~n-2)-[u0u1⋮un-1](x~n-1,φx~0,…,φx~n-2).Theorem 2.
LetT be a block Toeplitz matrix given by (1). If (15)–(18) are solvable for some φ≠0 and an arbitrary matrix Tn of order m, then(a)
Tis invertible;(b)
T-1 can be denoted as
(22)T-1=φφ-ψ((u-φ-ψφE0,ψ)C(x,ψ)·C(Ju~,φ)-C(u-φ-ψφE0,ψ)·C(Jx~,φ)),where ψ(≠φ) is an arbitrary number.Proof.
(a) Assume that there exists nonzero vectorp of dimension mn such that Tp=0. Then by computing (16) and (18), we have (-Tn,T-1-φTn-1,…,T1-n-φT1)Zφp=0 and (Im,0,…,0)Zφp=0. These imply ∇φ(T)Zφp=0. Since ∇φ(T)=T-ZφTZ1/φ′, we obtain TZφp=0. A similar argument shows that TZφkp=0(k=2,3,…,n-1). Premultiplying the equalities TZφkp=0(k=0,1,…,n-1) by (x~0,x~1,…,x~n-1), we can conclude that all elements of the vector are equal to zero. Therefore, the invertibility of T is now proved.
(b) According to Theorem1, we get
(23)T-1=C(lr,φ)+φφ-ψ(C(x,ψ)·C(φZ1/φu~,1φ)′+C(u,ψ)·C(φZ1/φx~,1φ)′).C(lr,φ) is the block φ-circulant matrix with the same last block row as that of T-1. It is not difficult to see that C(lr,φ)=C(φZ1/φx~,1/φ)′=C(Jx~,φ). After computations and arrangement, we obtain the formula (22) on the inverses of block Toeplitz matrices.Remark 3.
In fact, the inverse formula (22) is a generalization of the formula of Gohberg and Olshevsky [20], where they consider scalar Toeplitz matrices. Since the matrix inverse does not hold the property of persymmetry, in the block case, for constructing T-1 we need to solve four linear equations with the same coefficient matrix T. Labahn et al. also gave this conclusion in terms of certain matrix Padé forms [14].Remark 4.
For the inverse formula (22), we take an interest in two particular cases. When φ=1 and ψ=0, the inverse formula (22) can be written as
(24)T-1={[x00⋯0x1x0⋱⋮⋮⋱⋱0xn-1⋮x1x0]×[u~n-1u~0⋯u~n-2u~n-2u~n-1⋱⋮⋮⋱⋱u~0u~0⋮u~n-2u~n-1]-[u0-Im0⋯0u1u0-Im⋱⋮⋮⋱⋱0un-1⋮u1u0-Im]×[x~n-1x~0⋯x~n-2x~n-2x~n-1⋱⋮⋮⋱⋱x~0x~0⋮x~n-2x~n-1]}.
So we obtain that the inverse of a block Toeplitz matrix can be represented as a sum of products of block lower triangular Toeplitz matrices and block circulant matrices. This is a generalization of the formula of Ammar and Gader [19]. And when φ=1 and ψ=-1, the inverse formula (22) can be written as a sum of products of block skew-circulant matrices and block circulant matrices.
(25)T-1=12{[x0-xn-1⋯-x1x1x0⋱⋮⋮⋱⋱-xn-1xn-1⋮x1x0]×[u~n-1u~0⋯u~n-2u~n-2u~n-1⋱⋮⋮⋱⋱u~0u~0⋮u~n-2u~n-1]-[u0-2Im-un-1⋯-u1u1u0-2Im⋱⋮⋮⋱⋱-un-1un-1⋮u1u0-2Im]×[x~n-1x~0⋯x~n-2x~n-2x~n-1⋱⋮⋮⋱⋱x~0x~0⋮x~n-2x~n-1]}.
This is a generalization of the formula of Ammar and Gader [21], where they considered the Hermitian Toeplitz matrix.Lety=(y0,y1,…,yn-1)′, z=(z0,z1,…,zn-1)′, y~′=(y~0,y~1,…,y~n-1) and z~′=(z~0,z~1,…,z~n-1) be the solutions of the equations Ty=Ek, Tz=Ek+1, y~′T=En-k-1′, and z~′T=En-k-2′ for some integer k(0≤k≤n-1), respectively. In addition, yn-1 and y~0 are both nonsingular, y~0-1∑i=1n-1‍y~iT-n+i=∑i=1n-1‍T-iyi-1yn-1-1 for 0≤k≤n-2 and (1/φ)y~0-1+y~0-1∑i=1n-1‍y~iT-n+i=(1/φ)yn-1-1+∑i=1n-1‍T-iyi-1yn-1-1 for k=n-1.Fork<n-1, we have Tn=T0+(1/φ)∑i=1n-1‍T-iyi-1yn-1-1=T0+(1/φ)y~0-1∑i=1n-1‍k~iT-n+i. Then we obtain
(26)Tu=T1φ(Zφy-z)yn-1-1=1φT[φyn-10⋮0]yn-1-1+1φT[0y0⋮yn-2]yn-1-1-1φTzyn-1-1=[T0T1⋮Tn-1]+1φ[φ(Tn-T0)yn-1-T-n+1yn-1⋮-T-1yn-1]×yn-1-1+1φEk+1yn-1-1-1φEk+1yn-1-1=[TnT1-1φT-n+1⋮Tn-1-1φT-1],u~′T=1φy~0-1(y~′Zφ-z~′)T=1φy~0-1(0,…,0,φy~0)T+1φy~0-1(y~1,…,y~n-1,0)-1φy~-1z~′T=(Tn-1,…,T1,T0)+1φy~0-1(-y~0T-1,…,-y~0T-n+1,φy~0(Tn-T0))+1φy~0-1En-k-1′-1φy~0-1En-k-1′=(Tn-1-1φT-1,…,T1-1φT-n+1,Tn).
For k=n-1, we have Tn-T0=(1φ)yn-1-1+(1φ)∑k=1n-1‍T-iyi-1yn-1-1=(1φ)y~0-1+(1/φ)y~0-1∑k=1n-1‍y~kT-n+k. A similar argument shows that
(27)Tu=[TnT1-1φT-n+1⋮Tn-1-1φT-1],u~′T=(Tn-1-1φT-1,…,T1-1φT-n+1,Tn).As a result, we obtain thatu=(1/φ)(Zφy-z)yn-1-1 and u~′=(1/φ)y0-1(y~′Zφ-z~′) are the solutions of (17) and (18), respectively. This result together with Theorem 2 yields the following corollary.Corollary 5.
LetT be the block Toeplitz matrix given by (1). If (15) and (16), Ty=Ek, Tz=Ek+1, y~′T=En-k-1′, and z~′T=En-k-2′ are solvable for some integer k(0≤k≤n-1), in addition, yn-1 and y~0 are both nonsingular, y~0-1∑i=1n-1‍y~iT-n+i=∑i=1n-1‍T-iyi-1yn-1-1 for 0≤k≤n-2 and (1/φ)y~0-1+y~0-1∑i=1n-1‍y~iT-n+i=(1/φ)yn-1-1+∑i=1n-1‍T-iyi-1yn-1-1 for k=n-1, then T is invertible and
(28)T-1=1φ-ψ(C(x,ψ)·C(Jy~0-1(Zφ′y~-z~),φ))-C((Zψy-z)yn-1-1,ψ)·C(Jx~,φ)).Corollary5 shows how to construct the inverse of a block Toeplitz matrix, provided that the first block column and last block row, along with two successive block columns and block rows of the inverse, are given. More precisely, the choice of k=n-1 gives that Ek+1=E0 and En-k-2=En-1. This means that z=x and z~=x~. As a consequence, we have the following result.Corollary 6.
LetT be the block Toeplitz matrix given by (1). If (15) and (16), Ty=En-1, and y~′T=E0′ are solvable, in addition, yn-1 and y~0 are both nonsingular, y~0-1∑k=1n-1‍y~kT-n+k=∑k=1n-1‍T-iyi-1yn-1-1, then T is invertible and
(29)T-1=1φ-ψ(C(x,ψ)·C(Jy~0-1(Zφ′y~-x~),φ))-C((Zψy-x)yn-1-1,ψ)·C(Jx~,φ)).Corollary6 is a generalization of the well-known formula of Gohberg and Heĭnig. In [13], the authors have shown that the first and last block columns together with the first and last block rows of the inverse are sufficient to construct the inverse T-1. In addition, we decompose the inverses of block Toeplitz matrices as a sum of products of block circulant matrices.


## 4. Stability Analysis

In the scalar case, the inverse formula (22) in Section 3 is just the well-known formula of Gohberg and Olshevsky; see Theorem 3.1 in [20]. Hence, solving two linear systems are sufficient to reconstruct the inverse of the Toeplitz matrix T-1. Let x=(x0,x1,…,xn-1)′ and u=(u0,u1,…,un-1)′ be the solutions of (15) and (17), respectively. In the scalar case, formula (22) can be written as
(30)T-1=φφ-ψ((u-φ-ψφE0,ψ)C(x,ψ)·C(u,φ)-C(u-φ-ψφE0,ψ)·C(x,φ)),
where φ≠0 and ψ(≠φ) is an arbitrary number. For convenience, we rewrite T-1 as
(31)T-1≐φφ-ψ(C11C12-C21C22).
In this section, we want to show that the evaluation of some scalar inverse formulas in Section 3 is forward stable. An algorithm is called forward stable if for all well-conditioned problems, the computed solution x^ is close to the true solution x in the sense that the relative error ∥x-x^∥2/∥x∥2 is small. In the matrix computation, roundoff errors occur. Let A,B∈Cn,n and α∈C; if we neglect the O(ε2) terms, then for any floating-point arithmetic with machine precision ε, there are
(32)fl(αA)=αA+E,∥E∥F≤ε|α|∥A∥F≤εn|α|∥A∥2,fl(A+B)=A+B+E,∥E∥F≤ε∥A+B∥F≤εn∥A+B∥2,fl(AB)=AB+E,∥E∥F≤εn∥A∥F∥B∥F.
See [22]. According to the floating-point arithmetic, we have the following result.Theorem 7.
LetT be a nonsingular Toeplitz matrix given by (1) with m=1 and let it be well conditioned then the inversion formula (30) is forward stable for φ≠0 and a given number ψ(≠φ).Proof.
Assume that we have computed the solutionsx^, u^ in the inverse formula (30) which are perturbed by the normwise relative errors bounded by ε^(33)∥x^∥2≤∥x∥2(1+ε^),∥u^∥2≤∥u∥2(1+ε^).
Let N=max{1,ψ} and M=max{1,φ}. Then, we have
(34)∥C11∥F≤nN∥x∥2,∥C12∥F≤nM∥u∥2,∥C21∥F≤n(φ-ψφ)2+nN2∥u∥22≤n|φ-ψφ|+nN∥u∥2,∥C22∥F≤nM∥x∥2.
By using the perturbed solutions x^, u^, the inverse formula (30) can be expressed as
(35)T^-1=fl(φφ-ψ(C^11C^12+C^21C^22))=fl(φφ-ψ((C11+ΔC11)(C12+ΔC12)+(C21+ΔC21)(C22+ΔC22))φφ-ψ)=T-1+φφ-ψ(ΔC11C12+C11ΔC12+ΔC21C22+C21ΔC22+E+F)+G.
Here, E is the matrix containing the error which results from computing the matrix products, F contains the error from subtracting the matrices, and G represents the error of the multiplication by φ/(φ-ψ). For the error matrices ΔC11, ΔC12, ΔC21, and ΔC22, we have
(36)∥ΔC11∥F≤ε^∥C11∥F≤ε^nN∥x∥2,∥ΔC12∥F≤ε^∥C12∥F≤ε^nM∥u∥2,∥ΔC21∥F≤ε^∥C21∥F≤ε^n(|φ-ψφ|+N∥u∥2),∥ΔC22∥F≤ε^∥C22∥F=ε^nM∥x∥2.
It follows that
(37)∥E∥2≤∥E∥F≤εn(∥C11∥F∥C12∥F+∥C21∥F∥C22∥F)≤εn2M∥x∥2(|φ-ψφ|+2N∥u∥2),∥F∥2≤εn∥T-1∥2,∥G∥2≤∥G∥F≤εφφ-ψ(∥C11∥F∥C12∥F+∥C21∥F∥C22∥F)≤εnMφφ-ψ∥x∥2(|φ-ψφ|+2N∥u∥2).
After adding all these error bounds, we have
(38)∥T^-1-T-1∥2≤φφ-ψ(2ε^n+εn2+εn)×M∥x∥2(|φ-ψφ|+2N∥u∥2)+εnφφ-ψ∥T-1∥2.
Note that x and u are the solutions of (15) and (17), respectively; then ∥x∥2≤∥T-1∥2 and ∥u∥2≤∥T-1∥2∥f∥2, where f=(Tn,T1-(1/φ)T1-n,…,Tn-1-(1/φ)T-1)′. Thus, the relative error is
(39)∥T^-1-T-1∥2∥T-1∥2≤φφ-ψ(2ε^n+εn2+εn)×M(|φ-ψφ|+2N∥T-1∥2∥f∥2)+εnφφ-ψ.
As T is well conditioned, thus, ∥T-1∥2 is finite. Obviously, ∥f∥2 is finite. Therefore, the formula (30) presented in this section is forward stable.For example, there are two particular cases of the inverse formula (30). When φ=1 and ψ=-1, the inverse formula T-1=(1/2)(C(x,-1)·C(u,1)-C(u-2E0,-1)·C(x,1)), which denotes T-1 as a sum of products of skew-circulant and circulant matrices, is numerically forward stable for a well-conditioned and nonsingular Toeplitz matrix T. In fact, this is the formula of Ammar and Gader in [21]. And when φ=1 and ψ=0, this is the formula of Ammar and Gader in [19]. The inverse formula T-1=(C(x,0)·C(u,1)-C(u-E0,0)·C(x,1)) in which skew-circulant matrices are replaced by upper triangular factors is also forward stable, if T is nonsingular and well conditioned.We also find that even whenψ=∞ and a given number φ≠0, the inverse formula (30) is still numerically forward stable. A similar argument can show that the inverse formulas in Corollaries 5 and 6 for the scalar case are all numerically forward stable when T is nonsingular and well conditioned.


## 5. Concluding Remarks

In this paper, with the help of the block cyclic displacement, the inverses of block Toeplitz matrices are discussed. New formulas for inversion of block Toeplitz matrices are obtained, which can be decomposed in a sum of products of block circulant matrices. In the scalar case, we analyze the stability of the inverse formulas. In addition, it should be remarked that any mention of matrix Padé forms for representing inverses of Toeplitz matrices could also be given in terms of solving block linear systems. Also the proofs of the inverses formulas in [14] could also be extended to prove the inverse formulas in this work.



---

*Source: 207176-2013-04-16.xml*