Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 2 down vote favorite

Suppose $A$ is a fixed nonnegative $n\times n$ real matrix (i.e. $A_{ij}\geq0$ for all $i,j$). Then for any arbitrary $n$ positive real numbers $x_1,\ldots,x_n$, we denote: $$F(x_1,\ldots,x_n)=\min_i\frac{1}{x_i}\sum_{j=1}^n x_jA_{ij}$$ Frobenius Theorem tells us that there's always an inequality $$F(x_1,\ldots,x_n)\leq\rho(A)$$ where $\rho(A)$ is the spectral radius of $A$.

Here my question is, what is the maximum of $F(x_1,\ldots,x_n)$ ? Is it just $\rho(A)$ ? Or there's no maximum but a supremum? Thanks a lot for your help.

share|improve this question
I am not sure about what is your question. Because the inequality given by you clearly shows that $F$ is bounded above by spectral radius and by taking $A=\mathbb{I}$ and $x_i=1$ for all $i$ the we can see that the upper bound is achieved. – tessellation Aug 18 at 4:33
@tessellation $A$ is fixed. It's a given matrix. – Wild Chan Aug 18 at 4:40
Now I get it. Is it just a matrix with non-negative integers or it has some special properties like being Orthogonal or Symmetric. – tessellation Aug 18 at 4:44
@WildChan the inequality you've written just gives an upper bound. The bound is not necessarily sharp. – S.B. Aug 18 at 4:45
@tessellation No other properties, just non-negative entries (not necessarily integers). – Wild Chan Aug 18 at 5:14
show 1 more comment

2 Answers

up vote 0 down vote accepted

This might not lead to a full solution you want, but it is worth rewriting the desired optimization as $$\sup_{t\geq 0,\mathbf{x}> \mathbf{0}} t\\ \text{subject to }(\mathbf{A}-t\mathbf{I})\mathbf{x}\geq \mathbf{0}.$$

Update: Let $t_0 = \frac{1}{2}\lambda_{\max}\left(\mathbf{A}+\mathbf{A}^T\right)$. For any $t>t_0$ and all $\mathbf{x}\ne \mathbf{0}$ we have $\mathbf{x}(\mathbf{A}-t\mathbf{I})\mathbf{x}^T<0$. Therefore, $(\mathbf{A}-t\mathbf{I})\mathbf{x}\geq \mathbf{0}$ cannot hold for any $\mathbf{x}>0$. So your optimal $t$ should be less than or equal to $t_0$.

Furthermore, for positive $A$ the maximum is the Perron-Frobenius eigenvalue (see here item #6).

share|improve this answer
Thank you. I also deduced this yesterday. But how to use this result? – Wild Chan Aug 19 at 0:43
@WildChan: Did the update help? – S.B. Aug 20 at 16:35
Sorry that it's been a long time I'm away from the Internet. Your answer really does help, THX. – Wild Chan Sep 3 at 15:21
up vote 0 down vote

You are essentially looking at collatz-weilandt formula. If your matrix $A$ is strictly positive or irreducible, then the maximum is the spectral radius.

share|improve this answer
Thanks. Cna you give me some resources on Collatz-Wielandt formula? Wikipedia doesn't talk a lot about this. What if $A$ isn't irreducible? – Wild Chan Aug 19 at 7:28
I was also looking for the same!!. I am not able to find it now. I will check it and let you know when time permits. Is your $A$ irreducible? – dineshdileep Aug 19 at 7:39
Actually not. This question arose when I was looking up Frobenius Theorem, and the only constraint on $A$ is non-negative. – Wild Chan Aug 19 at 7:48

Your Answer

 
discard

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.