Dear MathTalk,
Following on from http://answers.google.com/answers/threadview?id=550005
(I got a little lost in your theory, and thought it only fair that if
I was going to pester you for clarifications, a new question be
posted)...
I've tightened the question parameters somewhat.
Let M be a square matrix of size n.
Let M be stochastic.
So, M has only non-negative entries, and M has spectral radius 1.
Let V be another square matrix of the same size n, where
all the rows of V are given by the same row vector v of size n.
How would one go about choosing vector v so that the spectral radius
of the matrix given by (M - V) is less than one? Also, if one wanted
(M-V) to be of a particular spectral radius, how would one go about
choosing v? Any examples to illustrate would be much appreciated.
Furthermore, how would the ratio of the eigenvalues change as one
varies v? If one wanted the condition number to be of a particular
value, what would one do? Also, if one wanted the ratio of the
dominant and subdominant eigenvalues to be of a particular value, what
would one do?
Thanking you in anticipation,
Dooogle. |
Request for Question Clarification by
mathtalk-ga
on
15 Aug 2005 07:53 PDT
Hi, dooogle-ga:
Thanks for posting this follow-up Question for me, it is very generous.
I've drafted a treatment of the nonnegative/stochastic case, but will
need to polish a bit. Look for something this evening.
regards, mathtalk-ga
|
Clarification of Question by
dooogle-ga
on
15 Aug 2005 09:52 PDT
No probs.
Looking forward to your thoughts.
Been wondering: you wrote that a v orthogonal to left eigenvector
doesn't reduce the spectral radius and that your hunch was that a v in
the same direction as the left eigenvector would do the trick. What
would happen for v which is neither orthogonal nor in the same
direction?
So, the question is, could one experimentally find an appropriate v
(not knowing the left eigenvector)?
Many thanks for your help,
Dooogle
|
Clarification of Question by
dooogle-ga
on
15 Aug 2005 11:47 PDT
Hoping not to prove a nuisance, but was wondering...
Could you also consider choosing vector v so that the spectral radius
of (|M-V|) is less than one? I ask because (M-V) might have negative
entries for certain v, and a significant potential interest for me is
not just the spectral radius of (M-V), but also the spectral radius of
the |M-V|?
Cheery thanks,
Dooogle
|
Request for Question Clarification by
mathtalk-ga
on
20 Aug 2005 09:53 PDT
Hi, dooogle-ga:
At the point you posted the last Clarification I was set to provide a
set of examples & theory to show how these can be established in with
some generality.
However the Clarification leaves me uncertain about whether this
material is going to provide you much satisfaction. Let me use this
Request for Clarification to talk you through the outlines of the
facts, as nearly as I can determine, with regard to what you would
like.
We have a matrix M, possibly nonnegative and even better stochastic
(row sums equal to 1). IF this stochastic matrix were irreducible,
then there is a very nice theory that says there exists a rank one
matrix V of the desired form (1,...,1)'*v, where v is a "left"
eigenvector of M corresponding to maximal eigenvalue 1, such that M -
V has smaller spectral radius than M.
But there are two things you are keen to have beyond this much.
First, you would like to omit the condition that M is irreducible.
Second, you would like to know that the "absolute value" (entry-wise)
|M - V| has smaller spectral radius. [As the Comments on your other
open Question show, the latter is a stronger condition than rho(M - V)
< 1 = rho(M).]
Example 1.
==========
/ 1 0 \
If M = \ 0 1 / , then no rank one matrix V exists such that rho(M-V) < 1.
Here we have a paradigm of the reducible stochastic matrix, with two
independent eigenvectors for eigenvalue 1. Although a rank one
"update" (adding or subtracting V to the identity matrix M) could
easily increase the spectral radius, it cannot decrease the spectral
radius because M - V will inevitably still have an eigenvalue 1.
What makes the example above "tick" is the existence of two
independent eigenvectors for the common eigenvalue 1 (or more
generally, for whatever the maximal eigenvalue happens to be). There
is a borderline case, which something of the kind you'd like to do is
possible, having geometric multiplicity of the eigenvalue 1 but
algebraic multiplicity = 2. The following illustrates this:
Example 2.
==========
/ 1 1 \ / 1 1 \
Consider the (nonstochastic) matrix M = \ 0 1 / and V = \ 1 1 /.
Then rho(M) = 1 and rho(M-V) = 0.
/ 0 0 \
Indeed here |M - V| is similar to M - V = \-1 0 /, and so it too has a
spectral radius of zero.
However these cases of "deficiency" between the geometric and
algebraic multiplicities are fragile, in the sense of depending on
exact arithmetic, and so far as I can see they are irrelevant to
working with stochastic matrices.
* * * * * * * * * * * * * * * * * * * * * * *
Within the bounds of mathematical reasoning one can provide a proof of
how nice the irreducible stochastic matrix case is (generalizable to
positive matrices), i.e. rank one updates reduce the spectral radius.
One can also show generally, as implied above, that when the geometric
multiplicity of a maximum modulus eigenvalue is greater than 1, no
rank one update will suffice to reduce the spectral radius (much less
reduce the spectral radius of the "absolute value").
There may be some room to explore the situation of an irreducible but
not strictly positive stochastic matrix as far as reducing the
spectral radius of |M-V| as well as M-V. My instinct is that in most
cases it will be possible to do this, but again the hook is the
irreducible (though not outright positiveness) of the original M.
I don't wish to present only "bad news" in response to your very
considerate posting of this Question to my attention, and for other
reasons beyond my immediate control, I will not be able to provide an
Answer here. I'd be happy respond to further discussion either as
Requests for Clarification on my earlier Answer, or if you prefer as
Comments on this thread. You may also wish to indicate that you will
accept an Answer from other Researchers here, and I'll do my part to
communicate your interest if that is the case.
best wishes, mathtalk-ga
|
Clarification of Question by
dooogle-ga
on
22 Aug 2005 03:27 PDT
Dear MathTalk,
Thank you for comments.
I don't mind your considering primarily irreducible M, though it would
be handy if you considered the more general case where M's maximal
eigenvalue 1 has geometric multiplicity 1 - so ruling out the two
independent eigenvectors. If I understand correctly, eigenvalue 1 will
have geometric multiplicity 1 if, using Markov chain terminology,
there is some state in the finite set of states such that all states
communicate with this state - or, eqivalently, there is just one
terminal, strongly-connected subset (by terminal set, I mean a subset
of states from which one cannot exit). This is more general than
irreducibility.
I am very curious about your reasoning for ensuring that rho(M-V) is
less than 1 and would love to see it, though must confess, I'm
primarily concerned with ensuring that rho(|M-V|) is less than 1 -
which I now understand is a trickier question. If you could assist on
this front, I'd be most appreciative.
Many thanks,
Dooogle
(If you think another researcher would be better placed to tackle the
question, then please do offer it up. This said, I 've been very
pleased with your suggestions thusfar. Indeed, I've grown quite
excited to read your thoughts. So, I'm hopeful that you can assist.)
|
Clarification of Question by
dooogle-ga
on
23 Aug 2005 06:01 PDT
Dear MathTalk,
Had a few thought this morning. Not sure if these ramblings help with
ensuring that rho(|M-V|)<1, but here goes.
Lets first assume, as you suggested, that M is irreducible.
First, how do the eigenvalues of M compare with the eigenvalues of (cM
+ (1-c)I) where 0<c<=1 and I is the identity matrix? I ask because the
latter matrix, for suitable choice of c, is also stochastic, and is
aperiodic. And, we have the following, where x is the unique steady
state:
x = cx + (1-c)x
= cMx + (1-c)Ix
= (cM+(1-c)I)x
Secondly, how do the eigenvalues of an irredudible and APERIODIC
matrix M compare with the spectral radius of M^n, for any positive
integer n? I ask because it seems to me that, potentially, we could
run into trouble with the spectral radius of |M-V| when M-V has
negative entries - in which case there may be a divergence between
rho(M-V) and rho(|M-V|). But, if M is irreducible and aperiodic, then,
I believe, that there exists some n such that all entries in M^n are
positive. So, by choosing appropriately small entries in V we could
ensure that there are no potentially troublesome negative entries.
Looking forward to your opinion,
Dooogle
|
Clarification of Question by
dooogle-ga
on
23 Aug 2005 06:55 PDT
Using the stochastic property, and considering the norm bound on
spectral radius given by sum_j^n P_ij, then it would seem that the
spectral radius of M, namely 1, is equal to that of (cM+(1-c)I) and
that of M^n and that of (cM+(1-c)I)^n.
So, if all my scribblings are to be of use (so, for example,
n\(cM+(1-c)I)^n does not have multiple steady states), then I suppose
the question is how does rho((cM+(1-c)I)^n-V) compare with
rho((cM+(1-c)I) -V) and rho(M-V)? And, also, how does
rho(|(cM+(1-c)I)^n-V|) compare with rho(|(cM+(1-c)I) -V|) and
rho(|M-V|)?
Thanking you,
Dooogle
|
Clarification of Question by
dooogle-ga
on
23 Aug 2005 06:57 PDT
Apologies: \n was a typo
|
Clarification of Question by
dooogle-ga
on
29 Aug 2005 02:56 PDT
List price changed
|
Clarification of Question by
dooogle-ga
on
30 Aug 2005 22:21 PDT
Changed once more
|
As I've outlined a couple of simple examples (counterexamples?) above
to show what limitations there are, let me lay out some theory for a
"nice" case.
Suppose the (square) matrix M is diagonalizable, meaning that it has a
basis of eignenvectors. Another way to say this is:
M = P D P?¹ = P D Q
where D is a diagonal matrix consisting of the eigenvalues of M, and P
has columns that are (right) eigenvectors of M in corresponding order.
The notation for matrix inverse may be difficult for some to read
here, so let me refer to the inverse of P as Q. P is invertible by
the assumption that M has a basis of eigenvectors, namely the columns
of P. The rows of Q are equally left eigenvectors of M, in the same
correspondance with the diagonal entries of D as the eigenvalues.
Although it is not immediate from the above representation of M, we
can write M in a "spectral decomposition" of rank one matrices
obtained from the columns of P and rows of Q (the inverse of P). In
particular:
M = SUM d_i·(p_i * q_i)
i
where d_i is the (scalar) i'th diagonal entry of D, p_i the i'th
column of P, and q_i the i'th row of Q.
One way to verify this decomposition is to check that the action of
both sides on a basis, namely the columns of P, is the same. Saying
that the columns of P are the eigenvectors of M that correspond to the
diagonal entries of D amounts to this equality of matrix products:
MP = (PDQ)P = PD(QP) = PD because QP = I
Mp_i = d_i·p_i (i.e. scalar product of column vector)
(Some thought should be given to the fact that multiplying P on the
right by D gives the appropriate multiple of each column of P.)
On the other hand, picking the j'th column to test:
( SUM d_i·(p_i * q_i) ) p_j = SUM (d_i·p_i) * (q_i*p_j)
i i
= d_j·p_j
because q_i*p_j is a 1x1 matrix product (row times column) that is 1
when i=j and zero otherwise. This shows that the expression SUM
d_i·(p_i * q_i) acts on the columns of P in the same manner as M does,
and so (because these columns form a basis, or if you prefer, because
P is invertible) it must equal M.
Now in the case that M is stochastic, we may take the first column of
P to be the right eigenvector (1,...,1)' that corresponds to
eigenvalue 1. If M is irreducible and aperiodic, then as explained in
full detail in a previous Answer:
[Google Answers: Page Rank Definition - Proof of convergence and uniqueness]
http://answers.google.com/answers/threadview?id=379557
the eigenvalue 1 is simple (nullity of M-I is 1) by a classic theorem
of Perron and its extension by Frobenius.
The first term of our "spectral decomposition" is then exactly of the
form you would want:
V = (1,...,1)'*q_1
and subtracting a small multiple c of V from M would have the effect
of diminishing d_1 = 1 by that much. The spectral radius of M-V would
therefore drop from 1 down to whatever eigenvalue gives the second
largest modulus.
You have expressed interest in a variety of topics into which we might
branch at this point. For example, you wonder if the spectral radius,
not of M-V, but of the "absolute value" (entrywise) of M-V will be
reduced. You also ask about the relationship between the spectrum
(eigenvalues) of M and that of:
cM + (1-c)I for 0 ? c ? 1
I believe it is clear that as c varies from 0 to 1 we have a
"homotopy" (continuous path) from the identity matrix I to M, along
with which the eigenvalues may be said to follow "straight lines" from
1 to d_i (all eigenvalues of I being 1, and all the eigenvalues of M
being the d_i's, regardless of ordering).
Since for stochastic M, at least one of the eigenvalues of M is
already 1, and that of maximum modulus, we may say that as many
eigenvalues of M are 1, that many remain "unmoved" by the homotopy.
With respect to the taking of the absolute values of entries in M-V,
I'm not sure what would be more expeditious than to look at some
examples typical of your intended application. It is not clear to me
why you would be interested in only a rank one modification V to M,
since taking these absolute values will in general (unless M is
positive and V small) destroy that rank one "measure" of the update.
It is also unclear why the goal of reducing spectral radius is set,
other than that is makes for an intriguing math problem. If the
spectral radius ought to be reduced by a simple mechanism, one of
thinks first of cM where as above c is a parameter that "shrinks" M,
and thus rho(cM) = c rho(M), for nonnegative c.
It is very thoughtful of you to have increase the list price offered
on this Question, but circumstances do not allow me to post an Answer.
Please accept these notes as a free Comment, and consider perhaps
providing additional notes yourself about the background that might
help another Researcher to address how those absolute values and the
spectral radius enter a larger context for your Question.
regards, mathtalk-ga |
