E-mail: mcatral@uvic.ca

The Kemeny Constant in Finite Homogeneous Ergodic Markov Chains

By Minerva Catral. For a finite homogeneous ergodic Markov chain, the Kemeny constant is an interesting quantity which is defined in terms of the mean first passage times and the stationary distribution vector. A formula in terms of group inverses and inverses of associated M-matrices is presented and perturbation results are derived.

Keywords: Kemeny constant, Finite Markov Chains, Group Inverses

AMS classification: 15

E-mail: eubanks@math.wsu.edu

Generalized Soules Matrices

By Sherod Eubanks. I will discuss a generalization of Soules matrices and its application to the nonnegative inverse eigenvalue problem, eventually nonnegative matrices, and exponentially nonnegative matrices.

Keywords: eventually nonnegative matrices, exponentially nonnegative matrices, inverse eigenvalue problem, Soules matrix

AMS classification: 15A57

E-mail: Thomas.Laffey@ucd.ie

Some constructive techniques in the nonnegative inverse eigenvalue problem

By Thomas Laffey.

Let σ := (λ_{1}, ... , λ_{n}) be a list of complex numbers and let

s_{k} := λ_{1}^{k} + ... + λ_{n}^{k}, k = 1, 2, 3, ...

be the associated Newton power sums. A famous result of Boyle and Handelman states that if all the s_{k} are positive, then there exists a nonnegative integer N such that

σ_{N} := (λ_{1}, ... , λ_{n}, 0, ... , 0), (N zeros)

is the spectrum of a nonnegative (n + N) × (n + N) matrix A. The problem of obtaining a constructive proof of this result with an effective bound on the minimum number N of zeros required has not yet been solved. We present a number of techniques for constructing nonnegative matrices with given nonzero spectrum σ, and use them to obtain new upper bounds on the minimal size of such an A, for various classes of σ. This is joint work with Helena Smigoc.

Keywords: Nonegative Matrices, Nonzero Spectrum

AMS classification: 15

E-mail: jmcdonald@math.wsu.edu

Nonnegative and Eventually Nonnegative Matrices

By Judith McDonald. I will discuss the interplay between the properties of nonnegative and eventually nonnegative matrices, and the role that the inverse eigenvalue problem plays in this relationship.

Keywords: nonnegative, eventually nonnegative, inverse eigenvalue problem

AMS classification: 15A48

E-mail: neumann@math.uconn.edu

On Optimal Condition Numbers For Markov Chains

By Michael Neumann and Nung–Sing Sze. Let T = (t_{i,j}) and T̃ = T −E be arbitrary nonnegative, irreducible, stochastic matrices corresponding to two ergodic Markov chains on n states. A function κ(·) is called a condition number for Markov chains with respect to the (α, β)–norm pair if ∥π − π̃∥_{α} ≤ κ(T)∥E∥_{β}. Various condition numbers, particularly with respect to the (1, ∞) and (∞, ∞) have been suggested in the literature by several authors. They were ranked according to their size by Cho and Meyer in a paper from 2001. In this paper we first of all show that what we call the generalized ergodicity coefficient τ_{p}(∗) = sup_{y^{t}e=0} \frac{∥y^{t}∗∥_{p}}{∥y∥_{1}} , where e is the n–vector of all 1’s, is the smallest of the condition numbers of Markov chains with respect to the (p, ∞)–norm pair. We use this result to identify the smallest condition number of Markov chains among the (∞, ∞) and (1, ∞)–norm pairs. These are, respectively, κ_{3} and κ_{6} in the Cho–Meyer list of 8 condition numbers. Kirkland has studied κ_{3}(T). He has shown that κ_{3}(T) ≥ \frac{n−1}{2n} and he has characterized the properties of transition matrices for which equality holds. We prove again that 2κ_{3}(T) ≤ κ(6) which appears in the Cho–Meyer paper and we characterize the transition matrices T for which κ_{6}(T) = \frac{n−1}{n}. There is only one such matrix: T = (J_{n} − I)/(n − 1). where J_{n} is the n × n matrix of all 1’s. This result demands the development of the cyclic structure of a doubly stochastic matrix with a zero diagonal. Research supported by NSA Grant No. 06G–232

Keywords: Markov chains, stationary distribution, stochastic matrix, group inverses, sensitivity analysis, perturbation theory, condition numbers.

AMS classification: 15A51

E-mail: dmorris@math.wsu.edu

Jordan forms corresponding to nonnegative and eventually nonnegative matrices

By Judith McDonald, DeAnne Morris.

We give necessary and sufficient conditions for a set of Jordan blocks to correspond to the peripheral spectrum of a nonnegative matrix. For each eigenvalue, λ, the λ-level characteristic (with respect to the spectral radius) is defined. The necessary and sufficient conditions include a requirement that the λ-level characteristic is majorized by the λ-height characteristic. An algorithm which determines whether or not a multiset of Jordan blocks corresponds to the peripheral spectrum of a nonnegative matrix will be discussed. We also offer necessary and sufficient conditions for a multiset of Jordan blocks to correspond to the spectrum of an eventually nonnegative matrix.

Keywords: nonnegative

AMS classification:

E-mail: Helena.Smigoc@ucd.ie

An example of constructing a nonnegative matrix with given spectrum

By Thomas J. Laffey, Helena Šmigoc. We say that a list of n complex numbers σ is the nonzero spectrum of a nonnegative matrix, if there exists a nonnegative integer N such that σ together with N zeros added to it is the spectrum of some (n + N) × (n + N) nonnegative matrix. Boyle and Handelman characterized all lists of n complex numbers that can be the nonzero spectrum of a nonnegative matrix. In this talk we will present a constructive proof that τ(t) = (3 + t, 3 − t, −2, −2, −2) is the nonzero spectrum of some nonnegative matrix for every t > 0. We will give a bound for the number of zeros that needs to be added to τ(t) to achieve a nonnegative realization. We will discuss how the method presented could be applied to more general situations.

Keywords: Nonnegative Inverse Eigenvalue Problem, Nonzero Spectrum, Spectral Gap

AMS classification: 15A48