# neverendingbooks Posts

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
5)”

Here is an intuitive idea of
_PageRank_ : a page has high rank if the sum of the ranks of its
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
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

Never
ever tell an ICT-aware person that you want to try to set up a
home-network before you understand all 65536 port-numbers and their corresponding
protocols. Here is what happened to me this week. Jan Adriaenssens returned from an extended vacation in New Zealand and I told him
about my problems with trying to set up WebDAV securely. He
stared at me with that look that teenage children have if they
find out their parents dont know how to handle the simplest things on a
mobile such as saving a number, writing an SMS let alone use the
dictionary… and asked ‘now why would you want to do that??? I just
use AppleTalk to connect to my computer securely’. Now I’m not such a
fool that I didnt try this out but I didnt manage to get matrix
mounted on my Desktop. ‘Oh, but thats probably because of the
firewall’ Jan said ‘just send an email to Peter (the guy running the
defenses here) and ask him to open up ports 548 and
427…’ And sure enough five minutes later the problem was
solved and I could trow my WebDAV-plans in the dustbin (although, I
think Ive found a use for WebDAV but will keep this a bit longer to
myself until I checked it out). If you think that was the end of it,
think twice. Never ever point an ICT-professional to your
computer. They then start looking at its firewall-logs and find all
sorts of things such as : ‘I noticed that traffic from port 53
was dropped to the firewall, could it be that you configured the
firewall as DNS-server. If this is the case, you better remove it and it
will increase your network-speed, I think.’ And sure enough that
IP-address was set on my machine as one of two possibilities for the
DNS-server so I quickly removed it and in the process thought that maybe
I should also remove the other one so I did send Peter another email
asking whether that was ok. It turned out that the second IP address was
the genuine DNS-server so I got a sec answer back ‘You better leave
this as it is otherwise not much will work…’ Oh, shame, shame eternal
shame on me!

My only defense is that I still belong
to what I would call the cpu 2 generation (I’m a few years too
old to belong to the more computer-aware generation X). When I
started out doing research in 1980 the single most important command was

cpu 2

which you had to type before you could run any program.
By typing this you asked to be given 2 minutes of central processing
time, so you had to write all your programs in such a way that either
they gave a result back within 2 minutes or to include lots of
output-commands giving you a chance to determine at which parameters you
would restart the program for your next cpu 2. I once computed in
this way all factorial maximal orders in quaternion algebras by spending
a couple of days in the computer room. These days any desktop computer
would finish this task in half a minute. Perhaps the younger generations
will appreciate all the hard computer-work we had to do back then if
they read a bit from the computer history museum page!

Yesterday I made reservations for lecture rooms to run the
master class on non-commutative geometry sponsored by the ESF-NOG project. We have a lecture room on
monday- and wednesday afternoon and friday the whole day which should be
enough. I will run two courses in the program : non-commutative
geometry
and projects in non-commutative geometry both 30
hours. I hope that Raf Bocklandt will do most of the work on the
Geometric invariant theory course so that my contribution to it
can be minimal. Here are the first ideas of topics I want to cover in my
courses. As always, all suggestions are wellcome (just add a
comment).

non-commutative geometry : As
I am running this course jointly with Markus Reineke and as Markus will give a
mini-course on his work on non-commutative Hilbert schemes, I will explain
the theory of formally smooth algebras. I will cover most of the
paper by Joachim Cuntz and Daniel Quillen “Algebra extensions and
nonsingularity”, Journal of AMS, v.8, no. 2, 1995, 251?289. Further,
I’ll do the first section of the paper by Alexander Rosenberg and Maxim Kontsevich,
Noncommutative smooth spaces“. Then, I will
explain some of my own work including the “One
quiver to rule them all
” paper and my recent attempts to classify
all formally smooth algebras up to non-commutative birational
equivalence. When dealing with the last topic I will explain some of Aidan Schofield‘s paper
Birational classification of moduli spaces of representations of quivers“.

projects in
non-commutative geometry
: This is one of the two courses (the other
being “projects in non-commutative algebra” run by Fred Van Oystaeyen)
for which the students have to write a paper so I will take as the topic
of my talks the application of non-commutative geometry (in particular
the theory of orders in central simple algebras) to the resolution of
commutative singularities and ask the students to carry out the detailed
analysis for one of the following important classes of examples :
quantum groups at roots of unity, deformed preprojective algebras or
symplectic reflexion algebras. I will explain in much more detail three talks I gave on the subject last fall in
Luminy. But I will begin with more background material on central simple
algebras and orders.

The
game of sprouts is a two-person game invented by John Conway and Michael Paterson in 1967 (for some
historical comments visit the encyclopedia). You just need pen and paper to
play it. Here are the rules : Two players, Left and Right, alternate
moves until no more moves are possible. In the normal game, the last
person to move is the winner. In misere play, the last person to move is
the loser. The starting position is some number of small circles called
“spots”. A move consists of drawing a new spot g and then drawing two
lines, in the loose sense, each terminating at one end at spot g and at
the other end at some other spot. (The two lines can go to different
spots or the same spot, subject to the following conditions.) The lines
drawn cannot touch or cross any line or spot along the way. Also, no
more than three lines can terminate at any spot. A spot with three lines
attached is said to be “dead”, since it cannot facilitate any further
action.

You can play sprouts online using this Java applet.
There is also an ongoing discussion about sprouts on the geometry math forum. Probably the most complete
information can be found at the world game
of sprouts association
. The analysis of the game involves some nice
topology (the Euler number) and as the options for Left and Right are
the same at each position it is an impartial game and the outcome
depends on counting arguments. There is also a (joke) variation on the
game called Brussels sprouts (although some people seem to miss the point
entirely).

Some years ago I invented some variations
on sprouts making it into a partizan game (that is, at a given
position, Left and Right have different legal moves). Here are the rules
:

dots. Left is allowed to connect two White dots or a White and bLue dot
or two bLue dots and must draw an additional Red dot on the connecting
line. Right is allowed to connect two White dots, a Red and a White dot
or two Red dots and must draw an additional bLue dot on the connecting
line.

White dots. Left is allowed to connect two White dots or a White and
bLue dot or two bLue dots and must draw an additional bLue dot on the
connecting line. Right is allowed to connect two White dots, a Red and a
White dot or two Red dots and must draw an additional Red dot on the
connecting line.

Although the rules look pretty
similar, the analysis of these two games in entirely different. On
february 11th I’ll give a talk on this as an example in
Combinatorial Game Theory. I will show that Cold Antwerp Sprouts
is very similar to the game of COL, whereas Hot Antwerp Sprouts resembles SNORT.

The
other members of my family don’t understand what I am trying to do the
last couple of days with all those ethernet-cables, airport-stations,
computer-books and the like. ‘Improving our network’ doesn’t make
much of an impression. To them, our network is fine as it is : from
every computer one has access to the internet and to the only
house-printer and that is what they want. To them, my
computer-phase is just an occupational therapy while recovering
from the flu. Probably they are right but I am obstinate in
experimenting to prove them wrong. Not that there is much hope,
searching the web for possible fun uses of home-networks does not give
that many interesting pages. A noteworthy exception is a series of four
articles by Alan Graham for the macdevcenter
on the homemade dot-mac with OS X-project.

In
the first article Homemade Dot-Mac with OS X he explains how to
set-up a house-network (I will give a detailed account of our
home-network shortly) and firing up your Apache webserver. One nice
feature I learned from this is to connect a computer by ethernet to the
router and via an Airport card to the network (you can force this by
specifying the order of active network ports in the
SystemPreferences/Network/Show Network port configuration-pane :
first Built-in Ethernet and second Airport). This way you
get a faster connection to the internet while still connecting to the
other computers on the network. In the second part he explains how to
get yourself a free domain name even if you have (as we do) a dynamic
IP-address via a service like DynDNS. Indeed it is quite easy to set this up but
so far I failed to reach my new DNS-server from outside the network,
probably because of bad port-mapping of my old isb2lan-router.
This afternoon I just lost two hours trying to fix this (so far :
failed) as I didn’t even know how to talk to my router as I lost the
manual which is no longer online. A few Google-searches further I
learned that i just had to type http://192.168.0.1 to get at the set-up pages
(there is even a hidden page) but you shouldnt try these links
unless you are connected to one of these routers. Maybe I will need
another look at this review.

In the second
article, Homemade Dot-Mac with OS X, Part 2 he discusses in
length setting up a firewall with BrickHouse (shareware costing $25) compared to the built-in firewall-pane in SystemPreferences/Sharing convincing me to stay with the built-in option. Further he explains what tools one can use to set up a homepage (stressing the iPhoto-option).Finally, and this is the most interesting part (though a bit obscure), he hints at the possibility of setting up your own iDisk facility either using FTP (insecure) or WebDAV. The third article in the series is Homemade Dot Mac: Home Web Radio in which he claims that one can turn the standard OS X-Apache server into an iTunes streaming server. He uses for this purpose the QuickTime Streaming Sever which you can get for free from the Apple site but which I think works only when you have an X-server. It seems that all nice features require an X-server so maybe I should consider buying one… The (so far) final article is Six Great Tips for Homemade Dot Mac Servers is really interesting and I will come back to most op these possibilities when (if) I get them to work. The for me most promising options are : the central file server (which he synchronizes using the shareware-product ExecutiveSync ($15 for an academic license) but
I’m experimenting also a bit with the freeware Lacie-program Silverkeeper which seems to be doing roughly the
same things. The iTunes central-hack is next on my ToDo-list as
is (at a later stage) the WebDav and the Rendezvous-idea. So it seems
I’ll prolong my occupational therapy a while…

As I am going to give a talk on Combinatorial Game Theory early
next month I have to update my rusty knowledge of canonical forms of
two-person game positions, their temperature theory and the like. As
most of the concepts in this field are recursive they are hard to work
out by humans but easy for computers. So it is nice to have a good
program to use. I remember that David Wolfe wrote a couple of years ago the Gamesman Toolkit but it seems he has taken it off
his website. Still, you can get it from the Software released by Michael Ernst page. So,
Then do the following

cd Desktop/games sudo make sudo cp
games /usr/bin/ /usr/bin/games

to get it up and
running (for documentation of how to use it see the Gamesman
Toolkit-paper above. But, it seems that as of July 2003 there is a much
better alternative around : the Combinatorial Game Suite of Aaron Siegel. It is an open source Java-program so it
runs on many platforms (including Mac OSX). Here is the way to get it
cgsuite-0.4-folder on your desktop. Then type

cd
Desktop/cgsuite-0.4 java -jar cgsuite.jar

and after a few
questions (including whether you want to be on the mailing list of the
project) the program starts up. It is very well documented with an
on-line manual which I have to read over the coming
days…

A
longer term project is to get the web-server www.matrix.ua.ac.be integrated in our home-network
as an external WebDAV-server (similar to the .Mac-service
offered by Apple). But as this server runs all information about the
master-class on non-comutative geometry connecting to it via HTTP to use
combinations will be send without encryption. Hence the natural question
whether this server can be set up to run SSL (Secure Sockets
Layer) such that one can connect via HTTPS and all exchanged information
will be encrypted. As the server is an Apache it comes down to get
mod-ssl running. A Google on mod_ssl OS X gives the
ADC-document Using mod-ssl on Mac OS X which seems to be just
instructions of using the openssl command. However, the
end-result is rather weak : it only makes the localhost running
HTTPS, that is, one can connect to your own computer safely… which is
pretty ridiculous (other computers in the same network cannot even
connect safely).

So, back to the Google-list on which
one link raises my interest Configuring mod-ssl on Mac OS X which looks like
the previous link but has one essential difference : the page is written
by Marc Liyanage. If you ever tried to get PHP and/or MySQL
running under OS X you will have noticed that his pages are by far the
most reliable on the subject, hence maybe he has also something
interesting to say on mod-ssl. However, the bottom line of the
document is not very promising :

You
should now be able to access the content with https://127.0.0.1 from
the same machine.

which is again the
localhost. So perhaps it is just impossible to run mod-ssl
without having an X-server. Anyway, let us try out his procedure.
Begin by issuing the following commands in the Terminal

sudo -s cd /etc/httpd mkdir ssl chmod 700 ssl cd
ssl gzip -c --best /var/log/system.log > random.dat openssl rand
-rand file:random.dat 0

Next, we need a server certificate. If you
want to do it properly you need a certificate from a certification
authority
such as Thawte but this costs at least $200 a year which I am not willing to pay. The alternative is to use a self-signed certificate which will force the browser to display an error-message but if the user dismisses it all traffic exchanged with the server will still be encrypted which is just what I want. So, type the command openssl req -keyout privkey-2001.pem -newkey rsa:1024 -nodes -x509 -days 365 -out cert-2001.pem (all on one line). You will be asked a couple of questions (the only important one is the Common Name (eg, YOUR name). Here you should take care to enter the host name of your web server exactly as it will be used later in the common name field. In my test-case, if I want to get my server used by other computers in the network this name will be imaclieven.local. (note the trailing .). Now issue the following commands chmod 600 privkey-2001.pem chown root privkey-2001.pem apxs -e -a -n ssl /usr/libexec/httpd/libssl.so  which will activate the SSL-module (if at a later state you want to de-activate it you have to change -a by -A in the last command). Finally, we have to change the /etc/httpd/httpd.conf file so first save a backup-version and then add the following lines at the end of the file : (IfModule mod-ssl.c) Listen 80 Listen 443 SSLCertificateFile /etc/httpd/ssl/cert-2001.pem SSLCertificateKeyFile /etc/httpd/ssl/privkey-2001.pem SSLRandomSeed startup builtin SSLRandomSeed connect builtin (VirtualHost -default- :443) SSLEngine on (/VirtualHost) (/IfModule) Observe that round brackets () should be replaced by <>. Finally, we do apachectl stop apachectl start and we are done! Going to another computer in the network and typing in Safari https://imaclieven.local./ will result in an error message Just click Continue and you will have a secure connection to the server. Thanks Marc Liyanage! (Added january 11th) Whereas the above allows one to make a HTTPS connection it is not enough for my intended purposes. In order to get a secure connection to a WebDAV server, this server must have the mod-auth-digest module running which seems to be impossible for the standard Apache server of 10.3. You need an X-server to have this facility. So I think I have to scale down my ambitions a bit. So far I found it rather easy to post one or more messages a day as I was installing a lot of software or trying to get things working and was merely logging my progress for future reference. These notes are useful to me but probably not to the rest of the world. Another thing I noticed is that I’m using this blog sometimes as a replacement for my Bookmarks, merely listing interesting web-pages without too much personal comments. I will continue to post both install-logs and bookmark-logs but in addition I want to write (say weekly) a lengthier post on a specific topic with more background, more details (such as screenshots) and more personal comments. We will see how this works out in the coming weeks… Another thing that slightly worried me is that people visiting my homepage and clicking on to my blog may expect entirely different things there. But this cant be helped, I’m sitting on an OSX-cloud at the moment but no doubt this will change quickly. Beginning of february I have to give a talk on Combinatorial Game Theory and soon afterwards the Non-commutative Geometry Master Class starts in which I’m giving a couple of courses, so mathematics will become more dominant in this blog from next month on… On a blog-tech matter : I found a quite good editor pMpost which is meant to write pMachine-blogs offline and upload them by one click. It also synchronizes categories etc. on login. Further, it has a spelling-checker but the thing I really like about it is that you can save texts as a draft and continue at a later time (sadly, it remember the date/hour when you start your post so when you finally submit it it will be posted at the starting- rather than the posting-day. Still, there is nothing that copy/paste cannot solve. I hope to use this facility when (read if) I’m going for a more in-depth post. Another matter that I will address to as quickly as possible (probably over the weekend) is teh layout of this site. The main annoying thing is that the text doesnt resize when you increase/decrease window width. So I will address this matter first and probably leave a personal layout and color-scheme to later. Fortunately, I did find a good site containg a lot of CSS templates for pMachine weblogs. Another site I’ll have to investigate over the weekend is pMtemplates. But don’t expect too much from the layout-side, I still have other projects to worry about : SSL, WebDAV, streaming iTunes, getting on Ethernet-DVD player to work and so on. What then is all this WarWalking, WarDriving, WarChalking and so on? In particular, why the aggressive War-word in them ? From what I learned, the historical origin of these terms comes from the 1983 movie “War Games” in which a kid sets up his modem to dial numbers until it finds a computer to hack leading inevitably to the US-army in total panic. This hobby created the phrase WarDialing. In analogy, a person driving around in a car with a laptop in search for wireless networks is said to be WarDriving, if (s)he is on foot it is clearly WarWalking. Because of the aggressive nature of the War-subword some people have re-engineered an explanation : WAR = Wireless Access Reconnaissance so let us hope this acronym will catch on. Now then, what is WarChalking ? It was invented by Matt Jones and the idea is that a WarWalker should write a symbol in chalk on the wall nearest to the discovered Access Point describing its nature (see picture on the left) : the first sign depicts an open node, the next a closed one and the last one is a node with WEP-protection (btw. WEP=Wired Equivalent Privacy). A lot of people seem to take this fairly serious, there is even a webpage warchalking.org devoted to it on which you can find a lot more information. And as warchalking was originally British, there had to be also an American site containing among other things a not that active forum. Further, the unofficial HOW-TO of WarDriving may be interesting. To me it all sounds as an excuse to buy a GPS-receiver and a laptop We still have an original iMac (Bondi Blue). It runs at 233 MHz, has 192Mb RAM and a hard-disk of 4Gb, so is pretty outdated. Still, when Mac OSX was introduced I had a hard time installing extra RAM in it (for this model you have to take it apart disconnecting all sorts of cables) so it would be a shame if this oldest member of the family is left out of the network. The problem is that it has an Ethernet card but no possibility to include an Airport-Card… So I bought a D-Link Wireless USB adapter and was told that installation would be plug-and-play : just connect it to the USB-port, open up the Applications/Utilities/Airport Setup Assistant and everything would rum smoothly. Hahah! When I started the Assistant it was clever enough to detect that no Airport-Card was installed and refused further action. But, there is a CD in the package so I did install the driver which really adds a new icon Wireless Adaptor to the System Preferences . Clicking it gave the sobering message No Wireless Device Attached and I couldnt press the Scan button for detection of possible networks. But disconnecting the D-Link a number of times and pressing it very hard eventually I got a wireless icon in the toolbar but still it couldnt give me a signal strength of available networks. But that might be right as the ABS is protected both by WEP and by MAC-access. So, I added the MAC-address of the D-Link to the list in the Access Control pane of the Airport Admin Utility which also gives a way to get at the Hex-equivalent of the WEP-key : click on the Password icon. So, i manually created in the Wireless Adaptor-preferences a network with the correct name, WEP-key equivalent and so on and thought that would do it. But no, now I did get a signal strength but it showed that I was not connected and that the WEP-key was incorrect. On the other hand, no complaints were listed when i tried to access the ABS as Peer-to-peer but this created all other sorts of problems as I could detect with iStumbler so I quickly removed this option and got to bed. This morning I realized that I still have the old Graphite Airport Base Station lying idle so I connected it with a patch cable to the Router, reconfigured it without WEP-protection and without Access Control and instructed BondiBlue to connect to this new network, which it immediately managed to do but it took a few restarts and time to get it onto Internet and connected to other computers on this second network. So, now I will increase security on this new network and see where it fails. First, add Access Control by including the MAC Address of the D-Link and other computers, reconfigure the ABS and the BondiBlue is still on the network! Next, WEP : in the Apple documentation it is mentioned to take a passphrase of exactly 5 symbols to ‘increase compatibility with third-party products’. Let’s try ab;12, change in the Wireless Adaptor-Prefrences the properties of the network by choosing Enable WEP 40 Bits ASCII (5 characters) and give the key ab;12 and sure enough : everything works! So the problem was that our regular network is WEP-protected by a longer passphrase and D-Link could not handle the HEX-equivalent 10 digit number. A final attempt : in the D-Link documentation a solution is offered by giving the ABS a 10-digit Hex together with a starting$-sign so let’s try
\$4bb2603b52 on the ABS and 4bb2603b52 in the properties of