Eigen value
An eigen value of a square matrix $A = [a_{ij}]$ is a scalar $\lambda$ such that there exists a non-zero vector $v = \begin{pmatrix} v_1 \\ v_2 \\ \vdots \\ v_n \end{pmatrix}$, called an eigen vector, for which the following equation holds:
$$A \cdot v = \lambda \cdot v$$
This equation means that the action of the matrix $A$ on the vector $v$ only scales the vector by the scalar $\lambda$ (i.e., the direction of the eigenvector remains unchanged under the transformation represented by $A$).
Eigen vector
An eigen vector of a square matrix $A = [a_{ij}]$ corresponding to an eigenvalue $\lambda$ is a non-zero vector $v = \begin{pmatrix} v_1 \\ v_2 \\ \vdots \\ v_n \end{pmatrix}$ that satisfies the equation:
$$A \cdot v = \lambda \cdot v$$
In other words, when the matrix $A$ is applied to the eigenvector $v$, the result is simply a scaled version of $v$, where the scaling factor is the eigenvalue $\lambda$.
Algorithm to Find Eigenvalues and Eigenvectors
Input:
- A square matrix $A = [a_{ij}]$ of size $n \times n$.
Output:
- Eigenvalues $\lambda_1, \lambda_2, \dots, \lambda_n$ (if they exist).
- Eigenvectors corresponding to each eigenvalue.
Step-by-Step Algorithm:
- Compute the Characteristic Equation:
- The characteristic equation of a matrix $A$ is given by:
$$\text{det}(A – \lambda I_n) = 0$$ where $I_n$ is the identity matrix of size $n \times n$ and $\lambda$ is a scalar. This equation is a polynomial in $\lambda$ (called the characteristic polynomial).
- The characteristic equation of a matrix $A$ is given by:
- Solve the Characteristic Equation:
- Solve the characteristic equation $\text{det}(A – \lambda I_n) = 0$ for $\lambda$ to find the eigenvalues.
- The solutions to this equation are the eigen values of the matrix $A$. These eigenvalues can be real or complex numbers.
- If there are repeated eigen values (i.e., multiple solutions for the same $\lambda$), they are called degenerate eigen values. This means the matrix has multiple eigenvectors corresponding to the same eigenvalue.
Remark: If an eigenvalue $\lambda$ has multiplicity greater than 1, it is called a repeated eigen value. In such cases, the matrix may have multiple linearly independent eigenvectors corresponding to this eigenvalue.
- Find Eigenvectors for Each Eigenvalue:
- For each eigenvalue $\lambda_i$, substitute $\lambda_i$ into the equation:
$$(A – \lambda_i I_n) \cdot v = 0$$ - This is a system of linear equations. Solve this system to find the eigenvector(s) corresponding to $\lambda_i$. The eigenvector is any non-zero solution to this system.
- For each eigenvalue $\lambda_i$, substitute $\lambda_i$ into the equation:
- Normalize the Eigenvectors (Optional):
- Eigenvectors are typically normalized so that their length (or norm) is 1. This step is optional but often done for convenience in certain applications.
- Eigenvectors are typically normalized so that their length (or norm) is 1. This step is optional but often done for convenience in certain applications.
- Repeat for All Eigenvalues:
- Repeat steps 3 and 4 for all distinct eigenvalues obtained from the characteristic equation.
Remarks:
- Repeated Eigenvalues: If an eigenvalue $\lambda$ has multiplicity greater than 1 (i.e., it appears more than once as a solution to the characteristic equation), then there may be multiple linearly independent eigenvectors corresponding to that eigenvalue.
- If the number of linearly independent eigenvectors corresponding to a repeated eigenvalue is equal to the multiplicity of the eigenvalue, the matrix is diagonalizable.
- If the number of linearly independent eigenvectors is less than the multiplicity of the eigenvalue, the matrix is not diagonalizable.
2×2 Matrix Example: Eigenvalues and Eigenvectors
Consider the matrix:
$$A = \begin{bmatrix} 4 & 1 \\ 2 & 3 \end{bmatrix} $$
We want to find the eigenvalues and eigenvectors of this matrix.
Step 1: Find the Characteristic Equation
The characteristic equation is determined by solving:
$$ \text{det}(A – \lambda I) = 0 $$
Where $\lambda$ represents the eigenvalue and $I$ is the identity matrix.
First, calculate $A – \lambda I$:
$$ A – \lambda I = \begin{bmatrix} 4 – \lambda & 1 \\ 2 & 3 – \lambda \end{bmatrix} $$
Now, compute the determinant of $A – \lambda I$:
$$ \text{det}(A – \lambda I) = \begin{vmatrix} 4 – \lambda & 1 \\ 2 & 3 – \lambda \end{vmatrix} $$
We expand the determinant as:
$$ = (4 – \lambda)(3 – \lambda) – 1 \times 2 $$
Simplifying:
$$ = (4 – \lambda)(3 – \lambda) – 2 $$
Expanding further:
$$ = 12 – 4\lambda – 3\lambda + \lambda^2 – 2 $$
Simplify the expression:
$$ = \lambda^2 – 7\lambda + 10 $$
So, the characteristic equation is:
$$ \lambda^2 – 7\lambda + 10 = 0 $$
Step 2: Find the Eigenvalues
We solve the quadratic equation $ \lambda^2 – 7\lambda + 10 = 0 $ using the quadratic formula:
$$ \lambda = \frac{-(-7) \pm \sqrt{(-7)^2 – 4(1)(10)}}{2(1)} = \frac{7 \pm \sqrt{49 – 40}}{2} = \frac{7 \pm \sqrt{9}}{2} $$
Thus, the roots are:
$$ \lambda_1 = \frac{7 + 3}{2} = 5, \quad \lambda_2 = \frac{7 – 3}{2} = 2 $$
So, the eigenvalues are:
$$ \lambda_1 = 5, \quad \lambda_2 = 2 $$
Step 3: Find the Eigenvectors
Now, we solve $(A – \lambda I)\mathbf{v} = 0$ for each eigenvalue.
Eigenvector for $ \lambda_1 = 5 $:
Substitute $ \lambda_1 = 5 $ into $ A – 5I $:
$$ A – 5I = \begin{bmatrix} 4 – 5 & 1 \\ 2 & 3 – 5 \end{bmatrix} = \begin{bmatrix} -1 & 1 \\ 2 & -2 \end{bmatrix} $$
Solve $ (A – 5I)\mathbf{v} = 0 $:
$$ \begin{bmatrix} -1 & 1 \\ 2 & -2 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix} $$
This gives the system of equations:
$$ -x + y = 0 $$
$$ 2x – 2y = 0 $$
From the first equation, we find:
$$ x = y $$
Thus, the eigenvector corresponding to $ \lambda_1 = 5 $ is:
$$ \mathbf{v_1} = \begin{bmatrix} 1 \\ 1 \end{bmatrix} $$
Eigenvector for $ \lambda_2 = 2 $:
Substitute $ \lambda_2 = 2 $ into $ A – 2I $:
$$ A – 2I = \begin{bmatrix} 4 – 2 & 1 \\ 2 & 3 – 2 \end{bmatrix} = \begin{bmatrix} 2 & 1 \\ 2 & 1 \end{bmatrix} $$
Solve $ (A – 2I)\mathbf{v} = 0 $:
$$ \begin{bmatrix} 2 & 1 \\ 2 & 1 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix} $$
This gives the system of equations:
$$ 2x + y = 0 $$
$$ 2x + y = 0 $$
From the first equation, we find:
$$ y = -2x $$
Thus, the eigenvector corresponding to $ \lambda_2 = 2 $ is:
$$ \mathbf{v_2} = \begin{bmatrix} 1 \\ -2 \end{bmatrix} $$
Conclusion: Eigenvalues and Eigenvectors
The eigenvalues for the matrix $ A = \begin{bmatrix} 4 & 1 \\ 2 & 3 \end{bmatrix} $ are:
- $ \lambda_1 = 5 $, with eigenvector $ \mathbf{v_1} = \begin{bmatrix} 1 \\ 1 \end{bmatrix} $
- $ \lambda_2 = 2 $, with eigenvector $ \mathbf{v_2} = \begin{bmatrix} 1 \\ -2 \end{bmatrix} $
Matrix $\longmapsto$ Vector Operation:-
Any point $X$ in $\mathbb{R}^n$ can be expressed as a Linear Combination of $v_1, v_2 \cdots v_n$, eigen vectors of $A$.
(i.e) $$X = \sum_{i=1}^{n} C_i v_i \qquad C_i \in \mathbb{R}$$
$$\therefore \quad AX = A\left[\sum C_i v_i\right] = \sum C_i A v_i$$
$$AX = \sum C_i \lambda_i v_i$$
Hence a matrix multiplication (LHS) is a Vector operation (RHS).
Example 1:
Let $n = 2 \quad A = \begin{bmatrix} 3 & 2 \\ 1 & 2 \end{bmatrix} \quad \text{and} \quad X = \begin{bmatrix} 5 \\ -8 \end{bmatrix} \quad \lambda_1 = 4, \quad \lambda_2 = 1$
$$v_1 = \begin{bmatrix} 2 \\ 1 \end{bmatrix} \quad v_2 = \begin{bmatrix} 1 \\ -1 \end{bmatrix}$$
$$\therefore \quad X = c_1 v_1 + c_2 v_2$$
$$ X = c_1\begin{bmatrix} 2 \\ 1 \end{bmatrix} + c_2\begin{bmatrix} 1 \\ -1 \end{bmatrix}$$
$$ 2c_1 + c_2 = 5 $$
$$c_1 – c_2 = -8 $$
Hence, $$c_1 = -1, \quad c_2 = 7$$
$$\therefore \quad AX = \sum c_i \lambda_i v_i$$
$$\Rightarrow \quad AX = (-1)\,4\begin{bmatrix} 2 \\ 1 \end{bmatrix} + (7)(1)\begin{bmatrix} 1 \\ -1 \end{bmatrix}$$
$$= \begin{bmatrix} -1 \\ -11 \end{bmatrix}$$
Cross check: $$AX = \begin{bmatrix} 3 & 2 \\ 1 & 2 \end{bmatrix}\begin{bmatrix} 5 \\ -8 \end{bmatrix} = \begin{bmatrix} 15-16 \\ 5-16 \end{bmatrix}$$
$$= \begin{bmatrix} -1 \\ -11 \end{bmatrix}$$
Eigen (spectral) Decomposition:-
Let $A$ be a square matrix of order $n$. Let $v_1, v_2 \cdots v_n$ be $n$ eigen vectors of $A$ corresponding to eigen values $\lambda_i$ $(i = 1, 2, \cdots n)$
Then $$A = VDV^{-1}$$ is called Eigen Decomposition where $D = \text{diag}(\lambda_1, \lambda_2, \cdots \lambda_n)$ and $V$ is a square matrix of order $n$ whose columns are $\{v_1, v_2, \cdots v_n\}$, eigen vectors of $A$.
Particular case:
If $A$ is Symmetric, then $A = VDV^{-1}$ has an additional Characteristic. $V$ has orthonormal columns from $\{v_1, \cdots v_n\}$. Hence $V^{-1} = V^T$
$$\Rightarrow \quad A = VDV^T$$
So, if $A$ is symmetric, real and has distinct eigen values, then its spectral decomposition is “clean” and simple (less resource) computation.
If $A$ is real symmetric, and has distinct eigen values, then Spectral decomposition is simpler in computation. This is due to the natural and immediate orthogonal matrix $V$. Else (equal eig. val) orthogonalization will be required.
Limitations:-
Eigen or spectral
- requires square matrices
- eigen vectors may not exist (defective matrices)
- Unstable when $V$ is ill conditioned ($V$: matrix of eig vectors)
Usage:
In $n$ dimensions, a vector is a point, and a matrix transforms that point linearly (stretch/contract/tilt (shear)).
Eigen values and vectors reveal the fundamental directions and stretch factor. Both do not describe translation.
3 steps in spectral decomposition: $A = VDV^{-1}$
Matrix multiplication $AX$ is
- Change Coordinates to the eigenvector basis $(V^{-1}X)$
- how much of $x$ points along each eigen directions (coordinates in the eig.vec. basis)
- Express $x$ as a linear combination of $v_1, v_2 \cdots$
- Scale each coordinate independently $(DV^{-1}X)$
- Independent stretch/shrink along each eigen directions.
- Convert back to original coordinate system $(VDV^{-1}X)$
Some more observations:
- For real non-symmetric $A$, the eigen values may be complex conjugate pairs. So, real spectral decomposition $VDV^{-1}$ may not possible.
- orthogonalization ($V$ as orthogonal) will be lost.
- Eigen vectors may not be orthogonal.
- For real symmetric $A$, eigen values are always real, so that spectral decomposition is possible.
- If eigen values are distinct, normalized eigen vectors will provide orthogonality
- Else, orthogonalization is needed.
Example 2:
Process of decomposition (Matrix multiplication)
$P_1$:
$$A = \begin{bmatrix} 3 & 2 \\ 1 & 2 \end{bmatrix} \quad X = \begin{bmatrix} 5 \\ -8 \end{bmatrix} $$
$$\lambda: \{4, 1\} \quad v_1 = \begin{bmatrix} 2 \\ 1 \end{bmatrix} \quad v_2 = \begin{bmatrix} 1 \\ -1 \end{bmatrix} \quad v_1^T v_2 \ne 0$$
$$V = \begin{bmatrix} 2 & 1 \\ 1 & -1 \end{bmatrix} \quad D = \begin{bmatrix} 4 & 0 \\ 0 & 1 \end{bmatrix}$$
$$V^{-1} = \begin{bmatrix} 1/3 & 1/3 \\ 1/3 & -2/3 \end{bmatrix}$$
$P_2$:
$$V^{-1}X = \begin{bmatrix} -1 \\ 7 \end{bmatrix}$$
$P_3$:
$$DV^{-1}X = \begin{bmatrix} -4 \\ 7 \end{bmatrix}$$
$P_4$:
$$VDV^{-1}X = \begin{bmatrix} -1 \\ -11 \end{bmatrix}_{P_4} = AX$$
Observations:
Matrix multiplication $AX$ defines how the entire plane is transformed.
Eigen vectors are the directions that are preserved (Principal axes chosen by $A$).
Eigen values tell how strong the action is along these directions
Spectral/eigen decomposition – same transformation in its natural coordinate system (for $A$)
Example 3: Symmetric, Distinct Eigen Values.
$$A = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix} \quad X = \begin{bmatrix} 5 \\ -8 \end{bmatrix}$$
$$\lambda = \{3, 1\} \quad v_1 = \begin{bmatrix} 1 \\ 1 \end{bmatrix} \quad v_2 = \begin{bmatrix} 1 \\ -1 \end{bmatrix} \quad V^T V = 0$$
Normalized $V$s: $$\begin{bmatrix} 1/\sqrt{2} \\ 1/\sqrt{2} \end{bmatrix}, \begin{bmatrix} 1/\sqrt{2} \\ -1/\sqrt{2} \end{bmatrix}$$
$$\therefore \quad V = \begin{bmatrix} 1/\sqrt{2} & 1/\sqrt{2} \\ 1/\sqrt{2} & -1/\sqrt{2} \end{bmatrix} \qquad V^T = \begin{bmatrix} 1/\sqrt{2} & 1/\sqrt{2} \\ 1/\sqrt{2} & -1/\sqrt{2} \end{bmatrix}$$
$$D = \begin{bmatrix} 3 & 0 \\ 0 & 1 \end{bmatrix}$$
Now, $$V^TX = \begin{bmatrix} -3/\sqrt{2} \\ 13/\sqrt{2} \end{bmatrix}$$
$$DV^TX = \begin{bmatrix} -9/\sqrt{2} \\ 13/\sqrt{2} \end{bmatrix}$$
$$VDV^TX = \begin{bmatrix} 2 \\ -11 \end{bmatrix} = AX$$
Example 4: Symmetric, non distinct
$$A = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix}. \quad \lambda = 2$$
Any vector $X$ is an eigen vector
$$AX = \begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix}\begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} 2x_1 \\ 2x_2 \end{pmatrix} = 2\begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \lambda X$$
Let $v_1 = \begin{pmatrix} 1 \\ 3 \end{pmatrix}$. To get an orthogonal vector, $v_2$, we need $v_1^T v_2 = 0$
$$\Rightarrow (1\ \ 3)\begin{pmatrix} x \\ y \end{pmatrix} = 0$$
$$\Rightarrow x – 3y = 0$$
$$\therefore \quad v_2 = \begin{bmatrix} 3 \\ -1 \end{bmatrix}$$
$$\therefore \quad V = \begin{bmatrix} 1/\sqrt{10} & 3/\sqrt{10} \\ 3/\sqrt{10} & -1/\sqrt{10} \end{bmatrix}$$
$$V^T = V \qquad D = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix}$$
$$VDV^TX = \begin{bmatrix} 10 \\ 16 \end{bmatrix} = VDV^{-1}X$$
Example 5: For $3 \times 3$ distinct eigenvector and symmetric matrix $A$
$$A = \begin{bmatrix} -2 & 4 & -2 \\ 4 & 4 & -4 \\ -2 & -4 & 5 \end{bmatrix} \qquad \text{Eigen values } \lambda: \{-4, 1, 10\}$$
$$V_1 = \begin{bmatrix} 2 \\ -1 \\ 0 \end{bmatrix} \quad V_2 = \begin{bmatrix} 2 \\ 4 \\ 5 \end{bmatrix} \quad V_3 = \begin{bmatrix} 1 \\ 2 \\ -2 \end{bmatrix}$$
Normalized $$V_1 = \dfrac{1}{\sqrt{5}}\begin{bmatrix} 2 \\ -1 \\ 0 \end{bmatrix};\quad V_2 = \dfrac{1}{\sqrt{45}}\begin{bmatrix} 2 \\ 4 \\ 5 \end{bmatrix};\quad V_3 = \dfrac{1}{3}\begin{bmatrix} 1 \\ 2 \\ -2 \end{bmatrix}$$
Manually, $V_1^T V_2$
$$V_1^T V_2 = \dfrac{1}{\sqrt{5}}[2\ -1\ 0]\ \dfrac{1}{\sqrt{45}}\begin{bmatrix} 2 \\ 4 \\ 5 \end{bmatrix}$$
$$= \dfrac{4}{\sqrt{5}\sqrt{45}} – \dfrac{4}{\sqrt{5}\sqrt{45}} + 0.$$
$$= 0.$$
But in $R$, $6\times10^{-7}$. Computational aspect.
If eigen values are equal for a real symmetric $A$.
Let $$A = \begin{bmatrix} 3 & 2 & 4 \\ 2 & 0 & 2 \\ 4 & 2 & 3 \end{bmatrix} \quad \text{with}$$
eigen values $\{8, -1, -1\}$
For $\lambda = -1$
$$V_1 = \begin{bmatrix} 2 \\ 1 \\ 2 \end{bmatrix} $$
$$4x_1 + 2x_2 + 4x_3 = 0$$
$$2x_1 + x_2 + 2x_3 = 0$$
$$4x_1 + 2x_2 + 4x_3 = 0$$
$$x_2 = -2(x_1 + x_3)$$
$$V_2 = \begin{bmatrix} 1 \\ -2 \\ 0 \end{bmatrix} \qquad V_3 = \begin{bmatrix} 0 \\ -2 \\ 1 \end{bmatrix}$$
$$V_2^T \cdot V_3 = (1\ -2\ 0)\begin{pmatrix} 0 \\ -2 \\ 1 \end{pmatrix} = 0+4+0$$
$$\ne 0$$
Not orthogonal.
If we use any orthogonalization process, then we can find an orthogonal $V$ s.t.
$$A = VDV^T = VDV^{-1}$$