Page 106 - Textos de Matemática Vol. 39

96 THOMAS LAFFEY AND HELENA SˇMIGOC
and where k(x) has degree smaller than n. We call h(x) the truncation of f(x)g(x) at degree n.
It follows from the solution of the NIEP for n = 4 that every realizable list (λ1, λ2, λ3, λ4) can be realized by αI + C(f, g) for some α ≥ 0 and quartics f(x) and g(x) with C(f) ≥ 0 and C(g) ≥ 0. Later we will show that this is not true for n = 5.
Let f be a monic polynomial of degree n, g a monic polynomial of degree m and r(x) = rn−1xn−1 + rn−2xn−2 + ... + r0. Let Nn×m be n × m matrix with all elements equal to zero except its (n, 1) entry, which is equal to 1, and let Mm×n(r) denote the m × n matrix with all but the last row equal to zero and the last row equal to (r0, r1, . . . , rn−1).
In [12] Laffey noticed that a large class of spectra can be realized by the matrices of the following type:
(3.1) A= C(f) Nn×m. Mm×n(r) C(g)
Observe that the matrix A has the characteristic polynomial (3.2) f (x)g(x) − r(x).
Suppose f and g have both degree n and that C(f) and C(g) are nonneg- ative. Let us write f(x)g(x) as before:
g(x)f(x)=x2n +h1x2n−1 +...+hnxn +k(x).
Observethatifwewritek(x)=kn+1xn−1+kn+2xn−2+...+k2n,thenallkj ≥0. Furthermore, if we take r(x) = k(x), then the characteristic polynomial of the matrix A in (3.1) is xnh(x).
The fact that the list τ of roots of h(x) = 0 together with n zeros is a realizable spectrum follows from this, but the fact that τ itself is realizable follows from nonnegativity of C(f, g).
Suppose that σ = (λ1,λ2,...,λn) and f(x) = (x−λ1)(x−λ2)...(x−λn). Boyle and Handelman [4] showed that if all the corresponding power sums sk of σ are positive then there exists a nonnegative integer N such that σ with N zeros appended is realizable. In studying this issue it is more convenient to replace f(x) by
c(t) = (1 − λ1t) . . . (1 − λnt).
If one can find a matrix B(t) whose entries are polynomials in t with nonneg-
ative coefficients and zero constant term, which satisfies c(t) = det(I − B(t))
then one can construct a nonnegative real matrix A with spectrum σ with some N ≥ 0 zeros appended. The matrix A is obtained from B(t) by interpreting the polynomials in graph-theoretic terms. See [1] and [3]. Boyle and Handelman