The next task is to establish an explicit formula for the Cholesky factors
${D}_{n}$
in terms of the Jacobi parameters. First, we obtain a recursive relation for
${D}_{n}$
.
Lemma 3.3.
For
$n\ge 1$
,
$${D}_{n}={F}_{n}(1\oplus {D}_{n1}),$$
where
$${F}_{n}=\left[\begin{array}{cccccc}1& {b}_{0}& {c}_{0,1}& {c}_{0,2}& ...& {c}_{0,n1}\\ 0& {a}_{1}& {b}_{1}& {c}_{1,2}& & {c}_{1,n1}\\ 0& 0& {a}_{2}& {b}_{2}& & \mathtt{.}\mathtt{.}\mathtt{.}\\ 0& 0& 0& {a}_{3}& \mathtt{.}\mathtt{.}\mathtt{.}& \\ \mathtt{.}\mathtt{.}\mathtt{.}& & & \mathtt{.}\mathtt{.}\mathtt{.}& \mathtt{.}\mathtt{.}\mathtt{.}& {b}_{n1}\\ 0& & ...& & 0& {a}_{n}\end{array}\right].$$

Proof.
We have
${D}_{0}=1$
and then
$${D}_{1}=\left[\begin{array}{cc}1& {b}_{0}\\ 0& {a}_{1}\end{array}\right]={F}_{1}\left[\begin{array}{cc}1& 0\\ 0& {D}_{0}\end{array}\right].$$
Assume the statement is true up to
$n$
. Then
$${D}_{n+1}=\left[\begin{array}{cc}{D}_{n}& \\ & {J}_{n+2,n+1}\dots {J}_{2,1}\\ 0& \end{array}\right].$$
By the induction hypothesis,
$$\left[\begin{array}{c}{D}_{n}\\ 0\end{array}\right]=\left[\begin{array}{c}{F}_{n}\left(1\oplus {D}_{n1}\right)\\ 0\end{array}\right]={F}_{n+1}\left[\begin{array}{cc}1& 0\\ 0& {D}_{n1}\\ 0& 0\end{array}\right]$$
and we notice that
$${J}_{n+2,n+1}\dots {J}_{2,1}={F}_{n+1}\left[\begin{array}{c}0\\ {J}_{n+1,n}\dots {J}_{2,1}\end{array}\right],$$
so that
$${D}_{n+1}={F}_{n+1}\left[\begin{array}{ccc}1& 0& 0\\ 0& {D}_{n1}& \\ & & {J}_{n+1,n}\dots {J}_{2,1}\\ 0& 0& \end{array}\right]={F}_{n+1}\left(1\oplus {D}_{n}\right).$$
□
The matrices
${F}_{n}$
have a very simple recursive multiplicative structure. Actually it is convenient to make the dependence of
${F}_{n}$
on the Jacobi parameters more explicit and introduce
$${F}_{m,k}=\left[\begin{array}{ccccc}1& {b}_{k}& {c}_{k,k+1}& ...& {c}_{k,m1}\\ 0& {a}_{k+1}& {b}_{k+1}& & {c}_{k+1,m1}\\ & 0& {a}_{k+2}& & \\ & & & ...& {b}_{m1}\\ & & & 0& {a}_{m}\end{array}\right]$$
for
$m\ge 1$
and
$0\le k<m1$
. In particular,
${F}_{n,0}={F}_{n}$
. We show that the building blocks of
${F}_{m,k}$
(consequently, of
${D}_{n}$
) are the
$2\times 2$
matrices
$${B}_{k}=\left[\begin{array}{cc}1& {b}_{k}\\ 0& {a}_{k+1}\end{array}\right],k\ge 0,$$
and the
$(lk+2)\times (lk+2)$
matrices
$${C}_{k,l}=\left[\begin{array}{ccccc}1& 0& ...& 0& {c}_{k,l}\\ 0& 1& & 0& 0\\ & & & ...& 0\\ 0& & & 0& 1\end{array}\right],0\le k<l.$$
Lemma 3.4.
For
$m\ge 1$
and
$0\le k<m1$
,
$${F}_{m,k}=\left(1\oplus {F}_{m,k+1}\right){G}_{m,k},$$
where
$${G}_{m,k}={C}_{k,m1}\left({C}_{k,m2}\oplus 1\right)\dots \left({C}_{k,k+1}\oplus {1}_{mk2}\right)\left({B}_{k}\oplus {1}_{mk1}\right).$$

Proof.
The proof is a straightforward calculation and can be omitted. □
Once again it is convenient to visualize all those matrix multiplications by means of a transmission line picture similar to the one in Figure 3. Thus, Figure 5 illustrates how to calculate
${D}_{3}$
by using Lemma 3.3 and Lemma 3.4 . In particular, if
$1$
is the imput at
$A$
then at
$B$
we read the expression of
$K(0,3)$
in terms of the Jacobi parameters,
$$K(0,3)={b}_{0}^{3}+{b}_{0}{a}_{1}{c}_{0,1}+{a}_{1}{c}_{0,1}{b}_{0}+{a}_{1}{b}_{1}{c}_{0,1}+{a}_{1}{a}_{2}{c}_{0,2}.$$
Figure 5 suggests a connection with weighted Lukasiewicz paths. A Lukasiewicz path of length
$n$
is a path in the positive quadrant of the lattice
${\mathbb{Z}}^{2}$
which starts at
$(0,0)$
, ends at
$(n,0)$
, and consists of rise unit steps, horizontal unit steps, and fall steps of arbitrary depth. Let
${\mathcal{\mathcal{L}}}_{n,0}$
denote the set of Lukasiewicz paths of length
$n$
.
Figure 5
. Transmission line representation for
${D}_{3}$
We also consider
${\mathcal{\mathcal{L}}}_{n,k}$
the set of paths of length
$n$
in the positive quadrant, starting at
$(0,0)$
and consisting of the same type of steps as above, but ending at
$(n,k)$
. We introduce a weigth on the elements of
${\mathcal{\mathcal{L}}}_{n,k}$
as follows. Let
$\mathbf{p}\in {\mathcal{\mathcal{L}}}_{n,k}$
consists of steps
${\mathbf{p}}_{1}$
,
$\dots $
,
${\mathbf{p}}_{n}$
. Then
$$w(\mathbf{p}){=}^{n}{\prod}_{k=1}w\left({\mathbf{p}}_{k}\right)$$
and
$w\left({\mathbf{p}}_{k}\right)=\{\begin{array}{cc}{a}_{l}& \text{if}{\mathbf{p}}_{k}\text{is a rise step}(j,l)\to (j+1,l+1)\text{for some}j\ge 0\text{;}\\ {b}_{l}& \text{if}{\mathbf{p}}_{k}\text{is a horizontal step}(j,l)\to (j+1,l)\text{for some}j\ge 0\text{;}\\ {c}_{k,l}& \text{if}{\mathbf{p}}_{k}\text{is a fall step}(j,l)\to (j+1,k)\text{for some}j\ge l\text{.}\end{array}$
Figure 6
. Passing from paths of length
$n1$
to paths of lentgh
$n$
Theorem 3.5.
The Cholesky factor
${D}_{n}={\left[{d}_{i,j}\right]}_{0\le i,j\le n}$
is given by the formula
$$\begin{array}{c}{d}_{i,j}={\sum}_{\mathbf{p}\in {\mathcal{\mathcal{L}}}_{j,i}}w(\mathbf{p}),i\le j,(i,j)\ne (0,0).\end{array}$$ 
(3.8)


Proof.
We can prove the statement by induction on
$n$
. For
$n\le 3$
, 3.8 is seen from Figure 5. The general induction step is provided by Lemma 3.3 . Thus,
$$\begin{array}{ccc}{d}_{0,n}& =& {b}_{0}{d}_{0,n1}+{c}_{0,1}{d}_{1,n1}+\dots +{c}_{0,n1}{d}_{n1,n1}\end{array}$$  
$$\begin{array}{ccc}{d}_{1,n}& =& {a}_{1}{d}_{0,n1}+{b}_{1}{d}_{1,n1}+\dots +{c}_{1,n1}{d}_{n1,n1}\end{array}$$  
$$\begin{array}{ccc}& ...& \end{array}$$  
$$\begin{array}{ccc}{d}_{n,n}& =& {a}_{n}{d}_{n1,n1},\end{array}$$  
and these relations are precisely those obtained by passing from weighted paths of length
$n1$
to weighted paths of length
$n$
, as showed in Figure 6. □
Remarks
$\left(a\right)$
For a Hankel kernel
$K$
, Theorem 3.5 reduces to wellknown results in the combinatorial theory for orthogonal polynomials (on the real line), [
4]
, [
9]
. Indeed, by 3.7 there are no fall steps of depth other than one. In this case, the summation in 3.8 is only over Motzkin paths, which is the classical formula in [
4]
, [
9]
. It might be interesting to note that the correpsonding formula for orthogonal polynomials on the unit circle, 2.4 , involves summation over labelled configurations in
${\mathbb{Z}}^{2}$
rather than over weighted paths.
$\left(b\right)$
There are other significant differences between the two parametrizations discussed in this paper. For instance, the parameters
$\left\{{\gamma}_{k,j}\right\}$
have the following inheritance property: the parameters of the kernel
${K}^{\left(1\right)}={\left[K(l,m)\right]}_{1\le l,m}$
are precisely
$\{{\gamma}_{k,j}{\}}_{1\le k<j}$
.
The Jacobi parameters do not have such a property. Another difference involves computations of determinants. Thus, we have already notice the formula (we assume
$K(0,0)=1$
):
$$det{\left[K(l,m)\right]}_{l,m=0}^{n}{=}^{n}{\prod}_{k=1}{f}_{k}{\prod}_{0\le i<j\le n}{d}_{i,j}^{2},$$
and from Lemma 3.3 we deduce
$$det{\left[K(l,m)\right]}_{l,m=0}^{n}{=}^{n}{\prod}_{k=1}{a}_{k}^{2(nk)},$$
which does not involve all the Jacobi parameters (up tu
$n$
). So the first determinant formula is much tighter in its parameters.
$\left(c\right)$
Theorem 3.5 gives, in particular, that
$$\begin{array}{c}K(0,n)={\sum}_{\mathbf{p}\in {\mathcal{\mathcal{L}}}_{n,0}}w(\mathbf{p}),n\ge 1.\end{array}$$ 
(3.9)

Since the Jacobi parameters do not have the inheritance property mentioned above, we cannot have formulae of this type for any
$K(l,n)$
. Instead we have the following construction.
For
$n$
fixed we consider admissible steps in the psitive quadrant of the following types: between the vertical lines
$x=0$
and
$x=n$
only of Lukasiewicz type are allowed and between the vertical lines
$x=n$
and
$x=2n$
only reflections with respect to the line
$x=n$
of Lukasiewicz steps are allowed (and they are weighted with the complex conjugate of the weight of the reflected Lukasiewicz step, see Figure 7).
Denote by
${\mathcal{K}}_{n,k}$
the set of paths in the positive quadrant of
${\mathbb{Z}}^{2}$
made of admissible steps, starting at
$(0,0)$
and ending at
$(n+k,0)$
,
$0\le k\le n$
. In particular,
${\mathcal{K}}_{n,0}={\mathcal{\mathcal{L}}}_{n,0}$
. The weights are defined correspondingly. With these elements, we deduce from Theorem 3.5 that
$$\begin{array}{c}K(l,n)={\sum}_{\mathbf{p}\in {\mathcal{K}}_{n,l}}w(\mathbf{p}),0\le l\le n.\end{array}$$ 
(3.10)

$\left(d\right)$
We notice that the proof of Theorem 2.2 gives a formula for the Cholesky factor
${D}_{n}$
in terms of Dyck type paths analogous to formula 3.8 .
$\square $
References

T. Banks, T. Constantinescu, and N. ElSissi, Tensor algebras and displacement structure. IV. Invariant kernels, math.FA/0410491, to appear in Linear Alg. Appl.

T. Constantinescu, Schur analysis of positive blockmatrices, in I. Schur Methods in Operator Theory and Signal Processing (I. Gohberg, Ed.), Birkhäuser, Basel, 1986, pp. 191206.

T. Constantinescu, Schur Parameters, Factorization and Dilation Problems, Birkhäuser, Basel, 1996.

P. Flajolet, Combinatorial aspects of continued fractions, Discrete Math., 32(1980), 125161.

A. N. Kolmogorov, Sur l'interpolation et l'extrapolation des suites stationaire, C. R. Acad. Sci. (Paris), 208(1939), 20432045.

B. Simon, Orthogonal Polynomials on the Unit Circle, Colloquium Publications, 54, Amer. Math. Soc., Providence, Rhode Island, 2004.

R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge Univ. Press, Cambridge, 1999.

G. Szegö, Orthogonal Polynomials, Colloquium Publications, 23, Amer. Math. Soc., Providence, Rhode Island, 1939.

G. Viennot, A combinatorial theory for general orthogonal polynomials with extensions and applications, in: Orthogonal polynomials and applications (BarleDuc, 1984), 139157, Lecture Notes in Math., 1171, Springer, Berlin, 1985.
Department of Mathematics, University of Texas at Dallas, Richardson, TX 75083 Email address : tiberiu@utdallas.edu Department of Mathematics, University of Texas at Dallas, Richardson, TX 75083 Email address : nae021000@utdallas.edu