Google Answers Logo
View Question
 
Q: Eigenvalues of Page and Brin's "Naive" Webgraph Matrix ( Answered,   1 Comment )
Question  
Subject: Eigenvalues of Page and Brin's "Naive" Webgraph Matrix
Category: Science > Math
Asked by: dvd03-ga
List Price: $20.00
Posted: 06 Aug 2004 02:59 PDT
Expires: 05 Sep 2004 02:59 PDT
Question ID: 384263
Consider the nxn square matrix, M, defined as
 	Mij = 0 or c where 0 < c < 1.

Can we make any claims about the spectral radius of M - in particular,
that the spectral radius is strictly less than 1?

Clarification of Question by dvd03-ga on 06 Aug 2004 03:06 PDT
Apologies, let me redefine M.

Let A be a square matrix such that
	Aij 	= 	0 or 1/n where n is the number of non-zero entries in row i -
			i.e. if a row has a non-zero entry, then the sum of this row's
 			entries is one.

Let M = c*A where c is a real such that 0 < c < 1.

Now, what can be said about M's spectral radius?

Many thanks,

dvd

Clarification of Question by dvd03-ga on 06 Aug 2004 07:30 PDT
Dear mathtalk,
 	What is the effect on spectral radius of rows possbly being entirely
zero - the matrix, I believe, being accordingly not a proper
transition matrix?
	Regards

	dvd

Request for Question Clarification by mathtalk-ga on 06 Aug 2004 07:42 PDT
Let A be a matrix whose rows each have 1-norm less than or equal to 1.

Using the triangle inequality, show that for any row vector x:

  ||xA|| =<  ||x||

where the 1-norm is indicated by the ||.|| notation.

Conclude from this that the spectral radius of A is less than or equal to 1.

regards, mathtalk-ga

Clarification of Question by dvd03-ga on 09 Aug 2004 02:50 PDT
OK, and
 	if M is some square matrix, and R is s*M for some scalar s, then
		i) how do the eigenvalues of R compare with those of M; and
		ii) how do the corresponding eigenvectors of R compare with those of s?

Regards

Clarification of Question by dvd03-ga on 09 Aug 2004 02:51 PDT
PS in (ii) I meant M, not s.

Thank you
Answer  
Subject: Re: Eigenvalues of Page and Brin's "Naive" Webgraph Matrix
Answered By: mathtalk-ga on 15 Aug 2004 12:07 PDT
 
Hi, dvd03-ga:

The "spectral radius" of a (square) matrix is the "maximum modulus"
(largest absolute value) of its eigenvalues.  This odd name is due to
terming the set of eigenvalues the "spectrum" of the matrix.

Because an nn matrix has at most n eigenvalues, there is no ambiguity
of speaking of the maximum of the absolute values of these
"characteristic roots", but there may distinct eigenvalues with the
same modulus or an eigenvalue that has multiplicity greater than 1
(either algebraic multiplicity, which counts the number of equal roots
in the characteristic polynomial, or geometric multiplicity, which
counts the number of linearly independent eigenvectors that correspond
to the eigenvalue).

Every characteristic root has at least one (nonzero) eigenvector, so
there is no distinction between "algebraic" and "geometric"
eigenvalues, only between the two kinds of multiplicity.

If we have a scalar multiple of a square matrix, say M = c*A, then the
relationship between their spectrums (eigenvalues) is just what we'd
expect and hope for.  Assuming c is nonzero:

  d is an eigenvalue of A <==> c*d is an eigenvalue of M

For this reason we are assured that the spectral radius of M is |c|
times the spectral radius of A, and this true without assuming
nonnegativity of A or any other properties of a probabilty transition
matrix.

If we know some information about the 1-norms of the rows of A (as for
example we do in the case of probability transition matrix), then we
may be able to give a bound on the spectral radius of A, and thus of
M.

For example, if the largest 1-norm (sum of absolute values) of the
rows of A is C, then we have this estimate on how right-multiplication
of rows by A affects the 1-norm.  For any compatible row x:

  xA = x(1) * A(1,-) + x(2) * A(2,-) + . . . _ x(n) * A(n,-)

Therefore by the triangle inequality for the 1-norm ||.|| we have:

  ||xA|| =< |x(1)|*||A(1,-)|| + ... + |x(n)|*||A(n,-)||

         =< C * ( |x(1)| + |x(2)| + ... + |x(n)| )

         =  C * ||x||

Therefore the absolute value of any eigenvalue d of A would be less
than or equal to C, as we see by this "calculation":

   xA  =  dx

   ||dx|| = ||xA|| =< C * ||x||

   |d| * ||x||  =<  C * ||x||

and dividing by ||x|| which is nonzero:

   |d| =< C

Therefore the spectral radius of A, which is the maximum of |d|, will
be bounded by C, which is the maximum 1-norm of a row of A.  Similarly
one can get an estimate of the spectral radius involving the maximum
1-norm of a column of A (by considering eigenvectors from the "other
side" of A), and the estimates could be based on the operator norm of
A induced by other vector norms (besides the 1-norm as we used here).

A more "delicate" method for estimating the locations of eigenvalues
and hence the spectral radius is given by a result known as
Gershgorin's Disk (or Circles) Theorem:

[Gershgorin's Circle Theorem - PlanetMath]
http://planetmath.org/encyclopedia/GershgorinsCircleTheorem.html

The idea here is to use a bounding circle centered on a diagonal
element of A and the radius of which is the 1-norm of the remaining
off-diagonal entries.  The union of these n-disks (on for each
diagonal entry) contains all the eigenvalues of A.

regards, mathtalk-ga
Comments  
Subject: Re: Eigenvalues of Page and Brin's "Naive" Webgraph Matrix
From: mathtalk-ga on 06 Aug 2004 06:25 PDT
 
The spectral radius is the maximum absolute value of an eigenvalue (or
root of the characteristic equation) for a matrix.

Thus if M = c*A, then spectral radius of M is |c| times the spectral radius of A.

The spectral radius of a probability transition matrix is always 1.

regards, mathtalk-ga

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  


Google Home - Answers FAQ - Terms of Service - Privacy Policy