Inertias of Block Band Matrix Completions.
This paper classifies the ranks and inertias of hermitian completion for the partially specified 3 x 3 block band hermitian matrix (also known as a "bordered matrix") P=\pmatrix{A&B&?\cr B^*&C&D\cr ?&D^*&E}. The full set of completion inertias is described in terms of seven linear inequalities involving inertias and ranks of specified submatrices. The minimal completion rank for P  is computed.We study the completion inertias of partially specified hermitian block band matrices, using a block generalization of the Dym--Gohberg algorithm. At each inductive step, we use our classification of the possible inertias for hermitian completions of bordered matrices. We show that when all the maximal specified submatrices are invertible, any inertia consistent with Poincar's inequalities is obtainable. These results generalize the nonblock band results of Dancis [SIAM J. Matrix Anal. Appl., 14 (1993), pp. 813--829]. All our results remain valid for real symmetric completions.
Introduction
We address the following completion problem: given a partially specified hermitian matrix
characterize all the possible inertias In d) of the various hermitian completions H of
P: We call this set the "inertial set" or "inertial polygon" of P .
The issue of classifying positive definite and semidefinite completions of partial matrices is relevant
to various applications involving interpolation, and has been studied thoroughly, e.g. [AHMR],
[D5], [GJSW]. Invertible completions have been studied in [DG] and [EGL2], for band patterns, in
[L] for general patterns, and are associated with maximum entropy and statistics. For other results
concerning ranks and general inertias, see [D1-D6], [EL], [G], [H], [JR1], [CG3].
Following some preliminary material (Sections 2-4), we present in Sections 5 and 6 several
contributions to the inertia classification problem.
will denote the inertia, that is the number of positive, negative,
and zero eigenvalues of a hermitian matrix H. They are also called the positivity, negativity and
nullity of H.
The main result is:
Theorem 1.1 Given the block "bordered" matrix
@
Z   D   EC
A
are Hermitian (real or complex) matrices of sizes ff \Theta ff, fi \Theta fi and fl \Theta fl,
respectively, and B and D are matrices of sizes ff \Theta fi and fi \Theta fl, respectively. Set:
In
and (- In
For given integers n and p, there exist an ff \Theta fl (real or complex, respectively) matrix Z such
that
In
if and only if

Figure

1.1. Graph of the inertial polygon for the bordered matrix
The block partition is not required to be uniform; rectangular (non-square) blocks are permitted.
For this partial matrix P (Z), Theorem 1.1 shows that the inertial set is a (possibly degenerate)
convex seven sided lattice polygon as depicted above.
The proof of Theorem 1.1 is presented in Section 5, along with a variety of corollaries including
a small application to the algebraic matrix Riccati equation.
Cain and Sa established the 2x2 case (i.e., [CS]. The result was generalized to an
arbitrary number of diagonal blocks by Cain in [C], with further results by Dancis in [D1]. The
case with one given diagonal block was proven as Theorem 1 of [S] and as Theorem 1.2 of
[D1]. These cases are reviewed in detail in Section 4, and are later used as milestones in computing
the inertial polygon of Theorem 1.1.
The possible inertias for a bordered matrix missing a single (scalar) entry was catologued by
the second author in [D6], mostly using his Extended Poincar'e's Inequalities (3.3). In [JR] the
lower bounds in (5.5) and (5.6) were determined for the case when the given principal blocks are
invertible (i.e., ff extends to the case of "chordal
patterns".
In computing the inertial set for Theorem 1.1, we combine four simple elements: (i) Schur
complements, (ii) Poincar'e and Extended Poincar'e Inequalities (3.3) as necessary conditions on
the inertia, (iii) the technique of "restricted congruence" (presented in Subsection 2.4), including
a new formula (2.7), for simplifying a partial hermitian matrix and (iv) elimination of variables in
systems of linear inequalities (see Sections 2-3 for details). These techniques enable us to reduce
Theorem 1.1 to a combination of the simpler cases presented in Section 4. These four elements
of the proof, without (2.7), are commonly used in the matrix literature, and in particular in the
completion literature cited above.
Staircase hermitian matrices are the mild generalization of block band matrices described as
generalized block band matrices in the appendix of [JR2]; they look like a double staircase which is
symmetric about and includes the main diagonal.
A staircase (or generalized block band) matrix with s steps is a partial hermitian n \Theta n
R with precisely s specified hermitian submatrices, fR 1
are defined by
@
a
a k i
1. The inertia of each of the
R i 's is denoted by In R
Staircase matrices allow the non-diagonal blocks to be non-square rectangles. Note that R 1
need not overlap R 3 as would be required in a block band matrix. In fact, R 1 need not even
but the main diagonal must be contained in the union of the R i 's. Also the definition
includes block diagonal matrices.
The next theorem shows that a staircase matrix, with all maximal submatrices being invertible,
has hermitian completions with all the inertias consistent with Poincare's Inequalities.
Theorem 1.2 (An inertial triangle) Given an s-step hermitian staircase m \Theta m matrix R.
Suppose that each of the maximal submatrices R 1 s of R is invertible. Then the
inertial polygon of R is the triangle
The proof of Theorem 1.2 is presented in Section 6, along with several theorems about the
possible inertias of hermitian completions of staircase matrices. We will employ the method of
Dym and Gohberg [DG], which decomposes the completion process into a succession of simple
steps, each of which is a Theorem 1.1 step.
These results generalize the (scalar) band hermitian completion results of the second author in
[D6]. A related of Johnson and Rodman is restated as Lemma 5.7 herein.
We state our results for complex hermitian matrices, but they are all equally valid in the real
symmetric case.
Preliminaries
2.1. Notation: We shall denote by p; n and p; n the minimal, resp. maximal possible values
of the positivity and the negativity of the completions of a given partially specified matrix.
Similarly, r and r will denote the minimal and maximal possible values for the rank of
completion matrices of a given partially specified matrix. We have the obvious inequality r - p+n;
which is generally strict. The determination of the maximal rank r for arbitrary (including non-
band) hermitian completion problems is done in [CD]. In fact, it is shown there that the maximal
completion rank does not increase if the assumption that the completion is hermitian is dropped;
consequently, this rank can be computed explicitly using a result of [CJRW].
The inequality r - p + n is similarly obvious; however, it becomes an equality (i.e.
in many cases, including that of Theorem 1.1, see Corollary 5.4, and certain block band matrices,
see Theorem 6.2.
d) will denote the square matrix I p \Phi \GammaI n \Phi 0 d of inertia (p; n; d) . Sometimes we
shall use the triple (-; ffi) to denote the inertia of a given (maximal) specified submatrix and
d) to denote the inertia of a hermitian completion of a given partial matrix. Congruence of
matrices is denoted by - =.
If a square matrix X is written in block form, say ij is of
size a i \Theta a j ; we shall describe X as having block sizes (a
2.2. Schur Complements: Let
If A is invertible then the Schur complement
of A is
Haynesworth [H] has shown that H is congruent to A \Phi C \Theta . In particular,
In
More generally, if H is a k \Theta k block matrix, and T is a subset of f1; :::; kg; let A be the
principal submatrix whose block indices are in T : We can move A to the left upper corner by a
permutation of the coordinates, and proceed as before, provided A is invertible. This procedure
will be referred to as complementation with respect to coordinates T . The block division will always
be clear from the context.
A similar procedure is available for non-hermitian matrices, yielding the weaker identity for
and C
We shall refer to this procedure as non-hermitian complementation.
2.3. Canonical Forms: We shall repeatedly use the following terminology:
(i) Equivalence canonical form: It is well known that two matrices A and B are equivalent if
their exist two invertible matrices S and T such that A = SBT . Every matrix A can be transformed
by equivalence to the form
I a 0
, where a = rank A.
We shall also need the following case of "block equivalence": For every matrix in block form
are invertible matrices
respectively, such that
@
I a
A
where
(ii) Strong congruence canonical form: Every hermitian matrix A of inertia (p; n; d) is congruent
to a matrix of the form J(p; n; d):
(iii) Weak congruence canonical form: Every hermitian matrix A of rank r is congruent to a
matrix of the form A 0 \Phi 0, where A 0 is an invertible r \Theta r matrix.
2.4. Restricted Congruence: If P is a partial matrix, and S is invertible, the matrix
can be interpreted as a partial matrix, in the following sense: an entry p 0
ij of P 0 is
determined if it is equal to fS   HSg ij for every possible completion H of P: We call
a restricted congruence if p ij being a specified entry of P implies that p 0
ij is specified in P 0 .
There are some similarities between our concept of "restricted congruence" and Ball et al's
concept of "lower similarity" in [BGRS].
We will use restricted congruence in two ways:
block-diagonal congruence is used to put some (specified or unspecified) blocks of P in
canonical form;
some row and column operations are used to annihilate blocks in P:
In some cases, unspecified blocks may become specified (in fact, annihilated) by congruence.
For example, the 1,1 block of
I
I 0
can be annihilated by the process
I
!/
Z I
I 0
!/
I 0
I
I 0
I 0 0C C A can be simplified toB B @
I 0 0C C A as follows:B
@
I
I \GammaX
@
I 0 0C
@
I
A =B
@
I 0 0C
Inequalities
Necessary conditions. The shape of an inertial polygon for a hermitian completion problem is,
to a large extent, determined by a few inequalities relating matrices and submatrices:
(i) Rank Interlacing. If A is a k \Theta l rectangular block of the m \Theta m matrix H; we have
Inequalities. Let A be a k \Theta k principal submatrix of the m \Theta m hermitian
matrix H: Let - i and - i be the ordered eigenvalues of A and H; respectively. The Cauchy
interlacing Theorem states that - i - i - i+m\Gammak (see e.g. Theorem 4.3.15 in [HJ]). An equivalent
statement are the Poincar'e inequalities:
The upper and lower bounds of (3.2) were strengthened in Theorem 1.2 of [D2]; the lower bound
was strengthened as follows:
(iii) Extended Poincar'e's Inequalities. ([D2]) Given a hermitian matrix in block form,
set
Then
In H - In
Inequalities (3.1), (3.2), (3.3) form a set of a priori bounds on completion inertias. In fact, in
[CJRW] it is proved that the upper bound in (3.1) is sufficient for the determination of the maximal
completion rank in the case of non-hermitian completions, and in [CD] the same is shown in the case
of hermitian completions. It turns out that the necessary conditions of type (3.1), (3.2), (3.3) are
also sufficient in determining the full inertial polygon in many cases, including the bordered matrix
case (Theorem 1.1) and the block diagonal case ([D1]). We shall emphasize cases of sufficiency of
these conditions in the text.
4 Towards the 3 \Theta 3 Bordered Case
This section paves the way for the analysis of the bordered case, which is carried out in Section
5. The material in this section has independent value, and much of it is well-known. We shall
compute the inertial polygon for a 3 \Theta 3 block pattern of the form
@
as Lemma 4.8. The special cases
A ?
and
A ?
, originally due to Cain and S'a, will
also be reviewed, as Lemmas 4.1 and 4.5. We shall also compute the possible inertias of a matrix
of the form A+X with inertia limitations on the unknown matrix X as Lemma 4.3. The results
of Lemma 4.1 will be used to establish Lemmas 4.3 and 4.8 . The result of Lemma 4.3 will be used
to establish Lemma 4.5 which will be used in the proof of Lemma 4.8 which will be used in the
proof of Theorem 1.1. The proof of Theorem 1.1 and Lemma 5.10 consist of reduction to the case
of (4.1), which itself, is of independent interest.
Lemma 4.1 Let
be a partially specified hermitian matrix of block sizes (ff; fi).
Then the inertial polygon for H is the pentagon that contains all the lattice points (-(H); -(H))
which satisfy the inequalities:
Proof. The necessity of (4.2) follows from (3.1) and (3.2). For sufficiency, put H 1 in diagonal
form, and complete H to a diagonal matrix. It is easy to show that every inertia in (4.2) is obtained.
See also Theorem 1 in [S] and Theorem 1.2 in [D2].
Corollary 4.2 In Lemma 4.1 the extremal values are
Moreover, H in Lemma 4.1 admits positive definite, non-negative definite, or invertible completions
if and only if H 1 is positive definite, non-negative definite, or rank(H 1
respectively.
The following result can be deduced with some effort from Theorem 2 in [S]:
Lemma 4.3 Let A and X be m \Theta m hermitian matrices. We consider A to be fixed and X to be
a variable matrix with -(X) - a and -(X) - b: Then the possible inertias of are the
nonnegative lattice points satisfying the following inequalities:
Proof. Necessity is obvious due to Sylvester's inertia principle. For sufficiency, take A to be
diagonal, and restrict X to be diagonal as well. It is easy to show that every inertia in (4.3) is
obtained.
Corollary 4.4 In Lemma 4.3, 0g. Also, A admits positive
definite completions if and only if - a and - non-negative definite completions if
and only if - a; and invertible completions if and only if ffi - a
For the values of n; n in Lemma 4.3, see also [CG3] Lemma 2.2.
The following result is due to Cain and S'a.
Lemma 4.5 ([CS]) Let
be hermitian of block sizes (ff; fl): Then the inertial
polygon of H is determined by these inequalities:
\Gamma-
A generalization of Lemma 4.5 and (4.4) to more than two diagonal blocks can be found in
Brian Cain's paper [C]. A short proof of the necessity part of Cain's result was obtained by J.
Dancis ([D1] Corollary 11.1 and Lemma 11.2). In the 2 \Theta 2 block case, this proof is given below.
Proof of necessity of Inequalities (4.4).
be a completion of H. Set
F
G
Noting that
rank
F
we apply the Extended Poincare Inequalities (3.3) to both F and G and we obtain
Subtracting this inequality from -(H) yield the right side of (4:4). A
symmetric argument produces the left inequality.
Proof of Lemma 4.5. We show by reduction to Lemma 4.3 that Inequalities (4.4) describe the
inertial polygon. Let
be a completion of H. Putting F in weak canonical
form, and taking the Schur complement of the new first coordinate, F 0 , we calculate, using (2.2):
@
A
Hence
Putting G \Theta in weak canonical form, we get H
@
Putting X 4 in
equivalence canonical form, we get
@
I r
A
We set
In(G \Theta
Removing coordinate 5 and taking the Schur complement of coordinates 1,3, and 4, in H 0 , we
calculate using Equations (2.2) and (2.7):
We now develop the relevant inequalities involving the dummy variables in (4.6). By Lemma 4.3
the inertial polygon of G \Theta is determined by the inequalities on
\Gamma-
By Lemma 4.3 again, we compute the inertial polygon for
The only restriction on r is the size of X
Now (4.4) is obtained from Equations (4.5) - (4.9) by eliminating -
- and r:
The values of p; p; n; n can easily be computed from Lemma 4.5. The values n and n; were
computed in [CS].
Lemma 4.6 [D1] In Lemma 4.5 we have
Moreover, there exists a matrix X which simultaneously achieves the minimal possible ranks
for
F
and
G
namely
rank
G
Proof. The values of p and n follows directly from Lemma 4.5. To show the rest, we may put F
and G in strong canonical form:
@
I
@
I
@
Choose the diagonal entries of X 1;1 and X 2;2 by the rule (X 1;1 1. Choose all
other entries of X to be zero. We get a completion with the desired minimal ranks.
The original result of J. Dancis ([D1] Theorem 1.3) is in fact more general in two respects: first,
it extends to more than two block diagonals. Moreover, it is not restricted to minimal ranks: it
shows, more generally, that any choice of kernels of a column decomposition as well as any choice
of inertia which is consistent with the Extended Poincar'e inequalities, can be obtained:
Theorem 4.7 constrained hermitian completion.) [D1] Given hermitian matrices H ii ;
In H ii be the block diagonal
matrix of size Choose a subspace K i ae ker H ii such that dim ker H ii \Gamma dim K i -
s:
Then an integer triple (-; ffi) satisfying the equality - is the inertia of a hermitian
completion H of S with column block structure:
each M i is an n \Theta n i matrix; and ker M
if and only if (-; ffi) satisfies the inequalities
(The notation here is different than the one used in [D1]: the r i and \Delta i here correspond to -
The next lemma is the main result of this section; it combines Lemmas 4.1 and 4.5.
Lemma 4.8 Let P be a partial matrix of the formB B
@
A and of block sizes (ff; fl; ffl):
Then the inertial polygon of P consists of the lattice points determined by these inequalities:
The sufficiency proof of Inequalities (4.12) is the same as for Inequalities (4.4).
Proof. Every completion H of P has the form

F
G
was computed in Lemma 4.5. By Lemma 4.1, In(H 1 ) and In(H) are connected by
and eliminating In(H 1 ) from Inequalities (4.4) and (4.13), and using the identities
we get Inequalities (4.12).
5 Inertias of Block Bordered Matrices
In this section we establish Theorem 1.1 using the results stated in Sections 3 and 4. The material
in this section is new. The scalar case was classified in [D3]. Other special cases of Theorem 1.1
occur in [D1], [L],[G], and [CG3].
Subsections 5.3-5.5 contain additional results and corollaries of of Theorem 1.1 concerning
minimal rank completions of various types, and the case where the two maximal specified hermitian
submatrices R 1 and R 2 of P (Z) of Theorem 1.1 are invertible. In Subsection 5.6 we present a
small application to the algebraic matrix Riccati equation A+AZ   +ZB   +ZCZ  0: a criterion
for solvability and a characterization of the possible inertias of the solution matrix Z (which need
not be hermitian).
5.1. Internal Relations for Bordered Matrices.
For the the bordered matrix P (Z) of Theorem 1.1, we note that R
; and R
are the maximal specified hermitian submatrices of P (Z) and
the maximal specified non-hermitian submatrix of P (Z).
Observation 5.1 (Internal relations for a bordered matrix) With the notation of Theorem
1.1, we define
and
Then
Proof. The inequality of (5.1) follows from rank considerations. The equality, as well as (5.4),
follows from the definitions. Applying the Extended Poincar'e's Inequalities to C as a submatrix
of R 1 or R 2 provides (5.2). (5.3) also follows from the Extended Poincar'e's Inequalities.
5.2. Proof of Theorem 1.1.
Before proving the theorem, let us comment on the necessity and minimality of its conditions:
Minimality: The inertial polygon for a simple matrix, with all seven edges present, is illustrated
in Fig. 5.1. The matrix chosen was of block sizes (6; 1;
and B; C and D are zero matrices of appropriate order. This results in r and the three \Delta's
being zero. This example shows that the set of seven inequalities defining the inertial diamond is
not redundant.

Figure

5.1. A seven-sided inertial polygon.
Necessity: Necessity of each one of the seven inequalities can be easily demonstrated: inequality
(1.4) follows from (3.1). The upper bounds in Inequalities (1.1) - (1.2) are a consequence of (3.2).
The lower bounds in (1.1) and (1.2) are just the Extended poincar'e's inequalities (3.3). It remains
to derive (1.3).
5.2 The Extended Poincar'e's Inequalities (3.3) imply (1.3).
Proof. We define the partial matrices
and their completions
Z D   E
Let
Using the Extended Poincar'e's Inequalities(3.3) twice, we have:
Substitute for one of the p's on the left hand side
Using the identities -
We note that
But this translates into:
or equivalently
Finally, (5.8) and (5.9) establish (1.3).
We will establish Theorem 1.1 by using Schur complements (Equation (2.2)) and row and
column operations (Equation (2.7)) and the other forms presented in Section 2, repeatedly, in
order to reduce Theorem 1.1 to Lemma 4.8.
Proof of Theorem 1.1 We begin by putting C in weak canonical form:
with block sizes (ff; rank C; Taking the Schur complement of C 0 in P (Z) as in
yields
In In -
In
where
@
Y   D"   GC C
Next we put [B"   ; D"] in the canonical form (2.4). Using (5.10), we obtain the matrix
@
F
F
I
22 X
A
The block sizes here are are
blocks of Y , the F ij 's and G ij 's are conforming blocks of F and G. The new block sizes are related
to ff; fi; fl via
Next we use restricted congruence, see Section 2. By row and column operations based on
and H
, we may assume without loss of generality, that
are all zero. This modifies the matrix -
without changing its inertia, to
@
I \Delta 00
22 X
A
We may discard row 7 and column 7, which are all zero. Next we complement H 0 with respect
to the block
[1;2;4;5;6;10] =B
@
I \Delta 00
A
The Schur complement turns out to be
@
@
22
@
I
@
A
@
22
@
with block sizes (ff . By the Schur complement inertia formula (2.2), we get
In In H 0
In
In H 00
(The fi 0 accounts for removing coordinate 7 from H 0 ). Thus we have
In In In
We will use Equation (5.17) and Lemma 4.8 to calculate In P (Z); to find In H 00 , we must first
calculate In F 33 and In G 11 :
5.3
In F In In C 0
In G In In
Proof. By restricting Equations (5.10)-(5.14) to the upper left corner R 1 , we may take the
Schur complement of C 0 as a submatrix of R 1 ; this yields:
In
@
In In
F B"
where F is as in Equation (5.11). Using elimination, Equation (2.7), we note that
In
F B"
@
I
A
In F 33
where F 33 is as in (5.12). Solving for In F 33 in Equations (5.19) and (5.20) yields the first part
of (5.18). A similar argument holds for the second part.
We proceed with the proof of Theorem 1.1. Applying the size identities
and Lemma 4.8 (with its submatrices F and G corresponding to F 33 and G 11 here), we obtain these
inequalities for In H 00 :
Inequalities are obtained by plugging Inequalities (5.21) and Equation (5.18) into
Equation (5.17) and then using Equations (5.1), (5.4) and (5.13) to eliminate all the intermediary
inertias.
5.3. Extremal inertia values and inertia preserving completions
In this subsection and the next, we use the geometry of the inertial polygon as the basis (i) for
establishing a minimum rank completion for the bordered matrix P of Theorem 1.1 (Corollary
5.5); and (ii) for showing that, assuming invertibility of R 1 and R 2 , all the inertias which are
consistent with Poincare's Inequalities can be obtained by completion (Corollary 5.8). In Section
6 we will use these results as building blocks for our proofs of completion theorems for "staircase"
matrices.
First we show, under the notation of Theorem 1.1, that there is always a completion whose
positivity and negativity are the minimal ones allowed by the Extended Poincar'e's Inequalities.
This implies that the minimal rank is
Corollary 5.4 (Minimal rank completions.) With the notation of Theorem 1.1, there exists a
hermitian completion
Proof. We argue by inspection on Figure 5.1. If the vertex not in the inertial
polygon for P (z), this vertex must be cut off by one of the extremal lines defining Inequalities (1.2
- 1.4). Since these inequalities are consistent, it is clear that (p must satisfy (1.2) and (1.4).
It remains to check the two inequalities (1.3). We have to consider four possible choices for p 0 and
in the notation of Theorem 1.1:
Suppose that
Rank considerations imply that Rank C Equation (5.1) implies that -
This and Equation (5.22) imply that
proving the right inequality in (1.3). Interchanging the roles of the - 0 s and the - 0 s
establishes the left inequality.
(II) A similar proof applies to the case (p 0
then a combination of Equations (5.1),(5.3) and (5.4) yields rank R 1
algebra we get - This and (5.23) implies that
proving the right inequality in (1.3). Interchanging the roles of the - 0 s and the - 0 s
establishes the left inequality.
(IV) A similar proof applies to the case
Remark. This Corollary 5.4 implies that the minimal rank of the set of hermitian completions of
Constantinescu and A. Gheondea presented in [CG3] another formula for n.
Of particular interest is the case where the minimal rank solutions inherit their inertia values
and n from the specified blocks R 1 and R 2 , i.e.
We call such completions inertia preserving. Note that (5.24) does not guarantee that the minimal
completion rank is g: The following simple result will play a major role in
finding inertia preserving completions for block band matrices in Section
Corollary 5.5 (Inertia preserving completions.) Assume the notation of Theorem 1.1. Suppose
that P satisfies an "equality of ranks" condition:
Then P admits inertia preserving completions.
Indeed, under condition (5.25), the formulas of the inertial polygon simplify, since we have
In particular, (5.24) holds.
Condition (5.24) and Corollary 5.5 are implied by the stronger condition
In the notation of Observation 5.1, Equation 5.26 is equivalent to any of the following:
This condition is satisfied if e.g. C is invertible.
Condition (5.25) is not necessary for the existence of inertia preserving completions. As an
example, consider the partial matrix
@
A simple argument, using the Extended Poincar'e's Inequalities(3.3), shows that if (5.25) is not
satisfied, then the inertia preserving completion must inherit both p and n, from the same block.
Hence In the above example,
5.4. The width of the inertial set
We define the width w of the inertial polygon to be the maximal value of
all pairs of points (p; n) and (p belonging to the inertial polygon. See Figure 1.1. This width
equals the sum of the lengths of the two perpendicular sides of the inertial polygon. It is clear
that Inequality (1.3) puts a limitation on the width; namely, w cannot exceed the modulus of the
difference of the right and left hand sides in this inequality:
(it can be shown directly that this value is always non-negative).
The sides, with slope of minus 1, come from Inequality (1.3), which may be rewritten as
In this way
is related to the width of the inertial polygon. The width of the inertial polygon tends to increase
as we increase the ranks of R 1 and R 2 : In this section we study the two extreme cases. The "slim"
case is when Rank R Here the polygon degenerates to a segment with a
degree inclination. The "fat" case occurs under the maximal rank condition det R 1 det R 2 6= 0;
here the polygon extends to maximum capacity, and fills a triangle (Corollary 5.8 ). We start with
the "slim" case.
Corollary 5.6 Given the notation of Theorem 1.1. Suppose that
Then the inertial polygon coincides with the segment
Moreover, the minimal rank completion is unique.
Proof. Condition (5.30) together with the Poincar'e inequalities imply that C; R 1 and R 2 all have
the same inertia (-;  ) (with possibly different nullities). The same condition also implies (5.26),
hence (5.25), and Corollary 5.5 can be used. We conclude that
That condition (5.31) implies zero width, is clear from (5.27). The rest which restricts the
polygon to a line segment of the form (- K: The value
follows from Theorem 1.1 with some algebra. It can also be deduced from the maximal rank
considerations in [CD].
To prove uniqueness of the minimal rank completion, we note that (5.30) forces the factorizations
I
I
can check that
the completion rank is rank C the unique solution requires that Z
Observation 5.6 represents the extreme case of a "slim" inertial set. We now turn to examine
the other extreme case of a "fat" inertial set. Under the assumption that R 1 and R 2 are invertible
matrices, four inequalities among (1.1-1.4) are redundant, and the inertial polygon becomes a
triangle, admitting any inertia compatible with the Poincar'e inequalities and the size limitation.
First we quote the following known result about matrices with chordal graphs. Chordality is
discussed in [GJSW], [JR1] and [JR2], and it suffices to say that block bordered 3 \Theta 3 patterns (and
in fact the general staircase patterns of Section have chordal graphs.
Lemma 5.7 . (Corollary 6 of [JR1]) In any hermitian partial matrix P of size m \Theta m whose
pattern has a chordal graph, and all its maximal hermitian specified submatrices are invertible, the
points together with all the lattice points on the straight
line segment connecting them, belong to the inertial set of P:
In the bordered case we can say more:
Corollary 5.8 Assume the notation of Theorem 1.1. Suppose that R 1 and R 2 are invertible.
Then the inertial polygon is the triangle whose vertices are
In other words, every inertia consistent with the Poincar'e inequalities
Proof. Let T be the triangle defined by the above three inequalities. Let D be the inertial polygon.
It is easy to check that v 0 are the three vertices of T : Since the Poincar'e inequalities are a
subset of (1.1) - (1.4), we get the inclusion D ae T : Note that in (1.4) our hypothesis implies that
On the other hand, v By convexity, we
conclude that T ae D:
5.5. Simultaneous rank minimization
We now strengthen the minimal rank result obtained in the last subsection (Corollary 5.4). Consider
the partial matrices N 0 and N 00 of Equation 5.5. We wish to find a matrix Z which will
simultaneously induce minimal rank completions in N 0 and N 00 as well as in the full bordered
matrix P .
Before we tackle the general case, let us make the simplifying assumption (5.26), for which a
slightly stronger result is available. This very simple special case also serves as an outline and
motivation for the general case. Also readers who are only interested in Theorems 6.2 and 1.2 and
Corollary 6.4 but not in Theorem 6.7 may read the proof of Lemma 5.9 and skip the calculations
of Lemma 5.10.
Lemma 5.9 Assume, along with the notation of Theorem 1.1, that
Then there exists a matrix Z 0 satisfying simultaneously the inertia preserving condition
and (using the notation of Equations 5.5 and 5.6) the two minimal rank conditions
Such a completion also satisfies the kernel condition
Ker
Proof. Since Equation (5.26) implies Corollary 5.5, P admits inertia preserving completions,
(5.32). The fact that rank(R 1 ) and Rank(R 2 ) are the minimal completion ranks for N 0 and N 00
is obvious. To prove that conditions (5.32-5.33) are attainable simultaneously, we re-examine the
proof of Theorem 1.1, and reduce the situation to Lemma 4.6, where a positive answer is available.
We assume the rank condition (5.26), which implies -
follow the proof of Theorem
1.1. The matrices B 00 and D 00 in (5.10) turn out to be zero:
@
A
of block sizes (ff; rank C; ffi(C); fl) . Now removing the zero row and column and then taking the
Schur complement with respect to C 0 yields
Y   G
We get therefore
Y
G
Lemma 4.8 shows that a matrix exists for which -
G
are simultaneously
minimum rank completions. Choosing Z we see from (5.34) that Z 0
minimizes all the three ranks involved.
It remains to show the kernel condition. First, we observe, for all Z, that
Ker P (Z) oe Ker (N 0 (Z) \Phi I) and Ker(N 0 (Z)) ae Ker(R 1
For Z 0 just obtained, we actually have (5.33), hence the second containment must be equality:
Now the first containment becomes
Ker
Similarly Ker P (Z 0 ) oe Ker (I \Phi R 2
Ker
In the general situation, when the simplifying assumption rank
is not assumed, a simultaneous minimal rank solution still exists, but it is not necessarily an inertia
preserving solution, and the additional kernel condition cannot be guaranteed.
Lemma 5.10 simultaneous minimal rank completion lemma) With the notation of Theorem
1.1, the minimal completion ranks for are, respectively,
Moreover, there exists a matrix Z 0 which produces these ranks simultaneously.
Proof. Assume the notation of Theorem 1.1 and Observation 5.1. First we verify the expressions
for the minimal ranks involved. Corollary 5.4 implies that matrices.
Using our definitions of \Delta 0 and \Delta 00 , the identities r(N 0
are obvious.
Having computed the minimum completion ranks for these 3 matrices, we now demonstrate
that the three minimum ranks can be achieved simultaneously. Our plan is to perform all the
steps of the proof of Theorem 1.1 simultaneously on the three matrices involved. We call a step
permissible if a completion exists which preserves the three minimal ranks. As will be seen, not all
steps are permissible, and some modification will be necessary.
The reduction of H to -
H in (5.12) is permissible, since C is a common block in all three
matrices. Besides -
H; this reduction applied to N 0 and N 00 yields
@
F
F
I
A
@
I
A
Using (2.3), these operations preserve ranks:
Our aim now is to minimize simultaneously rank -
H in (5.12) and rank -
The passage from -
H in (5.12) to H 0 in (5.14) is also permissible, and may be followed by a
similar passage from -
H i to new matrices H 0
all the F; G; X entries located in first and
last block rows and columns in -
H i are made zero. We also discard zero rows and columns in these
matrices (the seventh block coordinate in H 0 ).
Permissibility is violated in the passage from H 0 to H 00 in (5.15). More precisely, complementation
of H 0 with respect to coordinates 1,4,6,10 is permissible; unfortunately, symmetric
complementation with respect to coordinates 2 and 5 is not permissible, since these coordinates are
not present in both H 0
Consequently, the proof of Theorem 1.1 has to be modified: we
perform on H 0 non-hermitian complementation (2.3) with respect to block rows 1,2,5,6 and block
columns 4,5,9,10, i.e. with respect to the matrix
[1;2;5;6][4;5;9;10] =B
@
I \Delta 00
A
. The Schur complement of H 0 with respect to H 0
[1;2;5;6][4;5;9;10] isB
@
I \Delta 00
22 X
A
\GammaB
@
A
@
I \Delta 00
A
@
A
@
I
22 X
A
This matrix is of the general formB
@
I
A
where the W i 's are unspecified. Indeed, it is easy to see that any arbitrary choice of the W i 's
can be achieved by appropriate choice of the X i 's. The respective Schur complements of H 0
1 and
2 with respect to H 0
[1;2;5;6][4;5;9;10] turn out to be
~
I
@
A
Taking zero is obviously a minimal rank choice for all three matrices.
We have reduced the original problem to the simpler problem of simultaneously minimizing the
ranks of the three matrices
F
G 11
Reduction to Lemma 4.8 is completed.
In Section 6 we shall use the following weakened form of Lemma 5.10, which has better propagation
properties.
Corollary 5.11 (Propogation of internal inequalities of Bordered Matrices) Given the notation
of Theorem 1.1 and Observation 5.1, then there exists a matrix Z 1 such that
Corollary 5.11 follows directly from Lemma 5.10 and Observation 5.1.
5.6. Solvability of the Ricatti equation.
We end this section with a small contribution connected to the theory of Lyapunov and Riccati
equations.
Lemma 5.12 Given matrices A; B, and C of sizes ff \Theta ff; al \Theta fi; fi \Theta fi; respectively, with
A and C hermitian, define
Then the possible inertias of matrices of the form P arbitrary
Z, form the septagon
Proof. This is an easy corollary of Theorem 1.1, using complementation on the last two block
coordinates of the bordered matrixB B
@
Z   I 0C C
In [CG3] the values of n and n were determined for this case.
Corollary 5.13 The Riccati equation A solvable if and only if
These results apply also for the Lyapunov or Stein equations: simply assume that C or B is a
zero matrix. We emphasize, however, that in the classical context of these equations Z is assumed
hermitian (at least), and then it is not clear whether this puts additional restrictions on the set of
inertias.
6 Some Completion Results for General Band Matrice

In this section, we consider hermitian matrices with general block band or "staircase structure",
where again the blocks may vary in size. We follow the method of Dym and Gohberg [DG], which
decomposes the completion process into a succession of simple steps, each involving the completion
of one bordered submatrix. Combining this procedure with the results of Section 5, we are able to
draw several interesting conclusions:
In Subsection 6.3 we identify certain classes of staircase hermitian matrices which admit
inertia preserving completions; these are completions which inherit their inertia values p and n
from (possibly two different) specified blocks of the given partial matrix P . Such completions are
obviously minimal rank completions (See Theorem 6.2 and Corollaries 6.3 and 6.9). These results
generalize the (scalar) band hermitian completion results of the second author in [D6].
In Subsection 6.3 we consider block band or staircase matrices for which all maximal
specified hermitian submatrices are invertible. We show that such matrices admit all the possible
completion inertias consistent with Poincar'e's inequalities (See Theorem 1.2) which includes inertia
preserving completions. These results generalize the (scalar) band hermitian completion results of
the second author in [D6].
(III) Not every partial matrix admits inertia preserving completions. In Subsection 6.4 we
establish modest upper bounds on the minimal posssible rank for hermitian completions of staircase
hermitian matrices.
6.1. The Staircase Matrix Notation
In dealing with staircase partial matrices, we shall adhere to the following notation and observations,
which shall collectively be referred to as the Staircase Notation.
We recognize the bordered matrix of Theorem 1.1 in each pair (R i and R i+1 ) of successive
maximal hermitian submatrices. We therefore define the s bordered partial submatrices P i to be:
@
where these specified submatrices A of R are
As in the notation of Theorem 1.1, we observe that the R i are the specified block submatrices:
and that each C i is the overlap of R i and R i+1 . The submatrices R 1 ; C and R 2 of the
notation of Theorem 1.1 correspond to the submatrices R of each bordered
submatrix P i .
We shall denote by P i (Z i ) the completions of P i , using Z i in the right upper block of
We denote the inertias of P i (Z i ) by (- 0
In dealing with the i'th bordered submatrix P i ; the incremental ranks
d defined in the notation of Theorem 1.1 and Observation 5.1will be distinguished by the
subscript i.
6.2. The Diagonal Completion Formalism
diagonal [partial] completion R+ of an s-step staircase partial matrix R is an
staircase partial hermitian matrix obtained by completing all the s bordered matrices P i of R. This
entails the addition of a matched pair of whole block diagonals alongside the specified band. In a
diagonal completion the different bordered completions P i (Z i ) are independent of each other, that
is the Z i do not overlap.
(II) A standard procedure for completing a staircase matrix is by a succession of diagonal
completions. Let F denote a full hermitian completion of R. We may obtain F via a chain of s
staircase partial matrices,
Each matrix in (6.1) is obtained from its precursor via diagonal completion, and its staircase pattern
is reduced by one step. We shall distinguish between the relevant submatrices of each
matrix in this chain by attaching to them the appropriate number of (subscript) plus signs.
(III) The N st matrix (1 - in the above chain is called an N-diagonal [partial]
completion of R.
We will identify certain submatrices of R with their counterparts in R+ : For example,
the completed bordered matrices P i (Z i ) of R will be identified with the matrices R+i of R+ : In
addition, the maximal submatrices R i of R will be identified with the submatrices C+i of R+ :
The ordering of these matrices will always be from top left to bottom right.
This technique of completing a hermitian scalar band matrix by adding successive pairs of
diagonals was developed by Dym and Gohberg in [DG]. This technique of completing a hermitian
scalar band matrix was later used in many papers, including [D5], [D6], [DG], [EGL1], [EGL1] and
[EL]. We shall use the more general staircase or general block band approach of the appendix of
[JR2].
In applying the bordered case (for example, Theorem 1.1) to sections of a band matrix or the
more general staircase matrices, the key concept is propagation. Those properties which survive a
single (Theorem 1.1) completion step, will by induction, survive the full completion process. Our
results in this section are all based on properties which propagate.
6.3. Inertia preserving completions
We call an N-step completion R 0 of R inertia preserving if it satisfies the equations:
In particular, if F is a fully specified completion then it is inertia preserving if
Such a completion is necessarily a minimal rank completion.
Not every partial staircase matrix admits an inertia preserving completion. In fact, Example
6.10 will present an infinite sequence of partial staircase matrices whose maximal specified
submatrices all have rank 2 but all the full hermitian completions are invertible.
Lemma 6.1 (Propagation of inertia preservation) Given an s-step hermitian staircase matrix
R. Using the notation of Subsection 6.1, suppose that the blocks of R satisfy these propagation
equations:
Rank (B
for each (using the notation of Subsection 6.2):
(i) There exists a one step inertia preserving completion R+ of R for which
Rank (B
for each
(ii) This completion R+ satisfies the kernel condition
Ker R+i oe Ker (R i \Phi I)
Proof. The proof of (i) is a straightforward application of Lemma 5.9 repeated s times. (6.4)
implies that each P i fulfills the hypothesis of that lemma. Therefore each P i admits a completion
simultaneously
using the notation of Equations 5.5 and 5.6. For the condition rank N
into
For the condition rank N
Rank (B
Together this is precisely (6.5). The condition -(P of Lemma 5.7 applied to each
Part (ii) follows from part (i), (3.3) and Lemma 5.9.
We observe that (6.4) is a propagation condition: Lemma 6.1 shows that this condition can be
made to survive a single diagonal completion. Repeating Lemma 5.12 s times along the chain (6.1),
we get
Theorem 6.2 (Inertia preserving completions) Given an s-step hermitian staircase matrix
R fulfilling the propagation Equation (6.4):
rank (B
Then R admits an inertia preserving fully specified completion F for which
Moreover, for this completion F , Ker F contains all the appropriate kernels of the form Ker (I \Phi
Theorem 6.2 and its proof are largely a block generalization of Dancis' proof in [D6]. The
inequalities show that the expressions in the theorem are lower bounds for
Theorem 6.2 shows that they are achieved.
Corollary 6.3 If all the matrices, C i and R i in a staircase matrix R, have the same rank r,
then there exists a hermitian completion F with rank r.
Proof. The condition that all the C i and R i matrices have the same rank implies (6.4) and
hence Theorem 6.2 is applicable.
This corollary was established for (hermitian and nonhermitian) completions of hermitian and
nonhermitian, resp., band matrices in [EL].
An important special case where Theorem 6.2 is applicable is when all the C i submatrices of
R are invertible.
Corollary 6.4 (Inertia preserving completions) Given an s-step staircase hermitian matrix R.
Suppose that the s submatrices C i of R are all invertible. Then R admits an inertia preserving
completion F whose kernel contains all the appropriate kernels of the form Ker (I \Phi R i \Phi I):
Proof Since all the C i are invertible, the propogation Equation (6.4) holds and Theorem 6.2
applies.
6.4. Incremental bounds on inertia growth
In general, even assuming a minimal rank completion in each step, the ranks of the matrices in (6.1)
may increase. At present, we cannot compute the minimal rank for the completions of a general
staircase matrix or even for a general scalar band matrix. The reason is lack of propagation: the
inertias of P i (Z i ) do not depend exclusively on the inertias of R i and C i ; as is evident from Theorem
1.1. However, use of Corollary 5.11 will enable us to obtain an upper bound on the inertia increase.
In the next observation and lemma, the B+i ; C+i and D+i matrices are the B
matrices of a diagonal completion, R+ ; the d+i will be
which is consistent with our general notation.
Observation 6.5 Let R be a staircase matrix, together with the notation of Subsections 6.1 and
6.2. Suppose that R+ is a diagonal completion of R for which all bordered completions
satisfy the simultaneous minimal rank completion Lemma 5.10. Then the incremental ranks of the
bordered submatrices of R and of R+ are related via
i and d 00
Proof. We have the following connections between R-related and R+ -related objects:
From Lemma 5.10 we note that
Combining these equations yields d 0
. The other equation may be similarly observed.
Lemma 6.6 (Propagation of incremental ranks) Let R be an s-step hermitian staircase ma-
trix. We use the notation
which is consistent with our bordered and band matrix notation. Set -
d+i g:
Then there exists a diagonal completion R+ of R for which
Proof. The proof is a straightforward application of Corollary 5.11. The definition of -
d and
implies that -
Therefore for each P i , there exists a completion P i (Z i ) which achieves
simultaneously
and
The last inequalities (6.9) translate to d 0
d and d 00
d; which repeated over all i implies that
d: The former inequalities (6.8) prove the rest of (6.7).
We observe that Inequalities (??) combine to form a propagation condition: Lemma 6.6 shows
that these inequalities may be transferred from a staircase matrix to a diagonal completion. Repeating
Lemma 6.6 untill R is fully completed, we get:
Theorem 6.7 (Incremental bounds on inertia growth) Given an s-step hermitian staircase
matrix R (together with the notation of Subsection 6.1) then there exists a hermitian completion F
of R whose inertia (p; n; d) satisfies
Corollary 6.8 Given a hermitian staircase matrix R (together with the notation of Subsection
6.1). Suppose there is an integer t such that
then there exists a hermitian completion F of R such that
st st
Proof. The hypotheses and (5.3) provide: rank C
d i are integers, this inequality becomes -
t. In this way, one
sees that t - maxf -
and the theorem is applicable.
The case is of particular interest:
Corollary 6.9 Given a hermitian staircase matrix R (together with the notation of Subsection
6.1). Suppose that
then there exists an inertia preserving hermitian completion F of R .
That Theorem 6.7 is best possible without additional hypotheses is demonstrated by the next
example:
Example 6.10 Consider the matrix
I
where U is an
strictly upper triangular matrix. We consider R(U) as a partial s-step band matrix, in which U is
unspecified. In the notation of Theorem 6.7, all -
Thus, by this theorem,
we expect to find a completion with
However, since det hence (6.10) can only be satisfied with
equality. In fact, using the extended Poincar'e inequalities, we see that every completion R(U)
satisfies (6.10) with equality.
6.5. Proof of Theorem 1.2. - a staircase of invertible maximal
hermitian submatrices
Throughout this subsection we shall assume that R is an s-step staircase partial matrix with all
maximal submatrices R i invertible. In this case, all inertias compatible with Poincares Inequalities
are achievable with a hermitian completion.
First we present the minimal-rank inertia-preserving case as the next lemma.
Lemma 6.11 (An inertia preserving lemma) Given an s-step staircase hermitian matrix R
(together with the notation of Subsection 6.1). Suppose that each of the maximal submatrices
s of R is an invertible matrix. Then there is a hermitian completion F of R such
that
and such that
Ker F contains Ker R 1 +Ker R 2
Proof. We use Corollary 5.13 s times as we construct an inertia preserving diagonal completion
R+ of R. Then R+ will satisfy the hypotheses of Corollary 6.4, which will produce the desired
hermitian completion F with -(F
Proof of Theorem 1.2. We will use Corollary 5.8 repeatedly to construct successive diagonal
completions with invertible maximal matrices and increasing inertias.
Construction of the (first) diagonal completion (R+ ).
Case 1. If the size of P then Corollary 5.8 is used to choose a matrix Z i such that
is an invertible matrix with
Case 2. If the size of P then Corollary 5.8 is used to choose a matrix Z i such that
In
Depending only on its size, P i (Z i ) may be an invertible or a non-invertible matrix.
In both cases, the new fC+i g are the previous maximal submatrices, fR i g, and hence all the
new fC+i g of R+ are invertible matrices.
If Case 2 occurred, at least once, then the desired positivity and negativity has been achieved.
Then Corollary 6.4 applied to R+ will provide the desired full completion F , with In
If no Case 2 has occured, only Case 1, then all the maximal submatrices of R+ are invertible.
In this manner, one constructs a number of successive diagonal completions until Case 2 is
used. With each successive diagonal completion, the values of the positivity and negativity grow.
At some point, at least one of the new -(R i ) and one of the new -(R j ) (for the latest successive
diagonal completion reach the desired values p and n . Then
This will occur when Case 2 is used, possibly sooner. With the possible
exception of the current diagonal completion, all the maximal specified submatrices of the various
successive diagonal completions were invertible (since only Case 1 was used). Therefore all the
C i of the current diagonal completion were the invertible maximal submatrices of the previous
diagonal completion. Therefore Corollary 6.4 is applicable and it completes the proof.



--R

Positive definite matrices with a given sparsity pattern.
On the eigenvalues of matrices with given upper triangular part
Determinantal formulae for matrix completions associated with chordal graphs.
The inertia of a Hermitian matrix having prescribed diagonal blocks.
Maximal rank Hermitian completions of partially specified Hermitian matrices.
Minimal signature in lifting of operators I
Minimal signature in lifting of operators II
The negative signature of some Hermitian matrices
Ranks of completions of partial matrices.

The possible inertias for a Hermitian matrix and its principal submatrices.
On the inertias of symmetric matrices and bounded self-adjoint operators

Several consequences of an inertia theorem.
Positive semidefinite completions of partial Hermitian matrices.
Choosing the inertias for completions of certain partially specified matrices
Ranks and Inertias of Hermitian Toeplitz matrices Report
Extensions of band matrices with band inverses.
maximum entropy and the permanence principle.
Invertible self adjoint extensions of band matrices and their entropy.

Completing Hermitian partial matrices with minimal negative signature.

Determination of the ii
On the inertia of some classes of partitioned matrices.
Matrix Analysis I

Inertia possibilities for completions of partial Hermitian matrices.
Chordal inheritance principles and positive definite completions of partial matrices over function rings
chordal graphs and matrix completions.
On the matrix equation AX

--TR
matrices;minimal rank;inertia;hermitian;completion