In what

way is a formally smooth algebra a _machine_ producing families of

manifolds? Consider the special case of the path algebra $\mathbb{C} Q$ of a

quiver and recall that an $n$-dimensional representation is an algebra

map $\mathbb{C} Q \rightarrow^{\phi} M_n(\mathbb{C})$ or, equivalently, an

$n$-dimensional left $\mathbb{C} Q$-module $\mathbb{C}^n_{\phi}$ with the action

determined by the rule $a.v = \phi(a) v~\forall v \in \mathbb{C}^n_{\phi},

\forall a \in \mathbb{C} Q$ If the $e_i~1 \leq i \leq k$ are the idempotents

in $\mathbb{C} Q$ corresponding to the vertices (see this [post][1]) then we get

a direct sum decomposition $\mathbb{C}^n_{\phi} = \phi(e_1)\mathbb{C}^n_{\phi} \oplus

\ldots \oplus \phi(e_k)\mathbb{C}^n_{\phi}$ and so every $n$-dimensional

representation does determine a _dimension vector_ $\alpha =

(a_1,\ldots,a_k)~\text{with}~a_i = dim_{\mathbb{C}} V_i = dim_{\mathbb{C}}

\phi(e_i)\mathbb{C}^n_{\phi}$ with $ | \alpha | = \sum_i a_i = n$. Further,

for every arrow $\xymatrix{\vtx{e_i} \ar[rr]^a & &

\vtx{e_j}} $ we have (because $e_j.a.e_i = a$ that $\phi(a)$

defines a linear map $\phi(a)~:~V_i \rightarrow V_j$ (that was the

whole point of writing paths in the quiver from right to left so that a

representation is determined by its _vertex spaces_ $V_i$ and as many

linear maps between them as there are arrows). Fixing vectorspace bases

in the vertex-spaces one observes that the space of all

$\alpha$-dimensional representations of the quiver is just an affine

space $\mathbf{rep}_{\alpha}~Q = \oplus_a~M_{a_j \times a_i}(\mathbb{C})$ and

base-change in the vertex-spaces does determine the action of the

_base-change group_ $GL(\alpha) = GL_{a_1} \times \ldots \times

GL_{a_k}$ on this space. Finally, as all this started out with fixing

a bases in $\mathbb{C}^n_{\phi}$ we get the affine variety of all

$n$-dimensional representations by bringing in the base-change

$GL_n$-action (by conjugation) and have $\mathbf{rep}_n~\mathbb{C} Q =

\bigsqcup_{| \alpha | = n} GL_n \times^{GL(\alpha)}

\mathbf{rep}_{\alpha}~Q$ and in this decomposition the connected

components are no longer just affine spaces with a groupaction but

essentially equal to them as there is a natural one-to-one

correspondence between $GL_n$-orbits in the fiber-bundle $GL_n

\times^{GL(\alpha)} \mathbf{rep}_{\alpha}~Q$ and $GL(\alpha)$-orbits in the

affine space $\mathbf{rep}_{\alpha}~Q$. In our main example

$\xymatrix{\vtx{e} \ar@/^/[rr]^a & & \vtx{f} \ar@(u,ur)^x

\ar@(d,dr)_y \ar@/^/[ll]^b} $ an $n$-dimensional representation

determines vertex-spaces $V = \phi(e) \mathbb{C}^n_{\phi}$ and $W = \phi(f)

\mathbb{C}^n_{\phi}$ of dimensions $p,q~\text{with}~p+q = n$. The arrows

determine linear maps between these spaces $\xymatrix{V

\ar@/^/[rr]^{\phi(a)} & & W \ar@(u,ur)^{\phi(x)} \ar@(d,dr)_{\phi(y)}

\ar@/^/[ll]^{\phi(b)}} $ and if we fix a set of bases in these two

vertex-spaces, we can represent these maps by matrices

$\xymatrix{\mathbb{C}^p \ar@/^/[rr]^{A} & & \mathbb{C}^q \ar@(u,ur)^{X}

\ar@(d,dr)_{Y} \ar@/^/[ll]^{B}} $ which can be considered as block

$n \times n$ matrices $a \mapsto \begin{bmatrix} 0 & 0 \\ A & 0

\end{bmatrix}~b \mapsto \begin{bmatrix} 0 & B \\ 0 & 0 \end{bmatrix}$

$x \mapsto \begin{bmatrix} 0 & 0 \\ 0 & X \end{bmatrix}~y \mapsto

\begin{bmatrix} 0 & 0 \\ 0 & Y \end{bmatrix}$ The basechange group

$GL(\alpha) = GL_p \times GL_q$ is the diagonal subgroup of $GL_n$

$GL(\alpha) = \begin{bmatrix} GL_p & 0 \\ 0 & GL_q \end{bmatrix}$ and

acts on the representation space $\mathbf{rep}_{\alpha}~Q = M_{q \times

p}(\mathbb{C}) \oplus M_{p \times q}(\mathbb{C}) \oplus M_q(\mathbb{C}) \oplus M_q(\mathbb{C})$

(embedded as block-matrices in $M_n(\mathbb{C})^{\oplus 4}$ as above) by

simultaneous conjugation. More generally, if $A$ is a formally smooth

algebra, then all its representation varieties $\mathbf{rep}_n~A$ are

affine smooth varieties equipped with a $GL_n$-action. This follows more

or less immediately from the definition and [Grothendieck][2]\’s

characterization of commutative regular algebras. For the record, an

algebra $A$ is said to be _formally smooth_ if for every algebra map $A

\rightarrow B/I$ with $I$ a nilpotent ideal of $B$ there exists a lift

$A \rightarrow B$. The path algebra of a quiver is formally smooth

because for every map $\phi~:~\mathbb{C} Q \rightarrow B/I$ the images of the

vertex-idempotents form an orthogonal set of idempotents which is known

to lift modulo nilpotent ideals and call this lift $\psi$. But then also

every arrow lifts as we can send it to an arbitrary element of

$\psi(e_j)\pi^{-1}(\phi(a))\psi(e_i)$. In case $A$ is commutative and

$B$ is allowed to run over all commutative algebras, then by

Grothendieck\’s criterium $A$ is a commutative regular algebra. This

also clarifies why so few commutative regular algebras are formally

smooth : being formally smooth is a vastly more restrictive property as

the lifting property extends to all algebras $B$ and whenever the

dimension of the commutative variety is at least two one can think of

maps from its coordinate ring to the commutative quotient of a

non-commutative ring by a nilpotent ideal which do not lift (for an

example, see for example [this preprint][3]). The aim of

non-commutative algebraic geometry is to study _families_ of manifolds

$\mathbf{rep}_n~A$ associated to the formally-smooth algebra $A$. [1]:

http://www.matrix.ua.ac.be/wp-trackback.php/10 [2]:

http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Grothendieck.

html [3]: http://www.arxiv.org/abs/math.AG/9904171

# Tag: arxiv

The previous post can be found [here][1].

Pierre Gabriel invented a lot of new notation (see his book [Representations of finite dimensional algebras][2] for a rather extreme case) and is responsible for calling a directed graph a quiver. For example,

$\xymatrix{\vtx{} \ar@/^/[rr] & & \vtx{} \ar@(u,ur) \ar@(d,dr) \ar@/^/[ll]} $

is a quiver. Note than it is allowed to have multiple arrows between vertices, as well as loops in vertices. For us it will be important that a quiver $Q $ depicts how to compute in a certain non-commutative algebra : the path algebra $\mathbb{C} Q $. If the quiver has $k $ vertices and $l $ arrows (including loops) then the path algebra $\mathbb{C} Q $ is a subalgebra of the full $k \times k $ matrix-algebra over the free algebra in $l $ non-commuting variables

$\mathbb{C} Q \subset M_k(\mathbb{C} \langle x_1,\ldots,x_l \rangle) $

Under this map, a vertex $v_i $ is mapped to the basis $i $-th diagonal matrix-idempotent and an arrow

$\xymatrix{\vtx{v_i} \ar[rr]^{x_a} & & \vtx{v_j}} $

is mapped to the matrix having all its entries zero except the $(j,i) $-entry which is equal to $x_a $. That is, in our main example

$\xymatrix{\vtx{e} \ar@/^/[rr]^a & & \vtx{f} \ar@(u,ur)^x \ar@(d,dr)_y \ar@/^/[ll]^b} $

the corresponding path algebra is the subalgebra of $M_2(\mathbb{C} \langle a,b,x,y \rangle) $ generated by the matrices

$e \mapsto \begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix} $ $ f \mapsto \begin{bmatrix} 0 & 0 \\ 0 & 1 \end{bmatrix} $

$a \mapsto \begin{bmatrix} 0 & 0 \\ a & 0 \end{bmatrix} $ $b \mapsto \begin{bmatrix} 0 & b \\ 0 & 0 \end{bmatrix} $

$x \mapsto \begin{bmatrix} 0 & 0 \\ 0 & x \end{bmatrix} $ $y \mapsto \begin{bmatrix} 0 & 0 \\ 0 & y \end{bmatrix} $

The name \’path algebra\’ comes from the fact that the subspace of $\mathbb{C} Q $ at the $(j,i) $-place is the vectorspace spanned by all paths in the quiver starting at vertex $v_i $ and ending in vertex $v_j $. For an easier and concrete example of a path algebra. consider the quiver

$\xymatrix{\vtx{e} \ar[rr]^a & & \vtx{f} \ar@(ur,dr)^x} $

and verify that in this case, the path algebra is just

$\mathbb{C} Q = \begin{bmatrix} \mathbb{C} & 0 \\ \mathbb{C}[x]a & \mathbb{C}[x] \end{bmatrix} $

Observe that we write and read paths in the quiver from right to left. The reason for this strange convention is that later we will be interested in left-modules rather than right-modules. Right-minder people can go for the more natural left to right convention for writing paths.

Why are path algebras of quivers of interest in non-commutative geometry? Well, to begin they are examples of _formally smooth algebras_ (some say _quasi-free algebras_, I just call them _qurves_). These algebras were introduced and studied by Joachim Cuntz and Daniel Quillen and they are precisely the algebras allowing a good theory of non-commutative differential forms.

So you should think of formally smooth algebras as being non-commutative manifolds and under this analogy path algebras of quivers correspond to _affine spaces_. That is, one expects path algebras of quivers to turn up in two instances : (1) given a non-commutative manifold (aka formally smooth algebra) it must be \’embedded\’ in some non-commutative affine space (aka path algebra of a quiver) and (2) given a non-commutative manifold, the \’tangent spaces\’ should be determined by path algebras of quivers.

The first fact is easy enough to prove, every affine $\mathbb{C} $-algebra is an epimorphic image of a free algebra in say $l $ generators, which is just the path algebra of the _bouquet quiver_ having $l $ loops

$\xymatrix{\vtx{} \ar@(dl,l)^{x_1} \ar@(l,ul)^{x_2} \ar@(ur,r)^{x_i} \ar@(r,dr)^{x_l}} $

The second statement requires more work. For a first attempt to clarify this you can consult my preprint [Qurves and quivers][3] but I\’ll come back to this in another post. For now, just take my word for it : if formally smooth algebras are the non-commutative analogon of manifolds then path algebras of quivers are the non-commutative version of affine spaces!

[1]: http://www.neverendingbooks.org/index.php?p=71

[2]: http://www.booxtra.de/verteiler.asp?site=artikel.asp&wea=1070000&sh=homehome&artikelnummer=000000689724

[3]: http://www.arxiv.org/abs/math.RA/0406618

Today Travis Schedler posted a nice paper on the arXiv

“A Hopf algebra quantizing a necklace Lie algebra

canonically associated to a quiver”. I heard the first time about

necklace Lie algebras from Jacques Alev who had heard a talk by Kirillov

who constructed an infinite dimensional Lie algebra on the monomials in

two non-commuting variables X and Y (upto cyclic permutation of the

word, whence ‘necklace’). Later I learned that this Lie algebra was

defined by Maxim Kontsevich for the free algebra in an even number of

variables in his “Formal (non)commutative symplectic geometry” paper

(published in the Gelfand seminar proceedings 1993). Later I extended

this construction together with Raf Bocklandt in “Necklace Lie algebras and non-commutative symplectic

geometry” (see also Victor Ginzburg’s paper “Non-commutative symplectic geometry, quiver

varieties and operads”. Here, the necklace Lie algebra appears from

(relative) non-commutative differential forms on a symmetric quiver and

its main purpose is to define invariant symplectic flows on quotient

varieties of representations of the quiver.

Travis Schedler

extends this construction in two important ways. First, he shows that

the Lie-algebra is really a Lie-bialgebra hence there is some sort of

group-like object acting on all the representation varieties. Even more

impoprtant, he is able to define a quantization of this structure

defining a Hopf algebra. In this quantization, necklaces play a role

similar to that of (projected) flat links in the plane whereas their

quantization (necklaces with a height) are similar to genuine links in

3-space.

Sadly, at the moment there is no known natural

representations for this Hopf algebra playing a similar role to the

quotient varieties of quiver-varieties in the case of the necklace Lie

bialgebra.

Can

it be that one forgets an entire proof because the result doesn’t seem

important or relevant at the time? It seems the only logical explanation

for what happened last week. Raf Bocklandt asked me whether a

classification was known of all group algebras **l G** which are

noncommutative manifolds (that is, which are formally smooth a la Kontsevich-Rosenberg or, equivalently, quasi-free

a la Cuntz-Quillen). I said I didn’t know the answer and that it looked

like a difficult problem but at the same time it was entirely clear to

me how to attack this problem, even which book I needed to have a look

at to get started. And, indeed, after a visit to the library borrowing

Warren Dicks

lecture notes in mathematics 790 “Groups, trees and projective

modules” and browsing through it for a few minutes I had the rough

outline of the classification. As the proof is basicly a two-liner I

might as well sketch it here.

If **l G** is quasi-free it

must be hereditary so the augmentation ideal must be a projective

module. But Martin Dunwoody proved that this is equivalent to

**G** being a group acting on a (usually infinite) tree with finite

group vertex-stabilizers all of its orders being invertible in the

basefield **l**. Hence, by Bass-Serre theory **G** is the

fundamental group of a graph of finite groups (all orders being units in

**l**) and using this structural result it is then not difficult to

show that the group algebra **l G** does indeed have the lifting

property for morphisms modulo nilpotent ideals and hence is

quasi-free.

If **l** has characteristic zero (hence the

extra order conditions are void) one can invoke a result of Karrass

saying that quasi-freeness of **l G** is equivalent to **G** being

*virtually free* (that is, **G** has a free subgroup of finite

index). There are many interesting examples of virtually free groups.

One source are the discrete subgroups commensurable with **SL(2,Z)**

(among which all groups appearing in monstrous moonshine), another

source comes from the classification of rank two vectorbundles over

projective smooth curves over finite fields (see the later chapters of

Serre’s Trees). So

one can use non-commutative geometry to study the finite dimensional

representations of virtually free groups generalizing the approach with

Jan Adriaenssens in Non-commutative covers and the modular group (btw.

Jan claims that a revision of this paper will be available soon).

In order to avoid that I forget all of this once again, I’ve

written over the last couple of days a short note explaining what I know

of representations of virtually free groups (or more generally of

*fundamental algebras* of finite graphs of separable

**l**-algebras). I may (or may not) post this note on the arXiv in

the coming weeks. But, if you have a reason to be interested in this,

send me an email and I’ll send you a sneak preview.

If

you are interested in getting daily RSS-feeds of one (or more) of the

following arXiv

sections : **math.RA**, **math.AG**, **math.QA** and

**math.RT** you can point your news-aggregator to

*www.matrix.ua.ac.be*. Most of the solution to my first

Perl-exercise I did explain already yesterday but the current program

has a few changes. First, my idea was to scrape the *recent*-files

from the arXiv, for example for *math.RA* I would get http://www.arxiv.org/list/math.RA/recent but this

contains only titles, authors and links but no abstracts of the papers.

So I thought I had to scrape for the URLs of these papers and then

download each of the abstracts-files. Fortunately, I found a way around

this. There is a lesser known way to get at all abstracts from

**math** of the current day (or the few last days) by using the Catchup interface. The syntax of this interface is

as follows : for example to get all *math-papers* **with
abstracts** posted on April 2, 2004 you have to get the page with

URL

http://www.arxiv.org/catchup?smonth=04&sday=02&num=50&archive= math&method=with&syear=2004

so in order to use it I had

to find a way to parse the present day into a numeric

*day,month,year* format. This is quite easy as there is the very

well documented Date::Manip-module in Perl. Another problem with

*arXiv* is that there are no posts in the weekend. I worked around

this by requesting the *Catchup* starting from the *previous
business day* (an option of the

*DateCalc*-function. This means

that over the weekend I get the RSS feeds of papers posted on Friday, on

Monday I\’ll get those of Friday&Monday and for all other days I\’ll get

those of today&yesterday. But it is easy to change the script to allow

for a longer period so please tell me if you want to have RSS-feeds for

the last 3 or 4 days. Also, if you need feeds for other sections that

can easily be done, so tell me.

Here are the URLs to give to

your

*news-aggregator*for these sections :

**math.RA** at

**http://www.matrix.ua.ac.be/arxivRSS/mathRA/**

**math.QA** at

**http://www.matrix.ua.ac.be/arxivRSS/mathQA/**

**math.RT** at

**http://www.matrix.ua.ac.be/arxivRSS/mathRT/**

**math.AG** at

**http://www.matrix.ua.ac.be/arxivRSS/mathAG/**

If

your news-aggregator is not clever then you may have to add an

additional **index.xml** at the end. If you like to use these feeds

on a Mac, a good free news-aggregator is NetNewsWire Lite. To get at the above feeds, click on the *Subscribe
button* and copy one of the above links in the pop-up window. I

don\’t think my Perl-script breaks the Robots Beware rule of the arXiv. All it does it to download one page a day

using their Catchup-Method. I still have to set up a

*cron*-job to

do this daily, but I have to find out at which (local)time at night the

arXiv refreshes its pages…

As

far as I know (but I am fairly ignorant) the arXiv does not

provide *RSS feeds* for a particular section, say mathRA. Still it would be a good idea for anyone

having a *news aggregator* to follows some weblogs and

news-channels having RSS syndication. So I decided to write one as my

first Perl-exercise and to my own surprise I have after a few hours work

a prototype-scraper for *math.RA*. It is not yet perfect, I still

have to convert the local URLs to global URLs so that they can be

clicked and at the moment I have only collected the titles, authors and

abstract-links whereas it would make more sense to include the full

abstract in the RSS feed, but give me a few more days…

The

basic idea is fairly simple (and based on an O\’Reilly hack).

One uses the Template::Extract module to

extract the goodies from the arXiv\’s template HTML. Maybe I am still

not used to Perl-documentation but it was hard for me to work out how to

do this in detail either from the hack or the online

module-documentation. Fortunately there is a good Perl Advent

Calendar page giving me the details that I needed. Once one has this

info one can turn it into a proper RSS-page using the XML::RSS-module.

In fact, I spend far

more time trying to get *XML::RSS* installed under OS X than

writing the code. The usual method, that is via

iMacLieven:~ lieven$ sudo /usr/bin/perl -MCPAN -e shell Terminal does not support AddHistory. cpan shell -- CPAN exploration and modules installation (v1.76) ReadLine support available (try \'install Bundle::CPAN\') cpan> install XML::RSS

failed and even a

manual install for which the drill is : download the package from CPAN, go to the

extracted directory and give the commands

sudo /usr/bin/perl Makefile.pl sudo make sudo make test sudo make install

failed. Also a Google didn\’t give immediate results until

I did find this ADC page which set me on the right track.

It seems that the problem is in installing the XML::Parser for which one first need *expat*

to be installed. Now, the generic *sourceforge* page contains a

version for Linux but fortunately it is also part of the *Fink
project* so I did a

sudo fink install expat

which worked

without problems but afterwards I still was not able to install

*XML::Parser* because Fink installs everything in the */sw*

tree. But after

sudo perl Makefile.pl EXPATLIBPATH=/sw/lib EXPATINCPATH=/sw/include

I finally got the manual installation

going. I will try to tidy up the script over the weekend…

I

just finished the formal lecture-part of the course *Projects in
non-commutative geometry* (btw. I am completely exhausted after this

afternoon\’s session but hopeful that some students actually may do

something with my crazy ideas), springtime seems to have arrived and

next week the easter-vacation starts so it may be time to have some fun

like making a new webpage (yes,

*again*…). At the moment the main

matrix.ua.ac.be page is not really up to standards

and Raf and Hans will be using it soon for the information about the

*Liegrits*-project (at the moment they just have a beautiful logo). My aim is to make the main page to be the

starting page of the

**geoMetry**site

(guess what M stands for ?) on which I want

to collect as much information as possible on non-commutative geometry.

To get at that info I plan to set some

*spiders*or

*bots*or

*scrapers*loose on the web (this is just an excuse to force myself

to learn Perl). But it seems one has to follow strict ethical guidelines

in doing so. One of the first sites I want to spider is clearly the arXiv but they have

a scary Robots Beware page! I don\’t know whether their

robots.txt file will allow me to get at any of

their goodies. In a

*robots.txt*file the webmaster can put the

directories on his/her site which are off limits to robots and as I

don\’t want to do anything that may cause that the arXiv is no longer

available to me (or even worse, to the whole department) I better follow

these guidelines. First site on my list to study tomorrow will be The

Web Robots Pages …

Yesterday morning I thought that I could use some discussions I had a

week before with Markus Reineke to begin to make sense of one

sentence in Kontsevich’ Arbeitstagung talk Non-commutative smooth

spaces :

It seems plausible that Borcherds’ infinite rank

algebras with Monstrous symmetry can be realized inside Hall-Ringel

algebras for some small smooth noncommutative

spaces

However, as I’m running on a 68K RAM-memory, I

didn’t recall the fine details of all connections between the monster,

moonshine, vertex algebras and the like. Fortunately, there is the vast

amount of knowledge buried in the arXiv and a quick search on Borcherds gave me a

list of 17 papers. Among

these there are some delightful short (3 to 8 pages) expository papers

that gave me a quick recap on things I once must have read but forgot.

Moreover, Richard Borcherds has the gift of writing at the same time

readable and informative papers. If you want to get to the essence of

things in 15 minutes I can recommend What

is a vertex algebra? (“The answer to the question in the title is

that a vertex algebra is really a sort of commutative ring.”), What

is moonshine? (“At the time he discovered these relations, several

people thought it so unlikely that there could be a relation between the

monster and the elliptic modular function that they politely told McKay

that he was talking nonsense.”) and What

is the monster? (“3. It is the automorphism group of the monster

vertex algebra. (This is probably the best answer.)”). Borcherds

maintains also his homepage on which I found a few more (longer)

expository papers : Problems in moonshine and Automorphic forms and Lie algebras. After these

preliminaries it was time for the real goodies such as The

fake monster formal group, Quantum vertex algebras and the like.

After a day of enjoyable reading I think I’m again ‘a point’

wrt. vertex algebras. Unfortunately, I completely forgot what all this

could have to do with Kontsevich’ remark…

This morning there was an intriguing post on arXiv/math.RA

entitled A Note on

the Eigenvalues of the Google Matrix. At first I thought it was a

joke but a quick Google revealed that the PageRank algorithm really

is at the heart of Google technology, so I simply had to find out more

about it. An extremely readable account of it can be found in The PageRank Citation Ranking: Bringing Order to the Web which is really the

start of Google. It is coauthored by the two founders : Larry Page and

Sergey Brin. A quote from the introduction

“To test the utility of PageRank for search, we built a web

search engine called Google (Section

5)”

Here is an intuitive idea of

_PageRank_ : a page has high rank if the sum of the ranks of its

_backlinks_ (that is, pages linking to the page in question) is

high and it is computed by the _Random Surfer Model_ (see

sections 2.5 and 2.6 of the paper). More formally (at least from my

quick browsing of some papers, maybe the following account is slightly

erroneous and I’ll have to spend some more time reading) let

**N** be the number of webpages (estimated between 3 and 4

billion) and consider the **N x N** matrix

**A** the so called **GoogleMatrix** where

```
A = cP + (1-c)(v x
vec(1))
```

where **P** is the

column-stochastic matrix (meaning : all entries are zero or positive and

the sum of all entries in each column adds up to 1) with

entries

```
P(i,j) = 1/N(i) if i->j and 0
otherwise
```

where i and j are webpages and i->j

denotes that page i has a link to page j and where N(i) is the total

number of pages linked to in page i (all this information is available

once we download page i). c is a constant 0 < c < 1 and

corresponds to the fraction of webpages containing an _outlink (that

is, a link to another page) by all webpages (it seems that Google uses

c=0.85 as an estimate). Finally, v is a column vector with zero or

positive numbers adding up to 1 and vec(1) is the constant row vector

(1,…,1). The idea behind this term is that in the _Random Surfer

Model_ to compute the PageRank the Googlebot (normally following

links randomly in pages it enters) jumps every (1-c)x100% links randomly

to an entirely different webpage where the chance that it will end up at

page i is given by the i-th entry of v (this is to avoid being trapped

in a web-loop). So, in Googles model the bot _teleports_ itself

randomly every 6th link or so. Now, the **PageRank** is a

column-eigenvector for the GoogleMatrix A with eigenvalue 1 which can be

approximated by the RandomSurfer model and the rate of convergence of

this process depends on the _second_ largest eigenvalue for A

(the largest being 1). Now, in the paper posted this morning a simple

proof is given that this eigenvalue is c (because the matrix P has

multiple eigenvalues equal to 1). According to a previous paper on the

subject The

Second Eigenvalue of the Google Matrix, this statement has

implications for the convergence rate of the standard PageRank algorithm

as the web scales, for the stability of PageRank to perturbations to the

link structure of the web, for the detection of Google spammers, and for

the design of algorithms to speed up PageRank. But I’ll have to

read more to understand the Google spammers bit…