1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Spectral Radius: Matrix

  1. Feb 18, 2012 #1
    1. The problem statement, all variables and given/known data


    Let A be a real nxn matrix with non-negative elements satisfying [itex]\sum_{j=0}^n a_{ij}=1.[/itex] Determine the spectral radius of A.
    2. Relevant equations
    Denote spectral radius [itex]\varsigma(A)=max(\lambda_{i})[/itex]
    We know [itex]\varsigma(A) \leq ||A||[/itex] for any norm || ||

    3. Attempt at the solution
    Well, we know:
    ||A||1[itex]\leq[/itex]n
    ||A||2[itex]\leq[/itex][itex]\sqrt{n}[/itex]
    ||A||inf=1

    So, can't all we say is that [itex]\varsigma(A) \leq 1[/itex] ? Or can we say more?
     
  2. jcsd
  3. Feb 18, 2012 #2

    kai_sikorski

    User Avatar
    Gold Member

    There is a really simple column vector that you can easily show is an eigenvector with eigenvalue 1; which would give you a lower bound.

    I'm not familiar with the result you use in (3), but if it is true than the upper and lower bound together would give you a value of 1 for the spectral radius.
     
  4. Feb 18, 2012 #3
    Which result are you unsure of?
    From class, I know that:

    Spectral radius < any norm of A
    Spectral radius = max(eigenvalues)



    So, we have an upperbound for A: 1.
    Are you saying that we can construct A such that A has a column vector which is just [1,0,...,0] --> eigenvalue=1 --> (spectral radius)>=1 ?
    But how do we know that that 1 is a lowerbound too?
     
  5. Feb 18, 2012 #4

    kai_sikorski

    User Avatar
    Gold Member

    The result I'm not familiar with is the norm result. I'm not saying I don't believe you that it's true, I'm just not familiar with it.

    What I'm saying is that there is one fixed vector, call it v, that will be an eigenvector for all matrices of the type described in (1) and it's eigenvalue will always be 1 for all such matrices.
     
  6. Feb 18, 2012 #5

    kai_sikorski

    User Avatar
    Gold Member

    Here's a Hint:

    so [itex]\sum_{j=0}^n 1*a_{ij}=1.[/itex]
     
  7. Feb 18, 2012 #6
    Hmm, I'll have to think about that and the hint.
    In the meantime: http://en.wikipedia.org/wiki/Matrix_norm
    Scroll down to where it says "Any induced norm satisfies the inequality."
    There is some justification. It seems very important when you want to look at convergence and successive powers of a matrix.
     
  8. Feb 18, 2012 #7

    kai_sikorski

    User Avatar
    Gold Member

    Oh okay, I can see why it would be true for induced norms. Come to think of it I probably knew that result at some point but have forgotten. Good to know. Thanks!
     
  9. Feb 18, 2012 #8

    kai_sikorski

    User Avatar
    Gold Member

    By the way, these types of matrices are often called stochastic matrices, because of their use as probability transition matrices for stochastic processes. The spectral properties are really important there, in particular the second largest eigenvalue determines how fast the stochastic process goes to its stationary distribution and the fact that this eigenvalue must be less than 1 is crucial.
     
  10. Feb 18, 2012 #9
    Hmm, interesting. I suppose that does make sense!
    I'm still not sure exactly how to proceed.
    From [itex]\sum_{j=1}^n 1*a_{ij}=1,[/itex] we know that 1 * (sum of any row) = 1.
    Even if we find such a eigenvector that gives us an eigenvalue of 1 for all matrices, how does that help us?
    After all, what's stopping us from finding an eigenvector that gives us an eigenvalue < 1. I just don't see how that gives us (spectral radius) ≥ 1 [itex]\rightarrow[/itex] (spectral radius) = 1.

    I'm sorry I'm being dumb about this.
     
  11. Feb 18, 2012 #10

    kai_sikorski

    User Avatar
    Gold Member

    Well as you said yourself

    So it doesn't matter if there is another eigenvalue smaller than 1, we would still have [itex]\varsigma(A)=1[/itex].

    Okay here's another hint for how to find the eigenvector. How would you write down the fact that rows of A sum to 1 using matrices and vectors.
     
  12. Feb 18, 2012 #11
    Sorry, I must have thought of that wrong: if we find a [itex]\lambda>1[/itex], then [itex]\varsigma(A)>1[/itex].
    But, idk how you would find such an eigenvalue lol so that doesn't make sense.
    Hm.. well if a row sums to 1, then (Matrix Row)*(vector) = 1 [itex]\rightarrow[/itex] vector = all 1's, correct?
    Then, Ax =[itex]\lambda[/itex]x [itex]\rightarrow[/itex] [itex]\lambda[/itex] = 1 if x = [1,...,1]
     
  13. Feb 18, 2012 #12

    kai_sikorski

    User Avatar
    Gold Member

    You proved yourself that [itex]\varsigma(A)\le 1[/itex] using your norm argument. So your argument bounds it from above and the fact that there is an eigenvalue equal to 1 makes that a tight bound.

    Yes exactly!

    One thing that I would be careful about, is that I think that the spectral radius is only a bound for induced norms, not entry-wise norms (unless I'm mistaken). It seems to me like you were basing your bounds on the norms in your original post part 3 under the assumption that you're dealing with entry-wise norms.
     
  14. Feb 18, 2012 #13
    Ya sorry, I ran 10 miles a little bit ago, I'm a little weary haha.
    As for induced: I think you're right it only works for induced norms. But, the idea should still work here since ||.||inf is an induced norm and that's the norm we care about for this problem.
     
  15. Feb 18, 2012 #14

    kai_sikorski

    User Avatar
    Gold Member

    I think your statement that [itex] \| A \|_\infty = 1 [/itex] is true. But it doesn't simply follow from the fact that the largest entry of A is less than or equal to 1. For example this simple matrix has all entries less than 1, but induced [itex]\infty[/itex] norm equal to 4/3.

    [tex] \left(
    \begin{array}{cc}
    \frac{2}{3} & \frac{2}{3} \\
    \frac{2}{3} & \frac{2}{3} \\
    \end{array}
    \right) [/tex]
     
  16. Feb 18, 2012 #15
    Yes, but that matrix doesn't fit the classification given to us. The sum of any given row must be = 1 by the problem statement.
     
  17. Feb 18, 2012 #16

    kai_sikorski

    User Avatar
    Gold Member

    Yes, I was just using it to illustrate that if you're writing a proof of the fact that A must have spectral radius less than one then it can not only rely on the fact that all it's entries are less than 1. It must rely on the properties of A more subtly.
     
  18. Feb 18, 2012 #17
    I wasn't using the property that all entries are less than 1 really. I was using the fact that the row sum = 1 and non-negative entries must thus require that all entries are <=1 in this case.
     
  19. Feb 18, 2012 #18

    kai_sikorski

    User Avatar
    Gold Member

    :confused:

    Your two sentences are completely contradictory. In the first you say you're not using [itex]a_{ij}<=1[/itex] and in the second you say you do.
     
  20. Feb 18, 2012 #19
    Sorry, I should clarify: I don't use the fact that each element is <= 1, but it's obvious from the row sum + non-negative requirements.
     
  21. Feb 18, 2012 #20

    kai_sikorski

    User Avatar
    Gold Member

    Yes it's obvious that [itex] a_{ij} \le 1 [/itex]! I'm not arguing against that! But it's not obvious that this implies that the induced ∞ norm is ≤ 1. It implies the entry wise ∞ norm is ≤1, but that's a different thing. Sorry I don't know how else to explain this to you, maybe someone else can try.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook