Eigenvalue Properties

How do we get Eigenvalues?

Say we have a elementary first-order scalar ODE. Such as:

$\frac{du}{dt}=au$

where $a\in \mathbb{R}$ and u(t) is the unknown scalar function. The solution will follow an exponential form. The general solution is: $u(t)=c{e}^{at}$. c is the integration constant and derived via separation of variables. The initial condition $u(t_0)=b$ defines the unique solution for the ODE. So our final solution is then given by:

$u(t)=b{e}^{a(t-t_0)}$

A first-order dynamical system consists of a system of n coupled first-order ODE like that explained above.

So, time for vectors! We write the system in vector form like this:

$\frac{du}{dt}=f(t,u)$ where $u_1(t),...,u_n(t){)}^T$ is the vector-valued solution. This representation parameterizes a curve in ${\mathbb{R}}^n$.

The matrix formulation for these linear systems is:

$\frac{du}{dt}=Au$, where A is constant n x n matrix for the n equations with its n terms. So now, we seek a solution of the form $u(t)=e^{\lambda t}v$, where lambda is a scalar and v is constant vector. Taking the derivative, we end up with $\frac{du}{dt}=\lambda e^{\lambda t}v$. Substituting into the system we end up with $\lambda e^{\lambda t}v=e^{\lambda t}Av$. Which will finally become $\lambda v=Av$. This is the eigenvalue equation.

This eigenvalue equation then can be rewritten as: $(A-\lambda I)v=0$. So, $A-\lambda I$ must be singular and the rank of it must be less than n.

Finally, to get eigenvalues and eigenvectors:

1. Solve $det(A-\lambda I)=0$ for $\lambda$
2. For each eigenvalue, solve $(A-\lambda I)v=0$ for v

What is an Eigenspace and how do they relate to Eigenvalues?

Given a real eigenvalue $\lambda \in \mathbb{R}$, the corresponding eigenspace $V_{\lambda }\subset {\mathbb{R}}^n$ is the subspace spanned by all eigenvectors associated with $\lambda$. Equivalently, the eigenspace $V_{\lambda }$ is equal to $ker(A-\lambda I)$. The properties of an eigenspace are as follows:

• $\lambda$ is an eigenvalue, so $ker(A-\lambda I)\ne \{0\}$ and vice versa
• Every nonzero element in $V_{\lambda }$ is the corresponding eigenvector
• A basis of an eigenspace is the easiest way to represent it

From that first property, if $\lambda =0$ then $ker(A)\ne \{0\}$ and vice versa. As such, the matrix A is singular.Therefore, a matrix is singular if and only if it has a zero eigenvalue.

To compute an eigenspace, you take the matrix and solve for $det(A-\lambda I)$. It should give a characteristic polynomial, and solve for its roots. Those roots are the eigenvalues. Then plug-in those eigenvalues into $(A-\lambda I)v=0$. Solve for v. These vectors v for each lambda is the corresponding eigenvector. The eigenvectors span the eigenspace.

If A is a real matrix with a complex eigenvalue: $\lambda =\mu +iv$ with the corresponding complex eigenvector $v=x+iy$ then the complex conjugate $\bar{\lambda }=\mu -iv$ is also an eigenvalue of A. The complex conjugate $\bar{v}=x-iy$.

If A is symmetric $A=A^T$ then all eigenvalues are real and the eigenvectors corresponding to distinct eigenvalues are orthogonal.

The constant term in the characteristic polynomial is the determinant of A. Every matrix n x n possess at least one and at most n distinct complex eigenvalues. An eigenvalue’s multiplicity is the power of term in the factorization of the characteristic polynomial.

A square matrix A and its transpose have the same characteristic equation and the same values and multiplicities. The sum of the eigenvalues of A equals its trace. The product of the eigenvalues equals its determinant.

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.