Let T be a tree and letx0 be a vertex ofT

ON THE INVERSE EIGENVALUE PROBLEMS: THE CASE OF SUPERSTARS^∗

ROS ´ARIO FERNANDES^†

Abstract. Let T be a tree and letx0 be a vertex ofT. T is called a superstar with central vertexx0ifT−x0is a union of paths. The General Inverse Eigenvalue Problem for certain trees is partially answered. Using this description, some superstars are presented for which the problem of ordered multiplicity lists and the Inverse Eigenvalue Problem are not equivalent.

Key words. Eigenvalues, Tree, Graph, Symmetric matrices.

AMS subject classifications.15A18, 05C38, 05C50.

1. Introduction. LetA= [aij] be an n×nreal symmetric matrix. We denote by G(A) = (X, U) the simple graph on n vertices, {1, . . . , n}, such that {i, j} ∈U, i=j, if and only if aij = 0 . LetA(i) denote the principal submatrix of Aobtained by deleting row and columni.

Let G= (X, U) a simple graph, whereX ={x₁, . . . , xn} is the vertex set of G and letS(G) be the set of all n×nreal symmetric matricesAsuch thatG(A)∼=G.

One of the most important problems of Spectral Graph Theory is the General Inverse Eigenvalue Problem forS(G) (GIEP forS(G)):

“What are all the real numbers λ₁ ≤. . . ≤ λ_n and µ₁ ≤. . . ≤ µ_n−1 that may occur as the eigenvalues ofAandA(i), respectively, asAruns overS(G)?”

Another important problem is the Inverse Eigenvalue Problem forS(G) (IEP for S(G));

“What are all the real numbersλ₁≤. . .≤λn that may occur as the eigenvalues ofA, asAruns overS(G)?”

First, we remind the reader of some results concerning the GIEP.

Perhaps the most well known result on this subject is the Interlacing Theorem for Eigenvalues of Hermitian matrices:

∗Received by the editors September 16, 2007. Accepted for publication July 27, 2009. Handling Editor: Stephen J. Kirkland.

†Departamento de Matem´atica, Faculdade de Ciˆencias e Tecnologia, Universidade Nova de Lisboa, Quinta da Torre, 2829-516 Caparica, Portugal (mrff@fct.unl.pt). This research was done within the activities of “Centro de Estruturas Lineares e Combinat´orias”.

442

Theorem 1.1. [11] If A is an n×n Hermitian matrix with eigenvalues λ₁ ≤ . . .≤λn and ifA(i)has eigenvalues µ₁≤. . .≤µn−1 then

λ₁≤µ₁≤λ₂≤. . .≤λn−1≤µn−1≤λn.

If λ is a real number and A is an n×n real symmetric matrix, we denote by m_A(λ) the multiplicity ofλas an eigenvalue ofA. As a Corollary of Theorem 1.1 we have the following result:

Proposition 1.2. [11] Let A be an n×n Hermitian matrix and let λ be an eigenvalue of A. Then

mA(λ)−1≤m_A(i)(λ)≤mA(λ) + 1, i= 1, . . . , n.

When the graphGis a path, we have the well-known fact:

Proposition 1.3. Let T be a path. IfA is a matrix inS(T)andj is a pendant vertex of T(A), all the eigenvalues of A have multiplicity 1 and the eigenvalues of A(j)strictly interlace those of A.

Several authors proved the converse of Proposition 1.3.

The solution of the GIEP for S(G) when G is a cycle is also well known, see [3, 4, 5, 6].

Leal Duarte generalized the converse of Proposition 1.3 to any tree, [13].

Proposition 1.4. Let T be a tree on nvertices and let i be a vertex ofT. Let λ₁< . . . < λ_n andµ₁< . . . < µ_n−1 be real numbers. If

λ₁< µ₁< λ₂< . . . < µn−1< λn,

then there exists a matrixA inS(T), with eigenvalues λ₁< . . . < λ_n, and such that, A(i)has eigenvaluesµ₁< . . . < µn−1.

In [7], Johnson and Leal Duarte studied this problem for vertices, of a generic pathT, of degree two and solved it for the particular case that occurs when A is a matrix inS(T) andA(i) has eigenvalues of multiplicity two.

In 2003, Johnson, Leal Duarte and Saiago, [8], rewrote the GIEP forS(G):

“LetGbe a simple connected graphGonnvertices,x₀be a vertex ofGof degree k and G₁, . . . , Gk be the connected components of G−x₀. Let λ₁, . . . , λn be real numbers,g₁(t), . . . , g_k(t) be monic polynomials having only real roots and such that

degg_i(t) is equal to the number of vertices ofG_i. Is it possible to construct a matrix A inS(G) such thatA has eigenvaluesλ₁, . . . , λn and the characteristic polynomial ofA[Gi] isgi(t) (A[Gi] is the principal submatrix ofAobtained by deleting rows and columns that correspond to vertices ofG−G_i)?”

With respect to GIEP forS(G) as written above, the following results are proven in [8].

Theorem 1.5. Let T be a tree onnvertices andx₀ be a vertex of T of degreek whose neighbors are x₁, . . . , x_k. Let T_i be the branch (connected component) of T at x₀ containingxi andsi be the number of vertices inTi,i= 1, . . . , k.

Let g₁(t), . . . , g_k(t)be monic polynomials having only distinct real roots, with deg gi(t) = si, p₁, . . . , ps be the distinct roots among polynomials gi(t) and mi be the multiplicity of root pi in k

i=1gi(t).

Let g(t)be a monic polynomial of degrees+ 1.

There exists a matrix Ain S(T)with characteristic polynomial f(t) =g(t)

s i=1

(t−p_i)^mi−1

and such that

1) A[T_i] has characteristic polynomialg_i(t),i= 1, . . . , k,

2) If 1≤i≤k andsi >1, the eigenvalues ofA[Ti−xi]strictly interlace those of A[Ti],

if and only if the roots ofg(t)strictly interlace those of s

i=1(t−p_i).

The statement of the previous theorem is shorter when T is a generalized tree, [8].

Theorem 1.6. Let T be a generalized star on nvertices with central vertex x₀, letT₁, . . . , Tk be the branches ofT atx₀, and let l₀, . . . , lk be the number of vertices of T₁, . . . , T_k, respectively.

Let g₁(t), . . . , gk(t)be monic polynomials having only real roots, with deg gi(t) = li, let p₁, . . . , pl be the distinct roots among polynomials gi(t)and let mi be the mul- tiplicity of root p_i in k

i=1g_i(t), (m_i≥1).

Let g(t)be a monic polynomial of degreel+ 1.

There exists a matrix Ain S(T)with characteristic polynomial f(t) =g(t)

l i=1

(t−pi)^mi−1

and such thatA[T_i]has characteristic polynomialg_i(t),i= 1, . . . , k, if and only if each gi(t)has only simple roots and the roots ofg(t)strictly interlace those ofl

i=1(t−pi).

In [8], the GIEP was solved for S(T) when T is a generalized star. Moreover, the authors of [8] proved that the IEP for S(G) when Gis a generalized star, T, is equivalent to the determination of all possible ordered multiplicity lists ofT; that is, ifA ∈ S(T) has eigenvalues λ₁ < . . . < λt of multiplicitiesm₁, . . . , mt, respectively, then for any set of real numbersλ₁< . . . < λ_t, there exists a matrixA∈ S(T) having eigenvaluesλ₁< . . . < λ_tof multiplicitiesm₁, . . . , m_t, respectively.

The case of double generalized stars has also been studied by Barioli and Fallat in [1].

In [2], Barioli and Fallat gave the first example of a graph (the graph T) for which the equivalence between the ordered multiplicity lists and the IEP does not occur. Another example appears in [10], the graphT.

✉ ✉ ✉

✉

✉

✉ ✉ ✉

✉

✉

✉

✉ ✉ ✉

✉

❅❅

❅

❅❅

❅ x₀

T

✉ ✉

✉

✉

✉

✉

✉ ✉

✉

✉

❅❅

❅ x₀

T

Bearing in mind these two graphs, we give now the following definitions.

Definition 1.7. LetT be a tree and x₀ be a vertex ofT. A superstarT with central vertexx₀ is a tree such that T−x₀ is a union of paths.

Definition 1.8. LetT be a tree andx₀be a vertex ofT. LetT_ibe a connected component ofT −x₀ andxi be the vertex ofTi adjacent tox₀ inT. We say thatTi

is a cut branch atxi ifTi−xi has at most two connected components.

The aforementioned trees T and T are superstars. All the paths, stars and generalized stars (defined in [8]) are also superstars. Sometimes, whenTis a superstar

with central vertexx₀, we say thatT is a superstar atx₀.

More recently, ([12] Lemma 16) Kim and Shader proved a necessary condition for the GIEP to have a solution for some superstars. Notice that in [12] thek-whirls are the superstars of the present paper.

Lemma 1.9. ([12] Lemma 16) Let T be a superstar on n vertices with central vertexx₀ whose neighbors are x₁, . . . , xk. Let Ti be the branch ofT at x₀ containing x_i,i= 1, . . . , k. Suppose that T₁, . . . , T_k are cut branches atx₁, . . . , x_r, respectively, and letαⁱ₁, αⁱ₂ be the paths ofT_i−x_i,i= 1, . . . , k.

Let A in S(T) and let A be the direct sum of A[αⁱ_j], for all i ∈ {1, . . . , k} and j∈ {1,2}. Ifn_r denotes the number of eigenvalues ofA with multiplicityr, then the following holds:

(a) nk+1 ≤1 andnj = 0for j≥k+ 2;

(b) if λis an eigenvalue ofA andm_A(λ) =k+ 1, thenλis a simple eigenvalue of A[αⁱ_j], for alli∈ {1, . . . , k} andj∈ {1,2}, andmA(λ) = 2k;

(c) if µis an eigenvalue ofA andmA(µ) =k, then for all i=s,j andt,µis a simple eigenvalue of at least one ofA[αⁱ_j],A[α^s_t], andm_A(µ)≥2k−2; and (d) (2k−2)n_k+ (2k)n_k+1≤n−(k+ 1).

In section 3, the methods used to prove Theorem 1.5 allows us to generalize it. As in this generalization we suppose that some branches of the treeT are cut branches we obtain a much more general result than Lemma 1.9. Using this generalization we prove in section 4:

1) there is no matrixA∈ S(T) (whereTis the above mentioned tree) having eigenvalues

(0,2,2,3,3,3,3,4,4,5,5,5,6,6,7), but there exists a matrixA∈ S(T) having eigenvalues (1,2,2,3,3,3,3,4,4,5,5,5,6,6,7).

2) there is no matrixA∈ S(T) (whereTis the above mentioned tree) having eigenvalues

(−√ 5,−√

2,−√

2,0,0,0,0,√ 2,√

2,2), but there exists a matrixA∈ S(T) having eigenvalues

(−√ 5,−√

2,−√

2,0,0,0,0,√ 2,√

2,√ 5).

In section 4, we also prove that the converse of Lemma 1.9 is not true.

2. Prior Results. The key tool used to prove Proposition 1.4 and Theorem 1.5 was the decomposition of a real rational function into partial fractions. We recall here the following well known results, which will be useful for the present work.

Lemma 2.1. [13] Let g(t) be a monic polynomial of degree n, n > 1, having only distinct real roots andh(t)be a monic polynomial with degh(t)<degg(t). Then h(t) has n−1 distinct real roots strictly interlacing the roots of g(t) if and only if the coefficients of the partial fraction decomposition (pfd) of ^h_g(^(t_t)⁾ are positive real numbers.

Remark 2.2. Ifλ₁, . . . , λn andµ₁, . . . , µn−1 are real numbers such that λ₁< µ₁< λ₂< . . . < µn−1< λn

and,g(t) andh(t) are the monic polynomials g(t) = (t−λ₁)(t−λ₂). . .(t−λ_n), h(t) = (t−µ₁)(t−µ₂). . .(t−µ_n−1),

it is easy to show that _h^g(₍^t_t⁾₎ can be represented in a unique way as g(t)

h(t)= (t−a)−

n−1 i=1

xi

t−µ_i in whicha=n

i=1λ_i−n−1

i=1 µ_i and x_i, i= 1, . . . , n−1, are positive real numbers such that

x_i=− g(µi) n−1

j=1,j=i(µi−µj) =− n

j=1(µi−λj) n−1

j=1,j=i(µi−µj).

If T is a tree on n vertices, A∈ S(T) and Ti is a subgraph of T, we denote by A[T_i] (respectively,A(T_i)) the principal submatrix ofAobtained by deleting rows and columns that correspond to vertices ofT\T_i(respectively,T_i). We will also need the expansion of the characteristic polynomial at a particular vertex ofT with neighbors x₁, . . . , xk.

Lemma 2.3. [9] Let T be a tree on n vertices and let A = [aij] be a matrix in S(T). Ifx₀ is a vertex of T of degreek, whose neighbors inT are x₁, . . . , xk, then

pA(t) = (t−ax₀x₀)p_A[T−x0](t)− k i=1

|ax₀x_i|²p_A[Ti−xi](t) k j=1,j=i

p_A[Tj](t), (2.1)

with the convention thatp_A[Ti−xi](t) = 1whenever the vertex set ofT_i is{x_i}.

SinceT is a tree, ifAis a matrix inS(T) andx₀ is a vertex of degreek, we have A(x₀) =A[T₁]⊕. . .⊕A[Tk], whereTi is the branch ofT−x₀containing the neighbor xi ofx₀ inT. The following result was shown in [8].

Lemma 2.4. [8] Let T be a tree and A be a matrix inS(T). Let x₀ be a vertex of T andλbe an eigenvalue of A(x₀). Let x_i be a neighbor ofx₀ inT andT_i be the branch of T atx₀ containingxi. Ifλis an eigenvalue ofA[Ti] and

m_A[Ti−xi](λ) =m_A[Ti](λ)−1, thenm_A(x0)(λ) =m_A(λ) + 1.

WhenT is a generalized star with central vertexx₀, each branchTi ofT atx₀ is a path. Thus, ifB is a matrix inS(Ti) then all the eigenvalues ofB have multiplicity 1 and the eigenvalues ofB(x_i) strictly interlace those ofB.

Lemma 2.5. [8] Let T be a generalized star with central vertex x₀. If A is a matrix inS(T)andλis an eigenvalue of A(x₀)thenm_A(x0)(λ) =m_A(λ) + 1.

LetT be a tree andAbe a matrix inS(T). A result concerning the multiplicity of the largest and smallest eigenvalues ofAwas proved in [9].

Lemma 2.6. IfT is a tree, the largest and smallest eigenvalues of each matrixA inS(T), have multiplicity1. Moreover, the largest or smallest eigenvalue of a matrix A inS(T)cannot occur as an eigenvalue of a submatrix A(x₀), for any vertexx₀ in T.

Using this result we can prove the following lemma.

Lemma 2.7. Let T be a tree on n >1 vertices, x₀ be a vertex in T and A be a matrix in S(T). Then there exists an eigenvalue λ of A(x₀) such that m_A(λ) = m_A(x0)(λ)−1.

Proof. Suppose that for each eigenvalueλofA(x₀) we havem_A(λ)=m_A(x0)(λ)−

1.Consequently, ifλis an eigenvalue ofA(x₀) thenm_A(λ)≥m_A(x0)(λ).SinceA(x₀) hasn−1 eigenvalues andAhasneigenvalues, there exists at most one eigenvalue of Awhich is not an eigenvalue ofA(x₀). Using Lemma 2.6 we obtain a contradiction, and the result follows.

LetT be a tree andA be a matrix inS(T). We have the following result, which can be obtained collectively from [14, 15]. Note that if Ais a matrix in S(T), then A(i) will be a direct sum of matrices, and we refer to the direct summands as blocks ofA(i).

Theorem 2.8. Let T be a tree, A be a matrix inS(T) and λbe an eigenvalue of Asuch that m_A(λ)≥2. Then there exists a vertex iin G(A) such that

1) m_A(i)(λ) =m_A(λ) + 1;

2) λis an eigenvalue of at least three blocks of A(i).

3. General Inverse Eigenvalue Problem. The following theorem generalizes Theorem 1.5 and gives a partial answer of the GIEP for S(T) when some of the branches ofT, at a fixed vertexx₀, are cut branches.

Theorem 3.1. Let T be a tree onnvertices andx₀ be a vertex of T of degreek whose neighbors are x₁, . . . , x_k. Let T_i be the branch ofT atx₀ containingx_i ands_i be the number of vertices inTi,i= 1, . . . , k.

Let T₁, . . . , Tr, with 0 ≤ r ≤k, be cut branches at x₁, . . . , xr, respectively, and l_j= min{number of vertices in each connected component of T_j−x_j},j= 1, . . . , r.

Let g₁(t), . . . , gk(t)be monic polynomials having only distinct real roots, with deg g_i(t) = s_i, p₁, . . . , p_s be the distinct roots among polynomials g_i(t) and m_j be the multiplicity of root p_j ink

i=1g_i(t).

Let g(t)be a monic polynomial of degrees+ 1,p₁, . . . , pl be the common roots of g(t)ands

i=1(t−p_i)and

g(t) = g(t)

l

i=1(t−pi).

For each 1≤j≤r, let q_j1< q_j2< . . . < q_jvj, with1≤v_j ≤l_j, be roots ofg_j(t).

Let

gj(t) =

_g

j(t)

(t−q_j1)...(t−q_jvj) if 1≤j≤r gj(t) if r < j≤k.

and

mij=

1 ifp_i is a root ofg_j(t) 0 otherwise.

There exists a matrix Ain S(T)with characteristic polynomial f(t) =g(t)

s i=1

(t−pi)^mi−1

and such that

1) A[Ti] has characteristic polynomialgi(t),i= 1, . . . , k,

2) for each1≤j≤r,qj1, qj2, . . . , qjv_j are the common eigenvalues ofA[Tj]and A[T_j−x_j], andm_[Tj−xj](q_j1) =. . .=m_[Tj−xj](q_jvj) = 2,

3) if r < i≤k ands_i >1, the eigenvalues ofA[T_i−x_i] strictly interlace those of A[Ti],

if and only if I) s−l≥1,

II) the roots ofg(t)strictly interlace those ofs

i=l+1(t−pi),

III) p₁, . . . , pl are not roots of gj(t) and there exist positive real numbers yij, i∈ {l+ 1, . . . , s},j∈ {1, . . . , k}such that

for eachi∈ {l+ 1, . . . , s}

−_s g(p_i)

j=l+1,j=i(pi−pj) = k j=1

m_ijy_ij, (3.1)

and for each j∈ {1, . . . , r},u∈ {1, . . . , vj} s

i=l+1,m_ij=1

mijyij

qju−pi = 0.

(3.2)

Proof. We start by proving the necessity of the stated conditions for the existence of the matrixA. Firstly notice that the characteristic polynomial ofA(x₀) =A[T₁]⊕ . . .⊕A[T_k] isk

i=1g_i(t) =s

i=1(t−p_i)^mi. By hypothesis,f(t) =g(t)s

i=1(t−p_i)^mi−1 is the characteristic polynomial of A. So, using Lemma 2.7 there exists 1≤ i ≤ s such that pi is not a root ofg(t). Because p₁, . . . , plare roots ofg(t) then s−l ≥1 and we have I).

Ass

i=1mi =n−1 thenn−s−1 +l=s

i=1(mi−1) +l is the degree of the polynomial s

i=1(t−pi)^mi−1l

j=1(t−pj). Because pA(t) = f(t) = g(t)l j=1(t− p_j)s

i=1(t−p_i)^mi−1 is a polynomial of degreen theng(t) is a polynomial of degree s−l+ 1. By hypothesis,p₁, . . . , p_lare the common roots ofg(t) ands

i=1(t−p_i) then g(t) must haves−l+ 1 real roots (becauseAis symmetric), each one different from eachpl+1, . . . , ps. By the interlacing theorem for eigenvalues of Hermitian matrices, the roots ofp_A(t) must interlace the roots ofp_A(x0)(t) =s

i=1(t−p_i)^mi. Then the roots ofg(t) must strictly interlace those ofs

i=l+1(t−pi). So, we have II).

Now we are going to prove III). Letj∈ {1, . . . , k}. Ifsj >1, denote byhj(t) the characteristic polynomial ofA[T_j−x_j]; ifs_j= 1, defineh_j(t) = 1. Let

h_j(t) =

_h

j(t)

(t−q_j1)...(t−q_jvj) if 1≤j≤r h_j(t) ifr < j ≤k.

By the interlacing theorem for eigenvalues of Hermitian matrices, and by hypothesis 2), if 1≤j ≤r or by hypothesis 3), ifr < j ≤k andsj >1, then the roots ofgj(t) must strictly interlace those ofh_j(t). By Lemma 2.1, if s_j>1, or by construction, if

s_j= 1, there exist positive real numbersb_ij, with 1≤i≤s, 1≤j ≤k, such that for eachj∈ {1, . . . , k},

hj(t)

gj(t) = hj(t) gj(t) =

s i=1

mijbij

t−pi.

By hypothesis, if 1 ≤ i ≤ l then p_i is a root of g(t). So, if 1 ≤ i ≤ l then m_i = m_A(x0)(pi)=mA(pi) + 1. Therefore, using Lemma 2.4, if 1≤i≤l and pi is a root of A[Tj] thenpi is a root of A[Tj−xj]. By hypothesis, it follows that m_A[Tj](pi) is equal to 1 or to 0. Consequently,p₁, . . . , p_l are not roots of g_j(t) (if r < j ≤k and s_j>1 we use hypothesis 3); if 1≤j≤r, we use hypothesis 2) and the fact thatg_j(t) has distinct real roots).

Therefore, there exist positive real numbers b_ij, withl+ 1≤i≤s, 1 ≤j ≤k, such that for eachj∈ {1, . . . , k},

hj(t)

g_j(t) = hj(t) g_j(t) =

s i=l+1

mijbij

t−p_i (3.3)

SinceA= [aij] is a matrix inS(T), we define for eachj∈ {1, . . . , k},xj=|ax₀x_j|² anda=a_x0x0. According to (2.1), the characteristic polynomial ofAmay be written as

pA(t) = (t−ax₀x₀) k j=1

p_A[Tj](t)− k j=1

|ax₀x_j|²p_A[Tj−xj](t) k u=1u=j

p_A[Tu](t)

= (t−a) k j=1

gj(t)− k j=1

xj

p_A[Tj−xj](t) p_A[Tj](t)

k u=1

gu(t)

= ((t−a)− k j=1

x_j s i=l+1

m_ijb_ij t−p_i)

s i=1

(t−p_i)^mi

= ((t−a)− s i=l+1

k

j=1x_jm_ijb_ij t−pi )

s i=1

(t−p_i) s i=1

(t−p_i)^mi−1

Consequently,

g(t) = ((t−a)− s i=l+1

k

j=1xjmijbij

t−p_i ) s i=1

(t−pi)

and

g(t) = g(t)

l

i=1(t−pi) = (t−a) s i=l+1

(t−pi)− s i=l+1

k j=1

(xjmijbij) s u=l+1,u=i

(t−pu)

So, for eachi∈ {l+ 1, . . . , s},g(pi) =−k

j=1(xjmijbij)s

u=l+1,u=i(pi−pu). Then

−s g(pi)

u=l+1,u=i(p_i−p_u) = k j=1

(xjmijbij).

For each i∈ {l+ 1, . . . , s} andj ∈ {1, . . . , k}, we denote x_jb_ij byy_ij. Since b_ij, x_j are positive real numbers, theny_ij is a positive real number and we have III)(3.1).

Let j ∈ {1, . . . , r}. Since qj1, . . . , qjv_j are the common eigenvalues of A[Tj] and A[T_j −x_j], and m_A[Tj−xj](q_j1) = . . . = m_A[Tj−xj](q_jvj) = 2, by hypothesis 2), we have thatq_j1, . . . , q_jvj are roots ofh_j(t) but not ofg_j(t). Thus, ifp_i is a root ofg_j(t) thenpi∈ {qj1, . . . , qjv_j}. Therefore, by (3.3), for eachu∈ {1, . . . , vj},

0 = xjhj(qju) gj(qju) =

s i=l+1, m_ij=1

mij(xjbij) qju−pi =

s i=l+1, m_ij=1

mijyij

qju−pi.

So, we have III)(3.2).

Next, we prove the sufficiency of the stated conditions. Because of the strict interlacing between the roots ofg(t) and those ofs

i=l+1(t−pi) (hypothesis II) and becauseg(t) is a polynomial of degrees+ 1−l >1, due to Remark 2.2, we conclude the existence of a real numberaand positive real numbersxl+1, . . . , xssuch that

s g(t)

i=l+1(t−p_i) = (t−a)− s i=l+1

xi

(t−p_i) i.e.,

g(t) =

(t−a)− s i=l+1

xi

(t−p_i) _s

i=l+1

(t−pi)

= (t−a) s i=l+1

(t−pi)− s i=l+1

xi

s j=l+1,j=i

(t−pj).

Therefore, if l+ 1≤i≤s,

g(p_i) =−x_i s j=l+1,j=i

(p_i−p_j)

and

xi=−s g(pi)

j=l+1j=i(p_i−p_j).

Using hypothesis III)(3.1), there exist real positive numbersy_ij, withl+ 1≤i≤s, 1≤j ≤k such thatxi=k

j=1mijyij. So, g(t) =

(t−a)− s i=l+1

k

j=1m_ijy_ij (t−pi)

_s

i=l+1

(t−pi)

=

(t−a)−( s i=l+1

m_i1y_i1

(t−pi)+. . .+ s i=l+1

m_iky_ik (t−pi))

_s

i=l+1

(t−pi).

By hypothesis III) then g_j(t) = s

i=l+1(t−p_i)^mij. Notice that, when deg g_j(t) >

1, s

i=l+1m_ijy_ij

(t−p_i) is a pfd of ^h_g^j(t)

j(t) for some polynomial h_j(t). By Lemma 2.1, the coefficients of this pfd are positive which means that degh_j(t) =degg_j(t)−1 andh_j(t) has only real roots strict interlacing those ofgj(t). If deggj(t) = 1,s

i=l+1m_ijy_ij (t−p_i) =

m_ujy_uj

g_j(t) , m_ujy_uj > 0, for some u ∈ {l+ 1, . . . , s}. In this case, for convenience we denotem_ujy_uj byh_j(t).

If 1≤j≤r, sinceqj1, . . . , qjv_j are not roots ofgj(t), using III)(3.2) we have that q_j1, . . . , q_jvj are roots ofh_j(t) but not ofg_j(t). Remark that the leading coefficient of h_j(t) is the positive real numbers

i=l+1m_ijy_ij. Let h_j(t) be the monic polynomial such thathj(t)(t−qj1). . .(t−qju_j) = (s

i=l+1mijyij)hj(t). So, g(t) =



(t−a)− k j=1

( s i=l+1

m_ijy_ij)h_j(t) gj(t)



 ^s

i=l+1

(t−p_i).

By hypothesis, if 1 ≤ j ≤ r then Tj is a cut branch at xi. Since gj(t) = gj(t)v_j

i=1(t−qji), the roots ofhj(t) strictly interlace those ofgj(t) andqj1, . . . , qjv_j

are roots ofh_j(t), then by Theorem 1.5, there exists a matrixA_j in S(Tj) such that pA_j(t) =gj(t) andp_Aj[Tj−xj](t) =hj(t). So, we have 2).

Ifr+ 1≤j≤k, by Proposition 1.4, there exists a matrixAj in S(Tj) such that p_Aj(t) =g_j(t) andp_Aj[Tj−xj](t) =h_j(t) (recall the convention that p_Aj[Tj−xj](t) = 1 whenever the vertex set ofTj is{xj}). Therefore, we have 3) and 1).

Now define a matrixA= [aij] in S(T) in the following way:

• ax₀x₀ =a

• a_x0xj =a_xjx0=s

i=l+1m_ijy_ij, forj= 1, . . . , k

• A[T_j] =A_j, forj= 1, . . . , k

• the remaining entries ofA are 0.

According to (2.1), the characteristic polynomial ofAmay be written as

(t−ax₀x₀)p_A[T−x0](t)− k j=1

|ax_ox_j|²p_A[Tj−xj](t) k i=1,i=j

p_A[Ti](t).

Note thatA[T−x₀] =A[T₁]⊕. . .⊕A[Tk] which impliesp_A[T−x0](t) =k

j=1p_A[Tj](t).

Moreover the characteristic polynomial ofA[Tj] isgj(t) and the characteristic polyno- mial ofA[T_j−x_j] ish_j(t). Consequently, by hypothesis,k

j=1g_j(t) =s

i=1(t−p_i)^mi and

p_A(t) = (t−a) s i=1

(t−p_i)^mi− k j=1

( s i=l+1

m_ijy_ij)h_j(t) gj(t)

s i=1

(t−p_i)^mi

=g(t) l i=1

(t−p_i) s i=1

(t−p_i)^mi−1=f(t)

i.e.,pA(t) =f(t).

Under the conditions and following the notation of Theorem 3.1, ifT is a superstar andTj is a cut branch atxj ofT, thenTj is a path. So, ifqjiis a common eigenvalue of A[T_j] andA[T_j−x_j] then m_A[Tj−xj](q_ji) = 2.Therefore, if we suppose that T is a superstar then condition 2) of Theorem 3.1 is shorter and we have the following result.

Theorem 3.2. Let T be a superstar onnvertices andx₀be a central vertex ofT of degreekwhose neighbors arex₁, . . . , x_k. LetT_i be the branch ofT atx₀containing xi andsi be the number of vertices in Ti,i= 1, . . . , k.

Let T₁, . . . , T_r, with 0 ≤ r ≤k, be cut branches at x₁, . . . , x_r, respectively, and l_j= min{number of vertices in each connected component of T_j−x_j},j= 1, . . . , r.

Let g₁(t), . . . , gk(t)be monic polynomials having only distinct real roots, with deg gi(t) = si, p₁, . . . , ps be the distinct roots among polynomials gi(t) and mj be the multiplicity of root p_j ink

i=1g_i(t).

Let g(t)be a monic polynomial of degrees+ 1,p₁, . . . , pl be the common roots of g(t)ands

i=1(t−p_i)and

g(t) = g(t)

l

i=1(t−p_i).