Eigenvalues and EigenvectorsGeometrically, an eigenvector, corresponding to a real nonzero eigenvalue, points in a direction in which it is stretched by the transformation and the eigenvalue is the factor by which it is stretched. If the eigenvalue is negative, the direction is reversed.
Definition:
Let A∈Rn×n be a square matrix. Then λ∈R is an eigen value of A and x∈Rn/0 is the corresponding eigen vector of A if
Ax=λx
We call this as Eigenvalue equation
The following statements are equivalent
λ is the eigen value of A
There exist an x∈Rn/0 with Ax=λx or equivalently (A−λIn)x=0 can be solved non trivially i.e., x≠0
rank(A−λI)≤n
det(A−λI)=0
collinearity and codirection
Two vectors that point in the same direction are called codirected.Two vectors are collinear if they point in the same or opposite direction.
if x is an eigen vector of A associated with eigen values λ then for any c∈R/0, it holds that cx is an eigenvector of A with the same eigen value since
A(cx)=cAx=cλx=λ(cx)
Thus all vectors that are collinear to x are also eigenvectors of A
Characteristic Polynomial
For λ∈R and a square matrix A∈Rn×n
PA(λ)=det(A−λI)=(−1)nλn+Cn−1λn−1+…+C2λ2+C1λ+C0
The characteristic polynomial will allow us to compute eigen values and eigen vectors.
In the characteristic polynomial
C0=det(A)
Cn−1=(−1)n−1tr(A)
λ∈R is eigenvalue of A∈Rn×n if and only if λ is the root of the characteristic polynomial.
The algebraic multiplicity of λi is the number of times the root appears in the characteristic polynomial.
Eigen space and eigen spectrum
For A∈Rn×n,the set of all eigen vectors associated with an eigen value λ spans a subspace of Rn, which is called the eigen space of A with respect to λ and is denoted by Eλ.
The set of all eigen values of A is called eigen spectrum or spectrum of A.
If λ is the eigen value of A∈Rn×n, then the corresponding eigen space Eλ is the solution space of the homogenious system of linear equation (A−λI)x=0. Geometrically the eigen vector corresponds to a non zero eigen value points in a direction that is stretched by the linear mapping. The eigen value is the factor by it is stretched.If the eigen value is negative , the direction of the stretching is flipped.
properties
The identity matrix I∈Rn×n has characteristic polynomial (1−λ)n=0, which has only one eigenvalue λ=1 that occures n times.Moreover Ix=1x holds for all vectors x∈Rn.Because of this eigenspace spans all the dimensions and all standard basis vectors of Rn are eigen vectors of I.
A matrix A and its transpose AT having the same eigen values, but not necessarily the same eigen vectors.
The eigen space is the null space(kernal) of (A−λI)
Similar matrices having same eigen value.Therefore linear mapping matrix has an eigen value that is independent of the basis.
symmetric positive definite matrices always have positive real eigen values.
Determinant of a matrix is the product of its eigen values.
Trace of a matrix is the sum of its eigen values.
Ax=λx so A−1Ax=A−1λx ie; A−1x=1λx ie; eigen values of A−1 is 1λ
Ax=λx so A2x=λ2x ie; in general Akx=λkx
Applications
Eigenvalues and eigenvectors play a significant role in various aspects of machine learning. Some of the key applications of eigenvalues and eigenvectors in machine learning are as follows:
Dimensionality Reduction: One of the most common applications of eigenvalues and eigenvectors in machine learning is in dimensionality reduction techniques like Principal Component Analysis (PCA). PCA finds the principal components (eigenvectors) of the data, which are the directions along which the data varies the most. The corresponding eigenvalues indicate the amount of variance captured by each principal component. By retaining only the top eigenvalues and their corresponding eigenvectors, PCA allows for effective dimensionality reduction while preserving the most important patterns in the data.
Image Compression: Eigenvalues and eigenvectors are used in image compression techniques like Singular Value Decomposition (SVD). SVD decomposes an image matrix into its constituent eigenvalues and eigenvectors. By keeping only the most significant eigenvalues and their corresponding eigenvectors, images can be efficiently compressed without losing critical visual information.
Spectral Clustering: Spectral clustering is a powerful technique used in unsupervised learning to partition data into clusters. It utilizes the eigenvectors of similarity or affinity matrices to find the cluster assignments. Eigenvectors corresponding to the smallest eigenvalues provide information about the cluster structure of the data.
Recommender Systems: Collaborative filtering in recommender systems can use the concepts of eigenvectors to identify latent factors and represent user-item interactions in lower-dimensional spaces. This helps in making personalized recommendations efficiently.
Natural Language Processing: In natural language processing tasks like topic modeling or latent semantic analysis, eigenvectors can be used to identify latent topics or dimensions in the text data, making it easier to discover underlying structures and patterns.
Graph Analysis: In graph-based machine learning algorithms, eigenvectors are used to calculate centrality measures, such as PageRank in web graph analysis, which helps to rank web pages based on their importance.
Neural Networks: In some neural network architectures, such as autoencoders, the hidden layers' activations correspond to the eigenvectors of the covariance matrix of the input data. Understanding the eigenvectors can provide insights into the network's internal representations and how it captures relevant features in the data.
In summary, eigenvalues and eigenvectors have diverse applications in machine learning, ranging from dimensionality reduction and clustering to image compression and graph analysis. They enable efficient data representation, feature extraction, and structure discovery, making them powerful tools for understanding and processing complex data in various machine learning tasks.
Computing the Eigenvalues, eigen vectors and eigen spaces
Step1. Find the roots of the characteristic polynomial to find the eigen values.
Step2:Find the eigen vectors that corresponds to the eigen values by finding vectors x such that (A−λI)x=0, which the null space of the matrix A−λI.
Example
Find the eigenvalues and eigenvectors for
A=[64−3−1]Solution
If
Ax=λxthen
|A−λI|=0
A−λI=[6−λ4−3−1−λ]
Taking determinants of both sides, we get the characteristic polynomial
(6−λ)(−1−λ)+12=0
λ2−5λ+6=0
(λ−2)(λ−3)=0
The eigenvalues are
λ=2 and λ=3
To find the eigenvectors, we plug the eigenvalues into the equation
(A−λI)x=0
and find the null space of the left hand side. For the eigenvalue λ=2, we have
A−λI=[44−3−3]The first row gives
x1=−x2so that an eigenvector corresponding to the eigenvalue λ=2 is
x=[1−1]For the eigenvalue λ=3, we have
A−λI=[34−3−4]The first row gives
3x1=−4x2
so that an eigenvector corresponding to the eigenvalue λ=3 is
x=[3−4]Typically, we want to normalize the eigenvectors, that is find unit eigenvectors. We get
v1=[1√2−1√2]and
v2=[35−45]
import numpy as np
A=np.array([[6,4],[-3,-1]])
print(" Matrix A")
print(A)
eigva,eigv=np.linalg.eig(A)
print("eigen values")
print(eigva)
print("eigen vectors normalized")
print(eigv)
o/p
Matrix A
[[ 6 4]
[-3 -1]]
eigen values
[3. 2.]
eigen vectors
[[ 0.8 -0.70710678]
import numpy as np
A=np.array([[4,2],[1,3]])
print(" Matrix A")
print(A)
eigva,eigv=np.linalg.eig(A)
print("eigen values")
print(eigva)
print("eigen vectors un normalized")
print(eigv[:,0]*np.sqrt(5))
print(eigv[:,1]*np.sqrt(2))
o/p
Matrix A
[[4 2]
[1 3]]
eigen values
[5. 2.]
eigen vectors un normalized
[2. 1.]
[-1. 1.]
sympy code
from sympy import Matrix
M = Matrix(3, 3, [2, 1,-2, 1, 0, 0, 1, 0, 0])
print(M.charpoly().as_expr())
print(M.eigenvals())
print(M.eigenvects())
output:
lambda**3 - 2*lambda**2 + lambda
{1: 2, 0: 1}
[(0, 1, [Matrix([ [0], [2], [1]])]), (1, 2, [Matrix([ [1], [1], [1]])])]
Geometric Multiplicity and algebraic multiplicity
Let λi be an eigenvalue of a square matrix A. Then the geometric multiplicity of λi is the number of linearly independent eigen vectors associated with λi.
The algebraic multiplicity specifies how many times the eigen value λi occurs.
Remark. A specific eigenvalue’s geometric multiplicity must be at least one because every eigenvalue has at least one associated eigenvector. An eigenvalue’s geometric multiplicity cannot exceed its algebraic multiplicity,but it may be lower.
Example:
The matrix A=[2102] has two repeated eigen values λ1=λ2=2 and hence an algebraic multiplicity of 2. The eigenvalue has however only one distinct eigen vector x=[10] and thus geometric multiplicity 1.
Eigen Basis
The eigenvectors x1,x2,…,xn of a matrix A∈Rn×n with n distinct eigenvalues λ1,λ2,…,λn are linearly independent.This states that eigen vectors of a matrix with n distinct eigen values form a basis of Rn.
A square matrix A∈Rn×n is defective, if it possesses fewer than n linearly independent eigen vectors.It cannot have n distict eigenvalues.
Spectral Theorem
Given a matrix A∈Rn×n, we can always obtain a symmetric positive definite matrix S∈Rn×n by defining
S=ATA
If rk(A)=n, then S=ATA is symmetric, positive definite.
Symmetry: Symmetry requires S=ST
So S=(ATA)=AT.(AT)T=(ATA)T=ST
Positive Semi Definiteness: this requires xTSx≥0 i.e.,xTSx=xTATAx=(xTAT)(Ax)=(Ax)T(Ax)≥0. The dot product is sum of squares which are non negative.
If A∈Rn×n is symmetric, there exists an orthonormal basis of the corresponding vector space v consisting of eigenvectors of A, and each eigen value is real.
The direct implication of spectral theorem is that eigen decomposition of a symmetric matrix A exist and we can find ortho normal basis of eigen vectors so that A=PDPT, where D is the diagonal matrix with eigen values and columns of P contains eigen vectors. Eigen decomposition will be discussed later.
The eigen vectors associated with the same eigen values are not orthogonal( geometric multiplicity greater than 1). We can use Gram-Schidt algorithm for orthogonalization in this case.
Relationship Between Determinant and Trace
The determinant of a matrix A∈Rn×n is the product of its eigenvalues .i.e,
det(A)=∏ni=1λi
The trace of a matrix A∈Rn×n is the sum of its eigen values.i.e,
tr(A)=∑ni=1λi
where λi are eigenvalues of A.
More Example:
Compute the Eigen value and eigen vectors of
A=[1011]
Characteristic polynomial
p(λ)=|A−λI|=|1−λ011−λ|=(1−λ)2=0 So λ=1 is the only root of p and therefore the only eigenvalue of A
To compute the eigen space, we need to compute the null space of A−λI
(A−1.I)x=0⟹[0010]x=0
So the only eigen vector is
E1=[01]Compute the Eigen value and eigen vectors of
A=[−2221]Characteristic polynomial
p(λ)=|A−λI|=|−2−λ221−λ|=(−2−λ)(1−λ)−4=0
λ2+λ−6=0
so the eigenvalues are λ=−3 and λ=2 .Note that the product -6 is the determinant of the matrix and the sum -1 is the trace ( sum of the diagonal element)
when λ=−3 the null space of A−λI is
A−λI=[1224]is
E1=[2−1] and is the eigen space corresponds to the eigen value λ=−3
when λ=2 the null space of A−λI is
A−λI=[−422−1]is
E2=[1/21] and is the eigen space corresponds to the eigen value λ=2
Find the eigen values of the following matrix in terms of k. Can you find an eigen vector corresponding to each of the eigen values?
[1k21] Characteristic polynomial can be found by
p(λ)=|A−λI|=|1−λk21−λ|==0 (1−λ)2−2k=0
λ2−2λ+(1−2k)=0
λ=2±√4−4(1−2k)2
λ=2±2√2k2
λ=1±√2k are the eigen values
Lets find the eigen vectors
When λ=1+√2k the null space of (A−λI) gives eigen vector corresponds to the eigen value 1+√2k
[1−1−√2kk21−1−√2k] [−√2kk2−√2k]
[1−√k/21−√k/2]
[1−√k/200]So the null space is [√k/21], which is the eigen vector
similarly when λ=1−√2k the null space of (A−λI) gives eigen vector corresponds to the eigen value 1−√2k
and the eigen vector is
[−√k/21]
Compute the Eigen value of a 3 x 3 matrix
A=[−12222−12−12]Characteristic Polynomial can be found by setting |A−λI|=0
[−1−λ2222−λ−12−12−λ]=0
(−1−λ)(4−4λ+λ2−1)−2(4−2λ+2)+2(−2−4+2λ)
(−1−λ)(3−4λ+λ2)−2(6−2λ)+2(−6+2λ)
−λ3+3λ2+9λ−27=0
λ3−3λ2−9λ+27=0
(λ−3)(λ2−9)=0
(λ−3)(λ+3)(λ−3)=0
So the eigen values are λ=3(with algebraic multiplicity 2) and λ=−3
Find the eigen values and eigen vectors of the following matrix
A=[5−21−210101]Characteristic Polynomial can be found by setting |A−λI|=0
|5−λ−21−21−λ0101−λ| (5−λ)(1−λ)2+2(−2(1−λ))−(1−λ)
(5−λ)(λ2−2λ+1)−4+4λ−1+λ
(5−λ)(λ2−2λ+1)+5λ−5
5λ2−10λ+5−λ3+2λ2−λ+5λ−5
λ3−7λ2+6λ
λ(λ2−7λ+6)
So the eigen values are λ=0,λ=6, λ=1
The eigen vector corresponds to λ=0 is the null space of A−λI
A=[5−21−210101]
Exchanging R1 and R3
A=[101−2105−21]
R2=−2×R1+R2
A=[1010125−21]
R3=−5×R1+R3 then R3=R3/−2
A=[101012012]
R3=R3−R2
A=[101012000]
So the eigen vector corresponds to the eigen value λ=0 is
[12−1]Similarly the eigen vector corresponds to the eigen value λ=1 is
[012]Similarly the eigen vector corresponds to the eigen value λ=6 is
[5−21]
Find the characteristic equation, eigenvalues, and eigenspaces corresponding to each eigenvalue of the following matrix
A=[204030012]Characteristic Polynomial can be found by setting |A−λI|=0
|2−λ0403−λ0012−λ|=0
(2−λ)(3−λ)((2−λ)=0So
λ=2 or
λ=3The eigen vector corresponds to λ=2 can be found by finding the null space of A−λI
|004010010|the null space is
[100],
Similarly the eigenvector corresponds to λ=3 can be found by finding the null space of A−λI
|−10400001−1|the null space is
[−4−1−1],
So the eigen space consist of following vectors
Ev1=[100]
Find the eigen values and eigen vectors corresponds to
A=[4213] ( university question)
Characteristic Polynomial can be found by setting |A−λI|=0
|4−λ213−λ|=0
(4−λ)(3−λ)−2=0
λ2−7λ+10=0
(λ−5)(λ−2)=0
So
λ=2 or λ=5
The eigen vector corresponds to λ=2 can be found by finding the null space of A−λI
|2211|the null space is
[1−1],
The eigen vector corresponds to λ=5 can be found by finding the null space of A−λI
|−121−2|the null space is
[21],
So the eigen values are
λ1=2 and λ2=5
and the corresponding eigen vectors are
[1−1], and
Find the characteristic equation. Eigen values and Eigen spaces for the following matrix.
( university qn)
[21−2100100]
Characteristic equation can be found by evaluating |A−λI|=0
|2−λ1−21−λ010λ|=0
(2−λ)λ2−1(−λ)−2(λ)=0
2λ2−λ3+λ−2λ=0
λ3−2λ2+λ=0
λ(λ2−2λ+1)=0 characteristic equation
λ(λ−1)(λ−1)=0
λ=0 or λ=1 eigen values( λ=1 has algebraic multiplicity=2)
The eigen vector corresponds to λ=0 can be found by finding the null space of A−λI
[21−2100100]x=0 So x=[021]
Similarly the eigenvector corresponds to λ=1 is
[11−21−1010−1]x=0x=[111]
Find the eigen values and eigen vectors corresponds to ( university question)
A=[8426]
Characteristic Polynomial can be found by setting |A−λI|=0
|8−λ426−λ|=0
(8−λ)(6−λ)−8=0
λ2−14λ+40=0
(λ−4)(λ−10)=0
So
λ=4 or λ=10
The eigen vector corresponds to λ=4 can be found by finding the null space of A−λI
|4422|the null space is
[1−1],
The eigen vector corresponds to λ=10 can be found by finding the null space of A−λI
|−242−4|the null space is
[21],
So the eigen values are
λ1=4 and λ2=10
and the corresponding eigen vectors are
[1−1], and
[21]
Comments
Post a Comment