Page 105 - Textos de Matemática Vol. 39

NONNEGATIVE INVERSE EIGENVALUE PROBLEM 95
Clearly not all realizable lists can be realized by a companion matrix, since a nonnegative companion matrix can only have one positive real eigen- value. Less restrictive is the condition that a given list σ = (λ1, λ2, . . . , λn) be realizable by a matrix of the form
(2.1) B = αI + C(g),
where α ≥ 0 and C(g) is a nonnegative companion matrix with trace 0.
For example, if n = 3 and σ is realizable and it is not realizable by a reducible nonnegative matrix, then by the solution of the NIEP for n = 3, σ is
realizable by a matrix of the form (2.1).
More generally, we proved in [15] that if σ = (λ1,λ2,...,λn) is a list of
complex numbers with λ1 > 0 and all other λj having non-positive real part, then σ is realizable if and only if it is realizable by a matrix of the form (2.1). The theorem below gives the solution to the NIEP in this case.
Theorem 2.1 (Laffey, Sˇmigoc [15]). Let λ2, λ3, . . . , λn be complex numbers with real parts less than or equal to zero and let ρ be a positive real number. Then the list σ = (ρ, λ2, . . . , λn) is the spectrum of a nonnegative matrix if and only if the following conditions are satisfied:
(1) The list (ρ, λ2, λ3, . . . , λn) is closed under complex conjugation. n
(2)s1=ρ+ λi≥0. i=2
(3)s2=ρ2+ ni=2λ2i≥0. ( 4 ) s 21 ≤ n s 2 .
For n > 3, there exist realizable lists σ which are realizable by n × n irreducible nonnegative matrices, but not realizable by a nonnegative matrix of the form αI + A, where α ≥ 0, A ≥ 0 and trace(A) = 0.
3. Companion type matrices
Letf(x)=xn +p1xn−1 +...+pn andg(x)=xn +q1xn−1 +...+qn be monic polynomials of degree n. The doubly companion matrix C(f,g) is the matrix
⎡⎢−p1 100...0⎤⎥ ⎢−p2 010...0⎥
C(f,g) = ⎢ . ...
−pn −qn −qn−1 ... −q3 −q2 −q1
... ... ... .
⎥. ⎢⎣−pn−1 0...001⎥⎦
It was introduced by Butcher [5] in the context of Runge-Kutta methods for the solution of PDE. It is easy to check that C(f,g) has characteristic polynomial h(x) = xn + h1xn−1 + . . . + hn, where
g(x)f(x)=x2n +h1x2n−1 +...+hnxn +k(x),