Ronan Quarez
email: ronan.quarez@univ-rennes1.fr

Sturm and Sylvester algorithms revisited via tridiagonal determinantal representations

Keywords:

First, we show that Sturm algorithm and Sylvester algorithm, which compute the number of real roots of a given univariate polynomial, lead to two dual tridiagonal determinantal representations of the polynomial. Next, we show that the number of real roots of a polynomial given by a tridiagonal determinantal representation is greater than the signature of this representation.

Introduction

There are several methods to count the number of real roots of an univariate polynomial p(x) ∈ R[x] of degree n (for details we refer to [BPR]). Among them, the Sturm algorithm says that the number of real roots of p(x) is equal to the number of Permanence minus the number of variations of signs which appears in the leading coefficients of the signed remainders sequence of p(x) and p ′ (x).

Another method is the Sylvester algorithm which says that the number of real roots of p(x) is equal to the signature of the symmetric matrix whose (i, j)-th entry is the i + j-th Newton sums of the roots of the polynomial p(x).

One purpose of the paper is to point out, at least in the generic situation, that these two classical algorithms can be viewed as dual.

In section 1, we introduce signed remainders sequences of two given monic polynomials p(x) and q(x) of respective degrees n and n -1. With some conventions of signs and others, we give a presentation of this sequence through a tridiagonal matrix Td(p, q). Next, we give a decomposition of this tridiagonal matrix as Td(p, q) = LC T p L -1 where L is lower triangular and C T p is the transposed of the companion matrix associated to p(x).

1

In section 2, we introduce the duality between the Sturm and Sylvester algorithm, first when the polynomial p(x) has only single and real roots, and then in Theorem 2.5 we generalize it to the generic case.

More precisely, on one hand we have p(x) = det(xId n -Td(p, q)) q(x) = det(xId n-1 -Td(p, q) n-1 )

with the conventions that Id n (or Id in short) denotes the identity matrix of R n×n and A k ∈ R k×k (respectively A k ∈ R k×k ) denotes the k-th principal submatrix (respectively the k-th antiprincipal submatrix) of A which corresponds to extracting the first k (respectively the last k) rows and columns in the matrix A ∈ R n×n .

On the other hand, we consider a natural Hankel (hence symmetric) matrix H(q/p) ∈ R n×n associated to p(x) and q(x). Generically it admits an LU decomposition of the form H(q/p) = KJK T where J is a signature matrix (a diagonal matrix with coefficients ±1 onto the diagonal) and K is lower triangular. Then, we introduce the tridiagonal matrix Td = K -1 C T p K, which is such that p(x) = det(xId n -Td).

If we consider that the matrices Td(p, q) and Td represent linear mappings in some basis, then the duality Theorem 2.5 means that one matrix can be deduced from the other simply by reversing the ordering of the basis.

We shall mention that, in the case when all the roots of p(x) are real, the existence of a tridiagonal symmetric matrix Td given by the signed remainders sequence of p(x) and q(x) together with the identity p(x) = det(xId n -Td) corresponds to the Routh-Lanczos algorithm which answers a structured Jacobi inverse problem. Namely, the question to find a real symmetric tridiagonal matrix A with a given characteristic polynomial p(x) and such that the characteristic polynomial of its principal minor A n-1 , of size n -1, is proportional to p ′ (x). We refer to [EP] for a survey on the subject.

In section 3, we focus on the relation of the question of real roots counting and the question of determinantal representation. We say that p(x) = det(J -xA) is a determinantal representation of the polynomial p(x) if J ∈ R n×n is a signature matrix and A ∈ R n×n is a symmetric matrix.

Remark that we may transform the identity p(x) = det(J -xA) into p * (x) = det(xJ -A) where p * (x) is the reciprocal polynomial of p(x). If we write

p * (x) = det(J) × det(xId -AJ),
it shows a connexion with the results of section 2 when the matrix AJ is tridiagonal. More precisely, we establish that such a determinantal representation is always possible : we may even find a family of representations for a given polynomial p(x). We show also that, given such a determinantal representation for a polynomial p(x), its number of real roots is at least equal to the signature of the signature matrix J.

Finally, in section 4 we end with some worked examples.

1 Tridiagonal representation of signed remainders sequences

Definitions

Let α = (α 1 , . . . , α n ), β = (β 1 , . . . , β n-1 ) and γ = (γ 1 , . . . , γ n-1 ) be three sequences of real numbers. We set the tridiagonal matrix Td(α, β, γ) to be :

Td(α, β, γ) =          α n γ n-1 0 . . . 0 β n-1 α n-1 γ n-2 . . . . . . 0 β n-2 . . . . . . 0 . . . . . . . . . . . . γ 1 0 . . . 0 β 1 α 1         
Let p(x) and q(x) be two monic polynomials of respective degrees n and n -1. We set SRemS(p, q) = (p k (x)) k to be the signed remainders sequence of p(x) and q(x) defined in the following way :

   p 0 (x) = p(x) p 1 (x) = q(x) p k (x) = q k+1 (x)p k+1 (x) -ǫ k+1 β 2 k+1 p k+2 (x) (1)
where

       p k (x), q k+1 (x) ∈ R[x], ǫ k+1 ∈ {-1, +1}, β k+1 is a positive real number, p k+2 (x) is monic and deg p k+2 < deg p k+1 .
(2) This is a finite sequence which stops at the step just before we reach the zero polynomial as remainder. With these conventions, the signed remainders sequence SRemS(p, q) that we obtain is also called the Sturm-Habicht sequence of p(x) and q(x).

Let us assume that there is no degree breakdown in SRemS(p, q). Namely :

(∀k ∈ {0, . . . , n}) (deg p k = n -k) (3)
Then, q k+1 (x) is a degree one polynomial which we write q k+1 (x) = (x -α k+1 ) with α k+1 ∈ R. Another consequence is that gcd(p, q) = 1.

Let γ k+1 = ǫ k+1 β k+1 and consider the following tridiagonal matrix :

Td(p, q) = Td(α, β, γ)
We may read on this matrix all the informations about the signed remainders sequence SRemS(p, q). For a given tridiagonal matrix Td = Td(α, β, γ) ∈ R n×n , we define the first principal lower diagonal (respectively the first principal upper diagonal) of Td to be the sequence β = (β 1 , . . . , β n-1 ) (respectively γ = (γ 1 , . . . , γ n-1 )). We will say that these first principal diagonals are non-singular if all the coefficients β i (respectively γ i ) are different from zero.

Note that the no degree breakdown assumption (3) implies that the principal diagonals of Td(p, q) are non-singular. Proposition 1.1 (i) To any tridiagonal matrix Td = Td(α, β, γ) with non-singular principal diagonals, we may canonically associate a (unique) couple of monic polynomials p(x) and q(x) of respective degrees n and n -1 such that the sequence SRemS(p, q) has no degree breakdown and the characteristic polynomial of Td k is equal to p n-k (x) :

det(xId k -Td k ) = p n-k (x).
(ii) To any couple of monic polynomials p(x) and q(x) of respective degrees n and n -1 such that SRemS(p, q) has no degree breakdown, we may associate a unique tridiagonal matrix with non-singular principal diagonals Td(p, q) = Td(α, β, γ) satisfying for all k, β k > 0 and γ k = ǫ k β k where ǫ k = ±1.

(iii) When we have (i) and (ii), the matrix T d(p, q)) × P is tridiagonal and symmetric, where we have set

P =        ǫ n-1 × . . . × ǫ 1 . . . ǫ 2 × ǫ 1 ǫ 1 1       
.

(iv) When we have (i) and (ii), the sequence of signs in the leading coefficients of the signed remainders sequence SRemS(p, q) is :

(1, 1, ǫ 1 , ǫ 2 , ǫ 1 × ǫ 3 , ǫ 2 × ǫ 4 , ǫ 1 × ǫ 3 × ǫ 5 , . . . , ǫ n-1 mod 2 × . . . × ǫ n-3 × ǫ n-1 )
Proof : Concerning (i), the polynomials p(x) and q(x) are taken to be p(x) = det(xId n -Td) and q(x) = det(xId n-1 -Td n-1 ). Then, we set for all k,

δ n-k (x) = det(xId k -Td k )
(where Td k is the k-th principal submatrix of Td) and we develop the determinant

δ 0 (x) = det(xId n -Td)
with respect to the last row. We get

δ 0 (x) = (x -α 1 )δ 1 (x) -(β 1 γ 1 )δ 2 (x)
Repeating the process, we obtain the same recurrence relation as the one defining the sequence (p k (x)) k in (1). Since δ 0 (x) = p 0 (x) and δ 1 (x) = p 1 (x), we get the wanted identity.

Point (ii) follows straightforward from the beginning of the section, whereas points (iii) and (iv) follows from elementary computation.

⊓ ⊔

We may note that to the tridiagonal matrix Td(p, q), we may associate also another natural polynomial remainder sequence : SRemS(p, q) = SRemS(p, q) where p(x) = det(xId n -Td) and q(x) = det(xId n-1 -Td n-1 ), with the convention that Td k is the k-th antiprincipal submatrix of Td. The signed remainders sequence SRemS(p, q) will be considered as the dual signed remainders sequence of SRemS(p, q). This only means that we may read on a tridiagonal matrix from the top left rather than from the bottom right !

For cosmetic reasons we will write Td(p, q) in place of Td(p, q). We obviously have :

Td(p, q) = Ad × Td(p, q) × Ad (4)
where Ad n ∈ R n×n (Ad in short) stand for the anti-identity matrix of size n :

Ad n =       0 . . . 0 1 . . . . . . . . . 0 0 . . . . . . . . . 1 0 . . . 0      

Companion matrix

We denote by A T the transposed of the matrix A ∈ R n×n and we define the companion matrix of the polynomial p(x) = x n + a n-1 x n-1 + . . . + a 0 to be

C p =          0 . . . . . . 0 -a 0 1 . . . . . . -a 1 0 . . . . . . . . . . . . . . . . . . . . . 0 -a n-2 0 . . . 0 1 -a n-1         
We recall a well-know identity (see for instance [EP]) :

Proposition 1.2 Let p(x) and q(x) be two monic polynomials of respective degrees n and n -1 such that SRemS(p, q) has no degree breakdown. Then, there is a lower triangular matrix L such that Td(p, q) = LC T p L -1 (5)

Proof : With the notation of Subsection 1.1, let P(x) = (γ 1 . . . γ n-1 p n (x), . . . , γ 1 p 2 (x), p 1 (x)). A direct computation gives

P(x) (Td(p, q)) T = xP(x) + (0, . . . , 0, -p(x))
Let U be the upper triangular matrix whose columns are the coefficients of the polynomials of P(x) in the canonical basis C(x) = (1, x, . . . , x n-1 ). In other words :

C(x)U = P(x) Besides, we have C(x)C p = xC(x) + (0, . . . , 0, -p(x)) Thus C(x)C p U = xC(x)U + (0, . . . , 0, -p(x)) since p 1 (x) is monic = P(x) (Td(p, q)) T = C(x)U (Td(p, q)) T
We deduce the identity

V (x 1 , . . . , x n )C p U = V (x 1 , . . . , x n )U (T d(p, q)) T
for any Vandermonde matrix V (x 1 , . . . , x n ) whose lines are (1, x i , . . . , x n-1 i

) for i = 1 . . . n. If we choose the n reals x 1 , . . . , x n to be distinct, then V (x 1 , . . . , x n ) becomes invertible and we get :

Td(p, q) = LC T p L -1
where L is the lower triangular matrix defined by L = U T . ⊓ ⊔

The following result says that the decomposition generically exists for any tridiagonal matrix, and also it is unique : Proposition 1.3 Any tridiagonal matrix Td with non-singular principal diagonals can be written Td = LC T p L -1 where p(x) = det(xId -Td) and L is a lower triangular matrix. Moreover the matrix L is unique up to a multiplication by a real number.

Proof : The existence is given by Proposition 1.1 and Proposition 1.2.

We come now to the unicity. Assume that

L 1 C T p L -1 1 = L 2 C T p L -1 2 where L 1 and L 2 are lower triangular. Then, L = L -1 2 L 1 is a lower triangular matrix which commute with C T p . If L = (t i,j ) 1≤i,j≤n , then LC T p =         0 t 1,1 0 . . . 0 . . . t 2,1 t 2,2 . . . . . . . . . . . . . . . 0 0 t n-1,1 . . . . . . t n-1,n-1 ? . . . . . . . . . ?         and C T p L =         t 2,1 t 2,2 0 . . . 0 t 3,1 t 3,2 t 3,3 . . . . . . . . . . . . . . . 0 t n,1 . . . . . . t n,n-1 t n,n ? . . . . . . . . . ?         Thus t 1,1 = t 2,2 = . . . = t n,n and t 2,1 = t 3,2 = . . . = t n,n-1 = 0 and t 3,1 = t 4,2 = . . . = t n,n-2 = 0,
and so on until t n,1 = 0. We deduce that L = λId and we are done.

⊓ ⊔

Sturm algorithm

As a particularly important case of signed remainders sequences, we shall mention the Sturm sequence which is SRemS(p, q) where q is taken to be the derivative of the polynomial p(x) up to normalization, i.e. q = p ′ /deg (p). For a given finite sequence ν = (ν 1 , . . . , ν k ) of elements in {-1, +1}, we recall the Permanence minus Variations number :

PmV(ν 1 , . . . , ν k ) = k-1 i=1 ν i ν i+1 .
Here the sequence ν will be for the sequence of signs of leading coefficients in SRemS(p, q). Then, the Sturm Theorem [START_REF] Basu | Algorithms in Real Algberaic Geometry[END_REF]Theorem 2.50] says that the number PmV(ν) is exactly the number of real roots of p(x).

If we assume that the polynomial p(x) has n distinct real roots, then the Sturm sequence has no degree breakdown and for all k we have ν k = 1. Hence we get a symmetric tridiagonal matrix Td(p, q) which has the decomposition Td(p, q) = LC T p L -1 where L is the lower triangular matrix defined as in subsection 1.2. In particular, the last row of L gives the list of coefficients of the polynomial q(x) in the canonical basis.

Duality between Sturm and Sylvester algorithms 2.1 Sylvester algorithm

Let us introduce the symmetric matrix Newt p (n) = (n i,j ) 0≤i,j≤n-1 define as

n i,j = Trace (C i+j p ) = N i+j
which is nothing but the i + j-th Newton sum of the polynomial p(x). To be more explicit, if α 1 , . . . , α n denote all the complex roots of the polynomial p(x), then the k-th Newton sum is the real number

N k = α k 1 + . . . + α k n .
Recall that the signature sign(A) of a real symmetric matrix A ∈ R n×n , is defined to be the number p -q, where p is the number of positive eigenvalues of A (counted with multiplicity) and q the number of negative eigenvalues of A (counted with multiplicity). The Sylvester Theorem (which has been generalized later by Hermite : [START_REF] Basu | Algorithms in Real Algberaic Geometry[END_REF]Theorem 4.57]) says that the matrix Newt p (n) is invertible if and only if p(x) has only single roots, and also that sgn(Newt p (n)) is exactly the number of distinct real roots of p(x).

In particular, if the polynomial p(x) has n distinct real roots, then the matrix Newt p (n) is positive definite. Thus, by the Choleski decomposition algorithm, we can find a lower triangular matrix K such that Newt p (n) = KK T . Le us show how to exploit this decomposition.

First, we write p(x) = det(xId -C T p ) Then, we introduce a useful identity (which will be discussed in more details in the forthcoming section) :

Newt p (n)C p = C T p Newt p (n), So, we get : p(x) = det(xId -K -1 C T p K)
Note that the matrix K -1 C T p K is tridiagonal. Our purpose in the following is to establish a connexion with the identity p(x) = det(xId -LC T p L -1 ) obtained in Proposition 1.3.

More generally, we will point out a connexion between tridiagonal representations associated to signed remainders sequences on one hand, and tridiagonal representations derived from decompositions of some Hankel matrices on the other hand.

Hankel matrices and Intertwinning relation

Roughly speaking, the idea of previous section is to start with the canonical companion identity

p(x) = det(xId -C T p )
and then to use a symmetric invertible matrix H satisfying the so-called intertwinning relation

HC p = C T p H (6)
Since H is supposed to be symmetric invertible, Equation ( 6) only says that the matrix HC p is symmetric. It is a classical and elementary result that a matrix H satisfying equation ( 6) is necessarily an Hankel matrix.

Definition 2.1 We say that the matrix

H = (h i,j ) 0≤i,j≤n-1 ∈ R n×n is an Hankel matrix if h i,j = h i ′ ,j ′ whenever i + j = i ′ + j ′ .
Then, it makes sense to introduce the real numbers a i+j = h i,j which allow to write in short H = (a i+j ) 0≤i,j≤n-1 .

Let s = (s k ) be a sequence of real numbers. We denote by H n (s) or by H(s 0 , . . . , s 2n-2 ) the following Hankel matrix of R n×n :

H n (s) = (s i+j ) 0≤i,j≤n-1 =      s 0 s 1 . . . s n s 1 . . . s n+1 . . . . . . . . . . . . s n s n+1 . . . s 2n-2     
We get from [START_REF] Basu | Algorithms in Real Algberaic Geometry[END_REF]Theorem 9.17] :

Proposition 2.2 Let p(x) = x n + a n-1 x n-1 + . . . + a 0 and s = (s k ) be a sequence of real numbers. The following assertions are equivalent

(i) (∀k ≥ n) (s k = -a n-1 s k-1 -. . . -a 0 s k-n ) (ii) There is a polynomial q(x) of degree deg q < deg p such that q(x) p(x) = ∞ j=0 s j x j+1
(iii) There is an integer r ≤ n such that det(H r (s)) = 0, and for all k > r, det(H k (s)) = 0.

Whenever these conditions are fulfilled, we denote by H n (q/p) the Hankel matrix H n (s).

Back to the intertwinning relation ( 6) : it is immediate that an Hankel matrix H is a solution if and only if the (finite) sequence (s 0 , . . . , s 2n-2 ) satisfies the linear recurrence relation of Proposition 2.2(i), for k = n, . . . , 2n -2.

For further details and developments about the intertwinning relation, we refer to [HV].

The vector subspace of Hankel matrices in R n×n satisfying relation ( 6) has dimension n, and contains a remarkable element : the Hankel matrix Newt p (n) that was considered in subsection 2.1 about Sylvester algorithm. Indeed, it is a well-known and elementary fact that the N k 's are real numbers which verify the Newton identities :

(∀k ≥ n) (N k + a n-1 N k-1 + . . . + a 0 N k-n = 0)

Barnett formula

First, recall that if p(x) = x n + a n-1 x n-1 + . . . + a 0 and q(x) is a (non-necessarily monic) polynomial in R[x] whose degree is equal to n -1, the Bezoutian of p(x) and q(x) is defined as the two-variables polynomial :

Bez(p, q) = q(y)p(x) -q(x)p(y) x -y ∈ R[x, y]
Let B(z) be any basis of the n-dimentional vector space R[z]/p(z) over R. We denote by Bez B (p, q) the symmetric matrix of the coefficients of Bez(p, q) with respect to the basis B(x) and B(y).

Among all the basis of R[z]/p(z) that will be interesting for the following, let us mention the canonical basis C = (1, z, . . . , z n-1 ) and also the (degree decreasing) Horner basis H(z) = (h 0 , . . . , h n-1 ) associated to the polynomial p(z) and which is defined by :

                   h 0 (z) = z n-1 + a n-1 z n-2 + . . . + a 1 . . . h i (z) = z n-1-i + a n-1 z n-2-i + . . . + a i+1 = zh i+1 (z) + a i+1 . . . h n-2 (z) = z + a n-1 h n-1 (z) = 1
We recall from [START_REF] Basu | Algorithms in Real Algberaic Geometry[END_REF]Proposition 9.20] :

Proposition 2.3 Let p(x) and q(x) be two polynomials such that deg q < deg p = n. Let s be the sequence of real numbers defined by

q(x) p(x) = ∞ j=0 s j x j+1
Then, Bez H (p, q) = H n (s) = H n (q/p).

We come to a central proposition which is a consequence of the Barnett formula [Ba].

Proposition 2.4 Let p(x) and q(x) be two polynomials such that deg q < deg p = n and let P CH be the change of basis matrix from the canonical basis C to the Horner basis H. We have

q(C p ) = P T CH × H n (q/p)
Proof : The Barnett formula has been established in [Ba] using direct matrix computations.

For the convenience of the reader, we give here another proof (which may be found at various places in the literature).

The obvious identity q(y)(p(x) -p(y)) = q(y)p(x) -p(y)q(x) + p(y)(q(x) -q(y))

implies, by definition of the Bezoutian B(p, q), that :

q(y) p(x) -p(y) x -y ≡ Bez(p, q) mod p(y)
Noticing that p(x)-p(y)

x-y

= n-1 j=0 h j (y)x j , we get q(y)

n-1 j=0 h j (y)x j ≡ C(y)Bez C (p, q)C(x) T mod p(y)
In other words, if we denote by M the matrix whose columns are the coefficients of q(y)h j (y) in the basis C(y), we get the identity

C(y)M C(x) T ≡ C(y)Bez C (p, q)C(x) T mod p(y)
Since C p is the matrix of the multiplication by y mod p(y) with respect to the canonical basis C(y), we have also the identity

M = q(C p )P CH
where the change of basis matrix P CH is in fact the following Hankel matrix P CH = H(a 0 , a 1 , . . . , a n-1 , 1, 0, . . . , 0) ∈ R n×n with the usual notation p(x) = x n + a n-1 x n-1 + . . . + a 0 . Hence, we get the Barnett Formula Bez C (p, q) = q(C p )P CH Finally, by Proposition 2.3, we derive the wanted relation :

Bez C (p, q) = P T CH Bez H (p, q)P CH = P T CH H n (q/p)P CH Which concludes the proof. ⊓ ⊔
To end the section, we show how Sturm and Sylvester algorithms can be considered as dual, in the case where all the roots of p(x) are real and simple, say x 1 < . . . < x n . Then, q(x) = p ′ (x)/n has also n -1 simple real roots y 1 < . . . < y n-1 which are interlacing those of p(x). Namely

x 1 < y 1 < x 2 < y 2 < . . . < y n-1 < x n

We may repeat the argument to see that this interlacing property of real roots remains for any two consecutive polynomials p k (x) and p k+1 (x) of the sequence SRemS(p, q). In particular, SRemS(p, q) does not have any degree breakdown, all the ǫ k are equal to +1, and N (q/p) is positive definite.

We have, by Proposition 2.4 q(C T p ) = H n (q/p)P CH Since H n (q/p) is positive definite, the Cholesky algorithm gives a decomposition

H n (q/p) = KK T
where K ∈ R n×n is lower triangular. So that we can write

p(x) = det(xId -K -1 C T p K)
We shall remark at this point that the matrix K -1 C T p K is tridiagonal and symmetric.

We get q(C T p ) = KAdL where L = AdK T P CH . Then, we observe that L is a lower triangular matrix (since P CH Ad is upper triangular) and KAdL commute with C T p . Thus, we have the identity :

LC T p L -1 = Ad(K -1 C T p K)Ad
We denote by Td this tridiagonal matrix. Let (p k (x)) be the signed remainders sequence associated to Td as given in Proposition 1.1 (i). The first row of KAdL is proportional to the last row of the matrix L which is proportional to p 1 (x). It remains to observe that the first row of KAdL = q(C T p ) gives exactly the coefficients of the polynomial q(x) in the canonical basis. Then, p 1 (x) = q(x).

In summary, we have shown that, if p(x) has n simple real roots and q(x) = p ′ (x)/n, then H n (q/p) is positive definite with Cholesky decomposition H n (q/p) = KK T , and if we denote by q(x) the monic polynomial whose coefficients are proportional to the last row of K -1 , then Td(p, q) = Td(p, q). Which settle the announced duality.

Generic case

We turn now to the generic situation. Let p(x) and q(x) be monic polynomials of respective degrees n and n -1 and such that SRemS(p, q) does not have any degree breakdown. This condition is equivalent to saying that all the principal minors of the Hankel matrix H n (q/p) do not vanish. We refer to [BPR] for this point. One way to see this is to figure out the connexion with the subresultants of p(x) and q(x).

A little bit more precisely, the j-th signed subresultant coefficient of p(x) and q(x) is denoted by sRes j (p, q) for j = 0 . . . n -1. If for all j, sRes j (p, q) = 0, we say that the sequence of subresultants is non-defective. Then, by [START_REF] Basu | Algorithms in Real Algberaic Geometry[END_REF]Corollary 8.33] and Proposition 1.1 (iv), we deduce that the non-defective condition is equivalent to the fact that SRemS(p, q) has no degree breakdown. Moreover, from [START_REF] Basu | Algorithms in Real Algberaic Geometry[END_REF]Lemma 9.26] we know that (∀j ∈ {1 . . . n}) (sRes n-j (p, q) = det(H j (q/p))) .

In conclusion, our no degree breakdown assumption means also that all the principal minors of the Hankel matrix H n (q/p) do not vanish.

At this point, we may add another equivalent condition, which will be essential for the following. Indeed, the condition that all the principal minors of the Hankel matrix H n (q/p) do not vanish is also equivalent to saying that the matrix H n (q/p) admits an invertible LU decomposition. Namely, it exists a lower triangular matrix L with 1 entries onto the diagonal, and an upper invertible triangular matrix U such that H n (q/p) = LU . Moreover this decomposition is unique and since H n (q/p) is symmetric we may write it as H n (q/p) = LDL T where D is diagonal. In fact, for our purpose, we will prefer the unique decomposition H n (q/p) = KJK T where K is lower triangular and J is a signature matrix.

Generalizing the previous section, we get :

Theorem 2.5 Let p(x) and q(x) be two monic polynomials of respective degrees n and n -1 such that SRemS(p, q) does not have any degree breakdown. Consider the symmetric LUdecomposition of the Hankel matrix H n (q/p) = KJK T , where J is a signature matrix and K a lower triangular matrix, and denote by q(x) the monic polynomials whose coefficients in the canonical basis are proportional to the last row of K -1 . Then, Td(p, q) = Td(p, q).

Proof : We start with the companion identity :

p(x) = det(xId -C T p )
Next, because of Proposition 2.2(i), we notice that the matrix H n (q/p) verifies the intertwinning relation :

H n (q/p)C p = C T p H n (q/p) Then, we write the symmetric LU -decomposition of H n (q/p) :

H n (q/p) = KJK T Which gives the identity p(x) = det(xId -K -1 C T p K).
We have, by Proposition 2.4

q(C T p ) = H n (q/p)P CH = KAdL where L = AdJK T P CH
We observe first that L is a lower triangular matrix (since P CH Ad is upper triangular), and second that KAdL commute with C T p . Thus, we have the identity :

LC T p L -1 = Ad(K -1 C T p K)Ad
Proposition 1.3 gives Td(p, q) = Ad(K -1 C T p K)Ad Moreover, the first row of KAdL is proportional to the last row of the matrix L. It remains to observe that the first row of KAdL = q(C T p ) gives exactly the coefficients of the polynomial q(x) in the canonical basis. Thus, by Proposition 1.3 we get

LC T p L -1 = Td(p, q) Which concludes the proof. ⊓ ⊔
Remark 2.6 Note that K -1 C T p KJ is symmetric and hence also the matrix LC T p L -1 J , where J = AdJAd.

Tridiagonal determinantal representations

Notations

We say that an univariate polynomial p

(x) ∈ R[x] of degree n such that p(0) = 0 has a determinantal representation if (DR) p(x) = α det(J -Ax)
where α ∈ R * , J is a signature matrix in R n×n , and A is a symmetric matrix in R n×n (we obviously have α = det(J)p(0)).

Likewise, we say that p(x) has a weak determinantal representation if

(WDR) p(x) = α det(S -Ax)
where α ∈ R * , S is symmetric invertible and A is symmetric.

Of course the existence of (DR) is obvious for univariate polynomials, but we will focus on the problem of effectivity. Namely, we want an algorithm (say of polynomial complexity with respect to the coefficients and the degree of p(x)) which produces the representation. Typically, we do want to avoid the use of the roots of p(x).

One result in that direction can be found in [START_REF] Quarez | Représentations déterminantales des polynômes univariés par les matrices flèches[END_REF] (which is inspired from [Fi]). It uses arrow matrices as a "model", whereas in the present article we make use of tridiagonal matrices.

When all the roots of p(x) are real, the effective existence of determinantal representation for univariate real polynomials exists even if we add the condition that J = Id. It has been discussed in several places, although not exactly with the determinantal representation formulation. Indeed, in place of looking for DR we may consider the equivalent problem of the research of a symmetric matrix whose characteristic polynomial is given. Indeed, if the size of the matrix A is equal to the degree n of the polynomial, the condition

p(x) = det(Id -xA) is equivalent to p * (x) = det(xId -A)
where p * (x) is the reciprocal polynomial of p(x). In [Fi], arrow matrices are used to answer this last problem. On the other hand, the Routh-Lanczos algorithm (which can be viewed as Proposition 1.1) gives also an answer, using tridiagonal model. Note that the problem may also be reformulated as a structured Jacobi inverse problem (confer [EP] for a survey).

In the following, we generalize the tridiagonal model to any polynomial p(x), possibly having non real roots. Doing that, general signature matrices J appear, whose entries depend on the number of real roots of p(x).

Over a general field

A lot of identities in Section 2 are still valid over a general field k. For instance, if p(x) and q(x) are monic polynomials of respective degrees n -1 and n, we may still associate the Hankel matrix H(q/p) = (s i+j ) 0≤i,j≤n-1 ∈ k n×n defined by the identity

q(x) p(x) = ∞ j=0 s j x j+1
Then, we have the following :

Theorem 3.1 Let p(x) ∈ k[x], q(x) ∈ k[x]
be two monic polynomials of respective degrees n and n -1, and set H = H(q/p). Then, the matrix C T p H is symmetric and we have the WDR :

det(H) × p(x) = det(xH -C T p H)
Moreover, if H admits the LU-decomposition H = KDK T where K ∈ k n×n is lower triangular with entries 1 onto the diagonal and D ∈ k n×n a diagonal matrix, then we have :

p(x) = det(xD -Td)
where Td = K -1 C T p KD is a tridiagonal symmetric matrix.

Proof : We exactly follow the proof of Theorem 2.5.

⊓ ⊔

Note that the condition for H to be invertible is equivalent to the fact that the polynomials p(x) and q(x) are coprime, since we have rk(Bez(q, p)) = deg (p) -deg (gcd(p, q)).

To see this, we may refer to the first assertion of [START_REF] Basu | Algorithms in Real Algberaic Geometry[END_REF]Theorem 9.4] whose proof is valid over any field.

The WDR of Theorem 3.1 has the advantage that the considered matrices have entries in the ring generated by the coefficients of the polynomial p(x). This point is not satisfied in the methods proposed in [START_REF] Quarez | Représentations déterminantales des polynômes univariés par les matrices flèches[END_REF] or in the Routh-Lanczos algorithm.

In fact, the use of Hankel matrices satisfying the intertwinning relation seems to be more convenient since we are able to "stop the algorithm at an earlier stage", namely before having to compute a square root of the matrix H (or of the matrix D).

Since gcd(p, p ′ ) = 1, we set r(x) to be the unique polynomial of degree < n such that r ≡ q p ′ mod p.

Then, p ′ r ≡ q mod p and from Proposition 3.2, we get :

PmV(ν) = TaQ(r, p) ≤ #{x ∈ R | p(x) = 0}
Let us introduce some notations at this step. First, let Td = Td(α, β, γ), next denote by ǫ(a) the sign in {-1, +1} of the non zero real number a, and finally let

J =      θ n-1 . . . θ 1 1     
.

Then, we can write p(x) = det xId n -P (Td × J)P -1

where

P =      (θ n-1 . . . θ 1 ) × (ǫ(γ n-1 ) . . . ǫ(γ 1 )) . . . θ 1 × ǫ(γ 1 ) 1      .
We note in fact that P (Td × J)P -1 = Td(p, q). Indeed, all the coefficients onto the first lower principal diagonal are positive. Moreover, all the coefficients onto the first upper principal diagonal are given by the sequence (θ n-1 × θ n-2 , . . . , θ 2 × θ 1 , θ 1 ).

We deduce from Proposition 1.1 (iv) that the sequence of signs of leading coefficients in the signed remainders sequence SRemS(p, q) is the following :

ν = (θ n-1 × . . . × θ 1 , . . . , θ 2 × θ 1 , θ 1 , 1, 1). Thus PmV(ν) = 1 + n-1 k=1 θ k = sgn(J)
and we are done.

⊓ ⊔

Another way, maybe less constructive, to prove the result is to use the duality of Theorem 2.5. Indeed, replacing as in the previous proof the matrix Td × J with P (Td × J)P -1 , we write the identity Td × J = LC T p L -1

Then, by duality, we have LC T p L -1 = AdK -1 C T p KJ ′ Ad where we have set the LU-decomposition

H n (q/p) = KJ ′ K T .
Let us introduce J′ = AdJ ′ Ad ; we get :

LC T p L -1 J × (J J′ ) = AdK -1 C p KJ ′ Ad
We remark that the matrices LC T p L -1 J and K -1 C p KJ ′ are both tridiagonal and symmetric with non-singular principal diagonals, so that we necessarily have

J J′ = ±Id.
Notice that by assumption the last coefficient of J is +1 and that the first coefficient of J ′ is always +1 (since it is the leading coefficient of q(x) p(x) ). Thus

J J′ = Id.
Then, we may conclude by Proposition 3.2. An alternative way to make use of this computation is to say that we get another proof of the equality PmV(ν) = sgn(Bez(p, q)) which appears in the sequence of identities sgn(Bez(p, q)) = sgn(H n (q/p)) = sgn(J ′ ) = sgn(J) = PmV(ν) = TaQ(r, p).

Remark 3.4 It is possible to extend Theorem 3.3 in the case where principal diagonals of Td = Td(α, β, β) are singular. Namely, for all k such that β k = 0, we have to assume that the corresponding k-th entry onto the diagonal of J is equal to +1. Then, we get that the number of real roots of p(x), counted with multiplicity, is greater than sgn(J).

To see this, it suffices to note that the polynomial defined by p(x) = det(J) det(xJ -Td) factorizes through

p(x) = det(J 1 ) det(xJ 1 -Td k ) × det(J 2 ) det(xJ 2 -Td n-k )
Moreover, the matrices Td k and Td n-k remain tridiagonal symmetric and J 1 , J 2 remain signature matrices. If we denote by the usual direct sum of matrices, we have J = J 1 J 2 and Td = Td k Td n-k . Thus, we may proceed by induction on the degree of p(x).

Before stating the converse property of Theorem 3.3, we establish a genericity lemma.

Lemma 3.5 Let p(x) be a monic polynomial of degree n with only single roots and q(x) = x n-1 + b 1 x n-1 + . . . + b n-1 . Then, the set of all (n -1)-tuples (b 1 , . . . , b n-1 ) ∈ R n-1 such that there is an integer k ∈ {1, . . . , n} satisfying det(H k (q/p)) = 0, is a proper subvariety of R n-1 .

Proof : We only have to show that for all k, det(H k (q/p)), viewed as a polynomial in the variables b 1 , . . . , b n-1 , is not the zero polynomial.

Let H n (q/p) = (s i+j ) 0≤i,j≤n-1 where

q(x) p(x) = ∞ j=0 s j x j+1
and denote by α 1 , . . . , α n the set of all (possibly complex) roots of p(x). Then,

s j = n i=1 q(α i ) p ′ (α i ) α j i
Let us introduce the real numbers defined as

u j = n i=1 α j i p ′ (α i )
We obviously have u j = 0 whenever j ≤ n -2 and also u n-1 = 1 (look at lim x→+∞ x j q(x) p(x) ). So that we deduce :

       s 0 = 1 s 1 = b 1 + u n and more generally (∀j ∈ {1, . . . , 2n -2}) (s j = b j + b j-1 u n + . . . + b 1 u n+j-2 + u n+j-1 )
Then, it becomes clear that H k+1 (q/p) ≡ 0 for any k such that k ≤ ⌊ n-1 2 ⌋ = r, since s 2k ∈ R[b 1 , . . . , b 2k ] has degree 1 in the variable b 2k and so is the case for H k+1 (q/p).

Next, for r < k ≤ n, we develop the determinant H k (q/p) successively according to the first columns, and we remark that its degree in the variable b n-1 is equal to 2k -n (with leading coefficient equal to -1). This concludes the proof.

⊓ ⊔

In other words, the Lemma says that the condition (∀k ∈ {1, . . . , n}) ( det(H k (q/p)) = 0) is generic with respect to the space of coefficients of the polynomial q(x). Because of the relations between coefficients and roots, the condition is also generic with respect to the (possibly complex) roots of the polynomial q(x).

Here is our converse statement about real roots counting :

Theorem 3.6 Let p(x) be a monic polynomial of degree n which has exactly s real roots counted with multiplicity. We can find effectively a generic family of symmetric tridiagonal matrices Td and signature matrices J with sgn(J) = s, and such that p(x) = det(J) × det(xJ -Td).

Proof :

If p(x) has multiple roots, then we may factorize it by gcd(p, p ′ ) and use the multiplicative property of the determinant to argue by induction on the degree. Now, we assume that p(x) has only simple roots.

We take for q(x) any monic polynomials of degree n -1 which has exactly s -1 real roots interlacing those of p(x). Namely, if we denote by x 1 < . . . < x s all the real roots of p(x) and by y 1 < . . . < y s-1 all the real roots of q(x), we ask that x 1 < y 1 < x 1 < y 2 < . . . < y s-1 < x s .

Let r(x) be the unique polynomial of degree < n such that r(x) ≡ q(x) p ′ (x) mod p(x) (since p ′ (x) is invertible modulo p(x)).

From p ′ r ≡ q mod p and p ′ (x i ) = q(x i ) for all real root x i of p(x), we get

TaQ(r, p) = s = #{x ∈ R | p(x) = 0}
At this point, we need that q(x) satisfies another hypothesis : that is SRemS(p, q) shall not have any degree breakdown, or equivalently that H(q/p) shall admit a LU -decomposition H n (q/p) = KJK T . According to Lemma 3.5, this hypothesis is generically satisfied, although it may not be always satisfied for the natural candidate q(x) = p ′ (x)/n.

Then, we get from Theorem 2.5

p(x) = det(xJ -K -1 C T p KJ)
where Td = K -1 C T p KJ is tridiagonal symmetric and J is a signature matrix.

By the proof of Proposition 3.3, we get moreover that sgn(J) = TaQ(r, p) = sgn(H n (q/p)).

This concludes the proof since TaQ(r, p) = s. ⊓ ⊔ Remark 3.7 (i) The choice of such polynomials q(x) with the interlacing roots property need to count and localize the real roots of p(x). It can be done via Sturm sequences for instance.

(ii) Although the polynomial q(x) = p ′ (x)/n has not necessarily the interlacing property in general, it is the case when all the roots of p(x) are real and simple. Moreover, in this case, the interlacing roots condition is equivalent to the no degree breakdown condition. Indeed, TaQ(p ′ q mod p, p) = n if and only if p ′ (x) and q(x) have same signs at each root of p(x).

Some worked examples

In order to get lighter formulas in our examples, we decide to get rid off denominators. That is why we replace signature matrices by only non-singular diagonal matrices. If one wants to deduce formulas with signature matrices, it suffices to normalize. 2) Consider the polynomial p(x) = x 5 -5x 3 + 4x, which in fact factorizes through p(x) =

x(x -1)(x + 1)(x -2)(x + 2). Let q(x) = p ′ (x)/5. We have In order to get some parametrized identities, let us introduce the following family of polynomials

N (q/p) =       5
q a (x) = (x -a) x + 3 2 x + 1 2 x - 1 2 .     1 -1
2 (a + 1)(2a -5)

15 16

(2a-1)(4a 2 -a-15) (a+1)(2a-5) 45 128 48a 4 -16a 3 -216a 2 +58a+105 (2a-1)(4a 2 -a-15) 315 8

(a+2)(a+1)a(a-1)(a-2) 48a 4 -16a 3 -216a

2 +58a+105       
The condition for H a (q/p) to be positive definite is equivalent to having only positive coefficients onto the diagonal of J a .

First, it yields J a (2, 2) > 0, which means that a ∈] -1, 5 2 [. Then, we add the condition J a (3, 3) > 0 which means that a ∈] 1 2 , 2, 06..[. Then, we add the condition J a (4, 4) > 0 which means that a ∈]0, 9.., 2, 00..[. And finally, we add the condition J a (5, 5) > 0, which means that a ∈]1, 2[ and gives exactly the interlacing property for the polynomial q a (x).

1)

  Let p(x) = x 3 + sx + t with s = 0, and q(x) = p ′ (x) = 3x 2 + s. Let us introduce the discriminant of p(x) as ∆ = -4s 3 -27t 2 . Consider the decomposition of the Hankel matrix well-known fact that p(x) has three distinct real roots if and only if s < 0 and ∆ > 0, which obviously reduces to the single condition ∆ > 0.Then, we have the determinantal representation ∆ × p(x) = det(xJ -

  = det(xId -Td).

  For instance, with a = 3 2 we get p(x) = det xId -

Acknowledgments.

I wish to thank Marie-Francoise Roy for helpful discussions on the subject.

Of course, at the time we want to derive a DR, then we have to add some conditions on the field k, for instance we shall work over an ordered field where square roots of positive elements exist.

To end the section, we may summarize that, for a given polynomial p(x), we have an obvious but non effective (i.e. using factorization) DR with entries in the splitting field of p(x) over k, to compare with an effective WDR given by Theorem 3.1 where entries are in the field generated by the coefficients of p(x).

Symmetric tridiagonal representation and real roots counting

If p(x) and r(x) are two real polynomials, we recall the number known as the Tarski Query :

We also recall the definition of the Permanences minus variations number of a given sequence of signs ν = (ν 1 , . . . , ν k ) :

We summarize, from [START_REF] Basu | Algorithms in Real Algberaic Geometry[END_REF]Theorem 4.32,Proposition 9.25,Corollary 9.8] some useful properties of these numbers, Proposition 3.2 Let p(x) and q(x) be two monic polynomials of respective degrees n and n -1, and such that the sequence SRemS(p, q) has no degree breakdown. Let r(x) be another polynomial such that q(x) is the remainder of p ′ (x)r(x) modulo p(x). Then,

where ν is the sequence of signs of the leading coefficients in the signed remainders sequence SRemS(p, q).

We come now to our main result about real roots counting : Theorem 3.3 Let Td ∈ R n×n be a tridiagonal symmetric matrix with non-singular first principal diagonals. Let also p(x) ∈ R[x] be a real polynomial with no multiple root and such that p(x) = det(J) det(xJ -Td),

where J is a signature matrix whose last entry onto the diagonal is +1.

Then, the number of real roots of p(x) is greater than sgn(J).

and we set q

The matrix Td × J is still tridiagonal with non-singular first principal diagonals. Then, we consider the sequence SRemS(p, q) and denote by ν the associated sequence of signs of leading coefficients.

We write the LU-decomposition


Mouhamad El

On three blocks paths

research documents, whether they are published or not. The documents may come

Introduction

Throughout this paper, all graphs are considered to be simple, that is, there are no loops and no multiple edges. By giving an orientation to each edge of a graph G, the obtained oriented graph is called a digraph. Reciprocally, the graph obtained from a digraph D by ignoring the directions of its arcs is called the underlying graph of D, and denoted by G(D). For a digraph D, we denote by D the digraph obtained from D by reversing the direction of its arcs. Let D be a digraph and let A, B ⊆ D, we denote by N + (B) the set of out-neighbors of the vertices of B outside B, N + A (B) the set N + (B) ∩ A, similarly we dene N -(B), N - A (B). We may use the same notation for N (B) and N A (B) in G(D). The chromatic number of a graph G, denoted by χ(G), is the minimum number of colors needed to color properly the vertices of G, that is no two adjacent vertices share the same color. The girth of a graph G, denoted by g(G), is the length of a shortest cycle in G. The chromatic number (resp. girth) of a digraph is the chromatic number (resp. girth) of its underlying graph. One of the known problems in graph theory is to nd an integer k such that any k-chromatic digraph contains each element of a specied family of digraphs. Erdös [START_REF] Erdös | Graph Theory and probability[END_REF] proved by probabilistic methods that for any positive integers k and l there exists a graph whose girth is at least l and whose chromatic number is greater than k. This gives the existence of digraphs with arbitrary high girth and high chromatic number. An immediate consequence of Erdös's theorem is that, if D is a family of digraphs in which one of its elements has an oriented cycle of a given length, we are not able to nd an integer k for which every k-chromatic digraph contains each element of D. This emphasizes many mathematicians to take into consideration two interesting categories of digraphs: the oriented trees (contain no cycles), and the oriented cycles whose length is not bounded from above.

From one side, Bondy [START_REF] Bondy | Disconnected orientations and a conjecture of Las Vergnas[END_REF] proved that every strong digraph D contains a circuit whose length is at least χ(D). A subdivision cycle with two blocks C(k, l) is an oriented cycle which consists of two internally vertex-disjoint directed paths of lengths at least k and l respectively, from a vertex to another one. Addario et al. [START_REF] Addario-Berry | Paths with two blocks in n-chromatic digraphs[END_REF] asked if the chromatic number of strong digraphs not containing subdivisions of a two-blocks cycle C(k, l) can be bounded from above by O(k + l), which remains an open problem. Assuming that t = max{k, l}, the best reached upper bound, found by Kim et al. [START_REF] Kim | Cycles with two blocks in kchromatic digraphs[END_REF], is 12t 2 .

From the other side, Burr [START_REF] Burr | Subtrees of directed graphs and hypergraphs[END_REF] proved that any (n -1) 2 -chromatic digraph contains any oriented tree of order n, and he conjectured that this bound can be improved to 2n -2. The best known bound for a general oriented tree, found by Addario-Berry et al. [START_REF] Addario-Berry | Oriented trees in digraphs[END_REF], is n 2 2 -n 2 +1. In contrast, considering some special oriented trees, better bounds on the chromatic number have been determined. The most celebrated one, known as Gallai-Hasse-Roy-Vitaver theorem [START_REF] Gallai | On directed paths and circuits[END_REF][START_REF] Hasse | Zur algeraischen Begündung der Graphentheorie. I[END_REF][START_REF] Roy | Nombre chromatique et plus longs chemins d'un graphe[END_REF][START_REF] Vitaver | Determination of minimal coloring of vertices of a graph by means of Boolean powers of the incidence matrix[END_REF], deals with directed paths and states that every nchromatic digraph contains a directed path of length n -1. Another wellstudied trees class is that of two-blocks paths. A block of a path P is a maximal directed sub-path of P . For k, l ∈ N * , we dened P (k, l) (resp.

P -(k, l)) be a path formed by k forward arcs (resp. k backward arcs) followed by l backward arcs (resp. l forward arcs). Addario et al. [START_REF] Addario-Berry | Paths with two blocks in n-chromatic digraphs[END_REF] proved that every n-path (A path of order n) with exactly two blocks is contained in every nchromatic digraph. Beyond paths with two blocks, no any linear bound is established. We denote by P (k, l, r) an oriented path formed by k forward arcs followed by l backward arcs followed by r forward arcs. As a rst step in this direction, Mortada et al. [START_REF] Mortada | Paths with three blocks in digraphs[END_REF] proved that any (2n -5)-chromatic digraph contains a path of type P (1, n -3, 1), n ≥ 4. Also, Mortada et al. [START_REF] Mortada | About paths with three blocks[END_REF] proved that any (n + 1)-chromatic digraph contains a path of type P (n -3, 1, 1). In this paper, we mainly establish a linear bound for paths with three blocks by proving that any 4.6n-chromatic digraph contains any n-path with three blocks.

Paths with three blocks

In this section, we are going to establish a linear bound for chromatic number of digraphs in order to contain any n-path with three blocks. For the sake of the proof, we are going to introduce some tools, presented as denitions and lemmas. An outbranching B is a digraph containing a vertex of indegree zero which is called the source of B, and the other vertices are of in-degree one. The level of a vertex v in an out-branching B, denoted by l B (v), is the order of the unique directed path starting from the source of B and ending at v. An out-forest F is a digraph in which each connected component is an out-branching. The level of a vertex v in an outforest F , denoted by l F (v), is its level in the out-branching containing it. For i

1, set L i (F ) = {v ∈ V (F ) : l F (v) = i}. Note that any digraph contains a spanning out-forest. A spanning out-forest F of a digraph D is said to be maximal if v∈V (D) l F (v)
is maximal. After introducing maximal forests, El Sahili and kouider [START_REF] Sahili | About paths with two blocks[END_REF] proved that if F is a maximal forest of a digraph D then L i (F ) is stable in D for all i 1, and consequently the number of levels in F should be at least χ(D) which gives a very simple proof of Gallai-Hasse-Roy-Vitaver Theorem. Below, we recall the result of Addario et al. about two-blocks paths we will need in our result: Based on this theorem we may extend the bound to 4n -4 to guarantee the existence of any n-path P (k, l, 1). This fact is convenient to complete the proof of our main result. Theorem 2.2. Every (4n-4)-chromatic digraph, n ≥ 4, contains any n-path of type P (k, l, 1).

Proof. For the case n = 4, the result holds directly due to [START_REF] Sahili | Functions and line digraphs[END_REF] which states that any 4-chromatic digraph contains a P (1, 1, 1). Moving on to the case n ≥ 5, let (S i ) 1≤i≤4n-2 be a sequence of stable sets covering D. Consider the two sub-digraphs of D, D 1 and D 2 , induced by (S 1 ∪ • • • ∪ S 2n-1 ) and

(S 2n ∪ • • • ∪ S 4n-2 ) respectively. Clearly, χ(D 1 ) = χ(D 2 ) = 2n -1. Set D 1 = D[N - D 1 (D 2 )] and D 2 = D[N - D 2 (D 1 )
]. Suppose that, D contains no P (k, l, 1), then D 1 and D 2 both contain no P (k, l) with k + l = n -2, and so we have by Theorem 2.1 that χ(D 1 ) ≤ n -2 and χ(D 2 ) ≤ n -2. Therefore, there is no arc between D 1 -D 1 and D 2 -D 2 , and so: ) and (S χ(D)

χ(D) ≤ χ(D 1 ) + χ(D 2 ) + χ((D 1 -D 1 ) ∪ (D 2 -D 2 )) ≤ 2(n -2) + max{χ(D 1 -D 1 ), χ(D 2 -D 2 )} ≤ 2(n -2) + 2n -1 = 4n -5, a contradiction.
2 +1 ∪• • •∪S χ(D) ) respectively. Let F be a maximal out-forest of D 1 . Set D 3 = D[ i≥k+1 L i (F )] and D = D-( k i=1 L i (F )). Therefore, χ(D i ) ≤ 1 2-2b χ(D ), i = 2, 3. Proof. Clearly χ(D 2 ), χ(D 3 ) ≤ χ(D) 2 and χ(D ) ≥ χ(D) -k. Since χ(D) ≥ k/b, then χ(D) -k ≥ (1 -b)χ(D). Therefore, χ(D 2 ) χ(D ) ≤ χ(D)/2 χ(D) -k ≤ χ(D)/2 (1 -b)χ(D) = 1 2 -2b . Hence, χ(D 2 ) ≤ 1 2-2b χ(D ), and similarly χ(D 3 ) ≤ 1 2-2b χ(D ). Lemma 2.2. Let D be a digraph and let 1/2 ≤ a < 1. Let (X 1 , X 2 ) be a parti- tion of V (D), with χ(D[X i ]) ≤ aχ(D) for i = 1, 2. Set D = D[N X 2 (X 1 )]. If D contains no vertex
which is the end of a path P (k, l) and a path P (k, l -1)

simultaneously with k + l = n -1, then χ(D) ≤ 2n-3 1-a .
Proof. Let H the subdigraph of D induced by the ends of a path P (k, l) contained in D . Clearly D -H contains no P (k, l) and so by Theorem 2.1,

χ(D -H) ≤ n -1. We have χ(H) ≤ n -2, since otherwise H contains a path P (k, l -1)
. Therefore, χ(D ) ≤ 2n -3. Note that there is no arc between X 1 and X 2 -V (D ), and so

χ(D) ≤ χ(D ) + χ(D[X 1 ] ∪ (D[X 2 ] -D )) ≤ 2n -3 + max{χ(D[X 1 ]), χ(D[X 2 ] -D )} ≤ 2n -3 + aχ(D).
Hence, χ(D) ≤ 2n-3 1-a . Proof. Note that D contains no P (k, l, r) if and only if D contains no P (r, l, k). For this reason, and since χ(D) = χ( D), we may suppose without loss of generality that k ≤ n-2 2 . Then, χ(D) ≥ n-1 2b > k b , and so by Theorem 2.3, we have χ , 1 2 .

(D) ≤ 2-2b 1-2b (2m-3)+k where m = l +r +1. Note that k = n-m, then χ(D) ≤ 2-2b 1-2b (2m -3) + k = 4-4b 1-2b m -6-6b 1-2b + n -m ≤ ( 4-4b 1-2b -1)n -6-6b 1-2b + n = 4-4b 1-2b (n -3 2 ) < 4-
Theorem 2.5. Every digraph with chromatic number at least

Theorem 2 . 1 .

 21 Every n-chromatic digraph, n ≥ 4, contains any path with two blocks of length n -1.

Lemma 2 . 1 .

 21 Let D be a digraph with an even chromatic number such that χ(D) ≥ k/b where k ∈ N * and b ∈]0, 1 2 [. Let (S i ) 1≤i≤χ(D) be a sequence of stable sets covering D. Consider the two sub-digraphs of D, D 1 and D 2 , induced by (S 1 ∪• • •∪S χ(D) 2

Theorem 2 . 3 . 2 )

 232 Let b ∈]0, 1 2 [, and let k, l, r ∈ N * . Set m = l + r + 1. Let D be a digraph with an even chromatic number such that χ(D) ≥ k/b. Suppose that D contains no P (k, l, r), then χ(D) ≤ 2-2b 1-2b (2m -3) + k.Proof. Let (S i ) 1≤i≤χ(D) be a sequence of stable sets covering D. Consider the two sub-digraphs of D, D 1 and D 2 , induced by(S 1 ∪ • • • ∪ S χ(D) and (Sχ(D) 2 +1 ∪ • • • ∪ S χ(D) ) respectively. Let F be a maximal forest of D 1 . Set D 3 = D[ i≥k+1 L i (F )] and D = D -( k i=1 L i (F )). Then by Lemma 2.1, we have χ(D i ) ≤ 1 2-2b χ(D ) for i = 2, 3. Set H = D[N V (D 2 ) (V (D 3 ))]. Since Dcontains no P (k, l, r) and every vertex in D 3 is an end of directed path of length at least k in F , then H contains no vertex which is the end of a path P -(r, l) and a path P -(r, l -1) simultaneously. Therefore, by Lemma 2.2, we have χ(D ) ≤ 2m-3 1-a with a = 1 2-2b , and so χ(D ) ≤ 2-2b 1-2b (2m -3). In conclusion, χ(D) ≤2-2b 1-2b (2m -3) + k. Theorem 2.4. Let b ∈ 0, 1 2 , and let k, l, r ∈ N * . Set n = k + l + r + 1. Let D be a digraph with an even chromatic number χ(D) ≥ n-1 2b . If D contains no P (k, l, r), then b ∈ 5-

4b 1 -

 1 2b (n -1). And so, , and so 8b 2 -10b + 1 < 0. Hence b ∈

8 . 1 2b 2 ,

 812 tains any path with three blocks of length n -1.Proof. Set b = 5- √ 17 If χ(D) is even, then we have χ(D) ≥ n 2b ≥ n-then by Theorem 2.4, D contains any path P (k, l, r) with k + l + r = n -1. If χ(D) is odd, then D contains a subdigraph D with χ(D ) = χ(D) -1. Note that χ(D ) is even. Moreover, χ(D ) ≥ n 2b -1 = n-2b 2b ≥ n-1 2b. By applying Theorem 2.4, and since D ⊆ D, we may deduce that D contains any path P (k, l, r) with k + l + r = n -1. 561..., which guaranties our result.

Acknowledgements I would like to thank Professor Amine El Sahili and Doctor Maydoun Mortada for what they have provided Helpful comments.