What is the Spectral Radius of a Real Matrix with Non-Negative Elements?

[Scootertaj]

Homework Statement

Let A be a real nxn matrix with non-negative elements satisfying \sum_{j=0}^n a_{ij}=1. Determine the spectral radius of A.

Homework Equations

Denote spectral radius \varsigma(A)=max(\lambda_{i})
We know \varsigma(A) \leq ||A|| for any norm || ||

3. Attempt at the solution
Well, we know:
||A||₁\leqn
||A||₂\leq\sqrt{n}
||A||_inf=1

So, can't all we say is that \varsigma(A) \leq 1 ? Or can we say more?

 

[kai_sikorski]

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.

 

[Scootertaj]

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.

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?

 

[kai_sikorski]

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.

 

[kai_sikorski]

Here's a Hint:

Let A be a real nxn matrix with non-negative elements satisfying \sum_{j=0}^n a_{ij}=1.

so \sum_{j=0}^n 1*a_{ij}=1.

 

[Scootertaj]

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.

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.

 

[kai_sikorski]

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!

 

[kai_sikorski]

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.

 

[Scootertaj]

Hmm, interesting. I suppose that does make sense!
I'm still not sure exactly how to proceed.
From \sum_{j=1}^n 1*a_{ij}=1, 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 \rightarrow (spectral radius) = 1.

I'm sorry I'm being dumb about this.

 

[kai_sikorski]

Well as you said yourself

Denote spectral radius \varsigma(A)=max(\lambda_{i})

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

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.

 

[Scootertaj]

Well as you said yourself



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

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.

Sorry, I must have thought of that wrong: if we find a \lambda&gt;1, then \varsigma(A)&gt;1.
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 \rightarrow vector = all 1's, correct?
Then, Ax =\lambdax \rightarrow \lambda = 1 if x = [1,...,1]

 

[kai_sikorski]

Sorry, I must have wrote that wrong: if we find a \lambda&gt;1, then \varsigma(A)&gt;1.

You proved yourself that \varsigma(A)\le 1 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.

vector = all 1's, correct?

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.

 

[Scootertaj]

You proved yourself that \varsigma(A)\le 1 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.

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.

 

[kai_sikorski]

I think your statement that \| A \|_\infty = 1 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 \infty norm equal to 4/3.

\left(<br /> \begin{array}{cc}<br /> \frac{2}{3} &amp; \frac{2}{3} \\<br /> \frac{2}{3} &amp; \frac{2}{3} \\<br /> \end{array}<br /> \right)

 

[Scootertaj]

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.

 

[kai_sikorski]

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.

 

[Scootertaj]

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.

 

[kai_sikorski]

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.

Your two sentences are completely contradictory. In the first you say you're not using a_{ij}&lt;=1 and in the second you say you do.

 

[Scootertaj]

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.

 

[kai_sikorski]

Yes it's obvious that a_{ij} \le 1! 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.

 

[Scootertaj]

Yes it's obvious that a_{ij} \le 1! 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.

Perhaps I'm confused about induced ∞ norm vs. entry-wise, sorry :/
We haven't discussed entry-wise vs induced.
The point I will be making is that since the row-sum of any given row is 1, then the ∞ norm = 1 --> spectral radius ≤ 1.
From there, show that we can construct an eigenvector that, for each matrix of type (1), we get an eigenvalue = 1.
Thus, 1 = max(eigenvalues) since no eigenvalue can be > 1 by the infinity norm proof.

 

[kai_sikorski]

The point I will be making is that since the row-sum of any given row is 1, then the ∞ norm = 1 --> spectral radius ≤ 1.

You are right. I think maybe I miss understood what your argument was.

 

[Scootertaj]

My bad, I didn't mean to be confusing :/
Thank you so much!