The amazing librarian

June 2008

Given an $n \times n$ matrix $H$ and a vector $I$ of length $n$, their product $J$ is also vector of length $n$ (strictly speaking we should write $I$ as a column vector here). The first entry of $J$ is the sum:

 

the first entry of the first row of $H$ ×  the first entry of $I$

+

the second entry of the first row of $H$ ×  the second entry of $I$

+

...

+

the last entry of the first row of $H$ ×  the last entry of $I$.

Now recall how we have built the matrix $H$. The first row records the information on back links of the page $P_1$: the first entry of this row is zero if $P_1$ does not link to itself and $\frac{1}{l_1}$ if it does, the second entry of the first row is 0 if $P_2$ does not link to $P_1$ and $\frac{1}{l_2}$ if it does, etc. Here the $l_ j$ are the total number of links on page $P_ j$. Now each entry of the first row of $H$ is multiplied by the corresponding entry of the importance vector $I$. So the first entry is multiplied by the importance of $P_1$, to get either 0 or $\frac{I_1}{l_1}$. The second entry is multiplied by the importance of $P_2$ to get either 0 or $\frac{I_2}{l_2}$, etc. Putting all this together shows that the first entry of the vector $J$ is equal to the sum of the importance of the pages that link to page $P_1,$ weighted by the total number of links on those pages. This is precisely what we defined the importance of page $P_1$ to be. So the first entry of $J$ is equal to the first entry of the importance vector $I$. The second entry of $J$ is the sum:
 

the first entry of the second row of $H$ ×  the first entry of $I$

+

the second entry of the second row of $H$ ×  the second entry of $I$

+

...

+

the last entry of the second row of $H$ ×  the last entry of $I$.

Again we see that the second entry of $J$ is equal to $I_2$, the second entry of the importance vector $I$. The multiplication carries on correspondingly for each row of $H$, and this shows that $J=I$.

Return to article