Rafic Nader
email: naderafic12@gmail.com

Bassam Mourad
email: bmourad@ul.edu.lb

Alain Bretto
email: alain.bretto@unicaen.fr

Hassan Abbas
email: habbas@ul.edu

A note on the real inverse spectral problem for doubly stochastic matrices

Keywords: Symmetric doubly stochastic matrices, Inverse eigenvalue problem, Normalized Suleimanova spectrum 2000 MSC: 15A12, 15A18, 15A51

The real (resp. symmetric) doubly stochastic inverse spectral problem is the problem of determining necessary and sufficient conditions for a real n-tuple λ = (1, λ 2 , ..., λ n ) to be the spectrum of an n × n (resp. symmetric) doubly stochastic matrix. If λ i ≤ 0 for all i = 2, ..., n and the sum of all the entries in λ is nonnegative, then we refer to such λ as a normalized Suleimanova spectrum.

The purpose of this paper is to first fix an error in Theorem 9 of the recent paper [ I. Adeli, M. Taheria, M.M Moghadama, A recursive method for constructing doubly stochastic matrices and inverse eigenvalue problem, Linear Algebra Appl. 537 (2018) 318-331], after giving a counterexample. Secondly, we give a negative answer to a question posed in [C.R. Johnson, P. Paparella, Perron spectratopes and the real nonnegative inverse eigenvalue problem, Linear Algebra Appl. 493 (2016) 281-300] concerning the realizability of normalized Suleimanova spectra for the case when n is odd. Some sufficient conditions for a positive answer to this question are given.

Introduction

An n × n matrix A with real entries is said to be nonnegative if all of its entries are nonnegative. A nonnegative matrix A is said to be doubly stochastic if each of its row and column sum is equal to 1. Let I n and J n be the n × n identity matrix and the n × n matrix whose all entries are 1 n respectively. In addition, if e n = 1 √ n (1, ..., 1) T then clearly an n × n nonnegative matrix A is doubly stochastic if and only if Ae n = e n and A T e n = e n or equivalently AJ n = J n A = J n .

The real (resp. symmetric) doubly stochastic inverse eigenvalue problem RDIEP (resp. SDIEP) is the problem of determining necessary and sufficient conditions for a real n-tuple σ = {1, λ 2 , ..., λ n } to be the spectrum of an n × n (resp. symmetric) doubly stochastic matrix. If there exists a doubly stochastic matrix A whose spectrum is σ, then we shall say that σ is realizable and A realizes σ.

So far, the SDIEP has only been solved for the case n = 3 by Perfect and Mirsky [START_REF] Perfect | Spectral properties of doubly-stochastic matrices[END_REF] and remains open for the cases n ≥ 4 (see [START_REF] Lei | On the symmetric doubly stochastic inverse eigenvalue problem[END_REF][START_REF] Mourad | An inverse problem for symmetric doubly stochastic matrices[END_REF][START_REF] Mourad | A note on the boundary of the set where the decreasingly ordered spectra of symmetric doubly stochastic matrices lie[END_REF][START_REF] Mourad | On a spectral property of doubly stochastic matrices and its application to their inverse eigenvalue[END_REF][START_REF] Mourad | An algorithm for constructing doubly stochastic matrices for the inverse eigenvalue problem[END_REF][START_REF] Perfect | Spectral properties of doubly-stochastic matrices[END_REF][START_REF] Soules | Constructing symmetric nonnegative matrices[END_REF] for a collection of most sufficient conditions for the SDIEP). Until now, there are two principal methods to solve the SDIEP. The first one relies on taking a diagonal matrix Λ = diag(1, λ 2 , ..., λ n ) and a nonsingular matrix P , and then exploring the conditions under which A = P -1 ΛP is doubly stochastic. The second method falls into the category of constructing new doubly stochastic matrices from smaller size matrices with known spectra. Our paper here falls under the second category.

We call σ = {1, λ 2 , ..., λ n } ⊂ R a normalized Suleimanova spectrum if 1 + λ 2 + ... + λ n ≥ 0 and 0 ≥ λ i ≥ -1 for all i = 2, ..., n. In [START_REF] Johnson | Perron spectratopes and the real nonnegative inverse eigenvalue problem[END_REF], the following question was posed. Question 1. If σ is a normalized Suleimanova spectrum, is σ realizable by a doubly stochastic matrix?

The authors in [START_REF] Johnson | Perron spectratopes and the real nonnegative inverse eigenvalue problem[END_REF] proved that the answer is yes for all Hadamard orders (i.e. n = 2 k ) and in this case the realizing matrix is symmetric. We will denote by NS-SDIEP to be the problem which asks what sets of normalized Suleimanova spectrum occur as the spectrum of a symmetric doubly stochastic matrix.

This paper is organised as follows. In Section 2, we collect some preliminary results that will be used later. In section 3, we give a counterexample to Theorem 9 in [START_REF] Adeli | A recursive method for constructing doubly stochastic matrices and inverse eigenvalue problem[END_REF] in the case where n is odd and we present an alternative statement though in this case it will not be an improvement of the results in [START_REF] Soules | Constructing symmetric nonnegative matrices[END_REF] (as was claimed in [START_REF] Adeli | A recursive method for constructing doubly stochastic matrices and inverse eigenvalue problem[END_REF]) but rather a new independent sufficient condition for the SDIEP. In Section 4, we give a negative answer to Question 1 in the case where n is odd and we present some sufficient conditions for the realizability of normalized Suleimanova spectrum.

Auxiliary materials

We present in this section auxiliary results concerning spectral properties of certain block doubly stochastic matrices. We start with the following theorem from [START_REF] Mourad | On a spectral property of doubly stochastic matrices and its application to their inverse eigenvalue[END_REF][START_REF] Mourad | Generalization of some results concerning eigenvalues of a certain class of matrices and some applications[END_REF]. Theorem 1. Let A be an n × n doubly stochastic matrix whose eigenvalues are given by 1, λ 2 , ..., λ n and let B be an m × m doubly stochastic matrix with eigenvalues 1, µ 2 , ..., µ m . Then for any ρ ≥ 0 and for any r ≥ 0 such that ρ and r do not vanish simultaneously, the (m + n) × (m + n) matrix C defined by Remark 1. It is worthy to mention here that the preceding theorem is a specialisation of a result in [START_REF] Mourad | Generalization of some results concerning eigenvalues of a certain class of matrices and some applications[END_REF] that deals with k diagonal blocks instead of only two. Its proof relies on a result which is presented in Perfect [START_REF] Perfect | Methods for constructing certain stochastic matrices II[END_REF] and is due to R. Rado. An alternative 1 proof can be achieved from Fiedler [START_REF] Fiedler | Eigenvalues of non-negative symmetric matrices[END_REF]. Indeed, the proof of Lemma 2.2 there, is essentially the same as the proof of Theorem 1. One simply replaces the symmetry assumption in Fiedler's paper by the property that the algebraic and geometric multiplicities of the eigenvalue 1 of any doubly stochastic matrix are the same.

• For m ≥ n, C = 1 r + ρm
As a conclusion, we have the following two lemmas that are Theorem 1 and Theorem 2 in [START_REF] Adeli | A recursive method for constructing doubly stochastic matrices and inverse eigenvalue problem[END_REF] and which constitute the basis for their results. Lemma 1. Let A be an n × n doubly stochastic matrix with eigenvalues 1, λ 2 , ..., λ n . Then, for any 0 ≤ r ≤ 1, there exists an (n + 1) × (n + 1) doubly stochastic matrix C with eigenvalues given by 1, 1 -n+1 n r, n-r n λ 2 , ..., n-r n λ n .

Proof: It suffices to check that the matrix

C = 1 -r r √ n e T n r √ n e n ( n-r n )A
is doubly stochastic with eigenvalues 1, 1 -n+1 n r, n-r n λ 2 , ..., n-r n λ n . Lemma 2. Let A be an n×n doubly stochastic matrix with eigenvalues 1, λ 2 , ..., λ n . In addition, let B be an m×m doubly stochastic matrix with eigenvalues 1, µ 2 , ..., µ m . Then for any 0 ≤ r ≤ 1 and n ≥ m, there exists an (n+m)×(n+m) doubly stochastic matrix C with eigenvalues given by 1, α+r-1, αλ 2 , ..., αλ n , rµ 2 , ..., rµ m where 1-α m = 1-r n .

Proof: It suffices to check that the matrix C = αA

(1-r) √ m √ n e n e T m (1-r) √ m √ n
e m e T n rB is doubly stochastic with eigenvalues 1, α + r -1, αλ 2 , ..., αλ n , rµ 2 , ..., rµ m .

For our purposes, the following result due to Soules [START_REF] Soules | Constructing symmetric nonnegative matrices[END_REF], is also needed.

Theorem 2. [13] If 1 ≥ λ 2 ≥ ... ≥ λ n ≥ -1 and
1 n + n -m -1 n(m + 1) λ 2 + m k=1 λ n-2k+2 (k + 1)k ≥ 0, (1)
holds with n = 2m + 2 if n even and n = 2m + 1 if n odd, then there exists an n × n symmetric doubly stochastic matrix D such that D has eigenvalues 1, λ 2 , ...., λ n .

Remark 2. The proof of the preceding theorem is done by constructing an n × n matrix whose off-diagonal entries are all nonnegative and its smallest diagonal entry is given by the left-hand side of (1). So if ( 1) is valid then we obtain the symmetric doubly stochastic matrix D mentioned in the preceding theorem and so its trace is nonnegative.

Consequently, if 1 ≥ λ 2 ≥ ... ≥ λ n ≥ -1 and (1) is true, then 1 + λ 2 + ... + λ n ≥ 0.
Finally, we have the following simple observation which is very useful for us and will be used later.

Lemma 3. Let n > 1 be a positive integer. Then, the following statements hold.

i)

1 n + 1 n(n-1) + ... + 1 3×2 + 1 2×1 = 1.
ii) Let p be any positive integer which is greater than 1. If n > 2 p , then

1 n + 1 n(n -1) + ... + 1 2 p (2 p + 1) + 2 p -1 2 p = 1.
iii) For any positive integer m ≥ 1, it holds that

m k=1 1 (k+1)k = 1 -1 m+1 = m m+1 . Consequently, for any positive integer m ≥ 2, we have m k=2 1 (k+1)k = m m+1 -1 2 .
iv) For any positive even integer m ≥ 2, it holds that

m-1 k= m 2 1 (k+1)k = 1 m . Hence, for any positive even integer m ≥ 4, we have m-2 k= m 2 1 (k+1)k = 1 m - 1 m(m-1)
.

Proof:

i) The left hand side in Part i) can be rewritten as

1 n + n-1 k=1 1 k(k + 1) = 1 n + n-1 k=1 1 k - 1 k + 1 = 1 n + 1 n -1 - 1 n + ... + 1 2 - 1 3 + 1 - 1 2 = 1.
ii) From Part i), we can write

1 2 p (2 p -1) + 1 (2 p -1)(2 p -2) ... + 1 3 × 2 + 1 2 × 1 = 1 - 1 2 p = 2 p -1 2 p .
It follows that

1 n + 1 n(n -1) +...+ 1 2 p (2 p + 1) + 2 p -1 2 p = 1 n + 1 n(n -1) +...+ 1 2 p (2 p + 1) + 1 2 p (2 p -1) +...+ 1 2 × 1 = 1.
iii) It follows easily from the first part.

iv) For m = 2, the assertion is true. Suppose m > 2, then from Part i), we certainly know that

m-1 k=1 1 (k+1)k = 1 -1 m = m-1 m . Therefore, m 2 -1 k=1 1 (k+1)k + m-1 k= m 2 1 (k+1)k = m-1 m
, and thus we obtain

m-1 k= m 2 1 (k + 1)k = m -1 m - m 2 -1 k=1 1 (k + 1)k = m -1 m -1 - 1 m 2 = 1 m .

Main observations

In a recent paper [START_REF] Adeli | A recursive method for constructing doubly stochastic matrices and inverse eigenvalue problem[END_REF], the authors used Lemma 1 and Lemma 2 to obtain a recursive method for constructing doubly stochastic matrices for the inverse eigenvalue problem by distinguishing between the cases n even and n odd. In addition, it is claimed that these new sufficient conditions improve Soules condition (1) in both cases.

Theorem 3. [1] Let n ≥ 5. If 1 ≥ λ 2 ≥ .... ≥ λ n ≥ -1 and 1 n + 1 n λ 2 + n 2 -[ n+2 4 ] n 2 [ n+2 4 ] λ 4 + [ n+2 4 ]-1 k=1 λ n-4k+4 (k + 1)k ≥ 0, (2)
for n even ([.] stands for the integer part) and

1 n + n -1 n(n + 1) λ 2 + n+1 2 -[ n+3 4 ] n+1 2 [ n+3 4 ] λ 3 + [ n+3 4 ]-1 k=1 λ n-4k+4 (k + 1)k ≥ 0, (3)
for n odd, holds. Then there exists an n × n symmetric doubly stochastic matrix C whose eigenvalues are 1, λ 2 , λ 3 , ..., λ n .

Next we give a counterexample to the preceding theorem in the case when n is odd. Consider the following list of real numbers σ

= (1, 1, 1, -2 3 , -2 3 , -2 3 , -1).
It is easy to see that σ satisfies (3). Hence, by Theorem 3, there exists a 7 × 7 symmetric doubly stochastic matrix A with spectrum σ. On the other hand, σ cannot be the spectrum of any 7 × 7 nonnegative matrix since otherwise by the Perron-Frobenius theorem (see [START_REF] Minc | Non-Negative Matrices[END_REF]), there would exist a reducible nonnegative matrix with spectrum σ. However, there is no way of splitting σ into 3 subsets where each subset has a nonnegative sum. That leads to a contradiction.

More explicitly, the authors in [START_REF] Adeli | A recursive method for constructing doubly stochastic matrices and inverse eigenvalue problem[END_REF] claimed (without justification) that when n is odd, and (3) is verified, then we have

1 n+1 2 + n+1 2 -[ n+3 4 ] n+1 2 [ n+3 4 ] 1 α λ 3 + [ n+3 4 ]-1 k=1 1 α λ n-4k+4 (k + 1)k ≥ 0, (4)
and

1 n-1 2 + n-1 2 -[ n+1 4 ] n-1 2 [ n+1 4 ] 1 r λ 4 + [ n+1 4 ]-1 k=1 1 r λ n-4k+3 (k + 1)k ≥ 0, (5)
where α = (n-1)λ2+(n+1) 2n and r = (n+1)λ2+(n-1)

2n

. In fact, if (3) is valid then it holds that

0 ≤ 1 n + n -1 n(n + 1) λ 2 + n+1 2 -[ n+3 4 ] n+1 2 [ n+3 4 ] λ 3 + [ n+3 4 ]-1 k=1 λ n-4k+4 (k + 1)k = (n -1)λ 2 + (n + 1) 2n   1 n+1 2 + n+1 2 -[ n+3 4 ] n+1 2 [ n+3 4 ] 1 α λ 3 + [ n+3 4 ]-1 k=1 1 α λ n-4k+4 (k + 1)k   = α   1 n+1 2 + n+1 2 -[ n+3 4 ] n+1 2 [ n+3 4 ] 1 α λ 3 + [ n+3 4 ]-1 k=1 1 α λ n-4k+4 (k + 1)k   .
As α is positive, then this shows that if (3) is valid then inequality (4) is always true. However, inequality (5) may not necessarily be true when (3) is valid, as can be easily checked for the list σ = (1, 1, 1, -2 3 , -2 3 , -2 3 , -1) that satisfies (3) and does not verify [START_REF] Minc | Non-Negative Matrices[END_REF]. Next, we shall present an alternative sufficient condition for the odd case by using the same recursive method for constructing doubly stochastic matrices. However, this will not be an improvement of Soules condition, but rather an independent condition as we shall prove. Before doing so, we need the following auxiliary lemma. Lemma 4. Let n ≥ 5 be odd and let 1 ≥ λ 2 ≥ .... ≥ λ n ≥ -1. Then

1 n + n -1 n(n + 1) λ 2 + n+1 2 -[ n+3 4 ] n+1 2 [ n+3 4 ] λ 4 + [ n+3 4 ]-1 k=1 λ n-4k+4 (k + 1)k ≤ 1 n + n -1 n(n + 1) λ 2 + 4 (n -1)(n + 1) λ 2 + n-1 2 -[ n+1 4 ] n-1 2 [ n+1 4 ] λ 4 + [ n+1 4 ]-1 k=1 λ n-4k+3 (k + 1)k .
Proof: We distinguish between the cases n = 4m + 1 and n = 4m + 3 (since n here takes only odd values).

For n = 4m + 1, we have

1 n + n -1 n(n + 1) λ 2 + m (2m + 1)(m + 1) λ 4 + m k=1 λ n-4k+4 (k + 1)k ≤ 1 n + n -1 n(n + 1) λ 2 + m (2m + 1)(m + 1) λ 4 + m k=1 λ n-4k+3 (k + 1)k (since λ n-4k+4 ≤ λ n-4k+3 ) = 1 n + n -1 n(n + 1) λ 2 + m (2m + 1)(m + 1) λ 4 + 1 m(m + 1) λ 4 + m-1 k=1 λ n-4k+3 (k + 1)k = 1 n + n -1 n(n + 1) λ 2 + m + 1 m(2m + 1) λ 4 + m-1 k=1 λ n-4k+3 (k + 1)k = 1 n + n -1 n(n + 1) λ 2 + 1 2m(2m + 1) + 1 2m λ 4 + m-1 k=1 λ n-4k+3 (k + 1)k ≤ 1 n + n -1 n(n + 1) λ 2 + 1 2m(2m + 1) λ 2 + 1 2m λ 4 + m-1 k=1 λ n-4k+3 (k + 1)k (since λ 4 ≤ λ 2 ) = 1 n + n -1 n(n + 1) λ 2 + 4 (n -1)(n + 1) λ 2 + n-1 2 -[ n+1 4 ] n-1 2 [ n+1 4 ] λ 4 + [ n+1 4 ]-1 k=1 λ n-4k+3 (k + 1)k .
For n = 4m + 3, we have

1 n + n -1 n(n + 1) λ 2 + 1 2m + 2 λ 4 + m k=1 λ n-4k+4 (k + 1)k = 1 n + n -1 n(n + 1) λ 2 + 1 (2m + 2)(2m + 1) + m (m + 1)(2m + 1) λ 4 + m k=1 λ n-4k+4 (k + 1)k ≤ 1 n + n -1 n(n + 1) λ 2 + 1 (2m + 2)(2m + 1) λ 2 + m (m + 1)(2m + 1) λ 4 + m k=1 λ n-4k+3 (k + 1)k = 1 n + n -1 n(n + 1) λ 2 + 4 (n -1)(n + 1) λ 2 + n-1 2 -[ n+1 4 ] n-1 2 [ n+1 4 ] λ 4 + [ n+1 4 ]-1 k=1 λ n-4k+3 (k + 1)k .
Thus the proof is complete.

Theorem 4. Let n ≥ 5 be odd and let

1 ≥ λ 2 ≥ .... ≥ λ n ≥ -1. If 1 n + n -1 n(n + 1) λ 2 + n+1 2 -[ n+3 4 ] n+1 2 [ n+3 4 ] λ 4 + [ n+3 4 ]-1 k=1 λ n-4k+4 (k + 1)k ≥ 0, (6)
then there exists an n × n symmetric doubly stochastic matrix C with eigenvalues 1, λ 2 , λ 3 , ..., λ n .

Proof: As n is odd, then by [START_REF] Mourad | An inverse problem for symmetric doubly stochastic matrices[END_REF], we know that 0 ≤

1 n + n -1 n(n + 1) λ 2 + n+1 2 -[ n+3 4 ] n+1 2 [ n+3 4 ] λ 4 + [ n+3 4 ]-1 k=1 λ n-4k+4 (k + 1)k ≤ 1 n + n -1 n(n + 1) λ 2 + n+1 2 -[ n+3 4 ] n+1 2 [ n+3 4 ] λ 3 + [ n+3 4 ]-1 k=1 λ n-4k+4 (k + 1)k (since λ 4 ≤ λ 3 and its coefficient is > 0) = (n -1)λ 2 + (n + 1) 2n 1 n+1 2 + n+1 2 -[ n+3 4 ] n+1 2 [ n+3 4 ] λ 3 + [ n+3 4 ]-1 k=1 λ n-4k+4 (k + 1)k = α   1 n+1 2 + n+1 2 -[ n+3 4 ] n+1 2 [ n+3 4 ] 1 α λ 3 + [ n+3 4 ]-1 k=1 1 α λ n-4k+4 (k + 1)k   ,
where α = (n-1)λ2+(n+1) 2n > 0. In order to apply Theorem 2, we first show by contradiction that λn α ≥ -1 and λ3 α ≤ 1 (since the λ i are in the decreasing order). Suppose that λn α < -1, that is, 2nλ n +(n-1)λ 2 +(n+1) < 0. It then follows that, 1 n + n-1 n(n+1) λ 2 + 2 n+1 λ n < 0, and hence (6) implies that

1 n + n -1 n(n + 1) λ 2 + n+1 2 -[ n+3 4 ] n+1 2 [ n+3 4 ] λ 4 + [ n+3 4 ]-1 k=1 λ n-4k+4 (k + 1)k ≥ 0 > 1 n + n -1 n(n + 1) λ 2 + 2 n + 1 λ n , that is, n+1 2 -[ n+3 4 ] n+1 2 [ n+3 4 ] λ 4 + [ n+3 4 ]-1 k=2 λ n-4k+4 (k + 1)k + 1 2 λ n - 2 n + 1 λ n > 0. Since 1 ≥ λ 2 ≥ ... ≥ λ n ≥ -1, then we can write 0 < n+1 2 -[ n+3 4 ] n+1 2 [ n+3 4 ] λ 2 + [ n+3 4 ]-1 k=2 λ 2 (k + 1)k + 1 2 λ n - 2 n + 1 λ n =   n+1 2 -[ n+3 4 ] n+1 2 [ n+3 4 ] + [ n+3 4 ]-1 k=2 1 (k + 1)k   λ 2 + 1 2 - 2 n + 1 λ n = n+1 2 -[ n+3 4 ] n+1 2 [ n+3 4 ] + [ n+3 4 ] -1 [ n+3 4 ] - 1 2 λ 2 + 1 2 - 2 n + 1 λ n (using Lemma 3, Part iii) with m = [ n+3 4 ] -1) = n -3 2(n + 1) (λ 2 + λ n ).
So λ 2 +λ n > 0, and this implies that 0

> 2nλ n +(n-1)λ 2 +(n+1) = n(λ 2 +λ n )+n(1+λ n )+1-λ 2 > 0, and we get a contradiction. Therefore, λn α ≥ -1. Suppose now that λ3 α > 1, that is, 2nλ 3 -(n-1)λ 2 -(n+1) > 0. But this implies that 2nλ 3 -(n -1)λ 2 -(n + 1) = (n -1)(λ 3 -λ 2 ) + (n + 1)(λ 3 -1)
> 0, and we also get a contradiction. Therefore, λ3 α ≤ 1 and hence by Soules condition (1), there exists an ( n+1 2 ) × ( n+1 2 ) symmetric doubly stochastic matrix A with eigenvalues 1, 1 α λ 3 , 1 α λ 5 , ..., 1 α λ n . On the other hand, by [START_REF] Mourad | An inverse problem for symmetric doubly stochastic matrices[END_REF] and Lemma 4, we have

0 ≤ 1 n + n -1 n(n + 1) λ 2 + n+1 2 -[ n+3 4 ] n+1 2 [ n+3 4 ] λ 4 + [ n+3 4 ]-1 k=1 λ n-4k+4 (k + 1)k ≤ 1 n + n -1 n(n + 1) λ 2 + 4 (n -1)(n + 1) λ 2 + n-1 2 -[ n+1 4 ] n-1 2 [ n+1 4 ] λ 4 + [ n+1 4 ]-1 k=1 λ n-4k+3 (k + 1)k = (n + 1)λ 2 + (n -1) 2n 1 n-1 2 + n-1 2 -[ n+1 4 ] n-1 2 [ n+1 4 ] λ 4 + [ n+1 4 ]-1 k=1 λ n-4k+3 (k + 1)k = r   1 n-1 2 + n-1 2 -[ n+1 4 ] n-1 2 [ n+1 4 ] 1 r λ 4 + [ n+1 4 ]-1 k=1 1 r λ n-4k+3 (k + 1)k   ,
where r = (n+1)λ2+(n-1)

2n

. Next, we prove that r is positive. Indeed, by ( 6), we know that

0 ≤ 1 n + n -1 n(n + 1) λ 2 + n+1 2 -[ n+3 4 ] n+1 2 [ n+3 4 ] λ 4 + [ n+3 4 ]-1 k=1 λ n-4k+4 (k + 1)k ≤ 1 n + n -1 n(n + 1) λ 2 + n+1 2 -[ n+3 4 ] n+1 2 [ n+3 4 ] λ 2 + [ n+3 4 ]-1 k=1 λ 2 (k + 1)k (since λ 2 ≥ λ 4 ≥ ..., and their coefficients are > 0) = 1 n +   n -1 n(n + 1) + n+1 2 -[ n+3 4 ] n+1 2 [ n+3 4 ] + [ n+3 4 ]-1 k=1 1 (k + 1)k   λ 2 = 1 n + n -1 n(n + 1) + n+1 2 -[ n+3 4 ] n+1 2 [ n+3 4 ] + 1 - 1 [ n+3 4 ] λ 2 = 1 n + n -1 n λ 2 .
So obviously λ 2 = -1, and it follows that (n + 1)

λ 2 + (n -1) = 1 + (n -1)λ 2 + (n -2) + 2λ 2 > 0 for n > 4.
This implies that r > 0. Also, as (n + 1)λ 2 + (n -1) ≤ n + 1 + n -1 = 2n, then r ≤ 1. Next, in order to again apply Theorem 2, we shall show that λn r ≥ -1 and λ3 r ≤ 1 by contradiction. Suppose that λn r < -1, that is,

2nλ n + (n + 1)λ 2 + (n -1) < 0. It follows that, 1 n + n+1 n(n-1) λ 2 + 2 n-1 λ n < 0. From (6), we get 1 n + n -1 n(n + 1) λ 2 + n+1 2 -[ n+3 4 ] n+1 2 [ n+3 4 ] λ 4 + [ n+3 4 ]-1 k=1 λ n-4k+4 (k + 1)k ≥ 0 > 1 n + n + 1 n(n -1) λ 2 + 2 n -1 λ n , that is, n -1 n(n + 1) - n + 1 n(n -1) λ 2 + n+1 2 -[ n+3 4 ] n+1 2 [ n+3 4 ] λ 4 + [ n+3 4 ]-1 k=2 λ n-4k+4 (k + 1)k + 1 2 λ n - 2 n -1 λ n > 0. Since 1 ≥ λ 2 ≥ ... ≥ λ n ≥ -1, then we can write 0 < n -1 n(n + 1) - n + 1 n(n -1) λ 2 + n+1 2 -[ n+3 4 ] n+1 2 [ n+3 4 ] λ 2 + [ n+3 4 ]-1 k=2 λ 2 (k + 1)k + 1 2 λ n - 2 n -1 λ n =   n -1 n(n + 1) - n + 1 n(n -1) + n+1 2 -[ n+3 4 ] n+1 2 [ n+3 4 ] + [ n+3 4 ]-1 k=2 1 (k + 1)k   λ 2 + 1 2 - 2 n -1 λ n = n -1 n(n + 1) - n + 1 n(n -1) + n+1 2 -[ n+3 4 ] n+1 2 [ n+3 4 ] + [ n+3 4 ] -1 [ n+3 4 ] - 1 2 λ 2 + 1 2 - 2 n -1 λ n (by Lemma 3, Part iii)) = n -1 n(n + 1) - n + 1 n(n -1) + 1 [ n+3 4 ] - 1 n+1 2 + 1 - 1 [ n+3 4 ] - 1 2 λ 2 + 1 2 - 2 n -1 λ n = n -5 2(n -1) (λ 2 + λ n ).
Hence λ 2 + λ n > 0, and it then follows that 0

> 2nλ n + (n + 1)λ 2 + (n -1) = n(λ 2 + λ n ) + (n - 1)(1 + λ n ) + (λ 2 + λ n ) > 0,
and we have a contradiction. Suppose now that λ3 r > 1. This implies that 2nλ

3 -(n + 1)λ 2 -(n -1) = (n + 1)(λ 3 -λ 2 ) + (n -1)(λ 3 -1)
> 0, and we again get a contradiction. Therefore, by Soules condition (1), there exists an ( n-1

2 ) × ( n-1 2 ) symmetric doubly stochastic matrix B with eigenvalues 1, 1 r λ 4 , 1 r λ 6 , ..., 1 r λ n-1 . Finally, applying Lemma 2 with A = A and B = B, we obtain an n × n symmetric doubly stochastic matrix C whose eigenvalues are 1, λ 2 , ..., λ n . Notation 1. We will say that New condition 1 holds if ( 2) is satisfied when n is even, while ( 6) is satisfied if n is odd.

Observation 1. For n even, Soules implies New condition 1. For n odd, Soules and New condition 1 are independent.

Proof: Let n be even. Suppose now that σ satisfies Soules condition. Since

λ n-4i ≥ λ n-2i , i = 1, 2, ..., n+2 4 -2 and λ 4 ≥ λ i , i = 6, 8, ..., n -n+2 2 + 2,
then σ obviously satisfies New condition 1. For the second part, it suffices to check that for n = 7, the list (1, 0, 0, 0, -2 7 , -2 7 , -2 7 ) satisfies New condition 1 and does not satisfy Soules condition, while the list (1, 0, 0, -3 14 , -3 14 , -3 14 , -3 14 ) does the opposite i.e. it satisfies Soules condition and does not satisfy New condition 1.

Next, we present the following auxiliary lemma. Lemma 5. Let n = 4m + 1 ≥ 9 where m is a positive integer and 1 ≥ λ 2 ≥ ... ≥ λ n ≥ -1. Then

1 n + n -1 n(n + 1) λ 2 + 2(n -1) (n + 1)(n + 3) λ 4 + n+3 4 -[ n+7 8 ] n+3 4 [ n+7 8 ] λ 8 + [ n+7 8 ]-1 k=1 λ n-8k+8 (k + 1)k ≤ 1 n + n -1 n(n + 1) λ 2 + 4 (n -1)(n + 1) λ 2 + 2 n -1 λ 4 + n-1 4 -[ n+3 8 ] n-1 4 [ n+3 8 ] λ 8 + [ n+3 8 ]-1 k=1 λ n-8k+7 (k + 1)k .
Proof: As n = 4m + 1, we have

1 n + n -1 n(n + 1) λ 2 + 2(n -1) (n + 1)(n + 3) λ 4 + n+3 4 -[ n+7 8 ] n+3 4 [ n+7 8 ] λ 8 + [ n+7 8 ]-1 k=1 λ n-8k+8 (k + 1)k = 1 n + n -1 n(n + 1) λ 2 + 1 2m(2m + 1) + m -1 2m(m + 1) λ 4 + n+3 4 -[ n+7 8 ] n+3 4 [ n+7 8 ] λ 8 + [ n+7 8 ]-1 k=1 λ n-8k+8 (k + 1)k ≤ 1 n + n -1 n(n + 1) λ 2 + 1 2m(2m + 1) λ 2 + m -1 2m(m + 1) λ 4 + n+3 4 -[ n+7 8 ] n+3 4 [ n+7 8 ] λ 8 + [ n+7 8 ]-1 k=1 λ n-8k+7 (k + 1)k .
Next, we distinguish between the cases m odd and m even. Case 1: For m = 2p + 1, then n = 8p + 5 and hence

n + 7 8 = n + 3 8 = p + 1.
Therefore,

1 n + n -1 n(n + 1) λ 2 + 1 2m(2m + 1) λ 2 + m -1 2m(m + 1) λ 4 + n+3 4 -[ n+7 8 ] n+3 4 [ n+7 8 ] λ 8 + [ n+7 8 ]-1 k=1 λ n-8k+7 (k + 1)k = 1 n + n -1 n(n + 1) λ 2 + 1 2m(2m + 1) λ 2 + m -1 2m(m + 1) λ 4 + 1 2p + 2 λ 8 + p k=1 λ n-8k+7 (k + 1)k = 1 n + n -1 n(n + 1) λ 2 + 1 2m(2m + 1) λ 2 + m -1 2m(m + 1) λ 4 + 1 (2p + 1)(2p + 2) + p (2p + 1)(p + 1) λ 8 + p k=1 λ n-8k+7 (k + 1)k ≤ 1 n + n -1 n(n + 1) λ 2 + 1 2m(2m + 1) λ 2 + m -1 2m(m + 1) λ 4 + 1 (2p + 1)(2p + 2) λ 4 + p (2p + 1)(p + 1) λ 8 + p k=1 λ n-8k+7 (k + 1)k = 1 n + n -1 n(n + 1) λ 2 + 1 2m(2m + 1) λ 2 + 1 2m λ 4 + p (2p + 1)(p + 1) λ 8 + p k=1 λ n-8k+7 (k + 1)k = 1 n + n -1 n(n + 1) λ 2 + 4 (n -1)(n + 1) λ 2 + 2 n -1 λ 4 + n-1 4 -[ n+3 8 ] n-1 4 [ n+3 8 ] λ 8 + [ n+3 8 ]-1 k=1 λ n-8k+7 (k + 1)k .
Case 2: For m = 2p, then n = 8p + 1 and in this case, we have

n + 7 8 = n + 3 8 + 1 = p + 1.
Therefore,

1 n + n -1 n(n + 1) λ 2 + 1 2m(2m + 1) λ 2 + m -1 2m(m + 1) λ 4 + n+3 4 -[ n+7 8 ] n+3 4 [ n+7 8 ] λ 8 + [ n+7 8 ]-1 k=1 λ n-8k+7 (k + 1)k = 1 n + n -1 n(n + 1) λ 2 + 1 2m(2m + 1) λ 2 + m -1 2m(m + 1) λ 4 + p (2p + 1)(p + 1) λ 8 + p k=1 λ n-8k+7 (k + 1)k = 1 n + n -1 n(n + 1) λ 2 + 1 2m(2m + 1) λ 2 + m -1 2m(m + 1) λ 4 + p (2p + 1)(p + 1) λ 8 + 1 p(p + 1) λ 8 + p-1 k=1 λ n-8k+7 (k + 1)k = 1 n + n -1 n(n + 1) λ 2 + 1 2m(2m + 1) λ 2 + m -1 2m(m + 1) λ 4 + p + 1 p(2p + 1) λ 8 + p-1 k=1 λ n-8k+7 (k + 1)k = 1 n + n -1 n(n + 1) λ 2 + 1 2m(2m + 1) λ 2 + m -1 2m(m + 1) λ 4 + 1 2p(2p + 1) + 1 2p λ 8 + p-1 k=1 λ n-8k+7 (k + 1)k ≤ 1 n + n -1 n(n + 1) λ 2 + 1 2m(2m + 1) λ 2 + m -1 2m(m + 1) λ 4 + 1 2p(2p + 1) λ 4 + 1 2p λ 8 + p-1 k=1 λ n-8k+7 (k + 1)k = 1 n + n -1 n(n + 1) λ 2 + 1 2m(2m + 1) λ 2 + 1 2m λ 4 + 1 2p λ 8 + p-1 k=1 λ n-8k+7 (k + 1)k = 1 n + n -1 n(n + 1) λ 2 + 4 (n -1)(n + 1) λ 2 + 2 n -1 λ 4 + n-1 4 -[ n+3 8 ] n-1 4 [ n+3 8 ] λ 8 + [ n+3 8 ]-1 k=1 λ n-8k+7 (k + 1)k .
Thus the proof is complete.

By substituting in Lemma 2, the doubly stochastic matrices obtained when New condition 1 holds, we have the following theorem. It is worthy to point out here that its proof (and the proofs of many other theorems below) may appear to be somewhat tedious, however the technique used in each case of the proof is similar to that of Theorem 4 with only minor difference, namely in the expressions of α and r in each case (see below).

Theorem 5. Let n ≥ 8 and let 1 ≥ λ 2 ≥ .... ≥ λ n ≥ -1. If 1 n + 1 n λ 2 + 2 n λ 4 + n 4 -[ n+4 8 ] n 4 [ n+4 8 ] λ 8 + [ n+4 8 ]-1 k=1 λ n-8k+8 (k + 1)k ≥ 0, (7)
for n = 4m,

1 n + 1 n λ 2 + 2(n -2) n(n + 2) λ 4 + n+2 4 -[ n+6 8 ] n+2 4 [ n+6 8 ] λ 8 + [ n+6 8 ]-1 k=1 λ n-8k+8 (k + 1)k ≥ 0, (8)
for n = 4m + 2,

1 n + n -1 n(n + 1) λ 2 + 2 n + 1 λ 4 + n+1 4 -[ n+5 8 ] n+1 4 [ n+5 8 ] λ 8 + [ n+5 8 ]-1 k=1 λ n-8k+8 (k + 1)k ≥ 0, (9)
for n = 4m + 3, and

1 n + n -1 n(n + 1) λ 2 + 2(n -1) (n + 1)(n + 3) λ 4 + n+3 4 -[ n+7 8 ] n+3 4 [ n+7 8 ] λ 8 + [ n+7 8 ]-1 k=1 λ n-8k+8 (k + 1)k ≥ 0, (10)
for n = 4m + 1 hold, then there exists an n × n symmetric doubly stochastic matrix with eigenvalues 1, λ 2 , ..., λ n .

Proof: The proof is similar to that of Theorem 4. First suppose that n = 4m. By [START_REF] Mourad | A note on the boundary of the set where the decreasingly ordered spectra of symmetric doubly stochastic matrices lie[END_REF], we have

α   2 n + 2 n 1 α λ 4 + n 4 -[ n+4 8 ] n 4 [ n+4 8 ] 1 α λ 8 + [ n+4 8 ]-1 k=1 1 α λ n-8k+8 (k + 1)k   ≥ 0,
where α = 1+λ2 2 ≥ 0. We show by contradiction that α > 0. Suppose that α = 0. Then, λ 2 = -1, which implies that λ 3 = .... = λ n = -1. It follows that

1 n + 1 n λ 2 + 2 n λ 4 + n 4 -[ n+4 8 ] n 4 [ n+4 8 ] λ 8 + [ n+4 8 ]-1 k=1 λ n-8k+8 (k + 1)k < 0,
and this contradicts [START_REF] Mourad | A note on the boundary of the set where the decreasingly ordered spectra of symmetric doubly stochastic matrices lie[END_REF]. Equivalently, we have

1 n 2 + 1 n 2 1 α λ 4 + n 4 -[ n+4 8 ] n 4 [ n+4 8 ] 1 α λ 8 + [ n+4 8 ]-1 k=1 1 α λ n-8k+8 (k + 1)k ≥ 0,
and hence

1 n 2 + 1 n 2 1 α λ 3 + n 4 -[ n+4 8 ] n 4 [ n+4 8 ] 1 α λ 7 + [ n+4 8 ]-1 k=1 1 α λ n-8k+7 (k + 1)k ≥ 0.
We first show by contradiction that λn α ≥ -1. The proof of this, is virtually the same as earlier with only minor difference. Indeed, suppose that λn α < -1, that is, 2λ n +λ 2 +1 < 0. It follows that, [START_REF] Mourad | A note on the boundary of the set where the decreasingly ordered spectra of symmetric doubly stochastic matrices lie[END_REF], we conclude that For n = 4m + 2, using (8), we conclude that

1 n + 1 n λ 2 + 2 n λ n < 0. From condition
1 n + 1 n λ 2 + 2 n λ 4 + n 4 -[ n+4 8 ] n 4 [ n+4 8 ] λ 8 + [ n+4 8 ]-1 k=1 λ n-8k+8 (k + 1)k ≥ 0 > 1 n + 1 n λ 2 + 2 n λ n , that is, 2 n λ 4 + n 4 -[ n+4 8 ] n 4 [ n+4 8 ] λ 8 + [ n+4 8 ]-1 k=2 λ n-8k+8 (k + 1)k + 1 2 λ n - 2 n λ n > 0. Since 1 ≥ λ 2 ≥ ... ≥ λ n ≥ -1, then we clearly have 0 <   2 n + n 4 -[ n+4 8 ] n 4 [ n+4 8 ] + [ n+4 8 ]-1 k=2 1 (k + 1)k   λ 2 + 1 2 λ n - 2 n λ n = 2 n + n 4 -[ n+4 8 ] n 4 [ n+4 8 ] + [ n+4 8 ] -1 [ n+4 8 ] - 1 2 λ 2 + 1 2 λ n - 2 n λ n (using Lemma 3, Part iii) with m = [ n+4 8 ] -1) = n -4 2n (λ 2 + λ n ). Therefore λ 2 + λ n > 0. It follows that 0 > 2λ n + λ 2 + 1 = (λ 2 + λ n ) + (1 + λ n ) > 0,
1 n 2 + n 2 -1 n 2 ( n 2 + 1) 1 α λ 4 + n+2 4 -[ n+6 8 ] n+2 4 [ n+6 8 ] 1 α λ 8 + [ n+6 8 ]-1 k=1 1 α λ n-8k+8 (k + 1)k ≥ 0, and
1 n 2 + n 2 -1 n 2 ( n 2 + 1) 1 α λ 3 + n+2 4 -[ n+6 8 ] n+2 4
[ n+6 8 ] 1 α λ 7 + [ n+6 8 ]-1 k=1 1 α λ n-8k+7 (k + 1)k ≥ 0,
where α = 1+λ2 2 > 0. We show that λn α ≥ -1 by a similar argument as in the previous case. Suppose that

λn α < -1, that is, 2λ n + λ 2 + 1 < 0. It follows that, 1 n + 1 n λ 2 + 2 n λ n < 0.
Then by [START_REF] Mourad | On a spectral property of doubly stochastic matrices and its application to their inverse eigenvalue[END_REF], it holds that

1 n + 1 n λ 2 + 2(n -2) n(n + 2) λ 4 + n+2 4 -[ n+6 8 ] n+2 4 [ n+6 8 ] λ 8 + [ n+6 8 ]-1 k=1 λ n-8k+8 (k + 1)k ≥ 0 > 1 n + 1 n λ 2 + 2 n λ n , that is, 2(n -2) n(n + 2) λ 4 + n+2 4 -[ n+6 8 ] n+2 4 [ n+6 8 ] λ 8 + [ n+6 8 ]-1 k=2 λ n-8k+8 (k + 1)k + 1 2 λ n - 2 n λ n > 0. Since 1 ≥ λ 2 ≥ ... ≥ λ n ≥ -1, we have 0 <   2(n -2) n(n + 2) + n+2 4 -[ n+6 8 ] n+2 4
[ n+6 8 ] + [ n+6 8 ]-1 k=2 1 (k + 1)k   λ 2 + 1 2 λ n - 2 n λ n = 2(n -2) n(n + 2) + n+2 4 -[ n+6 8 ] n+2 4
[ n+6 8 ] + [ n+6 8 ] -1 [ n+6 8 ] - 1 2 λ 2 + 1 2 λ n - 2 n λ n (using Lemma 3, Part iii) with m = [ n+6 8 ] -1) = n -4 2n (λ 2 + λ n ).
Hence λ 2 + λ n > 0, and it then follows that 0 > 2λ n + λ 2 + 1 = (λ 2 + λ n ) + (1 + λ n ) > 0, and we have a contradiction. Note that λ3 α ≤ 1 by a similar argument as in the previous case. Thus, by New condition 1, there are ( n 2 ) × ( n 2 ) symmetric doubly stochastic matrices A and B with eigenvalues 1, 1 α λ 4 , 1 α λ 6 , ..., 1 α λ n and 1, 1 α λ 3 , 1 α λ 5 , ..., 1 α λ n-1 respectively. Now by applying Lemma 2 with A = A, B = B and r = α = 1+λ2 2 , the proof of the second part can be achieved.

For the case n = 4m + 3, using (9) we can write

0 ≤ 1 n + n -1 n(n + 1) λ 2 + 2 n + 1 λ 4 + n+1 4 -[ n+5 8 ] n+1 4 [ n+5 8 ] λ 8 + [ n+5 8 ]-1 k=1 λ n-8k+8 (k + 1)k ≤ 1 n + n -1 n(n + 1) λ 2 + 2 n + 1 λ 3 + n+1 4 -[ n+5 8 ] n+1 4 [ n+5 8 ] λ 7 + [ n+5 8 ]-1 k=1 λ n-8k+8 (k + 1)k = α   1 n+1 2 + 1 n+1 2 1 α λ 3 + n+1 4 -[ n+5 8 ] n+1 4 [ n+5 8 ] 1 α λ 7 + [ n+5 8 ]-1 k=1 1 α λ n-8k+8 (k + 1)k   ,
where α = (n-1)λ2+(n+1) 2n > 0. As earlier, we shall show now that λn α ≥ -1 by contradiction. Suppose that λn α < -1, that is, 2nλ n + (n -1)λ 2 + (n + 1) < 0. It follows that 1 n + n-1 n(n+1) λ 2 + 2 n+1 λ n < 0. From (9), we conclude that

1 n + n -1 n(n + 1) λ 2 + 2 n + 1 λ 4 + n+1 4 -[ n+5 8 ] n+1 4 [ n+5 8 ] λ 8 + [ n+5 8 ]-1 k=1 λ n-8k+8 (k + 1)k ≥ 0 > 1 n + n -1 n(n + 1) λ 2 + 2 n + 1 λ n , that is, 2 n + 1 λ 4 + n+1 4 -[ n+5 8 ] n+1 4 [ n+5 8 ] λ 8 + [ n+5 8 ]-1 k=2 λ n-8k+8 (k + 1)k + 1 2 λ n - 2 n + 1 λ n > 0. Since 1 ≥ λ 2 ≥ ... ≥ λ n ≥ -1, we have 0 <   2 n + 1 + n+1 4 -[ n+5 8 ] n+1 4
[ n+5 8 ] + [ n+5 8 ]-1 k=2 1 (k + 1)k   λ 2 + 1 2 λ n - 2 n + 1 λ n = 2 n + 1 + n+1 4 -[ n+5 8 ] n+1 4
[ n+5 8 ] + [ n+5 8 ] -1 [ n+5 8 ] - 1 2 λ 2 + 1 2 λ n - 2 n + 1 λ n (using Lemma 3, Part iii) with m = [ n+5 8 ] -1) = n -3 2(n + 1) (λ 2 + λ n ).
Hence λ 2 +λ n > 0, and it then follows that 0

> 2nλ n +(n-1)λ 2 +(n+1) = n(λ 2 +λ n )+n(1+λ n )+1-λ 2 > 0,
and again we get a contradiction. In addition, λ3 α ≤ 1 by a similar argument as in the proof of Theorem 4. Therefore by New condition 1, there exists an ( n+1 2 ) × ( n+1 2 ) symmetric doubly stochastic matrix A with eigenvalues 1, 1 α λ 3 , 1 α λ 5 , ..., 1 α λ n . Now from (9), we can write

0 ≤ 1 n + n -1 n(n + 1) λ 2 + 2 n + 1 λ 4 + n+1 4 -[ n+5 8 ] n+1 4 [ n+5 8 ] λ 8 + [ n+5 8 ]-1 k=1 λ n-8k+8 (k + 1)k = 1 n + n -1 n(n + 1) λ 2 + 1 n+1 2 n-1 2 + n-3 2 n+1 2 n-1 2 λ 4 + n+1 4 -[ n+5 8 ] n+1 4 [ n+5 8 ] λ 8 + [ n+5 8 ]-1 k=1 λ n-8k+8 (k + 1)k ≤ 1 n + n -1 n(n + 1) λ 2 + 1 n+1 2 n-1 2 λ 2 + n-3 2 n+1 2 n-1 2 λ 4 + n+1 4 -[ n+5 8 ] n+1 4 [ n+5 8 ] λ 8 + [ n+5 8 ]-1 k=1 λ n-8k+7 (k + 1)k = r   1 n-1 2 + n-3 2 n+1 2 n-1 2 1 r λ 4 + n+1 4 -[ n+5 8 ] n+1 4 [ n+5 8 ] 1 r λ 8 + [ n+5 8 ]-1 k=1 1 r λ n-8k+7 (k + 1)k   ,
where r = (n+1)λ2+(n-1)

2n

. A virtually identical proof to that used in Theorem 4 for the same claim, shows that 0 < r ≤ 1. Next, in order to apply Lemma 2, we shall show as earlier that λn r ≥ -1 by contradiction. Suppose that λn r < -1, that is, 2nλ n + (n + 1)λ 2 + (n -1) < 0. It follows that 1 n + n+1 n(n-1) λ 2 + 2 n-1 λ n < 0, and hence using (9), we obtain

1 n + n -1 n(n + 1) λ 2 + 2 n + 1 λ 4 + n+1 4 -[ n+5 8 ] n+1 4 [ n+5 8 ] λ 8 + [ n+5 8 ]-1 k=1 λ n-8k+8 (k + 1)k ≥ 0 > 1 n + n + 1 n(n -1) λ 2 + 2 n -1 λ n , that is, n -1 n(n + 1) - n + 1 n(n -1) λ 2 + 2 n + 1 λ 4 + n+1 4 -[ n+5 8 ] n+1 4 [ n+5 8 ] λ 8 + [ n+5 8 ]-1 k=2 λ n-8k+8 (k + 1)k + 1 2 λ n - 2 n -1 λ n > 0. Since 1 ≥ λ 2 ≥ ... ≥ λ n ≥ -1, then we have 0 <   n -1 n(n + 1) - n + 1 n(n -1) + 2 n + 1 + n+1 4 -[ n+5 8 ] n+1 4
[ n+5 8 ] + [ n+5 8 ]-1 k=2 1 (k + 1)k   λ 2 + 1 2 λ n - 2 n -1 λ n = n -1 n(n + 1) - n + 1 n(n -1) + 2 n + 1 + n+1 4 -[ n+5 8 ] n+1 4
[ n+5 8 ] + [ n+5 8 ] -1 [ n+5 8 ] - 1 2 λ 2 + 1 2 - 2 n -1 λ n = n -5 2(n -1) (λ 2 + λ n ).
It then follows that 0

> 2nλ n + (n + 1)λ 2 + (n -1) = n(λ 2 + λ n ) + (n -1)(1 + λ n ) + (λ 2 + λ n ) > 0,
and we have a contradiction. In addition, the proof that λ3 r ≤ 1 can be easily done as that of Theorem 4. Therefore, by New condition 1, there exists an ( n-1

2 ) × ( n-1 2 ) symmetric doubly stochastic matrix B with eigenvalues 1, 1 r λ 4 , 1 r λ 6 , ..., 1 r λ n-1 . Now applying Lemma 2 with A = A and B = B, we obtain an n × n symmetric doubly stochastic matrix C with eigenvalues 1, λ 2 , ..., λ n .

Finally, let n = 4m + 1. From (10), we conclude that

0 ≤ 1 n + n -1 n(n + 1) λ 2 + 2(n -1) (n + 1)(n + 3) λ 4 + n+3 4 -[ n+7 8 ] n+3 4 [ n+7 8 ] λ 8 + [ n+7 8 ]-1 k=1 λ n-8k+8 (k + 1)k ≤ 1 n + n -1 n(n + 1) λ 2 + 2(n -1) (n + 1)(n + 3) λ 3 + n+3 4 -[ n+7 8 ] n+3 4 [ n+7 8 ] λ 7 + [ n+7 8 ]-1 k=1 λ n-8k+8 (k + 1)k = α   1 n+1 2 + n+1 2 -1 n+1 2 ( n+1 2 + 1) 1 α λ 3 + n+3 4 -[ n+7 8 ] n+3 4 [ n+7 8 ] 1 α λ 7 + [ n+7 8 ]-1 k=1 1 α λ n-8k+8 (k + 1)k   ,
where α = (n-1)λ2+(n+1) 2n > 0. By a similar argument as the one used in the previous case, we can show that λn α ≥ -1 and λ3 α ≤ 1. On the other hand, by [START_REF] Mourad | An algorithm for constructing doubly stochastic matrices for the inverse eigenvalue problem[END_REF] and Lemma 5 we also have

0 ≤ 1 n + n -1 n(n + 1) λ 2 + 2(n -1) (n + 1)(n + 3) λ 4 + n+3 4 -[ n+7 8 ] n+3 4 [ n+7 8 ] λ 8 + [ n+7 8 ]-1 k=1 λ n-8k+8 (k + 1)k ≤ 1 n + n -1 n(n + 1) λ 2 + 4 (n -1)(n + 1) λ 2 + 2 n -1 λ 4 + n-1 4 -[ n+3 8 ] n-1 4 [ n+3 8 ] λ 8 + [ n+3 8 ]-1 k=1 λ n-8k+7 (k + 1)k = r   1 n-1 2 + 1 n-1 2 1 r λ 4 + n-1 4 -[ n+3 8 ] n-1 4 [ n+3 8 ] 1 r λ 8 + [ n+3 8 ]-1 k=1 1 r λ n-8k+7 (k + 1)k   ,
where r = (n+1)λ2+(n-1) 2n with λn r ≥ -1 and λ3 r ≤ 1 (again for this, a similar proof as above can be employed). Thus by New condition 1, there are ( n+12 )×( n+1 2 ) and ( n-1 2 )×( n-1 2 ) symmetric doubly stochastic matrices A and B with eigenvalues 1, 1 α λ 3 , 1 α λ 5 , ..., 1 α λ n and 1, 1 r λ 4 , 1 r λ 6 , ..., 1 r λ n-1 respectively and such that 0 < r ≤ 1 as earlier. Finally, applying Lemma 2 with A = A and B = B, we obtain an n × n symmetric doubly stochastic matrix C whose eigenvalues are 1, λ 2 , ..., λ n . Notation 2. The conditions of Theorem 5 are referred to as New condition 2.

Observation 2. New condition 2 and New condition 1 are independent. For n = 14, the list given by (1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, -

satisfies New condition 1 and does not satisfy neither New condition 2 nor Soules condition (1). However the list (1, 0, 0, 0, 0, -

3 50 , - 3 50 , - 3 35 , - 3 35 , - 1 10 , - 1 10 , - 1 10 , - 1 10 , - 1 10 )
satisfies New condition 2 and does not satisfy neither New condition 1 nor Soules condition (1).

We can recursively apply the same process to obtain more general sufficient conditions for the SDIEP.

Although, it seems that there is no systematic way of doing this for general n, however we put forward the following conjecture.

Conjecture 1.

Let k and n be any positive integers such that n ≥ 2 k , and let 1 ≥ λ 2 ≥ ... ≥ λ n ≥ -1. For each i = 1, ..., k, denote by α i-1 to be the remainder of the Euclidean division of n by 2 i-1 and define

r (n) i = 2 i-1 -α i-1 if α i-1 = 0 0 if α i-1 = 0. If 1 n + n -[ n+1 2 ] n[ n+1 2 ] λ 2 + n+r (n) 2 2 - n+2+r (n) 2 4 n+r (n) 2 2 n+2+r (n) 2 4 λ 4 + n+r (n) 3 4 - n+4+r (n) 3 8 n+r (n) 3 4 n+4+r (n) 3 8 λ 8 + ... ... + n+r (n) k 2 k-1 - n+2 k-1 +r (n) k 2 k n+r (n) k 2 k-1 n+2 k-1 +r (n) k 2 k λ 2 k + n+2 k-1 +r (n) k 2 k -1 i=1 λ n-2 k i+2 k (i + 1)i ≥ 0,
then there exists a n × n symmetric doubly stochastic matrix with eigenvalues 1, λ 2 , ..., λ n .

Note that for k = 1, k = 2 and k = 3, we obtain respectively Soules condition, New condition 1 and New condition 2. In order to support this conjecture, we shall verify it for the case n = 26 and we refer to the new condition in this case as New condition 3.

Example 1. Let σ = {1, λ 2 , ...,
1 α λ 3 + 3 28 1 α λ 7 + 1 4 1 α λ 15 + 1 2 1 α λ 25 ≥ 0.
Hence, there exists a 13 × 13 symmetric doubly stochastic matrix Bwith eigenvalues 1, λ3 α , λ5 α , ..., λ25 α . Again applying Lemma 2 with A = A and B = B and r = α = 1+λ2 2 , we obtain a 26 × 26 symmetric doubly stochastic matrix C with eigenvalues 1, λ 2 , ..., λ 26 . Note that the list given by (1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -

1 13 , - 1 13 , - 1 13
, -

1 13 , - 1 13
, -

1 13 , - 1 13
, -

1 13 , - 1 13 )
satisfies New condition 3 and does not satisfy New condition 1 nor New condition 2.

Notation 3. For convenience, we shall denote by S, N the sets of all n-tuples σ satisfying Soules condition, and New condition 1, respectively.

4. On the realizability of normalized Suleimanova spectra

A negative answer to Question 1

We begin with a lemma whose proof can be found in [START_REF] Minc | Non-Negative Matrices[END_REF].

Lemma 6. Let A be an n × n indecomposable doubly stochastic matrix. If A has exactly r roots of unit modulus, then these are the r-roots of unity. If r > 1, then r is a divisor of n. Moreover, A is cogredient to a matrix of the form

       0 A 1 0 . . . 0 0 0 A 1 . . . 0 . . . . . . . . . . . . . . . 0 0 0 . . . A r-1 A r 0 0 . . . 0        , (11)
where the A i are doubly stochastic of order n r × n r , i = 1, . . . , r. Making use of the above lemma we have the following: Proposition 1. If n is odd and λ = (1, λ 2 , ..., λ n-1 , -1) with |λ i | < 1 for all i = 2, ..., n -1, then λ cannot be the spectrum of any n × n doubly stochastic matrix.

Proof: Suppose that λ = (1, λ 2 , . . . , λ n-1 , -1) is the spectrum of an n × n doubly stochastic matrix A. Now as A has 2 eigenvalues of unit modulus which are 1 and -1, then by virtue of the preceding lemma, 2 must be a divisor of n which is a contradiction as n is odd.

A direct conclusion is the following corollary that gives a negative answer for Question 1 in the case when n is odd.

Corollary 1. If n is odd, then λ = (1, 0, ..., 0, -1) cannot be the spectrum of any n × n doubly stochastic matrix.

It should be noted here that for n odd, λ = (1, 0, ..., 0, -1) is not the only normalized Suleimanova spectrum that is not realizable by an n × n doubly stochastic matrix. Indeed, for n = 3 there exists an infinite number of such points. To see this, we first recall the following result from Perfect and Mirsky [START_REF] Perfect | Spectral properties of doubly-stochastic matrices[END_REF]. Theorem 6. [START_REF] Perfect | Spectral properties of doubly-stochastic matrices[END_REF] Let 1 ≥ λ 2 ≥ λ 3 ≥ -1, and 1 + λ 2 + λ 3 ≥ 0. There exists a 3 × 3 doubly stochastic matrix with spectrum (1, λ 2 , λ 3 ) if and only if 2 + λ 2 + 3λ 3 ≥ 0.

As a conclusion, we have the following.

Corollary 2. Let 1 ≥ λ 2 ≥ λ 3 ≥ -1,and 1 + λ 2 + λ 3 ≥ 0. There exists a 3 × 3 doubly stochastic matrix with spectrum (1, λ 2 , λ 3 ) if and only if

(1, λ 2 , λ 3 ) is in Convhull[(1, 1, 1), (1, 1, -1), (1, -1/2, -1/2)]
where Convhull stands for convex hull.

Thus we have the following conclusion.

Corollary 3. The region of R 3 that contains all decreasingly ordered normalized Suleimanova spectra that are realizable by doubly stochastic matrices, is

Convhull[(1, -1/2, -1/2), (1, 0, 0), (1, 0, -2/3)],
and the region of all decreasingly ordered normalized Suleimanova spectra that are not realizable by doubly stochastic matrices, is

Convhull[(1, -1/2, -1/2), (1, 0, -1), (1, 0, -2/3)] \ [(1, -1/2, -1/2), (1, 0, -2/3)],
where [(1, -1/2, -1/2), (1, 0, -2/3)] is the line-segment joining (1, -1/2, -1/2) to (1, 0, -2/3).

Some improvement

Here we will derive new sufficient conditions for a normalized Suleimanova spectrum to be the spectrum of a symmetric doubly stochastic matrix. We shall start with the following definition.

Definition 1. An n × n matrix H is a Hadamard matrix if h ij ∈ {±1} and HH T = nI n .
If n is a positive integer such that an n × n Hadamard matrix exists, then n is said to be a Hadamard order.

Let H 0 = (1), H 1 = 1 1 1 -1
, and for n ∈ N\{0, 1} (where N is the set of natural numbers), define

H n := H 1 ⊗ H n-1 = H n-1 H n-1 H n-1 -H n-1 ∈ M 2 n (R).
It is well-known that H n is a Hadamard matrix for every n ∈ N, and the matrix H n obtained from the previous construction is known as the Walsh matrix of order 2 n . Note that Walsh matrices satisfy the following additional well-known properties:

• H T n = H n ; • H -1 n = 1 2 n H n .
Next, we recall the following result which is due to Johnson and Paparella [START_REF] Johnson | Perron spectratopes and the real nonnegative inverse eigenvalue problem[END_REF].

Theorem 7. [3] For any positive integer k and for any

n = 2 k , let λ = (1, λ 2 , λ 3 , ..., λ n ) be a list of n real numbers with 1 λ 2 λ 3 ... λ n -1, λ i ≤ 0 for i = 2, ..., n, and
1 + n i=2 λ i ≥ 0.
Then there exists an n × n symmetric doubly stochastic matrix with spectrum λ.

It is worth mentioning here that the proof of the preceding theorem is constructive. Indeed, with the same notation as above, the authors prove that H k diag(1, λ 2 , λ 3 , ..., λ n )H -1 k is actually an n×n symmetric doubly stochastic matrix with spectrum (1, λ 2 , λ 3 , ..., λ n ).

Our next objective is to exploit the recursive method described earlier in order to find new families of sufficient conditions for NS-SDIEP that improve Soules condition, and New condition 1 for the case of normalized Suleimanova spectra. Theorem 8. Let p and n be two positive integers such that p ≥ 2 and n ≥ 2 p , and let

0 ≥ λ 2 ≥ ... ≥ λ n ≥ -1. If 1 + λ 2 + ... + λ n-1 + λ n ≥ 0, (12)
for n = 2 p , and

1 n + 1 n(n -1) λ 2 + ... + 1 2 p (2 p + 1) λ n-2 p +1 + 1 2 p (λ n-2 p +2 + ... + λ n-1 + λ n ) ≥ 0, (13)
for n > 2 p , then there is an n×n symmetric doubly stochastic matrix with normalized Suleimanova spectrum 1, λ 2 , ..., λ n .

Proof: We will proceed by induction. For n = 2 p , this is true by Theorem 7. Let n > 2 p and suppose that the assertion is true for n -1. Since

0 ≤ 1 n + 1 n(n -1) λ 2 + ... + 1 2 p (2 p + 1) λ n-2 p +1 + 1 2 p (λ n-2 p +2 + ... + λ n-1 + λ n ) = n -1 + λ 2 n(n -1) + 1 (n -1)(n -2) λ 3 + ... + 1 2 p (2 p + 1) λ n-2 p +1 + 1 2 p (λ n-2 p +2 + ... + λ n-1 + λ n )
> 0, and consequently λi θ ≤ 0 for i = 3, ..., n. Next, we show that λi θ ≥ -1 by contradiction. Suppose that λn θ < -1, then 1 n + 1 n(n-1) λ 2 + 1 n-1 λ n < 0. In view of (13), we conclude that

1 n + 1 n(n -1) λ 2 + ... + 1 2 p (2 p + 1) λ n-2 p +1 + 1 2 p (λ n-2 p +2 + ... + λ n-1 + λ n ) ≥ 0 > 1 n + 1 n(n -1) λ 2 + 1 n -1 λ n , that is, 1 (n -1)(n -2) λ 3 + ... + 1 2 p (2 p + 1) λ n-2 p +1 + 1 2 p (λ n-2 p +2 + ... + λ n-1 ) + 1 2 p - 1 n -1 λ n > 0.
As n > 2 p and all the λ i ≤ 0, we get a contradiction. Thus, we arrive at the following inequality:

1 n -1 + 1 (n -1)(n -2) λ 3 θ + ... + 1 2 p (2 p + 1) λ n-2 p +1 θ + 1 2 p λ n-2 p +2 θ + ... + λ n-1 θ + λ n θ ≥ 0.
Therefore, by the induction hypothesis, there exists an (n -1) × (n -1) symmetric doubly stochastic matrix A with eigenvalues (1, λ3 θ , ..., λn θ ). Next, let r = n-1 n (1 -λ 2 ) = 1 -1+(n-1)λ2 n . In order to apply Lemma 1, we shall prove that 0 ≤ r ≤ 1. First observe that n ≥ 1 + (n -1)λ 2 . Moreover, using [START_REF] Soules | Constructing symmetric nonnegative matrices[END_REF], we can write

0 ≤ 1 n + 1 n(n -1) λ 2 + ... + 1 2 p (2 p + 1) λ n-2 p +1 + 1 2 p (λ n-2 p +2 + ... + λ n-1 + λ n ) ≤ 1 n + 1 n(n -1) + ... + 1 2 p (2 p + 1) + 2 p -1 2 p λ 2 = 1 n + n -1 n λ 2 .
Hence 1 + (n -1)λ 2 ≥ 0 and therefore 0 ≤ r ≤ 1. Now applying Lemma 1 with this r and with A = A, we obtain an n × n symmetric doubly stochastic matrix C with eigenvalues 1, λ 2 , ..., λ n .

Next, we present the following remark.

Remark 3. In the sequel, we shall make the convention that a summation over the empty index set is defined to be zero. Now substituting in Lemma 2, the doubly stochastic matrices obtained from Theorem 8, we arrive at the following theorem.

Theorem 9. Let p and n be two positive integers such that p ≥ 2 and n ≥ 2 p+1 , and let

0 ≥ λ 2 ≥ ... ≥ λ n ≥ -1. If 1 n + n -k -1 n(k + 1) λ 2 + k i=2 p λ n-2i+2 (i + 1)i + 1 2 p 2 p -1 i=1 λ n-2i+2 ≥ 0, ( 14
)
holds with n = 2k + 2 for n even and n = 2k + 1 for n odd, then there exists an n × n symmetric doubly stochastic matrix with eigenvalues 1, λ 2 , ..., λ n .

Proof: Case 1: For n = 2k + 2, Inequality (14) can be rewritten as

0 ≤ 1 n + 1 n λ 2 + k i=2 p λ n-2i+2 (i + 1)i + 1 2 p 2 p -1 i=1 λ n-2i+2 = α 1 k + 1 + k i=2 p 1 α λ n-2i+2 (i + 1)i + 1 2 p 1 α 2 p -1 i=1 λ n-2i+2 ,
with α = 1+λ2 2 ≥ 0. We show by contradiction that α > 0. Suppose that α = 0. Then, λ 2 = -1, which implies that λ 3 = .... = λ n = -1. It follows that

1 n + 1 n λ 2 + k i=2 p λ n-2i+2 (i + 1)i + 1 2 p 2 p -1 i=1 λ n-2i+2 < 0,
and this contradicts (14). As before, we show next that λn α ≥ -1 by contradiction. Suppose that λn α < -1, that is, 2λ n + λ 2 + 1 < 0 so that 1 n + 1 n λ 2 + 2 n λ n < 0. From condition (14), we conclude that

1 n + 1 n λ 2 + k i=2 p λ n-2i+2 (i + 1)i + 1 2 p 2 p -1 i=1 λ n-2i+2 ≥ 0 > 1 n + 1 n λ 2 + 2 n λ n , that is, k i=2 p λ n-2i+2 (i + 1)i + 1 2 p 2 p -1 i=2 λ n-2i+2 + 1 2 p - 2 n λ n > 0.
Again as n ≥ 2 p+1 and all λ i ≤ 0, we have a contradiction. Hence by Theorem 8, there exists a (k+1)×(k+1) symmetric doubly stochastic matrix A with eigenvalues 1,

1 α λ 4 , ..., 1 α λ 2k+2 . Moreover, since 1 ≥ λ 2 ≥ ... ≥ λ n ≥ -1, then 1 k + 1 + k i=2 p 1 α λ n-2i+1 (i + 1)i + 1 2 p 1 α 2 p -1 i=1 λ n-2i+1 ≥ 0,
and therefore, there exists a (k + 1) × (k + 1) symmetric doubly stochastic matrix B with eigenvalues 1, 1 α λ 3 , ..., 1 α λ 2k+1 . Applying now Lemma 2, with A = A, B = B and α = r, we obtain an n × n symmetric doubly stochastic matrix C with eigenvalues 1, λ 2 , ..., λ n . Case 2: For n = 2k + 1, we have

0 ≤ 1 2k + 1 + k (2k + 1)(k + 1) λ 2 + k i=2 p λ n-2i+2 (i + 1)i + 1 2 p 2 p -1 i=1 λ n-2i+2 = α 1 k + 1 + k i=2 p 1 α λ n-2i+2 (i + 1)i + 1 2 p 1 α 2 p -1 i=1 λ n-2i+2 , with α = (k+1)+kλ2 2k+1 = (n+1)+(n-1)λ2 2n = 2+(n-1)(1+λ2)
2n > 0. Again, at this point we shall show by contradiction that λn α ≥ -1. Suppose that λn α < -1, that is, 2nλ n + (n -1)λ 2 + (n + 1) < 0. It follows that

1 n + n-1 n(n+1) λ 2 + 2 n+1
λ n < 0, and hence by ( 14), we conclude that

1 n + n -1 n(n + 1) λ 2 + k i=2 p λ n-2i+2 (i + 1)i + 1 2 p 2 p -1 i=1 λ n-2i+2 ≥ 0 > 1 n + n -1 n(n + 1) λ 2 + 2 n + 1 λ n , that is, k i=2 p λ n-2i+2 (i + 1)i + 1 2 p 2 p -1 i=2 λ n-2i+2 + 1 2 p - 2 n + 1 λ n > 0.
As n ≥ 2 p+1 and all the λ i ≤ 0, this leads to a contradiction. Hence, by Theorem 8, there exists a (k + 1) × (k + 1) symmetric doubly stochastic matrix with eigenvalues 1, 1 α λ 3 , ..., 1 α λ 2k+1 . On the other hand, we know that 0

≤ 1 2k + 1 + k (2k + 1)(k + 1) λ 2 + k i=2 p λ n-2i+2 (i + 1)i + 1 2 p 2 p -1 i=1 λ n-2i+2 ≤ 1 2k + 1 + k (2k + 1)(k + 1) λ 2 + 1 k(k + 1) λ 2 + k-1 i=2 p λ n-2i+1 (i + 1)i + 1 2 p 2 p -1 i=1 λ n-2i+1 = r 1 k + k-1 i=2 p 1 r λ n-2i+1 (i + 1)i + 1 2 p 1 r 2 p -1 i=1 λ n-2i+1 ,
where r = (k+1)λ2+k 2k+1

. In order to apply Lemma 2, we need to show that 0 < r ≤ 1. Now since r can be rewritten as r = (k+1)λ2+k 2k+1

= (n+1)λ2+(n-1) 2n = (n-1)λ2+1+2λ2+n-2 2n
, then it is enough to show that 1 + (n -1)λ 2 ≥ 0 (as n > 4). From (14), we conclude that 0

≤ 1 2k + 1 + k (2k + 1)(k + 1) λ 2 + k i=2 p λ n-2i+2 (i + 1)i + 1 2 p 2 p -1 i=1 λ n-2i+2 ≤ 1 2k + 1 + k (2k + 1)(k + 1) + k i=2 p 1 (i + 1)i + 1 2 p 2 p -1 i=1 1 λ 2 = 1 2k + 1 + k (2k + 1)(k + 1) + k k + 1 - 2 p -1 2 p + 2 p -1 2 p λ 2 = 1 2k + 1 + 2k 2k + 1 λ 2 = 1 n + n -1 n λ 2 .
Hence 1 + (n -1)λ 2 ≥ 0 and so 1 + (n -1)λ

2 + 2λ 2 + n -2 ≥ 1 + (n -1)λ 2 -2 + n -2 > 0. Hence, r > 0. Also, as (n + 1)λ 2 + (n -1) ≤ n + 1 + n -1 = 2n, then r ≤ 1.
As earlier, we next show by contradiction that λn r ≥ -1. Suppose that λn r < -1, that is, 2nλ n + (n + 1)λ 2 + (n -1) < 0. It follows that 1 n + n+1 n(n-1) λ 2 + 2 n-1 λ n < 0, and therefore by ( 14), we conclude that

1 n + n -1 n(n + 1) λ 2 + k i=2 p λ n-2i+2 (i + 1)i + 1 2 p 2 p -1 i=1 λ n-2i+2 ≥ 0 > 1 n + n + 1 n(n -1) λ 2 + 2 n -1 λ n , that is, n -1 n(n + 1) - n + 1 n(n -1) λ 2 + k i=2 p λ n-2i+2 (i + 1)i + 1 2 p 2 p -1 i=2 λ n-2i+2 + 1 2 p - 2 n -1 λ n > 0. Since 1 ≥ λ 2 ≥ ... ≥ λ n ≥ -1, then we can write 0 < n -1 n(n + 1) - n + 1 n(n -1) + k i=2 p 1 (i + 1)i + 1 2 p 2 p -1 i=2 1 λ 2 + 1 2 p - 2 n -1 λ n = n -1 n(n + 1) - n + 1 n(n -1) + k k + 1 - 2 p -1 2 p + 2 p -2 2 p λ 2 + 1 2 p - 2 n -1 λ n = n -1 n(n + 1) - n + 1 n(n -1) + n -1 n + 1 -1 + 1 2 p + 1 - 2 2 p λ 2 + 1 2 p - 2 n -1 λ n since k = n -1 2 = n -5 n -1 + 2 n -1 - 1 2 p λ 2 + 1 2 p - 2 n -1 λ n = n -5 n -1 λ 2 + 1 2 p - 2 n -1 (λ n -λ 2 ).
Since n = 2k + 1 and n ≥ 2 p+1 , then obviously n ≥ 2 p+1 + 1. However, this leads to a contradiction as λ 2 ≤ 0 and (λ n -λ 2 ) ≤ 0. Therefore, by Theorem 8, there exists a k × k symmetric doubly stochastic matrix with eigenvalues 1, 1 r λ 4 , ..., 1 r λ 2k . Now the proof can be easily completed by applying Lemma 2, with A = A and B = B.

Again, substituting in Lemma 2 the doubly stochastic matrices obtained from Theorem 9, we obtain the following theorem for which its proof is virtually identical to that of Theorem 4. So only, a sketch of its proof is given here. Theorem 10. Let p and n be two positive integers such that p ≥ 2 and n ≥ 2 p+2 , and let 0 ≥ λ 2 ≥ ... ≥ λ n ≥ -1. Suppose that

1 n + 1 n λ 2 + n 2 -[ n+2 4 ] n 2 [ n+2 4 ] λ 4 + [ n+2 4 ]-1 i=2 p λ n-4i+4 (i + 1)i + 1 2 p 2 p -1 i=1 λ n-4i+4 ≥ 0, (15)
for n even and

1 n + n -1 n(n + 1) λ 2 + n+1 2 -[ n+3 4 ] n+1 2 [ n+3 4 ] λ 4 + [ n+3 4 ]-1 i=2 p λ n-4i+4 (i + 1)i + 1 2 p 2 p -1 i=1 λ n-4i+4 ≥ 0, (16)
for n odd, hold. Then there exists an n × n symmetric doubly stochastic matrix D whose eigenvalues are 1, λ 2 , ..., λ n .

Proof: If n is even, then by (15) and Theorem 9, there are ( n 2 ) × ( n 2 ) symmetric doubly stochastic matrices A and B with eigenvalues 1, 1 α λ 4 , 1 α λ 6 , ..., 1 α λ n and 1, 1 α λ 3 , 1 α λ 5 , ..., 1 α λ n-1 respectively, where α = 1+λ2 2 . Apply now Lemma 2, with A = A and B = B, then we obtain an n × n symmetric doubly stochastic C with eigenvalues 1, λ 2 , ..., λ n . If n is odd, then by (16) and Theorem 9, there are ( n+12 ) × ( n+1 2 ) and ( n-1 2 ) × ( n-1 2 ) symmetric doubly stochastic matrices A and B with eigenvalues 1, 1 α λ 3 , 1 α λ 5 , ..., 1 α λ n and 1, 1 r λ 4 , 1 r λ 6 , ..., 1 r λ n-1 respectively with α = (n-1)λ2+(n+1) 2n and r = (n+1)λ2+(n-1) 2n . Applying Lemma 2 (the reason we can apply it, can be justified as earlier) with A = A and B = B, we obtain an n × n symmetric doubly stochastic matrix C with eigenvalues 1, λ 2 , .., λ n . Notation 4. For convenience, we denote by M p the condition of Theorem 8, S p the condition of Theorem 9 and N p the condition of Theorem 10.

With these new notations, we have the following observations. Observation 3. Let σ = {1, λ 2 , ..., λ n } be a normalized Suleimanova spectrum with n ≥ 8. If σ satisfies S then σ satisfies S 2 . Consequently, with a slight abuse of notation, we conclude that S ⊂ S 2 .

Proof: Suppose that σ satisfies S. If n = 2k + 1 for n odd and n = 2k + 2 for n even, then clearly we have Therefore, σ satisfies N 2 . A similar argument can also be employed, for the case when n is odd.

0 ≤ 1 n + n -k -1 n(k +
Theorem 11. Let n ≥ 4 be an integer, and let 0 ≥ λ 2 ≥ ... ≥ λ n ≥ -1. Define w p , v p , z p and y p as follows. λ n-4i+4 .

• For n odd, and for any positive integer p ≥ 2 with 2 p+2 ≤ n, define

y p := 1 n + n -1 n(n + 1) λ 2 + n+1 2 -[ n+3 4 ] n+1 2 [ n+3 4 ] λ 4 + [ n+3 4 ]-1 i=2 p λ n-4i+4 (i + 1)i + 1 2 p 2 p -1 i=1 λ n-4i+4 .
Then, for p > 2, Consider the list σ = (1, 0, 0, 0, 0, -2 3 ). It is easy to see that σ does not verify Soules condition (1) but it verifies condition M 2 . Therefore, it is the spectrum of a 6 × 6 symmetric doubly stochastic matrix.

Example 3. For n = 9, consider the list σ = (1, 0, 0, 0, 0, -1 5 , -1 5 , -1 5 , -1 5 ). A simple check shows that σ does not verify Soules condition (1). However, σ verifies conditions S 2 and M 3 , and therefore it is the spectrum of a 9 × 9 symmetric doubly stochastic matrix.

Finally, by making use of Theorem 1, we end our discussion with the following sufficient condition concerning realizable Suleimanova spectra of even order.

  and we have a contradiction. Next, we show that λ3 α ≤ 1 by contradiction. If λ3 α > 1, then clearly 2λ 3 -λ 2 -1 > 0, and we get a contradiction. Thus, by New condition 1, there are ( n 2 ) × ( n 2 ) symmetric doubly stochastic matrices A and B with eigenvalues 1, 1 α λ 4 , 1 α λ 6 , ..., 1 α λ n and 1, 1 α λ 3 , 1 α λ 5 , ..., 1 α λ n-1 respectively. Now applying Lemma 12 2 with A = A, B = B and r = α = 1+λ2 2 , we obtain an n × n symmetric doubly stochastic matrix C whose eigenvalues are 1, λ 2 , ..., λ n .

1 ).Observation 5 .

 15 w p -w p-1 ≥ 0, 2) v p -v p-1 ≥ 0, 3) z p -z p-1 ≥ 0, 4) y p -y p-1 ≥ 0, Proof: We shall only give the proof of Part 1), as the rest can be proved similarly. For simplicity, let us denote m = 2 p . Then, It follows that for p > 2,w p -w p-1 = --m+2 -λ n-i+1 ) ≥ 0, since 0 ≥ λ 2 ≥ ... ≥ λ n ≥ -1. Thus the proof is complete.As a result, we have the following observation (keeping in mind a slight abuse of notation). For a normalized Suleimanova spectrum, we have• M 2 ⊂ M 3 ⊂ ... ⊂ M p ⊂ M p+1 ⊂ .... • S 2 ⊂ S 3 ⊂ ... ⊂ S p ⊂ S p+1 ⊂ .... • N 2 ⊂ N 3 ⊂ ... ⊂ N p ⊂ N p+1 ⊂ .... Example 2.

Theorem 12 .

 12 For any two nonnegative powers of 2, n and m with m ≥ n, let σ = {1, λ 2 , ..., λ n+m } ⊂ R, such that 0 ≥ λ 2 ≥ ... ≥ λ n+m ≥ -1. If there exists a permutation π on {λ 2 , ..., λ n+m } such that π(λ 2 , ..., λ n+m ) = (µ 2 , ..., µ n+m ) andµ 2 > -n m , µ 3 + ... + µ n+1 ≥ -mµ 2 + n m + n ,

  λ 26 } be a list of 26 real numbers such that 1 ≥ λ 2 ≥ ... ≥ λ 26 ≥ -1. . By[START_REF] Mourad | An algorithm for constructing doubly stochastic matrices for the inverse eigenvalue problem[END_REF] of Theorem 5, there exists a 13 × 13 symmetric doubly stochastic matrix A with eigenvalues 1, λ4 α , λ6 α , ..., λ26 α . On the other hand, since 1 ≥ λ 2 ≥ ... ≥ λ n ≥ -1, we conclude that

	with α = 1+λ2 2 1 13	+	6 (13)(7)
																In this
	case, New condition 3 states
	0 ≤	1 26	+	1 26	λ 2 +	6 (13)(7)	λ 4 +	3 28	λ 8 +	1 4	λ 16 +	1 2	λ 26
	= α	1 13	+	6 (13)(7)	1 α	λ 4 +	3 28	1 α	λ 8 +	1 4	1 α	λ 16 +	1 2	1 α	λ 26

  Observation 4. Let σ = {1, λ 2 , ..., λ n } be a normalized Suleimanova spectrum with n ≥ 16. If σ satisfies N then σ satisfies N 2 . Thus, with a slight abuse of notation, we have N ⊂ N 2 .

												1)	λ 2 +	k i=4	λ n-2i+2 (i + 1)i	+	1 12	λ n-4 +	1 6	λ n-2 +	1 2	λ n
					≤		1 n	+	n -k -1 n(k + 1)	λ 2 +	k i=4	λ n-2i+2 (i + 1)i	+	1 12	λ n-4 +	1 6	λ n-4 +	1 4	λ n-2 +	1 4	λ n
					=		1 n	+	n -k -1 n(k + 1)	λ 2 +	k i=4	λ n-2i+2 (i + 1)i	+	1 4	λ n-4 +	1 4	λ n-2 +	1 4	λ n .
	0 ≤	1 n	+	1 n	λ 2 +	n 2 -[ n+2 4 ] n 2 [ n+2 4 ]	λ 4 +	[ n+2 4 ]-1 i=4	λ n-4i+4 (i + 1)i	+	1 12	λ n-8 +	1 6	λ n-4 +	1 2	λ n
	≤	1 n	+	1 n	λ 2 +	n 2 -[ n+2 4 ] n 2 [ n+2 4 ]	λ 4 +	[ n+2 4 ]-1 i=4	λ n-4i+4 (i + 1)i	+	1 12	λ n-8 +	1 6	λ n-8 +	1 4	λ n-4 +	1 4	λ n
	=	1 n	+	1 n	λ 2 +	n 2 -[ n+2 4 ] n 2 [ n+2 4 ]	λ 4 +	[ n+2 4 ]-1 i=4	λ n-4i+4 (i + 1)i	+	1 4	λ n-8 +	1 4	λ n-4 +	1 4	λ n .

Therefore, σ satisfies S 2 .

Proof: If n is even and σ satisfies N , then

•

  For any positive integer p ≥ 2 with 2 p ≤ n, let (λ n-2 p +2 + ... + λ n-1 + λ n ). For n even, and for all positive integers p ≥ 2 with 2 p+2 ≤ n, let

	w p := 2 p • For n = 1 n + 1 n(n -1) λ 2 + ... + 1 2 p (2 p + 1) 1 λ n-2 p +1 + 2k + 1 if n is odd 2k + 2 if n is even , and for all positive integers p ≥ 2 with 2 p+1 ≤ n, let
		v p :=	1 n	+	n -k -1 n(k + 1)	λ 2 +	k i=2 p	λ n-2i+2 (i + 1)i	+	1 2 p	2 p -1 i=1	λ n-2i+2 .
	z p :=	1 n	+	1 n	λ 2 +	n 2 -[ n+2 4 ] n 2 [ n+2 4 ]	λ 4 +	[ n+2 4 ]-1 i=2 p	λ n-4i+4 (i + 1)i	+	1 2 p	2 p -1 i=1

•

Many thanks go to the reviewer for pointing out this.

Acknowledgments

The authors sincerely thank the referee for his/her valuable suggestions and many useful comments which have helped to improve the paper and clarify the details. Also, many thanks go to the Editor and the Editor-in-Chief for giving us a chance to revise.

The first, the second and the fourth authors acknowledge financial support from the Lebanese University research grants program.

and µ n+2 + ... + µ n+m ≥ -nµ 2 + m m + n , then σ is realizable by an (n + m) × (n + m) symmetric doubly stochastic matrix.

Proof: Since 0 ≥ m+n mµ2+n µ 3 + ... + m+n mµ2+n µ n+1 ≥ -1, and n is a nonnegative power of 2, then in view of Theorem 7, there exists an n×n symmetric doubly stochastic matrix A with eigenvalues (1, m+n mµ2+n µ 3 , ..., m+n mµ2+n µ n+1 ). Similarly, since 0 ≥ m+n nµ2+m λ n+2 +...+ m+n nµ2+m µ n+m ≥ -1 and m is a nonnegative power of 2, then by Theorem 7, there exists an m×m symmetric doubly stochastic matrix B with spectrum (1, m+n nµ2+m µ n+2 , ..., m+n nµ2+m µ n+m ). In Theorem 1, taking r = 1, ρ = √ mn(1-µ2) mµ2+n

(as µ 2 > -n m , then ρ > 0), A = A and B = B, then we get an (n + m) × (n + m) symmetric doubly stochastic matrix D with eigenvalues 1, λ 2 , λ 3 , ..., λ n+m .

Example 4. Consider the list of 6 real numbers σ = {1, 0, 0, -1 6 , -1 6 , -11 18 }. It is easy to check that σ does not verify S nor N . Moreover, σ does not verify M 2 (note that S 2 and N 2 cannot be applied). However, taking µ 2 = -1 6 , µ 3 = -1 6 , µ 4 = 0, µ 5 = 0, and µ 6 = -11 18 , then σ verifies Theorem 12 for the case of order 6 = m + n with m = 4 and n = 2. Therefore, it is realizable by a 6 × 6 symmetric doubly stochastic matrix.


Marthe Bonamy

Thomas J Perrett

Gallai

Gallai's path decomposition conjecture for graphs of small maximum degree

Introduction

A decomposition D of a graph G is a collection of subgraphs of G such that each edge belongs to precisely one graph in D. A path decomposition is a decomposition D such that every subgraph in D is a path. If G has a path decomposition D such that |D| = k, then we say that G can be decomposed into k paths. In answer to a question of Erdős, Gallai conjectured the following, see [START_REF] Lovász | On covering of graphs[END_REF].

Conjecture 1.1. [START_REF] Lovász | On covering of graphs[END_REF] Every connected graph on n vertices can be decomposed into n 2 paths.

Gallai's conjecture is easily seen to be sharp: If G is a graph in which every vertex has odd degree, then in any path decomposition of G each vertex must be the endpoint of some path, and so at least n 2 paths are required. Lovász [START_REF] Lovász | On covering of graphs[END_REF] proved that every graph on n vertices has a decomposition D consisting of paths and cycles, and such that |D| = n 2 ::::::::: |D| ≤ n 2 . By an argument similar to the above, it follows that in a graph with at most one vertex of even degree, such a decomposition must be a path decomposition. Thus, Gallai's conjecture holds for all graphs with at most one vertex of even degree.

Let G E denote the subgraph of G induced by the vertices of even degree. Building on Lovász's result, Conjecture 1.1 has been proved for several classes of graphs defined by imposing some structure on G E . The first result of this kind was obtained by Pyber ::: [START_REF] Pyber | Covering the edges of a connected graph by paths[END_REF].

Theorem 1.1. [START_REF] Pyber | Covering the edges of a connected graph by paths[END_REF] If G is a graph on n vertices such that G E is a forest, then G can be decomposed into n 2 paths.

Later, Theorem 1.1 was strengthened by Fan ::: [START_REF] Fan | Path decompositions and Gallai's conjecture[END_REF], who proved the following.

Theorem 1.2. [START_REF] Fan | Path decompositions and Gallai's conjecture[END_REF] If G is a graph on n vertices such that each block of G E is a triangle free ::::::::::

triangle-free : graph of maximum degree at most 3, then G can be decomposed into n 2 paths.

Gallai's conjecture is also known to hold for a variety of other graph classes. In 1988, Favaron

and Koudier [START_REF] Favaron | Path partitions and cycle partitions of Eulerian graphs of maximum degree 4[END_REF] proved that the conjecture holds for graphs where the degree of every vertex is either 2 or 4. More recently, Botler and Jiménez [START_REF] Botler | On path decompositions of 2k-regular graphs[END_REF] proved that the conjecture holds for 2k-regular graphs of large girth and admitting a pair of disjoint perfect matchings. Jiménez and Wakabayashi [START_REF] Jiménez | On path-cycle decompositions of triangle-free graphs[END_REF] showed that the conjecture holds for a subclass of planar, triangle-free graphs satisfying a distance condition on the vertices of odd degree. Finally, it was shown by Geng, Fang and Li [START_REF] Geng | Gallai's conjecture for outerplanar graphs[END_REF], that the conjecture holds for maximal outerplanar graphs. In this article, we prove that Gallai's conjecture holds for the class of graphs with maximum degree at most 5.

Theorem 1.3. Let G be a connected graph on n vertices. If ∆(G) ≤ 5, then G admits a path decomposition into n 2 paths.

To prove Theorem 1.3, we show that if G is a smallest counterexample, then G cannot contain one ::: any : of 5 configurations ::::: given ::::::::::::: configurations :::::::: (Lemma :::: 3.1). This restriction is enough to show that G E is a forest ::::::: (Lemma :::: 3.2), whence the result follows by Theorem 1.1. It seems that proving Theorem 1.3 for graphs of maximum degree 6 will require some new ideas. However, we think the approach of considering graphs of bounded maximum degree allows step-by-step improvements which could :::: may eventually lead to a general solution.

In proving special cases of Conjecture 1. 2 Definitions and notation ::::::::::::::::: Background All graphs in this article are finite and simple, that is, : they contain no loops or multiple edges. We

say that a path decomposition D of a graph G is good if |D| ≤ |V (G)| 2 .
In figures we make use of the following conventions: Solid black circles denote vertices for which all incident edges are depicted. White hollow circles denote vertices which may have other, undepicted incident edges. Vertices containing a number indicate a vertex of that specific degree.

A dotted line between two vertices indicates that those vertices are non-adjacent. ::

We :::::: often ::: use ::::::::: component :: as : a :::::::: shortcut ::: for :::::::::: connected :::::::::: component. :

We will often modify a path decomposition of a graph G to give a path decomposition of another graph G . To describe these modifications we use a number of fixed expressions, which we formally define here. Let D be a path decomposition of G. Let P ∈ D be a path and Q be a subpath of P .

If R is a path in G with the same end vertices as P :: Q, we say that we replace Q with R to mean that we define a new path P = P -Q + R and redefine D to be the collection D -P + P . If R is a path in G with an endpoint in common with P , we say that we extend P with R to mean that we define a new path P = P + R and redefine D to be the collection D -P + P . For a vertex u on P , we say that we split P at u to mean that we define paths P 1 and P 2 such that P 1 ∪ P 2 = P and P 1 ∩ P 2 = u, and redefine D to be the collection D -P + P 1 + P 2 . Finally, for a path R in G , we say that we add the path R to mean that we redefine D to be the collection D + R. ::::: Given :: a ::::: graph ::

G ::: and :::: two ::::::: disjoint :::: sets ::: A :::: and :: B :: of ::::::: vertices ::: of ::: G, ::: we :::::: denote ::: by :::::::: E(A, B) ::: the ::: set ::: of ::::: edges ::::: with ::: one , then D is a good path decomposition of G.

Let |V (G)| = n. We have |D| ≤ |D | + 1 ≤ n-2 2 + 1 = n 2 .
Thus D is a good path decomposition of G. Let G, G 1 and G 2 have n, n 1 and n 2 vertices respectively. We have

|D| ≤ |D 1 | + |D 2 | -1 ≤ n1 2 + n2 2 -1 ≤ n 2 . Thus D is a good path decomposition of G. Proposition 2.3. Let G, G 1 and G 2 be three graphs such that |V (G)| ≥ |V (G 1 )| + |V (G 2 )| + 1,
and let D be a path decomposition of G. If there are good path decompositions D 1 and D 2 of G 1 and

G 2 (respectively) and |D| ≤ |D 1 | + |D 2 |, then D is a good path decomposition of G.
Let G, G 1 and G 2 have n, n 1 and n 2 vertices respectively. We have

|D| ≤ |D 1 | + |D 2 | ≤ n1 2 + n2 2 ≤ n 2 .
Thus D is a good path decomposition of G.

Main Result

Let G be a graph with ∆(G) ≤ k. We first prove that a number of configurations are reducible in G, if . :::::: That ::: is, :: if :: G :::::::: contains :::: one :: of :::::: them :::: and Gallai's conjecture holds for all smaller graphs of maximum degree k, ::::: then ::::::: Gallai's :::::::::: conjecture ::::: holds ::: for :: G. the three other neighbors ::::::::: neighbours : of u (resp. v), the pairs t 1 t 2 and w 1 w 2 are not edges and Proof.

d(u) = d(v) = 4. C 4 : An edge uv such that d(u) = d(v) = 4,
t 3 = w 3 .
Claim 1. G does not contain the configuration C 1 .

Proof. Suppose that the claim is false. Let u be the vertex of degree 2 with N (u) = {v, w}, and let G be the graph G -u + vw. Since v and w are non-adjacent :: in :: G, G is a simple graph. By the minimality of G, we have that G admits a good path decomposition D . By Proposition 2.3, we obtain a good path decomposition of G by replacing the edge vw with the path vuw (see Figure 2). Proof. Suppose that the claim is false. Let :: uv ::: be :::: the :::: edge :::::: stated ::: in ::::::::::::: Configuration ::: C 3 , :::: and ::: let : x and y be the :::: two common neighbours of u and v. Since d(u) = d(v) = 4, both u and v both : u :::: and : v have precisely one other neighbour. Let these vertices be :::: more :::::::::: neighbour, ::: say : u and v respectively.

Since u and v have precisely two common neighbours, we have that , :::::::::::: respectively, ::::: where : u = v .

Suppose first that at most one of the edges xu , u y, yv , v x ::: xu , :::: u y, :::: yv , :::: In this decomposition, replace xy by xuy and replace yz by yvz. Finally, add a new path xvuz (see Figure 4). This gives a good path decomposition of G, a contradiction. We may thus assume that u and v have at most one common neighbour.

v x : is present in G, say xu . If G -u -v is connected, then let G be the graph G -u -v + u y + v x. Otherwise, let G = G -u -v + u y + v x + xy. Note that G is connected,
We now consider three cases depending on the structure of G -{u, v}. In each case we assume the previous ones do not apply (up to symmetry). Let G be the graph obtained from G -{u, v} by adding the edges t 1 t 2 and w 1 w 2 . By the argument above, G is connected, and so by the minimality of G, there is a good path decomposition of G . We obtain a path decomposition of G by replacing t 1 t 2 with t 1 ut 2 and w 1 w 2 with w 1 vw 2 , and adding the path t 3 uvw 3 . Note that since t 3 = w 3 the latter is really a path. By Proposition 2.1, and since we add ::::: added : at most one new path, this yields a good path decomposition of G. We consider three cases. 2. Assume that one of the edges ux 1 , ux 2 , vy 1 , vy 2 , wz 1 , wz 2 :::: ux 1 , :::: ux 2 , ::::: vy 1 , :::: vy 2 , ::::: wz 1 , :::: wz 2 is not a cut-edge. Assume without loss of generality that ux 1 is such an edge. Let G be the graph obtained from G -u by contracting the edge vw to a vertex s, and adding the edge sx 2 . Note that G is connected and |V (G )| = |V (G)| -2, so by the minimality of G, there is a good path decomposition D of G .

t 1 u v w 2 t 3 t 2 w 3 w 1 t 1 w 2 t 3 t 2 w 3 w 1 P Q t 1 u v w 2 t 3 t 2 w 3 w 1 P P Q Q R R R
We obtain a path decomposition of G as follows. We first replace any subpath of the form ysz, y ∈ {y 1 , y 2 }, z ∈ {z 1 , z 2 } with yvwz (preferably) or with yvuwz (if there are two such subpaths). We then replace any subpath of the form x 2 st, t ∈ {y 1 , y 2 , z 1 , z 2 }, with x 2 urt where r is the vertex of {v, w} adjacent to t. We replace any remaining edge of the form ts, t ∈ {x 2 , y 1 , y 2 , z 1 , z 2 } with tr, where r is the vertex of {u, v, w} adjacent to t. Let D be the resulting collection of disjoint paths in G. Note that since d(s) = 5, there is a path P in D that ends in s, thus a path P in D that ends in r ∈ {u, v, w}. We consider the set of edges of G that do not belong to a path in D . If that set does not induce a path, then we extend P to wu or wv. Note that this guarantees the only remaining edges induce a path Q, which we add to the path collection. By Proposition 2.1, and since we added at most one new path, this yields a good path decomposition of G. w) is adjacent to no other triangle and some edge in E({u, v, w}, {x 1 , x 2 , y 1 , y 2 , z 1 , z 2 }) is not a cut-edge.

x 1 y 1 , x 2 y 2 and z 1 z 2 . Note that G has precisely three connected components G 1 , G 2 , and G 3 . By the minimality of G, there are good path decompositions of G 1 , G 2 and G 3 . We obtain a path decomposition of G by replacing x 1 y 1 with the path x 1 uvy 1 , replacing x 2 y 2 with x 2 uwvy 2 , and replacing z 1 z 2 with the path z 1 wz 2 (see Figure 11). These paths are all distinct since the edges x 1 y 1 , x 2 y 2 and z 1 z 2 belong to different components of G . Note that the total number of paths involved in the resulting path decomposition of G is at most

|V (G1)|+1 2 + |V (G2)|+1 2 + |V (G3)|+1 2 = |V (G)| 2
, thus it is a good path decomposition.

:Proposition 2 . 1 .

 21 ::::::: endpoint :: in :: A :::: and :::: the ::::: other :: in ::: B. : :: By ::::::: simple :::::::::: arithmetic, ::: we :::: can :::::: obtain ::: the ::::: three :::::::::::: propositions :::::: below. : Let G and G be two graphs such that |V (G)| ≥ |V (G )| + 2, and let D be a path decomposition of G. If there is a good path decomposition D of G and |D| ≤ |D | + 1 :

Proposition 2 . 2 .

 22 Let G, G 1 and G 2 be three graphs such that |V (G)| ≥ |V (G 1 )| + |V (G 2 )|, and let D be a path decomposition of G. If there are good path decompositions D 1 and D 2 of G 1 and G 2 (respectively) and |D| ≤ |D 1 | + |D 2 | -1, then D is a good path decomposition of G.

Lemma 3 . 1 .

 31 Let k ∈ N. Let G be a connected graph with maximum degree ∆(G) ≤ k, and suppose that G does not admit a good path decomposition. If G is vertex minimal with these properties, then G does not contain any of the following configurations (see Figure1): C 1 : A vertex of degree 2 whose neighbours are not adjacent.

C 2 :

 2 A cut-edge uv such that d(u) and d(v) are even.

C 3 :

 3 An edge uv such that ::::::::::::::: d(u) = d(v) = 4, :::: and u and v have precisely 2 common neighbours, and

Figure 1 :C 5 :

 15 Figure 1: Configurations C 1 , C 3 , C 4 and C 5 from Lemma 3.1.

Figure 2 :Figure 3 :

 23 Figure 2: The reduction of C 1 .

  and so by the minimality of G, it admits a good path decomposition. Now, replace v x by xvv :::: v vx : and replace u y by u uy. Furthermore, if xy ∈ E(G ) \ E(G), then replace xy by xuvy. Otherwise, : add a new path xuvy to the decomposition. By Proposition 2.1, and since we add ::::: added : at most one new path, the resulting decomposition is a good path decomposition of G. This contradicts the assumption that G has no such decomposition. Next, suppose that xu , u y, yv , v x ∈ E(G) ::: xu , :::: u y, :::: yv , ::::::::::: v x ∈ E(G), so the graph G = Gu -v is connected. By the minimality of G, the graph G has a good path decomposition. Now replace the edge xu with the path xvuu , and add a new path u xuyvv to the decomposition. By Proposition 2.1, and since we add ::::: added : at most one new path, the resulting decomposition is a good path decomposition of G, contradicting the assumption. Finally, suppose that precisely two or three of the edges xu , u y, yv , v x ::: xu , :::: u y, :::: yv , :::: v x : are present in G. As a consequence, from the set {xu , u y, yv , v x} \ E(G), we may choose an edge, xu say, such that the graph G = G -u -v + xu is connected. By the minimality of G, the graph G has a good path decomposition. Now replace xu by xvuu , and add a new path xuyvv to the decomposition. Again, by Proposition 2.1, and since we add :::::: added at most one new path, the resulting decomposition is a good path decomposition of G, contradicting the assumption. ♦ Claim 4. G does not contain the configuration C 4 . Proof. Suppose that the claim is false. Since G does not contain Configuration C 3 , the vertices u and v do not have precisely two common neighbours. First suppose that u and v have 3 common neighbours x, y and z. In this case, since there is a pair of non-adjacent vertices amongst N (u)\{v}, we may assume xy ∈ E(G). Furthermore, by the definition of Configuration C 4 , the third vertex z is non-adjacent to at least one of x or y. We conclude that there are two non-edges amongst x, y and z, say these are xy and yz; :::: say ::::::::: yz ∈ E(G). Let G be the graph G -u -v + xy + yz. It is easy to see that G is connected. By the minimality of G, the graph G has a good path decomposition.

Figure 4 :

 4 Figure 4: The reduction of C 4 in the case where u and v have three common neighbors :::::::::: neighbours.

1 .

 1 Suppose first that t and w lie in the same component of G -u -v. Since G -u -v has at most 3 components, and G -u and G -v have at most 2 components, there are non edges tt and ww for some t ∈ T and w ∈ W such that G -u -v + tt + ww is connected. Furthermore, since t and w are the only possible common neighbours of u and v, we have that the single vertices in T \ {t, t } and W \ {w, w } are not equal. Thus, letting t 1 = t, t 2 = t , w 1 = w, w 2 = w and setting t 3 and w 3 to be the remaining vertices gives the desired relabeling.Suppose now that t and w lie in different components of G -u -v. In particular this implies that T ∩ W = ∅. Again, since G -u -v has at most 3 components, and G -u and G -v have at most 2 components, there are non-edges e T and e W amongst the vertices of T and W respectively, such that G -u -v + e T + e W is connected. We relabel the vertices in T and W such that t 1 and t 2 are the endpoints of e T , w 1 and w 2 are the endpoints of e W , and t 3 and w 3 are the remaining vertices. Since T ∩ W = ∅, we have that t 3 = w 3 are : as : required.

Figure 5 :Figure 6 :Figure 7 :Figure 8 :

 5678 Figure 5: The reduction of C 4 in the connected case.

Figure 9 :

 9 Figure 9: The reduction of C 5 when u and w have precisely one common neighbor :::::::: neighbour : and d(v) = 2.

3 .Figure 10 :

 310 Figure 10: An example of the reduction of C 5 when d(u) = d(v) = d(w) = 4, the triangle (u, v, w) is adjacent to no other triangle and some edge in E({u, v, w}, {x 1 , x 2 , y 1 , y 2 , z 1 , z 2 }) is not a cut-edge.

1 Figure 11 :Lemma 3 . 2 .

 11132 Figure 11: The reduction of C 5 when d(u) = d(v) = d(w) = 4, the triangle (u, v, w) is adjacent to no other triangle and every edge in E({u, v, w}, {x 1 , x 2 , y 1 , y 2 , z 1 , z 2 }) is a cut-edge.

  and for t 1 , t 2 , t 3 ::

t 1 , ::: t 2 , :: t 3 : (resp. w 1 , w 2 , w 3 ::: w 1 , ::: w 2 , :::: w 3 )

1 .

 1 Assume that G -u has at least three connected components. Because uv is not a cut-edge, the component of G -u containing v contains at least one other neighbor ::::::::: neighbour : of u. Thus G -u has precisely three components, and t 1 and t 2 lie in different components of G -u. Let G be the graph formed from G -u by adding the edge t 1 t 2 . Thus G has two components G 1 and G 2 , and by the minimality of G, both have good path decompositions D 1 and D 2 . The edge t 1 t 2 is replaced with t 1 ut 2 , w 1 w 2 with w 1 vw 3 , and t 3 w 3 with t 3 uvw 3 ) to obtain a path decomposition of G. By Proposition 2.3, this yields a good path decomposition of G.3. Now G -{u, v} has at most three connected components, and each of G -u and G -v has at most two connected components. Let T = {t 1 , t 2 , t 3 } and W = {w 1 , w 2 , w 3 }. We claim that we can relabel the vertices in T and W such that the graph G -u -v + t 1 t 2 + w 1 w 2 is connected and the properties that t 1 t 2 , w 1 w 2 ∈ E(G)

Without loss of generality we suppose G 2 contains v. Let P ∈ D 1 be the path containing the edge t 1 t 2 . Furthermore, let P 1 and P 2 be the possibly empty subpaths of P -t 1 t 2 containing t 1 and t 2 respectively. Note that since v has degree 3 in G , there is some path Q ∈ D 2 which ends at v. We construct a path decomposition of G by taking the union D 1 ∪ D 2 and replacing P and Q with the paths P 1 + t 1 uv + Q and P 2 + t 2 ut 3 . By Proposition 2.3, and since we introduced no new ::: did ::: not :::::::: increase ::: the ::::::: number ::: of paths, the resulting path decomposition is good, a contradiction. 2. Assume that G -{u, v} has at least four connected components. Since both G -u and Gv have at most two connected components, there are precisely four connected components C 1 , C 2 , C 3 and C 4 ::: H 1 , :::: H 2 , ::: H 3 :::: and ::: H 4 . Furthermore, two of these components contain both a neighbour of u and a neighbour of v, one component contains only a neighbour of u, and one component contains only a neighbour of v. Relabeling if necessary, we may suppose that t 1 , w 1 ∈ C 1 , t 2 , w 2 ∈ C 2 , t 3 ∈ C 3 and w 3 ∈ C 4 :: t 1 , :::::::: w 1 ∈ H 1 , ::: t 2 , ::::::::: w 2 ∈ H 2 , ::::::: t 3 ∈ H 3 :::: and :::::::: w 3 ∈ H 4 . This relabelling preserves the fact that t 1 t 2 , w 1 w 2 ∈ E(G) :::: t 1 t 2 , ::::::::::::: w 1 w 2 ∈ E(G) : and t 3 = w 3 . Consider the graph G 1 obtained from C 1 and C 2 :: H 1 :::: and :::: H 2 by adding the edges t 1 t 2 and w 1 w 2 . Similarly, consider the graph G 2 obtained from C 3 and C 4 :: H 3 :::: and ::: H 4 : by adding the edge t 3 w 3 . By the minimality of G, we obtain good path decompositions of G 1 and G 2 , which we merge in the obvious way. :::: t 1 t 2 , :::::::::::: w 1 w 2 ∈ E(G) : and t 3 = w 3 are preserved. Indeed if u and v have a common neighbour, let t ∈ T and w ∈ W be such that t = w. Otherwise : , : let t = t 1 and w = w

1 .

 1 Assume first that one of v and w has degree 2, say d(v) = 2. Let G be the graph obtained from G -v by contracting the edge uw. Note that G is connected and|V (G )| = |V (G)| -2.By the minimality of G, there is a good path decomposition D of G . To obtain a path decomposition of G, we consider two cases depending on whether ux 1 and ux 2 belong to the same path in D , see Figures9 and 10. If they do not, then replace ux 1 with the path wux 1 , and replace ux 2 with the path wvux 2 . However, if ux 1 and ux 2 belong to the same path P ∈ D , then split P at u into two paths P 1 and P 2 . Extend P 1 with the edge uw and extend P 2 with the path uvw. Note that no edge incident to w is in P 1 or P 2 . By Proposition 2.1, and since we created at most one new path, this yields a good path decomposition of G.

						v
		x 1	P	w	x 1	P 1
	v					u	w
		x 2			x 2	2
	x 1
	u	w
	x 2	x 1		w

Let uv be an edge of C. Let t 1 , t 2 , t 3 :: t 1 , :::: t 2 , :: t 3 : be the neighbours of u apart from v and let w 1 , w 2 , w 3 ::: w 1 , ::: w 2 , :::: w 3 : be the neighbours of v apart from u. Note that, since uv is an edge of C, at least one of t 1 , t It follows that ::: By ::::::::: symmetry, ::: we :::::: obtain ::::: that ::::::::::: {w 1 , w 2 , w 3 } ::::: does ::: not ::::::: induce : a ::::::: clique.

:::::::

Suppose :::: now ::::: that ::::::::::: t 1 t 2 ∈ E(G). By :::::::::: symmetry, : all of the edges t 1 t 2 , t 1 t 3 , w 1 w 2 , w 1 w 3 ∈ E(G) ::: t 1 t 2 , ::::: t 1 t 3 , :::::: w 1 w 2 , :::::::::::: w 1 w 3 ∈ E(G). As a consequence, t 1 = w 1 , otherwise this vertex would have degree 6, which is larger than ∆(G). Thus

Acknowledgements

The authors wish to thank François Dross for useful discussions : , :::: and ::: the :::::::::: anonymous ::::::::: reviewers ::: for :::::::

remarks :::::::::: improving ::: the :::::::::::: presentation. The second author was supported by ERC Advanced Grant GRACOL, project number 320812.