{'fraction_non_alphanumeric': 0.052069137443908925, 'fraction_numerical': 0.016154229682566062, 'mean_word_length': 3.648203939745075, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 53, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Solving singular generalized eigenvalue problems. Part II: projection and augmentation

Generalized eigenvalue problems involving a singular pencil may be very challenging to solve, both with respect to accuracy and efficiency. While Part I presented a rank-completing addition to a singular pencil, we now develop two alternative methods. The first technique is based on a projection onto subspaces with dimension equal to the normal rank of the pencil while the second approach exploits an augmented matrix pencil. The projection approach seems to be the most attractive version for generic singular pencils because of its efficiency, while the augmented pencil approach may be suitable for applications where a linear system with the augmented pencil can be solved efficiently.

1. Introduction. In this paper, which is a sequel to Part I [9], we further study the computation of eigenvalues of singular matrix pencils. Whereas in [9] a method based on a rank-completing perturbation has been introduced (i.e., an update by a pencil of a rank that is precisely sufficient to render the updated pencil regular), we propose in this paper a scheme based on rank projection (i.e., a projection of the pencil onto a subspace of maximal possible size such that the projected pencil is generically regular), as well as an augmentation method, as two alternative techniques.
We briefly recall the context and main results from [9]. Let A − λB be a singular pencil, where A, B are (real or complex) n × m matrices. This means that either m = n, or m = n and det(A − λB) ≡ 0. Then the normal rank of A − λB, which is a crucial quantity for the methods in [9] and in this paper, is given by nrank(A, B) := max ζ∈C rank(A − ζB).
The value λ 0 ∈ C is an eigenvalue of the pencil A − λB when rank(A − λ 0 B) < nrank(A, B), and if rank(B) < nrank(A, B) then λ 0 = ∞ is an eigenvalue of A − λB. Most of this paper focuses on the square case m = n. Some results, such as Theorem 4.5 and Algorithm 1, are also for the nonsquare case, where we can assume n ≥ m without loss of generality because we can always switch to the transpose pencil.
In [9], the predecessor of this paper, we have investigated generic rank-completing perturbations of square singular pencils A − λB, i.e., perturbations of rank k := n − nrank(A, B) that have the form where D A , D B ∈ C k,k are diagonal matrices such that D A − λD B is a regular pencil, U, V ∈ C n,k , and τ ∈ C is nonzero. The name rank-completing perturbation is based on the observation that the rank k of the perturbation pencil U D A V * − λ U D B V * is just large enough to "complete" the normal rank n − k of A − λB to full rank n. Indeed, it turns out that generically with respect to the entries of U and V * the perturbed pencil in (1.1) has full rank and is consequently regular; see [9] and below for details. Rank-completing perturbations have shown to often give excellent results, as seen in [9] as well as subsequent publications (see, e.g., [11]). Still, the following observations may be considered minor disadvantages of the technique of using rank-completing perturbations.
• Computing the updates τ U D A V * and τ U D B V * in (1.1) requires O(kn 2 ) operations as extra work, and potentially leads to a minor loss of accuracy. When k = O(n), as is the case in problems related to systems of bivariate polynomials in Example 7.3, the amount of extra work is O(n 3 ), albeit with a small constant. This means that this amount is of the same order as that for solving the generalized eigenproblem.
• The approach is not parameter-free, in the sense that generic (e.g., random) n × k matrices U and V as well as a parameter τ and k × k (diagonal) matrices D A and D B have to be selected. In contrast, the approach developed in section 4 and subsection 5.1 does not require τ , D A and D B , while the technique in subsection 5.2 avoids any work prior to the solution of the generalized eigenproblem and leaves the matrices A and B intact. • Although a singular pencil has only r < n true eigenvalues (where sometimes even r ≪ n), the method still needs to compute eigenvalues of an n × n pencil together with the right and left eigenvectors. This forms the main computational work of the algorithm and the projection approach in section 4 and subsection 5.1 always works on a smaller pencil of size equal to the normal rank: (n − k) × (n − k). Motivated by these observations, we present two alternative approaches in subsection 5.1 (with its theoretical foundation developed in section 4) and subsection 5.2. These techniques have their own features, resulting in alternative and complementing schemes. The approaches are partly inspired by techniques for constrained eigenvalue problems; see, e.g., the classic work by Golub, Arbenz and coauthors [8,2,1] for symmetric constrained standard and generalized eigenvalue problems. In this paper, the focus is on generalized nonsymmetric constrained eigenproblems (see also [9,Remark 4.8]), with special attention to the singularity of the pencil.
The paper is organized as follows. In section 2 we recall the main results of Part I [9], to ensure that this document is reasonably self-contained, but also to provide a preparation for new results derived in this paper. Several necessary technical results are presented in section 3 before the theory of generic projections of singular pencils to a regular pencil of size equal to the normal rank is developed in section 4. Subsection 5.1 then introduces a projection approach based on the results from the previous section. This method seems attractive for all problems, particularly for those having large k/n ratios (that is, a relatively small normal rank compared to the size of the pencil). As a second alternative method, subsection 5.2 treats a new method based on an augmented pencil, which may be interesting in cases where the ratio k/n is small (i.e., the normal rank is large in comparison to n) and we can solve a (regular) eigenvalue problem with the augmented matrices efficiently. In section 6 we discuss how to extract finite eigenvalues from eigenvalues of the regular part. Some numerical experiments are presented in section 7, followed by section 8, where we discuss the computation of the normal rank and consequences of using an inaccurate normal rank. Finally, conclusions are summarized in section 9.
2. Review of rank-completing perturbations of singular pencils. The following main result from Part I [9,Summary 4.7] (see also [9,Thms. 4.3 and 4.6]) characterizes the dependence of eigenvalues and eigenvectors of the perturbed pencil (1.1) on τ , D A , D B , U , and V * . (For a reminder of the Kronecker canonical form and a specification of the term "generic" we refer to section 3.) Summary 2.1. Let A − λB be an n × n singular pencil of normal rank n − k with left minimal indices n 1 , . . . , n k and right minimal indices m 1 , . . . , m k . Let N = n 1 + · · · + n k and M = m 1 + · · · + m k . Thus, the regular part of A − λB has size r := n − N − M − k. Then, generically with respect to the entries of the matrices U and V * in (1.1), the perturbed pencil (1.1) is regular and its eigenvalues are classified as follows: 1. True eigenvalues: There are r eigenvalues that coincide precisely with the eigenvalues of the original pencil A − λB. The corresponding right eigenvectors x and left eigenvectors y satisfy the orthogonality relations V * x = 0 and U * y = 0. 2. Prescribed eigenvalues: There are k eigenvalues such that the corresponding right eigenvectors x and left eigenvectors y satisfy both V * x = 0 and U * y = 0. These eigenvalues are the k eigenvalues of D A − λD B . 3. Random eigenvalues: These are the remaining N + M (= n − r − k) eigenvalues. They are simple and if µ is such an eigenvalue with the corresponding right eigenvector x and left eigenvector y, then we either have V * x = 0 and U * y = 0, or V * x = 0 and U * y = 0.
Note that the vectors x and y referred to above are eigenvectors of the perturbed pencil. They may be viewed as well-defined eigenvectors of the original pencil with two added orthogonality constraints V * x = 0 and U * y = 0. This agrees with a recent definition of eigenvectors of singular pencils in [6], where eigenvectors are subspaces of certain quotient spaces, as the vectors x and y as above are particular elements of these quotient spaces.
In our three approaches (the rank-completing algorithm from [9] and the new algorithms from subsection 5.1 and subsection 5.2) we first extract the true eigenvalues λ i , i = 1, . . . , r, together with the right and left eigenvectors x i and y i in this former sense, and then we use the values |y * i Bx i | to further separate the true eigenvalues into finite and infinite ones; for details see section 6. In Table 2.1 we provide an overview of the main work for the three approaches: the perturbation method of [9], and the new projection and augmentation schemes of this paper. The numbers of various types of eigenvalues of the different methods are given in Table 2.2. Table 2.1 Main work for an n × n singular pencil with normal rank n − k (and therefore rank-completing dimension k) for each of the three methods: determining the normal rank, the update/projection/augmentation step, and the actual solution of the eigenproblem.
For large n if we can solve the augmented system efficiently Table 2.2 Number of various types of eigenvalues for an n × n singular pencil with normal rank n − k: true (finite n f and infinite n i ), prescribed, and random nr, where n f + n i + nr = n − k.

Method
True λ's Prescribed λ's Random λ's Total Perturbation Example 2.2. We consider a system of two random bivariate polynomials p 1 and p 2 of total degree 10 (e.g., coefficients that follow a normal distribution). The number of (finite) roots is (generically) 100. The determinantal representation from [4] gives 19 × 19 matrices A 1 , B 1 , C 1 and A 2 , B 2 , C 2 with p i (λ, µ) = det(A i + λB i + µC i ) for i = 1, 2. To solve for λ, we define the operator determinants which are of size 361 × 361, with ranks 280 and 198, respectively. The normal rank is also 280, which means that the rank-completing dimension is k = 361 − 280 = 81. Therefore, the perturbed pencil (1.1), modified by a rank-81 perturbation, has 81 prescribed eigenvalues, which we select ourselves by the particular choice of the update pencil (D A , D B ). The perturbed pencil for this type of application has no random eigenvalues (so n r = 0) and all 280 remaining eigenvalues of ( A, B) are true eigenvalues of the original pencil. Of these, 100 are finite true eigenvalues, corresponding to roots of the polynomial system; i.e., n f = 100, n i = 180. The projection method developed in section 4 and subsection 5.1 is more efficient for this example as it computes eigenvalues of a 280 × 280 pencil (missing the k = 81 prescribed eigenvalues), while the rankcompleting method from [9] works with a 361 × 361 pencil. In Example 7.3 we analyze this application in more detail.

Preliminaries.
In this section, we gather some results that will be used in the rest of the paper. This section has a modest overlap with [9], which is necessary to explain and prove the new results of this paper. We start by clarifying the notion of genericity. Let F denote one of the fields C or R. A set A ⊆ F m is called algebraic if it is the set of common zeros of finitely many polynomials in m variables. A set Ω ⊆ F m is called generic if its complement is contained in a proper algebraic set, i.e., an algebraic set that is not F m .
In [9] the following concept of genericity of matrices has been used. There, a set Ω ⊆ C n,k has been called generic if it can be canonically identified with a generic subset of C nk . In this paper, we will use a slightly more general concept which is necessary as sometimes we have to explicitly deal with complex conjugation which is not a complex polynomial map. Therefore, we view a complex number as the real pair of its real and imaginary parts and identify C m canonically with the real vector space R 2m . We thus say that Ω ⊆ C n,k is generic if it can be canonically identified with a generic subset of R 2nk . Clearly, a set Ω ⊆ C n,k that is generic in the sense of [9] is also generic in the new sense, because any polynomial in (say) m complex variables can also be viewed as a polynomial in 2m real variables (or more precisely as a pair of real polynomials in 2m real variables that are obtained by taking the real and imaginary parts of the aforementioned polynomial which still may have complex coefficients). Hence, all results from [9] can also be expressed in terms of the new notion and we will do so without further notice when quoting those results.
If Ω ⊆ C n,k is generic, then so is the set of all matrices from Ω that have full rank. This immediately follows from two basic facts. Firstly, the set of all matrices from C n,k having full rank is a generic set, because an n × k matrix has rank less than ρ := max(n, k) if and only if all ρ × ρ minors (which are polynomials in the entries of the matrix, or, more precisely, in the real and imaginary parts of the entries) are zero. Secondly, the intersection of finitely many generic sets is again a generic set. Therefore, we can always assume in the following that a generic set Ω ⊆ C n,k only consists of matrices having full rank.
Theorem 3.1 (Kronecker canonical form). Let A, B ∈ C n,m . Then there exist nonsingular matrices P ∈ C n,n and Q ∈ C m,m such that where J and N are in Jordan canonical form with N nilpotent. Furthermore, , and m i ≥ 0 for i = 1, . . . , k, and n i ≥ 0 for i = 1, . . . , ℓ.
The pencil R(λ) in (3.1) is called the regular part of A − λB and contains the eigenvalues of A − λB. The pencil S(λ) is called the singular part of A−λB and contains right singular blocks L m1 (λ), . . . , L m k (λ) and left singular blocks L n1 (λ) ⊤ , . . . , L n ℓ (λ) ⊤ , where m 1 , . . . , m k and n 1 , . . . , n ℓ are called the right and left minimal indices of the pencil, respectively. (Note that the values m i = 0 and n i = 0 are explicitly allowed here. In that case the blocks L mi (λ) or L ni (λ) ⊤ correspond to a zero column or row in S(λ), respectively.) We highlight that the regular and singular parts of A − λB are uniquely determined (up to permutation of blocks), but the transformation matrices P and Q are not.
We say that a subspace M is a reducing subspace [19] for The main results of [9] on rank-completing perturbations of the form A − λB + τ U (D A − λD B ) V * of an n × n pencil of normal rank n − k with matrices U, V ∈ C n,k and D A , D B ∈ C k,k are stated to hold "generically with respect to the entries of U and V * " which is equivalent to the existence of a generic set Ω ⊆ C n,k × C k,n such that the corresponding statements hold for all (U, V * ) ∈ Ω. Due to the different notion of genericity in this paper, it is no longer necessary to distinguish between the entries of V and V * , because any polynomial in the real and imaginary parts of the entries of V is also a polynomial in the real and imaginary parts of the entries of V * . Furthermore, it will turn out to be convenient to express this genericity in a slightly different way, and the next lemma justifies that this is indeed possible.
Let Ω ⊆ C n,k × C n,k be a generic set. Then there exists a generic set Ω 2 ⊆ C n,k with the property that for each U ∈ Ω 2 there exists a generic set Ω 3 ⊆ C n,k such that V ∈ Ω 3 implies (U, V ) ∈ Ω.
Proof. By definition, the complement of Ω is contained in the set of common zeros of finitely many polynomials in 4nk real variables. In fact, we may assume without loss of generality, that the complement of Ω is contained in the set of zeros of just one polynomial p by choosing p to be the product of the previous finitely many polynomials. Then for U ∈ C n,k and T ∈ C n,k we have that p(U, T ) = 0 implies (U, T ) ∈ Ω. (Here, p(U, T ) is interpreted as evaluating p in the real and imaginary parts of the entries of U and T .) For the moment, let T ∈ C n,k be fixed such that p : C n,k → C with p(U ) := p(U, T ) is not the zero polynomial. Then the set Ω 2 ⊆ C n,k of all U ∈ C n,k for which p(U ) = 0 is, by definition, a generic set. Now let U ∈ Ω 2 be fixed. Then the set Ω ′ 3 of all T ∈ C n,k for which we have p(U, T ) = 0 is a generic set, because by construction of Ω 2 the polynomial p : T → p(U, T ) is not the zero polynomial. The statement of the lemma now follows by taking Ω 3 ⊆ C n,k to be the set of all V ∈ C n,k satisfying p(V ) = 0 as this implies p(U, V ) = 0.
The following theorem combines the results from [9,Thm. 4.3] and [9,Thm. 4.6], and adapts the notion of genericity as outlined above and with the help of Lemma 3.2.
Theorem 3.3. Let A − λB be an n × n singular pencil of normal rank n − k and let D A , D B ∈ C k,k be such that D A − λD B is regular and all eigenvalues of D A − λD B are distinct from the eigenvalues of A − λB. Then there exists a generic set Ω 2 ⊆ C n,k with the following property: for each U ∈ Ω 2 there exists a generic set Ω 3 ⊆ C n,k such that for all V ∈ Ω 3 the following statements hold: 1) For each τ = 0, there exist nonsingular matrices P τ and Q τ such that where R(λ) is the regular part of the original pencil A − λB, R pre (λ) = D A − λD B , and R ran (λ) is regular and independent of τ . For the remaining items, let τ = 0 be fixed.
2) If λ 0 is an eigenvalue of R(λ) and x and y are corresponding right and left eigenvectors of If λ 0 is an eigenvalue of R pre (λ) and x and y are corresponding right and left eigenvectors of The eigenvalues of R ran (λ) are all simple and distinct from the eigenvalues of R(λ) and R pre (λ).
If λ 0 is an eigenvalue of R ran (λ) and x and y are corresponding right and left eigenvectors of Remark 3.4. It follows from the proof of Theorem 3.3 (which is [9,Thm. 4.6]) that random eigenvalues with corresponding left eigenvectors satisfying U * y = 0 are generated by a perturbation of a singular block L ⊤ ni in the Kronecker canonical form of A − λB that corresponds to a nonzero left minimal index n i , while random eigenvalues with corresponding right eigenvectors satisfying V * x = 0 come from a perturbation of a singular block L mj corresponding to a nonzero right minimal index m j . In particular, the sums N and M of the left minimal indices or right minimal indices, respectively, coincide with the numbers of random eigenvalues of "type U * y = 0" or "type V * x = 0", respectively. Remark 3.5. As a side result of Theorem 3.3 we get from (1.1) also a basis for the minimal reducing subspace M RS (A, B) (see [19]). The basis is composed of all right eigenvectors x that belong either to a prescribed eigenvalue or to a random eigenvalue such that U * y = 0. In other words, if we collect all right eigenvectors x from eigentriplets (λ, x, y) of (1.1) such that U * y = 0, these vectors form a basis for M RS (A, B). In a similar way, all left eigenvectors y from eigentriplets (λ, x, y) of (1.1) such that V * x = 0, form a basis for the left minimal reducing subspace L RS (A, B).
We can show that the set of random eigenvalues from Theorem 3.3 does not depend on the choice of τ , D A or D B . Note that the independency of τ has already been addressed in [9,Thm. 4.6]. Proof. Suppose that µ is a random eigenvalue of (1.1) with a right eigenvector x and a left eigenvector y such that V * x = 0 and U * y = 0. Then clearly (A − µB) x + τ U (D A − µD B )V * x = 0 independently of τ , D A , and D B . Analogously, when V * x = 0 and U * y = 0, then y * (A − µB) + τ y * U (D A − µD B )V * = 0 independently of τ , D A , and D B .
In Theorem 3.3 we have shown that left and right eigenvectors of true eigenvalues of (1.1) are orthogonal to U and V , respectively. By reviewing the proof of [9,Thm. 4.3] the result on orthogonality can be extended to root vectors of true eigenvalues as well, that is, for the case when true eigenvalues are multiple and not semisimple. To show this, we first quote another key result from [9].
Proposition 3.7. [9, Prop. 4.2] Let A − λB be an n × m singular matrix pencil having at least k left minimal indices, and let U ∈ C n,k . Then there exists a generic set Ω 1 ⊆ C n,k such that for each U ∈ Ω 1 there exist nonsingular matrices P , Q such that where R(λ) and S(λ) are the regular and singular part of A − λB, respectively, and P U is partitioned conformably with P (A − λB) Q. [9,Thm. 4.3]] Under the same assumptions as is Theorem 3.3, the following assertions additionally hold for the perturbed pencil (1.1).
Proof. Applying Proposition 3.7, there exist nonsingular matrices P , Q such that where R(λ) and S(λ) are the regular and singular parts of A − λB, respectively, and U and V are partitioned conformably with A − λB. The perturbed pencil (1.1) takes the form . It follows from y i2 = 0 and the nonsingularity of R new (λ 0 ) that y i+1,2 = 0. Consequently, we have y * i U = y * i P −1 P U = 0 for i = 1, . . . , d. To show 1(a), we apply the already proved part 1(b) to the pencil A * − λB * and the perturbation To show 2) we apply the already proved part 1) to the pencil λA − B. We are now in the position to explore new alternatives to the rank-completing perturbation approach.

Projections of singular pencils.
In this section, we will develop the theory that leads to Algorithm 1 in the next section. To this end, consider a given singular pencil A − λB and matrices U , V , D A , D B as in Theorem 3.3. Then choosing matrices U ⊥ and V ⊥ whose columns form bases for the orthogonal complement of the ranges of U and V , respectively, we can build an equivalent pencil A key observation for the development of the new methods is that with respect to (4.1), the perturbed pencil A−λB +τ U (D A −λD B ) V * only differs from the original pencil by an extra term τ (D A −λD B ) in the (1, 1)-block. The following simple result shows that under mild additional assumptions it is possible to extract the true eigenvalues of the pencil A−λB from the pencil U * ⊥ (A−λB)V ⊥ of size (n−k)×(n−k), which ultimately leads to Algorithm 1. Proof. We know from Summary 2.1 and Lemma 3.6 that true eigenvalues of A − λB and random eigenvalues of (1.1) are independent of τ, D A , and D B . Let µ be a true or a random eigenvalue of (1.1). It follows from Summary 2.1 that then the right eigenvector is V ⊥ s for a nonzero s ∈ C n−k or the left eigenvector is U ⊥ t for a nonzero t ∈ C n−k (both statements are true for a true eigenvalue and exactly one of the statements is true for a random eigenvalue). Then (A 22 − µB 22 )s = 0 or t * (A 22 − µB 22 ) = 0, therefore µ is an eigenvalue of A 22 − λB 22 . We know from Summary 2.1 that (1.1) altogether has n − k eigenvalues of type a) and b). By a simple counting argument this gives all eigenvalues of A 22 − λB 22 . Proposition 4.1 suggests to extract the finite eigenvalues of a singular pencil by projection to a regular pencil of smaller size-an approach that is followed up in Algorithm 1 in the next section. However, for a rigorous justification of that algorithm, we have to prove that the projected pencil U * ⊥ (A − λB)V ⊥ is generically regular. The challenge here is that genericity in Theorem 3.3 is expressed in terms of the matrices U and V instead of the matrices W := U ⊥ and Z := V ⊥ , which depend on the choice of U and V although the latter matrices are no longer needed to form the projected pencil.
In what follows, we will develop a justification for Algorithm 1 of the next section. Before we present our main result of this section, we need some technical preparations.
We aim to show that with Ω also Ω ⊥ is generic.
3) The entries of q j (w 1 , . . . , w j ) are polynomials in the real and imaginary parts of the entries of w 1 , . . . , w j ∈ C n for j = 1, . . . , ℓ. These function can easily be recursively constructed using a Gram-Schmidt type orthogonalization without a normalization step. The omission of this step guarantees that the entries of the orthogonalized vectors are polynomials in the real and imaginary parts of the entries of the original vectors w 1 , . . . , w ℓ . Indeed, set q 1 (w 1 ) := w 1 and if q 1 (w 1 ), . . . , q ℓ−1 (w 1 , . . . , w ℓ−1 ) have already been constructed then define where for the ease of notation we have dropped the dependence of q 1 , . . . , q ℓ−1 on w 1 , . . . , w ℓ−1 . The verification of the properties 1)-3) is then straightforward.
Let Ω ⊆ C n,k be a generic set. Then also Ω ⊥ ⊆ C n,n−k is a generic set.
Proof. We take an arbitrary U = [ u 1 . . . u k ] ∈ Ω. By definition the complement of Ω is contained in the set of common zeros of finitely many polynomials in 2nk real variables. Since U ∈ Ω, there exists a polynomial p out of those polynomials such that p( U ) = 0. Furthermore, let q 1 , . . . , q n−k+1 be the functions from Remark 4.3 and define p(w 1 , . . . , w n−k ) = p q n−k+1 (w 1 , . . . , w n−k , u 1 ), . . . , q n−k+1 (w 1 , . . . , w n−k , u k ) . Then it follows from Remark 4.3 that p is a polynomial in the real and imaginary parts of the n(n − k) entries of w 1 , . . . , w n−k . (In fact, it is also a polynomial in the real and imaginary parts of the entries of w 1 , . . . , w n−k , u 1 , . . . , u k , but we regard the entries of u 1 , . . . , u k as constants here.) Furthermore, p is not the zero polynomial. Indeed, let W = [ w 1 . . . w n−k ] ∈ C n,n−k be a matrix with orthonormal columns such that W * U = 0. Then we have q n−k+1 ( w 1 , . . . , w n−k , u i ) = u i for i = 1, . . . , k and consequently that p( w 1 , . . . , w n−k ) = p( u 1 , . . . , u k ) = 0. Now let W = [w 1 . . . w n−k ] be such that p(w 1 , . . . , w n−k ) = 0 and set U := [ q n−k+1 (w 1 , . . . , w n−k , u 1 ) . . . q n−k+1 (w 1 , . . . , w n−k , u k ) ]. Then by construction and by definition of p we have W * U = 0 and U ∈ Ω which implies W ∈ Ω ⊥ . It follows by contraposition that the complement of Ω ⊥ is contained in the set of zeros of p and thus Ω ⊥ is a generic set.
The following theorem is the main theoretical result in the paper and paves the way for the numerical method for singular generalized eigenvalue problems presented in Algorithm 1 in the next section. It also shows that the algorithm will work for rectangular pencils and that the assumption of semisimplicity of eigenvalues in Proposition 4.1 can be dropped.
Theorem 4.5. Let A − λB be a complex n × m matrix pencil having normal rank n − k and assume n ≥ m. Then there exists a generic set Ω ⊆ C n,n−k with the property that for each W ∈ Ω there exists a generic set Ω ′ ⊆ C n,n−k such that for all the following statements hold: where R(λ) coincides with the regular part of A − λB and where all eigenvalues of R ran (λ) are simple and distinct from the eigenvalues of R(λ). 2. Let the columns of W ⊥ , Z ⊥ ∈ C n,k form bases of the orthogonal complements of the ranges of W and Z, respectively, and let Z ⊥ ∈ C m,k denote the upper m×k submatrix of Z ⊥ . Furthermore, let λ 0 be an eigenvalue of W * (A−λB)Z with corresponding left eigenvector y and right eigenvector x.
First, we claim that there exists a generic set Ω r ⊆ C n,n−k with the property that for each W ∈ Ω r there exists a generic set Ω ′ r ⊆ C n,n−k such that for all Z ∈ Ω ′ r the pencil W * (A − λB) Z is regular, where Z is the upper m × (n − k) submatrix of Z as in (4.2). To see this, observe that the determinant of W * (A − λB) Z is a polynomial in the real and imaginary parts of the entries of W and Z (and thus also in the entries of W and Z) that is not the zero polynomial, because the pencil A − λB has normal rank n − k which means that there exists a nonzero minor of size n − k. (Choosing W and Z appropriately, this minor can be extracted giving a nonzero value for the determinant of W * (A − λB)Z.) Applying Lemma 3.2 then proves the existence of Ω r and Ω ′ r as above, where the latter set depends on W ∈ Ω r .
In the following, we will frequently work with the extended n × n pencil A − λ B that is obtained from A − λB by just adding n − m zero columns.
Next, let Ω : where Ω 1 and Ω 2 are the generic subsets of C n,k from Proposition 3.7 applied to A − λB and Theorem 3.3 applied to A − λ B. Then Ω is generic. Let W ∈ Ω be fixed. Then there exists a matrix U ∈ Ω 1 ∩ Ω 2 such that W * U = 0. Since in particular U ∈ Ω 1 , there exist nonsingular matrices P ∈ C n,n and Q ∈ C m,m such that where R(λ) and S(λ) are the regular and singular parts of A − λB, respectively, and P U is partitioned conformably with P (A − λB) Q. Setting Q := diag(Q, I k−ℓ ), we then obtain Let R(λ) have the size r × r, i.e., we have U ∈ C n−r,k . Since U and thus also U have full column rank k, there exists a nonsingular matrix T ∈ C n−r,n−r such that with P := diag(I r , T ) · P we have where S 11 (λ) ∈ C n−k−r,n−k−r and P U is partitioned conformably with P (A − λB) Q. Observe that Next, we claim that there exists a generic set Ω 0 ⊆ C n,n−k such that for each Z ∈ Ω 0 the first n − k rows of Q −1 Z are linearly independent. This easily follows since the determinant of this submatrix is a nonzero polynomial in the real and imaginary parts of the entries of Z. (Note that Ω 0 depends on Q and hence on W .) Define Ω ′ : where Ω ′ r and Ω 3 , the generic subset from Theorem 3.3 (applied to the extended pencil A − λ B), depend on W . Then Ω ′ is generic. Let Z ∈ Ω ′ and partition Z as in (4.2), i.e., Observe that due to the special block structure Q = diag(Q, I n−m ), we have Since Ω ′ ⊆ Ω 0 it follows that Z ∈ C n−k,n−k is nonsingular and since Ω ′ ⊆ Ω ⊥ 3 there exists a matrix V ∈ C n,k such that Z * V = 0. We then obtain and R ran (λ) are as in Theorem 3.3. We will now show that R(λ) and R ran (λ) are equivalent by showing that each eigenvalue of R ran (λ) is also an eigenvalue of R(λ). Since all eigenvalues of R ran (λ) are simple and R(λ) has the same size as R ran (λ), it follows that the two pencils are equivalent. Now let λ 0 ∈ C ∪ {∞} be an eigenvalue of R ran (λ) (generically, this eigenvalue will be finite) and let x be a right eigenvector and y be a left eigenvector of A − λ B + τ (U D A V * − λ U D B V * ) associated with λ 0 . It follows from Theorem 3.3 that then either V * x = 0 or U * y = 0 (exactly one of these statements is true) and thus, since the columns of W and Z are bases of the orthogonal complements of the ranges of U and V , respectively, we obtain that either x = Zz for a nonzero z ∈ C n−k or y = W w for a nonzero w ∈ C n−k (again, exactly one of the statements is true). Then either For the proof of 2), first observe that if λ 0 is an eigenvalue of R(λ) and x and y are right and left eigenvectors of the extended pencil A − λ B associated with λ 0 , respectively, then following the same argument as in the paragraph above, it follows from Theorem 3.3 that both x = Zz and y = W w for nonzero vectors z, w ∈ C n−k . In particular, the map x → z is a bijection from the set of right eigenvectors of A − λ B associated with λ 0 to the set of right eigenvectors of W * (A − λB)Z associated with λ 0 . Similar observations hold for the map y → w, and even for the analogous maps in the case that λ 0 is an eigenvalue of R ran (λ), where, of course, the sets of eigenvectors have to be restricted to those eigenvectors satisfying the orthogonality conditions from Theorem 3.3.
Thus, if λ 0 ∈ C is an eigenvalue of W * (A − λB)Z with left eigenvector y and right eigenvector x, then both W y and Zx are left respectively right eigenvectors of A − λ B associated with λ 0 if λ 0 is an eigenvalue of R(λ). This implies If on the other hand λ 0 is an eigenvalue of R ran , then either W y or Zx is a left or right eigenvector of A − λ B, respectively, but not both. First assume, that W y is a left eigenvector of A − λ B associated with λ 0 . Then W * ⊥ (A − λ 0 B)Zx = W * ⊥ ( A − λ 0 B) Zx = 0, because otherwise, keeping in mind that [W W ⊥ ] is nonsingular, we would have ( A − λ 0 B) Zx = 0 implying that Zx is a right eigenvector which is a contradiction. Analogously, we show that y * W * (A − λ 0 B)Z ⊥ = 0 when Zx is a right eigenvector of A − λ B associated with λ 0 . The claim in the case that λ 0 = ∞ is an eigenvalue of W * (A − λB)Z follows in a similar way.

5.
Numerical methods for extracting the eigenvalues of singular pencils. After having established the supporting theory we now present numerical methods that extract the eigenvalues of a given singular matrix pencil.
5.1. First extraction method: projection. Theorem 4.5 justifies the following algorithm that returns the regular eigenvalues λ i of a given singular pencil A − λB for i = 1, . . . , r, where r is the size of the regular part of A − λB. To further extract finite eigenvalues from all eigenvalues of the regular part, we will apply Algorithm 3 from section 6. The latter algorithm will need as an input the reciprocals of the condition numbers of the regular eigenvalues of the corresponding projected regular pencil that we therefore add as an output to the following algorithm. For the theoretical background on the condition numbers we refer to section 6.

2:
Form Z and Z ⊥ by removing the last n − m rows of Z and Z ⊥ , respectively.

3:
Compute the eigenvalues λ i , i = 1, . . . , n − k, and normalized right and left eigenvectors x i and y i of W * (A − λB)Z.
One clear advantage of Algorithm 1 over the perturbation method from [9] is the smaller size of the regular pencil W * (A − λB)Z which is (n − k) × (n − k) instead of n × n. We note that the computation of eigenvalues and left and right eigenvectors of n × n perturbed pencil (1.1), where typically the QZ algorithm is applied, is by far the most expensive step of the method from [9]. The extra work needed to apply the projections with matrices W and Z in Algorithm 1, although it can take O(n 3 ) operations, is in practice negligible and pays off with smaller matrices in Step 3 of Algorithm 1, which is thus usually more efficient even when k is small compared to n.
A strategy that circumvents the need of computing projection matrices is the following. As the set of matrices W , Z for which the statements in Summary 2.1 hold is a generic set, it is likely that it contains all matrices whose columns are the first n − k columns of a permutation matrix. (Indeed, this is expected to be the case with probability one for random singular matrix pencils, but if special pencils from applications are considered, one has to be careful as the selected matrices may happen to be in the complements of the generic sets from Theorem 4.5.) In that case, the matrices [W W ⊥ ] and [ Z Z ⊥ ] can be chosen to be permutation matrices and hence the pencil W * (A − λB)Z from Theorem 4.5 can be obtained by extracting n − k rows and columns from A − λB without any computational cost. Clearly, the columns of Z should consist of vectors from the first m standard basis vectors of C n , otherwise, the corresponding split off matrix Z would contain a zero column.
In the special case n − k = m < n (i.e., the pencil A − λB is of full rank, but nonsquare and thus still singular) the approach above will render the matrix Z ⊥ = 0, because the matrix Z ⊥ necessarily has to consist of the last n−m standard basis vectors of C n . This fits with the observation in Remark 3.4, because in this case, the extended pencil A − λ B only has right minimal indices that are zero and consequently, each random eigenvalue λ 0 of W * (A − λB)Z will satisfy the condition W * ⊥ (A − λ 0 B)Zx = 0, where x is a right eigenvector of W * (A − λB)Z associated with λ 0 .

Second alternative extraction method: augmentation.
We now present a second new alternative approach to the method of [9] via the (n + k) × (n + k) augmented (or bordered) matrix pencil where S A , S B , T A , and T B are k × k diagonal matrices. Observe that this approach can be interpreted as applying a rank-completing perturbation of rank 2k to the (n + k) × (n + k) matrix pencil diag(A, 0) − λ diag(B, 0) of normal rank n − k and hence it is expected that generically the augmented pencil will be regular. However, this does not immediately follow from the results in [9], because of the special block structure of the perturbation pencil. To simplify the presentation, we will not give a rigorous proof analogue to Theorem 4.5 from the previous section. Instead, we present the following result, similar to Proposition 4.1, that motivates Algorithm 2. Proof. For part a), clearly, if µ is an eigenvalue of T A − λT B with an eigenvector e i ∈ C k , then and µ is an eigenvalue of (5.1). In a similar way, if µ is an eigenvalue of S A − λS B with an eigenvector e i ∈ C k , then [ 0 * e * i ] (A a − µB a ) = 0 and µ is an eigenvalue of (5.1). As we assumed that all eigenvalues of T A − λT B and S A − λS B are pairwise distinct, this gives 2k eigenvalues of A a − λB a .
For the cases b) and c) we consider the perturbed pencil (1.1) with the same U and V and with D A = T A S A and D B = T B S B . Then we make use of the fact that by Lemma 3.6 the random eigenvalues of (1.1) are independent of τ, D A , and D B . Thus, if µ is a random eigenvalue of (1.1) then it follows from Summary 2.1 that either the right eigenvector is V ⊥ s for a nonzero s ∈ C n−k or the left eigenvector is U ⊥ t for a nonzero t ∈ C n−k . Then either For c), similarly as in b), we know from Summary 2.1 that µ is a true eigenvalue of A − λB when µ is an eigenvalue of (1.1) with the right and left eigenvector of the form V ⊥ s and U ⊥ t, where s, t ∈ C n−k . It follows that As all eigenvalues in b) are semisimple and all eigenvalues in a) and c) are simple, it follows by a simple counting argument that this gives all eigenvalues of A a − λB a .
From the above proof we can learn how to extract the true eigenvalues of A− λB from the eigenvalues of A a − λB a . Suppose that (θ, x, y) is an eigentriplet of A a − λB a , where x = x 1 x 2 , y = y 1 y 2 are in block form in accordance with (5.1). It is easy to see that θ is a true eigenvalue if and only if x 2 = y 2 = 0. Here we assume that the diagonal matrices T A , T B , S A , S B are chosen in such a way that all prescribed eigenvalues differ from the true eigenvalues of A − λB. We give an overview of the method, based on the augmented pencil (5.1), in Algorithm 2. In practice, this algorithm can be applied to an arbitrary singular pencil, not just to those covered by Proposition 5.1. As for Algorithm 1, to further extract finite eigenvalues from all eigenvalues of the regular part, we apply Algorithm 3 from section 6.

Algorithm 2: Computing regular eigenvalues of a singular pencil A−λB by an augmentation.
Input: A, B ∈ C n,n , k = n − nrank(A, B), threshold δ (default ε 1/2 ). Output: Eigenvalues and reciprocals of the condition numbers of the regular eigenvalues.

1:
Select random n × k matrices U and V with orthonormal columns.

2:
Select diagonal k × k matrices T A , T B , S A , and S B such that the eigenvalues of T A − λT B and S A − λS B are (likely) different from those of A − λB (default: choose diagonal elements uniformly random from the interval [1,2]).
Compared to the approach of (1.1) and Algorithm 1, in Algorithm 2 we have to compute eigenvalues and eigenvectors of a regular pencil of the larger size (n + k) × (n + k). Because of that the other two methods, in particular the rank projection method, are more suitable for dense singular pencils. An advantage of the augmented pencil approach is that it does not change the original matrices A and B. If the matrices are sparse and such that a linear system with the augmented matrix A a − σB a can be solved efficiently, then we can apply a shift-and-invert subspace method, for instance eigs in Matlab, to compute a subset of true eigenvalues close to a target σ.
Remark 5.2. If one is interested only in the finite eigenvalues of the given singular pencil, then instead of (5.1) we can consider a simpler augmented pencil This is equivalent to selecting T A = S A = I k and T B = S B = 0 in line 2 of Algorithm 2. Although this case is not covered by Proposition 5.1, numerical tests suggest that the method still works well. In this case all 2k prescribed eigenvalues are ∞, which makes it harder to separate infinite prescribed eigenvalues from the infinite true eigenvalues, but since we are only interested in finite true eigenvalues, this is not important. On the other hand, it is guaranteed that the prescribed eigenvalues are different from the finite eigenvalues of the given singular pencil.
6. Classification of regular eigenvalues into finite and infinite. Suppose that using Algorithm 1, Algorithm 2, or the algorithm from [9] we have extracted the true eigenvalues of the singular pencil. In the second phase, which is common to all three methods, we extract the finite eigenvalues from the set of identified true eigenvalues. In [9], we have used the values s i = y * i Bx i as a criterion, where y i and x i are normalized left and right eigenvectors, respectively, corresponding to an eigenvalue λ i of the perturbed pencil (1.1). If λ i is a simple eigenvalue, then 1/|s i | appears in the expression for a standard condition number. However, this is a condition number of λ i as an eigenvalue of the regular pencil (1.1), and for different matrices U , V we get different eigenvectors and thus different values of s i for the same eigenvalue.
Since an eigenvalue of a singular pencil can always be perturbed into an arbitrary value using arbitrarily small perturbations it follows that the condition number of that eigenvalue for the original singular matrix pencil is infinite. Therefore, Lotz and Noferini suggest in [12] to consider the so-called δ-weak condition number of eigenvalues for singular pencils and show that it can be approximated by an expression that is given in the following definition. Based on the above definition and also on the fact that a similar approach, supported by strong theoretical results, has recently been used in an algorithm for computing finite eigenvalues of a singular pencil in [11], where full-rank random perturbations are exploited, we opt to use and satisfy x i = y i = 1, V * x i = 0 and U * y i = 0. Since Y * BX 1 = 0 and Y * 1 BX = 0, we get y * i Bx i = αβ * y * Bx and thus γ i = |α| |β| γ(λ i ). Since 0 ≤ |α|, |β| ≤ 1, we always get γ i ≤ γ(λ i ). Numerical results suggest that if the elements of U and V are independent and identically distributed standard normal random variables, then the expected value of |α| |β| behaves as O(1/k) and the computed condition numbers can thus be used as reliable criteria to extract simple finite eigenvalues satisfying γ i = 0. A detailed stochastic analysis is outside the scope of this paper.
In [9], we have used the criterion |y * i Bx i | ≥ δ 2 with a default value of δ 2 = 10 2 ε, where ε is the machine precision (ε = 2.2 · 10 −16 in double precision), to detect finite eigenvalues. The criterion is based on the fact that y * i Bx i = 0 if λ i is a simple eigenvalue. However, singular pencils can also have multiple eigenvalues and for those values y * i Bx i might be 0. In practice, an eigenvalue of algebraic multiplicity m is numerically evaluated as m simple eigenvalues with nonzero values y * i Bx i and because of that [9, Algorithm 1] properly extracts multiple finite eigenvalues in most cases.
To further improve the detection of finite eigenvalues, we propose the heuristic criteria presented in Algorithm 3. As another distinctive value for the recognition we use the relative gap of an eigenvalue, which we define as The main idea is that a computed representative λ i of a multiple finite eigenvalue will have a small γ i but also a small gap i . On the other hand, a (multiple) infinite eigenvalue will usually appear as a finite eigenvalue with γ i very close to zero and a large gap i (close to 1).
Algorithm 3: Extraction of finite eigenvalues from the regular eigenvalues of a singular pencil A − λB.
A brief explanation of the criteria in Algorithm 3 is as follows. If the pencil A − λB has an eigenvalue λ 0 with a Jordan block J d (λ 0 ), where d ≥ 2, then a backward stable numerical algorithm that we apply to (1.1) will typically compute d simple eigenvalues λ This explains the observation that in practice we get a small nonzero value γ i in case of a multiple eigenvalue that is usually large enough so that we recognize the eigenvalue as a finite one. If however, we find an eigenvalue with a value γ i very close to zero and a small value of gap i , then we can deduce that this also represents a multiple eigenvalue.
Rather than setting inclusive criteria for finite eigenvalues, we set two sufficient criteria for infinite eigenvalues and treat the remaining eigenvalues as finite. In line 2, if we have an eigenvalue with a very large gap i and sufficiently small γ i (we use δ 1 = ε 1/2 since we expect that a simple finite eigenvalue will have γ i > δ 1 ), then this indicates an infinite eigenvalue. In line 3, if γ i is very small, this indicates either a finite eigenvalue of large multiplicity or an infinite eigenvalue. A finite eigenvalue will also have small gap i , on the contrary to an infinite eigenvalue. Algorithm 3 usually works well, unless the pencil A − λB has blocks J d and N d in the regular part with a very large size d.

Numerical examples.
In this section we demonstrate the methods with several numerical examples computed in Matlab 2021b. All numerical examples and implementations of the algorithms are available in [16].
A uniform determinantal representation from [4] gives a two-parameter eigenvalue problem of the form (7.3) where p i (λ, µ) = det(A i + λB i + µC i ) for i = 1, 2. There are 9 solutions (λ, µ) and we can compute the λ-parts as eigenvalues of the corresponding singular generalized eigenvalue problem (∆ 1 − λ∆ 0 ) z = 0 of size 25 × 25 that has normal rank 21. Table 7.5 contains the results obtained from Algorithm 1 and Algorithm 3. Compared to [9,Ex. 7.1], where we have solved the same problem with the rank-completing algorithm that requires solutions of a problem of size 25×25, we now use the projection method that leads to a smaller generalized eigenvalue problem of size 21×21. The gap between finite and infinite eigenvalues can clearly be seen. Notice also that all eigenvalues of the projected pencil are true eigenvalues. We show below that this holds for a generic system of polynomials if we use the same uniform determinantal representation. Some properties of singular pencils related to the determinantal representation of bivariate polynomials of total degree d [4] are presented in Table 7.6. The associated singular pencil has size n = (2d − 1) 2 and rank-completion index k = (d − 1) 2 . The perturbed pencil (1.1) therefore has k prescribed eigenvalues. The remaining n − k eigenvalues are all true, i.e., there are no random eigenvalues. Of those n − k eigenvalues, d 2 correspond to roots of the polynomial system, while the remaining true eigenvalues are ∞ and have no meaning for the original problem.
We have for the asymptotic ratio of singularity, for large total degree d, Also, the number of true eigenvalues that are roots of the polynomial system converges to the same ratio: Moreover, we see that, interestingly, nearly 50% of the eigenvalues ( 1 2 (n − 1)) are true infinite eigenvalues, and there are no random eigenvalues in this type of problem. This happens because the KCF of ∆ 1 − λ∆ 0 contains only right singular blocks L 0 and left singular blocks L T 0 (corresponding to the zero rows and columns).
Although the singular pencil ∆ 1 − λ ∆ 0 looks perfect for Algorithm 1, it may happen that the method fails to identify all d 2 true eigenvalues if some of the eigenvalues λ are very ill-conditioned. Also, the infinite eigenvalues appear in large blocks that increase in size with d which makes it difficult to properly identify finite eigenvalues. A possible solution is to use arithmetic in higher precision (for instance by using the Multiprecision Computing Toolbox [17]). The construction that leads from a system of two bivariate polynomials to a singular pencil ∆ 1 − λ∆ 0 can be seen as a type of resultant method. It appears that this approach has the same problems as other resultant methods for finding roots of systems of bivariate polynomials, as explained in [18].
Example 7.4. Given two matrices A and B of size n, in [9,Ex. 6.4] we have shown how to apply the rank-completing method to find values λ such that A + λB has a double eigenvalue. The idea from [14] is to look for independent vectors x and y such that which is a quadratic two-parameter eigenvalue problem. We can linearize (7.4) as a linear two-parameter eigenvalue problem and solve the associated singular eigenvalue problem (∆ 1 −λ∆ 0 )z = 0 of size 3n 2 ×3n 2 ; for details see [9]. The normal rank of this pencil is 3n 2 −n and, contrary to the previous example, infinite eigenvalues, which have multiplicity n 2 , appear in blocks N 1 . Infinite eigenvalues are thus not an issue and the rank-completing algorithm from [9] performs better than the staircase method. Now we will show how to compute the values λ even more efficiently. Generically, if A + λB has a double eigenvalue, it is non-semisimple. If we assume that all double eigenvalues will be non-semisimple, then we can write the problem as a linear two-parameter eigenvalue problem (7.5) The second equation of (7.5) reads (A + λB − µI) z = 0 and (A + λB − µI) y = z, which means that vectors z and y form a Jordan chain for the J 2 (µ) block of matrix A+λB. The problem (7.5) is associated to a singular generalized eigenvalue problem ( The problem has 2n 2 − n as its normal rank, n(n − 1) finite eigenvalues that are solutions we are interested in, and n infinite eigenvalues, again in blocks N 1 . An improvement over (7.4) and [9] is that using Algorithm 1 we have to solve a generalized eigenproblem of size 2n 2 − n, while in [9] we had to solve a generalized eigenproblem of size 3n 2 . This enables us to solve the problem for even larger matrices. For random matrices A and B of size n = 20, the approach from [9] uses initial matrices of size 1200 × 1200 and runs for 6.58s, while the new approach, where we apply Algorithm 1 to 800 × 800 matrices (7.6) and we have to solve a generalized eigenproblem of size 780 × 780, requires just 1.72s. In both cases we found all 380 solutions without any problems. The regular part is well separated from the random eigenvalues and the same applies to the finite and infinite eigenvalues.
8. Normal rank. For both methods presented in this paper as well as for the original rank-updating approach from [9] it is important to correctly determine the normal rank of an n × n singular pencil A − λB. For some applications, for instance for the singular problem related to polynomial systems from Example 7.3 as well as for the double eigenvalue problem in Example 7.4, the normal rank is known in advance and this is not an issue.
If the normal rank is not known in advance, we can determine it by computing rank(A + ηB) for a random value η ∈ C. To increase the probability that the normal rank is accurate, we may repeat the computation several times. Although the computation of rank has complexity O(n 3 ), which is technically the same order as the complexity to compute eigenvalues and right and left eigenvectors of a matrix pencil of the same size, the constant is much smaller, and in practice the computation of the rank is a negligible part of the method. For instance, for two random 1000 × 1000 matrices A and B in Matlab, running rank(A+randn*B) takes 0.06s while [X,D,Y]=eig(A,B) takes 3.45s.
Even with a repeated computation it might happen that we fail to determine the normal rank correctly. In that case it is more likely that the normal rank is underestimated than overestimated, as this may typically happen when η is selected close to an eigenvalue of A − λB. We will show that, fortunately, if the supplied normal rank is an underestimation, we can detect this from the numerical results. The following result from [5] can be applied to the rank-completing algorithm from [9], where nonzero multiplicities in the theorem correspond to sizes of the Jordan blocks in case of a finite eigenvalue or to sizes of the infinite blocks in case of an infinite eigenvalue.
Theorem 8.1. [5,Thm. 4.3] Let λ 0 be an eigenvalue (finite or infinite) of a regular n × n complex matrix pencil A − λB, with nonzero multiplicities 0 < d 1 ≤ · · · ≤ d m . Let 0 < s < m be an integer, and denote by P s the set of all n × n matrix pencils with normal rank at most s. Then there is a generic set G in P s such that for all A 1 − λB 1 ∈ G, the partial multiplicities of the perturbed pencil If we apply the rank-completing algorithm from [9] and underestimate the normal rank, then the value k that we use in the perturbation (1.1) is k = n − nrank(A, B) + s for s > 0. We can apply Theorem 8.1 in a way, that in (1.1) we first update the singular pencil using a perturbation of normal rank n−nrank(A, B) to a regular pencil, for which we can apply the theorem, and then add a perturbation of normal rank s.
Remark 8.2. We observe a behavior similar to Theorem 8.1 when we project an n × n regular pencil A − λB to an (n − s) × (n − s) matrix pencil A − λ B := U * AV − λ U * BV , where U and V are random n × (n − s) matrices with orthonormal columns and s ≥ 1. A brief explanation for the case of a finite eigenvalue is as follows; the case with an infinite eigenvalue is similar.
To show that generically the KCF of A − λ B contains the smallest m − s Jordan blocks, we apply a similar argument as for the geometric multiplicity. We know that for r = 1, . . . , m the KCF of A − λB has exactly dim Ker ((A − λ 0 B) r ) / Ker (A − λ 0 B) r−1 blocks J d (λ 0 ) of size at least r. If we intersect these subspaces with Im(V ), we see that if the KCF of A − λB has m r > s Jordan blocks of size at least r, then the KCF of A − λ B generically has m r − s Jordan blocks of size at least r for r = 1, . . . , m. Therefore, the KCF of A − λ B generically contains the Jordan blocks J d1 (λ 0 ), . . . , J dm−s (λ 0 ).
Suppose that the estimated normal rank is equal to nrank(A, B) − s, where s > 0. In such case it follows from Theorem 8.1 and Remark 8.2 that all three methods generically return only multiple finite eigenvalues with a geometric multiplicity m > s. If λ 0 is an eigenvalue of A − λB with Jordan blocks J d1 (λ 0 ), . . . , J dm (λ 0 ), ordered so that d 1 ≤ · · · ≤ d m , then all three methods return d 1 + · · · + d m−s eigenvalues close to λ 0 . The same applies to ∞ if there are more than s corresponding infinite blocks in the KCF. All remaining eigenvalues are identified to be of the prescribed type, i.e., both α i = 0 and β i = 0, where α i , β i are as defined in Algorithm 1 and Algorithm 2, and α i = V * x i and β i = U * y i for [9, Algorithm 1]. Since we know that there should be no eigenvalues of prescribed type in Algorithm 1, a presence of such eigenvalues clearly indicates that the normal rank was underestimated. We can apply this also to [9,Algorithm 1], where in such case the number of eigenvalues of the prescribed type will exceed n − nrank(A, B). Example 8.3. If we apply Algorithm 1 to the singular pencil from Example 6.2, but use 15 for a normal rank instead of the correct 16, we get the values in Table 8.1. (max(α j , β j )) = 2.9 · 10 −16 ≪ min j=5,...,15 (max(α j , β j )) = 5.7 · 10 −4 .
The presence of eigenvalues of the prescribed type indicates that the estimated normal rank is incorrect. As predicted, the method returned 3 instances of eigenvalue 1 and one infinite eigenvalue, because the regular part of the KCF of A − λB contains the blocks J 1 (1), J 2 (1), J 4 (1), N 1 , and N 2 . If we use the same method with an estimate 14 for the normal rank, the method returns the eigenvalue 1 and 13 prescribed eigenvalues. For an estimate 13 or less for the normal rank, the method does not return any true eigenvalue.
What happens if we overestimate the normal rank? In this case the obtained pencil (perturbed, projected, or augmented) is still singular and we can expect similar problems if we apply for instance the QZ algorithm to the original pencil. In many cases the algorithm still works and the true eigenvalues are among the computed ones, but it is not as reliable as if we use the correct normal rank. In a similar way as we can detect an underestimated rank from the presence of eigenvalues of prescribed type, in the case of an overestimated normal rank we get α i = 0 and β i = 0 for all eigenvalues and they are all identified as true eigenvalues. In the second phase, when we apply Algorithm 3 to extract the finite eigenvalues based on their values of γ i and gap i , all eigenvalues that are not finite true eigenvalues satisfy γ i = 0 and are declared as infinite eigenvalues. To demonstrate this, in the next example we apply Algorithm 1 to the same pencil as in Example 8.3, only this time we overestimate the normal rank.
Example 8.4. If we apply Algorithm 1 to the singular pencil from Example 6.2, but use 17 for a normal rank instead of correct 16, we get the values in Table 8.2. All values α i , β i are smaller than 1.3 · 10 −16 and all eigenvalues are declared to be from the regular part. In this particular example, in the second phase instances of eigenvalue 1 that has multiplicity 7 are correctly identified as finite eigenvalues.
The above examples together with the discussion show that the situation is not without hope if the computed normal rank does not equal the actual normal rank. In the case of an underestimation this can be detected via the presence of eigenvalues of prescribed type, which should not be present. In this case we can repeat the computation of the normal rank or manually increase the estimate. In case of an overestimate, we lose the ability to separate eigenvalues into true and random ones based on values α i and β i , but even in this case it can happen that Algorithm 3 correctly identifies the finite eigenvalues.
9. Conclusions. For the computation of eigenvalues of singular pencils, we have presented two new alternative approaches to the rank-complete perturbation method (1.1) of [9]. Based on theory developed in section 4, we have proposed a projection approach (Algorithm 1 in subsection 5.1), which reduces the dimension of the problem, and may be particularly attractive when the normal rank n − k is small. While the perturbation approach from [9] usually gives very good results already, the projection method seems to be even more attractive due to its smaller size: while the accuracy of the two methods is usually comparable (and excellent), the projection scheme is computationally more efficient (depending on the value of k). Compared to methods with perturbations of full rank (such as [11]), our methods need the normal rank of the pencil, but render more accurate results.
In subsection 5.2 we have proposed an augmentation approach (Algorithm 2), which enlarges the dimension of the problem, but does not require any computations prior to the solution of the generalized eigenproblem and does not change the original matrices A and B. In section 6 we have studied in detail how to extract finite eigenvalues from eigenvalues of the regular part, leading to Algorithm 3.
For all three extraction techniques (perturbation, projection, augmentation), it is relevant to determine a correct value of the normal rank of the pencil. In the total algorithm, this is an inexpensive operation. Since it may occasionally be possible that the computed normal rank is incorrect, we have analyzed detection and repair of this situation in section 8. In addition, for several singular pencils, it is easy to determine the normal rank by inspecting the number of zero columns and rows (provided that the remaining columns and rows are of full rank, which is often obvious from the matrix structure). The polynomial systems of Example 7.3 and the double eigenvalue problem of Example 7.4 are examples of this situation.
A code for the approach developed in this paper is available in [16].