MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $\Sigma$ be a finite non-empty set of symbols (i.e. an alphabet). Fix $\pi, \eta\in\mathbb{R}^{1\times m}$ and for every $\sigma\in\Sigma $ fix $A(\sigma)\in\mathbb{R}^{m\times m}$. We also require that for every $1 \leq i,j\leq m$ $\pi_i, \eta_i, (A(\sigma))_{i,j} \geq 0$ but $\pi,\eta,A(\sigma)\neq 0$.

If $w:=w_1\cdots w_n\in\Sigma^*$ let $A(w) := \prod_{i=1}^{n} A(w_i)$. Suppose that there exists a real $K$ such that for every $w\in\Sigma^*$ one has $|\pi A(w)\eta^{t} |\leq K$.

Is it true that this imply the existence of $K'$ such that for every $w\in\Sigma^*$ $||\pi A(w)||\leq K'$ for some $K'$? If not, any counterexample?

Here $||\cdot||$ denotes the usual $\ell_2$ norm of a real vector.

share|cite|improve this question
Is $\eta$ fixed? If $\eta$ is 0 you can't say anything. If $\eta| is strictly positive things look better. – Benjamin Steinberg Jul 26 '11 at 21:40
Thank you for replying. We fix $\eta, \pi$ and $A(\sigma)$ but we rule out the case $\eta=0$. I've edited the question. Thank you. – Carlo Jul 26 '11 at 21:59
I also guess there should be a counter-example with some η not strictly-positive and that the theorem might be true adding η>0 to hypothesis. Any hint or ref on this will be of great help. Thank you. – Carlo Jul 26 '11 at 22:12
As stated nothing works. Just choose matrices whose rows are orthogonal to $\eta$. Maybe you might want strictly positive matrices and vectors? – Benjamin Steinberg Jul 27 '11 at 0:27
up vote 1 down vote accepted

Here is a counterexample. Suppose that $A(\sigma)$ is upper triangular with a $1$ in upper left position, and that $\eta=[1\ 0\ 0\ \cdots\ 0]$ and $\pi=[1\ 1\ 1\cdots\ 1]$. Note that $A(w)$ is also upper triangular with a $1$ at upper left, and that $A(w)\eta^t=[1\ 0\ 0\ \cdots\ 0]^t$ and so $\pi A(w)\eta^t=1$ for all $w$. But meanwhile, it is easy to arrange that $\pi A(w)$ can become unboundedly large by taking $w$ large.

For a concrete example, use $A(\sigma)=[1\ 1;\ 0\ 1]$ and $\eta=[1\ 0]$ and $\pi=[1\ 1]$.

share|cite|improve this answer
This is an answer to the original question; it doesn't answer the strictly-positive version of the question. (So it would be fine, Recursive, to de-accept it, in the hope of getting an answer to the edited question.) – Joel David Hamkins Jul 27 '11 at 15:31
Ok I've re-edited, now the statement should be ok with my intended interpretation of the problem. Your counterexample answer my question. Thank you! – Carlo Jul 27 '11 at 16:57

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.