Press "Enter" to skip to content

Sherman inverse problem for Markov matrices

Let $X$ be an $n\times n$ complex matrix. The eigenvalues $\lambda_1(X), \ldots, \lambda_n(X)$ of $X$ are the roots in $\mathbb{C}$ of its characteristic polynomial. We label them in such a way that

$\displaystyle |\lambda_1(X)|\geq\cdots\geq|\lambda_n(X)|$

with growing phases. The spectral radius of $X$ is $\rho(X):=|\lambda_1(X)|$. The singular values

$\displaystyle s_1(X)\geq\cdots\geq s_n(X)$

of $X$ are the eigenvalues of the positive semi-definite Hermitian matrix $\sqrt{XX^*}$ where $X^*$ is the conjugate-transpose of $X$. We have thus $s_k(X)=\sqrt{\lambda_k(XX^*)}$. The operator norm of $X$ is $\Vert X\Vert_{2\to2}=s_1(X)$. Geometrically, the matrix $X$ maps the unit sphere to an ellipsoid, and the half lenghts of the principal axes of this ellipsoid are exactly the singular values of $X$.

H. Weyl has shown in 1949 that for every $k\in\{1,\ldots,n\}$, we have

$\displaystyle \prod_{i=k}^ns_k(X)\leq\prod_{i=k}^n|\lambda_i(X)| \quad\text{and}\quad \prod_{i=1}^k|\lambda_i(X)|\leq\prod_{i=1}^ks_k(X). $

This expresses a two ways logarithmic majorization. Note that we recover the radius/norm bound $\rho(X)\leq\Vert X\Vert_{2\to2}$. Note also that one may deduce the second Weyl inequalities from the first ones by using them for the inverse of $X+\varepsilon I$ (and conversely).  Note moreover that

$\displaystyle\prod_{i=1}^n|\lambda_i(X)|=\prod_{i=1}^ns_i(X)=|\det(X)|$.

In 1954, A. Horn has shown that any sequences of numbers in $\mathbb{C}$ and $\mathbb{R}_+$ satisfying to the Weyl inequalities and the ordering that we used are actually the eigenvalues and singular values of a complex matrix. This  solves positively a problem formulated by S. Sherman.

We say that $X$ is Markov (or stochastic) if $X$ has entries in $[0,1]$ and each row sums up to $1$. The spectrum of $X$ is then included in the unit disc of the complex plane, contains $1$, and is symmetric with respect to the real axis. With the Weyl-Sherman-Horn inverse problem in mind, one can ask about the possible set of singular values for a Markov matrix with prescribed  eigenvalues. One may also reverse the question. One has to take into account the additional symmetries due to the periods. Actually, instead of the singular values of $M$, it is maybe more natural, from a Markovian point of view, to consider the spectrum of $\sqrt{MM^{*\mu}}$ where $M^{*\mu}$ is the adjoint of $M$ for $\ell^2(\mu)$ where $\mu$ is the invariant measure of $M$ (when $M$ is irreducible). This remark leads to many other questions.

The content of this post is inspired from informal discussions with Laurent Miclo during the EVOL workshop held in Hammamet in May 2010.

    Leave a Reply

    Your email address will not be published.

    This site uses Akismet to reduce spam. Learn how your comment data is processed.

    Syntax · Style · .