Vector Spaces of Generalized Linearizations for Rectangular Matrix Polynomials
Biswajit Das Shreemayee Bora









Vector Spaces of Generalized Linearizations for Rectangular Matrix Polynomials
    Biswajit Das 
                 Department of Mathematics,
                Indian Institute of Technology Guwahati,
                Guwahati 781039, Assam, India,
               ()
Shreemayee Bora [1]
    
===========================================================================================================================================================================================================





        The seminal work <cit.> introduced vector spaces of matrix pencils, with the property that almost all the pencils
in the spaces are strong linearizations of a given square regular matrix polynomial. This work was subsequently extended to include the case of square singular
matrix polynomials in <cit.>. We extend this work to non-square matrix polynomials by proposing similar vector spaces of rectangular matrix pencils that are equal to the ones in <cit.> when the polynomial is square. Moreover, the properties of these vector spaces are similar to those in <cit.> for the singular case. In particular, the complete eigenvalue problem associated with the matrix polynomial can be solved by using almost every matrix pencil from these spaces. Further, almost every pencil in these spaces can be `trimmed' to form many smaller pencils that are strong linearizations of the matrix polynomial which readily solve the complete eigenvalue problem for the polynomial. These linearizations are easier to construct and are often smaller than the Fiedler linearizations introduced in <cit.>. Further, the global backward error analysis in <cit.> applied to these linearizations, shows that they provide a wide choice of linearizations with respect to which the complete polynomial eigenvalue problem can be solved in a globally backward stable manner.


AMS subject classification. 15A22, 15A18, 15A03, 15A23, 15A54, 47J10, 65F15, 65F35, 93B1.

0.2cm
Keywords. Rectangular matrix polynomials, generalized linearization, strong generalized linearization, linearization, strong linearization, complete polynomial eigenvalue problem, recovery of minimal indices and bases, backward error analysis.



§ INTRODUCTION
 

Eigenvalue problems associated with matrix polynomials P(λ) = ∑_i=0^kλ^iA_i, where A_i, i = 0, …, k are m × n real or complex matrices, occur in a wide range of applications like vibration analysis of machines, building and vehicles, in control theory and linear systems theory and as approximate solutions of other nonlinear eigenvalue problems <cit.>.

When the polynomial is square and regular, i.e.,  P(λ) ≢0, the associated polynomial eigenvalue problem consists of finding the finite and infinite eigenvalues and corresponding eigenvectors. However when the polynomial is singular, i.e., when it is either non-square or P(λ) ≡ 0, then the eigenvalue problem is said to be a complete eigenvalue problem as in addition to finite and infinite eigenvalues and corresponding elementary divisors, the minimal indices and bases corresponding to the left and right null spaces of the polynomial also have to be computed. The most common approach for solving such problems is to linearize them by converting the problem into an equivalent problem associated with a larger matrix pencil of the form L(λ) = λ X + Y called a linearization of P(λ), and solving the eigenvalue problem for L(λ) by using standard algorithms like the QZ algorithm <cit.> when L(λ) is regular, or the staircase algorithm <cit.> when L(λ) is singular. The solution for P(λ) is then recovered from that of its linearization.  The solution of the complete eigenvalue problem for singular matrix polynomials is more challenging as ideally, there should be a simple rule for extracting left and right minimal bases and indices of the polynomial from those of its linearization. We refer to <cit.> and a more recent survey article <cit.> for the theory of polynomial eigenvalue problems and their solutions.

The most commonly used forms of linearizations for solving polynomial eigenvalue problems associated with P(λ) = ∑_i=0^kλ^iA_i are the first and second Frobenius companion forms C_1(λ) and C_2(λ), given by (<ref>) and (<ref>) respectively. One of the first systematic studies of linearizations  to be undertaken was <cit.> which introduced the following vector spaces Ł_1(P) and Ł_1(P) of matrix pencils for a given n × n regular matrix polynomial P(λ) as sources of linearizations of P(λ).


    𝕃_1(P)    :=   {L(λ):L(λ)(Λ_k(λ)⊗ I_n)=v⊗ P(λ),v∈𝔽^k}, 
    𝕃_2(P)    :=   {L(λ):(Λ_k(λ)^T⊗ I_n)L(λ)=w^T⊗ P(λ),w∈𝔽^k}


    Λ_k(λ) := [λ^k-1,…,λ,1]^T.


The defining identities in (<ref>) and (<ref>) are called the right and left ansatz equations respectively and the corresponding vectors v in (<ref>) and the vector w in (<ref>) are called right and left ansatz vectors.
This work gave a whole new direction to research in the theory of linearizations due to the special properties of these vector spaces. For instance, it was shown that constructing pencils in these spaces corresponding to a given ansatz vector is very simple and almost all the resulting pencils are linearizations of P(λ) from which the eigenvalues and corresponding eigenvectors can be easily recovered. In further work <cit.>, it was shown that if P(λ) has some special structure like, Hermitian, symmetric, ⋆-alternating and ⋆-palindromic, (see <cit.> for definitions), then there exist subspaces of Ł_1(P) and Ł_2(P) with the property that almost every pencil of the subspace is a structure preserving linearization of P(λ) from which both finite and infinite eigenvalues of P(λ) and corresponding eigenvectors can be easily recovered.

It was shown in <cit.> that even when P(λ) is square but singular, almost every pencil in Ł_1(P) and Ł_2(P) is a linearization of P(λ) from which the solution of complete eigenvalue problem for P(λ) can be easily recovered. The vector space setting for constructing linearizations has since been extended to cover other polynomial bases <cit.> and inspired further work that throws fresh light on these spaces <cit.>. Other important choices of linearizations not covered by Ł_1(P) and Ł_2(P) are the Fiedler pencils and their generalizations <cit.> which are also sources of linearizations for non-square matrix polynomials <cit.>. Systematic studies of linearizations that cover both square and non-square linearizations are relatively recent in the literature. For example, <cit.> introduced the framework of block minimal bases pencils as potential linearizations of rectangular matrix polynomials with focus on particular subclasses like the Block Kronecker pencils. These ideas were further extended in <cit.>. Inspired by <cit.>, the recent work <cit.> considers linearizations of rectangular matrix polynomials in a vector space setting. Referred to as Block Kronecker ansatz spaces, these vector spaces contain Block Kronecker linearizations as well as Fiedler linearizations and their extensions modulo permutations and share some of the important properties that Ł_1(P) and Ł_2(P) have when P(λ) is square. However, the Block Kronecker ansatz spaces do not become Ł_1(P) and Ł_2(P) when P(λ) is square.

 The goal of this present work is to provide a direct generalization of the spaces Ł_1(P) and Ł_2(P) to the case when P(λ) is not square by forming vector spaces of matrix pencils that have some of the key features of Ł_1(P) and Ł_2(P) and coincide with them when P(λ) is square. We propose such vector spaces and show that the matrix pencils in these spaces can be constructed from the coefficient matrices of P(λ) in a manner very similar to the ones in Ł_1(P) and Ł_2(P). We also show that the solution of the complete eigenvalue problem for P(λ) can be easily recovered from that of almost every pencil in these spaces. To this end, we define generalized linearizations of matrix polynomials (which we refer to in short as g-linearizations), and their strong versions and show that the proposed vector spaces have all the properties with respect to being g-linearizations that Ł_1(P) and Ł_2(P) are shown to possess with respect to being linearizations of square singular polynomials in <cit.>.

 Although the pencils in our proposed vector spaces are not linearizations of the non-square polynomial P(λ) in the conventional sense, we show that almost every such pencil in these spaces can give rise to many linearizations of P(λ) from which the finite and infinite eigenvalues and corresponding elementary divisors as well as left and right minimal indices and bases of P(λ) can be easily extracted. We also give the relationship between these linearizations and those in some of the Block Kronecker ansatz spaces in <cit.>, thus showing how g-linearizations and linearizations arising from them, interact with some of the important linearizations for rectangular matrix polynomials in the literature.

 From the point of view of computation, a desirable property of any linearization for solving an eigenvalue problem associated with a matrix polynomial P(λ) is that the computed solution is the exact solution of some polynomial P(λ) + Δ P(λ) such that the ratio Δ P/P is of the order of unit roundoff u with respect to some choice of norm · on matrix polynomials. Moreover, when P(λ) is singular, it is also desirable that the rules for extracting the left and right minimal indices of P(λ) from a particular class of linearizations for P(λ) remains the same for P(λ) + Δ P(λ) with respect to that class. This is referred to as global backward stability analysis for the polynomial eigenvalue problem and has been undertaken for algorithms that use the Frobenius companion linearizations in <cit.>. More recently this has been extended to the Block Kronecker linearizations in <cit.> which identifies optimal choices of Block Kronecker linearizations that ensure global backward stability when used to solve the eigenvalue problem for P(λ). We extend the analysis in <cit.> to the linearizations of P(λ) extracted from g-linearizations. Our analysis shows that there is a wider choice of linearizations beyond the ones identified in <cit.> that can be used to solve the complete eigenvalue problem for P(λ) in a backward stable manner.



§ DEFINITIONS AND NOTATIONS


In this paper we use standard notations like  𝔽 to denote the field of real or complex numbers,  I_n to denote the n × n identity matrix and e_i,   1 ≤ i ≤ n, to denote the i-th column of I_n unless otherwise specified. Also, wherever it is necessary to emphasize the dimension of a zero matrix, we will use 0_n to denote a column of n zeros and 0_m × n to denote the m × n zero matrix. We will use 𝔽(λ) to denote the field of rational functions with coefficients in 𝔽 and 𝔽(λ)^n to denote the vector space of n-tuples with entries from 𝔽(λ). Also 𝔽[λ] will denote the ring of polynomials over the field 𝔽 and 𝔽[λ]^m × n will denote the ring of m × n matrix polynomials with entries from 𝔽[λ].

Here we will consider m× n matrix polynomials with grade k of the form

    P(λ)=∑_i=0^k λ^i A_i ∈𝔽[λ]^m× n,

where any of the coefficient matrices may be the zero matrix. Degree of P(λ) denoted by deg  P is the maximum integer d such that A_d≠ 0. In this paper we will assume that deg  P ≥ 2. A square matrix polynomial Q(λ) is said to be unimodular if its determinant is a nonzero constant independent of λ.

The normal rank of P(λ), denoted by nrankP(λ), is the rank of P(λ) considered as a matrix with entries in 𝔽(λ). Also the k-reversal rev_kP(λ) of  P(λ) is defined by rev_kP(λ)=λ^kP(1/λ).

A finite eigenvalue of P(λ) is an element λ_0∈𝔽 such that rankP(λ_0)<nrankP(λ). We say that P(λ) with grade k has an infinite eigenvalue if the k-reversal polynomial rev_kP(λ)=λ^kP(1/λ) has zero as an eigenvalue.

The following subspaces associated with P(λ) will be frequently used.


 The right and left null spaces of a m× n matrix polynomial P(λ), denoted by N_r(P) and N_l(P) respectively are defined as follows.
  
    N_r(P)     =    {x(λ)∈𝔽(λ)^n:P(λ)x(λ)≡ 0},
    
     N_l(P)     =    {y(λ)∈𝔽(λ)^m:y(λ)^TP(λ) ≡ 0}.



A vector polynomial is a vector whose entries are polynomials. For any subspace of 𝔽(λ)^n, it is always possible to find a basis consisting entirely of vector polynomials. The degree of a vector polynomial is the greatest degree of its components, and the order of a polynomial basis is defined as the sum of the degrees of its vectors. Also any subspace of 𝔽(λ)^n has a polynomial basis of least order among all such bases and the ordered list of degrees of the vector polynomials in any such basis is always the same <cit.>. A minimal basis of the subspace is therefore defined as any polynomial basis of least order among all such bases and the minimal indices of the subspace are the ordered list of degrees of the vector polynomials in such a basis. In particular we have the following definitions.

 For a given m× n matrix polynomial P(λ), a left minimal basis is a minimal basis of N_l(P) and a right minimal basis is a minimal basis of N_r(P).


 For a given m× n matrix polynomial P(λ), let { x_1(λ), …, x_p(λ)} be a right minimal basis and {y_1(λ), …, y_q(λ)} be a left minimal basis such that 
    deg  x_1 ≤⋯≤deg  x_p deg  y_1 ≤⋯≤deg  y_q.
 Setting η_i = deg  x_i, i = 1, …, p, and ϵ_j = deg  y_j, j = 1, …, q, the right and left minimal indices of P(λ) are defined as η_1 ≤⋯≤η_p, and ϵ_1 ≤⋯≤ϵ_q respectively.


The left and right minimal bases and indices of a matrix polynomial P(λ) are defined as the minimal bases and indices of its left  and right null spaces N_l(P) and N_r(P) respectively.

The most widely used approach for solving polynomial eigenvalue problems is linearization.


 A matrix pencil L(λ)=λ X+Y with X,Y∈ℂ^(m+s) × (n+s) is a linearization of an m × n matrix polynomial P(λ) of grade k if there exist two unimodular matrix polynomials E(λ)∈𝔽[λ]^(m+s) × (m+s) and F(λ)∈𝔽[λ]^(n+s) × (n+s) for some positive integer s such that
 
    E(λ)L(λ)F(λ)= [[ P(λ)     ;       I_s ]].



For example the first and second Frobenius companion forms C_1(λ) and C_2(λ) given by


    C_1(λ)     :=    λ[ A_k        ;     I_n        ;           ⋱;             I_n ] + [ A_k-1 A_k-2     …   A_0;  -I_n                 0;           ⋱      ;              -I_n     0 ]
    
    C_2(λ)     :=    λ[ A_k        ;     I_m        ;           ⋱;             I_m ] + [ A_k-1  -I_m     …      ; A_k-2            ;           ⋱        -I_m;   A_0     0           0 ]

are linearizations of P(λ) with s = (k-1)n and s = (k-1)m respectively. It is clear that a matrix polynomial and its linearization has the same finite eigenvalues and corresponding elementary divisors (for details, see, <cit.>). However, if the same is to be guranteed for the eigenvalue at infinity also, then the linearization has to be a strong linearization of P(λ).


A linearization L(λ) = λ X+Y of a matrix polynomial P(λ) of grade k is called a strong linearization of P(λ)  if rev_1   L(λ) is also a linearization of rev_k   P(λ).




§ VECTOR SPACES OF GENERALIZED LINEARIZATIONS


The vector spaces 𝕃_1(P) and 𝕃_2(P) defined by (<ref>) and (<ref>) were introduced in <cit.> as sources of linearizations for a given square regular matrix polynomial P(λ). This work was subsequently extended in <cit.> to the case of square singular matrix polynomials. In this section we extend the notion of these spaces to the case of rectangular matrix polynomials. For this we introduce the notion of generalized linearizations of matrix polynomials which we refer to  as g-linearizations in short. We then define vector spaces of matrix pencils corresponding to the polynomial P(λ) and show that they have properties with respect to g-linearizations that closely resemble those of Ł_1(P) and Ł_2(P) established in <cit.> with respect to linearizations in the square singular case.



 §.§ Generalized linearizations of matrix polynomials



 A matrix pencil L(λ)=λ X+Y with X,Y∈ℂ^mk× nk is called a g-linearization of an m × n matrix polynomial P(λ) of grade k if there exist two unimodular matrices E(λ)∈𝔽[λ]^mk× mk and F(λ)∈𝔽[λ]^nk× nk such that
 
    E(λ)L(λ)F(λ)=[ [         P(λ)             ;              I_k-1⊗ I_m,n ]]

 

Here I_m,n =[         I_n; 0_(m-n) × n ] if  m>n, I_m,n = [         I_m 0_m × (n-m) ] if  m<n and I_m,n=I_m=I_n  if  m=n.




 A matrix pencil L(λ)=λ X+Y with X,Y∈ℂ^mk× nk is a strong g-linearization of an m × n matrix polynomial P(λ) of grade k if L(λ) is a g-linearization of P(λ) and rev_1L(λ) is a g-linearization of rev_kP(λ).


From the above definition, it is clear that every linearization of a square matrix polynomial is also a generalized linearization, which justifies our choice for the term. Also, evidently a matrix polynomial has the same eigenvalues and elementary divisors as it g-linearization and the same finite and infinite eigenvalues and elementary divisors as its strong g-linearization. Therefore, to establish that the solution of a complete eigenvalue problem for a rectangular matrix polynomial can be obtained from a given strong g-linearization, it is enough to show that the minimal bases and indices of the polynomial can be easily recovered from the g-linearization.



 §.§ The vector spaces 𝕃_1(P) and 𝕃_2(P)


To extend the work in <cit.> to non-square matrix polynomials, we propose the following vector spaces, which we continue to denote by Ł_1(P) and Ł_2(P) for ease of notation.


    𝕃_1(P)     :=    {L(λ):L(λ)(Λ_k(λ)⊗ I_n)=v⊗ P(λ),v∈𝔽^k}, 
    𝕃_2(P)     :=    {L(λ):(Λ_k(λ)^T⊗ I_m)L(λ)=w^T⊗ P(λ),w∈𝔽^k}.


Following <cit.> we will refer to the vector v (w) in the identity in (<ref>), ((<ref>)) satisfied by L(λ) ∈Ł_1(P), (L(λ) ∈Ł_2(P)) as the right (left) ansatz vector corresponding to L(λ). The sets 𝕃_1(P) and 𝕃_2(P) are not empty as C_1^g(λ) := λ X_1+Y_1 ∈𝕃_1(P) with right ansatz vector v = e_1 ∈^k

where X_1=[   A_k            ;       I_m,n            ;                 ⋱;                   I_m,n ], Y_1=[  A_k-1  A_k-2      …    A_0; -I_m,n                    0;             ⋱       ;               -I_m,n      0 ].



and C_2^g(λ) := λ X_2+Y_2∈𝕃_2(P) with left ansatz vector w = e_1 ∈^k,

where X_2=[   A_k            ;       I_m,n            ;                 ⋱;                   I_m,n ], Y_2=[  A_k-1 -I_m,n      …       ;  A_k-2              ;             ⋱        -I_m,n;    A_0      0             0 ].

As Theorem <ref> and Theorem <ref> show, if m≥ n then C_1^g(λ) is a strong g-linerization of P(λ) and if m≤ n then C_2^g(λ) is a strong g-linerization of P(λ).

For any matrix polynomial P(λ), clearly 𝕃_1(P) and  𝕃_2(P) are vector spaces over . In this section we find some important properties of these vector spaces. The results show that if the m × n matrix polynomial P(λ) is tall, i.e., m≥ n, then the properties of Ł_1(P) with respect to g-linearizations are very similar to those of the corresponding space for square matrix polynomials considered in <cit.> and <cit.> with respect to linearizations. The same is true of  Ł_2(P) when P(λ) is broad, i.e., m≤ n.

For the case m = n, the matrix pencils in Ł_1(P) and Ł_2(P) were originally characterized in <cit.> by introducing special operations on block matrices called column shifted sums and row shifted sums respectively. We state these definitions with the aim of showing that the same characterizations also hold when m ≠ n.


Let X and Y be block matrices 


    X=[ X_11    … X_1k; X_21    … X_2k;    ⋮    ⋱    ⋮; X_k1    … X_kk ],Y=[ Y_11    … Y_1k; Y_21    … Y_2k;    ⋮    ⋱    ⋮; Y_k1    … Y_kk ]
 with blocks X_ij, Y_ij∈𝔽^m× n then the operations 



    X   Y     :=    [ X_11    ⋯ X_1k    0; X_21    ⋯ X_2k    0;    ⋮    ⋮    ⋱    ⋮; X_k1    … X_kk    0 ]+[    0 Y_11    ⋯ Y_1k;    0 Y_21    ⋯ Y_2k;    ⋮    ⋮    ⋱    ⋮;    0 Y_k1    ⋯ Y_kk ], and 
    
     X   Y     :=    [ X_11 X_12    … X_1k;    ⋮    ⋮    ⋱    ⋮; X_k1 X_k2    ⋯ X_kk;    0    0    ⋯    0 ]+[    0    0    ⋯    0; Y_11 Y_12    ⋯ Y_1k;    ⋮    ⋮    ⋱    ⋮; Y_k1 Y_k2    ⋯ Y_kk ],

where the zero blocks are also of size m× n are referred to as the column shifted sum and the row shifted sum of X and Y respectively.



The above definition immediately gives the following lemma, the proof of which is obvious.

 Let P(λ)=∑_i=0^k λ^i A_i be an m× n matrix polynomial of grade k and L(λ)=λ X+Y be an km× kn pencil. Then for v, w ∈𝔽^k,
 
    (λ X+Y)(Λ_k(λ)⊗ I_n)     =     v ⊗ P(λ) ⇔ X  Y=v⊗[   A_k A_k-1     …   A_0 ]
    
     (Λ_k(λ)^T⊗ I_m)(λ X+Y)     =     w^T ⊗ P(λ) ⇔ X  Y=w^T⊗[   A_k^T A_k-1^T       …   A_0^T ]^T



Thus we have an immediate characterization of the spaces 𝕃_1(P) and Ł_2(P) in the next theorem the proof of which is omitted as it follows by arguing exactly as in the proof of  <cit.>.


 Let P(λ)=∑_i=0^k λ^i A_i be a m× n matrix polynomial of grade k and v,w ∈𝔽^k. Then the pencils in 𝕃_1(P) with right ansatz vector v consists of all L(λ)=λ X+Y such that X=[ v⊗ A_k     -W ] and Y=[ W+v⊗[ A_k-1     …   A_1 ]                    v⊗ A_0 ] with W∈𝔽^km× (k-1)n chosen arbitrarily.

 Similarly, the pencils in Ł_2(P) with left ansatz vector w are given by L(λ) = λ X + Y such that X =  [ w^T ⊗ A_k;        -Ŵ ] and Y=[ Ŵ + w^T⊗[ A_k-1^T       …   A_1^T ]^T;                             w^T ⊗ A_0 ] with Ŵ∈𝔽^(k-1)m× kn chosen arbitrarily.


It is clear from Theorem <ref> that the vector spaces 𝕃_1(P) and 𝕃_2(P) are completely determined by the pairs (v, W) and (w, Ŵ) respectively,
 where v, w ∈𝔽^k, W ∈𝔽^km× (k-1)n and Ŵ∈^(k-1)m × kn. Hence the dimensions of the vector spaces 𝕃_1(P) and Ł_2(P) over  are both equal to k(k-1)mn+k. The following immediate corollary of Theorem <ref> shows that in particular matrix pencils in Ł_1(P) and Ł_2(P) with corresponding ansatz vector α e_1 ∈^k for some non zero scalar α are easy to construct from the coefficient matrices of P(λ).


 Suppose L(λ)=λ X+Y∈𝕃_1(P) with right ansatz vector v=α e_1 for α≠0. Then X=[[ α A_k  X_12;          -Z ]] and Y=[[  Y_11 α A_0;     Z       ]] where X_12, Y_11∈^m × (k-1)n satisfy X_12 + Y_11 =
 α[ A_k-1     …   A_1 ] and Z∈𝔽^(k-1)m× (k-1)n is arbitrary.

 Similarly, if L(λ) = λ X+Y ∈𝕃_2(P) has left ansatz vector w = α e_1 for α≠0, then X=[[ α A_k      ; X̂_12    -Ẑ ]] and Y=[[  Ŷ_11     Ẑ; α A_0       ]] where X̂_12, Ŷ_11∈^(k-1)m × n satisfy X̂_12 + Ŷ_11 = α[ A_k-1;     ⋮;   A_1 ] and  Ẑ∈𝔽^(k-1)m × (k-1)n is arbitrary.


Given an m × n matrix polyomial P(λ), it is easy to see that

    L(λ) ∈Ł_2(P) ⇔ L(λ)^T ∈Ł_1(P^T).


Therefore, the results in the rest of the paper for Ł_1(P) where P(λ) is of size m × n with m ≥ n, give rise to corresponding results for Ł_2(P) when m ≤ n with appropriate modifications. We provide proofs only for the statements concerning Ł_1(P) as the corresponding statements for Ł_2(P) follow either by using the correspondence (<ref>) or by similar independent arguments. The first among these is an analog of  <cit.>, that gives a sufficient condition for a pencil in Ł_1(P) (respectively, Ł_2(P)) to be a strong g-linearization of P(λ) when m ≥ n (respectively, m ≤ n).


 Let P(λ)=∑_i=0^k λ^i A_i be an m× n matrix polynomial. If m ≥ n and L(λ)∈𝕃_1(P) with right ansatz vector v ∈^k ∖{ 0 }, then for any nonsingular M∈𝔽^k× k such that Mv=α e_1 for some α≠ 0, the pencil (M⊗ I_m)L(λ) satisfies
 
    (M⊗ I_m)L(λ)=λ[[ α A_k  X_12;          -Z ]]+[[  Y_11 α A_0;     Z       ]]

 with Z∈𝔽^(k-1)m× (k-1)n. If Z is of full rank, i.e., Z = (k-1)n, then L(λ) ∈Ł_1(P)  is a strong g-linearization of P(λ).



We first prove the theorem for the case that v = α e_1 for some α≠ 0. Then 
    L(λ)=λ[[ α A_k  X_12;          -Z ]]+[[  Y_11 α A_0;     Z       ]] = λ X + Y (say),
 where X_12, Y_11∈^m × (k-1)n satisfy X_12 + Y_11 =
 α[ A_k-1     …   A_1 ] and Z∈𝔽^(k-1)m× (k-1)n is arbitrary.






 Partitioning Z as
 Z=[   Z_1   Z_2     … Z_k-1 ] Z_i ∈𝔽^(k-1)m × n, and setting 
    G(λ)=[     1     0     … λ^k-1;           ⋱           ⋮;                 1     λ;                       1 ]⊗ I_n,
 we have,
 
    L(λ)G(λ)   =   [               *               *               …               *               *;             Z_1     (Z_2-λ Z_1)               … (Z_k-1-λ Z_k-2)        -λ Z_k-1 ]G(λ)
       =   [               *               *               …               *          α P(λ);             Z_1     (Z_2-λ Z_1)               … (Z_k-1-λ Z_k-2)               0 ].

 Now,
 
    L(λ)G(λ)
      [   I_n λ I_n                  ;         I_n                  ;               I_n      ;                       ⋱;   I_n ][   I_n                        ;         I_n λ I_n            ;               I_n      ;                       ⋱;   I_n ]…[   I_n                        ;           ⋱                  ;               I_n λ I_n;                     I_n;   I_n ]
       =   [               *               *               …               *          α P(λ);             Z_1             Z_2               … (Z_k-1-λ Z_k-2)               0 ][   I_n                        ;         I_n λ I_n            ;               I_n      ;                       ⋱;   I_n ]…[   I_n                        ;           ⋱                  ;               I_n λ I_n;                     I_n;   I_n ]
       =   [      *      *      …      * α P(λ);    Z_1    Z_2      …  Z_k-1      0 ]
       =   [[      * α P(λ);      Z        ]].

Therefore there exist a unimodular matrix F(λ) such that

    L(λ)F(λ)=[[ P(λ) W(λ);         Z ]] for some W(λ) ∈[λ]^m × (k-1)n.


If Z is of full rank, then Z^† Z=I_(k-1)n. Therefore, 
    [[      I_m -W(λ)Z^†;          I_(k-1)m ]]L(λ)F(λ)=[[ P(λ)     ;         Z ]].

As rank  Z=(k-1)n=rank  (I_k-1⊗ I_m,n), there exist invertible matrices
E∈𝔽^(k-1)m× (k-1)m and F∈𝔽^(k-1)n× (k-1)n such that Z=E(I_k-1⊗ I_m,n)F.
This implies that L(λ) is a g-linearization of P(λ) as, 
    [[      I_m -W(λ)Z^†;          I_(k-1)m ]]L(λ)F(λ)=[[ I_m    ;       E ]][[         P(λ)             ;              I_k-1⊗ I_m,n ]][[ I_n    ;       F ]].


To show that L(λ) is a strong g-linearization of P(λ), notice that 
    λ^k-1Λ_k(1/λ)=[     1     λ     … λ^k-1 ]^T=R_kΛ_k(λ),  R_k=[ 1; ⋱; 1 ]_k × k.

As L(λ) ∈Ł_1(P) with corresponding right ansatz vector α e_1, we have




    rev_1L(λ)(R_kΛ_k(λ)⊗ I_n)=α e_1⊗rev_kP(λ)
     ⇒rev_1L(λ)(R_k ⊗ I_n)_=: L̃(λ)(Λ_k(λ) ⊗ I_n) = α e_1⊗rev_kP(λ).





Therefore L̃(λ)=λX̃+Ỹ∈Ł_1(rev P), where 
    X̃= Y(R_k⊗ I_n) = [[ α A_0 X̃_12;         -Z̃ ]]   and Ỹ=X(R_k⊗ I_n)
    = [[  Ỹ_11 α A_k;    Z̃ ]]

with Z̃=-Z(R_k-1⊗ I_n) which is of full rank if Z is of full rank. Hence L̃(λ) is a g-linearization of rev_kP(λ) and consequently rev_1L(λ) is a g-linearization of rev_kP(λ), this completes the proof for the case that v = α e_1.

Now let L(λ) ∈Ł_1(P) with corresponding nonzero right ansatz vector v ∈^k. From (<ref>) it follows that L(λ) is a strong g-linearization of P(λ) if and only if the pencil 
    L̂(λ) := λ[[ α A_k  X_12;          -Z ]]+[[  Y_11 α A_0;     Z       ]]
 is a strong g-linearization of P(λ). Clearly, L̂(λ) ∈Ł_1(P) with corresponding right ansatz vector α e_1. Since Z = (k-1)n, by the first part of the proof, it follows that L̂(λ) is a strong g-linearization of P(λ) and this completes the proof.


The corresponding theorem for Ł_2(P) is as follows.

  Let P(λ)=∑_i=0^k λ^i A_i be an m× n matrix polynomial.
If, m ≤ n and L(λ)∈𝕃_2(P) with left ansatz vector w ∈^k ∖{ 0 },  then for any nonsingular M̂∈𝔽^k× k such that M̂ w = α e_1 for some α≠ 0, the pencil L(λ)(M̂^T ⊗ I_n) satisfies

    L(λ)(M̂^T ⊗ I_n) =[[ α A_k      ; X̂_12    -Ẑ ]] + [[  Ŷ_11     Ẑ; α A_0       ]],

with Ẑ∈^(k-1)m × (k-1)n.
   If Ẑ is of full rank, i.e., Ẑ = (k-1)m, then L(λ) ∈Ł_2(P)  is a strong g-linearization of P(λ).


It was proved in <cit.> that if P(λ) is a square regular polynomial, then L(λ) ∈Ł_1(P) is a strong linearization of P(λ) if and only if the matrix in the position of the block labelled Z in (<ref>) is nonsingular. However as shown in <cit.>, the same is not a necessary condition for L(λ) to be a strong linearization of P(λ) if it is square but not regular. The following simple modification of that example shows that if P(λ) is an m × n matrix polynomial with m≥ n, then L(λ) ∈Ł_1(P) with corresponding nonzero right ansatz vector v ∈^k, can be a strong g-linearization of P(λ)
even if the matrix labelled Z in (<ref>) is rank deficient.

  Let P(λ) = λ^2 A_2 where A_2 = [[ 1 0; 0 0; 0 0 ]]. Then L(λ) = λ[[ A_2 -X̂;   0  -Z ]] + [[ X̂  0;  Z  0 ]] where 
    X̂ = [[  0  0;  0 -1;  0  0 ]],    Z = [[ -1  0;  0  0;  0  0 ]]
 belongs to Ł_1(P) with right ansatz vector e_1. Although Z = 1, interchanging the second and fifth rows of L(λ) gives C_1^g(λ) which is a strong g-linearization of P(λ).



Since the matrix in the block labelled Z in the reduction (<ref>) of L(λ) ∈Ł_1(P) plays an important role in determining whether L(λ) is a g-linearization of P(λ), we refer to it as the Z-matrix of L(λ) with respect to the pair (M, α) as it may vary depending on the choice of the nonsingular matrix M satisfying Mv = α e_1. Therefore it is important to know whether its rank can change with change in the choice of M. The next theorem shows that this does not happen, i.e., the rank of the Z-matrix
in a given L(λ) ∈Ł_1(P), remains invariant of the choice of M. The proof of the theorem is omitted as it follows by arguing exactly as in the proof of <cit.>.


Let P(λ)= ∑_i=0^k λ^i A_i be an m× n  matrix polynomial with m ≥ n and L(λ)=λ X+Y∈𝕃_1(P) with right ansatz vector v≠0. Suppose that M_1,M_2∈𝔽^k× k are two nonsingular matrices such that M_1v=α_1e_1 and M_2v=α_2e_1 for some α_1≠0, and α_2≠0. If Z_1,Z_2∈𝔽^(k-1)m× (k-1)n are the matrices in the block labelled Z in (<ref>) corresponding to the pairs  (M_1,α_1) and (M_2,α_2) respectively, then Z_1=  Z_2.


In a similar way it can also be shown that if the m × n matrix polynomial P(λ) satisfies m ≤ n, the rank of the matrix labelled Ẑ in the reduction (<ref>) is independent of the choice of the nonsingular matrix M̂.  The above result allows us to make the following definition.


  For an m × n matrix polynomial P(λ) with m ≥ n, (respectively m ≤ n,) the Z-rank of L(λ)∈𝕃_1(P) (respectively, L(λ) ∈Ł_2(P)) is the rank of any matrix appearing in the block labelled Z (respectively, Ẑ) under any reduction of L(λ) of the form (<ref>) (respectively, (<ref>)). If Z (respectively, Ẑ) in (<ref>) (respectively, (<ref>))  is of full rank, then we say that L(λ)∈𝕃_1(P) (respectively, L(λ)∈𝕃_2(P)) has full Z-rank.


The final result of this section shows that for a given m × n matrix polynomial P(λ) with m ≥ n, almost every pencil in Ł_1(P) is a g-linearization of P(λ).



(Genericity of g-linearizations in Ł_1(P) and Ł_2(P))
 For any m× n matrix polynomial P(λ) of grade k with m ≥ n, (respectively, m ≤ n,) almost every pencil in 𝕃_1(P) (respectively, Ł_2(P)) is a strong g-linearization of P(λ).



 Let P(λ)=∑_i=0^k λ^i A_i be an m× n matrix polynomial with m≥ n.
 The set of pencils in 𝕃_1(P) with right ansatz vector v consists of all L(λ)=λ X+Y such that
 
    X=[ v⊗ A_k     -W ] Y=[ W+v⊗[ A_k-1     …   A_1 ]                    v⊗ A_0 ]
 with W∈𝔽^km× (k-1)n chosen arbitrarily. For a parameterized 𝕃_1(P) we define the isomorphism

 
    Γ:𝕃_1(P)    →   𝔽^k×𝔽^km × (k-1)n
    λ X+Y    ↦    (v,W).


 Suppose L(λ)=λ X+Y∈𝕃_1(P) with right ansatz vector v=[ v_1   … v_k ]^T.
 Let 
    M=[[            1            0; -v_2
    ⋮
     -v_k     v_1I_k-1 ]],
 then Mv=v_1e_1 and if v_1≠ 0 then M is nonsingular.

Now (M⊗ I_m)L(λ)=λ ((M⊗ I_m)X)+((M⊗ I_m)Y) where
 
    (M⊗ I_m)X=[[    Mv⊗ A_k -(M⊗ I_m)W ]]=[[ v_1e_1⊗ A_k  -(M⊗ I_m)W ]]:=[[ v_1A_k      *;            Z̃ ]].

 Clearly -Z̃ is a Z-matrix of L(λ) with respect to (M, v_1).
Then 
    𝒫(v,W):=v_1∑( minor of Z̃ of order  (k-1)n)
 is a polynomial
in the k+k(k-1)mn entries of v and W. The pair corresponding to C_1^g(λ) has
 v=e_1 and W=[[             0; -I_k-1⊗ I_m,n ]].
Hence, Z̃= I_k-1⊗ I_m,n and thus 𝒫(v,W)≠0 for C_1^g(λ).
 Therefore the zero set of 𝒫(v,W) defines a proper algebraic subset of 𝕃_1(P). Clearly any pair (v,W) such that 𝒫(v,W)≠0 has v_1≠0 and any one of the minors of Z̃ of order (k-1)n has nonzero determinant. So the corresponding L(λ) will have full Z-rank and hence is a strong g-linearization of P(λ).


An important difference between linearizations of regular and singular square matrix polynomials P(λ) in the space Ł_1(P) is that while every linearization of P(λ) in Ł_1(P) is also a strong linearization of P(λ) when P(λ) is a regular matrix polynomial <cit.>, the same is not true if P(λ) is singular <cit.>. The following example shows that the same also holds for g-linearizations of rectangular matrix polynomials, i.e., there exist rectangular matrix polynomials P(λ) with g-linearizations in Ł_1(P) that are not strong g-linearizations.



Let P(λ) = [[ λ^2   λ;   λ   1;   0   0 ]]. Then 
    L(λ) = λ[[  1  0  0  0;  0  0  0  0;  0  0  0  0;  0  0 -1  0;  0  0  0  0;  0  0  0  0 ]] + [[ 0 1 0 0; 1 0 0 1; 0 0 0 0; 1 0 0 0; 0 0 0 0; 0 0 0 0 ]] ∈Ł_1(P)

is a g-linearization of P(λ) as E(λ)L(λ)F(λ) =  [[  P(λ)     0;     0 I_3,2 ]] for

    E(λ) = [[ 0 0 1 λ 0 0; 0 0 0 1 0 0; 0 0 0 0 1 0; 0 1 0 0 0 0; 1 0 0 0 0 0; 0 0 0 0 0 1 ]]  F(λ) = [[  0  1  0  0;  0 -λ  0  1; -1  0  0  0;  0 -1  1  0 ]].

But L(λ) is not a strong g-linearization of P(λ) as infinity is a eigenvalue of L(λ) but not of P(λ).





§ RECOVERY OF MINIMAL INDICES AND BASES IN Ł_1(P) AND Ł_2(P)


In this section we show the process of extraction of left and right minimal bases and indices of an m × n polynomial P(λ) from that of a g-linearization in Ł_1(P) or Ł_2(P). In particular we show that these extractions are possible from g-linearizations of P(λ) in Ł_1(P) with full Z-rank if m≥ n and those of P(λ) in Ł_2(P) if m≤  n. It is easy to see that if m≥ n and L(λ) ∈Ł_1(P) is of full Z-rank, then

    N_r(L) =   N_r(P)   N_l (L) + (k-1)(m-n) =   N_l(P).

On the other hand if m≤ n, and L(λ) ∈Ł_2(P) has full Z-rank, then the above equalities hold when the positions of the right and left null spaces are interchanged for both P(λ) and L(λ). Therefore the process of extracting the right (respectively, left) minimal bases and indices of P(λ) ∈[λ]^m × n from those of a g-linearization of P(λ) in Ł_1(P) (respectively, Ł_2(P)) is identical to the extraction of the same quantities from a linearization of a square singular polynomial in the respective spaces (as established in <cit.>). However, showing that the left (respectively, right) minimal bases and indices of P(λ) can also be extracted from those of L(λ) ∈Ł_1(P) (respectively, L(λ) ∈Ł_2(P)) with full Z-rank requires more work.



 §.§ Recovery of right (left) minimal indices and bases in Ł_1(P) (Ł_2(P))


Given an m × n matrix polynomial P(λ) with m≥ n, the following lemma provides an isomorphism between N_r(P) and N_r(L) that enables extraction of the right minimal bases and indices of P(λ) from those of L(λ) ∈Ł_1(P).


 Let P(λ) be an m× n matrix polynomial of grade k with m ≥ n, L(λ)∈𝕃_1(P) with nonzero right ansatz vector v, and x(λ)∈𝔽(λ)^n. Then Λ_k(λ)⊗ x(λ)∈ N_r(L) if and only if x(λ)∈ N_r(P). Moreover, if L(λ) is a g-linearization of P(λ), then the mapping
 
    R_Λ:N_r(P)   →    N_r(L)
    
     x(λ)   ↦   Λ_k(λ)⊗ x(λ).

 is a linear isomorphism between the 𝔽(λ)-vector spaces N_r(P) and N_r(L). Furthermore, x(λ)∈ N_r(P) is a vector polynomial if and only if Λ_k(λ)⊗ x(λ)∈ N_r(L) is a vector polynomial.


We skip the proof as it follows by arguing exactly as in the proof of <cit.>. Now the following theorem whose proof is immediate shows that the right minimal bases and indices of P(λ) ∈[λ]^m × n,   m≥ n, have a very simple relationship with those of a g-linearization L(λ) ∈Ł_1(P) and can be easily extracted from the latter.


 Let P(λ) be an m× n matrix polynomial of grade k with m≥ n and nrankP(λ)=r. Also let L(λ)∈𝕃_1(P) be a g-linearization of P(λ).

 
  
  * The right minimal indices of P(λ) are ϵ_1≤ϵ_2≤…≤ϵ_n-r if and only if the right minimal indices of L(λ) are (k-1)+ϵ_1≤(k-1)+ϵ_2≤…≤(k-1)+ϵ_n-r.
  
  * Every right minimal basis of L(λ) is of the form {Λ_k(λ)⊗ x_1(λ),…,Λ_k(λ)⊗ x_n-r(λ)} where 
 {x_1(λ),…,x_n-r(λ)} is a right minimal basis of P(λ).
 



Similarly, if P(λ) is an m × n matrix polynomial with m≤ n, then the mapping

    R_Λ:N_l(P) → N_l(L),     y(λ) ↦Λ_k(λ)⊗ y(λ),

 is an isomorphism between N_l(P) and N_l(L) that also induces a bijection between vector polynomials in N_l(P) and N_l(L). This results in the following counterpart of Theorem <ref> for extraction of the left minimal bases and indices of P(λ) from those of L(λ) ∈Ł_2(P) with full Z-rank.


 Let P(λ) be an m× n matrix polynomial of grade k with m ≤ n and nrankP(λ)=r. Also let L(λ)∈𝕃_2(P) be a g-linearization of P(λ).

 
  
  * The left minimal indices of P(λ) are ϵ_1≤ϵ_2≤…≤ϵ_m-r  if and only if the left minimal indices of L(λ) are (k-1)+ϵ_1≤(k-1)+ϵ_2≤…≤(k-1)+ϵ_m-r.
  
  * Every left minimal basis of L(λ) is of the form {Λ_k(λ)⊗ y_1(λ),…,Λ_k(λ)⊗ y_m-r(λ)} where 
 {y_1(λ),…, y_m-r(λ)} is a left minimal basis of P(λ).
 





 §.§ Recovery of left (right) minimal indices and bases in Ł_1(P) (Ł_2(P))


In this section we first show that the left minimal bases and indices of P(λ) ∈[λ]^m × n with m≥ n, can be extracted from the g-linearizations in Ł_1(P) that are of full Z-rank. The following lemmas will be very useful for establishing Theorem <ref> which is the main result.


 Let P(λ) = ∑_i = 0^k λ^iA_i be an m× n matrix polynomial of grade k with m ≥ n. Suppose L(λ)∈𝕃_1(P) has full Z-rank and right ansatz vector v≠ 0. Then the mapping
 
    ℒ_v:N_l(L)    →    N_l(P)
    
     y(λ)    ↦    (v^T⊗ I_m)y(λ)

 is a linear map from the vector space N_l(L) onto the vector space N_l(P) over (λ). Furthermore it is an onto map from the vector polynomials in N_l(L) to the vector polynomials in N_l(P) with the property that if q(λ) ∈ N_l(P) is a vector polynomial of degree δ, then there exists a vector polynomial y(λ) ∈ N_l(L) of degree δ such that ℒ_v(y(λ)) = q(λ).



 Let y(λ)∈ N_l(L). Since L(λ) ∈Ł_1(P),
 
    y(λ)^TL(λ)(Λ_k(λ)⊗ I_n)=0 ⇒ y(λ)^T(v⊗ P(λ))=0 ⇒ y(λ)^T(v⊗ I_m)P(λ)=0.

Therefore (v^T⊗ I_m)y(λ)∈ N_l(P) and this shows that ℒ_v is well defined and clearly linear.
































Let q(λ) ∈ N_l(P). To show that ℒ_v is onto we prove that there exists y(λ)∈ N_l(L) such that ℒ_v(y(λ)) = q(λ).
Let 
    S_k(λ) := [     1     λ     … λ^k-2;     ⋱     ⋱;     ⋱     λ;     1;     0 ]_k× (k-1),


    q_1(λ) :=[  q(λ); q̃(λ) ] y(λ)=(M^T⊗ I_m)q_1(λ)

where 
    q̃(λ)^T=-q(λ)^T(λ[  A_k X_12 ]+[ Y_11  A_0 ])(S_k(λ)⊗ I_n)Z^†_=: C
 and M is a nonsingular matrix such that Mv=e_1. Clearly ℒ_v(y(λ))=q(λ).

Now y(λ)∈ N_l(L) if and only if q_1(λ)∈ N_l(L̂), where L̂(λ)=(M⊗ I_m)L(λ). Also as L(λ) ∈Ł_1(P) corresponds to right ansatz vector v and Mv = e_1, therefore L̂(λ) ∈Ł_1(P) corresponds to right ansatz vector e_1.
So, 
    L̂(λ) = λ[ [  A_k X_12;        -Z ] ]+ [[ Y_11  A_0;    Z      ] ]

where Z has full rank and X_12 + Y_11 = [[ A_k-1 A_k-2     ⋯   A_1 ]].
 This implies that, 
    X_12 := [   X_1   X_2     ⋯ X_k-1 ] Y_11 := [   Y_1   Y_2     ⋯ Y_k-1 ]
 where X_i,Y_i∈𝔽^m× n satisfy X_i + Y_i = A_k-i for i = 1, 2, … k-1.
Now from (<ref>) and (<ref>),

    q_1(λ)^TL̂(λ)     =     [q(λ)^T   q̃(λ)^T]L̂(λ) 
        =     q(λ)^T[I_m    -C](λ[ [  A_k X_12;        -Z ] ]+ [[ Y_11  A_0;    Z      ] ]) 
        =     q(λ)^T(λ[A_k    X_12 + Ĉ] + [Y_11-Ĉ   A_0])

where

    Ĉ   =   (λ[   A_k   X_1   X_2     … X_k-1 ]+[   Y_1   Y_2     … Y_k-1   A_0 ])(S_k ⊗ I_n)
       =   ([     λ A_k+Y_1     λ X_1+Y_2     λ X_2+Y_3             … λ X_k-2+Y_k-1   λ X_k-1+A_0 ])(S_k ⊗ I_n)
       =    [[                           λ A_k+Y_1              λ^2A_k+λ (Y_1+X_1)+Y_2 λ^3A_k+λ^2(Y_1+X_1)+λ (Y_2+X_2)+Y_3 ]
          [                                              …                                              … λ^k-1A_k+λ^k-2(Y_1+X_1)+…+λ(Y_k-2+X_k-2)+Y_k-1 ]] 
        =     [[                         λ A_k+Y_1                λ^2A_k+λ A_k-1+Y_2                                 … λ^k-1A_k+λ^k-2A_k-1+…+λ A_2+Y_k-1 ]] 
        =     [[                       λ A_k              λ^2A_k+λ A_k-1                           … λ^k-1A_k+λ^k-2A_k-1+…+λ A_2 ]] + Y_11

the 2-nd last equality being due to the fact that X_i + Y_i = A_k-i, i = 1, 2, …, k-1. Therefore,

    λ(X_12 + Ĉ)     =    λ(X_12 + Y_11) + λ[[                       λ A_k              λ^2A_k+λ A_k-1                           … λ^k-1A_k+λ^k-2A_k-1+…+λ A_2 ]] 
        =     [[                   λ^2 A_k + λ A_k-1          λ^3A_k+λ^2 A_k-1 + λ A_k-2                                   … λ^k A_k+λ^k-1A_k-1+…+λ^2 A_2 +λ A_1 ]] 
          .

Using (<ref>) and (<ref>) in (<ref>),

    q_1(λ)^TL̂(λ)     =     q(λ)^T([[                       λ A_k            λ^2A_k + λ A_k-1 λ^3A_k+ λ^2 A_k-1 + λ A_k-2                           ⋯                  P(λ) - A_0 ]].  
           + . [[                       -λ A_k          -(λ^2A_k + λ A_k-1) -(λ^3A_k+ λ^2 A_k-1 + A_k-2)                            ⋯                          A_0 ]]) 
        =     q(λ)^T [[    0    0    ⋯    0 P(λ) ]] 
        =     0.


Therefore q_1(λ) ∈ N_l(L̂) and hence ℒ_v is an onto linear map from the vector space N_l(L) to the vector space N_l(P)
over (λ). Now clearly, if y(λ) ∈ N_l(L) is a vector polynomial, then so is ℒ_v(y(λ)). Conversely, if q(λ) ∈ N_l(P) is a vector polynomial, then from (<ref>) and (<ref>) it follows that q̃(λ), q_1(λ) and y(λ) are also a vector polynomials. Since  ℒ_v(y(λ)) = q(λ) and y(λ) ∈ N_l(L), it follows that ℒ_v maps the vector polynomials in N_l(L) onto the vector polynomials in N_l(P). To complete the proof we show that if the degree of q(λ) is δ, then y(λ) can be chosen so that it has degree δ.

 

















































 Let q(λ) ∈ N_l(P) and y(λ) ∈ N_1(L) be vector polynomials such that ℒ_v(y(λ))=q(λ). Let q = δ
 and suppose deg  y =δ̂>δ. Let q_1(λ) = (M^-T⊗ I_m)y(λ). Then deg  q_1 = δ̂
 and 
    q(λ) = ℒ_v (y(λ)) = (v^T ⊗ I_m)(M^T ⊗ I_m)q_1(λ) = (e_1^T ⊗ I_m)q_1(λ).

 This implies that q_1(λ) = [[  q(λ); q̃(λ) ]] where deg q̃ = δ̂.
 Hence 
    q_1(λ) = ∑_i = δ +1^δ̂λ^i [[   0; t_i ]] + [[             q(λ); ∑_i = 0^δλ^i t_i ]]_=:q̂(λ)

 where t_i ∈^(k-1)m, i = 0, …, δ̂, with t_δ̂≠ 0.
 Clearly deg q̂ = δ and

    q(λ) = ℒ_v(y(λ)) = (e_1^T ⊗ I_m)q_1(λ) = (e_1^T ⊗ I_m)q̂ (λ) = (v^T ⊗ I_m)
    (M^T ⊗ I_m)q̂(λ)_=: η( λ) = ℒ_v(η(λ)).

Since deg q̂ = δ, it follows that deg η = δ. To complete the proof we show
that η(λ) ∈ N_l(L). Now y(λ) ∈ N_l(L) ⇒ q_1(λ) ∈ N_l(L̂). Therefore,

    q_1(λ)^TL̂(λ) = 0 
       ⇒   ( [[                   0_m; ∑_i = δ + 1^δ̂λ^i t_i ]]^T + q̂(λ)^T )
     (λ[[  A_k X_12;        -Z ]] +  [[ Y_11  A_0;    Z      ]]) = 0 
       ⇒   λ[[                   0_m; ∑_i = δ + 1^δ̂λ^i t_i ]]^T [[  A_k X_12;        -Z ]] + [[                   0_m; ∑_i = δ + 1^δ̂λ^i t_i ]]^T[[ Y_11  A_0;    Z      ]] + q̂(λ)^TL̂(λ) = 0 
       ⇒   [[                      0^T_n -∑_i = δ + 1^δ̂λ^i+1t_i^TZ ]] + [[ ∑_i = δ + 1^δ̂λ^it_i^TZ                   0_n^T ]] + q̂(λ)^TL̂(λ) = 0 
       ⇒   λ^δ + 1[ t_δ +1^TZ    0_n^T] + λ^δ + 2([ t_δ + 2^TZ    0_n^T] +
     [ 0_n^T    -t_δ + 1^TZ]) + ⋯
          ⋯ + λ^δ̂( [ t_δ̂^TZ    0_n^T] + [ 0_n^T    -t_δ̂ - 1^T Z]) + λ^δ̂ + 1[0_n^T    -t_δ̂^TZ  ] + q̂(λ)^TL̂(λ) = 0.

Since the degree of q̂(λ)^T L̂(λ) is atmost δ + 1, equating the coefficients of λ^i, i = δ + 2, …, δ̂ + 1 in (<ref>) to 0, we have t_i^TZ = 0 for i = δ + 1, …, δ̂. Therefore (<ref>) implies that q̂(λ)^TL̂(λ) = 0 and this completes the proof as

    η(λ)^TL(λ) = q̂(λ)^T(M ⊗ I_m)L(λ) = q̂(λ)^TL̂(λ) = 0.











































 Let P(λ) = ∑_i=0^k λ^iA_i be an m × n matrix polynomial of grade k with m ≥ n and let L(λ) ∈Ł_1(P) correspond to a nonzero right ansatz vector v ∈^k with full Z-rank. Let r = nrank(P(λ)), c = (k-1)(m-n) and ℒ_v(y(λ)) = (v^T ⊗ I_m)y(λ) for all y(λ) ∈ N_l(L). Then there exists a minimal basis of N_l(L) of the form 
    {y_1(λ),…,y_m-r(λ),u_m-r+1,…,u_m-r+c},
 where  {u_m-r+1,…,u_m-r+c}⊂^km is a basis of N(ℒ_v).


 Since L(λ) is a g-linearization of P(λ) and m≥ n, therefore dim (N_l(L)) = dim (N_l(P)) + (k-1)(m-n).
Let r = nrank P(λ) and { v_1(λ), …, v_m-r(λ)} be a minimal basis of N_l(P) with deg  v_j = δ_j for j = 1, …, m-r.

By Lemma <ref>, there exist linearly independent vectors y_1(λ), …, y_m-r(λ) ∈ N_l(L) such that 
    ℒ_v (y_j(λ)) = v_j(λ), deg  y_j = δ_j.

Also from Lemma <ref> we have, ℒ_v = dim  N_l(P), and hence dim(N(ℒ_v)) = (k-1)(m-n) = c.
Let M ∈^k × k be a nonsingular matrix such that Mv = e_1 and L̂(λ) := (M ⊗ I_m)L(λ).
 Since L(λ) has full Z-rank, L̂(λ) = λ[[  A_k X_12;        -Z ]] + [[ Y_11  A_0;    Z      ]], where Z = (k-1)n. We show that there exists a basis of N(ℒ_v) consisting vectors of the form (M^T ⊗ I_m)[[ 0; v ]] such that v^TZ = 0. Since Z = (k-1)n, there exist c linearly independent vectors v_1, …, v_c ∈^(k-1)m such that v_i^TZ = 0 for all i = 1, …, c. Therefore β_v := { (M^T ⊗ I_m)[[   0; v_1 ]], …, (M^T ⊗ I_m)[[   0; v_c ]]} is a linearly independent subset of N(ℒ_v) as

    ((M^T ⊗ I_m)[[   0; v_i ]])^TL(λ) = [[   0; v_i ]]^T(M ⊗ I_m)L(λ) = [[   0; v_i ]]^TL̂(λ) = v_i^TZ = 0 
       and    (v^T ⊗ I_m)(M^T ⊗ I_m)[[   0; v_i ]] =
    (e_1^T ⊗ I_m)[[   0; v_i ]] = 0

for all i = 1, …, c. Clearly β_v is also a basis of N(ℒ_v) as it has c linearly independent vectors. Let 
    β = {y_1(λ), …, y_m-r(λ), u_m-r+1, …, u_m-r+c}
 where u_m-r+j :=  (M^T ⊗ I_m)[[   0; v_j ]], for j = 1, …, c. Since ℒ_v = dim(N_l(P)) = m-r, β has dim(N_l(L)) vectors. Therefore
 β is a basis of N_l(L) if it is a linearly independent set. Suppose there exist a_1(λ), …, a_m-r+c(λ) ∈(λ) such that

    a_1(λ)y_1(λ) + ⋯ + a_m-r(λ)y_m-r(λ) + a_m-r+1(λ)u_m-r+1 + ⋯ + a_m-r+c(λ)u_m-r+c = 0.

Then, ℒ_v(a_1(λ)y_1(λ) + ⋯ + a_m-r(λ)y_m-r(λ)) = 0 ⇒ a_1(λ)v_1(λ) + ⋯ + a_m-r(λ)v_m-r(λ) =0. 

This gives a_j(λ) = 0 for j = 1, …, m-r as {v_1(λ), …, v_m-r(λ)} is a basis of N_l(P). So from (<ref>) we have a_m-r+1(λ)u_m-r+1 + ⋯ + a_m-r+c(λ)u_m-r+c = 0 which implies that a_j(λ) = 0 for j = m-r+1, …, m-r+c as β_v is a basis of N(ℒ_v).  Hence β is a basis of N_l(L).  Suppose that it is not a minimal basis of N_l(L). Since the sum of the degrees of the polynomials in β is ∑_j=1^m-rδ_j, there exists a minimal basis
β̂ := {ŷ_1(λ), …, ŷ_m-r+c(λ) } of N_l(L) such that ∑_i = 1^m-r+cdeg ŷ_i < ∑_i=1^m-rδ_i. Then ℒ_v(β̂) is a spanning set in N_l(P). Let {ℒ_v(ŷ_i_1(λ)), …, ℒ_v(ŷ_i_m-r(λ))}⊂ℒ_v(β̂) be a basis of N_l(P). Then 
    ∑_j = 1^m-rdeg ℒ_v(ŷ_i_j) < ∑_j=1^m-rδ_j = ∑_j=1^m-rdeg  y_j =∑_j=1^m-rdeg  v_j.

But this contradicts the assumption that { v_1(λ), …, v_m-r(λ)} is a minimal basis of N_l(P). Hence the proof.


The following theorem now shows how the left minimal indices and bases of an m × n matrix polynomial P(λ) with m ≥ n can be extracted from those of L(λ) ∈Ł_1(P) with full Z-rank.

 Let P(λ) be an m × n matrix polynomial of grade k with m ≥ n, and let L(λ) ∈Ł_1(P) corresponding to nonzero right ansatz vector v ∈^k be of full Z-rank. Let r = nrank  P(λ), c = (k-1)(m-n) and ℒ_v(y(λ)) = (v^T ⊗ I_m)y(λ) for all y(λ) ∈ N_l(L).
 If β={y_1(λ),…,y_m-r(λ),u_m-r+1,…,u_m-r+c} be a minimal basis of N_l(L) satisfying the properties of Lemma <ref>, then {ℒ_v(y_1(λ)),…,ℒ_v(y_m-r(λ))} is a minimal basis of N_l(P). Moreover if δ_1≥δ_2≥…≥δ_m-r≥ 0=0=…=0_c   zeros are the left minimal indices of L(λ) then δ_1≥δ_2≥…≥δ_m-r are the left minimal indices of P(λ).



Since {u_m-r+1,…,u_m-r+c} forms a basis of N(ℒ_v), hence ℒ_v(u_i) = 0 for i=m-r+1,…, m-r+c.
Let z_i(λ) = ℒ_v(y_i(λ)) for i=1, …, m-r. Evidently, deg  y_i = deg  z_i  for all i=1,…,m-r
and { z_1(λ), …, z_m-r(λ)} is a basis of N_l(P). Now if it is not a minimal basis of N_l(P), then there exists a basis {ẑ_1(λ), …, ẑ_m-r(λ)} of N_l(P) such that deg ẑ_j_0 < deg  z_j_0 for some 1 < j_0 < m-r.
Consequently, by Lemma <ref> and Lemma <ref>, there exists
a basis 
    β̂ := {ŷ_1(λ), …, ŷ_m-r(λ), u_m-r+1, …, u_m-r+c}
 of N_l(L) such that ℒ_v(ŷ_j(λ)) = ẑ_j(λ) and deg ŷ_j = deg ẑ_j for j = 1, …, m-r.  The sum of the degrees of the vector polynomials in β̂ are clearly lower than that of the ones in β as, deg ẑ_j_0 < deg  z_j_0. But this contradicts the fact that β is a minimal basis of N_l(L). Hence the proof follows. 


A minimal basis of N_l(P) may be extracted from a basis of N_l(L) that satisfies the assumptions of Lemma <ref>. We outline the steps for constructing such a basis from any given minimal basis of N_l(L).


 
  * Let {y_1(λ),…,y_t(λ),y_t+1(λ),…, y_m-r+c(λ)} be a minimal basis of N_l(L) with deg  y_i = d_i such that d_1 ≥ d_2 ≥⋯≥ d_m-r+c. Without loss of generality we may assume that there exists 1 ≤ t ≤ m-r such that d_i > 0 for i=1,…,t and d_i = 0 for i = t+1, …, m-r+c.

 
  * Consider u_m-r+j=(M^T⊗ I_m)[[   0; v_j ]], for j=1,…,c such that {v_1,…,v_c} forms a basis of left null space of Z. Such a basis may be obtained by choosing v_1, …, v_c to be the complex conjugate transpose of the last c columns of the matrix Q of a QR decomposition of Z. Then u_m-r+j belongs to N_l(L) and ℒ_v(u_m-r+j)=0 for j=1,…,c.

 
  * Clearly the set β={y_1(λ),…,y_t(λ),u_m-r+1,…,u_m-r+c} is linearly independent. Check if  y_t+1(λ) belongs to span(β), and include it in β if this is not the case. Repeat the process for i = t+2, …, m-r+c with respect to the updated β after each step.



 There are situations when left minimal bases of L(λ) ∈Ł_1(P)
will generically satisfy the assumptions in Lemma <ref>. For example if  n < m ≤ (k+1)n, then generically, 𝒜 := [[ A_0   ⋯ A_k ]] is a full rank matrix and consequently, none of the left minimal indices of P(λ) are zero. Consequently, there does not exist any vector polynomial of degree zero in a left minimal basis of L(λ) that does not belong to N(ℒ_v). This implies that any such basis must satisfy the assumptions of Lemma <ref>.


The preceding results imply that if P(λ) ∈[λ]^m × n with m≤  n, then the right minimal bases and indices of P(λ) can be extracted from those of L(λ) ∈Ł_2(P) of full Z-rank. In particular we have in this case the following counterpart of Lemma <ref>  which can either be proved by arguing as in the proof of Lemma <ref> or by using the relation (<ref>).


 Let P(λ) = ∑_i = 0^k λ^iA_i be an m× n matrix polynomial of grade k with m ≤ n. Suppose L(λ)∈𝕃_2(P) has full Z-rank and nonzero left ansatz vector w ∈^k. Then the mapping
 
    ℒ_w:N_r(L)    →    N_r(P)
    
     x(λ)    ↦    (w^T⊗ I_n)x(λ)

 is a linear map from the vector space N_r(L) onto the vector space N_r(P) over (λ). Furthermore it is an onto map from the vector polynomials in N_r(L) to the vector polynomials in N_r(P) with the property that if q(λ) ∈ N_r(P) is a vector polynomial of degree δ, then there exists a vector polynomial x(λ) ∈ N_r(L) of degree δ such that ℒ_w(x(λ)) = q(λ).


Therefore, by arguing as in the proof of Lemma <ref>, there exists a minimal basis of N_r(L) of the form 
    {x_1(λ), …, x_n-r(λ), u_n-r+1, …, u_n-r+c},
 where  c = (n-m)(k-1) and {u_n-r+1,…,u_n-r+c}⊂^kn is a basis of N(ℒ_w). This leads to the following theorem for extracting the right minimal indices and bases of P(λ) from those of L(λ) ∈Ł_2(P) with full Z-rank.

 Let P(λ) be an m × n matrix polynomial of grade k with m≤ n, and L(λ) ∈Ł_2(P) with corresponding nonzero left ansatz vector w ∈^k be of full Z-rank. Let r = nrank  P(λ), c = (k-1)(n-m) and ℒ_w(x(λ)) = (w^T ⊗ I_n)x(λ) for all x(λ) ∈ N_r(L).
 If β={x_1(λ),…, x_n-r(λ),u_n-r+1,…,u_n-r+c} be a minimal basis of N_r(L) such that {u_n-r+1,…,u_n-r+c}⊂^kn is a basis of N(ℒ_w), then the set {ℒ_w(x_1(λ)),…,ℒ_w(x_n-r(λ))} is a minimal basis of N_r(P). Moreover if δ_1≥δ_2≥…≥δ_n-r≥ 0=0=…=0_c   zeros are the right minimal indices of L(λ) then δ_1≥δ_2≥…≥δ_n-r are the right minimal indices of P(λ).




§ LINEARIZATIONS ARISING FROM G-LINEARIZATIONS


Let P(λ) = ∑_i=0^k λ^i A_i be an m × n matrix polynomial of grade k. In this section we show that although the pencils in Ł_1(P) and Ł_2(P) are generically g-linearizations of P(λ), they can give rise to smaller pencils that are linearizations of P(λ) from which the left and right minimal bases and indices of P(λ) may be easily extracted. In the following we first describe the process of extracting these smaller pencils from g-linearizations of P(λ) of full Z-rank in Ł_1(P) when m≥ n.


Let L(λ) ∈Ł_1(P) with nonzero right ansatz vector v ∈^k be of full Z-rank. Let M ∈^k × k be a nonsingular matrix such that Mv = α e_1. From (<ref>), (M ⊗ I_m)L(λ)=[[ P(λ) W(λ);         Z ]](F(λ))^-1. Let

    Z = Q[ R̃;  0 ]

 be a  QR decomposition of  Z where Q ∈^(k-1)m × (k-1)m is an unitary matrix and R̃∈^(k-1)n × (k-1)n nonsingular and upper triangular. Then we have,




    [ I_m; Q^* ](M⊗ I_m)L(λ)=[[ P(λ) W(λ);        R̃;         0 ]]( F(λ))^-1,

 



Let Q = [[ Q_1 Q_2 ]], be a partition of Q such that Z = Q_1R̃ is the condensed QR decomposition of Z. Then recalling that c = (k-1)(m-n), the submatrix formed by the last c rows of the matrix [ I_m; Q^* ](M⊗ I_m) L(λ) is [     0 Q_2^* ](M⊗ I_m) L(λ). Since the last c rows of the matrix on the RHS of  (<ref>) are zero, we have  [     0 Q_2^* ](M⊗ I_m) L(λ)=0. Consider D ∈𝔽^m+(k-1)n× km such that 
    [                       D; [     0 Q_2^* ](M⊗ I_m) ]
 is nonsingular. Then [                       D; [     0 Q_2^* ](M⊗ I_m) ]L(λ)=[ DL(λ);     0 ]. We set,




    L_t(λ)=DL(λ).




Given a g-linearization L(λ) ∈Ł_1(P) of full Z-rank, the above process of extracting the pencil L_t(λ) from L(λ)  clearly depends not only on L(λ) but also on the choice of the nonsingular matrix M ∈^k × k satisfying Mv = α e_1 and the matrix D∈^m+(k-1)n × km such that the matrix in (<ref>) is nonsingular. For ease of expression, We will refer to L_t(λ) as  the trimmed version of L(λ) ∈Ł_1(P), with respect to M and D, the sizes of the matrices M and D being evident from the context.

Clearly, for a given choice of nonsingular M ∈^k × k, there are infinitely many choices of D in (<ref>). One possible choice is to set D to be the first m + (k-1)n rows of [ I_m; Q^* ](M⊗ I_m). Then the corresponding linearization is

    L̂_t(λ) := λ[[ α A_k  X_12;         -R̃ ]]+[[  Y_11 α A_0;    R̃       ]].

If L(λ) = C_1^g(λ), then such a choice of D results in L_t(λ) being the first Frobenius companion linearization C_1(λ).  Every other linearization L_t(λ) that is not of the form (<ref>) is strictly equivalent to some L̂_t(λ) as


    L_t(λ)    =    DL(λ)
       =    D(M^-1⊗ I_m){λ[[ α A_k  X_12;          -Z ]]+[[  Y_11 α A_0;     Z       ]]}
       =    D(M^-1⊗ I_m)[ I_m;   Q ]{λ[[ α A_k  X_12;         -R̃;     0 ]]+[[  Y_11 α A_0;    R̃      ;     0 ]]}
       =    D(M^-1⊗ I_m)[ I_m; Q_1 ]_= E_1{λ[[ α A_k  X_12;         -R̃ ]]+[[  Y_11 α A_0;    R̃ ]]}
       =   DE_1_=:D̃L̂_t(λ).

where clearly, D̃∈^m+(k-1)n × m+(k-1)n is nonsingular as it satisfies

    [[           D̃            *;              I_(k-1)(m-n) ]] = [                       D; [     0 Q_2^* ](M⊗ I_m) ](M^-1⊗ I_m)[ I_m;   Q ].



 The QR decomposition of the Z-matrix of the g-linearization L(λ) that has been used to extract the pencils L_t(λ), from L(λ) can easily be replaced by any other decomposition like the rank revealing QR decomposition or the SVD of Z without affecting the results and the analysis concerning these pencils. Therefore, the upper triangular structure of the block R̃ in (<ref>) is not essential for the rest of the paper.





 §.§ Trimming a g-linearization results in a strong linearization


 We now show that trimming a g-linearization of full Z-rank results in a strong linearization of P(λ) from which the left and right minimal bases and indices of P(λ) can easily be recovered. In doing so, we establish the connection between the resulting pencils with some of the important classes of linearizations for rectangular matrix polynomials that have been recently introduced in the literature. We begin with the block minimal bases pencils introduced in <cit.>.

 A block minimal bases pencil is a pencil of the form 
    [[    A(λ) B̂(λ)^T;    B(λ)         ]], [[ A(λ); B(λ) ]] [[    A(λ) B̂(λ)^T ]]

where the rows of B(λ) and B̂(λ) form minimal bases of the rational subspaces spanned by them.


We will need a few important concepts and results related to block minimal bases pencils from <cit.>. For convenience, following <cit.>,  we refer to a matrix polynomial whose rows form a minimal basis of the rational subspace spanned by them as a minimal basis. Such a minimal basis can be associated with a dual minimal basis defined as follows.

 A pair of minimal bases B(λ) ∈[λ]^n_1 × n and C(λ) ∈[λ]^n_2 × n are called dual minimal bases if n_1 + n_2 = n and B(λ)C(λ)^T = 0.


For example, the matrix polynomials

    H_j(λ)=[[ -1  λ         ;    -1  λ      ;        ⋱  ⋱   ;          -1  λ ]]_j × (j+1).

and Λ_j+1(λ)^T given by (<ref>) are dual minimal bases. For most practical purposes, we will need the following special kind of block minimal bases from <cit.>.


A block minimal bases pencil 
    L(λ) = [[     A(λ) B̂ (λ)^T;     B(λ)        0 ]]
 is called a strong block minimal bases pencil if it has the following additional properties:




  (a) The row degrees of B(λ) and B̂(λ) are all equal to one.

  (b) The row degrees of any minimal basis dual to B(λ) are all equal.

  (c) The row degrees of any minimal basis dual to B̂(λ) are all equal.




We will adopt the convention that if the block B(λ) (B̂(λ)) is absent, then the corresponding dual minimal basis is an identity matrix of the same size as the number of columns (rows) of A(λ). The following theorem about block minimal bases pencils which is a combination of  <cit.> will be important for the results in this section and the next one.

 Let L(λ) be a minimal bases pencil given by (<ref>) and C(λ) and Ĉ(λ) be the dual minimal bases of B(λ) and B̂(λ) respectively. Then L(λ) is a linearization of the matrix polynomial

    Q(λ) = Ĉ(λ)A(λ)C(λ)^T.

Moreover, if L(λ) is a strong block minimal bases pencil, then the following hold.



  (a) L(λ) is a strong linearization of Q(λ) considered as a polynomial of grade 1 + deg  C + deg Ĉ.

  (b) If 0 ≤ϵ_1 ≤ϵ_2 ≤⋯≤ϵ_p are the right minimal indices of Q(λ), then 
    ϵ_1 +   C ≤ϵ_2 +   C ≤⋯≤ϵ_p +   C,

    are the right minimal bases of L(λ).

  (c) If 0 ≤η_1 ≤η_2 ≤⋯≤η_q are the left minimal indices of Q(λ), then 
    η_1 +  Ĉ≤η_2 +  Ĉ≤⋯≤η_q +  Ĉ
 are the left minimal indices of L(λ).



Given a strong block minimal bases pencil, the above result shows the construction of a polynomial from the pencil such that the pencil is a strong linearization of the polynomial and lays out the recovery rules for extracting left and right minimal indices of the polynomial from those of the pencil. However in practice, we are generally more interested in the reverse process, i.e., given a matrix polynomial Q(λ) of grade k, we are interested in constructing a strong linearization from which the left and right minimal indices of the polynomial can be easily extracted. It was shown in <cit.>, that this easily achieved by the so called Block Kronecker pencils that are a special class of strong  block minimal bases pencils for which 
    B̂(λ)=H_ϵ(λ) ⊗ I_m  B(λ) =H_η(λ) ⊗ I_n
 with ϵ + η + 1 = k, and H_j(λ) given by (<ref>).  The conditions on the block A(λ) under which the Block Kronecker pencils become strong linearizations of a given polynomial P(λ) are given in <cit.>.  Now we have the main result of this section.






























 Let P(λ) = ∑_i=0^k λ^iA_i be an m × n matrix polynomial of grade k with m≥ n and r = nrank P(λ). Let L(λ) ∈Ł_1(P) with right ansatz vector v ∈^k ∖{0} be of full Z-rank. Let L_t(λ) be the pencil obtained by trimming L(λ) ∈Ł_1(P), with respect to M and D.
Then L_t(λ) is a strong linearization of P(λ) such that the following hold.




  (a) Every minimal basis of N_r(L_t) is of the form  {Λ_k(λ) ⊗ x_1(λ), …, Λ_k(λ) ⊗ x_n-r(λ)} where 
 { x_1(λ), …, x_n-r(λ)} is a minimal basis of N_r(P).


  (b) The right minimal indices of L_t(λ) are those of P(λ) shifted by k-1.


  (c) Every minimal basis of N_l(P) is of the form {(v^T⊗ I_m)D^Ty_1(λ), …, (v^T⊗ I_m)D^Ty_m-r(λ)} where {y_1(λ), …, y_m-r(λ)} is a minimal basis of N_l(L_t).


  (d) The left minimal indices of P(λ) are equal to those of L_t(λ).





From (<ref>) and (<ref>),

    L_t(λ) := D̃[[ I_m    ;      R̃ ]] λ[[     α A_k      X_12;           -I_(k-1)n ]]+[[     Y_11    α A_0; I_(k-1)n          ]]_=: K(λ)


Clearly K(λ) is in the Block Kronecker form [[ A(λ); B(λ) ]] with 
    A(λ) := λ[[ α A_k  X_12 ]] + [[  Y_11 α A_0 ]]  B(λ) = H_k-1(λ) ⊗ I_n.
 Now A(λ)C(λ)^T = P(λ), where C(λ) = 1/α(Λ_k(λ) ⊗ I_n)^T is a dual of B(λ). As the block B̂(λ) is absent in K(λ) (and consequently, Ĉ(λ) = I_m,) by Theorem <ref>, K(λ) is   a strong linearization of P(λ) such that P(λ) and K(λ) have the same left minimal indices and the right minimal indices of K(λ) are those of P(λ) shifted by k-1. The relation (<ref>), shows that the same is true of each pencil L_t(λ) obtained by trimming a strong g-linearization in 𝕃_1(P) and this proves (b) and (d).

The process of obtaining L_t(λ) from L(λ)  implies that N_r(L) = N_r(L_t). Therefore the proof of (a) follows from Theorem <ref>.
To prove (c) we consider the map
 
    ℒ:N_l(L_t)    →    N_l(P)
    
     y(λ)    ↦   ℒ_v(D^Ty(λ))

 If y(λ)∈ N_l(L_t) then D^Ty(λ)∈ N_l(L) ⊂ N_l(P), and therefore ℒ is well defined. Also from the definition of ℒ it is clear that it is a linear map from N_l(L_t) to N_l(P). We first show that ℒ is bijective. Let Z be the Z-matrix of (M ⊗ I_n)L(λ) and Q_2 be the last c = (k-1)(m-n) columns of the unitary matrix Q of a QR decomposition of Z. Now y(λ) ∈ N(ℒ) if and only if D^Ty(λ) ∈ N(ℒ_v).
 As noted in Remark <ref>, there exists a basis of N(ℒ_v) of the form
 {(M^T⊗ I_m)[   0; q_1 ],…, (M^T⊗ I_m)[   0; q_c ]} where c=(k-1)(m-n) and {q̅_1,…, q̅_c} are the columns of Q_2. Therefore there exists a nonzero a ∈^c such that 
    D^Ty(λ) = (M^T ⊗ I_m) [ I_m; Q_2 ][ 0; a ] = (M^T ⊗ I_m) [    0; Q_2a ].

This implies that
[ y(λ);   -a ]^T[                           D; [[     0 Q_2^* ]] (M ⊗ I_m) ]= 0, which gives y(λ)=0 as [                           D; [[     0 Q_2^* ]] (M ⊗ I_m) ] is nonsingular. Therefore ℒ is a one to one linear map. Since N_l(L_t) and N_l(P) are of the same dimension, it follows that ℒ is a bijective linear map.

Now we will show for any vector polynomial p(λ)∈ N_l(P) of degree δ we can find a polynomial vector z(λ)∈ N_l(L_t) of degree δ such that  ℒ(z(λ))=p(λ). By Lemma <ref> ∃ ẑ(λ)∈ N_l(L) such that ℒ_v(ẑ(λ))=p(λ) and deg ẑ=deg  p. Let z(λ) be the first with m + (k-1)n entries of a vector polynomial ŷ(λ) which satisfies [                          D; [[     0 Q_2^* ]](M ⊗ I_m) ]^Tŷ(λ) = ẑ(λ). Then z(λ) ∈ N_l(L_t) as,

    z(λ)^TL_t(λ) = ŷ(λ)^T[[ L_t(λ);    0_c ]] = ŷ(λ)^T[                          D; [[     0 Q_2^* ]](M ⊗ I_m) ]L(λ) = ẑ(λ)^TL(λ) = 0.


Now as (v^T ⊗ I_m)(M^T ⊗ I_m)[[ 0_m+(k-1)n;     Q̅_̅2̅ ]] = (α e_1^T ⊗ I_m)[[ 0_m+(k-1)n;     Q̅_̅2̅ ]] = 0, we have 
    ℒ (z(λ)) = (v^T ⊗ I_m)D^Tz(λ) = (v^T ⊗ I_m)[                          D; [[     0 Q_2^* ]](M ⊗ I_m) ]^Tŷ(λ) = ℒ_v (ẑ (λ)) = p(λ).

Also it is clear that z(λ) and p(λ)  have the same degree as 
    z  ≥  p =  ẑ =  ŷ≥  z.
  Now the proof of part (c) follows by arguing as in the proof of Theorem <ref>. 

 It can be proved that the pencils L_t(λ) are strong linearizations of P(λ) without establishing their connection with Block Kronecker pencils. However, we prefer to give this connection to highlight their position in the current literature of strong linearizations of rectangular matrix polynomials. In fact it is also clear from (<ref>) that among the linearizations formed by trimming g-linearizations in Ł_1(P), only the pencils L̂_t(λ) of the form (<ref>) belong to the Block Kronecker ansatz spaces 𝔾_1(P) introduced in <cit.>.



The recovery rules for the left and right minimal bases of P(λ) from those of L_t(λ) may also be derived from <cit.> which gives the rules for extracting the same for general Block Kronecker linearizations. However, as the pencils K(λ) in (<ref>) to which the pencils L_t(λ) are strictly equivalent are special types of Block Kronecker pencils, we prefer to prove these parts directly by using the notions and techniques previously introduced in the paper.


In a similar way, if m≤ n, pencils in Ł_2(P) of full Z-rank can provide strong linearizations of P(λ). In particular if L(λ) ∈Ł_2(P) with nonzero left ansatz vector w ∈^k has full Z-rank,  then for any nonsingular matrix M̂∈^k × k such that M̂w = α e_1 for some α≠ 0, 
    L(λ)(M̂^T ⊗ I_n) = λ[[ α A_k      ; X̂_12    -Ẑ ]] + [[  Ŷ_11     Ẑ; α A_0       ]],

where Ẑ∈^(k-1)m × (k-1)n with Ẑ = (k-1)m. If Ẑ^* = Q [[ R̂;  0 ]], be a QR decomposition of Ẑ^* and Q_2 is  the matrix formed by the last c = (k-1)(n-m) columns of Q, then it is easy to see that 
    L(λ)(M̂^T ⊗ I_n)[[   0; Q_2 ]] = 0.
 For any choice of D̂∈^kn × (n + (k-1)m), such that the kn × kn matrix

    [[                               D̂ (M̂^T ⊗ I_n) [[     0 Q_2^T ]]^T ]]

is nonsingular, we get the pencils L(λ) D̂. We refer to them as the pencils formed by trimming L(λ) ∈Ł_2(P), with respect to M̂ and D̂. For instance, the second companion linearization C_2(λ) arises from C_2^g(λ) ∈Ł_2(P), with respect to M̂ = I_k and D̂ = [[          I_n             ;              I_k-1⊗ I_n,m ]].

By arguing as in the proof of Theorem <ref>, these pencils can be shown to be strictly equivalent to Block Kronecker linearizations of P(λ) of the form [[             A(λ) H_k-1(λ)^T ⊗ I_m ]] from which the left and right minimal bases and indices of P(λ) may be easily extracted. In fact we have the following theorem.

 Let P(λ) = ∑_i=0^k λ^iA_i be an m × n matrix polynomial of grade k with m≤ n and r = nrank P(λ). Let L(λ) ∈Ł_2(P) with left ansatz vector w ∈^k ∖{0} be of full Z-rank. Let L_t(λ) be the pencil formed by trimming L(λ) ∈Ł_2(P), with respect to M̂ and D̂. Then L_t(λ) is a strong linearization of P(λ) and the following hold.




  (a) Every minimal basis of N_l(L_t) is of the form  {Λ_k(λ) ⊗ y_1(λ), …, Λ_k(λ) ⊗ y_m-r(λ)} where 
 { y_1(λ), …, y_m-r(λ)} is a minimal basis of N_l(P).


  (b) The left minimal indices of L_t(λ) are those of P(λ) shifted by k-1.


  (c) Every minimal basis of N_r(P) is of the form {(w^T⊗ I_n)D̂x_1(λ), …, (w^T⊗ I_n)D̂x_n-r(λ)} where {x_1(λ), …, x_n-r(λ)} is a minimal basis of N_r(L_t).


  (d) The right minimal indices of P(λ) are equal to those of L_t(λ).




 For L(λ) ∈𝕃_2(P) of full Z-rank with left ansatz vector w ∈^k ∖{0} and a given choice of M̂∈^k × k such that M̂w = α e_1, if the matrix D̂ in (<ref>) is chosen to be the first n + (k-1)m columns of (M̂^T ⊗ I_n) [[ I_n    ;       Q ]], then in fact, the resulting pencil belongs to the Block Kronecker ansatz space 𝔾_k(P) introduced in <cit.>. Also every other pencil formed by trimming L(λ) with respect to M̂ and some other choice of D̂ is strictly equivalent to such a pencil but does not belong to 𝔾_k(P).



As the following example shows, the linearizations L_t(λ) arising from the pencils of full Z-rank in Ł_1(P) and Ł_2(P) are not subclasses of the class of block minimal bases linearizations.

  Consider P(λ) = λ^2 A_2 + λ A_1 + A_0 where 
    A_2 = [[ 1 2; 2 5; 4 9 ]],   A_1 = [[  3  4;  9  2; 15 10 ]],  A_0 = [[  1  7;  2  5;  4 19 ]].

 Then L(λ) = λX̂ + Ŷ∈Ł_1(P) where 
    X̂ = [[  0  0 -1  0;  0  0  0 -1;  0  0  0  0;  1  2  0  0;  2  5  0  0;  4  9  0  0 ]],  Ŷ = [[  1  0  0  0;  0  1  0  0;  0  0  0  0;  3  4  1  7;  9  2  2  5; 15 10  4 19 ]],
 with corresponding right ansatz vector vector v = [[ 0; 1 ]]. Now [[ 0 1; 1 0 ]]_= : Mv = [[ 1; 0 ]], and 
    (M ⊗ I_3)L(λ) = λ X + Y,
 where
 
 
    X  =  (M ⊗ I_3)X̂ = [[  1  2  0  0;  2  5  0  0;  4  9  0  0;  0  0 -1  0;  0  0  0 -1;  0  0  0  0 ]], 
     Y  =  (M ⊗ I_3)Ŷ = [[  3  4  1  7;  9 12  2  5; 15 10  4 19;  1  0  0  0;  0  1  0  0;  0  0  0  0 ]].


 Clearly, Z = [[ 1 0; 0 1; 0 0 ]] is full rank with QR decomposition Z = I_3 Z. Hence, 
    [[     0 Q_2^* ]](M^T ⊗ I_3) = [[ 0 0 1 0 0 0 ]], [[  1  0  0  0  0  0;  0  1  0  0  0  0;  0  0  0  1  0  0;  0  0  0  0  1  0;  0  0  0 -2 -1  1;  0  0  1  0  0  0 ]]
 is nonsingular.  So, 
    L_t(λ) := [[  1  0  0  0  0  0;  0  1  0  0  0  0;  0  0  0  1  0  0;  0  0  0  0  1  0;  0  0  0 -2 -1  1 ]] L(λ) = λ[[  0  0 -1  0;  0  0  0 -1;  1  2  0  0;  2  5  0  0;  0  0  0  0 ]] + [[ 1 0 0 0; 0 1 0 0; 3 4 1 7; 9 2 2 5; 0 0 0 0 ]],
 is a strong linearization of P(λ). Evidently it is not a block minimal bases linearization.
 


 It is clear that if m≥ n the size  (m+(k-1)n)× kn of L_t(λ) is the same as that of the first Frobenius companion linearization C_1(λ) of P(λ).  On the other hand, if m≤ n, then L_t(λ) is of size km × (n + (k-1)m) which is the same as that of the second Frobenius companion linearization C_2(λ). Since C_1(λ) and C_2(λ) are the smallest among all possible Fiedler and Block Kronecker linearizations of P(λ), therefore, the size of L_t(λ) is less than or equal to that of all such linearizations for rectangular matrix polynomials.
 


Although the pencils L_t(λ) are extracted from g-linearizations in Ł_1(P) and Ł_2(P), in practice, it is not necessary to form them by trimming g-linearizations. For example we can directly build these linearizations from a given matrix polynomial P(λ) = ∑_i=0^k λ^i A_i, of grade k and m > n,  by using the fact that they are of the form L_t(λ) := D̃(λ[[ α A_k  X_12;         -R̃ ]]+[[  Y_11 α A_0;    R̃       ]] ) where α≠ 0, X_12+Y_11=α[ A_k-1     …   A_1 ] and D̃∈^m + (k-1)n × m + (k-1)n and R̃∈^(k-1)n × (k-1)n are nonsingular. The process of trimming g-linearizations to form linearizations of this type can be seen as a means to connect the g-linearizations of P(λ) with linearizations.


 In the next section we undertake a global backward stability analysis of the solution of polynomial eigenvalue problems using L_t(λ) on the lines of the analysis in <cit.> and show that their is in fact a wide choice of optimal strong linearizations (beyond the ones identified in <cit.>) which can be used to solve the complete eigenvalue problem for P(λ) in a globally backward stable manner.






§ GLOBAL BACKWARD ERROR ANALYSIS OF SOLUTIONS OF POLYNOMIAL EIGENVALUE PROBLEMS USING LINEARIZATIONS ARISING FROM G-LINEARIZATIONS


In this section we carry out a global backward error analysis of the process of solving the complete eigenvalue problem associated with a rectangular matrix polynomial P(λ) = ∑_i = 0^k λ^i A_i ∈[λ]^m × n of grade k by using linearizations that arise from a g-linearization in 𝕃_1(P) or 𝕃_2(P). It will be an extension of the one in <cit.> for Block Kronecker linearizations. As mentioned in Section <ref>, any solution of such a problem involves finding the finite and infinite eigenvalues and associated elementary divisors as well as the left and right minimal bases and indices of P(λ). Typically this is done by initially finding the said quantities for some choice of strong linearization via very effective backward stable methods like the staircase algorithm proposed in <cit.> and further developed in <cit.>. The backward stability of such algorithms guarantee that any computed solution of the eigenvalue problem corresponding to a linearization say, L(λ) of P(λ), is the exact solution of the problem for a pencil L(λ) + Δ L(λ) where Δ L/L = O(u) with respect to some norm ·. The solution of the complete eigenvalue problem for P(λ) is then computed from the solution for L(λ) + Δ L(λ) by applying the same recovery rules to L(λ) + Δ L(λ) that would have been applied to the solution for L(λ) if it were available. Following <cit.>, the process is said to be globally backward stable if it is the  exact solution of the complete eigenvalue problem for P(λ) + Δ P(λ) with the following conditions being met.



 
  (a) If P(λ) is of grade k,  the perturbed pencil L(λ) + Δ L(λ) a strong linearization of P(λ) + Δ P(λ) of grade k such that Δ P / P  = O( u).
 
  (b) The rules for extracting the left and right minimal indices of P(λ) from those of L(λ) remain the same when they are replaced by P(λ) + Δ P(λ) and L(λ) + Δ L(λ) respectively.
 

 The analysis in <cit.>, showed that (a) and (b) are satisfied for optimal choices of Block Kronecker linearization of P(λ) with respect to the norm 
    P _F := √(∑_i = 0^k  A_i_F^2)
 where A _F := √(trace  (A^*A)) is the Frobenius norm of A. In particular, it was shown that there exists a constant C_P, L depending on P(λ) and L(λ) such that 
    Δ P_F/P_F≤ C_P, LΔ L _F/ L _F,
 where, C_P, L≈ k^3√(m + n) under certain conditions that are satisfied by appropriate choice of Block Kronecker linearizations and scaling of P(λ).

 We establish that the same analysis can be extended to solutions obtained via linearizations L_t(λ) of P(λ) ∈[λ]^m × n that arise from g-linearizations in Ł_1(P) when m > n. Similar arguments can easily complete the corresponding analysis for the case m < n with respect to linearizations that arise from g-linearizations in 𝕃_2(P).

Our choice of norm  P _F on [λ]^m × n considered as a vector space over   is not submultiplicative.  The following  lemma from <cit.> which bounds the Frobenius norm of the product of two matrix polynomials will therefore be useful in the analysis. For notational convenience in this section we set  
    Λ_k,p(λ):=(Λ_k(λ)⊗ I_p), PQ(λ):=P(λ)Q(λ)  (P+Q)(λ):=P(λ)+Q(λ),
 for two matrix polynomials P(λ) and Q(λ) for which the above products and sums are defined.


 Let P(λ)=∑_i=0^d_1A_iλ^i and Q(λ)=∑_i=0^d_2B_iλ^i be two matrix polynomials and such that all the products below are defined. Then the following inequalities hold.

 
  
  * PQ_F ≤min{√(d_1+1),√(d_2+1)}P_FQ_F
  
  * PΛ_k,p_F ≤min{√(d_1+1),√(k)}P_F
 



Initially we analyse the global backward stability of the process of computing a solution of the complete eigenvalue problem for P(λ) arising from linearizations of the form (<ref>). Later on we will extend this analysis to the case where any linearization L_t(λ) arising from a g-linearization in 𝕃_1(P)
is used.



 Since the matrix R̃∈^(k-1)n of L̂_t(λ) given by (<ref>) is upper triangular and nonsingular, L̂_t(λ) is a strong block minimal bases pencil of the form 
    [[ A(λ); B(λ) ]]
 where,

    A(λ)     =    λ[[ α A_k  X_12 ]], + [[  Y_11 α A_0 ]],
    
    B(λ)     =    λ[[ 0_(k-1)n × n          -R̃ ]] +
    [[           R̃ 0_(k-1)n × n ]].

Note that Λ_k,n(λ)^T is a dual minimal basis of B(λ).

Any computed solution of the complete eigenvalue problem associated with L̂_t(λ) is an exact solution of a perturbed pencil L̂_t(λ) + ΔL̂_t(λ) where 
    ΔL̂_t(λ)=[[ Δ A(λ); Δ B(λ) ]]
 with  Δ A(λ)∈𝔽[λ]^m× kn and Δ B(λ)∈𝔽[λ]^(k-1)n× kn so that 
    L̂_t(λ) + ΔL̂_t(λ) = [[ A(λ) + Δ A(λ); B(λ) + Δ B(λ) ]].
 Our initial aim is to show that for small enough ΔL̂_t_F, L̂_t(λ) + ΔL̂_t(λ) is a strong block minimal bases linearization of some perturbed polynomial P(λ) + Δ P(λ) of grade k such that Δ P_F/P_F is bounded above by a small multiple of ΔL̂_t_F/L̂_t_F.

 We establish an upper bound on Δ B_F such that L̂_t(λ) + ΔL̂_t(λ) is a strong block minimal bases pencil. This requires that the following conditions are satisfied.

Condition (A) B(λ) + Δ B(λ) is a minimal basis with all row degrees equal to one;

Condition (B) There exists a matrix polynomial Δ D(λ) ∈[λ]^kn × n of grade k-1 such that Λ_k,n(λ)^T + Δ D(λ)^T is a dual minimal basis of B(λ) + Δ B(λ) with all row degrees equal to k-1.








































































Following the strategy in <cit.>, we will use the concept of convolution matrices associated with P(λ)= ∑_i=0^kA_iλ^i  which are defined as follows.

    C_j(P)=[   A_k; A_k-1   A_k;     ⋮ A_k-1     ⋱;   A_0     ⋮     ⋱   A_k;         A_0       A_k-1;           ⋱     ⋮;         A_0 ]_j+1 block columns j=0,1,2,….


The following lemma which states some important and useful properties of convolution matrices can be easily proved.

 Let P(λ)= ∑_i=0^kA_iλ^i and Q(λ)= ∑_i=0^lB_iλ^i be matrix polynomials of grade k and l respectively and C_j(P) and C_j(Q) for j=0,1,2,…, be corresponding convolution matrices as given by (<ref>).

 
  (a) If P(λ) and Q(λ) are of same size and grade then C_j(P + Q)=C_j(P)+C_j(Q) for all j.
 
  (b) C_j(P)_F=√(j+1)P_F for all j.
 
  (c) If the product P(λ)Q(λ) is defined, then considering it as a grade k+l matrix polynomial, we have C_0(PQ)=C_l(P)C_0(Q).



The next Theorem from <cit.> for convolution matrices will be useful to show that for sufficiently small Δ B _F, B(λ) + Δ B(λ) can be a minimal basis with all row degrees equal to 1.

 For any positive integer l, let N(λ) = A + λ B ∈[λ]^ln × (l+1)n and C_j(N) for j = 0, 1, …, be the sequence of convolution matrices of N(λ). Then N(λ) is a minimal basis with all its row degrees equal to 1 and all the row degrees of any dual minimal basis equal to l, if and only if C_l-1(N) ∈^(l+1)l n × (l+1) l n is nonsingular and C_l(N) ∈^l(l+2)n × (l+1)^2 n has full row rank.


Observing that B(λ) = R̃ (H_k-1(λ) ⊗ I_n) where H_k-1(λ) is given by (<ref>),



the next lemma which is proved in the appendix will be useful in establishing a bound on Δ B_F that achieves the desired objectives. [A proof of this result is available in <cit.> which is a revised version of <cit.>. Our proof was made independently and with different arguments.]



For τ(λ) := (H_k-1(λ) ⊗ I_n),  σ_min(C_k-2(τ))= σ_min(C_k-1(τ))=2sin(π/4k-2)≥3/2k.


The following result bounds Δ B_F such that B(λ) + Δ B(λ) is a minimal basis with all row degrees equal to 1.


   Let B(λ) be the pencil given by (<ref>), and Δ B(λ)∈𝔽[λ]^(k-1)n× kn be any pencil such that
   
    Δ B_F < 3 σ_min(R̃)/2k^3/2.
  Then B(λ)+Δ B(λ) is a minimal basis with all its row degrees equal to 1 and all row degrees of any minimal basis dual to it equal to k-1.



In view of Theorem <ref>,  the proof follows by establishing that C_k-2(B+Δ B) is nonsingular and C_k-1(B+Δ B) has full row rank.
 For j = k-1  k-2,

    σ_min(C_j(B)) =  σ_min([ R̃;  ⋱; R̃ ]C_j(τ))
     ≥σ_min(R̃)σ_min(C_j(τ)).

  Therefore by Lemma <ref>,
  
    σ_min(C_j(B)) ≥ 2σ_min(R̃)sinπ/4k-2≥σ_min(R̃)3/2k.

  Since R̃ is nonsingular, it follows that C_k-2(B) is nonsingular and C_k-1(B) has full row rank. By Lemma <ref>(a),
  
    C_j(B+Δ B)=C_j(B)+C_j(Δ B)
 for j = k-1 and k-2. Therefore  C_k-2(B+Δ B) is nonsingular and C_k-1(B+Δ B) has full row rank if C_j(Δ B)_F<σ_min(C_j(B))  for both values of j. But both inequalities follow from Lemma <ref>(b), and the relations (<ref>) and (<ref>). Hence the proof. 





Now the following result establishes the required upper bound on Δ B_F such that both Condition (A) and Condition (B) are fulfilled. The proof is omitted as it follows by arguing as in the proof of <cit.>.


 Let B(λ) be the pencil given by (<ref>) and Δ B(λ)∈𝔽[λ]^(k-1)n× kn be any pencil such that
 
    Δ B_F<σ_min(R̃)/2k^3/2.

  Then there exists a matrix polynomial Δ D(λ)∈𝔽[λ]^kn× n of grade k-1 such that
 
  
  (a) B(λ)+Δ B(λ) and Λ_k,n(λ)^T+Δ D(λ)^T are dual minimal bases, with all the row degrees equal to 1 and k-1 respectively, and
  
  (b) Δ D_F≤k√(2)/σ_min(R̃)Δ B_F<1/√(2k).
 

























Next we have the main result which completes the global backward error analysis for solutions of the complete eigenvalue problem for P(λ) obtained from the linearizations L̂_t(λ).


Let L̂_t(λ) be any linearization of P(λ) = ∑_i=0^k λ^iA_i ∈[λ]^m × n of grade k with m > n, of the form (<ref>).
Let A(λ) and B(λ) be the blocks of L̂_t(λ) as specified by (<ref>) and (<ref>) respectively and R̃∈^m + (k-1)n be the nonsingular upper triangular matrix appearing in the block B(λ).
  If ΔL̂_t(λ) is any pencil of the same size as L̂_t(λ) such that
  
    ΔL̂_t_F<σ_min(R̃)/2k^3/2

  then L̂_t(λ)+ΔL̂_t(λ) is a strong linearization of a matrix polynomial P(λ)+Δ P(λ) of grade k and
  
    Δ P_F/P_F≤Ĉ_L̂_t, PΔL̂_t_F/L̂_t_F

  where Ĉ_L̂_t,P =1/|α|L̂_t_F/P_F(3+2kA_F/σ_min(R̃)).

  The right minimal indices of L̂_t(λ)+ΔL̂_t(λ) are those of P(λ)+Δ P(λ) shifted by k-1 and left minimal indices of L̂_t(λ)+ΔL̂_t(λ) are same as those of P(λ)+Δ P(λ), which is the same as the corresponding relationship between the minimal indices of L̂_t(λ) and P(λ).
 

  Clearly, 
    ΔL̂_t_F<σ_min(R̃)/2k^3/2⇒Δ B_F<σ_min(R̃)/2k^3/2.

   By Theorem <ref>, there exists Δ D(λ) ∈𝔽[λ]^kn× n of grade k-1 such that B(λ)+Δ B(λ) and Λ_k,n(λ)^T+Δ D(λ)^T are dual minimal bases with all the row degrees 1 and k-1 respectively. Therefore L̂_t(λ) + ΔL̂_t(λ) is a strong block minimal bases pencil and Theorem <ref> implies that L̂_t(λ) + ΔL̂_t(λ) is a strong block minimal bases linearization of 
    1/α
    (A(λ) + Δ A(λ))(Λ_k.n(λ) + Δ D(λ)) := P(λ) + Δ P(λ)
 of grade k. As P(λ)=1/αA(λ)(Λ_k,n(λ)),
   we have, 
    Δ P(λ)=1/α{(A(λ)+Δ A(λ))Δ D(λ)+Δ A(λ)(Λ_k,n(λ))}

   which implies that
  
    Δ P_F≤1/|α|{A(Δ D)_F+(Δ A)(Δ D)_F+(Δ A)Λ_k,n_F}.

  By applying Lemma <ref> and Theorem <ref> (b), we get

  
    Δ P_F/P_F≤1/|α|L̂_t_F/P_F(3+2kA_F/σ_min(R̃))ΔL̂_t_F/L̂_t_F



Also as the block B̂(λ) is absent in the linearization L̂_t(λ) + ΔL̂_t(λ), we have Ĉ(λ) = I_m in (<ref>) and consequently by Theorem <ref>, the right minimal indices of L̂_t(λ)+ΔL̂_t(λ) are those of P(λ)+Δ P(λ) shifted by k-1 and left minimal indices of L̂_t(λ)+ΔL̂_t(λ) are same as those of P(λ)+Δ P(λ). By Theorem <ref>, the shifting relations between the left and right minimal indices of P(λ) + Δ P(λ) and L̂_t(λ) + ΔL̂_t(λ) are exactly the same as those between P(λ) and L̂_t(λ).




Now we extend the above analysis to solutions of the complete eigenvalue problem for P(λ) obtained via any linearization L_t(λ) arising from a g-linearization in 𝕃_1(P). As noted in Section <ref>, any such linearization L_t(λ) is strictly equivalent to a linearization of the form L̂_t(λ). Using this fact, and the results for L̂_t(λ), we have the following theorem.



Let L_t(λ) be any linearization of P(λ) = ∑_i=0^k λ^iA_i ∈[λ]^m × n of grade k with m > n, arising from a g-linearization in 𝕃_1(P).
  Let L̂_t(λ) = D̃^-1L_t(λ) where D̃ is as given in (<ref>).
  Then L̂_t(λ) is of the form (<ref>). Let A(λ) and B(λ) be the blocks of L̂_t(λ) as specified by (<ref>) and (<ref>) respectively and R̃∈^m + (k-1)n be the nonsingular upper triangular matrix appearing in the block B(λ). If Δ L_t(λ) be any pencil of the same size as L_t(λ) such that
    
    Δ L_t_F<σ_min(R̃)σ_min(D̃)/2k^3/2,

  then L_t(λ)+Δ L_t(λ) is a strong linearization of a matrix polynomial P(λ)+Δ P(λ) as grade k such that
  
    Δ P_F/P_F≤ C_L_t,PΔ L_t_F/ L_t_F,

  where C_L_t,P=κ_2(D̃)/|α|L̂_t_F/P_F(3+2kA_F/σ_min(R̃)), κ_2(D̃) being the 2-norm condition number of D̃. The right minimal indices of L_t(λ)+Δ  L_t(λ) are those of P(λ)+Δ P(λ) shifted by k-1 and left minimal indices of L_t(λ)+Δ  L_t(λ) are same as those of P(λ)+Δ P(λ), which is the same as the corresponding relations between the minimal indices of L_t(λ) and P(λ).
 

  Evidently, L̂_t(λ) := D̃^-1L_t(λ) is of the form form (<ref>). Since L_t(λ) + Δ L_t(λ) = D̃(L̂_t(λ) + D̃^-1Δ L_t (λ)), and (<ref>) implies that
 
    D̃^-1Δ L_t_F<σ_min(R̃)/2k^3/2,
 by Theorem <ref>, L̂_t(λ) + D̃^-1Δ L_t (λ) is a strong block minimal bases linearization of some polynomial P(λ) + Δ P(λ) of grade k such that
 
    Δ P_F/P_F≤1/|α|L̂_t_F/P_F(3+2kA_F/σ_min(R̃))D̃^-1Δ L_t_F/L̂_t_F.


The relation (<ref>) now follows by using the fact that L_t(λ)=D̃L̂_t(λ). Also as L_t(λ) + Δ L_t(λ) = D̃(L̂_t(λ) + D̃^-1Δ L_t(λ)), L̂_t(λ) + D̃^-1Δ L_t (λ) are strictly equivalent, L_t(λ) + Δ L_t(λ) is a strong linearization of P(λ) + Δ P(λ) and the recovery rules for the left and right minimal indices of P(λ) + Δ P(λ) from those of L_t(λ) + Δ L_t(λ) are the same as the ones from L̂_t(λ) + D̃^-1Δ L_t (λ). Therefore it follows from Theorem <ref>, that the right minimal indices of L_t(λ)+Δ  L_t(λ) are those of P(λ)+Δ P(λ) shifted by k-1 and left minimal indices of L_t(λ)+Δ  L_t(λ) are same as those of P(λ)+Δ P(λ), which is same as the corresponding relations between the minimal indices of L_t(λ) and P(λ).











Observe that as the block B̂(λ) is absent in the pencil L̂_t(λ) when compared with the block minimal bases pencil (<ref>), this greatly simplifies the analysis as the arguments in pages 24-30 of <cit.> for Block Kronecker linearizations  may be skipped as a consequence.

If the complete eigenvalue problem for L_t(λ) is solved by using a backward stable algorithm, then Δ L_t_F/L_t_F = O( u).  In such a situation (<ref>) shows that the process of solving the complete eigenvalue problem for P(λ) via linearizations L_t(λ), is globally backward stable if C_ L_t,P is not very large. As C_L_t, P =κ_2(D̃) Ĉ_L̂_t, P, so a good choice of L_t(λ) would be one for which κ_2(D̃) ≊ 1 and Ĉ_L̂_t, P is not large for the corresponding pencil L̂_t(λ) = D̃^-1L_t(λ). To identify such linearizations, we first note that for the block A(λ) of L̂_t(λ),

    α P(λ)=A(λ)Λ_k,n(λ)⇒|α| P_F=AΛ_k,n_F≤√(2)A_F.
 This implies that
 
    L̂_t_F/P_F≥A_F/P_F≥|α|/√(2).


Now if |α|P_F>>σ_min(R̃) then √(2)A_F/σ_min(R̃)>>1, and since L̂_t_F/|α|P_F≥1/√(2) so Ĉ_L̂_t,P will be big. Again if |α|P_F<<σ_min(R̃) then
L̂_t_F/|α|P_F > R̃_F/|α|P_F>>1 and once again Ĉ_L̂_t,P will be big. So, a good choice of L̂_t(λ) would be one for which |α|P_F≊σ_min(R̃).

Besides, if A_F ≊|α|P_F≊σ_min(R̃), and κ_2(R̃) ≊ 1 then 
    C_L_t, P≊ (3+2k)√(1+2(k-1)n)
 and then 
    Δ P_F/P_F⪅ (3+2k)√(1+2(k-1)n)Δ L_t_F/ L_t_F.


In summary, by using linearizations L_t(λ) satisfying


  (i) κ_2(D̃) ≊ 1 and κ_2(R̃) ≊ 1 and

  (ii) A_F ≊|α|P_F≊σ_min(R̃),

we will have Δ P_F/P_F = O( u) if Δ L_t_F/L_t_F = O( u). So the complete eigenvalue problem for P(λ) can be solved in a globally backward stable manner by using backward stable algorithms to solve the complete eigenvalue problem for such choices of L_t(λ).
The optimal Block Kronecker linearizations of the form [[ A(λ); B(λ) ]] ensuring global backward stability that were identified in <cit.> are included in the above choices. In fact they are the ones for which D̃ = I_m + (k-1)n, |α| = 1/P_F, R̃ = I_(k-1)n and X_12_F^2 + Y_11_F^2 ≊1/P_F^2∑_i=1^k-1A_i_F^2 in (<ref>) which include the Frobenius companion form C_1(λ). Our analysis shows that there exist many more choices of linearizations from among the pencils L_t(λ) with which the complete eigenvalue problem for P(λ) can be solved in a globally backward stable manner.












































































































































§ CONCLUSION
 Given an m × n rectangular matrix polynomial P(λ) = ∑_i=0^k λ^iA_i, of grade k, in this paper we have introduced the notion of a generalized linearization (g-linearization) of P(λ).  We have also constructed vector spaces of rectangular matrix pencils such that almost every matrix pencil in the space provides solutions of the complete eigenvalue problem for P(λ) with the property that the left and right minimal indices and bases of P(λ) can be easily extracted from those of the pencil. These spaces become the vector spaces Ł_1(P) and Ł_2(P) introduced in <cit.> whenever P(λ) is square. They also have the same properties with respect to g-linearizations that the spaces Ł_1(P) and Ł_2(P) have with respect to linearizations (as shown in <cit.>) when P(λ) is square and singular. The results provide a direct extension of the theory of the vector spaces Ł_1(P) and Ł_2(P) to the case of rectangular matrix polynomials. We have also shown a process of extracting many different strong linearizations from almost every pencil in Ł_1(P) and Ł_2(P). We believe that our work complements the recent work in <cit.> which allows the study of linearizations of rectangular matrix pencils in a vector space setting  by introducing the Block Kronecker ansatz spaces. While <cit.> gives the relationship between the particular Block Kronecker ansatz spaces 𝔾_1(P) and 𝔾_k(P) and the spaces Ł_1(P) and Ł_2(P) respectively when P(λ) is square and regular, our work extends the notion of the spaces Ł_1(P) and Ł_2(P) to the rectangular case and shows the relationship between strong linearizations of P(λ) extracted from the pencils in Ł_1(P) and Ł_2(P) and the linearizations in 𝔾_1(P) and 𝔾_k(P).

A global backward error analysis of the process of solving the complete eigenvalue problem for P(λ) via the linearizations that can be extracted from strong g-linearizations in Ł_1(P) and Ł_2(P) was also conducted on the lines of the one in <cit.>. It showed that these g-linearizations provide a wide choice of linearizations that can solve the eigenvalue problem for P(λ) in a globally backward stable manner. This analysis which was not carried out earlier even for the case that P(λ) is square, will be useful in making optimal choices of linearizations in computation. Moreover, we believe that when P(λ) is square and has some additional structure, the results may be extended to identify larger collections of optimal structure preserving linearizations beyond the ones known in the literature, with respect to which the eigenvalue problem for P(λ) can be solved in a globally backward stable manner.



§ APPENDIX: PROOF OF LEMMA <REF>





 As the result is obvious for k=2, we assume that k> 2. Since C_j(τ) = C_j(H_k-1) ⊗ I_n for j = k-1, k-2, it is enough to show that 
    σ_min(C_k-1(H_k-1)) = σ_min(C_k-2(H_k-1)) = 2sin(π/4k-2).

 For simplicity, we denote C_j(H_k-1) by C_j for j = k-1, k-2. To complete the proof it is enough to show that both the matrices C_k-1 and C_k-2 are full rank and the smallest nonzero eigenvalues of S_k-2 := C_k-2^*C_k-2 and S_k-1 := C_k-1^*C_k-1 are both equal to 2 + 2 cos(2(k-1)π/2k-1). For j ≥ 1, let
  
 

 D_j=[ 1; 2; ⋱; 2; 1 ]_j × j,
 L_j=[  0; -1  0;  ⋱  ⋱; -1  0 ]_j × j
 T_j = D_j + L_j + L_j^T + e_je_j^T, T̂_j = D_j + L_j + L_j^T + e_1e_1^T,
 

 where e_j is the j-th column of I_j.



 Now a simple multiplication shows that 
    S_k-2=[   D_k L_k^T;   L_k   D_k L_k^T;     ⋱     ⋱     ⋱;     ⋱     ⋱     ⋱;   L_k   D_k L_k^T;   L_k   D_k ]_(k-1) block columns. S_k-1=[   D_k L_k^T;   L_k   D_k L_k^T;     ⋱     ⋱     ⋱;     ⋱     ⋱     ⋱;   L_k   D_k L_k^T;   L_k   D_k ]_k block columns..

 






 To find the smallest eigenvalue of S_k-2 consider the permutation matrix 
    𝒫̃=[   𝒫̃_1   𝒫̃_2      … 𝒫̃_k+1 ]∈ℂ^k(k-1)× k(k-1)
 where 𝒫̃_1=[            ẽ_1      ẽ_1+(k+1)              … ẽ_1+(k-2)(k+1) ],
 𝒫̃_2=[            ẽ_2      ẽ_2+(k+1)              … ẽ_2+(k-2)(k+1) ] and 

 𝒫̃_i=[            ẽ_i      ẽ_i+(k+1)              … ẽ_i+(k-3)(k+1) ], for i=3,4,…,(k+1). Here ẽ_j is the j-th column of I_k(k-1). Then 𝒫̃^TS_k-2𝒫̃ is a block diagonal matrix of (k+1) blocks where the first block is T_k-1, the second block is T̂_k-1, and
the j-th block is [ T̂_k-j+1         ;             T_j-3 ] for j = 3,4,…,(k+1) with T_0 and T̂_0 being empty matrices.

 Clearly the first two blocks have the same eigenvalues and the sub-blocks of all other blocks are submatrices of the first or second block. Hence the smallest eigenvalue of S_k-2 is the smallest eigenvalue of any one of the first 2 blocks, in particular of the second block T̂_k-1.


 To find the smallest eigenvalue of S_k-1, consider the permutation matrix 
    𝒫̂=[   𝒫̂_1   𝒫̂_2      … 𝒫̂_k+1 ]∈ℂ^k^2× k^2

 where 𝒫̂_1=[            ê_1      ê_1+(k+1)              … ê_1+(k-1)(k+1) ] and 𝒫̂_i=[            ê_i      ê_i+(k+1)              … ê_i+(k-2)(k+1) ], for i=2,3,…,(k+1). Here ê_j is the j-th column of I_k^2. Then 𝒫̂^TS_k-1𝒫̂ is a block diagonal matrix of (k+1) blocks where  the
first block is D_k + L_k + L_k^T, the second block is T̂_k-1, and
 the j-th block is
 [ T̂_k-j+1         ;             T_j-2 ] for j=3,4,…,(k+1) with T̂_0 being the empty matrix.


 Clearly 0 is an eigenvalue of the first block and the second block can be obtained by removing the first row and first column of the first block. Hence the smallest eigenvalue of the second block is less than or equal to the second smallest eigenvalue of the first block. Again the sub-blocks of all other blocks are either submatrices of the second block T̂_k-1  or of T_k-1. Since T_k-1 and T̂_k-1 have the same eigenvalues, the smallest eigenvalue of S_k-1 is 0 and the second smallest eigenvalue is the smallest eigenvalue of the second block T̂_k-1.

 From <cit.> the smallest eigenvalue of T̂_k-1 is 2+2cos(2(k-1)π/2k-1) (≠ 0).
 Hence 2+2cos(2(k-1)π/2k-1) is the smallest nonzero eigenvalue of both the matrices S_k-1 and S_k-2. This proves that C_k-1 and C_k-2 are both full rank such that (<ref>) holds. □
 

plain



