On Existence of Solutions to Structured Lyapunov Inequalities
Aivar Sootla and James Anderson

arXiv:1603.07686v1 [math.OC] 24 Mar 2016

A condensed version of this paper will appear
in the Proceedings of the 2016 American Control Conference

Abstract— In this paper, we derive sufficient conditions
on drift matrices under which block-diagonal solutions to
Lyapunov inequalities exist. The motivation for the problem
comes from a recently proposed basis pursuit algorithm. In
particular, this algorithm can provide approximate solutions to
optimisation programmes with constraints involving Lyapunov
inequalities using linear or second order cone programming.
This algorithm requires an initial feasible point, which we aim
to provide in this paper. Our existence conditions are based
on the so-called H matrices. We also establish a link between
H matrices and an application of a small gain theorem to the
drift matrix. We finally show how to construct these solutions
in some cases without solving the full Lyapunov inequality.

I. I NTRODUCTION
Lyapunov equations and matrix inequalities play a central
role in control theory, since they are used for, e.g., verifying
stability of a dynamical systems, optimal control, and model
order reduction (cf. [2]). Lyapunov matrix inequalities with
sparsity constraints on the decision variables are used in
in the context of distributed control [3], structured model
reduction [4] etc. In such applications, a typical constraint
on the decision variables is block-diagonality of a matrix.
The major bottleneck in solving optimisation programmes
with a Lyapunov inequality constraint is scalability, since it
is a semidefinite programme (SDP). There exist a number of
methods addressing scalability of SDPs (cf. [5], [6], [7]), and
in one of them, it was proposed to replace the constraints in
the cone of positive semidefinite matrices with conic innerapproximations [8], [9]. There are two main conic approximations: one which results in a linear programme (LP), and
another which results in a second order cone programme
(SOCP). Since we are dealing with inner approximations of
the cone of positive semidefinite matrices, even if the LP
or SOCP solution can be computed, this solution is usually
conservative with respect to the optimal SDP solution. This
limitation was partially addressed using the basis pursuit
algorithm [1], which is iterates over LPs or SOCPs and
provides a guarantee of improvement with each iteration.
This algorithm requires an initial feasible point in order
J. Anderson is with St John’s College, Oxford and the Department of
Engineering Science, University of Oxford, Parks Road, Oxford, OX1 3PJ,
U.K. e-mail: james.anderson@eng.ox.acuk
A. Sootla is with the Montefiore Institute, University of Liège, B28, Liège
Belgium, B4000 e-mail: asootla@ulg.ac.be. A. Sootla holds an F.R.S–FNRS
fellowship. This paper is partially funded through the Belgian Network
DYSCO, and the Interuniversity Attraction Poles Programme initiated by
the Belgian Science Policy Office.
The authors would like to thank Prof. Amir Ali Ahmadi for valuable
discussions, and specifically for pointing out the reference [1].

to start the iterations. Hence, major questions still remain
concerning existence theorems and scalable computation of
block-diagonal solutions to Lyapunov inequalities.
Necessary and sufficient conditions for block-diagonal
stability were described more than 20 years ago in [10].
However, these results do not provide a constructive way
to build block-diagonal Lyapunov functions. This perhaps
explains why these results are relatively unused in the control
theory literature. Besides some simple cases, such as, the
drift matrix being block-triangular matrix (cf. [11]), it is
known that the closed loop interconnection of strictly passive
systems has a drift matrix which admits a block-diagonal
solution to Lyapunov inequalities [12]. It is also well-known
that stable Metzler matrices admit diagonal solutions to
the Lyapunov inequality [13]. Additional special cases are
covered in [14], [15] and revisited in what follows.
In this paper, we aim at identifying additional cases, when
a block-diagonal solution to a Lyapunov inequality can be
found using algebraic methods or LPs. We start by studying
a generalisation of Metzler matrices known as H matrices.
Stable H matrices possess many properties of stable Metzler
matrices, for example they also admit diagonal solutions
to Lyapunov inequalities [16]. We provide another such
property, namely we show that for H matrices, diagonal
solutions to Lyapunov inequalities can be computed using
algebraic methods and/or LPs. We then investigate conditions
on specific blocks in block-partitioned matrices. We establish
a link between the H matrix conditions and a version of the
small gain theorem before extending this intuition to blockpartitioned case. In the 2 by 2 block partitioned case, we
provide an explicit way to construct block-diagonal solutions
to the Lyapunov inequalities without the need to solve the
full inequality. An extension to n by n block partitioned case
is one of the future work directions.
The rest of the paper is organised as follows. In Section II,
we cover some preliminaries and motivate our problem formulation in Section III. We show how to construct diagonal
solutions to Lyapunov inequalities for H drift matrices in
Section IV. We provide stability results for block partitioned
matrices and link the condition for H matrices with the small
gain theorem in Section V. In Section VI we provide a largescale numerical example and we conclude in Section VII,
where we discuss linear programming solutions to Lyapunov
inequalities.
Notation: Our notation is mostly standard: ρ(A) stands
for the spectral radius of a matrix A, A ≥ 0 (respectively,

A  0) means that all entries aij of A are nonnegative
(respectively, positive), A  0 (respectively, A  0) means
that A is positive semidefinite (respectively, positive definite).
n
Let S n denote the set of symmetric n by n matrices, S+
denotes the cone of positive semidefinite n by n matrices.
Let kBk2 be the matrix induced norm, that is kBk2 is equal
to the maximum singular value of B, and let σ(B) denote the
minimum singular value of B. The H∞ norm of a transfer
matrix G is defined as kGkH∞ =
max
kG(s)k2 and
s∈C:Re(s)≥0

kGkH∞ = max kG(ω)k2 for stable G. For a space X, its
ω∈R
dual is denoted as X ∗ . Finally, I is the identity matrix of an
appropriate dimension.
II. P RELIMINARIES
Consider the linear time invariant dynamical system
ẋ(t) = Ax(t),

x(0) = x0

(1)

where x(t) ∈ Rn . An important concept associated with the
system (1) is stability, which is typically verified by solving
a linear matrix inequality (LMI).
Proposition 1: System (1) is stable if and only if there
exists an X  0 that satisfies the LMI
AX + XAT ≺ 0.
(2)
A matrix X which satisfies (2) defines a Lyapunov function of the form V (x) = x(t)T X −1 x(t) for system (1). In
this paper, we aim at describing some sufficient conditions
of solvability of the LMI (2) when the decision variable X
satisfies additional sparsity constraints.
In order to simplify the presentation we say that a matrix
A ∈ RN ×N has α = {k1 , . . . , kn }-partitioning with N =
n
P
ki , if the matrix A is written as follows
i=1



A11
 A21

A= .
 ..

A12
A22
..
.

...
...
..
.


A1n
A2n 

.. 
. 

An1

An2

...

Ann

where Aij ∈ Rki ×kj . We say that A is α-diagonal if it is
α-partitioned and Aij = 0 if i 6= j, and α-lower triangular
if Aij = 0 if i < j. We aim at characterising α-diagonally
stable matrices A ∈ RN ×N , which are such that there exists
an α-diagonal positive definite X ∈ RN ×N satisfying (2). If
α = {1, . . . , 1}, we say that an α-diagonal (respectively, αlower triangular, α-diagonally stable) matrix A is diagonal
(respectively, lower-triangular, diagonally stable).
We will make use of so-called scaled diagonally dominant
matrices.
Definition 1: A matrix A ∈ Rn×n is called strictly row
scaled diagonally dominant if there exist positive scalars
d1 , . . . , dn such that
X
di |aii | >
dj |aij |
j6=i

for all i = 1, . . . , n. The matrix A is strictly row diagonally
dominant if di = 1 for all i.

A related class to scaled diagonally dominant matrices is
the class of H matrices. In order to define this class we
require the following definitions:
Definition 2 ([17]): Given an α-partitioned matrix A with
nonsingular Aii for all i, we define the α-comparison matrix
Mα (A) as

−1
kA−1
if i = j,
α
ii k2
Mij (A) =
(3)
−kAij k2 otherwise,
When α = {1, . . . , 1}, we will simply write M(A).
−1
Note that kA−1
= σ(Aii ). Hence using a continuity
ii k2
−1
argument we can assume that kA−1
= 0 for a singuii k2
lar Aii , and Definition 2 is well-posed. The α-partitioned
matrices allow a version of Gershgorin circle theorem:
Proposition 2 ([18]): For an α-partitioned matrix A ∈
n
P
RN ×N , where α = {k1 , . . . , kn } and N =
ki , every
i=1

eigenvalue of A satisfies
k(λI − Aii )−1 k−1
2 ≤

n
X

kAij k2

j=1,j6=i

for at least one i where i = 1, . . . , n.
Definition 3: A matrix A ∈ Rn×n is said to be Metzler if
all the off-diagonal elements are positive.
Definition 4: A matrix A ∈ Rn×n is said to be an H
matrix, if the minimal real part of the eigenvalues of M(A)
is greater than or equal to zero.
It is clear that stable Metzler matrices are also H matrices.
It is also straightforward to show that A is strictly row and
column scaled diagonally dominant if and only if M(A)
has eigenvalues with positive real part [19]. We also refer the
reader to [20], [16] for additional information on H matrices.
Let DD+ denote the cone of matrices A such that A and
AT are strictly diagonally dominant and the elements on
the diagonal of A are positive (that is, Aii > 0). Similarly,
let H+ denote H matrices A with positive elements on the
diagonal of A. If A is a symmetric DD+ matrix, then by
Proposition 2 with α = {1, . . . , 1}, it is easy to show that
A  0. Moreover, the constraint that A = AT ∈ DD+ can
be written as a set of linear constraints
n
X
aii >
cij ∀i,
(4)
j6=i
− cij ≤ aij ≤ cij , and cij = cji ∀i 6= j.
Hence, a constraint A  0 can be replaced by a more
restrictive but scalable linear constraints. This approach
was proposed in [8], [9] to restrict some sum-of-squares
optimisation problems which are naturally SDPs to LPs.
A symmetric H+ matrix is also positive semidefinite, and
this constraint can be imposed by a number of second order
cone constraints [21]. That is A = AT ∈ H+ if and only if
A=

N
X

2
EiT Xi Ei , with X ∈ S+
, Ei ∈ T2

i=1

where E ∈ T2 , if E ∈ Rn×2 and every column of E has
only one non-zero element equal to one, and N = |T2 |.

To summarise the subsection, we will mention this strong
result on diagonal stability of H+ matrices, which we will
revisit in the sequel.
Proposition 3 ([16]): Let −A be an H+ matrix. Then A
is diagonally stable if and only if A is nonsingular.
III. M OTIVATION AND P ROBLEM F ORMULATION
A. Conic Programming

Fig. 1.

Conic optimisation problems take the generic form of optimising a linear functional over the intersection of an affine
subspace and a proper cone. Typically conic programmes
have the following primal and dual formulations:
minimise cT x
s.t.

Ax = b
x∈K

maximise bT y
s.t.

c − AT y = s

Lk+1 = decomp(Xk )

where K is a proper cone (i.e. closed, non-empty, pointed,
convex) and K∗ is the dual cone of K defined as
K∗ := {y | hy, xi ≥ 0, ∀x ∈ K} .
It is well known, that the cone of positive semidefinite
n
n ∗
n
. The
) = S+
is self dual meaning that (S+
matrices S+
cone of symmetric DD+ matrices
KLP = {X ∈ S n ∩ DD+ } ,
n
.
however, is not self-dual and it is larger than the cone S+
More specifically:

∗
KLP
= X ∈ S n viT Xvi ≥ 0, ∀vi ∈ T1 ,

where T1 is the set of all vectors in Rn with a maximum of
two non-zero elements, each of which is ±1. The cone of
symmetric H+ matrices defined as

X=X

has the dual

∗
KSOCP
= X ∈ S n EiT XEi  0, ∀Ei ∈ T2 .
We will make use of these cones and their duals in the
remainder of the paper.
B. Structured Gramians via Basis Pursuit
The standard from primal SDP [22] is written as

s.t X ∈ Sn+ ,

(5)
hAi , Xi = bi ,

where decomp(Xk ) is a Cholesky decomposition of Xk ,
the optimal solution decision variable from iteration k. In
some cases, Xk can have singular values close to zero, thus
creating numerical problems in the iterative procedure. In
order to avoid such cases, we can remove a k-th column of
L with the k-th entry close to zero (we assume that L is lower
triangular). One can also use LDL decomposition to avoid
dealing with negative eigenvalues of Xk . This approach
also slightly improves numerical complexity of the conic
programme by lowering the number of decision variables and
constraints. We finally note that the method relies on the fact
that at the first iteration a feasible solution X0 exists.
In many applications, it is desirable to solve the following
problem using an LP or SOCP rather than the more natural
SDP:
min trace(X)
such that: AX + XAT ≺ 0

KSOCP = {X ∈ S n ∩ H+ } ,

X

Note that Z ∈ K(L) ⇒ Z  0. The algorithm in [1] solves
a sequence of optimization problems of the form (5) but
with the conic constraint replaced by X ∈ K(Lk ) where the
sequence {Lk } is given by
L0 = I

(y, s) ∈ (Rm , K∗ )

min hC, Xi

Block-diagram of the boiler-header system.

i = 1, . . . , m

where Sn+ is the cone of n×n positive semidefinite matrices.
The basis pursuit algorithm proceeds as follows: At each
iteration the algorithm re-parameterizes the simpler cone that
approximates Sn+ and then solves an optimization problem
over this cone, the solution of which is then used to update
the cone for the next iteration. In particular, the algorithm
specifies for a fixed matrix L, the cone

K(L) = X | X = LT QL, Q = QT ∈ DD+ .

T

(6)

is α-diagonal,

where A is Hurwitz, and α is a given partitioning. Note that
since A is Hurwitz, then the condition X  0 is implied
by the solvability of (6). The basis pursuit can be applied
given an X satisfying the constraints of the programme (6).
Therefore, we set up our problem: find X satisfying the
constraints of (6) with algebraic or linear programming
methods.
There are many practical applications, where the problem
of the form (6) appears and one of them is structured model
reduction. For example, consider the boiler-header system
described in [12] and schematically depicted in Figure 1.
The state space can be partitioned according to dimensions
of the subsystems, which are {3, 3, 1}. The system always
admits diagonal generalised Gramians, since the drift matrix
of the closed loop system is a stable H+ matrix.
In order to perform structured model reduction [12] the authors computed a {3, 3, 1}-diagonal generalised controllability Gramian P = diag{P1 , P2 , P3 } such that P1 , P2 ∈ R3×3
and P3 ∈ R. The optimal trace of such a Gramian computed
using semidefinite programming is equal to 1.2817 · 104 .

Using linear programming, we found the minimum trace of
2.4132 · 104 signifying a loss of quality of almost 100%.
After solving one iteration of the basis pursuit algorithm we
obtain objective equal to 1.5893 · 104 , an additional iteration
of the algorithm gives 1.3172 · 104 , and one more provides a
value equal to 1.3093 · 104 , which comes really close to the
optimal value. Naturally, on this example we do not need
basis pursuit or linear programming to obtain an optimal
solution due to the low complexity of the problem. However,
this example indicates that the basis pursuit algorithm can be
beneficial to obtain an approximate solution of large scale
Lyapunov inequalities using linear programmes.
IV. H M ATRICES AND D IAGONAL S TABILITY
The main result of this section concerns diagonal stability
of H matrices, where we sharpen the results from [16] by
providing an explicit diagonal Lyapunov function for a class
of H+ matrices.
Theorem 1: Let −A be an H+ matrix with a nonsingular
M(A). Then the following conditions hold
T
1) There exist positive vectors v = v1 . . . vn ,
T
w = w1 . . . wn
such that M(A)v, wT M(A)
are also positive.
2) There exists a diagonal X such that −(AX + XAT )
is an H+ matrix. Moreover, we can choose it as
X = Pv Pw−1 , where Pv = diag{v1 , . . . , vn }, Pw =
diag{w1 , . . . , wn }, and v, w satisfy point 1).
3) There exists a diagonal positive definite matrix Y such
that
−Pw APw−1 Y − Y Pw−1 AT Pw ∈ DD+
(7)
Proof: 1) By definition −M(A) is a Metzler matrix
with all eigenvalues λi (M(A)) ≤ 0, since M(A) is nonsingular by the premise, −M(A) is a Hurwitz Metzler matrix.
Hence the claim follows by applying the results from [23].
2) Let X = Pv Pw−1 , then
(M(A)X+XM(AT ))w = (M(A)v+XM(A)T w)  0,
where the inequality follows since M(A)v and M(A)T w
are positive and X is nonnegative. Hence S = −M(A)X −
XM(AT ) is a Metzler matrix and there exists a positive
vector such that Sw is negative. This implies that S is a
symmetric Hurwitz and Metzler matrix, which means that
M(A)X + XM(AT ) is positive definite.
Note that aii < 0 for all i, let
(−AX − XAT )ij = −aij xj − aji xi
(
−aij xj − aji xi
(M(A)X + XM(AT ))ij =
−|aij |xj − |aji |xi

or equal to the minimal eigenvalue of M(−AX − XAT ).
This implies that M(−AX − XAT ) has eigenvalues with
positive real part, hence −AX − XAT is an H+ matrix.
3) Consider the matrix R = Pw M(A)Pv , and e the vector
of ones. Now it is easy to see that Re  0:
Pw M(A)Pv e = Pw M(A)v  0.
This implies that the matrix Pw M(A)Pv is row strictly diagonally dominant. Similarly, we can show that Pw M(A)Pv
is column strictly diagonally dominant. This by definition
implies that the matrix −Pw APv is a row and column diagonally dominant matrix with positive elements on the diagonal
or a DD+ matrix. Hence the matrix −Pw APv − Pv AT Pw
is positive definite. Since we can set Y = Pv Pw the result
follows.
We showed that there exists a diagonal X matrix such
that the matrix Z = −Pw APw−1 X − XPw−1 AT Pw is a DD+
matrix and hence positive definite. Note that the constraint
Z = Z T ∈ DD+ is linear and if needed we can relax the
sparsity constraints on X. This implies that given an H drift
matrix, we can compute an α-diagonal Lyapunov function
with an arbitrary α using linear programming.
If the entries of the A matrix are poorly scaled then solving
a linear programme can be numerically challenging. Using
our methods, this can be avoided if we compute an initial
point using the right and left eigenvectors of M(A), instead
of the positive vectors v and w satisfying point 1). Having
an initial point re-scales the optimisation programme and
can provide feasible points as shown on a specific example
in [24].
Theorem 1 is a direct generalisation of the similar result
for Metzer matrices (cf. [23]), but our result can be applied
to a broader class of matrices including lower-triangular
matrices. Using Theorem 1 other results for Metlzer matrices
can be extended to problems such as construction of sumand max-separable Lyapunov functions (cf. [23]).
The state-space transformation Pw is essential in order to
guarantee the diagonal dominance of the inequality. Consider
an asymptotically stable matrix


−1 −2
A=
.
2 −5
and a positive definite X = diag{x1 , x2 }. The matrix −A is
an H+ matrix and it is stable. The diagonal dominance of
AX +XAT requires the following inequalities to be fulfilled
2 · x1 > 2x2 + 2x1 ,

i=j
i 6= j

It is straightforward to show that M(A)X + XM(AT ) ≤
M(−AX − XAT ), moreover the elements on the diagonal are equal. This means that we can write M(A)X +
XM(AT ) = sI − R1 , M(−AX − XAT ) = sI − R2 , where
the matrices R1 and R2 satisfy R1 ≥ R2 ≥ 0. According
to Weilandt’s theorem ρ(R1 ) ≥ ρ(R2 ) (cf. [16]). Therefore
the minimal eigenvalue of M(A)X + XM(AT ) is smaller

2 · 5x2 > 2x2 + 2x1

for some positive x1 , x2 . The first inequality is equivalent
to 0 > 2x2 , which is impossible to fulfil.
V. α-D IAGONAL S TABILITY AND H+ M ATRICES
A. A Motivating Example
In this section, we cover two main classes of results for
diagonal stability and compare them to a classical example
from [14] for cyclic systems. These classes stem from two
arguments based on the passivity and the small gain theorem.
In this section, we will argue that the H+ matrix condition

Fig. 2.

Feedback interconnection of two stable systems G1 , G2 .

is an implicit constraint in these stability proofs. In order to
explain our motivation consider an example studied in [14]
and let:


01×n−1
−β1
A0n =
− diag{α1 , . . . , αn }
diag{β2 , . . . , βn } 0n−1×1
where αi , βi are positive scalars. This matrix represents the
dynamics of a negative feedback of a cascade of transfer
βi
. First, let us consider the 2 by 2
functions Gi (s) = s+α
i
case, which gives


−α1 −β1
A02 =
β2 −α2
β2
β1
and G2 = (s+α
.
and two transfer functions G1 = (s+α
1)
2)
According to the small gain theorem, the system is stable if

β1
s + α1

H∞

β2
s + α2

=
H∞

β1 β2
< 1.
α1 α2

This argument can be extended to an arbitrary size matrix
resulting in the condition
β1 · · · βn
< 1.
(8)
α1 · · · αn
Surprisingly, it is straightforward to verify by definition
that A0n is an H+ matrix if and only if (8) holds. Hence on
this loop the H+ matrix condition is a small gain condition.
Alternatively, using passivity arguments it was shown in [14],
that A0n is asymptotically stable if and only if
β1 · · · βn
< (sec(π/n))n .
(9)
α1 · · · αn
This in particular means that for n = 2 all matrices
in the form A02 are not only stable, but also diagonally
stable, however, they may not be H matrices. This analysis
is based on passivity arguments and has been extended to
less restrictive classes of systems in [15]. It is easy to
verify that with n → ∞ the limit (sec(π/n))n converges
to one. Hence, it appears (for this class of system) that
for large dimensions, H matrices constitute a large subset
of diagonally stable matrices. We will pursue the relation
between H+ matrices and small gain argument in the αdiagonal case in the remainder of the paper.
B. Passivity and Small Gain Conditions for α-Diagonal
Stability
Let Gc be the closed loop transfer function depicted in
Figure 2, which is an interconnection of two Linear Time
Invariant (LTI) subsystems


Ai B i
,
Gi =
Ci Di

where Ai ∈ Rki ×ki , Bi ∈ Rki ×mi , Ci ∈ Rli ×ki , Di ∈
Rli ×mi and m1 = l2 , m2 = l1 . The closed loop transfer
function from [u1 , u2 ] to [y1 , y2 ] has the following statespace realisation

 c
c
c
A11 Ac12 B11
B12
c
c 
 Ac21 Ac22 B21
B22

Gc = 
c
c
c
c ,
 C11
C12 D11 D12
c
c
c
c
C21
C22
D21
D22
where
Ac11 = A1 − B1 R21 D2 C1 ,

Ac12 = −B1 R21 C2

Ac21

Ac22

= B2 R12 C1 ,

(10)

= A2 − B2 R12 D1 C2

and R12 = (I + D1 D2 )−1 , R21 = (I + D2 D1 )−1 and the
rest of the matrices are computed accordingly. For the sake
of simplicity we assume that this realisation is minimal.
Passivity and small gain arguments can both be used to
determine if the closed loop system is stable but we will
focus on the small gain condition. Passivity results in this
direction will be addressed in future work, similar ideas were
pursued in [25], [26].
It is straightforward to verify that stability of the system
with inputs u1 , u2 and outputs y1 , y2 depends on stability
of the transfer function L = (I − G2 G1 )−1 .
Proposition 4 (Small Gain Theorem): Suppose B is a
Banach-algebra and Q ∈ B. If kQk < 1, then (I − Q)−1
exists and
∞
X
(I − Q)−1 =
Qk .
k=0

Applying Proposition 4 we can verify that if Q :=
kG2 G1 kH∞ ≤ kG2 kH∞ kG1 kH∞ < 1 then the function L
and hence the closed loop are stable (cf. [27]). We can
apply the small gain condition to the closed transfer function,
which would result in a condition on α-diagonal stability
of the matrix Ac . However, given only a partitioning α =
{k1 , k2 } and a realisation of the closed loop transfer function
Gc , these conditions again will be hard to verify. We can
apply a small gain theorem in another way, namely apply it
to the matrix Ac directly. In this case, we do not need to
know the realisation of transfer functions G1 , and G2 , all
we need to know is the matrix Ac and the partitioning α.
The conditions on α-diagonal stability of Ac are established
in the following proposition.
Proposition 5: Let Ac be α partitioned with α = {k1 , k2 }
 c

A11 Ac12
c
A =
.
Ac21 Ac22
Let K1 (s) = −(sI −Ac11 )−1 Ac12 , K2 (s) = (sI −Ac22 )−1 Ac21
with Hurwitz Ac11 , Ac22 . If there exists a γ > 0 such that
kK1 kH∞ < 1/γ and kK2 kH∞ < γ, then the matrix Ac is
α-diagonally stable.
Proof: We need to show that there exists an α-diagonal
Lyapunov function for the system ẋc = Ac xc . For the sake
of clarity we drop the superscript c from Acij and simply
write Aij . The inequality kK1 kH∞ < 1/γ and the Bounded

Real Lemma imply that X1  0 solves the Riccati equation
0 = A11 X1 + X1 AT11 + γ 2 X1 X1 + A12 AT12 =
(11)
 2



X
γ
I
0
1
k1
A11 X1 + X1 AT11 + X1 A12
,
0
Ik2
AT12
which has always has a solution since (I, A11 ) is a controllable pair (cf. [2]), since the control matrix is equal to I and
we can control every state independently.
Again, due to the Bounded Real Lemma the inequality
kK2 kH∞ < µ is equivalent to
A22 Y2 + Y2 AT22 + µ−2 Y2 Y2 + A21 AT21 = 0,

(12)

where Y2  0 since (I, A22 ) is a controllable pair (cf. [2]).
Let µ = γ − ε for some ε > 0 such that µ > kK2 kH∞ ,
which implies that µ−2 Y2 Y2  γ −2 Y2 Y2 and consequently:
A22 Y2 +

Y2 AT22

+ Y2 γ

−2

Y2 +

A21 AT21

≺0

By multiplying the equation by γ −2 setting X2 = Y2 γ −2
A22 X2 + X2 AT22 + X2 X2


+

+γ

T

−2

A21 AT21


≺0⇔

γ 2 Ik1
0

A21
(AT22 X2 + X2 A22 )−1 A21
X2

0
Ik2




X2  0

(13)

Combining the inequalities (11) and (13) yields


 AT21
T
X
A
0  A11 X1 + X1 A11 −
1
12
X2


 X1
· (A22 X2 + X2 AT22 )−1 A21 X2
A12
= A11 X1 + X1 AT11 − (X1 AT21 + A12 X2 )
· (X2 A22 + AT22 X2 )−1 (A21 X1 + X2 AT12 ). (14)
Applying the Schur complement properties to (14) yields


A11 X1 + X1 AT11 A12 X2 + X1 AT21
≺ 0,
A21 X1 + X2 AT12 A22 X2 + X2 AT22
thus the blocks on the diagonal are negative definite which
completes the proof.
Our proof is constructive, and shows how to build an αdiagonal Lyapunov function by solving two Riccati equations (11) and (12) instead of solving an LMI. Next we link
a simplified version of these conditions with α-partitioned
and H+ matrices.
C. Conditions for α-Diagonal Stability via H+ Matrices
The authors in [18] showed that A is Hurwitz if it is
an α-partitioned matrix such that Mα (A) ∈ DD+ , and the
matrices Aii are Hurwitz and Metzler for all i. In particular,
this result shows that stability of A is implied by stability of
all the blocks Aii . We provide a generalisation of this result.
Lemma 1: Let A be α-partitioned matrix and Mα (A) be
an H+ matrix. Let also Aii be Hurwitz matrices, and the
Hamiltonian matrices


Aii γi−2 I
Hi =
(15)
−I −ATii

have no purely imaginary eigenvalues with γi = kA−1
ii k2 + ε
for all ε > 0. Then A is a Hurwitz matrix.
Proof: We prove the result by contradiction. Let A have
eigenvalues with a positive real part. Since Mα (A) is an H+
matrix, there exists positive scalars di such that for every i
X
dj
−1
(16)
kA−1
kAij k2 .
ii k2 >
di
i6=j

The matrix A is unstable if and only if D−1 AD is unstable
with D = diag{d1 Ik1 , . . . , dn Ikn }. Let λ be the eigenvalue
of D−1 AD with a positive real part. By Proposition 2 there
exists an index i such that
X
X
dj
dj
Aij
=
kAij k2 .
k(λI − Aii )−1 k−1
2 ≤
di 2
di
i6=j

i6=j

(17)
Now since the Hamiltonian matrix Hi has no purely
imaginary eigenvalues for all ε > 0 and Aii is Hurwitz,
this implies that k(sI − Aii )−1 kH∞ = kA−1
ii k2 . Therefore
the maximum of k(zI − Aii )−1 k2 over z with Re(z) ≥ 0 is
−1
equal to kA−1
k2 ≤ kA−1
ii k2 , and k(λI − Aii )
ii k2 . Hence
due to (16)
X
dj
−1 −1
k(λI − Aii )−1 k−1
kAij k2 .
2 ≥ kAii k2 >
di
i6=j

We arrive at the contradiction with (17), which completes
the proof.
Lemma 1 allows us to determine stability of A by verifying
stability of the blocks Aii subject to the condition (15)
and Mα (A) being an H+ matrix. This, however, does not
directly imply that there exists an α-diagonal Lyapunov
function. In what follows, we only present the result for
α = {k1 , k2 } partitioning.
Theorem 2: Let A be α partitioned with α = {k1 , k2 },
then under the premise of Lemma 1 the matrix A is αdiagonally stable.
Proof: The proof is using the small gain argument for
the systems G1 (s) = (sI − A11 )−1 A12 , G2 (s) = (sI −
A22 )−1 A21 . We have that kG1 kH∞ kG2 kH∞ ≤ ∆ where
∆ := kA21 k2 k(sI − A11 )−1 kH∞ kA12 k2 k(sI − A22 )−1 kH∞ .
Under the premise of Lemma 1 we have that γkA12 k2 <
−1
−1
kA−1
and γ −1 kA21 k2 < kA−1
11 k2
22 k2 . Hence kG1 kH∞ <
−1
γ , while kG2 kH∞ < γ. Proposition 5 proves the claim.
Note that if A is such that Mα (A), Mα (AT ) ∈ DD+ ,
it is not generally true that Mα (A + AT ) ∈ DD+ . This
property holds for α = {1, . . . , 1} and was used in the proof
of Theorem 1. Hence the absence of this property for a
general α is the major obstacle for extending Theorem 1
to the α-diagonal case.
VI. N UMERICAL E XAMPLE
Consider the one-dimensional heat equation in the form
∂ 2 T (t, x)
∂T (t, x)
=α
+ u(x, t)
∂t
∂x2
T (0, t) = T (1, t) = 0,

t≥0

T (x, 0) = 0

x ∈ [0, 1]

x ∈ (0, 1), t > 0

TABLE I
T IME TO COMPUTE THE GENERALISED CONTROLLABILITY G RAMMIAN
Size of the system
SDP solution
SOCP relaxation
LP relaxation
LP relaxation w scaling

50
0.94
0.74
0.01
0.01

100
22.7
4.11
0.02
0.03

150
310.7
11.9
0.05
0.05

200
NA
31.2
0.10
0.10

with α = −0.01, where T (t, x) denotes the temperature at
time t at x. Assume, we want to heat (i.e. apply an input)
at a point of the rod located at 1/3 of its length across, and
observe the temperature at a point on the rod located at 2/3
of its length. Then as in [28], we can obtain the following
spatially discretised model:
Ẋ(t) = AX(t) + Bu(t),

X(0) = 0,

Y (t) = CX(t),
where X(t) ∈ Rn is the temperature
n spatial discretisation points, and

2 −1
−1 2 −1


..
..
A = α(n + 1)2 
.
.


−1

at time t at each of the

..

.
2
−1




 ∈ Rn×n ,

−1
2
(18)

The matrices B ∈ Rn×1 , C ∈ R1×n are equal to zero except
for the entries dn/3e and d2n/3e, respectively, which are
equal to one.
Our goal is to compute the diagonal controllability Gramians P for various n with a minimal trace, which we will do
in the dual form:
max trace(BB T Y ),
Y

s.t. diag{Y A + AT Y + I} = 0
Y ≺ 0.
In the dual form, we have an LP relaxation where −Y
belongs to the dual to the cone of symmetric DD+ matrices,
and an SOCP relaxation, −Y belongs to the dual to the
cone of symmetric H+ matrices. We solve only the dual
SDP formulation and the corresponding relaxation. Due to
the structure of the system, the trace of its Gramians does
not change much with dimensions and we always get the
optimal values in the range between 6.5 to 6.6 for the SDP
programme. Remarkably the results for the SOCP relaxation
are only slightly higher, but in the same range of values. This
however, is due to structure of the system, where the drift
is Metzler and the matrix BB T has only one non-zero entry
on the diagonal. The optimal solutions for the LP relaxation
are in the range between 10.7 − 10.9, hence there is a drop
in quality when using this relaxation.
In Table I, we provide the computational times for various
systems sizes n. The entry “NA” means that the programme
terminated due to running out of memory. Note however,
that we do not take into account the time for parsing the

constraints (that is, we plot only the variable “solvertime” in
Yalmip [29]). Since A is a Metlzer matrix it is straightforward to find a transformation T such that T AT −1 becomes
a diagonally dominant matrix (see Theorem 1). We have
implemented the LP relaxation while transforming the A, B
matrices with such a transformation T . The optimal solutions
for the trace vary between 7.1 and 7.3, thus drastically
improving the quality of the relaxation with a mild loss (if
any) in computational time.
VII. D ISCUSSION AND C ONCLUSION
We have provided some sufficient conditions on A, which
guarantee the existence of feasible points in (6) and interpreted these results as small gain like conditions. Moreover,
our sufficient conditions also provide computationally cheap
solutions, for example Proposition 5 replaces an LMI constraint with two Riccati Equation solutions. If we drop the
“X is α-diagonal” constraint and set Q = AX + XAT , then
the LMI (2) has a solution for any Q ≺ 0 if and only if
λi (A) + λ̄j (A) 6= 0. Since Q is arbitrarily negative definite,
we can replace the constraint AX + XAT ≺ 0 with −AX −
XAT ∈ DD+ . Thus our solvability LMI becomes a linear
program. Finally we showed how our constructive proofs
can be used to initiate a recently developed basis pursuit
algorithm for solving large scale optimization problems.
R EFERENCES
[1] A. A. Ahmadi and G. Hall, “Sum of squares basis pursuit with
linear and second order cone programming,” 2015, to appear in
Contemporary Mathematics.
[2] K. Zhou, J. C. Doyle, and K. Glover, Robust and optimal control.
Prentice Hall New Jersey, 1996, vol. 40.
[3] F. Lin, M. Fardad, and M. R. Jovanović, “Design of optimal sparse
feedback gains via the alternating direction method of multipliers,”
IEEE Trans Automat Control, vol. 58, no. 9, pp. 2426–2431, Sep 2013.
[4] H. Sandberg and R. M. Murray, “Model reduction of interconnected
linear systems,” Optimal control applications & methods, vol. 30,
no. 3, pp. 225–245, 2009.
[5] R. P. Mason and A. Papachristodoulou, “Chordal sparsity, decomposing SDPs and the Lyapunov equation,” in Proc Am Control Conf, 2014,
pp. 531–537.
[6] S. Kim, M. Kojima, M. Mevissen, and M. Yamashita, “Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite
matrix completion,” Mathematical programming, vol. 129, no. 1, pp.
33–68, 2011.
[7] M. Yamashita, K. Fujisawa, and M. Kojima, “SDPARA: Semidefinite
programming algorithm parallel version,” Parallel Computing, vol. 29,
no. 8, pp. 1053–1067, 2003.
[8] A. A. Ahmadi and A. Majumdar, “DSOS and SDSOS optimization:
LP and SOCP-based alternatives to sum of squares optimization,” in
Proc Conf Inform Sci Syst. Princeton University, 2014.
[9] A. Majumdar, A. A. Ahmadi, and R. Tedrake, “Control and verification
of high-dimensional systems with DSOS and SDSOS programming,”
in IEEE Conf Decision Control, 2014, pp. 394–401.
[10] D. Carlson, D. Hershkowitz, and D. Shasha, “Block diagonal semistability factors and lyapunov semistability of block triangular matrices,”
Linear Algebra Appl, vol. 172, pp. 1–25, 1992.
[11] J. Anderson and A. Sootla, “Decentralised H2-norm estimation and
guaranteed error bounds using structured gramians,” in Proc Sym Math
Theory Netw Syst, Groningen, Netherlands, July. 2014.
[12] P. Trnka, C. Sturk, H. Sandberg, V. Havlena, and J. Rehor, “Structured
model order reduction of parallel models in feedback,” IEEE Trans
Control Systems Technology, vol. 21, no. 3, pp. 739–752, 2013.
[13] A. Berman and R. J. Plemmons, Nonnegative Matrices in the Mathematical Sciences. SIAM, 1994, vol. 9.

[14] M. Arcak and E. D. Sontag, “Diagonal stability of a class of cyclic
systems and its connection with the secant criterion,” Automatica,
vol. 42, no. 9, pp. 1531–1537, 2006.
[15] M. Arcak, “Diagonal stability on cactus graphs and application to
network stability analysis,” IEEE Trans Autom Control, vol. 56, no. 12,
pp. 2766–2777, 2011.
[16] D. Hershkowitz and H. Schneider, “Lyapunov diagonal semistability
of real H-matrices,” Linear Algebra Appl, vol. 71, pp. 119–149, 1985.
[17] S.-h. Xiang and Z.-y. You, “Weak block diagonally dominant matrices,
weak block h-matrix and their applications,” Linear Algebra Appl, vol.
282, no. 1, pp. 263–274, 1998.
[18] D. G. Feingold, R. S. Varga, et al., “Block diagonally dominant
matrices and generalizations of the gerschgorin circle theorem,” Pacific
J. Math, vol. 12, no. 4, pp. 1241–1250, 1962.
[19] R. S. Varga, “On recurring theorems on diagonal dominance,” Linear
Algebra Appl, vol. 13, no. 1, pp. 1–9, 1976.
[20] J. Liu and Y. Huang, “Some properties on schur complements of hmatrices and diagonally dominant matrices,” Linear Algebra Appl, vol.
389, pp. 365–380, 2004.
[21] E. G. Boman, D. Chen, O. Parekh, and S. Toledo, “On factor width and
symmetric H-matrices,” Linear Algebra Appl, vol. 405, pp. 239–248,
2005.
[22] S. Boyd, L. Ghaoui, E. Feron, and V. Balakrishnan, Linear matrix
inequalities in system and control theory. SIAM, 1994, vol. 15.
[23] A. Rantzer, “Scalable control of positive systems,” European Journal
of Control, vol. 24, pp. 72–80, 2015.
[24] A. Sootla and J. Anderson, “Structured projection-based
model reduction with application to stochastic biochemical
networks,” Submitted to IEEE Trans. Autom. Control, Oct. 2015,
http://arxiv.org/abs/1510.05784.
[25] C. Sturk, H. Sandberg, P. Trnka, V. Havlena, and J. Rehor, “Structured
model order reduction of boiler-header models,” in Proceedings of the
18th IFAC World Congress, vol. 18, 2011, pp. 3341–3347.
[26] J. Anderson, A. Teixeira, H. Sandberg, and A. Papachristodoulou,
“Dynamical system decomposition using dissipation inequalities,” in
IEEE Conf Decision Control, 2011, pp. 211–216.
[27] H. K. Khalil, Nonlinear systems. Prentice Hall, 2002.
[28] Y. Chahlaoui and P. V. Dooren, “A collection of benchmark examples
for model reduction of linear time invariant dynamical systems,”
Univesité Catholique de Louvain,” SLICOT Working Note 2002-2,
February 2002.
[29] J. Löfberg, “YALMIP: A toolbox for modeling and optimization in
MATLAB,” in Proceedings of the 2004 IEEE International Symposium
on Computer Aided Control Systems Design. IEEE, 2004, pp. 284–
289.

