Source-linked AI summary
Improved Inclusion-Exclusion Eigenvalue Localization Sets for Matrices and Matrix Polynomials
Ljiljana Cvetkovic, Christina Michailidou, Irena Prodanovic
TL;DR
Existing localization regions can include substantial areas guaranteed to contain no eigenvalues, motivating sharper inclusion-exclusion sets. The paper combines S-SDD and CKV localization across arbitrary nonempty index subsets; its resulting set is generally sharper than previously known sets, and numerical examples show substantial region-size reductions.
Problem
Existing localization regions may contain substantial areas guaranteed to be eigenvalue-free, motivating tighter inclusion-exclusion localization sets.
Source: §1 · p. 2Method
The paper combines S-SDD localization with exclusion regions for arbitrary nonempty index subsets and intersects the resulting sets to define a CKV inclusion-exclusion set.
Source: §7 · p. 21Results
The resulting set is generally sharper than previously known localization sets, and numerical examples demonstrate substantial reductions in localization-region size.
Source: §7 · p. 21Takeaways & Limitations
The authors extend the exclusion-set approach to matrix polynomials, including a result locating infinite eigenvalues in the proposed set.
Source: §6.2 · pp. 15–16For the polynomial case, the stated setup requires a nonzero leading coefficient and a determinant that is not identically zero.
Source: §6 · p. 13
Abstract
from arXiv · showhide
Recent developments have shown that eigenvalue localization regions can often be significantly sharpened by identifying and excluding subsets that are guaranteed to contain no eigenvalues, leading to the concept of inclusion-exclusion localization sets. In this paper, we introduce a new family of inclusion-exclusion eigenvalue localization sets based on the S-strict diagonal dominance framework and the corresponding CKV localization regions. For an arbitrary nonempty subset S of the index set, we construct novel exclusion regions and derive the associated S-SDD inclusion-exclusion localization sets. We prove that every eigenvalue of a complex matrix belongs to the proposed regions and define a refined localization set obtained by intersecting the corresponding inclusion-exclusion regions over all nonempty subsets S. The proposed framework unifies and extends several existing results. In particular, we show that the classical Gershgorin inclusion-exclusion localization set and the Dashnic-Zusmanovich inclusion-exclusion localization set arise naturally as special cases of our construction. Consequently, the new localization set provides, in general, a sharper eigenvalue inclusion region than both of these previously known localization regions. The theory is further extended to matrix polynomials, yielding corresponding inclusion-exclusion localization results for polynomial eigenvalue problems. Several numerical examples illustrate the effectiveness of the proposed approach and demonstrate the improvement achieved over existing localization sets.
1. Introduction
Eigenvalue localization regions can contain substantial areas guaranteed to be eigenvalue-free, motivating inclusion-exclusion methods that sharpen spectral estimates. This paper combines those methods with arbitrary-subset CKV localization to construct a generally sharper family of sets.
1. Introduction
- Localization regions provide information about eigenvalue distributions and support applications including stability analysis, iterative methods, and control theory.Source: §1 · p. 1
- Inclusion-exclusion methods remove subregions guaranteed to contain no eigenvalues, often tightening estimates from the original localization regions.Source: §1 · p. 2
- CKV localization uses arbitrary index subsets S and intersects the corresponding S-localization regions.Source: §1 · p. 2
- The paper combines CKV localization with exclusion regions to construct S-SDD inclusion-exclusion sets for arbitrary subsets S.Source: §1 · p. 2
- Intersecting the proposed regions over all nonempty S yields a set generally sharper than the Gershgorin and Dashnic-Zusmanovich inclusion-exclusion sets.Source: §1 · p. 2
- The paper places its matrix-polynomial results in a context where inclusion and exclusion sets for polynomial spectra had already been studied.Source: §1 · p. 2
2. Preliminaries
The preliminaries establish matrix and index notation, then characterize a CKV set through an intersection-based representation. The following subsection introduces the classical Gershgorin and Dashnic-Zusmanovich inclusion-exclusion sets.
2. Preliminaries
- The preliminaries assume a complex matrix A and use N to denote its index set.Source: §2 · p. 2
2.1. A new characterization of the set CS(A)
- For a nonempty proper S, CS(A) can be represented as an intersection-based construction rather than a union of small Gershgorin disks.Source: §2.1 · p. 5
2.2. Gerˇsgorin and Dashnic-Zusmanovich inclusion-exclusion set
- The subsection presents definitions for the Gershgorin and Dashnic-Zusmanovich inclusion-exclusion localization sets.Source: §2.2 · p. 6
3. S−SDD inclusion-exclusion sets
The section constructs inclusion-exclusion localization sets by excluding selected subsets from CKV regions. It defines the sets for each nonempty index subset and forms a refined set by intersecting across subsets.
3. S−SDD inclusion-exclusion sets
- The section derives new inclusion-exclusion localization sets by excluding certain subsets from the corresponding CKV regions.Source: §3 · p. 6
- For nonempty S, the construction uses the S-specific set when S is proper and Ω(A) when S equals the full index set.Source: §3 · p. 8
- The refined CKV inclusion-exclusion set is formed by intersecting the inclusion-exclusion sets over all possible S.Source: §3 · p. 9
4. Comparisons with existing inclusion-exclusion localization sets
The proposed CKV inclusion-exclusion set recovers the Gershgorin and Dashnic-Zusmanovich sets through particular choices of S. The comparison also notes that Θ(A) is not contained in Ω(A).
4. Comparisons with existing inclusion-exclusion localization sets
- Taking S=N recovers the Gershgorin inclusion-exclusion localization set as a special case.Source: §4 · p. 9
- Intersecting over singleton subsets S={i} recovers the Dashnic-Zusmanovich inclusion-exclusion localization set.Source: §4 · p. 9
- The comparison states that Θ(A) is not contained in Ω(A); Figure 1 identifies Ω(A) in gray/red and Θ(A) in light blue/blue.Source: §4 · p. 10, Figure 1 · p. 10
5. Remarks on plotting ΞS(A) sets
The section derives an equivalent definition of the S-SDD inclusion-exclusion set and distinguishes the classical cases from the general subset setting.
- The paper derives an equivalent definition of ΞS(A) using an equivalent form of the CKV set CS(A).Source: §5 · p. 10
- When S is the full index set, the construction reduces to Gershgorin; when S is a singleton, it reduces to Dashnic-Zusmanovich.The discussion then considers the case where both S and its complement contain at least two indices.Source: §5 · p. 11
- For each i in S, at most one j in S satisfies 2|aij| > rS_i.Source: §5 · p. 11
6. Polynomial case
The paper extends S−SDD inclusion and inclusion-exclusion localization sets to matrix polynomials, with CKV sets covering finite and infinite eigenvalues. It also examines when the resulting inclusion-exclusion set improves boundedness properties.
6. Polynomial case
- The polynomial formulation extends S−SDD sets to P(λ), whose finite eigenvalues satisfy det P(µ)=0 and whose infinite eigenvalue occurs exactly when A_m is singular.The infinite-eigenvalue definition uses the reverse matrix polynomial.Source: §6 · pp. 12–13
6.1. S−SDD inclusion sets
- The polynomial CKV inclusion set C(P(λ)) is an intersection over S and contains finite and infinite eigenvalues; it is contained in the DZ set [6], using C(P(µ))⊆D(P(µ)).Source: §6.1 · pp. 14–15
6.2. S−SDD inclusion-exclusion sets
- The CKV inclusion-exclusion set Ξ(P(λ)), formed by intersecting the S-indexed regions, contains every finite and infinite eigenvalue of P(λ).The proof applies constant-matrix results to P(µ) and uses the reverse matrix polynomial for an infinite eigenvalue.Source: §6.2 · p. 16
6.3. Some geometric properties of the CKV inclusion-exclusion set
- Figures 12 and 13 illustrate the unbounded CKV set of P(λ) and improvement to a bounded corresponding CKV inclusion–exclusion set, while Figures 14 and 15 show the DZ and DZ inclusion–exclusion sets remain unbounded.The set ij(P(λ)) is bounded because 0 ∉ ΞS ij(A2), verifying Proposition 6.4.Source: §6.3 · p. 20
7. Conclusions
The S-SDD inclusion-exclusion framework unifies existing localization sets and yields a generally sharper set by intersecting regions over all nonempty subsets. Numerical examples show substantial reductions in localization-region size, and the theory also covers matrix polynomials.
- Combining CKV localization with exclusion regions extends inclusion-exclusion localization to arbitrary nonempty index subsets.Source: §7 · p. 21
- Intersecting the S-SDD regions gives a generally sharper CKV inclusion-exclusion set, with Gershgorin and Dashnic-Zusmanovich sets as special cases.Source: §7 · p. 21
- For matrix polynomials, the proposed localization regions include all finite and infinite eigenvalues.The extension introduces corresponding S-SDD inclusion and inclusion-exclusion sets and establishes structural properties of their exclusion sets.Source: §7 · p. 21
- Numerical examples show that the proposed approach can substantially reduce localization-region size compared with existing regions.Source: §7 · p. 21