Eigenvalue Properties

What is the key lemma relating eigenvalues of A and their corresponding eigenvectors?

If the eigenvalues ${\lambda }_1,{\lambda }_2,{\lambda }_3,...$ are distinct values of A, then the corresponding eigenvectors $v_1,v_2,v_3,...$ are linearly independent. The proof for this is inductive. First, any eigenvector $v_1\ne 0$ is trivially independent. The inductive step works as follows: $A(c_1{v}_1+...+c_k{v}_k)=c_1{\lambda }_1{v}_1+...+c_k{\lambda }_k{v}_k$ ${\lambda }_k(c_1{v}_1+...+c_k{v}_k)=c_1{\lambda }_k{v}_1+...+c_k{\lambda }_k{v}_k$ Subtracting these two, we get: $c_1({\lambda }_1-{\lambda }_k)v_1+...+c_{k-1}({\lambda }_{k-1}-{\lambda }_k)v_{k-1}=0$ We know that any two distinct eigenvalues have different values, so their difference is non-zero. Therefore, all coefficients must be zero for this equation to hold. Therefore, the eigenvector is linearly independent with all other eigenvectors.

What is the definition of completeness?

An eigenvalue $\lambda$ of a matrix A is called complete if the corresponding eigenspace $V_{\lambda }=ker(A-\lambda I)$ has the same dimension as its multiplicity.

The matrix A is said to be complete if all its eigenvalues are complete.

A simple eigenvalue is automatically complete. Only multiple eigenvalues can cause incompleteness. Completeness requires both geometric and algebraic multiplicity, the dimension of the eigenspace, and multiplicity as root of characteristic polynomial respectively. A matrix $A\in {\mathbb{C}}^{n\times n}$ is complete if and only if its eigenvectors span ${\mathbb{C}}^n$.

So, complex eigenvectors of a real matrix appear in conjugate pairs: $v=x\pm iy$. For complete real matrices, the real eigenvectors and the real and imaginary parts of the complex eigenvectors together form a basis of ${\mathbb{R}}^n$.

How does PageRank work?

Take all outgoing links from a webpage, treat it as a vector a la an adjacency matrix. Then, normalize this vector by dividing by total number of links on the page. Combine to create an adjacency matrix where the columns are normalized. Then plug in a page A into the following equation: $r_A={\sum }_{j=1}^n{L}_{Aj}\ast r_j$ or $r=Lr$.

We begin by assuming r is a vector of all ones divided by total pages in the graph. We iteratively solve $r=Lr$ till r stabilizes.