The Gauss quadrature for general linear functionals, Lanczos algorithm, and minimal partial realization
Stefano Pozza Miroslav S. Pranić





Gauss quadrature for functionals, Lanczos algorithm, and partial realization        





S. Pozza Faculty of Mathematics and Physics, Charles University, Sokolovská 83, 186 75 Praha 8, Czech Republic. Associated member of ISTI-CNR, Pisa, Italy, and member of INdAM-GNCS group, Italy. 



              pozza@karlin.mff.cuni.cz           

           M. Pranić Department of Mathematics and Informatics, University of Banja Luka, Faculty of Science,
 			     M. Stojanovića 2, 51000 , Bosnia and Herzegovina.






The Gauss quadrature for general linear functionals, Lanczos algorithm, and minimal partial realization



    Stefano Pozza         Miroslav Pranić 

    Received: date / Accepted: date
==========================================================================================================




 The concept of Gauss quadrature can be generalized to approximate linear functionals with complex moments.
  Following the existing literature, this survey will revisit such generalization. 
  It is well known that the (classical) Gauss quadrature for positive definite linear functionals
  is connected with orthogonal polynomials, and with the (Hermitian) Lanczos algorithm.
  Analogously, the Gauss quadrature for linear functionals is connected with formal orthogonal polynomials, 
  and with the non-Hermitian Lanczos algorithm with look-ahead strategy;
  moreover, it is related to the minimal partial realization problem.
  We will review these connections pointing out the relationships between several results established independently in related contexts.
  Original proofs of the Mismatch Theorem and of the Matching Moment Property are given 
  by using the properties of formal orthogonal polynomials and the Gauss quadrature for linear functionals.







§ INTRODUCTION

Let A be an N × N Hermitian positive definite matrix and 𝐯 a vector so that 𝐯^*𝐯=1,
where 𝐯^* is the conjugate transpose of 𝐯.
Consider the specific linear functional ℒ on the space of polynomials 
defined by 

    ℒ(λ^j) := 𝐯^* A^j 𝐯 = m_j,    j=0,1,… ,

where m_0, m_1, … are real numbers known as the moments of ℒ.
The functional ℒ can be expressed as the Riemann-Stieltjes integral 
with a non-decreasing positive distribution function μ(λ) 
supported on the real axis having finitely many points of increase; see, e.g, <cit.>,<cit.>, and <cit.>.
For 1 ≤ n ≤ N, the n-node (classical) Gauss quadrature approximating ℒ is given by the unique n-node quadrature formula
which matches the first 2n moments, i.e., 

    ℒ(λ^j) = ∫_ℝλ^j  dμ(λ) = ∑_i=1^nω_i  (λ_i)^j,    j=0,…,2n-1,

with ω_i positive weights and λ_i positive distinct nodes.
Classical results of the Gauss quadrature can be found, e.g., 
in <cit.>, <cit.>, <cit.>, <cit.>,
<cit.>, <cit.>.
The linear functional ℒ can be associated with a Jacobi matrix J_n
which is an n × n real symmetric tridiagonal matrix. 
For every function f defined on the spectrum of A and J_n,
the matrix J_n gives an algebraic expression for the Gauss quadrature, i.e.,

    𝐯^* f(A)  𝐯 =  ∫_ℝ f(λ)  dμ(λ) ≈∑_i=1^nω_i  f(λ_i) =  𝐞_1^T f(J_n)  𝐞_1,

where f(A) and f(J_n) are matrix functions, and 𝐞_1 is the first vector of the Euclidean basis (with 𝐞_1^T the transpose). 
The matrix J_n can be obtained by n iterations of the Hermitian Lanczos algorithm with inputs A and 𝐯.
Indeed, J_n = V_n^* A V_n, where V_n is the matrix given by the Lanczos algorithm
whose columns are an orthonormal basis of the Krylov subspace {𝐯, A 𝐯, …, A^n-1𝐯}.
Hence the Hermitian Lanczos algorithm with input A, 𝐯 
gives a matrix formulation of the Gauss quadrature for ℒ.
Figure <ref> (see <cit.>) represents the connections described above. 
Such connections can be derived by the properties of orthogonal polynomials;
a detailed explanation can be found, e.g., in <cit.> and <cit.>
(note that the relationships between the Conjugate Gradient method, Lanczos algorithm, and orthogonal polynomials 
were already pointed out by Hestenes and Stiefel in their seminal paper published in 1952 <cit.>).


  


This survey deals with the extension of the connections summarized in Figure <ref>
to the case of a general linear functional defined on the space 𝒫 of the polynomials with generally complex coefficients,
ℒ:𝒫→ℂ. 
We point out that, if not specified otherwise, 
we will consider linear functionals without the underlying assumption that they are determined by a matrix bilinear form analogous to (<ref>).
The survey will revisit the Gauss quadrature for linear functionals, 
its matrix formulation, its connection with the non-Hermitian Lanczos algorithm with look-ahead strategy,
and its relationship with the minimal partial realization problem. 
Furthermore, the connections between the incurable breakdown, the exactness of the Gauss quadrature, and the minimal realization problem,
will be examined with giving an original proof of the Mismatch Theorem (first proved in <cit.>).
The proof easily follows from the properties we will present,
providing a different interpretation of the Theorem in terms of formal orthogonal polynomials roots and nodes of the Gauss quadrature for linear functionals.

Information about the topics mentioned above and their mutual relationships are scattered in the literature. 
The survey aims to describe such topics and their connections
from the point of view of formal orthogonal polynomials.
We hope that such a presentation will be of interest for readers working in related different areas.

Regarding the formal orthogonal polynomials and the Gauss quadrature generalization, we will mainly follow the book <cit.> by Draux
where the Gauss quadrature is extended for the approximation of real-valued linear functionals. 
More precisely, a straightforward extension of Draux's definition to the case of complex-valued linear functionals will be presented.
The more recent Gauss quadrature definitions in <cit.> and in <cit.>, obtained independently of <cit.>, 
can be seen as a generalization to the complex quasi-definite case.
Indeed, for a real quasi-definite linear functional the quadratures in <cit.> are equivalent.
However, some results in <cit.> do not have a counterpart in the real setting of <cit.>
(for instance, formal orthonormal polynomials may have complex coefficients).
The case of a quasi-definite linear functional is simpler to treat; see, e.g., <cit.>.  
The survey will first recall the primary results associated with quasi-definite functionals and then deal with the case of a general linear functional.


This survey approaches the Lanczos algorithm in a finite dimensional setting.
Hence we will not treat infinite dimensional problems. 
For infinite dimensional problems related to positive definite linear functionals
refer, e.g., to <cit.>.
For the relationship with infinite dimensional Krylov subspace methods refer, e.g., to <cit.>, <cit.>,
and <cit.> where many references to original works can be found.


Throughout the survey, we will consider only computations in exact arithmetic.
Since rounding errors substantially affect computations with short recurrences,
the results described in this survey cannot be applied to finite precision computations without a thorough analysis. 
Such analysis is out of the scope of this survey.
The interested reader can refer to <cit.> and <cit.> for analysis of the non-Hermitian Lanczos algorithm in finite precision (assuming no breakdown);
see also the related works <cit.>.
As pointed out in <cit.>, 
in finite precision arithmetic the short recurrences cannot preserve the biorthogonality or even the linear independence of the computed Krylov subspace basis.
Therefore look-ahead techniques for the non-Hermitian Lanczos have a limited impact in computing sufficiently well-conditioned basis when dealing with the loss of biorthogonality.
The interplay of look-ahead techniques and rounding errors in practical computations is still an open issue.


The paper is organized as follows.
Section <ref> summarizes basic results of quasi-definite linear functionals. 
Section <ref> recalls properties of formal orthogonal polynomials and of quasi-orthogonal polynomials 
with respect to a linear functional ℒ:𝒫→ℂ.
The concept of Gauss quadrature for linear functionals and its matrix interpretation can be found respectively in Section <ref>
and Section <ref>.
The Gauss quadrature connections with the minimal partial realization problem 
and with the look-ahead Lanczos algorithm are described respectively in Section <ref> and Section <ref>.
Section <ref> concludes the survey summarizing the links between the Gauss quadrature, minimal partial realization, and look-ahead Lanczos algorithm.






§ QUASI-DEFINITE LINEAR FUNCTIONALS

We start recalling several results for quasi-definite linear functionals following the description in our previous works with Zdeněk Strakoš <cit.>. These results will be extended to the more challenging general case in the remaining sections.

Let ℒ: 𝒫→ℂ be a linear functional 
with complex moments,

    ℒ(λ^k)=m_k,   k=0,1,… .

An n-degree polynomial p_n(λ) ∈𝒫 is called formal orthogonal polynomial (FOP)
when it satisfies the orthogonality conditions with respect to ℒ

    ℒ(p_n λ^j)=0,     for  j=0,…,n-1;
 
 refer, e.g., to <cit.> and <cit.>.
 Notice that in <cit.> p_n(λ) is referred as general orthogonal polynomial;
 cf. the concept of weak orthogonal polynomial in <cit.> and <cit.>.
 The subindex n in the polynomial notation p_n(λ) will always stand for the degree of the polynomial
 and we will not emphasize it further on.
 Moreover, whenever appropriate the argument λ will be skipped for simplicity of notation. 


Denoting with 𝒫_k ⊂𝒫 the subspace of polynomials of degree at most k,
the following classes of linear functionals can be defined (see, e.g., Theorem 3.1, Definition 3.2, Theorem 3.4 and the subsequent Corollary in <cit.>, Theorem 1 and the subsequent Remark in <cit.>).

The linear functional ℒ is said to be quasi-definite on 𝒫_k
if there exist unique FOPs p_0(λ),…,p_k(λ)
(we always use the term “unique” for a polynomial in the sense of unique up to multiplication by a nonzero scalar)
satisfying the conditions

    ℒ(p_j p_n) = 0  ,  for  j ≠ n, 
        and  ℒ(p_n^2)≠ 0.

A linear functional is said to be positive definite on 𝒫_k if in addition p_0(λ),…,p_k(λ) are real polynomials, and ℒ(p_n^2) > 0, for n=0,…,k.

Note that the definition above is equivalent to the ones in <cit.> and <cit.>.

If a FOP p_n is such that ℒ(p_n^2) = 1, then it is a formal orthonormal polynomial.
A beautiful summary about FOPs in the quasi-definite case can be found in the book by Chihara <cit.>
(notice that Chihara used the simplified term orthogonal polynomials instead of formal orthogonal polynomials).
A sequence of formal orthonormal polynomials p_0(λ), …, p_k(λ) satisfy the three-term recurrence

    β_n  p_n(λ) = (λ - α_n-1) p_n-1 (λ) - β_n-1 p_n-2(λ),      n=1, …, k,
 
where β_0=0, p_-1(λ) = 0, p_0(λ) = 1/√(m_0)
and the coefficients α_n-1, β_n are given by

    α_n-1 = ℒ(λ p_n-1 p_n-1),   β_n =  ℒ(λ p_n-1 p_n).

see, e.g., <cit.>, <cit.>. 
Notice that in order to avoid ambiguity, we always take the principal value of the complex square root, i.e., we consider arg(√(c)) ∈ (-π/2,π/2].
The recurrences (<ref>) can be written in the compact form as 

    λ 𝐩(λ) = J_n 𝐩(λ) + β_n p_n(λ)  𝐞_n,    n = 1, …, k,

where 𝐩(λ) = [p_0(λ), p_1(λ), …, p_n-1(λ)]^T,
𝐞_n is the nth vector of the Euclidean basis,
and J_n is the nth complex Jacobi matrix
 
    J_n =  [ α_0    β_1         
    β_1    α_1     ⋱   
    
       ⋱   ⋱   β_n-1
          β_n-1   α_n-1 ],    n = 1, …, k;

 more information about complex Jacobi matrices and their properties can be found, e.g., in <cit.> and in <cit.>.

 
Given a smooth enough function f(λ), the Gauss quadrature for quasi-definite linear functionals considered in <cit.> has the form

    𝒢_n(f) :=
    ∑_i=1^ℓ∑_j=0^s_i-1ω_i,j f^(j)(λ_i),  
    n=s_1+ ⋯ +s_ℓ,

and satisfies the following properties.

  
  * G1: the quadrature 𝒢_n(f) has maximal degree of exactness 2n-1, 
	    i.e., it is exact for all polynomials of degree at most 2n-1;
  
  * G2: the quadrature 𝒢_n(f) is well-defined and it is unique.
  Moreover, Gauss quadratures with a smaller number of weights also exist
  and they are unique;
  
  * G3: the quadrature 𝒢_n(f) can be written as the matrix form
m_0 𝐞_1^Tf(J_n) 𝐞_1, where J_n is the
complex Jacobi matrix associated with ℒ. 
 
A quadrature having properties G1, G2 and G3 exists 
if and only if the linear functional ℒ is quasi-definite on 𝒫_n;
see <cit.> and <cit.>.




Property G3 corresponds to the so called Matching Moment Property of the complex Jacobi matrix, i.e.,
if the complex numbers m_0, …, m_2n-1 define a quasi-definite linear functional (<ref>) with associated Jacobi matrix J_n
(here and in the following the simplified term quasi-definite linear functional and positive definite linear functional
 will stand for linear functionals that are quasi-definite and positive definite on the space of polynomials of sufficiently large degree), then

    m_0 𝐞_1^T   (J_n)^j 𝐞_1 = m_j,    j=0,…, 2n-1;

see <cit.>.
In <cit.> the Matching Moment Property was proved for a quasi-definite linear functional given by

    ℒ(f) = 𝐰^* f(A) 𝐯,

where A is a complex matrix and 𝐰, 𝐯 are vectors (compare also with <cit.>).
In <cit.> it was derived by the Vorobyev method of moments  (see in particular Chapter III of <cit.>).





§ POLYNOMIALS AND ORTHOGONALITY

Let ℒ: 𝒫→ℂ be a linear functional  
with moments m_0, m_1, ….
Consider 
the sequence of k-dimensional Hankel matrices

    H_k-1=H(1:k;1:k)=[  
     m_0     m_1   …    m_k-1
    
    m_1     m_2   …    m_k
    ⋮   ⋮      ⋮
    
    m_k-1   m_k   …    m_2k-2  ],    k=1,2,… ,

with the corresponding determinant Δ_k-1
(the notation A(i:j;ℓ:n)
stands for the submatrix of A composed of the elements in the rows from i to j
and in the columns from ℓ to n).
Setting m_k-1 as the vector

    m_k-1=H(1:k;k+1)=[m_k,…,m_2k-1]^T,

we are interested in the properties of the linear system

    H_k-1  c=- m_k-1.

The solution of Hankel systems, and many related properties of Hankel matrices,
have been extensively treated in the literature;
see, e.g, to the seminal paper by Stieltjes <cit.>
(please notice that we refer to the English translation published by Springer in 1993), 
the monographs <cit.>, <cit.>, <cit.>, <cit.>, and <cit.>, and the paper <cit.>.
Here, we refer in particular to some results in Section 1.2 of <cit.>;
their straightforward generalization to the complex case is equivalent to Theorems <ref> and <ref> given in this section;
see also Theorem 7 in <cit.> in the context of infinite Hankel matrices with finite rank.
We do not report the proofs of Theorems <ref> and <ref> since they are based on the study of Hankel matrices,
and they would lead us too far from the main point of the survey.
We will use them as the starting point of our presentation.

Assume that Δ_k-1≠ 0, then Δ_k=0 if and only if

    -m_2k=c_0m_k+c_1m_k+1+…+c_k-1m_2k-1,

where c=[c_0,…,c_k-1]^T is the unique solution of the
linear system (<ref>).
Moreover, if Δ_k-1≠ 0 and  Δ_k=Δ_k+1=…=Δ_k + j -1=0  for j≥1,
then Δ_k+j=0 if and only if

    -m_2k+j=c_0m_k+j+c_1m_k+j+1+…+c_k-1m_2k+j-1.


As a consequence, we get the following theorem; see <cit.>.

Assume that Δ_k-1≠ 0 and
Δ_k=Δ_k+1=…=Δ_k+j-1=0. Then the system

    H_k+j-1  b=- m_k+j-1
 has (infinitely many) solutions 
if and only if Δ_k+j=Δ_k+j+1=…Δ_k+2j-1=0.

The following theorem gives necessary and sufficient conditions for the existence (and uniqueness) of a FOP p_n(λ) of degree n; see <cit.>. 

Let ℒ: 𝒫→ℂ be a linear functional.
An n-degree monic FOP exists if and only if one of the following conditions is satisfied.

 
  * Δ_n-1≠ 0 (unique monic FOP);
 
  * Δ_k-1≠ 0 and
Δ_k=Δ_k+1=…=Δ_n-1=… = Δ_2n-k-1=0
(infinitely many monic FOPs);

where Δ_0,Δ_1,… are the determinants of the Hankel submatrices H_0, H_1, … composed of the moments of ℒ.


A monic  FOP of degree n

    π_n(λ)=λ^n+c_n-1λ^n-1+…+c_1λ+c_0

exists if and only if 
ℒ(λ^jπ_n)=0, for j=0,…,n-1,
which gives the linear system (<ref>) with k=n.
Therefore if Δ_n-1≠ 0, then the polynomial π_n(λ) exists and is unique. 
If Δ_n-1=0, then necessary and sufficient conditions for the existence of π_n(λ) 
are given by Theorem <ref>: for Δ_k-1≠ 0 and
Δ_k=Δ_k+1=…=Δ_n-1=0, there exist infinitely many π_n(λ) if and only if Δ_n=Δ_n+1=…Δ_2n-k-1=0. 


Note that by Theorem <ref>, a linear functional ℒ is quasi-definite on 𝒫_k if and only if Δ_j ≠ 0, for j=0,1,…,k; see, e.g., <cit.>.


The second item of Theorem <ref> can be interpreted in the following way: 
consider the sequence Δ_0, Δ_1, Δ_2, …. 
Let R=R(n-1) be the number of zeros in the sequence between Δ_n-1 
and the first nonzero element in the sequence after Δ_n-1, i.e., 
Δ_n-1+j=0 for j=1,…,R and Δ_n+R≠ 0.
Note that the parameters R(n-1) are known as Kronecker index, and the differences R(n)-R(n-1) as Euclidean indices;
see <cit.>.
Let L=L(n-1) be the number of zeros in the sequence between Δ_n-1 
and the last nonzero element in the sequence before Δ_n-1, i.e., 
Δ_n-1-j=0 for j=1,…,L and Δ_n-L-2≠ 0. 
A FOP of degree n exists if and only if R(n-1)>L(n-1).
Roughly said, there are “more consecutive zeros to the right than to the left”.

Among the formal orthogonal polynomials the following cases can be distinguished;
see Definition on p. 47 of <cit.>. 

A formal orthogonal polynomial (FOP) p_n(λ) is called regular when Δ_n-1≠ 0 (i.e., when it is unique),
while it is called singular when Δ_n-1 = 0 (i.e., when it is not unique).



   Let p_k be a regular FOP and j≥ 0. Then ℒ(p_k q) = 0 for every q ∈𝒫_k+j if and only if Δ_k=Δ_k+1=…=Δ_k + j=0.


 Without loss of generality, let us assume p_k to be monic.
 The conditions ℒ(p_k  λ^k+i) = 0, for i=0,…,j, lead to the system
 
    -m_2k+i=c_0m_k+i+c_1m_k+i+1+…+c_k-1m_2k+i-1,    i=0,…,j,

 with c_0, …, c_k-1 the unique solution of the
linear system (<ref>).
 Theorem <ref> concludes the proof.


Knowing all the integers k such that Δ_k=0
allows determining all the integers n for which a FOP p_n(λ) exists.

Example 1. If the zero-nonzero pattern of the sequence of Hankel determinants Δ_k is

    [ Δ_k   =   ∗   ∗   0   ∗   ∗   0   0   0   0   ∗   0   0   0   ∗;   k   =   0   1   2   3   4   5   6   7   8   9  10  11  12  13 ],

then the FOPs of degree 3, 8, 9, 12 and 13 do not exist. 
There exist regular FOPs of degree 1, 2, 4, 5, 10 and 14 and
singular FOPs of degree 6, 7 and 11.

In order to fill the gaps in FOP sequences, we consider polynomials satisfying the following property.

The polynomial p_n(λ) is called quasi-orthogonal of order k (or k-quasi-orthogonal),
with k<n, when

    ℒ(p_nλ^j)=0,   j=0,…,n-k-1.





Quasi-orthogonal polynomials of order 1 were introduced by Riesz in <cit.> and then generalized to any order by Chihara in <cit.>;
see also <cit.>, <cit.>, <cit.>,
and compare the definition with the concept of inner formal orthogonal polynomials given in <cit.>
and of left and right quasi-formally biorthogonal polynomials in <cit.>.
Note that Definition <ref> does not require k to be minimal, i.e., it is not necessary that ℒ(p_nλ^n-k) 0. Thus a k-quasi-orthogonal polynomial of degree n is also j-quasi-orthogonal for j=k+1,…,n-1. Also, any formal orthogonal polynomial of degree n is k-quasi-orthogonal for k=1,…,n-1.


If Δ_k-1≠ 0, then an (n-k)-quasi orthogonal polynomial of degree n exists for every n larger than k; 
see, e.g., <cit.>. 
The following theorem will prove it together with the characterization of such polynomials; 
see discussion on pp. 47–51 of <cit.>. 
 
Let Δ_0,Δ_1,… be the Hankel determinants associated with the linear functional ℒ. 
Let Δ_k-1≠ 0, and Δ_k-1+i=0 for i=1,…,j, 
and let π_k(λ) be the regular monic FOP with respect to ℒ. 
Then all the monic i-quasi-orthogonal polynomials π_k+i(λ) for i=1,…,j are of the form

    π_k+i(λ)=π_k(λ)∏_t=1^i(λ-η_t),    η_t ∈ℂ.



The proof is by induction on i.
Let i=1. By Proposition <ref>, 
Δ_k=0 if and only if π_k(λ) is orthogonal to all polynomials of degree k.
Therefore λπ_k(λ) is a monic polynomial of degree k+1 that is orthogonal to 𝒫_k-1:

    ℒ(λ π_k q)=ℒ(π_k (λ q))=0,   for  q(λ) ∈𝒫_k-1.

Moreover, any polynomial of the form (λ-α)π_k(λ), α∈ℂ,
is a monic 1-quasi-orthogonal polynomial. 
On the other side, assume that p_k+1(λ) is an arbitrary monic polynomial of
degree k+1 that is orthogonal to 𝒫_k-1. 
Then the polynomial λπ_k(λ) - p_k+1(λ) has the following two properties:

  
  * it is of degree k, 
  
  * it is orthogonal to 𝒫_k-1.
 
Hence the uniqueness of π_k(λ) gives λπ_k(λ) - p_k+1(λ)=βπ_k(λ) for a certain complex number β, i.e.,

    p_k+1(λ)=(λ-β) π_k(λ),   for some β∈ℂ.


Set i between 2 and j-1, 
and assume that all the monic i-quasi-orthogonal polynomials of degree k+i are of the form (<ref>). 
By Proposition <ref>,
Δ_k=Δ_k+1=…=Δ_k+i=0 
if and only if π_k(λ) is orthogonal to all polynomials of degree k+i. 
Therefore λπ_k+i(λ) is a monic polynomial of degree k+i+1 that is orthogonal to 𝒫_k-1:

    ℒ(λ π_k+i q)=ℒ(π_k (λ (λ-η_1)⋯(λ-η_i) q))=0,   for  q(λ) ∈𝒫_k-1.
 
Clearly, (λ-α)π_k+i(λ) is a monic (i+1)-quasi-orthogonal polynomial of degree k+i+1, 
for any complex number α. 
It remains to prove that an arbitrary monic polynomial of degree k+i+1 that is orthogonal to 𝒫_k-1
is of the form (λ-β)π_k+i(λ), where β is a certain complex number, 
and π_k+i(λ) is a polynomial of the form (<ref>). 
It can be done similarly to the case i=1.



Let Δ_0,Δ_1,… be the Hankel determinants associated with the linear functional ℒ such that 
Δ_k-1≠ 0 and Δ_k+i=0 for i=0,…,2j-1. 
Then for i=0,…,j, p_k+i(λ) is a FOP
if and only if it is i-quasi-orthogonal.


 Clearly any FOP of degree k+i is i-quasi-orthogonal.
 Vice versa if p_k+i(λ) is i-quasi-orthogonal, 
 then it satisfies (<ref>).
 By Proposition <ref>, p_k(λ) is orthogonal to 𝒫_k+2j-1. Therefore if q(λ) ∈𝒫_k+i-1,
 then  ℒ (p_k+i q) = ℒ (p_k (λ - η_1) ⋯ (λ - η_i) q) = 0 for i=0,…,j.
 

Consider the sequence of polynomials

    p_0(λ), p_1(λ), p_2(λ), …

 constructed in the following way: 
p_n(λ) is a regular FOP (when possible) or p_n(λ) is a (n-k)-quasi-orthogonal polynomial, 
where p_k(λ) is the last regular FOP before p_n(λ). 
For later convenience, we consider every nonzero choice for p_0(λ) as a regular FOP.
Let us denote by ν(0),ν(1),ν(2),… all the indexes for which p_ν(j)(λ) is a regular FOP,
i.e., Δ_ν(j)-1≠ 0 (setting p_ν(0)(λ) = p_0(λ) ≠ 0, and ν(j+1) = ∞ when p_ν(j)(λ) is the last of the regular FOPs).
By Theorem <ref>,
the quasi-orthogonal polynomials between two consecutive regular FOPs p_ν(j)(λ), p_ν(j+1)(λ)
satisfy the recurrences

    β_np_n(λ) = λ p_n-1(λ) - ∑_i=ν(j)^n-1α_n,i p_i(λ),    n=ν(j)+1,…,ν(j+1)-1,

for some coefficients α_n,i∈ℂ and β_n ≠ 0;
see <cit.>.
Notice that any choice of α_n,i and β_n ≠ 0 defines a (n-ν(j))-quasi-orthogonal polynomial.
In particular, there exist families of such polynomials satisfying the two-term recurrences

    β_n p_n(λ)=(λ - α_n,n-1) p_n-1(λ),    n=ν(j)+1,…,ν(j+1)-1;

fixing α_n,n-1=0 gives even simpler recurrences. 


Setting n = ν(j+1) for some j ≥ 0,
the regular FOP p_n(λ) satisfies (see <cit.> and <cit.>) 

    β_n p_n(λ) = λ p_n - 1(λ) - ∑_i=ν(j)^n-1α_n,i p_i(λ) - γ_np_ν(j-1)(λ),

with p_ν(-1)(λ) = p_-1(λ) = 0, β_n a nonzero coefficient, γ_ν(1) = 0,

    γ_n = ℒ( λ p_n-1 p_ν(j)-1) /ℒ(p_ν(j)-1  p_ν(j-1)) ≠ 0,    j ≥ 1,

and α_n,i given by

    [[ ℒ( p_ν(j)   p_ν(j) )                    …   ℒ( p_ν(j)   p_n-1);                    ⋮                                         ⋮;     ℒ( p_n-1 p_ν(j))                    …      ℒ( p_n-1 p_n-1) ]]
    [[ α_n,ν(j);        ⋮;  α_n,n-1 ]]
    =
    [[ ℒ( λ p_ν(j) p_n-1 );                   ⋮;   ℒ( λ p_n-1 p_n-1) ]],

where the matrix of the system is nonsingular; see, e.g., <cit.>. 
Notice that for a quasi-definite linear functional
the related (regular) formal orthonormal polynomials satisfy the three term recurrences (<ref>).

Given n = 1, 2, …, the recurrences (<ref>) and (<ref>) 
can be expressed in the matrix form 
(see <cit.>, <cit.>; c.f.,
<cit.>, <cit.>, and <cit.>)

    λ 𝐩(λ)
      =
      T_n 𝐩(λ)
      +
      β_n p_n(λ) 𝐞_n,

 with 𝐩(λ) = [p_0(λ), p_1(λ), …, p_n-1(λ)]^T
 and where T_n is the block matrix 
  
    T_n =  [ 
           [               1-21|c                                                                                                                                                   ;  2|c|.6[0pt][0pt]A_0               β_ν(1)                                                                                                         ;                  1-4                                                                                                                                                   ;               γ_ν(2)                        2c|.6[0pt][0pt]A_1                  1l⋱                                                               ;                  3-6                                                                                                      1c|                                          ;                                                            1l⋱                          2c|.6[0pt][0pt]⋱               β_ν(ℓ)                     ;                  5-8                                                                                                                                                1c|;                                                                                                      γ_n                      2c|.6[0pt][0pt]A_ℓ^n;                  7-8 ]  ],

with the coefficients β_ν(j) on the first upper diagonal, 
the coefficients γ_ν(j) in the position (ν(j),ν(j-2)+1), 
γ_n = 0 when p_n(λ) is not regular, and 

    A_j^n =  [
    [      α_ν(j)+1, ν(j)           β_ν(j) +1                   0                   …                   0;      α_ν(j)+2, ν(j) α_ν(j) +2, ν(j) + 1           β_ν(j) +2                   ⋱                   ⋮;                   ⋮                   ⋮                   ⋱                   ⋱                   0;         α_n-1, ν(j)      α_n-1, ν(j) +1                   …                   ⋱               β_n-1;           α_n, ν(j)        α_n, ν(j) +1                   …                   …            α_n, n-1 ]],

for n=ν(j)+1,…,ν(j+1); A_j = A_j^ν(j+1) for simplicity.
Notice that using the recurrences (<ref>) with α_n,n-1 = 0 
gives the sparse matrix

    A_j =   [  
    [                  0          β_ν(j) +1                  0                  …                  0;                  0                  0          β_ν(j) +2                  ⋱                  ⋮;                  ⋮                  ⋮                  ⋱                  ⋱                  0;                  0                  0                  …                  0         β_ν(j+1)-1;     α_ν(j+1), ν(j)  α_ν(j+1), ν(j) +1                  …                  … α_ν(j+1), ν(j+1)-1 ]],

with α_ν(j+1), ν(j), …, α_ν(j+1), ν(j+1)-1 obtained by (<ref>).




When the polynomials p_0(λ),…, p_n(λ) are regular FOPs (the linear functional is quasi-definite on 𝒫_n-1) 
the blocks A_j are scalars.
Therefore T_n is an irreducible tridiagonal matrix 
since β_j and γ_j+1 are nonzero for j=1,…,n-1.
In particular, there exists a sequence of formal orthonormal polynomials
so that the matrix T_n is the complex Jacobi matrix (<ref>).







§ THE GAUSS QUADRATURE FOR LINEAR FUNCTIONALS

Given a linear functional ℒ and a smooth enough function f(λ), 
consider a quadrature approximating ℒ(f) of the form
(see <cit.>, <cit.>, and <cit.>)

    𝒢_n(f) :=
    ∑_i=1^ℓ∑_j=0^s_i-1ω_i,j f^(j)(λ_i),  
    n=s_1+ ⋯ +s_ℓ,

with ω_i,j the weights, λ_i the distinct nodes, and s_i
the multiplicity of the node λ_i. 
Notice that the number of nodes ℓ can be less than n. 
The quadrature (<ref>) will be referred as n-node quadrature
when ω_i, s_i-1≠ 0 for i=1, …, ℓ.
Otherwise, the sum of the multiplicities would be smaller than n.
For any choice of (distinct) nodes λ_1, …, λ_ℓ and their multiplicities s_i,
such that s_1+ ⋯ +s_ℓ=n, it is possible to achieve
that the quadrature (<ref>) is exact for any f(λ) ∈𝒫_n-1. 
It is necessary and sufficient to set the weights as

    ω_i,j = ℒ(h_i,j),

where h_i,j(λ) are polynomials from 𝒫_n-1 such that

    h_i,j^(t)(λ_k)    = 1    for λ_k= λ_i  and  t=j, 
    
      h_i,j^(t)(λ_k)    = 0    for λ_k≠λ_i  or  t≠ j,

with k=1,2,…,ℓ, and t=0,1,…,s_i-1;
see <cit.> or the proof of Theorem 7.1 in <cit.>.
In this case (<ref>) is known as interpolatory quadrature,
since it can be given by applying ℒ to the generalized (Hermite) interpolating polynomial for the function f(λ) at the nodes
λ_i of the multiplicities s_i.
An interpolatory quadrature is completely determined by its nodes and multiplicities.
Therefore in the following a quadrature 𝒢_n will be said to be determined by a polynomial p_n(λ)
when it is an interpolatory quadrature (<ref>)
with λ_i being the roots of p_n, and s_i the corresponding multiplicities of the roots.

The following definition is a straightforward extension to the complex case 
of the Gauss quadrature introduced by Draux in <cit.>.

The quadrature (<ref>) is called the n-node Gauss quadrature when it is exact on the space 𝒫_2n-1
and ω_i,s_i-1≠ 0 for i=1,…,ℓ (the number of nodes, counting the multiplicities, is n).


We point out the following remarks:


  * the algebraic degree of exactness of the n-node Gauss quadrature is allowed to be larger than 2n-1;

  * a Gauss quadrature with smaller number of nodes may or may not exist when the n-node Gauss quadrature exists.

Hence the n-node Gauss quadrature generally does not satisfy properties G1–G3 in Section <ref>.
However, when ℒ is a quasi-definite linear functional, 
then the n-node Gauss quadrature for ℒ satisfies properties G1–G3,
i.e., in this case Definition <ref> is equivalent to the one in <cit.>.



In order to give conditions for the existence of an n-node Gauss quadrature for a linear functional the following result is needed;
see <cit.>, see also <cit.> for positive definite linear functionals
and <cit.> for quasi-definite linear functionals.


  
A quadrature 𝒢_n determined by a polynomial p_n(λ) is exact for all the polynomials in 𝒫_n + k - 1
if and only if p_n(λ) is (n-k)-quasi-orthogonal.


Assume 𝒢_n to be exact for every polynomial in 𝒫_n + k - 1. 
Then p_n(λ) is (n-k)-quasi-orthogonal. Indeed, 

    ℒ(p_n q) = 𝒢_n(p_n q) = ∑_i=1^ℓ∑_j=0^s_i-1ω_i,j (p_n q)^(j)(λ_i) = 0,    q(λ) ∈𝒫_k-1,

since p_n^(j)(λ_i) = 0 for j=0, …, s_i -1, i=1, …, ℓ.
Inversely, let p_n(λ) be (n-k)-quasi-orthogonal.
Any f(λ) ∈𝒫_n+k-1 can be written as f(λ) = p_n(λ) q(λ) + r(λ) 
for some q(λ) ∈𝒫_k-1  and r(λ) ∈𝒫_n-1,
giving ℒ(f) = ℒ(r).
Since 𝒢_n is interpolatory it is exact on 𝒫_n-1 and thus 

    ℒ(f) = ℒ(r) = ∑_i=1^ℓ∑_j=0^s_i-1ω_i,j r^(j)(λ_i).

The proof is concluded since f^(j)(λ_i) = r^(j)(λ_i) for j=0,…, s_i-1, i=1,…,ℓ.

Note that the proof is a straightforward adaptation of the classical well-known argument used for proving the same result in the positive definite case.


As discussed in Section <ref>, for every linear functional ℒ
there exists a sequence of polynomials p_0(λ), p_1(λ), … (<ref>)
so that p_n(λ) is a regular FOP (when possible),
or p_n(λ) is (n-k)-quasi-orthogonal, where p_k(λ) is the last regular FOP before p_n(λ)
(p_0(λ) ≠ 0 is assumed to be regular). 
We denote by ν(0)=0, ν(1), … the indexes of the regular FOPs 
(with ν(t+1) = +∞ when ν(t) is the last of the regular FOPs).
Theorem <ref> implies the following corollary (see <cit.>).

   Let p_n(λ) be a polynomial in the sequence described above. 
   
    
  * If p_n(λ) is a regular FOP,
	    then it determines a quadrature 𝒢_n exact for every polynomials in 𝒫_2n-1.

  * if p_n(λ) is a (n-k)-quasi-orthogonal polynomial,
	    then it determines a quadrature 𝒢_n exact for every polynomials in 𝒫_n+k-1.
   


Notice that if ν(1) > 1, then Δ_0 = … = Δ_ν(1)-2 = 0. Thus m_j=0 for j=0,…,ν(1) -2 (see, e.g., <cit.>) and, consequently, 𝒢_n(f) ≡ 0 for n=1, …, ν(1) -1.

If ω_i, s_i-1 = 0 for some i, then the quadrature (<ref>) 
has a smaller number of nodes (counting the multiplicities).
The following lemmas deal with this issue; see <cit.>.


   Consider the quadratures 𝒢_n determined by the polynomial p_n(λ) in the sequence described above. 
   Given two consecutive regular FOPs p_ν(t)(λ) and p_ν(t+1)(λ), with t≥ 1, then
   
    𝒢_n = 𝒢_ν(t),    for  n=ν(t) + 1, …, ν(t+1) -1.
   


    Theorem <ref>  gives
    
    p_n(λ) = p_ν(t)(λ) q_n - ν(t)(λ),
   
    for some polynomial q_n - ν(λ)(λ).  
    Let λ_1, …, λ_ℓ be the roots of p_n(λ) 
    with multiplicities s_1, …, s_ℓ.
    The weights of the quadrature 𝒢_n are given by (<ref>).
    Consider the pair i,j so that (λ - λ_i)^j is not a factor of p_ν(t)(λ),
    i.e., the root λ_i is not a root of p_ν(t)(λ) or it is a root of p_ν(t)(λ)
    but with j greater than the multiplicity of λ_i as a root of p_ν(t)(λ).
    Then the (n-1)-degree interpolatory polynomial h_i,j(λ) defined in (<ref>) is a multiple of p_ν(t)(λ), i.e.,
    
    h_i,j(λ) = p_ν(t)(λ) r_n - ν(t) - 1(λ),

     for some polynomial r_n - ν(t) - 1(λ).
     By Proposition <ref>, p_ν(t)(λ) is orthogonal to 𝒫_ν(t+1) -2,
     giving
     
    ω_i,j = ℒ(h_i,j) = ℒ (p_ν(t) r_n - ν(t) - 1) = 0.

    Therefore 𝒢_n has at most ν(t) nodes.
    Moreover, each node of 𝒢_n is a node of 𝒢_ν(t)
    and has multiplicity smaller than or equal to the one of the corresponding node of 𝒢_ν(t).
     
    If λ_i is a root of p_ν(t)(λ) with multiplicity j,
    then there exists a polynomial h_i,j(λ) of the kind of (<ref>) 
    so that ω_i,j = ℒ(h_i,j) is the corresponding weight of 𝒢_ν(t).
    Since h_i,j(λ) has degree ν(t) - 1 the weight  ω_i,j is given by
    
    ω_i,j = 𝒢_n (h_i,j).

    Noticing that 𝒢_n (h_i,j) = ω_i,j  concludes the proof. 
    


   If p_n(λ) is a regular FOP, with n ≥ 1, then it determines a quadrature (<ref>) 
   such that ω_i, s_i -1≠ 0, for i=1,…,ℓ.
 
 
   Let t be such that p_ν(t)(λ) = p_n(λ) and h_i,j(λ) as in (<ref>), 
   then 
   
    ℒ(h_i, s_i-1 p_ν(t-1))    =   ∑_r=1^ℓ∑_s=0^s_i -1ω_r,s (h_i, s_i-1 p_ν(t-1))^(s) (λ_r) 
       =   ∑_r=1^ℓ∑_s=0^s_i -1ω_r,s∑_u=0^ss  u h_i, s_i-1^(u)(λ_r) p_ν(t-1)^(s-u) (λ_r) 
       =   ∑_s=0^s_i -1ω_i,s∑_u=0^ss  u h_i, s_i-1^(u)(λ_i) p_ν(t-1)^(s-u) (λ_i) 
       =   ω_i,s_i-1 p_ν(t-1) (λ_i).

  Proposition <ref> gives ℒ(h_i, s_i-1 p_ν(t-1)) ≠ 0, concluding the proof.
  

The following theorem summarizes the previous discussion; see <cit.>.


The n-node Gauss quadrature 𝒢_n exists (and is unique) if and only if Δ_n-1≠ 0.
Moreover, if Δ_n = Δ_n+1 = … = Δ_n+j = 0,
then 𝒢_n has degree of exactness at least 2n + j.
In particular, if n = ν(t), then 𝒢_n has (maximal) degree of exactness ν(t) + ν(t+1) -2,
with ν(t+1) = +∞ when n is the last of the regular FOPs.


   By Theorem <ref>, 𝒢_n is exact on 𝒫_2n-1 
   if and only if it is determined by a FOP with degree n, i.e., a polynomial p_n(λ) orthogonal to 𝒫_n-1.
   By Lemma <ref> if p_n(λ) is a singular FOP,
   then 𝒢_n has not n nodes. 
   Therefore it is not a n-node Gauss quadrature.
   Considering Lemma <ref> and noticing that regular FOPs are unique,
   𝒢_n exists and is unique if and only if Δ_n-1≠ 0.
   The proof is conclude noticing that Theorem <ref> and Lemma <ref> imply 
   that 𝒢_n is exact on 𝒫_2n+j.
   






§ MATRIX FORMULATION OF THE GAUSS QUADRATURE

If ℒ is a quasi-definite linear functional,
then the associated complex Jacobi matrix (<ref>) satisfies the Matching Moment Property (<ref>).
We will give an original proof of an extension of the Matching Moment Property for a general sequence of moments 
using the properties of the formal orthogonal polynomials and of the Gauss quadrature for the linear functionals.
The presented extension also considers the case of moments so that m_0 = … = m_ν(1) = 0.
The case of a linear functional of the kind ℒ(f) = 𝐰^* f(A) 𝐯,  with m_0 ≠ 0, was treated in <cit.>. 
We remark that assuming real moments (with a straightforward extension to the complex case),
the Matching Moment Property presented here, as well as the ones in <cit.>, 
can be derived by Theorem 5 of the 1983 paper by Gragg and Lindquist <cit.>,
where such property is related to the minimal partial realization problem.





Let  ℒ: 𝒫→ℂ be a linear functional
and let T_n be the corresponding block tridiagonal matrix (<ref>) associated with the sequence of polynomials p_0(λ),…,p_n(λ). 
Denote by p_ν(t)(λ) the subsequence of the regular FOPs
and recall that for ν(t) < n < ν(t+1) the polynomials p_n(λ) are (n-ν(t))-quasi-orthogonal.
Also recall that if ν(1)≥ 2, then m_j=0 for j=0,…,ν(1) -2. 
Since the elements in the superdiagonal of T_n are nonzero
the block tridiagonal matrix T_n is nonderogatory, i.e., its eigenvalues have geometric multiplicity 1.
Indeed, if λ is an eigenvalue, 
then deleting the first column and the last row of T_n - λ I 
gives a lower triangular nonsingular matrix (with I = [𝐞_1, …, 𝐞_n] the identity matrix). 
Thus the null space of T_n - λ I has dimension 1. 
Proving the Matching Moment Property will need the following lemmas.


   Let T_n and p_n(λ) be as in (<ref>). Then p_n(λ) is the characteristic polynomial of T_n (up to a nonzero rescaling).


Lemma <ref> is a consequence of Lemma 2 in <cit.>;
see also <cit.>.


 Let T_1, T_2, … be a sequence of block tridiagonal matrices (<ref>).
 For n ≥ν(1) + 1 the matrices T_n-1 and T_n satisfy
 
    𝐞_1^T   (T_n-1)^k  𝐞_ν(1) = 𝐞_1^T   (T_n)^k  𝐞_ν(1),    for   k=0,…,n-1,

where the vectors 𝐞_1, 𝐞_ν(1) have dimension n-1 on the left-hand side
and n on the right-hand side (we use the same notation for the sake of simplicity).


Consider the n-dimensional vectors 

    𝐮_k = (T_n)^k  𝐞_ν(1),    k=0, 1, … .

If the last element of 𝐮_k is zero for k=0, …, n-1, 
then 

    𝐞_1^T 𝐮_k = 𝐞_1^T   (T_n-1)^k  𝐞_ν(1),    k=0, …, n-1,

proving the lemma.
In the following, when the elements from the position i to the position j of a vector are possibly nonzero,
we denote them by *_i:j (*_i = *_i:i).
Similarly, when the elements from the position i to the position j are null, we denote them by 0_i:j.
Direct computations show that

    𝐮_1 = [
                          0_1:ν(1)-2
    _ν(1)-1:ν(1)
    
                          0_ν(1)+1:n],  𝐮_2 = [
                          0_1:ν(1)-3
    _ν(1)-2:ν(1)
    
                          0_ν(1)+1:n], …,  𝐮_ν(1)-1 = [
                          *_1:ν(1)
    
                          0_ν(1)+1:n
    ].

 Moreover,
 
    𝐮_ν(1) = [
                          *_1:ν(1)
    
                          0_ν(1)+1:ν(2)-1
    _ν(2)
    
                          0_ν(2)+1:n],
 
and 

    𝐮_ν(1)+1 = [
                          *_1:ν(1)
    
                          0_ν(1)+1:ν(2)-2
    _ν(2)-1:ν(2)
    
                          0_ν(2)+1:n], …,
       𝐮_ν(1)+ν(2)-1 = [
                          *_1:ν(2)
    
                          0_ν(2)+1:n].

 Repeating the argument gives
 
    𝐮_n-1 = [
                          *_1:n-1
    
                          0
                      ],

 concluding the proof. 
 



  Let ℒ be a linear functional with complex moments m_0, m_1, …,
  and let T_n be the associated block tridiagonal matrix (<ref>)
  with the corresponding polynomials p_0(λ),…,p_n(λ).
  Denote the indexes of the regular FOPs by ν(0)=0, ν(1), ν(2), … .
  For every n ≥ν(1) let t be so that ν(t)≤ n < ν(t+1), the matrix T_n satisfies
 
    μ  m_ν(1)-1 𝐞_1^T (T_n)^k  𝐞_ν(1) = m_k,     k=0,…, ν(t) + ν(t+1) -2,

 with 
 μ = (β_1 ⋯β_ν(1)-1)^-1 for ν(1) > 1, μ = 1 for ν(1) = 1,
 and ν(t+1) = +∞ when p_ν(t) is the last regular FOP.



Consider the linear functional

    ℒ^(n)(f) =  μ  m_ν(1)-1 𝐞_1^T f(T_n)  𝐞_ν(1),    f(λ) ∈𝒫.

If the linear functionals ℒ and ℒ^(n) are identical on the space 𝒫_ν(t) + ν(t+1) -2, then the proof is given.
By Lemma <ref> and the Cayley–Hamilton Theorem, the polynomial p_n(λ) satisfies the orthogonality conditions 

    ℒ^(n)(λ^k p_n) =  μ  m_ν(1)-1 𝐞_1^T (T_n)^k p_n(T_n)  𝐞_ν(1) = 0,    k=0,1,…  .




Proceeding by induction on n, first consider the case n = ν(1)> 1. 
Since T_ν(1) is a Hessenberg matrix it satisfies

    𝐞_1^T (T_ν(1))^k  𝐞_ν(1) = 0 = m_k,    k=0,…,ν(1)-2.

Direct computations give
𝐞_1^T (T_ν(1))^ν(1) - 1 𝐞_ν(1) = β_1 ⋯β_ν(1)-1≠ 0.
Therefore

    μ  m_ν(1) - 1 𝐞_1^T (T_ν(1))^k 𝐞_ν(1) = m_k,    k=0,…,ν(1) -1,

which also trivially stands for n = ν(1) = 1.
Using property (<ref>) and Theorem <ref>, 
p_ν(1)(λ) determines the quadrature 𝒢_ν(1)^(ν(1)) for ℒ^(ν(1)) 
so that 𝒢_ν(1)^(ν(1))(f) = ℒ^(ν(1))(f) for every f(λ) ∈𝒫.
Moreover, p_ν(1)(λ) determines the Gauss quadrature 𝒢_ν(1) for ℒ,
exact for polynomials of degree at most ν(1) + ν(2) -2.
The two quadratures 𝒢_ν(1)^(ν(1)) and 𝒢_ν(1) coincide since they have the same weights.
Indeed, if h_i,j(λ) is the interpolatory polynomial (<ref>) for n=ν(1),
then the weights of 𝒢_ν(1)^(ν(1)) and 𝒢_ν(1) are respectively given by

    ω_i,j^(ν(1)) = ℒ^(ν(1))(h_i,j)    and   ω_i,j = ℒ(h_i,j).

Since h_i,j(λ) has degree ν(1)-1, equality (<ref>) gives 

    ω_i,j^(ν(1)) = ℒ^(ν(1))(h_i,j) = ℒ(h_i,j) = ω_i,j,

proving the theorem for n=ν(1).

Assume n>ν(1), with t so that ν(t)≤ n < ν(t+1),
and define the quadrature 𝒢_n^(n) for ℒ^(n), determined by the polynomial p_n(λ).
By (<ref>) and Theorem <ref>,  𝒢_n^(n)(f) = ℒ^(n)(f) for every f(λ) ∈𝒫.
Furthermore, p_n(λ) determines the quadrature  𝒢_n = 𝒢_ν(t) for ℒ, 
exact for every polynomials of degree at most ν(t) + ν(t+1) - 2.
As noticed above, 𝒢_n^(n) ad 𝒢_n coincide if and only if 
the respective weights ω_i,j^(n) and ω_i,j coincide.
Let h_i,j(λ) be the interpolatory polynomials (<ref>). Since h_i,j(λ) has degree n-1 the weight ω_i,j^(n) satisfies

    ω_i,j^(n)  = ℒ^(n)(h_i,j)  𝐞_1^T   h_i,j(T_n)  𝐞_ν(1) 
    = μ  m_ν(1) -1 𝐞_1^T   h_i,j(T_n-1)  𝐞_ν(1) = ℒ(h_i,j) = ω_i,j,

where Lemma <ref> and the inductive assumption were used. 


   
 We recall the definition of matrix function.
A function  f(λ) is defined on the spectrum of the given matrix A
when for every eigenvalue λ_i of A there exist f^(j)(λ_i) for j = 0,1, …, s_i - 1, 
with s_i the order of the largest Jordan block of A in which λ_i appears. 
Consider the Jordan block Λ of the size s corresponding to the eigenvalue λ,
then the matrix function f(Λ) is defined as

    f(Λ) =   [ [                f(λ)            f'(λ)/1!         f^(2)(λ)/2!                   … f^(s -1)(λ)/(s -1)!;                   0                f(λ)            f'(λ)/1!                   … f^(s -2)(λ)/(s -2)!;                   ⋮                   ⋱                   ⋱                   ⋱                   ⋮;                   ⋮                                       ⋱                   ⋱            f'(λ)/1!;                   0                   …                   …                   0                f(λ) ] ].


Denoting

    A = W diag(Λ_1,…,Λ_ν) W^-1,

the Jordan decomposition of A, the matrix function f(A) is defined as

    f(A) = W diag (f(Λ_1),…, f(Λ_ν)) W^-1.

We refer to <cit.> for further information and for the equivalence to the other definitions of matrix function. 

Consider the block tridiagonal matrix T_n of Theorem <ref>
and its Jordan decomposition T_n = W diag (Λ_1,…, Λ_ℓ) W^-1.
Since T_n is nonderogatory, there are λ_1, …, λ_ℓ distinct eigenvalues
corresponding to the Jordan blocks Λ_1, …, Λ_ℓ of the sizes respectively s_1, …, s_ℓ.
If f(λ) is a smooth enough function so that f(T_n) is well defined, 
then the Jordan decomposition of T_n and some algebraic manipulations give

    μ  m_ν(1)-1 𝐞_1^T f(T_n)  𝐞_ν(1) = ∑_i=1^ℓ∑_j=0^s_i-1ω_i,j f^(j)(λ_i) ,

  with ω_i,j complex weights, μ and m_ν(1)-1 as in Theorem <ref>;
  see <cit.> and <cit.> for algebraic expressions of the weights.
  This observation together with the proof of Theorem <ref> 
  shows that when n=ν(t) the bilinear form μ  m_ν(1)-1 𝐞_1^T f(T_n)  𝐞_ν(1)
  is a matrix formulation of the n-node Gauss quadrature 𝒢_n(f) for the linear functional ℒ.
  Moreover, if ν(t) < n < ν(t+1), then Lemma <ref> gives 𝒢_n = 𝒢_ν(t);
  hence T_n and  T_ν(t) correspond to the same Gauss quadrature 𝒢_ν(t), despite being different.
  


§ THE MINIMAL PARTIAL REALIZATION AND GAUSS QUADRATURE

Any triplet (𝐰, A, 𝐯) composed of a matrix A and vectors 𝐯, 𝐰, 
can be associated with a dynamical system

    d𝐳/dt=A 𝐳(t)+𝐯 u(t)


    y(t)=𝐰^*𝐳(t),

with 𝐳(t) the state vector,  u(t) the scalar input (control), and y(t) the scalar output.
The transfer function 

    Γ(τ):=𝐰^*(τ I-A)^-1 𝐯=∑_j=0^∞𝐰^* A^j 𝐯/τ^j+1

connects u(t) with y(t) and it is obtained applying the Laplace transform;
refer, e.g., to <cit.>, <cit.>, <cit.>. 
The series representation holds only for |τ| large enough, 
and the coefficients {𝐰^*A^j  𝐯}_j=0^∞ are usually known as Markov parameters. 
The triplet (𝐰, A, 𝐯) is called a realization of Γ. 
One of the questions in systems theory is to determine all the realizations (𝐰, A, 𝐯) 
that yield a given (rational) function Γ, or equivalently, its Markov parameters. 
When the realization matches a finite number of Markov parameters it is said to be a partial realization.
A partial realization in which A has minimal dimension is called a minimal partial realization.
Among the extensive literature about the realization problem we refer the reader to the papers by Kalman <cit.>,
Gilbert <cit.>, Ho and Kalman <cit.>, Gragg <cit.>, Gragg and Lindquist <cit.>,
Parlett <cit.> (which offers an algebraic point of view), Heinig and Jankowski <cit.>, 
and to the monographs by Kailath <cit.>, Bultheel and Van Barel <cit.>, 
Antoulas <cit.>, and by Liesen and Strakoš <cit.>; 
see also <cit.>.
In the papers by Chebyshev from 1855–1859 <cit.> and Christoffel from 1858 <cit.>
the concept equivalent to the  minimal partial realization is present (without using the name)
for a sequence of moments defining a positive definite linear functional;
cf. the comment in <cit.>.
The seminal paper by Stieltjes on continued fractions published in 1894 <cit.>
provides an instructive description;
see also <cit.> and <cit.>.
The results about the Gauss quadrature for real linear functionals 
and about the minimal partial realization of a sequence of real numbers appeared in the same year (1983)
respectively in the monograph by Draux <cit.> and in the paper by Gragg and Lindquist <cit.>.
Section <ref> has presented the results by Draux extending them to the complex case.
Here the minimal partial realization of a sequence of complex numbers will be described 
together with the relationships between results in <cit.> and <cit.> 
(with extension to the complex case).




In the following we offer a non-standard formulation of the realization problem in systems theory.

Problem 1: For a given finite sequence of complex numbers 

    m_0, m_1, …, m_k,

find all the triplets (𝐰, A, 𝐯) 
such that 

    𝐰^* A^j 𝐯 = m_j,    j=0,…,k.

Notice that usually the Markov parameters are defined as η_j = m_j-1. 

There always exists a solution of dimension k+1 of Problem 1.
For instance, take  A∈ℂ^k+1× k+1 and 𝐯, 𝐰∈ℂ^k+1 as

    A =  [     0         1         
        0                 ⋱     
          ⋱      1   
              0
            ],
    	  𝐯 =  [ 
    	  m_0 
      m_1   
    ⋮
     m_k ],
    	  𝐰 =  [ 
    	  1 
      0   
    ⋮
     0
            ].

The sequence (<ref>) defines the linear functional ℒ on 𝒫_k 
with moments 

    ℒ(λ^j) = m_j,    j=0,…,k.

For any solution (𝐰, A, 𝐯) of dimension n,
let λ_1, …, λ_ℓ be the distinct eigenvalues of A
and s_i be the maximal geometric multiplicity of λ_i (the size of the largest Jordan block corresponding to λ_i).
Then the definition of matrix function (<ref>) and algebraic manipulations give

    𝐰^*f(A) 𝐯 = ∑_i=1^ℓ∑_s=0^s_i-1ω_i,s f^(s)(λ_i),    s_1 + … + s_ℓ≤ n,

with ω_i,s complex weights. 
Therefore every realization of the sequence (<ref>) defines a quadrature rule for the linear functional (<ref>).

Problem 2: Among all the realizations for (<ref>) find those of smallest dimension.

Let n be the smallest index so that
the unique n-node Gauss quadrature determined by the regular FOP p_n(λ)
is exact for every polynomial of degree smaller than or equal to k, i.e.,

    ℒ(q) = 𝒢_n(q) =  ∑_i=1^ℓ∑_s=0^s_i-1ω_i,s q^(s)(λ_i),    s_1 + … + s_ℓ = n,    q ∈𝒫_k.

If T_n is the block tridiagonal matrix (<ref>) corresponding to p_n(λ),
then Theorem <ref> shows that the triplet 
(𝐞_1, T_n, μ  m_ν(1)-1𝐞_ν(1))
is a minimal partial realization for (<ref>).
All the other minimal partial realizations can be expressed as

    (B^*𝐞_1,   B^-1T_n B,  μ  m_ν(1)-1 B^-1𝐞_ν(1)),

with B any n× n invertible matrix
(notice that this is a straightforward extension of the result given in <cit.> to complex Markov parameters).
Hence any minimal partial realization of a sequence of complex number m_0, m_1, … 
corresponds to a Gauss quadrature for the linear functional having m_0, m_1, … as moments.

Finally, we recall the following well-known spectral result about minimal realizations, giving a proof based on the previous developments.

Consider the matrix A and the vectors 𝐯, 𝐰. 
   If the triplet (𝐜, S, 𝐛) is a minimal realization of the sequence of Markov parameters given by

    m_j = 𝐰^* A^j 𝐯,    j =0, 1, … ,

then the spectrum of S is a subset of the spectrum of A.


 Let p_k(λ) be the characteristic polynomial of the matrix A and consider the linear functional ℒ defined by 
 
    ℒ(q) = 𝐰^* q(A)  𝐯,    q(λ) ∈𝒫.

 By Lemma <ref> and the Cayley–Hamilton Theorem 
 the k-degree polynomial p_k(λ) is formally orthogonal to every polynomial, i.e., 
 ℒ(p_k q) = 0 for every  q(λ) ∈𝒫.
 Consider the last regular FOP p_n(λ) in the sequence of the FOPs with respect to ℒ.
 The polynomial p_k(λ) is (k-n)-quasi-orthogonal (note that n ≤ k). 
 Hence the roots of p_n(λ) are roots of p_k(λ) by Theorem <ref>.
 As discussed above, every minimal realization can be expressed as
 (B^*𝐞_1,   B^-1T_n B,  μ  m_ν(1)-1 B^-1𝐞_ν(1)),
 with T_n the block tridiagonal matrix (<ref>) corresponding to p_n(λ)
 and B an invertible matrix.
 Thus Lemma <ref> concludes the proof.
 

We remark that the previous theorem is a consequence of the Canonical Structure Theorem of the linear system theory;
see, e.g., <cit.>, <cit.>, <cit.> and the description in <cit.>.

  



§ THE LOOK-AHEAD LANCZOS ALGORITHM AND GAUSS QUADRATURE

   Consider a complex matrix A  and a complex vector 𝐯 of the corresponding dimension.
   The nth Krylov subspace generated by A and 𝐯 
   is the subspace 
   
    𝒦_n(A,𝐯) =   
    	    span{𝐯,A 𝐯,…,A^n-1 𝐯},

   which can be equivalently expressed as
   
    𝒦_n(A,𝐯) = { p(A) 𝐯 : p(λ) ∈𝒫_n-1}.
 
   The basic facts about Krylov subspaces had been given by Gantmacher in <cit.>;
   other results can be found, e.g., in <cit.>.
   
   Let A be a complex matrix, 𝐯, 𝐰 be complex vectors,
   and ℒ: 𝒫→ℂ be the linear functional defined by
   
    ℒ(p) = 𝐰^* p(A)  𝐯,    p(λ) ∈𝒫.
  
  Denoting with p̅(λ) the polynomial whose coefficients are the conjugates of the coefficients of p(λ)
  and noticing that  
   
    p(A)^* = p̅(A^*),

   for p(λ), q(λ) ∈𝒫_n-1, give
   
    ℒ(qp)  = 𝐰^*q(A)p(A) 𝐯 =  𝐰^* 𝐯,

   with 𝐯 = p(A)  𝐯∈𝒦_n(A,𝐯)
   and 𝐰 = q̅(A^*)  𝐰∈𝒦_n(A^*,𝐰).
   
   The non-Hermitian Lanczos algorithm (formulated by Lanczos in <cit.> and <cit.>)
   gives, when possible, the vectors 
   
    𝐯_0, …, 𝐯_n-1   and   𝐰_0, …, 𝐰_n-1,

   which are respectively basis of 𝒦_n(A,𝐯) and 𝒦_n(A^*,𝐰) 
   satisfying the biorthogonality conditions
   
    𝐰_i^*𝐯_j = 0,    i ≠ j,    and   𝐰_i^*𝐯_i ≠ 0,    i,j=0,…,n-1.

   In this case, there exist regular FOPs p_0(λ), …, p_n-1(λ)
   with respect to the linear functional (<ref>) so that
   
    𝐯_j = p_j(A) 𝐯   and   𝐰_j = p̅_j(A^*) 𝐰,    j=0,…,n-1.

   Hence bases satisfying (<ref>) exist if and only if ℒ is quasi-definite on 𝒫_n-1;
   see, e.g., <cit.>.
   
   In the non-Hermitian Lanczos algorithm, the vectors 𝐯_j, 𝐰_j, j=0,…,n-1,
   are obtained by the three-term recurrences satisfied by the regular FOPs p_0, …, p_n-1;
   for details refer to <cit.>, <cit.>, 
   <cit.>, <cit.>, <cit.>,
   also refer to the survey <cit.> 
   where the connection with the Gauss quadrature for quasi-definite linear functionals is described.     
   Considering biorthonormal vectors, i.e., 𝐰_i^*𝐯_i = 1,
   the non-Hermitian Lanczos algorithm corresponds to the three-term recurrences (<ref>)
   and can be given as Algorithm <ref>;
   see, e.g., <cit.>.
   The outputs of the first n-1 iterations of Algorithm <ref>
   define the matrices
   
    V_n = [𝐯_0, …, 𝐯_n-1]    and    W_n = [𝐰_0, …, 𝐰_n-1]

   which satisfy W_n^* V_n = I, with I the identity matrix of dimension n.
   Moreover, 
  
    A V_n = V_n J_n + 𝐯_n 𝐞_n^T, 
    
       A^* W_n = W_n J̅_n + 𝐰_n 𝐞_n^T,

   with J_n the complex Jacobi matrix (<ref>) associated with the linear functional (<ref>),
   and J̅_n the Jacobi matrix with conjugate elements (𝐯_n and 𝐰_n are defined in Algorithm <ref>).
Therefore the non-Hermitian Lanczos algorithm can be seen as a way to compute J_n and hence the Gauss quadrature for the functional (<ref>); 
see <cit.> and also <cit.>
(for the block Lanczos algorithm see, e.g., <cit.>).
   
   
 
   
   
   If the nth iteration of Algorithm <ref> gives β_n = 0, then the algorithm has a breakdown.
   Since β_n = ℒ(λ  p_n-1 p_n),
   a breakdown arises if and only if ℒ is not quasi-definite on 𝒫_n. 
   In this case, the FOP p_n(λ) is orthogonal to itself.
   Therefore there do not exist biorthonormal bases of the Krylov subspaces 
   𝒦_n+1(A,𝐯) and 𝒦_n+1(A^*,𝐰).
   Moreover, there does not exist a regular FOP p_n+1(λ).
  There are two kinds of breakdown for Algorithm <ref>:
  
  
  * lucky breakdown  (or benign breakdown), when 𝐯_n = 0 or 𝐰_n = 0;
  
  * serious breakdown, when 𝐯_n≠0 and
	  𝐰_n≠0, 
	  but 𝐰_n^*𝐯_n=0.
  
In the first case either 𝒦_n(A,𝐯) is A-invariant or 𝒦_n(A^*,𝐰) is A^*-invariant.
Then the algorithm is usually stopped since an invariant subspace is often a desirable result; 
see, e.g., <cit.>, <cit.> and <cit.>.
The second case is problematic. 
In <cit.> 
Wilkinson showed with some examples that well-conditioned matrices with well-conditioned eigenvectors can produce a breakdown.
Hence as Wilkinson wrote, serious breakdown “is not associated with any shortcoming in the matrix A. 
It can happen even when the eigenproblem of A is very well-conditioned. 
We are forced to regard it as a specific weakness of the Lanczos method itself.”
The interested reader can also refer to 
<cit.>, <cit.>, <cit.>, <cit.>,
  <cit.>, and <cit.>.
 


Taylor in <cit.> and Parlett, Taylor, and Liu in <cit.>
first proposed the look-ahead Lanczos algorithm,
a strategy able to deal with the breakdown problem.
When 𝐰_n^*𝐯_n=0, 
the idea behind their strategy is to look for a vector 𝐰_k∈𝒦_k+1(A^*, 𝐰),
with k>n big enough, so that 𝐰_k^*𝐯_n≠0 
and 𝐰_k^*𝐯_j = 0 for j=0,…,n-1.
In <cit.> Freund, Gutknecht, and Nachtigal implemented a different look-ahead strategy
considering sequences of FOPs and quasi-orthogonal polynomials.
Their procedure is based on the work of Gutknecht published in <cit.> and later in <cit.>;
see also the thesis <cit.> by Nachtigal and the description in <cit.> by Freund.
We also refer the reader to the strategy in <cit.> and the related work <cit.>. 
The following part will describe the basic ideas behind the look-ahead Lanczos algorithm by Freund, Gutknecht, and Nachtigal.






Consider the linear functional (<ref>) and let p_0(λ)≠ 0,p_1(λ),… 
be the sequence (<ref>) of polynomials so that 
p_ν(0)(λ) = p_0(λ), p_ν(1)(λ),  … are the regular FOPs 
and p_n is an (n-ν(t))-quasi-orthogonal polynomial for ν(t) < n < ν(t+1),
with ν(t+1) = ∞ when p_ν(t) is the last of the regular FOPs.
Moreover, consider the vectors

    𝐯_n = p_n(A) 𝐯   and   𝐰_n = p̅_n(A^*) 𝐰,    n=0, 1, … ,

and the matrices V^(t)_n = [𝐯_ν(t), …, 𝐯_n-1],
W^(t)_n =[𝐰_ν(t), …, 𝐰_n-1],
with V^(t) = V^(t)_ν(t+1) and W^(t) = W^(t)_ν(t+1)
for simplicity of notation.
Hence for ν(t) < n ≤ν(t+1), the columns of V_n = [V^(0), …, V^(t)_n] and of W_n = [W^(0), …, W^(t)_n]
are respectively basis of 𝒦_n(A, 𝐯) and 𝒦_n(A^*, 𝐰).
However, instead of the biorthogonality conditions (<ref>), the following block-biorthogonality conditions hold

    W^(t)*_n V^(k)_ℓ = 0,   for  t ≠ k, 
       and    
       W^(t)*_n V^(t)_n = Ω^(t)_n,

 with
 
    Ω^(t)_n = [ ℒ(p_ν(t), p_ν(t))    …   ℒ(p_ν(t), p_n-1) 
    ⋮      ⋮
    ℒ(p_n-1, p_ν(t)) 	     …   ℒ(p_n-1, p_n-1) 
    ];

 we denote Ω^(t)_ν(t+1) by Ω^(t). 
 
 By Theorem <ref> and the recurrences (<ref>)
 if ν(t) < n < ν(t+1), 
 then for some complex coefficients 𝐚_n = [α_n,ν(t), …, α_n,n-1] and β_n ≠ 0 
 the following recurrences hold
 
    β_n𝐯_n = A 𝐯_n-1 - ∑_j=ν(t)^n-1α_n,j𝐯_j,
           and   β̅_n𝐰_n = A^* 𝐰_n-1 - ∑_j=ν(t)^n-1α̅_n,j𝐰_j.

If n = ν(t+1) with t ≥ 0, then for some β_n ≠ 0 the recurrences (<ref>) give

    β_n 𝐯_n    = A𝐯_n-1           - ∑_j=ν(t)^n-1α_n,j𝐯_j - γ_n𝐯_ν(t-1)
    β̅_n 𝐰_n    = A^*𝐰_n-1  - ∑_j=ν(t)^n-1α̅_n,j𝐰_j - γ̅_n𝐰_ν(t-1),

where ν(-1)=-1, 𝐯_-1 = 𝐰_-1 = 0, γ_ν(1) = 0,

    γ_n = 𝐰_ν(t)-1^* A  𝐯_n-1/𝐰_ν(t)-1^* 𝐯_ν(t-1),    t ≥ 1,

and the coefficients 𝐚_n = [α_n,ν(t), …, α_n,n-1] are given as the solution of the system 

    Ω^(t) 𝐚_n = W^(t)* A 𝐯_n-1;

see the linear system (<ref>).
The described recurrences can be expressed in the matrix form

    A V_n = V_n T_n^T + β_n+1𝐯_n𝐞_n^T
       and   
      A^* W_n = W_n T_n^* + β̅_n+1𝐰_n𝐞_n^T,

with T_n^T the transpose of the block tridiagonal matrix T_n defined in (<ref>)
and T_n^* the conjugate transpose of T_n.
The resulting form of the look-ahead Lanczos algorithm is given as Algorithm <ref>
and corresponds to the algorithm proposed in <cit.>; see also <cit.>. 


 

  
  The first n iterations of Algorithm <ref>
  produce the coefficients of the block tridiagonal matrix T_n. 
  If ν(t) ≤ n < ν(t+1),
  then the Gauss quadrature 𝒢_ν(t) for the linear functional (<ref>)
  has the matrix formulation (<ref>) which is determined by the matrix T_n.
  Hence Algorithm <ref> produces Gauss quadratures for the linear functional (<ref>).
  Notice that by Lemma <ref>  
  the matrix T_n corresponds to the Gauss quadrature 𝒢_ν(t) for n = ν(t), …, ν(t+1)-1.
  Nevertheless, the iterations ν(t)+1, …, ν(t+1) of Algorithm <ref> are informative
  since they show that 𝒢_ν(t) has degree of exactness larger than 2ν(t)-1.
  At the same time, Algorithm <ref> also produces the triplet (𝐞_1, T_ν(t), μ  m_ν(1)-1𝐞_ν(1)), 
  i.e., the minimal partial realization (<ref>) (with B = I) of the sequence of Markov parameters defined by
  
    m_j = 𝐰^* A^j  𝐯,    for  j=0,1,… .


  
  Consider the case in which a benign breakdown does not arise
  and the determinants of the Hankel submatrices (<ref>) composed of the moments 
  of the linear functional (<ref>) are such that

    Δ_n-1≠ 0,  Δ_n+k = 0,    for  k = 0, 1, …,

known as incurable breakdown;
see <cit.>, <cit.>, <cit.>.
Then p_n(λ) is the last of the regular FOPs (n = ν(t)).
By Theorem <ref>,  
the quadrature 𝒢_n determined by p_n(λ) is the Gauss quadrature with maximal number of nodes (counting the multiplicities)
and it is exact for every polynomial.
Equivalently, let T_n be the block tridiagonal matrix obtained at the nth step of the Lanczos algorithm. 
Theorem <ref> gives

    ℒ(p) = 𝐰^* p(A) 𝐯 = 𝒢_n(p) = μ  m_ν(1)-1 𝐞_1^T p(T_n)  𝐞_ν(1),    p(λ) ∈𝒫.

Moreover, if f(λ) is a function so that f(A) and f(T_n) are well defined matrix functions,
then there exists a polynomial q(λ) interpolating in the Hermite sense f(λ) at the spectra of A and T_n (note that q(λ) depends on f(λ), A, and T_m);
see, e.g., <cit.>. 
Therefore 

    ℒ(f) = 𝐰^* q(A)  𝐯 = μ  m_ν(1)-1 𝐞_1^T q(T_n)  𝐞_ν(1) = 𝒢_n(f).

Looking at the Lanczos algorithm as a method for getting the Gauss quadrature for a linear functional (<ref>),
the incurable breakdown corresponds to the solution of the problem as well as the lucky breakdown.
Furthermore, the triplet (𝐞_1, T_n, μ  m_ν(1)-1𝐞_ν(1))
is a minimal realization of the transfer function associated with (𝐰, A, 𝐯),
i.e., it matches the Markov parameters (<ref>).
The previous considerations together with Theorem <ref> give a new proof for the Mismatch Theorem
based on the properties of the Gauss quadrature for linear functionals. 
The Mismatch Theorem was first proved in <cit.> by Taylor; see also <cit.>, 
and <cit.> where the theorem was connected with the minimal realization problem.

   Le T_n be the block tridiagonal matrix obtained at the nth step of Algorithm <ref>
   with A as the input matrix and 𝐰,𝐯≠ 0 as the input vectors. 
   If the algorithm has an incurable breakdown at the nth step, i.e., 
   the Hankel determinants corresponding to the linear functional (<ref>)  satisfy (<ref>),
   then each eigenvalue of T_n (known as Ritz value) is an eigenvalue of A.


Notice that the look-ahead Lanczos algorithm in <cit.>
 produces a block tridiagonal matrix different from the matrix T_n (<ref>).
 However, both the matrices are minimal realization of the same sequence of numbers and therefore they are similar.





§ CONCLUSION

The n-node Gauss quadrature 𝒢_n for a linear functional ℒ described in Section <ref> 
is a straightforward extension of the quadrature introduced for real-valued linear functionals in <cit.> to the complex case 
and it satisfies the following properties:

  
  * the Gauss quadrature 𝒢_n has degree of exactness at least 2n - 1;
  
  * the Gauss quadrature 𝒢_n exists and is unique if and only if the Hankel submatrix of moments H_n-1 is nonsingular, i.e., Δ_n-1≠ 0;
  
  * by Theorem <ref> the Gauss quadrature can be written in the matrix form 
	    𝒢_n(f) = μ  m_ν(1)-1 𝐞_1^T f(T_n)  𝐞_ν(1).
 
Note that such properties are weaker forms of the properties G1–G3 in Section <ref>.

  


Figure <ref> summarizes the connections
between the Gauss quadrature for linear functionals, minimal partial realization, and look-ahead Lanczos algorithm.
On the right-hand side, 
the triplet (𝐰, A, 𝐯) is a partial realization matching the first k+1 elements of the sequence of complex numbers m_0, m_1, … .
A minimal partial realization
can be obtained applying the look-ahead Lanczos algorithm 
to the matrix A and the vectors 𝐯, 𝐰
(this is also connected with the concept of model reduction, see, e.g., <cit.>).
Notice that
the Lanczos algorithm applied to the partial realization (<ref>) 
is related to the Berlekamp-Massey algorithm <cit.> (see <cit.>, <cit.>, and <cit.>).
On the left-hand side, 
the sequence m_0, m_1, … determines the linear functional ℒ: 𝒫→ℂ 
by defining its moments. 
The functional ℒ can be approximated by a Gauss quadrature. 
Among all the Gauss quadratures exact on 𝒫_k,
there is one with the minimal number of nodes n (counting the multiplicities).
Such quadrature can be written in the matrix form

    𝒢_n(f) = μ  m_ν(1)-1 𝐞_1^T f(T_n)  𝐞_ν(1),

i.e., it corresponds to the minimal partial realization matching m_0, …, m_k.


In Sections <ref> and <ref>, we discussed the correspondence between the incurable breakdown in the look-ahead Lanczos algorithm and the minimal realization of an infinite sequence of complex numbers (and to the unique Gauss quadrature exact for every polynomial).
This connection led us to a new proof for the Mismatch Theorem <ref>.


We would like to thank Zdeněk Strakoš for the helpful comments and improvements suggested.
This work has been supported by Charles University Research program No. UNCE/SCI/023 
and by the Ministry for Scientific and Technological Development, Higher Education and Information Society of R. Srpska.












spmpsci























