# Eigenvalue and Eigenvector
Given an $m \times m$ matrix $A$, we say a ***nonzero vector*** $\vec{x} \in \mathbb{C}^m$ is an **eigenvector** of $A$, and a number $\lambda \in \mathbb{C}$ is its **eigenvalue**, if

$$A\vec{x} = \lambda \vec{x}$$

How to compute them?

$$A\vec{x} = \lambda \vec{x} \Longleftrightarrow \left( \lambda I - A \right)\vec{x} = \vec{0}$$


which has a ***nonzero solution*** $\vec{x}$, which requires that the matrix $\lambda I - A$ is ***singular***, thus

$$\DeclareMathOperator*{\det}{det} A\vec{x} = \lambda \vec{x} \Longleftrightarrow \left( \lambda I - A \right)\vec{x} = \vec{0} \Longleftrightarrow \det\left( \lambda I - A \right) = 0$$

Here $\det\left( \lambda I - A \right)$ is actually a polynomial of degree $m$ in $\lambda$, called the **characteristic polynomial** of matrix $A$.
1. Solve the **characteristic polynomial** to find possible $\lambda$s, the engenvalues
2. For each **engenvalue**, solve the linear system $\left( \lambda I - A \right)\vec{x} = \vec{0}$ to find the corresponding eigenvectors of $A$.

>**e.g.** Compute the eigenvalue of the matrix $A = \left[\begin{array}{cc}
2 & 1 \\
0 & 1
\end{array}\right]$
>
>>$$\lambda I - A = \lambda \cdot \left[\begin{array}{cc}
1 & 0 \\
0 & 1
\end{array}\right] - \left[\begin{array}{cc}
2 & 1 \\
0 & 1
\end{array}\right] = \left[\begin{array}{cc}
\lambda - 2 & 1 \\
0 & \lambda - 1
\end{array}\right]$$

>> So that the chracteristic polynomial of $A$ is $\left( \lambda - 2 \right)\left( \lambda - 1 \right)$. Therefore the eigenvalues of $A$ are $\lambda_1 = 2$ and $\lambda_2 = 1$. Corresponding to the eigenvalue $2$, the solution of the linear system $(\lambda_1 I - A) \vec{x} = \vec{0}$ would be

>>$$\left[\begin{array}{cc}
0 & -1 \\
0 & 1
\end{array}\right] \vec{x} = \left[\begin{array}{c}
0 \\
0 
\end{array}\right] \Longrightarrow \vec{x} = k_1 \cdot \left[\begin{array}{c}
1 \\
0 
\end{array}\right]
$$

>> where $k_1$ is an arbitrary constant. And the other one is $k_2 \cdot \left[\begin{array}{c}
1 \\
-1 
\end{array}\right]$

# Eigenspace and multiplicity of eigenvalues
$\odot$ If a vector $\vec{x}$  is an eigenvector of $A$ corresponding to an eigenvalue $\lambda$, then any scalar multiple of $\vec{x}$ is also an eigenvector of $A$ corresponding to $\lambda$.$\Join$

**eigenspace** of $A$ corresponding to the eigenvalue $\lambda$: the solution space of $\left( A - \lambda I\right)\vec{x} = \vec{0}$, denoted a $E_{\lambda}$. And the dimension of $E_{\lambda}$ is also the **geometric multiplicity** of $\lambda$, which represents the maximum number of linearly linearly independent eigenvectors corresponding to the eigenvalue $\lambda$.

**algebraic multiplicity**, the multiplicity of each root $\lambda$.

Now denote all the distinct eigenvalues of a matrix $A$ be $\lambda_1, \lambda_2, \dots, \lambda_k$, so that the characteristic polynomial $\det(\lambda I - A)$ would be then expressed as

$$\det(\lambda I - A) = (\lambda - \lambda_1)^{l_1}(\lambda - \lambda_2)^{l_2 }\cdots(\lambda - \lambda_k)^{l_k}$$

Here $l_1, l_2, \dots, l_k$ are the algebraic multiplicities of $\lambda_1, \lambda_2, \dots, \lambda_k$ respectively.

$Conclusion$

For any eigenvalue $\lambda^*$ of a matrix $A$, its geometric multiplicity is always less than or equal to its algebric multiplicity.

$Proof$

Suppose a $m \times m$ matrix $A$ with a eigenvalue $\lambda^*$ whose geomatrix multiplicity is $l^*$. Then let the orthonormal basis of its eigenspace $E_{\lambda^*}$ be $\vec{v}_1, \vec{v}_2, \dots, \vec{v}_{l^*}$. And let the complementary orthonormal vector be $\vec{v}_{l^*+1},\vec{v}_{l^*+2},\dots,\vec{v}_{m}$, so that they can form the orthogonormal basis of the $m\text{-dimensional}$ vector space.

Let $V$ be the orthogonal matrix with $\vec{v}_{1},\vec{v}_{2},\dots,\vec{v}_{m}$ as its columns, then we have

$$V^{\mathrm{T}}AV = \left[\begin{array}{cc}
\lambda I & C \\
\mathbf{0} & D
\end{array}\right]$$

where $I$ is the $l^* \times l^*$ identity matrix, $C$ is an $l^*\times (m-l^*)$ matrix, and $D$ is an $(m-l^*) \times (m-l^*)$ matrix. Note that $\det(V^{\mathrm{T}})\det(V) = 1$. So we have

$$\det(\lambda I - A) = \det(\lambda I - V^{\mathrm{T}}AV) = \det( (\lambda - \lambda^*)I ) \cdot \det(\lambda I - D) = (\lambda - \lambda^*)^{l^*} \det(\lambda I - D)$$

which implies that the algebraic multiplicity of $\lambda^*$ is at least $l^*$.

# Similarity and Diagonalizability
$Def$

A matrix $A$ is said to be **similar** to another $B$ $iff$ there exists a ***nonsigular matrix*** $X$ such that

$$A = XBX^{-1}$$

$Conclusion$

$$\det(A - \lambda I) = \det(XBX^{-1} - \lambda XIX^{-1}) = \det(B - \lambda I)$$

And therefore they have the same eigenvalues.

Here $m \times m$ matrix $A$ is called **diagonalizable** if it is similar to a diagonal matrix $\Lambda $.

$$A = X\Lambda X^{-1} \Longrightarrow AX = X\Lambda $$

We can also see that the columns of $X$ are eigenvectors of the matrix $A$ corresponding to eigenvalues on the diagonal of $\Lambda $: $A \vec{x}^c_i = \lambda_i \vec{x}^c_i$.

**defective**: An eigenvalue whose algebraic mutiplicity exceeds its geometric multiplicity is a **defective eigenvalue**; A matrix with defective eigenvalues is a **defective matrix**. This promises its eigenvalue decomposition. And of course any diagonal matrix is nondefective.

***
For simplicity, now we only consider real symmetric matrix $A$ ($A^{\mathrm{T}} = A$). So that the eigenvalues are all real numbers, and eigenvectors can form a orthonormal basis of the $m\text{-dimensional}$ vector space. 

$Theorem$ 1 

For any real symmetric $m \times m$ matrix $A$, there exist a real orthogonal matrix $Q$, and a real diagonal matrix $\Lambda$, such that 

$$A = Q \Lambda Q^{\mathrm{T}} \Longrightarrow A\left[
\begin{array}{cccc}
\vec{q}_1^c & \vec{q}_2^c & \cdots & \vec{q}_m^c \\
\end{array}
\right] = \left[
\begin{array}{cccc}
\vec{q}_1^c & \vec{q}_2^c & \cdots & \vec{q}_m^c \\
\end{array}
\right] \left[
\begin{array}{cccc}
\lambda_1 & & & \\
& \lambda_2 & & \\
& & \ddots & \\
& & & \lambda_m \\
\end{array}
\right]$$

This is the **eigenvalue decomposition** of matrix $A$. We can also give them an order so that $\left| \lambda_1 \right| \geq \left| \lambda_2 \right| \geq \cdots \geq \left| \lambda_1 \right| \geq\left| \lambda_m \right| \geq 0$

# Conditioning of Eigenvalue Problems
Given an $m \times m$ matrix $A$ which is diagonalizable with eigenvalues $\lambda_1, \lambda_2, \dots \lambda_m$, and a set of eigenvectors $\vec{x}^c_1,\vec{x}^c_2, \dots, \vec{x}^c_m$ so that we can write $A = X\Lambda X^{-1}$ or equivalently $\Lambda = X^{-1}AX$.

Assume there is a small perturbation $\Delta A$ on the matrix $A$. Let us consider eigenvalues of the perturbed matrix $A + \Delta A$. We denote

$$X^{-1}\Delta A X = F$$

So that $X^{-1}\left( A + \Delta A \right)X = \Lambda + F$ and let $\mu$ be the eigenvalue of $\left( A + \Delta A \right)$ and $D+F$ corresponding to the eigenvector $\vec{v}$.

$$\left( D + F \right) \vec{v} = \mu \vec{v} \Longrightarrow \mu \vec{v} - D \vec{v} = F\vec{v}$$

Therefore we have

$$\begin{align}
\left\| \vec{v} \right\|_2 &= \left\| \left( \mu I - D \right)^{-1} F \vec{v} \right\|_2 \\
&\leq \left\| \left( \mu I - D \right)^{-1} \right\|_2 \cdot \left\| F \right\|_2 \cdot \left\| \vec{v} \right\|_2 \\
&= \frac{\left\| F \right\|_2 \cdot \left\| \vec{v} \right\|_2} {\left| \mu - \lambda_k \right|}
\end{align}$$

So that 

$$\DeclareMathOperator*{\Cond}{Cond}
\begin{align}
\left| \mu - \lambda_k \right| &\leq \left\| F \right\|_2 \\
&\leq \left\| X \right\|_2 \cdot \left\| \Delta A \right\|_2 \cdot \left\| X^{-1} \right\|_2 \\
&= \Cond(X) \left\|\Delta A \right\|_2 
\end{align}$$

where $\lambda_k$ is the closest to $\mu$ among the eigenvalues of the matrix $A$. 

If the matrix $A$ is symmetric, then we know From $Theorem$ 1 that the matrix $Q$ is orthogonal. Therefore solving the eigenvalues of a symmetric matrix is always well-conditioned, since $\Cond(Q) = 1$ for orthogonal matrix Q.

# Algorithms for solving eigenvalue problems
To find the eigenvalue is to solve the corresponding characteristic polynomial. But that's an ill-conditioned problem. At the same time, there is no exact formula to express the roots of a general high order ($> 5$) polynomials. This means that in general finding the eigenvalues of a matrix cannot be achieved within a finite number of steps of operations. Therefore an eigensolver has to be *iterative*.

Similar to the idea from $QR$ and $LU$, we wish to multiply a sequence of orthogonal matrices and their transposes to the both sides of $A$, such that

$$Q_m \cdots Q_2 Q_1 A Q^{\mathrm{T}}_1 Q^{\mathrm{T}}_2 \cdots Q^{\mathrm{T}}_m = \Lambda$$

And then

$$A= Q^{\mathrm{T}}_1Q^{\mathrm{T}}_2\cdots Q^{\mathrm{T}}_m \Lambda Q_1Q_2 \cdots Q_m = Q^{\mathrm{T}}\Lambda Q$$

However such an approach is just an imagination. An eigenvalue problem cannot be solved in a finite number of steps in general. The approach to solve eigenvalue problem is in general to produce a sequence

$$Q_j \cdots Q_2 Q_1 A Q^{\mathrm{T}}_1 Q^{\mathrm{T}}_2 \cdots Q^{\mathrm{T}}_j$$

such that it converges to an diagonal matrix $\Lambda$ as $ j \to 1$. In this sense we say

**Any eigenvalue solver must be iterative.**

f8132f53dc720d462b8a8a82ec051f956ee3f519
ipynb
Jupyter Notebook
Computational/Intro to Numerical Computing/Note_Chap08_Fundamentals of Eigenvalue Problems.ipynb
XavierOwen/Notes
d262a9103b29ee043aa198b475654aabd7a2818d
MIT
2018-11-27T10:31:08.000Z
2019-01-20T03:11:58.000Z
Computational/Intro to Numerical Computing/Note_Chap08_Fundamentals of Eigenvalue Problems.ipynb
XavierOwen/Notes
d262a9103b29ee043aa198b475654aabd7a2818d
MIT
Computational/Intro to Numerical Computing/Note_Chap08_Fundamentals of Eigenvalue Problems.ipynb
XavierOwen/Notes
d262a9103b29ee043aa198b475654aabd7a2818d
MIT
2020-07-14T19:57:23.000Z
2020-07-14T19:57:23.000Z
Qwen/Qwen-72B
1. YES
2. YES