Skip to main content

2.13 Eigen decomposition and diagonalization

eigendecomposition (also known as eigenvalue decomposition, spectral decomposition, or diagonalization)

A diagonal matrix is a matrix that has value zero on all off-diagonal elements i.e., they are of the form
$D=\begin{bmatrix}
c_1 & \cdots & 0\\
\vdots&\ddots & \vdots \\
0& \cdots & c_n
\end{bmatrix}$
They allow fast computation of determinants, powers and inverses.The determinant is the product of its diagonal entries, a matrix power $D^k$ is given by each diagonal element raised to the power $k$, and the inverse $D^{-1}$ is the reciprocal of its diagonal elements, if all of them are nonzero.

Definition(Diagonalizable):A matrix $A \in \mathbb{R}^{n \times n}$ is diagonalizable, if it is similar to a diagonal matrix i.e., if there exists an invertable matrix $P \in \mathbb{R}^{n \times n}$ such that $D=P^{-1}AP$.

 Eigen decomposition can be done only on a square matrix.

let $A \in \mathbb{R}^{n \times n}$ and let $\lambda_1,\lambda_2,\ldots,\lambda_n$, be a set of scalars, and let $p_1,p_2,\ldots,p_n$ be set of vectors in $\mathbb{R}^n$.We define $P=[p_1,p_2,\ldots,p_n]$ and let $D \in \mathbb{R}^{n \times n}$ be a diagonal matrix with diagonal entries $\lambda_1,\lambda_2,\ldots,\lambda_n$, then we can show that

$A=PDP^{-1}$

if  and only if $\lambda_1,\lambda_2,\ldots,\lambda_n$ are the eigen values of $A$ and $p_1,p_2,\ldots,p_n$ are the corresponding eigen vectors of $A$.This requires that $P$ must be invertable and $P$ must have full rank.This requires  us to have $n$ linearly independent eigen vectors $p_1,\ldots,p_n$ and forms the basis of $\mathbb{R}^n$.

Theorem:(Eigen Decomposition). A square matrix $A \in \mathbb{R}^{n \times n}$ can be factored into

$A=PDP^{-1}$

where $P \in \mathbb{R}^n$ and $D$ is a diagonal matrix whose diagonal entries are the eigenvalues of $A$, if and only if the eigen vectors of $A$ form the basis of $\mathbb{R}^n$.

This theorem implies that only non defective matrix can be diagonalized and that the columns of $P$ are the $n$ eigen vectors of $A$.

A symmetric matrix $S \in \mathbb{R}^{n \times n}$ can always be diagonalized.

Spectral theorem states that we can find orthonormal eigen vectors .This makes $P$ an orthogonal matrix so that $A=PDP^T$ and $D=P^TAP$

Geometric Intuition

We can interpret the eigendecomposition of a matrix as follows.Let $A$ be a transformation matrix of a linear mapping with respect to the standard basis.$P^{-1}$ performs a basis change from the standard basis into eigen basis. Then the diagonal $D$ scales the vectors along these axes by the eigenvalues $\lambda_i$.Finally, $P$ transforms these scaled vectors back into standard/canonical coordinates.

Advantages

1.Diagonal matrix $D$ can be efficiently be raised to a power. Therefore we can find a matrix power for a matrix $A \in \mathbb{R}^{n \times n}$ via eigen value decomposition(if exist) so that

$A^k= ( PDP^{-1})^k= PD^kP^{-1}$

Computing $D^k$ is efficient because we apply this operation individually to any diagonal element.

2.Assume that eigen decomposition exist $A=PDP^{-1}$ exist, Then

   $det(A)=det(PDP^{-1})=det(P)det(D)det(P^{-1})=det(D)=\prod_i d_{ii}$

This allows efficient computation of the determinant of $A$.

3.The inverse of $A$ is $A^{-1}=(PDP^{-1})^{-1}=PD^{-1}P^{-1}$

$P^{-1}=P^T$ for orthonormal eignen vectors and $D^{-1}$ can be found by taking $1/\lambda_{ii}$

Eg: lets compute the eigen decomposition of  (  university question)

$A=\begin{bmatrix}2 &1 \\
1 & 2
\end{bmatrix}$

step1:Compute the eigen values and eigen vectors
The characteristic polynomial of $A$ is
$det(A-\lambda I)=det \left(\begin{bmatrix}
2-\lambda &1 \\
1 & 2-\lambda
\end{bmatrix}\right)$
$=(2-\lambda)^2-1=\lambda^2-4\lambda+3=(\lambda-3)(\lambda-1)$

Therefore the eigen values of $A$ are $\lambda_1=1$ and $\lambda_2=3$ and the corresponding normalized  eigen vectors are 
$p_1=\frac{1}{\sqrt{2}}\begin{bmatrix}1 \\
-1
\end{bmatrix}$ and 
$p_2=\frac{1}{\sqrt{2}}\begin{bmatrix}1 \\
1
\end{bmatrix}$ 

step2:Check for existence

The eigen vectors $p_1,p_2$ form a basis of $\mathbb{R}^2$. Therefore $A$ can be diagonalized.

step3: construct the matrix P to diagonalize A

We collect the eigenvectors of $A$ in $P$ so that

$P=[p_1,p_2]=\frac{1}{\sqrt{2}}\begin{bmatrix}1 &1 \\
-1 &1
\end{bmatrix}$
We then obtain 
$P^{-1}AP=\begin{bmatrix}1 &0 \\0 &3\end{bmatrix}=D$
Note that $P^{-1}=P^T$ since the eigenvectors form an Orthonormal basis.

Now the eigen decompostion of $A=PDP^T$ is 


import numpy as np
# define matrix
A = array([[2,1],[1,2]])
print("Original Matrix A")
print(A)
# factorize
values, vectors = np.linalg.eig(A)
# create matrix from eigenvectors
P = vectors
print("Normalized Eigen Vectors P")
print(P)
# create inverse of eigenvectors matrix
Pt = np.linalg.inv(P)
print("Inverse of P which is P^T")
print(Pt)
# create diagonal matrix from eigenvalues
D = np.diag(values)
print("diagonal Matrix D with eigen values on the diagonal")
print(D)
# reconstruct the original matrix
print("reconstructed original matrix PDP^T")
B = P.dot(D).dot(Pt)
print(B)

o/p
Original Matrix A 
[[2 1] 
 [1 2]] 
Normalized Eigen Vectors P
 [[ 0.70710678 -0.70710678] 
 [ 0.70710678 0.70710678]]
 Inverse of P which is P^T
 [[ 0.70710678 0.70710678] 
 [-0.70710678 0.70710678]] 
Diagonal Matrix D with eigen values on the digonal 
[[3. 0.]
 [0. 1.]] 
reconstructed original matrix PDP^T 
[[2. 1.] 
 [1. 2.]]

Sympy Code
from sympy import Matrix
M = Matrix(3, 3, [1, 2, 0, 0, 3, 0, 2, -4, 2])
(P, D) = M.diagonalize()
print(M)
print(D)
print(P)
print(P.inv() * M * P)

Matrix([ 
[1, 0, 0], 
[0, 2, 0], 
[0, 0, 3]]) 

Matrix([
 [-1, 0, -1], 
[ 0, 0, -1],
 [ 2, 1, 2]])

Matrix([ 
[1, 0, 0], 
[0, 2, 0], 
[0, 0, 3]])

Matrix([[1, 0, 0], [0, 2, 0], [0, 0, 3]])

Diagonalize the following matrix ( university question)
$A=\begin{bmatrix}
1 & -2 & 0 \\
-2 & 0 & 2 \\
0 & 2 & -1 \\
\end{bmatrix}$


The eigen values are $\lambda_1=0,\lambda_2=3,\lambda=-3$
The eigen vectors are$P$ $(-1, 2, -2), (-2, 1, 2), (2, 2, 1)$


So the Diagonalized matrix is $P^{-1}.A.P$
$\begin{bmatrix}
-3 & 0 & 0 \\
0 & 0 & 0 \\
0 & 0 & 3 \\
\end{bmatrix}$



Comments

Post a Comment

Popular posts from this blog

Mathematics for Machine Learning- CST 284 - KTU Minor Notes - Dr Binu V P

  Introduction About Me Syllabus Course Outcomes and Model Question Paper University Question Papers and Evaluation Scheme -Mathematics for Machine learning CST 284 KTU Overview of Machine Learning What is Machine Learning (video) Learn the Seven Steps in Machine Learning (video) Linear Algebra in Machine Learning Module I- Linear Algebra 1.Geometry of Linear Equations (video-Gilbert Strang) 2.Elimination with Matrices (video-Gilbert Strang) 3.Solving System of equations using Gauss Elimination Method 4.Row Echelon form and Reduced Row Echelon Form -Python Code 5.Solving system of equations Python code 6. Practice problems Gauss Elimination ( contact) 7.Finding Inverse using Gauss Jordan Elimination  (video) 8.Finding Inverse using Gauss Jordan Elimination-Python code Vectors in Machine Learning- Basics 9.Vector spaces and sub spaces 10.Linear Independence 11.Linear Independence, Basis and Dimension (video) 12.Generating set basis and span 13.Rank of a Matrix 14.Linear Mapping...
Post a Comment
Read more

4.3 Sum Rule, Product Rule, and Bayes’ Theorem

 We think of probability theory as an extension to logical reasoning Probabilistic modeling  provides a principled foundation for designing machine learning methods. Once we have defined probability distributions corresponding to the uncertainties of the data and our problem, it turns out that there are only two fundamental rules, the sum rule and the product rule. Let $p(x,y)$ is the joint distribution of the two random variables $x, y$. The distributions $p(x)$ and $p(y)$ are the corresponding marginal distributions, and $p(y |x)$ is the conditional distribution of $y$ given $x$. Sum Rule The addition rule states the probability of two events is the sum of the probability that either will happen minus the probability that both will happen. The addition rule is: $P(A∪B)=P(A)+P(B)−P(A∩B)$ Suppose $A$ and $B$ are disjoint, their intersection is empty. Then the probability of their intersection is zero. In symbols:  $P(A∩B)=0$  The addition law then simplifies to: $P(...
Post a Comment
Read more

5.1 Optimization using Gradient Descent

Since machine learning algorithms are implemented on a computer, the mathematical formulations are expressed as numerical optimization methods.Training a machine learning model often boils down to finding a good set of parameters. The notion of “good” is determined by the objective function or the probabilistic model. Given an objective function, finding the best value is done using optimization algorithms. There are two main branches of continuous optimization constrained and unconstrained. By convention, most objective functions in machine learning are intended to be minimized, that is, the best value is the minimum value. Intuitively finding the best value is like finding the valleys of the objective function, and the gradients point us uphill. The idea is to move downhill (opposite to the gradient) and hope to find the deepest point. For unconstrained optimization, this is the only concept we need,but there are several design choices. For constrained optimization, we need to intr...
Post a Comment
Read more