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