\documentclass{article}%
\usepackage{amsmath}%
\setcounter{MaxMatrixCols}{30}%
\usepackage{amsfonts}%
\usepackage{amssymb}%
\usepackage{graphicx}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.00.0.2552}
%TCIDATA{CSTFile=40 LaTeX article.cst}
%TCIDATA{Created=Monday, October 27, 2014 11:34:53}
%TCIDATA{LastRevised=Monday, October 27, 2014 11:43:15}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{<META NAME="DocumentShell" CONTENT="Standard LaTeX\Blank - Standard LaTeX Article">}
\newtheorem{theorem}{Theorem}
\newtheorem{acknowledgement}[theorem]{Acknowledgement}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{case}[theorem]{Case}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conclusion}[theorem]{Conclusion}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{solution}[theorem]{Solution}
\newtheorem{summary}[theorem]{Summary}
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\begin{document}

\title{Introduction to PageRank}
\maketitle

Consider the following web.%

%TCIMACRO{\FRAME{dtbpF}{2.9921in}{2.2474in}{0pt}{}{}{web1.wmf}%
%{\special{ language "Scientific Word";  type "GRAPHIC";
%maintain-aspect-ratio TRUE;  display "USEDEF";  valid_file "F";
%width 2.9921in;  height 2.2474in;  depth 0pt;  original-width 9.5998in;
%original-height 7.1996in;  cropleft "0";  croptop "1";  cropright "1";
%cropbottom "0";  filename 'pics/web1.wmf';file-properties "XNPEU";}} }%
%BeginExpansion
\begin{center}
\includegraphics[
natheight=7.199600in,
natwidth=9.599800in,
height=2.2474in,
width=2.9921in
]%
{pics/web1.wmf}%
\end{center}
%EndExpansion


1) Give a ranking of the pages in the web where $x_{k}$ equal the number of
backlinks for page $k,$ i.e., the number of links into page $k.$

2) Explain why the rankings of pages $1$ and $4$ should not be the same since
page $1$ has a ranking from a more important page than page $4$ does.

3) Now let $x_{k}$ be the ranking of page $k$ given so that the ranking of any
page is equal to the sum of the rankings from each page linking into it. Show
that this gives a systems of equations
\begin{align*}
x_{1} &  =x_{3}+x_{4}\\
x_{2} &  =x_{1}\\
x_{3} &  =x_{1}+x_{2}+x_{4}\\
x_{4} &  =x_{1}+x_{2}.
\end{align*}
Now show that this system has no solutions! Hint: solve the last 3 equations
and then show it is not consistent with the first equation.

4) Now let's change the ranking so that each page gets a single vote that is
divided equally among its outlinks, and the ranking $x_{k}$ is equal to the
sum of the votes times the rankings of all backlinks. The system is now
\begin{align*}
x_{1} &  =x_{3}+\frac{1}{2}x_{4}\\
x_{2} &  =\frac{1}{3}x_{1}\\
x_{3} &  =\frac{1}{3}x_{1}+\frac{1}{2}x_{2}+\frac{1}{2}x_{4}\\
x_{4} &  =\frac{1}{3}x_{1}+\frac{1}{2}x_{2}.
\end{align*}
Show that this system can be solved to get  $x_{1}=1,$ $x_{2}=\frac{1}{3},$
$x_{3}=\frac{3}{4},$ $x_{4}=\frac{1}{2}.$ 

Notice that $x_{1}$ has the highest ranking! This is because $x_{3}$ threw its
whole vote to $x_{1}$ and so that even though $x_{3}$ got votes from three
different sites, they still do not total as much as what $x_{1}$ gets. Note,
usually we will rescale so that the sum is equal to $1,$ and so we get
\[
x_{1}=\frac{12}{31},\;\;x_{2}=\frac{4}{31},\;\;x_{3}=\frac{9}{31}%
,\;\;x_{4}=\frac{6}{31}.
\]



\end{document}