Prove that the dimension of the eigenspace corresponding to the eigenvalue $\lambda=1$ of $H$ is at least the number of the clusters.. There are lots of ’islands’ in the world-wide-web, meaning clusters of websites that are not connected to other parts of the world wide web via hyperlinks. Let $H$ denote the column stochastic matrix that describes the probability of going from a website to another website. Assume there are $r$ different clusters of websites. Prove that the dimension of the eigenspace corresponding to the eigenvalue $\lambda=1$ of $H$ is at least $r$.

Without loss of generality, by reordering the websites, you can generate the stochastic matrix by clusters (put all websites in the first cluster, then all websites in the second, etc). This will produce a block-diagonal matrix, where each square block is itself a stochastic matrix. Each block diagonal will produce a linearly independent eigenvector for $\lambda = 1$ as each is a stochastic matrix in its own right. Therefore, the dimension of the eigenspace for $\lambda = 1$ is at least the number of blocks, i.e. $r$.