A NOTE ON THE EIGENVALUES OF SADDLE POINT MATRICES
J. LIESEN†
Abstract. Results of Benzi and Simoncini (Numer. Math. 103 (2006), pp. 173–196) on spectral
properties of block 2 ×2 matrices are generalized to the case of a symmetric positive semidefinite
block at the (2,2) position. More precisely, a sufficient condition is derived when a (nonsymmetric)
saddle point matrix of the form [A BT;−B C] with A=AT>0, full rank B, and C=CT≥0, is
diagonalizable and has real and positive eigenvalues.
Key words. saddle point problem, eigenvalues, Stokes problem, normal matrices
AMS subject classifications. 65F15, 65N22, 65F50
1. Introduction. Many applications in science and engineering require solving
large linear algebraic systems in saddle point form; see [1] for an extensive survey. In
such problems, the system matrix often is of the form
A BT
B−C,(1.1)
where A=AT∈Rn×nis positive definite (A > 0), B∈Rm×nhas full rank m, and
C=CT∈Rm×mis positive semidefinite (C≥0). The matrix in (1.1) is congruent to
the block diagonal matrix A0
0S, where S=−(C+BA−1BT) with S=ST<0.
Hence the matrix in (1.1) is indefinite with npositive and mnegative eigenvalues,
which represents a significant challenge for linear solvers such as Krylov subspace
methods.
It has been noted by several authors (see [1, p. 23] for references), that the matrix
A ≡ A BT
−B C ,(1.2)
which is obtained from (1.1) by multiplying the second block row by (−1) is positive
stable, i.e. has only eigenvalues with positive real parts; see, e.g., [1, Theorem 3.6] for a
proof of this statement. What is even more appealing is that, under certain conditions,
the matrix Ais diagonalizable with all its eigenvalues real and positive. This may be
advantageous when solving a linear system with Ausing a Krylov subspace method,
and in addition this gives rise to a three-term recurrence conjugate gradient type
method based on a positive definite inner product. The first instance of this fact has
been observed by Fischer et al. [4], who considered Awith A=ηI > 0, and C= 0.
Recently, the results of [4] have been extended by Benzi and Simoncini [2] to matrices
Awith A=AT>0 and C= 0. The purpose of this note is to generalize these
results to Awith a symmetric positive semidefinite (2,2) block C. This is of interest
in stabilized discretizations of Stokes and generalized Stokes problems; see, e.g. [3,
Chapters 5–6] and [2, Section 4] for examples.
†Institute of Mathematics, Technical University of Berlin, Straße des 17. Juni 136, 10623 Berlin,
Noether-Programm of the Deutsche Forschungsgemeinschaft.
1
2J. LIESEN
2. Main result. Consider a matrix Aas in (1.2) with A=AT>0, Bof full
rank, and C=CT≥0, and define the symmetric matrix
MC(γ)≡A−γI BT
B γI −C,(2.1)
where γis a yet to be specified real scalar. Note that the matrix M0(γ) (i.e. MC(γ)
with C= 0) is equal to the matrix Gdefined in [2, p. 182]. This relation and the
results for M0(γ) in [2] are key ingredients in our derivation below. An elementary
computation shows that
MC(γ)A=ATMC(γ).(2.2)
We will now derive conditions on the blocks A,B, and Cof Aand on γso that
MC(γ) is positive definite. If these conditions are satisfied, then
A=MC(γ)−1ATMC(γ),(2.3)
i.e., Ais similar to its transpose by a symmetric positive definite similarity trans-
formation. From a classical result of Taussky [8, Section 3] it then follows that Ais
similar to a real symmetric matrix. Since Ais known to be positive real, we see that
a positive definite MC(γ) is a sufficient condition for Ato be diagonalizable with all
its eigenvalues real and positive.
First note that MC(γ) is congruent to the block diagonal matrix
A−γI 0
0S,where S= (γI −C)−B(A−γI)−1BT.
Therefore a necessary (but not sufficient) condition in order to make MC(γ) positive
definite is that
λmin(A)> γ > λmax(C).(2.4)
In the following we will restrict our attention to γsatisfying (2.4). In case Aand C
are such that λmax(C)≥λmin(A), which particularly includes the case of singular A,
the approach presented here does not work, and we are unaware of any conditions that
guarantee Abeing diagonalizable with positive real eigenvalues. However, the case
λmin(A)> λmax(C) is of practical interest, particularly in the context of stabilized
discretizations of Stokes or generalized Stokes problems. For example, the stabilized
Stokes coefficient matrix in [3, p. 240] is of the form (1.1) with the (2,2) block given
by −C=−βh2D, where βis a nonnegative stabilization parameter and his the mesh
size (here a uniform mesh is assumed for simplicity). The matrix Dis symmetric
positive semidefinite and has norm 4, giving λmax(C) = 4βh2, which is is a very small
number unless the stabilization parameter βis chosen very large. In particular, for
any symmetric positive definite A,λmin(A)> λmax(C) holds for all β < 1
4h−2λmin(A).
Next, using a standard result on the eigenvalues of symmetric matrices (cf. e.g. [5,
Theorem 8.1.5]),
λmin(MC(γ)) ≥λmin A−γI BT
B γI +λmin 0 0
0−C
=λmin (M0(γ)) −λmax(C).(2.5)
A NOTE ON EIGENVALUES OF SADDLE-POINT MATRICES 3
Hence a sufficient condition so that MC(γ) is positive definite is
λmin (M0(γ)) > λmax(C).(2.6)
To derive properties on A,B,C, and γso that (2.6) holds, we consider the eigenvalue
problem M0(γ) [xT;yT]T=θ[xT;yT]T, or
(i) (A−γI)x+BTy=θx , and (ii)Bx +γy =θy .
If there exists an eigenvalue θwith θ=γ, then θ=γ > λmax(C) since we have
restricted our attention to γsatisfying (2.4). If θ6=γwe can transform equation (ii)
into its equivalent form y= (θ−γ)−1Bx, which, inserted into (i) yields
(A−γI)x+ (θ−γ)−1BTBx =θx .
Note that we must have x6= 0 for if otherwise equation (ii) would yield y= 0, a
contradiction to the fact that [xT, yT]Tis an eigenvector. After multiplying from the
left with xTand some algebraic manipulations we obtain the equation
θ+γ2xTx
xTAx =θ2xTx
xTAx +γ−xTBTBx
xTAx .(2.7)
As in the proof of [2, Corollary 3.2], we can bound the left hand side of (2.7) from
above by θ+γ2/λmin(A), and the right hand side from below by
γ−xTBTBx
xTAx ≥γ−λmax(BA−1BT),
which yields the following lower bound on θ,
θ≥γ−γ2
λmin(A)−λmax(BA−1BT).(2.8)
To maximize the lower bound on θwe set γ=γ∗≡1
2λmin(A). This value of γis also
used in [2], and it is there determined by a slightly different argument in the proof of
Proposition 3.1. With γ=γ∗, (2.8) becomes
θ≥1
4λmin(A)−λmax(BA−1BT).(2.9)
Combining this with (2.6) shows that MC(γ∗) is positive definite when
λmin(A)>4 ( λmax(C) + λmax(BA−1BT) ) .(2.10)
Note that if (2.10) holds, and γ=γ∗, then the necessary condition (2.4) on γis
satisfied. We summarize our discussion in the following theorem.
Proposition 2.1. Consider the matrix Aas in (1.2) with symmetric positive
definite A∈Rn×n,B∈Rm×nof full rank m, and symmetric positive semidefinite
C∈Rm×m, and let γ∗≡1
2λmin(A). If (2.10) holds, then the matrix MC(γ∗)in (2.1)
is positive definite, and Ais diagonalizable with all its eigenvalues real and positive.
This proposition is a generalization of results previously obtained in [4, 2]:
Fischer et al. [4] consider Awith A=ηI > 0 and C= 0. The condition (2.10)
then reads η > 2σmax(B), where σmax(B) denotes the largest singular value of B.
4J. LIESEN
This is precisely the condition derived in [4, pp. 531–532], and the matrix M0(η/2)
in (2.1) is equal to the matrix in [4, Equation (2.3)] multiplied by η/2.
Benzi and Simoncini [2, Section 3] consider Awith A=AT>0 and C= 0.
Their matrix Gin [2, p. 182] is equal to M0(γ) in (2.1), and [2, Proposition 3.1] is
equivalent with Proposition 2.1 above. For the case C=βI ≥0, [2, Corollary 2.6]
shows that if λmin(A)≥3β+ 4λmax(BA−1BT), then Ahas real eigenvalues. The
condition on β=λmax(C) in this special case is a bit weaker than (2.10). Note
however that (2.10) not only implies real eigenvalues but also diagonalizability of A.
In the terminiology of [6] and under the condition (2.10), the matrix Ais normal of
degree one with respect to the symmetric positive definite matrix MC(γ∗). According
to [6, Theorem 3.1], Amust be diagonalizable. If we write the eigendecomposition
as A=WΛW−1, where the eigenvalues and eigenvectors of Aare ordered so that
the same eigenvalues form a single block on the diagonal of Λ, then MC(γ∗) must be
of the form MC(γ∗) = (W DWT)−1, where Dis a symmetric positive definite block
diagonal matrix with block sizes corresponding to those of Λ, cf. [6, Theorem 3.1].
With ˆ
W=WD−1/2,MC(γ∗) = ( ˆ
Wˆ
WT)−1, and thus
κ(MC(γ∗)) = kMC(γ∗)k kMC(γ∗)−1k=κ(ˆ
W)2
(cf. [2, pp. 184–185], where a similar result is derived in a different way, and subse-
quently used to bound the residual norm of a Krylov subspace method applied to the
matrix A). An estimate for these quantities can be found as follows: First, by [5,
Theorem 8.1.5] and [2, Corollary 3.2],
λmax(MC(γ∗)) ≤λmax (M0(γ)) ≈λmax(A),
and second, by (2.5) and (2.9),
λmin(MC(γ∗)) ≥1
2γ∗−(λmax(C) + λmax(BA−1BT)) .
Combining these two inequalities yields
κ(MC(γ∗)) = λmax(MC(γ∗))
λmin(MC(γ∗)) ≈λmax(A)
1
2γ∗−(λmax(C) + λmax(BA−1BT)) .
For C= 0 this result corresponds to the one given in [2, Corollary 3.2].
Since Ais normal of degree one with respect to MC(γ∗), Aadmits an optimal
three-term recurrence for computing Krylov subspace bases that are orthogonal with
respect to the inner product generated by MC(γ∗), hx, yi ≡ yTMC(γ∗)x; see [6] for
details. Therefore, a three-term recurrence conjugate gradient type method based on
this inner product can be constructed. For a practical application of such method a
preconditioner that is symmetric positive definite with respect to this inner product
should be available, and the inner product matrix MC(γ∗) should be well condi-
tioned. While the condition number of MC(γ∗) depends on the conditioning of the
eigenvectors of Aand can be estimated as shown above, the construction of such
preconditioners is an open problem.
Finally, as a simple example we consider the matrix
A=
1 0 0 b0
0 2 0 0b
0 0 3 0 0
−b0 0 2c−c
0−b0−c2c
, b 6= 0 , c ≥0.
A NOTE ON EIGENVALUES OF SADDLE-POINT MATRICES 5
Elementary computations show that
λmin(A) = 1 , λmax(BA−1BT) = b2, λmax(C) = 3c ,
and hence the sufficient condition (2.10) becomes
1>12c+ 4b2.
If we choose b= 1/2, then this condition is not satisfied for any c≥0, and indeed a
MATLAB [7] computation reveals that the matrix Ais not diagonalizable for c= 0,
and has eigenvalues with nonzero imaginary parts for c > 0. On the other hand, if we
choose c= 1/12, then a MATLAB computation shows that Ahas five distinct real
and positive eigenvalues whenever |b| ≤ 0.4056855.
Acknowledgements. Part of this work was done during my visit of Emory
University in April 2006. I thank Michele Benzi for his kind hospitality and for very
helpful discussions and suggestions. I also thank Valeria Simoncini and Petr Tich´y
for their comments.
REFERENCES
[1] M. Benzi, G. H. Golub, and J. Liesen,Numerical solution of saddle point problems, Acta
Numer., 14 (2005), pp. 1–137.
[2] M. Benzi and V. Simoncini,On the eigenvalues of a class of saddle point matrices, Numer.
Math., 103 (2006), pp. 173–196.
[3] H. C. Elman, D. J. Silvester, and A. J. Wathen,Finite elements and fast iterative solvers:
with applications in incompressible fluid dynamics, Numerical Mathematics and Scientific
Computation, Oxford University Press, New York, 2005.
[4] B. Fischer, A. Ramage, D. J. Silvester, and A. J. Wathen,Minimum residual methods for
augmented systems, BIT, 38 (1998), pp. 527–543.
[5] G. H. Golub and C. F. Van Loan,Matrix computations, Johns Hopkins Studies in the Math-
ematical Sciences, Johns Hopkins University Press, Baltimore, MD, third ed., 1996.
[6] J. Liesen and Z. Strakoˇ
s,On optimal short-term recurrences for generating orthogonal Krylov
subspace bases, in preparation, (2006).
[7] MATLAB,The MathWorks Company, Natick, MA. http://www.mathworks.com.
[8] O. Taussky,The role of symmetric matrices in the study of general matrices, Linear Algebra
and Appl., 5 (1972), pp. 147–154.
Loading more pages...