# Spectral decomposition

  
This work by Jephian Lin is licensed under a [Creative Commons Attribution 4.0 International License](http://creativecommons.org/licenses/by/4.0/).


```python
import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits import mplot3d
from scipy import linalg as LA
import sympy
```


```python
def spec_decom(A, tol=0.0001):
    n = A.shape[0]
    vals,vecs = LA.eigh(A)
    
    inds = np.where((vals[1:] - vals[:-1]) > tol)[0]
    starts = np.hstack([np.array([0]), inds+1])
    ends = np.hstack([inds+1, np.array([n])])
    
    dist_vals = vals[starts]
    projs = np.zeros((len(dist_vals), n, n))
    i = 0
    for s,e in zip(starts,ends):
        space = vecs[:,s:e]
        projs[i] = space.dot(space.T)
        i += 1
    
    return dist_vals, projs
```

## Main idea

A matrix $A$ is **symmetric** if $A^\top = A$.  

Every symmetric matrix $A$ can be written as  
$$ A = \sum_{i=1}^q \lambda P_i$$
such that $\sum_{i=1}^q P_i = I$, $P_iP_j = O$ if $i\neq j$, and $P_i^2 = P_i$.  
This is called the **spectral decomposition** of $A$.  

Each $P_i$ is in fact a projection matrix onto a space $E_i$.  
For any vector ${\bf v}$ in $E_i$, $A{\bf v} = \lambda_i{\bf v}$.  
We call $\lambda_i$ an **eigenvalue** ,  
call ${\bf v}$ an **eigenvector** ,  
and $E_i$ an **eigenspace** of $A$.

## Side stories

- eigenvalue, eigenvector, eigenspace
- spectral decomposition = projection then scale

## Experiments

###### Exercise 1
Let  
```python
A = np.ones((5,5), dtype=float) - np.eye(5, dtype=float)
v1 = np.ones((5,), dtype=float)
v2 = np.array([1,-1,0,0,0], dtype=float)
```

###### 1(a)
Check if ${\bf v}_1$ is an eigenvector of $A$.  
If yes, what is the eigenvalue?


```python
### your answer here
```

###### 1(b)
Check if the $i$-th entry of ${\bf v}_2$ is zero then the $i$-th entry of $A{\bf v}_2$ is also zero.  


```python
### your answer here
```

###### 1(c)
Check if ${\bf v}_2$ is an eigenvector of $A$.  
If yes, what is the eigenvalue?


```python
### your answer here
```

###### Exercise 2
Let  
```python
A = np.array([[2,-1,-1],
              [-1,2,-1],
              [-1,-1,2]]) / 3
v1 = np.array([1,1,1])
v2 = np.array([1,-1,0])
```
Since checking the zero is tiring, we will use a different approach to test whether a vector is an eigenvector.  
The following are equivalent:  
- $A{\bf v} = \lambda{\bf v}$ for some $\lambda$
- $A{\bf v}$ is a multiple of ${\bf v}$
- $A{\bf v}$ and ${\bf v}$ are parallel (zero vectors are considered to be parallel to any vector)
- $|\langle A{\bf v}, {\bf v}\rangle| = \|A{\bf v}\|\|{\bf v}\|$

###### 2(a)
Compute $|\langle A{\bf v}_1, {\bf v}_1\rangle|$ and $\|A{\bf v}_1\|\|{\bf v}_1\|$.  
Then see if they are close.


```python
### your answer here
```

###### 2(b)
Do the same for ${\bf v}_2$.


```python
### your answer here
```

###### 2(c)
Run and understand the code below.  

```python
%matplotlib notebook

tol = 0.1
vs = 5*np.random.randn(3,10000)
Avs = A.dot(vs)
dots = np.abs(np.sum(vs * Avs, axis = 0)) ### |<Avi, vi>|'s
Avs_length = np.linalg.norm(Avs, axis=0) ### ||Avi||'s
vs_length = np.linalg.norm(vs, axis=0) ### ||vi||'s
diff = np.abs( dots - Avs_length*vs_length)
mask = (diff < tol) ### mask for potential eigenvectors
eigvecs = vs[:,mask]

ax = plt.axes(projection='3d')
ax.set_xlim(-5,5)
ax.set_ylim(-5,5)
ax.set_zlim(-5,5)
ax.scatter(eigvecs[0], eigvecs[1], eigvecs[2])
```
What is the plane in the output?  
Change `tol` to 1 or 2.  Then you will see a vague straight line appears.  Why?


```python
### your answer here
```

## Exercises

###### Exercise 3
Let  
```python
A = np.array([[0,1,0,0,0,1], 
              [1,0,1,0,0,0], 
              [0,1,0,1,0,0], 
              [0,0,1,0,1,0], 
              [0,0,0,1,0,1], 
              [1,0,0,0,1,0]])
vals,projs = spec_decom(A)
```
Here `vals` are all the $\lambda_i$'s and `projs` are all the $P_i$'s.  

###### 3(a)
Check if $A = \sum_{i=0}^3\lambda_iP_i$.  
Can you do it without any for loop?  
Note:  You might need `np.set_printoptions(precision=1, suppress=True)`.


```python
### your answer here
```

###### 3(b)
Let  
```python
v = np.ones((6,))
```
Check if $A{\bf v} = \sum_{i=0}^3 \lambda_i P_i{\bf v}$.


```python
### your answer here
```

###### 3(c)
Pick any $0\leq i,j\leq 3$.  
Check if $P_iP_j = O$.


```python
### your answer here
```

###### 3(d)
Pick any $0\leq i\leq 3$.  
Check if $P_i^2 = P_i$.


```python
### your answer here
```

##### Exercise 4
Let  
```python
%matplotlib inline
plt.axis('equal')
A = np.array([[2,1],
              [1,2]])
t = np.linspace(0, 2*np.pi, 36)
xs = np.cos(t)
ys = np.sin(t)
vs = np.vstack([xs, ys])
Avs = A.dot(vs)
```

###### 4(a)
Plot a red point at the origin.  
Plot the points (columns) in `vs` using `c=t` .  
Then plot the points (columns) in `Avs` using `c=t` .  
Interpret the output using the spectral decomposition.


```python
### your answer here
```

###### 4(b)
Do the same with  
```python
A = np.array([[1,1],
              [1,1]])
```


```python
### your answer here
```

##### Exercise 5
Let  
```python
A = np.array([[0,1,0,0,0,1], 
              [1,0,1,0,0,0], 
              [0,1,0,1,0,0], 
              [0,0,1,0,1,0], 
              [0,0,0,1,0,1], 
              [1,0,0,0,1,0]])
vals,projs = spec_decom(A)

k = 3
```

###### 5(a)
Let  
```python
B = k*A
vals_B,projs_B = spec_decom(B)
```
Find a relation between `vals` and `vals_B` using `k` .  
Find a relation between `projs` and `projs_B` .


```python
### your answer here
```

###### 5(b)
Let  
```python
B = A + k*np.eye(6)
vals_B,projs_B = spec_decom(B)
```
Find a relation between `vals` and `vals_B` using `k` .  
Find a relation between `projs` and `projs_B` .


```python
### your answer here
```

###### 5(c)
It looks like $\lambda=1$ is an eigenvalue of $A$.  
Use `sympy.Matrix` to find the null space of $A - \lambda I$.  
Find a projection matrix of it, and compare it with the corresponding projection matrix in `projs` .


```python
### your answer here
```

d2dd7510c8c980a783d2544bea025ebf59ed1b9f
ipynb
Jupyter Notebook
Mathematics/Linear Algebra/0.0b Supplement of MIT Course - Concept Explanations with Problems_and_Questions to Solve/09-Spectral-decomposition.ipynb
okara83/Becoming-a-Data-Scientist
f09a15f7f239b96b77a2f080c403b2f3e95c9650
MIT
Mathematics/Linear Algebra/0.0b Supplement of MIT Course - Concept Explanations with Problems_and_Questions to Solve/09-Spectral-decomposition.ipynb
okara83/Becoming-a-Data-Scientist
f09a15f7f239b96b77a2f080c403b2f3e95c9650
MIT
Mathematics/Linear Algebra/0.0b Supplement of MIT Course - Concept Explanations with Problems_and_Questions to Solve/09-Spectral-decomposition.ipynb
okara83/Becoming-a-Data-Scientist
f09a15f7f239b96b77a2f080c403b2f3e95c9650
MIT
2022-02-09T15:41:33.000Z
2022-02-11T07:47:40.000Z
Qwen/Qwen-72B
1. YES
2. YES