PaperlayerView exact revision on arXiv

Source-linked AI summary

Conditioning of solutions to the Sylvester equation

Massimiliano Fasi, Behnam Hashemi

arXiv:2609.04050v1math.NAcs.NA

TL;DR

Backward-error analysis of Sylvester and Lyapunov solvers motivates the question of when their solutions are well-conditioned. The paper derives bounds for solution conditioning, including Zolotarev-number lower bounds and bounds using matrix-exponential integral representations. It shows that well-conditioned inputs and a well-conditioned Kronecker matrix do not preclude an arbitrarily ill-conditioned Sylvester solution.

  • Problem

    The paper addresses when Sylvester and Lyapunov equation solutions are well-conditioned, a question that matters in backward-stability analysis because a small residual need not imply small backward error.

    Source: §1 · pp. 1–2

  • Method

    The paper derives bounds on solution conditioning, including Zolotarev-number lower bounds and bounds based on integral representations involving matrix exponentials.

    Source: §6.1 · pp. 13–14, §7 · p. 15

  • Results

    The Sylvester solution can be arbitrarily ill-conditioned even when the equation’s inputs and Kronecker matrix are well-conditioned, and lower bounds can grow exponentially with the gap between solution rank and displacement rank.

    Source: §1 · p. 3, §6.1 · p. 14

  • Takeaways & Limitations

    Solution conditioning depends on how the right-hand side interacts with operator singular directions, not only on spectral separation.

    Source: §1 · p. 3

    Sharp estimates may require all eigenvectors of A and direct work with the transformed solution, making them more naturally a posteriori than a priori.

    Source: §8 · p. 18

Abstract

from arXiv · show

We partially answer an open problem, posed by Nick Higham, concerning the conditioning of solutions to Sylvester and Lyapunov equations. The question arises in the backward stability analysis of numerical algorithms for these equations. We first show that the solution to the Sylvester equation $AX-XB = C$ can be arbitrarily ill-conditioned even if $A, B, C$ and the Kronecker sum $I \otimes A - B^T \otimes I$ are all perfectly conditioned. We then derive general a priori bounds on the condition number of the solution, as well as bounds for the Sylvester equation when $A$ and $B$ are diagonalizable. We also provide lower bounds involving matrix exponentials and Zolotarev numbers. For the Lyapunov equation $AX+XA^T = -C$, we obtain upper bounds in two settings: (i) when $A$ is symmetric positive definite while $C$ is symmetric negative definite, and (ii) when $A$ is strictly dissipative and $C$ is symmetric positive definite.

1 The Sylvester and Lyapunov equations

The paper studies conditioning of the Sylvester solution itself, motivated by backward-error analysis, and shows that it depends on how C interacts with operator singular directions as well as on spectral separation. It distinguishes this from conditioning the vectorized linear system and from solution sensitivity to perturbations in C.

1 The Sylvester and Lyapunov equations

  • The solution’s conditioning matters in backward-error analysis because a small residual need not imply small backward error, which can be large when the solution is ill-conditioned.This motivates conditions guaranteeing well-conditioned solutions, an open problem identified by Higham [14, p. 311].Source: §1 · p. 2
  • Vectorizing the Sylvester equation gives an equivalent linear system whose spectral condition number upper-bounds, but generally differs from, the structured condition number of the equation.Related structured condition numbers are developed by Ghavimi and Laub.Source: §1 · p. 2
  • The separation measures solution sensitivity to perturbations in C when A and B are fixed, rather than conditioning of X itself.The paper describes its focus as distinct from this operator sensitivity.Source: §1 · p. 3
  • The paper focuses on conditioning of X itself, which depends on spectral separation and on how C interacts with singular directions of the operator A.The authors identify settings guaranteeing well-conditioned solutions and show that X can be ill-conditioned even when A is well-conditioned.Source: §1 · p. 3
  • Earlier work largely studied when X is nonsingular, while related backward-error research developed structured perturbation bounds and residuals for Sylvester equations.The cited work includes Luenberger, Hearon, Datta, Higham, and Ghavimi and Laub.Source: §1 · p. 3

2 Preliminaries

The preliminaries introduce logarithmic norms, strict dissipativity, and a 2-norm version of separation for use in later bounds. They also state matrix-norm results with a caveat for rectangular matrices.

2 Preliminaries

  • The stated matrix-norm result’s part (i) need not hold when both matrices are rectangular.The preliminaries also state a separate result for two m × n matrices.Source: §2 · p. 4
  • The logarithmic norm induced by the Euclidean norm is the largest eigenvalue of a matrix’s symmetric part.The matrix exponential satisfies ∥e^(Mt)∥2 ≤ e^(tµ(M)) for t ≥ 0.Source: §2 · p. 4
  • A matrix is strictly dissipative when its symmetric part is negative definite; its symmetric-part eigenvalues then lie in an interval [−γ, −β] for some 0 < β ≤ γ.Every symmetric negative definite matrix is dissipative, but strict dissipativity does not require symmetry.Source: §2 · p. 4
  • The operator sep2 uses the separation definition from (5) with the 2-norm instead of the Frobenius norm..Source: §2 · p. 4

3 Simpler special cases

When B is zero, the solution’s conditioning is controlled by the conditioning of A and C. The section contrasts this special case with examples where ill-conditioned inputs lead to ill-conditioned solutions.

3 Simpler special cases

  • When B = 0, well-conditioned A and C ensure a well-conditioned solution X, while an ill-conditioned A or C can make X ill-conditioned.The section derives bounds for X and, when X is invertible, for X inverse.Source: §3 · p. 5
  • With A = I and C equal to the ill-conditioned Hilbert matrix, X = C is ill-conditioned; with C = I and A the Hilbert matrix, X = A inverse is ill-conditioned..Source: §3 · p. 5
  • The section also considers the corresponding equation XB = C and its solution.The stated solution is X = A inverse C for the left-multiplication case, including matrix inversion.Source: §3 · p. 5

4 General case

The general Sylvester equation can have an arbitrarily ill-conditioned solution even when its inputs and Kronecker matrix are well-conditioned. The section contrasts this with general bounds and bounds specialized to Lyapunov settings.

4 General case

  • κ2(X) = ε^-1 tends to infinity as ε approaches zero, although κ2(A) = κ2(B) = 1, κ2(C) ≤ 2, and the Kronecker matrix has κ2 = 3.The equation has a unique solution for any C because the eigenvalues of A and B are ±1 and ±2, respectively.Source: §4 · p. 6
  • The same ill-conditioning phenomenon occurs for the Lyapunov equation, with the cited example reporting κ2(A) ≈ 2.6, κ2(X) ≈ 5.7, and κ2(C) < 5.9 near ε = 0..Source: §4 · p. 6
  • In both examples, A, B, and C are indefinite..Source: §4 · p. 6
  • General bounds apply broadly but can be loose; the paper therefore also derives bounds for specific problem classes, including sufficient conditions for Lyapunov bounds resembling (13)..Source: §4 · p. 6

5 General a priori bounds on the condition number

The section develops a priori condition-number bounds by relating norms of the solution and its pseudoinverse. It also identifies limits of the bounds and shows how spectral conditioning can control Frobenius conditioning.

5 General a priori bounds on the condition number

  • Example 1 rules out a nontrivial upper bound depending only on A, B, and C, while bound (25) is never stronger than κ2(A) ≥ 1.The section notes that sharper lower bounds can instead use spectral norms of A and B.Source: §5 · pp. 7, 9
  • Any upper bound on κ2(X) yields an upper bound on κF(X), and the section's bound is tighter than κF(X) ≤ nκ2(X).The comparison follows from the section's norm inequalities.Source: §5 · p. 7
  • A Frobenius-norm lower bound is derived using pseudoinverse norm relations, including ||X+||2 = 1/σmin(X) when X has full column rank.The section combines these relations to obtain lower bounds on the solution's condition number.Source: §5 · pp. 6, 8, 9
  • The section gives a spectral-norm upper bound on ||X||2 in terms of ||C||2 and separation quantities involving the smallest singular values of A and B and their spectral norms.One bound requires σmin(B) > ||A||2 so its denominator is positive.Source: §5 · p. 9

6 Bounds for diagonalizable matrices

For diagonalizable coefficient matrices, the solution can be represented through a Hadamard product involving transformed data and a Cauchy matrix, yielding condition-number bounds. The section also gives Zolotarev-based lower bounds and Lyapunov conditioning results under specified matrix assumptions.

6 Bounds for diagonalizable matrices

  • For diagonalizable A and B with disjoint spectra, X is reconstructed from the Hadamard product of transformed C and a Cauchy matrix; its condition number is bounded using the eigenvector matrices.If A and B are normal, X and the Hadamard product have identical extreme singular values and condition numbers.Source: §6 · pp. 10–11
  • When A is symmetric positive definite and C is symmetric negative definite, the Lyapunov solution is symmetric positive definite, and well-conditioned A and C suffice for a well-conditioned solution.The condition is sufficient, not necessary; the cited discussion notes well-conditioned solutions can occur when A and C are moderately ill-conditioned.Source: §6 · pp. 11–12

6.1 Lower bounds in terms of Zolotarev numbers

  • For normal A and B, Zolotarev numbers yield lower bounds on κ2(X) from the spectra and the rank and displacement-rank parameters.The bounds can be trivial when r ≤ ν; in the three special cases, they grow exponentially with ℓ between the rank r and displacement rank ν, making X unavoidably ill-conditioned when r is moderately large relative to ν.Source: §6.1 · pp. 12, 14
  • For real symmetric spectral intervals, the lower-bound strength depends on the ratio λ = b/a, not just on the intervals being disjoint.For the other stated configurations, the section gives bounds involving the spectra’s cross-ratio or the radii of nested disks.Source: §6.1 · pp. 13–14
  • The Zolotarev lower bounds also extend to diagonalizable, potentially nonnormal A and B by transforming the equation to normal diagonal coefficients while preserving displacement rank.The resulting bounds can be combined with the diagonalizable-matrix condition-number bound.Source: §6.1 · p. 14

7 Bounds using integral representation

This section uses the integral representation of the Lyapunov solution to derive conditioning bounds. For symmetric positive definite C and strictly dissipative A, logarithmic-norm bounds on matrix exponentials and Loewner-order comparisons bound the solution’s extreme singular values.

7 Bounds using integral representation

  • The solution has the integral representation X = ∫_0^∞ e^tA C e^tA^T dt for stable A and symmetric positive definite C.Under these conditions it is the unique symmetric positive definite solution.Source: §7 · p. 15
  • With ϵ = 10^-10, the integrand norm is 4.9×10^6 at t = 5 and 1.6×10^13 at t = 10, motivating attention to transient growth in matrix exponentials.The passage connects conditions for modest κ(X) with the hump of matrix exponentials.Source: §7 · p. 15
  • For symmetric positive definite C and strictly dissipative A, the Lyapunov solution satisfies upper bounds derived by bounding matrix exponentials with logarithmic norms and carrying those bounds through the integral using Loewner order.Strict dissipativity ensures convergence of the integral representation used for the solution.Source: §7 · p. 17
  • The strict-dissipativity assumption is stronger than Hurwitz stability, so the bounds apply under a narrower condition than stability alone.The section notes an example that is Hurwitz stable but not dissipative for M > 2.Source: §7 · p. 18

8 Experiments

The experiments show that small spectral separation can affect solution conditioning differently depending on how the right-hand side loads the gap. They also illustrate Zolotarev lower bounds tracking solution-condition growth, while a priori bounds may overestimate actual conditioning.

8 Experiments

  • 10,000 Lyapunov tests yielded median κ2(X) = 1.94 × 10^4, with values from 2.97 to 1.47 × 10^12.The examples used 3 × 3 matrices with A symmetric positive definite and C symmetric negative definite; Figure 1 shows the distribution and comparison with the bound.Source: §8 · p. 18, Figure 1 · p. 19
  • Sharper estimates require all eigenvectors and direct work with the transformed solution, making them more naturally a posteriori than a priori.The authors note this cost when discussing sharp estimates.Source: §8 · p. 18
  • Theorem 1's a priori bounds can overestimate actual condition numbers; the largest observed gap is attributed to overestimation from inequalities such as (41).The largest-gap test problem is identified in Table 2.Source: §8 · pp. 18–19, Table 2 · p. 19

8.1 Illustration of the Zolotarev lower bounds

  • For the n = 50 Sylvester example, Zolotarev lower bounds closely track singular-value ratios and ultimately κ2(X).The solution's numerical rank is 16; Figure 2 plots the ratios and corresponding bounds.Source: §8.1 · p. 20, Figure 2 · p. 20
  • Across ten Lyapunov problems with n = 7, 9, 11, …, 25, Zolotarev bounds closely track the growth of κ2(X).The right panel of Figure 2 shows the condition numbers and corresponding lower bounds.Source: Figure 2 · p. 20, §8.1 · p. 21

8.2 When can a small separation lead to an ill-conditioned solution?

  • For the first and second choices of C, κ2(X) is respectively of order δ−2 and δ−1; σmax(X) is unchanged, while the second choice has larger σmin(X).Conditioning depends on how C loads the small spectral gap; X remains well conditioned when C’s (1, 2) entry is zero.Source: §8.2 · p. 21
  • With full normal A and B, whether a small separation contributes to ill-conditioning depends on C's entries in the eigenbases, not its original-basis entries.Both right-hand sides are numerically extremely ill-conditioned, with computed condition numbers 8.7 × 10^18 and 3.3 × 10^18, respectively.Source: §8.2 · p. 23
Loading 2609.04050v1…