The amazing librarian

Share this page

The amazing librarian

June 2008

Given an n×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 \textbf{first} entry of J is the sum: thefirstentryofthefirstrowof$H$×thefirstentryof$I$+thesecondentryofthefirstrowof$H$×thesecondentryof$I$+...+thelastentryofthefirstrowof$H$×thelastentryof$I$. \ Now recall how we have built the matrix H. The first row records the information on back links of the page P1: the first entry of this row is zero if P1 does not link to itself and 1l1 if it does, the second entry of the first row is 0 if P2 does not link to P1 and 1l2 if it does, etc. Here the lj are the total number of links on page Pj. 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 P1, to get either 0 or I1l1. The second entry is multiplied by the importance of P2 to get either 0 or I2l2, 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 P1, weighted by the total number of links on those pages. This is precisely what we defined the importance of page P1 to be. So the first entry of J is equal to the first entry of the importance vector I. The \textbf{second} entry of J is the sum: thefirstentryofthesecondrowof$H$×thefirstentryof$I$+thesecondentryofthesecondrowof$H$×thesecondentryof$I$+...+thelastentryofthesecondrowof$H$×thelastentryof$I$. \ Again we see that the second entry of J is equal to I2, 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