What is meant by the term: The matrix is "irreducible"

294 Views Asked by At

I came across the application of the Power Method used in determining the largest eigenvalue of a matrix in solving Google's PageRank algorithm and as a summary, the entire problem lies in finding the eigenvector $v$ such that : $$ Gv=v $$ where $\lambda=1$ is the largest eigenvalue of $G$ with $v$ being the largest eigenvector. Here $G$ is called the Google's matrix such that : $$ G=d*B+(1-d)*ones(n)/n $$ $B$ is a matrix whose each column sums up to one (Stochastic matrix) or in other words $\|B\|_{1}=1$ and $d$ is a damping factor where according to Larry Page and Sergey Brin in their famous article its set to $0.85$. Moreover, $ones(n)/n$ is an $n\times n$ matrix whose all entries are $1/n$ and is a stochastic matrix. Here $n$ is the length of $B$.

In order to ensure that the power method converges a sequence of vectors to the largest eigenvector $v$, an assumption is made is that $G$ is an irreducible matrix with no further context to what that means. Therefore, I hope someone can assist me in explaining what it means.

1

There are 1 best solutions below

0
On

A square matrix is irreducible if it is not reducible.

See https://mathworld.wolfram.com/ReducibleMatrix.html