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.
Writing a survey paper is a highly underestimated task. I once
tried it out with \’Centers of generic division algebras : the
rationality problem 1965-1990\’ and it took me a lot of time and that
was on a topic with only 10 to 15 key papers to consider… The task of
writing a survey paper on a topic with any breadth must be much more
difficult. Last week, Terry Gannon posted a survey paper on the arXiv :
Monstrous Moonshine : The first twenty-five years
which gives a very readable introduction to this exciting topic. It has
a marvelous opening line :
It has been approximately
twenty-five years since John McKay remarked that196 884 = 196 883 + 1
Anyone who is puzzled by this line (“So what?”)
should definitely have a go at this paper! Still not convinced? Here is
the second sentence :
That time has seen the discovery of
important structures, the establishment of another deep connection
between number theory and algebra, and a reinforcement of a new era of
cooperation between pure mathematics and mathematical
physics.
For the remaining sentences (quite a few, the paper
is 33 pages long) I happily refer you to the paper.
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…