**ON THE INVERSE EIGENVALUE PROBLEMS: THE CASE OF**
**SUPERSTARS**^{∗}

ROS ´ARIO FERNANDES^{†}

**Abstract.** Let *T* be a tree and let*x*0 be a vertex of*T*. *T* is called a superstar with central
vertex*x*0if*T**−**x*0is 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.** Let*A*= [a*ij*] be an *n×n*real 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* *a**ij* = 0 . Let*A(i) denote the principal submatrix of* *A*obtained
by deleting row and column*i.*

Let *G*= (X, U) a simple graph, where*X* =*{x*_{1}*, . . . , x**n**}* is the vertex set of *G*
and let*S(G) be the set of all* *n×n*real symmetric matrices*A*such that*G(A)∼*=*G.*

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

“What are all the real numbers *λ*_{1} *≤. . .* *≤* *λ** _{n}* and

*µ*

_{1}

*≤. . .*

*≤*

*µ*

_{n}*that may occur as the eigenvalues of*

_{−1}*A*and

*A(i), respectively, asA*runs over

*S(G)?”*

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

“What are all the real numbers*λ*_{1}*≤. . .≤λ**n* that may occur as the eigenvalues
of*A, asA*runs over*S*(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 (mrﬀ@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* *λ*_{1} *≤*
*. . .≤λ**n* *and ifA(i)has eigenvalues* *µ*_{1}*≤. . .≤µ**n**−1* *then*

*λ*_{1}*≤µ*_{1}*≤λ*_{2}*≤. . .≤λ**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 of

*A. 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*

*m**A*(λ)*−*1*≤m*_{A}_{(}_{i}_{)}(λ)*≤m**A*(λ) + 1, *i*= 1, . . . , n.

When the graph*G*is 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*
*λ*_{1}*< . . . < λ*_{n}*andµ*_{1}*< . . . < µ*_{n}_{−1}*be real numbers. If*

*λ*_{1}*< µ*_{1}*< λ*_{2}*< . . . < µ**n**−1**< λ**n**,*

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

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

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

“Let*G*be a simple connected graph*G*on*n*vertices,*x*_{0}be a vertex of*G*of degree
*k* and *G*_{1}*, . . . , G**k* be the connected components of *G−x*_{0}. Let *λ*_{1}*, . . . , λ**n* be real
numbers,*g*_{1}(t), . . . , g* _{k}*(t) be monic polynomials having only real roots and such that

deg*g** _{i}*(t) is equal to the number of vertices of

*G*

*. Is it possible to construct a matrix*

_{i}*A*in

*S(G) such thatA*has eigenvalues

*λ*

_{1}

*, . . . , λ*

*n*and the characteristic polynomial of

*A[G*

*i*] is

*g*

*i*(t) (A[G

*i*] is the principal submatrix of

*A*obtained by deleting rows and columns that correspond to vertices of

*G−G*

*)?”*

_{i}With respect to GIEP for*S(G) as written above, the following results are proven*
in [8].

Theorem 1.5. *Let* *T* *be a tree onnvertices andx*_{0} *be a vertex of* *T* *of degreek*
*whose neighbors are* *x*_{1}*, . . . , x*_{k}*. Let* *T*_{i}*be the branch* (connected component) *of* *T* *at*
*x*_{0} *containingx**i* *ands**i* *be the number of vertices inT**i**,i*= 1, . . . , k.

*Let* *g*_{1}(t), . . . , g* _{k}*(t)

*be monic polynomials having only distinct real roots, with deg*

*g*

*i*(t) =

*s*

*i*

*,*

*p*

_{1}

*, . . . , p*

*s*

*be the distinct roots among polynomials*

*g*

*i*(t)

*and*

*m*

*i*

*be the*

*multiplicity of root*

*p*

*i*

*in*

*k*

*i*=1*g**i*(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}*)

^{m}

^{i}

^{−1}*and such that*

1) *A[T** _{i}*]

*has characteristic polynomialg*

*(t),*

_{i}*i*= 1, . . . , k,

2) *If* 1*≤i≤k* *ands**i* *>*1, the eigenvalues of*A[T**i**−x**i*]*strictly interlace those*
*of* *A[T**i*],

*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*_{0}*,*
*letT*_{1}*, . . . , T**k* *be the branches ofT* *atx*_{0}*, and let* *l*_{0}*, . . . , l**k* *be the number of vertices*
*of* *T*_{1}*, . . . , T*_{k}*, respectively.*

*Let* *g*_{1}(t), . . . , g*k*(t)*be monic polynomials having only real roots, with deg* *g**i*(t) =
*l**i**, let* *p*_{1}*, . . . , p**l* *be the distinct roots among polynomials* *g**i*(t)*and let* *m**i* *be the mul-*
*tiplicity of root* *p*_{i}*in* *k*

*i*=1*g** _{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*−p**i*)^{m}^{i}^{−1}

*and such thatA[T** _{i}*]

*has characteristic polynomialg*

*(t),*

_{i}*i*= 1, . . . , k, if and only if each

*g*

*i*(t)

*has only simple roots and the roots ofg(t)strictly interlace those of*

*l*

*i*=1(t*−p**i*).

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* *G*is a generalized star, *T*, is
equivalent to the determination of all possible ordered multiplicity lists of*T*; that is,
if*A* *∈ S*(T) has eigenvalues *λ*_{1} *< . . . < λ**t* of multiplicities*m*_{1}*, . . . , m**t*, respectively,
then for any set of real numbers*λ*^{}_{1}*< . . . < λ*^{}* _{t}*, there exists a matrix

*A*

^{}*∈ S*(T) having eigenvalues

*λ*

^{}_{1}

*< . . . < λ*

^{}*of multiplicities*

_{t}*m*

_{1}

*, . . . , m*

*, respectively.*

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

In [2], Barioli and Fallat gave the ﬁrst 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 graph

*T*

*.*

^{}✉ ✉ ✉

✉

✉

✉ ✉ ✉

✉

✉

✉

✉ ✉ ✉

✉

❅❅

❅

❅❅

❅
*x*_{0}

*T*^{}

✉ ✉

✉

✉

✉

✉

✉ ✉

✉

✉

❅❅

❅
*x*_{0}

*T*^{}

Bearing in mind these two graphs, we give now the following deﬁnitions.

Definition 1.7. Let*T* be a tree and *x*_{0} be a vertex of*T*. A superstar*T* with
central vertex*x*_{0} is a tree such that *T−x*_{0} is a union of paths.

Definition 1.8. Let*T* be a tree and*x*_{0}be a vertex of*T*. Let*T** _{i}*be a connected
component of

*T*

*−x*

_{0}and

*x*

*i*be the vertex of

*T*

*i*adjacent to

*x*

_{0}in

*T*. We say that

*T*

*i*

is a cut branch at*x**i* if*T**i**−x**i* has at most two connected components.

The aforementioned trees *T** ^{}* and

*T*

*are superstars. All the paths, stars and generalized stars (deﬁned in [8]) are also superstars. Sometimes, when*

^{}*T*is a superstar

with central vertex*x*_{0}, we say that*T* is a superstar at*x*_{0}.

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] the*k-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*_{0} *whose neighbors are* *x*_{1}*, . . . , x**k**. Let* *T**i* *be the branch ofT* *at* *x*_{0} *containing*
*x*_{i}*,i*= 1, . . . , k. Suppose that *T*_{1}*, . . . , T*_{k}*are cut branches atx*_{1}*, . . . , x*_{r}*, respectively,*
*and letα*^{i}_{1}*, α*^{i}_{2} *be the paths ofT*_{i}*−x*_{i}*,i*= 1, . . . , k.

*Let* *A* *in* *S*(T) *and let* *A*^{}*be the direct sum of* *A[α*^{i}* _{j}*], for all

*i*

*∈ {*1, . . . , k

*}*

*and*

*j∈ {1,*2}. If

*n*

_{r}*denotes the number of eigenvalues ofA*

*with multiplicityr, then the*

*following holds:*

(a) *n**k*+1 *≤*1 *andn**j* = 0*for* *j≥k*+ 2;

(b) *if* *λis an eigenvalue ofA* *andm** _{A}*(λ) =

*k*+ 1, then

*λis a simple eigenvalue*

*of*

*A[α*

^{i}*], for all*

_{j}*i∈ {1, . . . , k}*

*andj∈ {1,*2}, and

*m*

*A*

*(λ) = 2k;*

^{}(c) *if* *µis an eigenvalue ofA* *andm**A*(µ) =*k, then for all* *i=s,j* *andt,µis a*
*simple eigenvalue of at least one ofA[α*^{i}* _{j}*],

*A[α*

^{s}*], and*

_{t}*m*

*(µ)*

_{A}*≥*2k

*−*2; and (d) (2k

*−*2)n

*+ (2k)n*

_{k}

_{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 tree*T* 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 matrix*A*^{}*∈ S(T** ^{}*) (where

*T*

*is 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 matrix*A∈ S*(T* ^{}*) having eigenvalues
(1,2,2,3,3,3,3,4,4,5,5,5,6,6,7).

2) there is no matrix*A*^{}*∈ S(T** ^{}*) (where

*T*

*is the above mentioned tree) having eigenvalues*

^{}(−*√*
5,*−√*

2,*−√*

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

2,2),
but there exists a matrix*A∈ 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 coeﬃcients of the partial fraction decomposition (pfd) of* ^{h}_{g}_{(}^{(}^{t}_{t}_{)}^{)} *are positive real*
*numbers.*

Remark 2.2. If*λ*_{1}*, . . . , λ**n* and*µ*_{1}*, . . . , µ**n**−1* are real numbers such that
*λ*_{1}*< µ*_{1}*< λ*_{2}*< . . . < µ**n**−1**< λ**n*

and,*g(t) andh(t) are the monic polynomials*
*g(t) = (t−λ*_{1})(t*−λ*_{2})*. . .*(t*−λ** _{n}*),

*h(t) = (t−µ*

_{1})(t

*−µ*

_{2})

*. . .*(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

*x**i*

*t−µ** _{i}*
in which

*a*=

*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 *T**i* is a subgraph of *T*, we denote by
*A[T** _{i}*] (respectively,

*A(T*

*)) the principal submatrix of*

_{i}*A*obtained by deleting rows and columns that correspond to vertices of

*T\T*

*(respectively,*

_{i}*T*

*). We will also need the expansion of the characteristic polynomial at a particular vertex of*

_{i}*T*with neighbors

*x*

_{1}

*, . . . , x*

*k*.

Lemma 2.3. [9] *Let* *T* *be a tree on* *n* *vertices and let* *A* = [a*ij*] *be a matrix in*
*S(T*). If*x*_{0} *is a vertex of* *T* *of degreek, whose neighbors inT* *are* *x*_{1}*, . . . , x**k**, then*

*p**A*(t) = (t*−a**x*_{0}*x*_{0})p_{A}_{[}_{T}_{−}_{x}_{0}_{]}(t)*−*
*k*
*i*=1

*|a**x*_{0}*x*_{i}*|*^{2}*p*_{A}_{[}_{T}_{i}_{−}_{x}_{i}_{]}(t)
*k*
*j*=1*,j**=**i*

*p*_{A}_{[}_{T}_{j}_{]}(t),
(2.1)

*with the convention thatp*_{A}_{[}_{T}_{i}_{−}_{x}_{i}_{]}(t) = 1*whenever the vertex set ofT*_{i}*is{x*_{i}*}.*

Since*T* is a tree, if*A*is a matrix in*S(T*) and*x*_{0} is a vertex of degree*k, we have*
*A(x*_{0}) =*A[T*_{1}]*⊕. . .⊕A[T**k*], where*T**i* is the branch of*T−x*_{0}containing the neighbor
*x**i* of*x*_{0} in*T*. 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*_{0} *be a vertex*
*of* *T* *andλbe an eigenvalue of* *A(x*_{0}). Let *x*_{i}*be a neighbor ofx*_{0} *inT* *andT*_{i}*be the*
*branch of* *T* *atx*_{0} *containingx**i**. Ifλis an eigenvalue ofA[T**i*] *and*

*m*_{A}_{[}_{T}_{i}_{−}_{x}_{i}_{]}(λ) =*m*_{A}_{[}_{T}_{i}_{]}(λ)*−*1,
*thenm*_{A}_{(}_{x}_{0}_{)}(λ) =*m** _{A}*(λ) + 1.

When*T* is a generalized star with central vertex*x*_{0}, each branch*T**i* of*T* at*x*_{0} is
a path. Thus, if*B* is a matrix in*S(T**i*) then all the eigenvalues of*B* have multiplicity
1 and the eigenvalues of*B(x** _{i}*) strictly interlace those of

*B.*

Lemma 2.5. [8] *Let* *T* *be a generalized star with central vertex* *x*_{0}*. If* *A* *is a*
*matrix inS(T*)*andλis an eigenvalue of* *A(x*_{0})*thenm*_{A}_{(}_{x}_{0}_{)}(λ) =*m** _{A}*(λ) + 1.

Let*T* be a tree and*A*be a matrix in*S(T*). A result concerning the multiplicity
of the largest and smallest eigenvalues of*A*was 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*_{0}), for any vertex*x*_{0} *in*
*T.*

Using this result we can prove the following lemma.

Lemma 2.7. *Let* *T* *be a tree on* *n >*1 *vertices,* *x*_{0} *be a vertex in* *T* *and* *A* *be*
*a matrix in* *S(T*). Then there exists an eigenvalue *λ* *of* *A(x*_{0}) *such that* *m** _{A}*(λ) =

*m*

_{A}_{(}

_{x}_{0}

_{)}(λ)

*−*1.

*Proof. Suppose that for each eigenvalueλ*of*A(x*_{0}) we have*m** _{A}*(λ)

*=m*

_{A}_{(}

_{x}_{0}

_{)}(λ)−

1.Consequently, if*λ*is an eigenvalue of*A(x*_{0}) then*m** _{A}*(λ)

*≥m*

_{A}_{(}

_{x}_{0}

_{)}(λ).Since

*A(x*

_{0}) has

*n−*1 eigenvalues and

*A*has

*n*eigenvalues, there exists at most one eigenvalue of

*A*which is not an eigenvalue of

*A(x*

_{0}). Using Lemma 2.6 we obtain a contradiction, and the result follows.

Let*T* be a tree and*A* be a matrix in*S(T). We have the following result, which*
can be obtained collectively from [14, 15]. Note that if *A*is a matrix in *S*(T), then
*A(i) will be a direct sum of matrices, and we refer to the direct summands as blocks*
of*A(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 of*T*, at a ﬁxed vertex*x*_{0}, are cut branches.

Theorem 3.1. *Let* *T* *be a tree onnvertices andx*_{0} *be a vertex of* *T* *of degreek*
*whose neighbors are* *x*_{1}*, . . . , x*_{k}*. Let* *T*_{i}*be the branch ofT* *atx*_{0} *containingx*_{i}*ands*_{i}*be the number of vertices inT**i**,i*= 1, . . . , k.

*Let* *T*_{1}*, . . . , T**r**, with* 0 *≤* *r* *≤k, be cut branches at* *x*_{1}*, . . . , x**r**, respectively, and*
*l** _{j}*= min{number of vertices in each connected component of

*T*

_{j}*−x*

_{j}*},j*= 1, . . . , r.

*Let* *g*_{1}(t), . . . , g*k*(t)*be monic polynomials having only distinct real roots, with deg*
*g** _{i}*(t) =

*s*

_{i}*,*

*p*

_{1}

*, . . . , p*

_{s}*be the distinct roots among polynomials*

*g*

*(t)*

_{i}*and*

*m*

_{j}*be the*

*multiplicity of root*

*p*

_{j}*in*

*k*

*i*=1*g** _{i}*(t).

*Let* *g(t)be a monic polynomial of degrees*+ 1,*p*_{1}*, . . . , p**l* *be the common roots of*
*g(t)and**s*

*i*=1(t*−p** _{i}*)

*and*

*g(t) =* *g(t)*

*l*

*i*=1(t*−p**i*)*.*

*For each* 1*≤j≤r, let* *q*_{j}_{1}*< q*_{j}_{2}*< . . . < q*_{jv}_{j}*, with*1*≤v*_{j}*≤l*_{j}*, be roots ofg** _{j}*(t).

*Let*

*g**j*(t) =

_{g}

*j*(*t*)

(*t**−**q** _{j1}*)

*...*(

*t*

*−*

*q*

*)*

_{jvj}*if*1

*≤j≤r*

*g*

*j*(t)

*if*

*r < j≤k.*

*and*

*m**ij*=

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*−p**i*)^{m}^{i}^{−1}

*and such that*

1) *A[T**i*] *has characteristic polynomialg**i*(t),*i*= 1, . . . , k,

2) *for each*1*≤j≤r,q**j*1*, q**j*2*, . . . , q**jv*_{j}*are the common eigenvalues ofA[T**j*]*and*
*A[T*_{j}*−x** _{j}*], and

*m*

_{[}

_{T}

_{j}

_{−}

_{x}

_{j}_{]}(q

_{j}_{1}) =

*. . .*=

*m*

_{[}

_{T}

_{j}

_{−}

_{x}

_{j}_{]}(q

_{jv}*) = 2,*

_{j}3) *if* *r < i≤k* *ands*_{i}*>*1, the eigenvalues of*A[T*_{i}*−x** _{i}*]

*strictly interlace those*

*of*

*A[T*

*i*],

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

II) *the roots ofg(t)strictly interlace those of**s*

*i*=*l*+1(t*−p**i*),

III) *p*_{1}*, . . . , p**l* *are not roots of* *g**j*(t) *and there exist positive real numbers* *y**ij**,*
*i∈ {l*+ 1, . . . , s*},j∈ {1, . . . , k}such that*

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

*−*_{s}*g(p** _{i}*)

*j*=*l*+1*,j**=**i*(p*i**−p**j*) =
*k*
*j*=1

*m*_{ij}*y*_{ij}*,*
(3.1)

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

*i*=*l*+1*,m** _{ij}*=1

*m**ij**y**ij*

*q**ju**−p**i* = 0.

(3.2)

*Proof. We start by proving the necessity of the stated conditions for the existence*
of the matrix*A. Firstly notice that the characteristic polynomial ofA(x*_{0}) =*A[T*_{1}]*⊕*
*. . .⊕A[T** _{k}*] is

*k*

*i*=1*g** _{i}*(t) =

*s*

*i*=1(t*−p** _{i}*)

^{m}*. By hypothesis,*

^{i}*f*(t) =

*g(t)*

*s*

*i*=1(t*−p** _{i}*)

^{m}

^{i}*is the characteristic polynomial of*

^{−1}*A. So, using Lemma 2.7 there exists 1≤*

*i*

*≤*

*s*such that

*p*

*i*is not a root of

*g(t). Because*

*p*

_{1}

*, . . . , p*

*l*are roots of

*g(t) then*

*s−l*

*≥*1 and we have I).

As*s*

*i*=1*m**i* =*n−*1 then*n−s−*1 +*l*=*s*

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

*i*=1(t*−p**i*)^{m}^{i}^{−1}*l*

*j*=1(t*−p**j*). Because *p**A*(t) = *f*(t) = *g(t)**l*
*j*=1(t*−*
*p** _{j}*)

*s*

*i*=1(t*−p** _{i}*)

^{m}

^{i}*is a polynomial of degree*

^{−1}*n*then

*g(t) is a polynomial of degree*

*s−l*+ 1. By hypothesis,

*p*

_{1}

*, . . . , p*

*are the common roots of*

_{l}*g(t) and*

*s*

*i*=1(t*−p** _{i}*) then

*g(t) must haves−l*+ 1 real roots (because

*A*is symmetric), each one diﬀerent from each

*p*

*l*+1

*, . . . , p*

*s*. By the interlacing theorem for eigenvalues of Hermitian matrices, the roots of

*p*

*(t) must interlace the roots of*

_{A}*p*

_{A}_{(}

_{x}_{0}

_{)}(t) =

*s*

*i*=1(t*−p** _{i}*)

^{m}*. Then the roots of*

^{i}*g(t) must strictly interlace those of*

*s*

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

Now we are going to prove III). Let*j∈ {*1, . . . , k*}*. If*s**j* *>*1, denote by*h**j*(t) the
characteristic polynomial of*A[T*_{j}*−x** _{j}*]; if

*s*

*= 1, deﬁne*

_{j}*h*

*(t) = 1. Let*

_{j}*h** _{j}*(t) =

_{h}

*j*(*t*)

(*t**−**q** _{j1}*)

*...*(

*t*

*−*

*q*

*) if 1*

_{jvj}*≤j≤r*

*h*

*(t) if*

_{j}*r < j*

*≤k.*

By the interlacing theorem for eigenvalues of Hermitian matrices, and by hypothesis
2), if 1*≤j* *≤r* or by hypothesis 3), if*r < j* *≤k* and*s**j* *>*1, then the roots of*g**j*(t)
must strictly interlace those of*h** _{j}*(t). By Lemma 2.1, if

*s*

_{j}*>*1, or by construction, if

*s** _{j}*= 1, there exist positive real numbers

*b*

*, with 1*

_{ij}*≤i≤s, 1≤j*

*≤k, such that for*each

*j∈ {1, . . . , k},*

*h**j*(t)

*g**j*(t) = *h**j*(t)
*g**j*(t) =

*s*
*i*=1

*m**ij**b**ij*

*t−p**i**.*

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}_{(}

_{x}_{0}

_{)}(p

*i*)

*=m*

*A*(p

*i*) + 1. Therefore, using Lemma 2.4, if 1

*≤i≤l*and

*p*

*i*is a root of

*A[T*

*j*] then

*p*

*i*is a root of

*A[T*

*j*

*−x*

*j*]. By hypothesis, it follows that

*m*

_{A}_{[}

_{T}

_{j}_{]}(p

*i*) is equal to 1 or to 0. Consequently,

*p*

_{1}

*, . . . , p*

*are not roots of*

_{l}*g*

*(t) (if*

_{j}*r < j*

*≤k*and

*s*

_{j}*>*1 we use hypothesis 3); if 1

*≤j≤r, we use hypothesis 2) and the fact thatg*

*(t) has distinct real roots).*

_{j}Therefore, there exist positive real numbers *b** _{ij}*, with

*l*+ 1

*≤i≤s, 1*

*≤j*

*≤k,*such that for each

*j∈ {1, . . . , k},*

*h**j*(t)

*g** _{j}*(t) =

*h*

*j*(t)

*g*

*(t) =*

_{j}*s*
*i*=*l*+1

*m**ij**b**ij*

*t−p** _{i}*
(3.3)

Since*A*= [a*ij*] is a matrix in*S(T*), we deﬁne for each*j∈ {1, . . . , k},x**j*=*|a**x*_{0}*x*_{j}*|*^{2}
and*a*=*a*_{x}_{0}_{x}_{0}. According to (2.1), the characteristic polynomial of*A*may be written
as

*p**A*(t) = (t*−a**x*_{0}*x*_{0})
*k*
*j*=1

*p*_{A}_{[}_{T}_{j}_{]}(t)*−*
*k*
*j*=1

*|a**x*_{0}*x*_{j}*|*^{2}*p*_{A}_{[}_{T}_{j}_{−}_{x}_{j}_{]}(t)
*k*
*u*=1*u**=**j*

*p*_{A}_{[}_{T}_{u}_{]}(t)

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

*g**j*(t)*−*
*k*
*j*=1

*x**j*

*p*_{A}_{[}_{T}_{j}_{−}_{x}_{j}_{]}(t)
*p*_{A}_{[}_{T}_{j}_{]}(t)

*k*
*u*=1

*g**u*(t)

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

*x*_{j}*s*
*i*=*l*+1

*m*_{ij}*b*_{ij}*t−p** _{i}*)

*s*
*i*=1

(t*−p** _{i}*)

^{m}

^{i}= ((t*−a)−*
*s*
*i*=*l*+1

*k*

*j*=1*x*_{j}*m*_{ij}*b*_{ij}*t−p**i* )

*s*
*i*=1

(t*−p** _{i}*)

*s*

*i*=1

(t*−p** _{i}*)

^{m}

^{i}

^{−1}Consequently,

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

*k*

*j*=1*x**j**m**ij**b**ij*

*t−p** _{i}* )

*s*

*i*=1

(t*−p**i*)

and

*g(t) =* *g(t)*

*l*

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

(t*−p**i*)*−*
*s*
*i*=*l*+1

*k*
*j*=1

(x*j**m**ij**b**ij*)
*s*
*u*=*l*+1*,u**=**i*

(t*−p**u*)

So, for each*i∈ {l*+ 1, . . . , s*},g(p**i*) =*−**k*

*j*=1(x*j**m**ij**b**ij*)*s*

*u*=*l*+1*,u**=**i*(p*i**−p**u*). Then

*−**s* *g(p**i*)

*u*=*l*+1*,u**=**i*(p_{i}*−p** _{u}*) =

*k*

*j*=1

(x*j**m**ij**b**ij*).

For each *i∈ {l*+ 1, . . . , s*}* and*j* *∈ {1, . . . , k}, we denote* *x*_{j}*b** _{ij}* by

*y*

*. Since*

_{ij}*b*

_{ij}*, x*

*are positive real numbers, then*

_{j}*y*

*is a positive real number and we have III)(3.1).*

_{ij}Let *j* *∈ {*1, . . . , r*}*. Since *q**j*1*, . . . , q**jv** _{j}* are the common eigenvalues of

*A[T*

*j*] and

*A[T*

_{j}*−x*

*], and*

_{j}*m*

_{A}_{[}

_{T}

_{j}

_{−}

_{x}

_{j}_{]}(q

_{j}_{1}) =

*. . .*=

*m*

_{A}_{[}

_{T}

_{j}

_{−}

_{x}

_{j}_{]}(q

_{jv}*) = 2, by hypothesis 2), we have that*

_{j}*q*

_{j}_{1}

*, . . . , q*

_{jv}*are roots of*

_{j}*h*

*(t) but not of*

_{j}*g*

*(t). Thus, if*

_{j}*p*

*is a root of*

_{i}*g*

*(t) then*

_{j}*p*

*i*

*∈ {q*

*j*1

*, . . . , q*

*jv*

_{j}*}. Therefore, by (3.3), for eachu∈ {1, . . . , v*

*j*

*},*

0 = *x**j**h**j*(q*ju*)
*g**j*(q*ju*) =

*s*
*i*=*l*+1*, m** _{ij}*=1

*m**ij*(x*j**b**ij*)
*q**ju**−p**i* =

*s*
*i*=*l*+1*, m** _{ij}*=1

*m**ij**y**ij*

*q**ju**−p**i**.*

So, we have III)(3.2).

Next, we prove the suﬃciency of the stated conditions. Because of the strict
interlacing between the roots of*g(t) and those of**s*

*i*=*l*+1(t*−p**i*) (hypothesis II) and
because*g(t) is a polynomial of degrees*+ 1*−l >*1, due to Remark 2.2, we conclude
the existence of a real number*a*and positive real numbers*x**l*+1*, . . . , x**s*such that

*s* *g(t)*

*i*=*l*+1(t*−p** _{i}*) = (t

*−a)−*

*s*

*i*=

*l*+1

*x**i*

(t*−p** _{i}*)
i.e.,

*g(t) =*

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

*x**i*

(t*−p** _{i}*)

_{s}

*i*=*l*+1

(t*−p**i*)

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

(t*−p**i*)*−*
*s*
*i*=*l*+1

*x**i*

*s*
*j*=*l*+1*,j**=**i*

(t*−p**j*).

Therefore, if *l*+ 1*≤i≤s,*

*g(p** _{i}*) =

*−x*

_{i}*s*

*j*=

*l*+1

*,j*

*=*

*i*

(p_{i}*−p** _{j}*)

and

*x**i*=*−**s* *g(p**i*)

*j*=*l*+1*j**=**i*(p_{i}*−p** _{j}*)

*.*

Using hypothesis III)(3.1), there exist real positive numbers*y** _{ij}*, with

*l*+ 1

*≤i≤s,*1

*≤j*

*≤k*such that

*x*

*i*=

*k*

*j*=1*m**ij**y**ij*. So,
*g(t) =*

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

*k*

*j*=1*m*_{ij}*y** _{ij}*
(t

*−p*

*i*)

_{s}

*i*=*l*+1

(t*−p**i*)

=

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

*m*_{i}_{1}*y*_{i}_{1}

(t*−p**i*)+*. . .*+
*s*
*i*=*l*+1

*m*_{ik}*y** _{ik}*
(t

*−p*

*i*))

_{s}

*i*=*l*+1

(t*−p**i*).

By hypothesis III) then *g** _{j}*(t) =

*s*

*i*=*l*+1(t*−p** _{i}*)

^{m}*. Notice that, when deg*

^{ij}*g*

*(t)*

_{j}*>*

1, *s*

*i*=*l*+1*m*_{ij}*y*_{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
coeﬃcients of this pfd are positive which means that deg

*h*

*(t) =deg*

_{j}*g*

*(t)−1 and*

_{j}*h*

*(t) has only real roots strict interlacing those of*

_{j}*g*

*j*(t). If deg

*g*

*j*(t) = 1,

*s*

*i*=*l*+1*m*_{ij}*y** _{ij}*
(

*t*

*−*

*p*

*) =*

_{i}*m*_{uj}*y*_{uj}

*g** _{j}*(

*t*) ,

*m*

_{uj}*y*

_{uj}*>*0, for some

*u*

*∈ {l*+ 1, . . . , s

*}. In this case, for convenience we*denote

*m*

_{uj}*y*

*by*

_{uj}*h*

*(t).*

_{j}If 1*≤j≤r, sinceq**j*1*, . . . , q**jv** _{j}* are not roots of

*g*

*j*(t), using III)(3.2) we have that

*q*

_{j}_{1}

*, . . . , q*

_{jv}*are roots of*

_{j}*h*

*(t) but not of*

_{j}*g*

*(t). Remark that the leading coeﬃcient of*

_{j}*h*

*(t) is the positive real number*

_{j}*s*

*i*=*l*+1*m*_{ij}*y** _{ij}*. Let

*h*

*(t) be the monic polynomial such that*

_{j}*h*

*j*(t)(t

*−q*

*j*1)

*. . .*(t

*−q*

*ju*

*) = (*

_{j}*s*

*i*=*l*+1*m**ij**y**ij*)h*j*(t). So,
*g(t) =*

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

(
*s*
*i*=*l*+1

*m*_{ij}*y** _{ij}*)

*h*

*(t)*

_{j}*g*

*j*(t)

^{s}

*i*=*l*+1

(t*−p** _{i}*).

By hypothesis, if 1 *≤* *j* *≤* *r* then *T**j* is a cut branch at *x**i*. Since *g**j*(t) =
*g**j*(t)*v*_{j}

*i*=1(t*−q**ji*), the roots of*h**j*(t) strictly interlace those of*g**j*(t) and*q**j*1*, . . . , q**jv*_{j}

are roots of*h** _{j}*(t), then by Theorem 1.5, there exists a matrix

*A*

*in*

_{j}*S(T*

*j*) such that

*p*

*A*

*(t) =*

_{j}*g*

*j*(t) and

*p*

_{A}

_{j}_{[}

_{T}

_{j}

_{−}

_{x}

_{j}_{]}(t) =

*h*

*j*(t). So, we have 2).

If*r*+ 1*≤j≤k, by Proposition 1.4, there exists a matrixA**j* in *S*(T*j*) such that
*p*_{A}* _{j}*(t) =

*g*

*(t) and*

_{j}*p*

_{A}

_{j}_{[}

_{T}

_{j}

_{−}

_{x}

_{j}_{]}(t) =

*h*

*(t) (recall the convention that*

_{j}*p*

_{A}

_{j}_{[}

_{T}

_{j}

_{−}

_{x}

_{j}_{]}(t) = 1 whenever the vertex set of

*T*

*j*is

*{x*

*j*

*}). Therefore, we have 3) and 1).*

Now deﬁne a matrix*A*= [a*ij*] in *S*(T) in the following way:

*•* *a**x*_{0}*x*_{0} =*a*

*•* *a*_{x}_{0}_{x}* _{j}* =

*a*

_{x}

_{j}

_{x}_{0}=

*s*

*i*=*l*+1*m*_{ij}*y** _{ij}*, for

*j*= 1, . . . , k

*•* *A[T** _{j}*] =

*A*

*, for*

_{j}*j*= 1, . . . , k

*•* the remaining entries of*A* are 0.

According to (2.1), the characteristic polynomial of*A*may be written as

(t*−a**x*_{0}*x*_{0})p_{A}_{[}_{T}_{−}_{x}_{0}_{]}(t)*−*
*k*
*j*=1

*|a**x*_{o}*x*_{j}*|*^{2}*p*_{A}_{[}_{T}_{j}_{−}_{x}_{j}_{]}(t)
*k*
*i*=1*,i**=**j*

*p*_{A}_{[}_{T}_{i}_{]}(t).

Note that*A[T−x*_{0}] =*A[T*_{1}]*⊕. . .⊕A[T**k*] which implies*p*_{A}_{[}_{T}_{−}_{x}_{0}_{]}(t) =*k*

*j*=1*p*_{A}_{[}_{T}_{j}_{]}(t).

Moreover the characteristic polynomial of*A[T**j*] is*g**j*(t) and the characteristic polyno-
mial of*A[T*_{j}*−x** _{j}*] is

*h*

*(t). Consequently, by hypothesis,*

_{j}*k*

*j*=1*g** _{j}*(t) =

*s*

*i*=1(t*−p** _{i}*)

^{m}*and*

^{i}*p** _{A}*(t) = (t

*−a)*

*s*

*i*=1

(t*−p** _{i}*)

^{m}

^{i}*−*

*k*

*j*=1

(
*s*
*i*=*l*+1

*m*_{ij}*y** _{ij}*)

*h*

*(t)*

_{j}*g*

*j*(t)

*s*
*i*=1

(t*−p** _{i}*)

^{m}

^{i}=*g(t)*
*l*
*i*=1

(t*−p** _{i}*)

*s*

*i*=1

(t*−p** _{i}*)

^{m}

^{i}*=*

^{−1}*f*(t)

i.e.,*p**A*(t) =*f*(t).

Under the conditions and following the notation of Theorem 3.1, if*T* is a superstar
and*T**j* is a cut branch at*x**j* of*T*, then*T**j* is a path. So, if*q**ji*is a common eigenvalue
of *A[T** _{j}*] and

*A[T*

_{j}*−x*

*] then*

_{j}*m*

_{A}_{[}

_{T}

_{j}

_{−}

_{x}

_{j}_{]}(q

*) = 2.Therefore, if we suppose that*

_{ji}*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*_{0}*be a central vertex ofT*
*of degreekwhose neighbors arex*_{1}*, . . . , x*_{k}*. LetT*_{i}*be the branch ofT* *atx*_{0}*containing*
*x**i* *ands**i* *be the number of vertices in* *T**i**,i*= 1, . . . , k.

*Let* *T*_{1}*, . . . , T*_{r}*, with* 0 *≤* *r* *≤k, be cut branches at* *x*_{1}*, . . . , x*_{r}*, respectively, and*
*l** _{j}*= min{number of vertices in each connected component of

*T*

_{j}*−x*

_{j}*},j*= 1, . . . , r.

*Let* *g*_{1}(t), . . . , g*k*(t)*be monic polynomials having only distinct real roots, with deg*
*g**i*(t) = *s**i**,* *p*_{1}*, . . . , p**s* *be the distinct roots among polynomials* *g**i*(t) *and* *m**j* *be the*
*multiplicity of root* *p*_{j}*in**k*

*i*=1*g** _{i}*(t).

*Let* *g(t)be a monic polynomial of degrees*+ 1,*p*_{1}*, . . . , p**l* *be the common roots of*
*g(t)and**s*

*i*=1(t*−p** _{i}*)

*and*

*g(t) =* *g(t)*

*l*

*i*=1(t*−p** _{i}*)

*.*