The universal realizability problem of spectra for certain structured matrices
El Problema de la realizabilidad universal de espectro para ciertas matrices estructuradas
Fecha
2019Autor
Soto Montero, Ricardo Lorenzo
UNIVERSIDAD CATOLICA DEL NORTE
Institución
Resumen
A list Λ = {λ1, λ2, …, λn} of complex numbers is said to be realizable, if it is the spectrum of a nonnegative matrix A, and in this case, A is called a realizing matrix, Λ is said diagonalizably realizable (DR) if it is the spectrum of a diagonalizable nonnegative matrix. Λ is said universally realizable (UR) if there exists a nonnegative matrix with spectrum Λ for each possible Jordan canonical form associated with Λ. The problem of characterizing universally realizable lists is called the Nonnegative Universal Realizability Problem (NURP).
The NURP is closely related to the nonnegative inverse eigenvalue problem (NIEP), which is the problem of determining necessary and sufficient conditions for a list of complex numbers Λ = {λ1, λ2, …, λn} to be the spectrum of an n×n entrywise nonnegative matrix. The NIEP is solved only for lists of n ≤ 4 elements. The NURP contains the NIEP, and both problems are equivalent if all elements of the list Λ = {λ1, λ2, …, λn} are distinct.
The objective of this Thesis was to study the NURP for spectra of certain nonnegative structured matrices, that is, matrices that have a particular structure such as symmetric, doubly stochastic, Toeplitz, etc. For that reason, we identified some open topics and / or sub-problems to work on, with a reasonable chance of success.
Our strategy consisted in the use of certain perturbation results, due to Brauer and Rado, which have been used successfully to derive sufficient conditions for both problems, NIEP and NURP, to have a solution. This Thesis has been organized as follows:
In Chapter 2 we present concepts, terminology, and preliminary results for a good understanding of this Thesis.
In Chapter 3 we considered the question of whether diagonalizably realizable implies universally realizable. This is known in a few cases, including n ≤ 4, nonnegative spectra, and Suleimanova spectra. In this Thesis we add some new classes of spectra that are UR. In particular, we study the universal realizability of lists of real numbers with two positive eigenvalues. Our results show that in the even n case, this type of list is always universally realizable. The content of this chapter corresponds essentially to the publication “M. Collao, C. R. Johnson, R. L. Soto, Universal realization of spectra with two positive eigenvalues. Linear Algebra Appl., 545 (2018) 226-239”.
In Chapter 4 we consider the NURP for generalized doubly stochastic matrices, and give new conditions for the existence and construction of a solution matrix. These conditions improve those given in “R. L. Soto, E. Valero, M. Salas, H. Nina, Nonnegative generalized doubly stochastic matrices with prescribed elementary divisors, Electron. J. Linear Algebra 30 (2015) 704-720”. The content of this chapter corresponds essentially to the publication “M. Collao, M. Salas, R. L. Soto, Spectra universally realizable by doubly stochastic matrices, Special Matrices 6 (2018) 301-309”.
In Chapter 5 we emphasize the relevance of a Brauer’s result, and its implication in the NIEP with prescribed diagonal entries. As a consequence, under certain conditions, given a list of complex numbers Λ = {λ1, λ2, …, λn} in the left half plane, that is, Re λi ≤ 0, i = 2,…, n, and given a list of nonnegative real numbers Γ = {γ1, γ2,…, γn}, the remarkably simple condition γ1+γ2+…+γn = λ1+ λ2+ …+ λn is necessary and sufficient for the existence and construction of a realizing matrix with diagonal entries Γ. Conditions for more general lists of complex numbers are also given. The content of this chapter corresponds essentially to the publication “R. L. Soto, A. I. Julio, M. Collao, Brauer’s theorem and nonnegative matrices with prescribed diagonal entries, Electron. J. Linear Algebra 35 (2019) 53-64”.
Finally, in Chapter 6 we showed that companion matrices are similar to Toeplitz ones. As a consequence, a realizable list of complex numbers in the left-half plane is in particular realizable by a Toeplitz matrix. Moreover, we show how to construct symmetric nonnegative block Toeplitz matrices with prescribed spectrum, and we explore the universal realizability of lists, which are symmetrically Toeplitz realizable in blocks. We also propose a Matlab Toeplitz routine to compute a Toeplitz solution matrix. The content of this chapter corresponds essentially to “M. Collao, M. Salas, R. L. Soto, Toeplitz nonnegative realization of spectra via companion matrices, Special Matrices 7 (2019) 230-245”. Una lista de números complejos Λ = {λ1, λ2, …, λn} se dice realizable si es el espectro de una matriz no negativa A, y en tal caso, A es llamada matriz realizadora, Λ se dice diagonalizablemente realizable (DR) si es el espectro de una matriz no negativa diagonalizable. Λ se dice universalmente realizable (UR) si existe una matriz no negativa con espectro Λ para cada posible forma canónica de Jordan asociada con Λ. El problema de caracterizar las listas universalmente realizables es llamado problema de la realizabilidad universal para matrices no negativas (en inglés Nonnegative Universal Realizability Problem, NURP).
El NURP está fuertemente relacionado con el problema inverso de autovalores para matrices no negativas (en inglés Nonnegative Inverse Eigenvalue Problem, NIEP), el cual consiste en determinar condiciones necesarias y suficientes para que una lista de números complejos Λ = {λ1, λ2, …, λn} sea el espectro de una matriz no negativa de orden n. El NIEP está resuelto sólo para listas con n ≤ 4 elementos. El NURP contiene al NIEP, y ambos problemas son equivalentes si los autovalores son todos distintos.
El objetivo de esta Tesis fue estudiar el NURP para espectros de ciertas matrices no negativas estructuradas, es decir, matrices que tienen una particular estructura tal como simétrica, doblemente estocástica, Toeplitz, etc. La razón de escoger este objetivo tiene su origen en la dificultad del problema. Entonces hemos identificado ciertos tópicos y/o subproblemas para trabajar sobre ellos, con una buena probabilidad de éxito.
Nuestra estrategia consistió en el uso de ciertos resultados de perturbación matricial, debidos a Brauer y Rado, los cuales han sido usados con éxito para derivar condiciones suficientes para que ambos problemas, NIEP y NURP, tengan una solución. Esta Tesis ha sido organizada como sigue:
En el Capítulo 2 presentamos conceptos, terminología y resultados preliminares para un buen entendimiento de esta Tesis.
En el Capítulo 3 consideramos la pregunta de si diagonalizablemente realizable implica universalmente realizable. Esto es sabido en algunos casos, incluyendo n ≤ 4, espectros no negativos, y espectros de tipo Suleimanova. En esta Tesis agregamos algunas nuevas clases de espectros que son UR. En particular, estudiamos la realizabilidad universal de listas de números reales con dos autovalores positivos. Nuestros resultados muestran que en el caso n par, este tipo de listas es siempre universalmente realizable. El contenido de este capítulo corresponde esencialmente a la publicación “M. Collao, C. R. Johnson, R. L. Soto, Universal realizability of spectra with two positive eigenvalues. Linear Algebra Appl., 545 (2018) 226-239”.
En el Capítulo 4 consideramos el NURP para matrices doblemente estocásticas generalizadas, y damos nuevas condiciones para la existencia y construcción de una matriz solución. Estas condiciones mejoran las dadas en “R. L. Soto, E. Valero, M. Salas, H. Nina, Nonnegative generalized doubly stochastic matrices with prescribed elementary divisors, Electron. J. Linear Algebra 30 (2015) 704-720”. El contenido de este capítulo corresponde esencialmente a la publicacón “M. Collao, M. Salas, R. L. Soto, Spectra universally realizable by doubly stochastic matrices, Special Matrices 6 (2018) 301-309”.
En el Capítulo 5 enfatizamos la relevancia de un resultado de Brauer, y su implicación en el NIEP con entradas diagonales prescritas. Como consecuencia, bajo ciertas condiciones, dadas una lista de números complejos Λ = {λ1, λ2, …, λn} en el semiplano izquierdo, esto es, Re λi ≤0, i = 2, …, n, y una lista de números reales no negativos Γ = {γ1, γ2, …, γn}, la notablemente simple condición γ1+γ2+…+γn= λ1+ λ2+ …+ λn es necesaria y suficiente para la existencia y construcción de una matriz realizadora con entradas diagonales en Γ. Condiciones para listas más generales de números complejos son también dadas. El contenido de este capítulo corresponde esencialmente a la publicación “R. L. Soto, A. I. Julio, M. Collao, Brauer’s theorem and nonnegative matrices with prescribed diagonal entries, Electron. J. Linear Algebra 35 (2019) 53-64”.
Finalmente, en el Capítulo 6 mostramos que matrices compañeras son similares a matrices Toeplitz. Como consecuencia, una lista realizable de números complejos en el semiplano izquierdo es en particular realizable por una matriz Toeplitz. Además, mostramos cómo construir matrices Toeplitz simétricas en bloques no negativas con espectro prescrito y, exploramos la realizabilidad universal de listas, las cuales son Toeplitz simétricamente realizables en bloques. También proponemos un procedimiento algorítmico, implementado en una rutina computacional Matlab, para computar una matriz solución Toeplitz. El contenido de este capítulo corresponde esencialmente a “M. Collao, M. Salas, R. L. Soto, Toeplitz nonnegative realization of spectra via companion matrices, Special Matrices 7 (2019) 230-245”.