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```
 ```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 n×n 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```
 ```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```