<jupyter_start><jupyter_text>Diagonalization ![Creative Commons License](https://i.creativecommons.org/l/by/4.0/88x31.png)  This work by <NAME> is licensed under a [Creative Commons Attribution 4.0 International License](http://creativecommons.org/licenses/by/4.0/).<jupyter_code>import numpy as np
import matplotlib.pyplot as plt
from scipy import linalg as LA
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<jupyter_output><empty_output><jupyter_text>Main idea For every $n\times n$ symmetric matrix $A$, there is an orthogonal basis $\beta = {\{\bf u}_1, \ldots, {\bf u}_n\}$ and $n$ numbers $\lambda_1,\ldots,\lambda_n$ such that $A{\bf u}_i=\lambda_i{\bf u}_i$ for all $i$.  Recall that $\lambda_i$'s are the eigenvalues and   ${\bf u}_i$'s are the eigenvectors.  We call $\beta$ an **eigenbasis** of $A$.Let $Q$ be the matrix whose columns are vectors in $\beta$ and $D$ the diagonal matrix whose diagonal entries are $\lambda_1,\ldots,\lambda_n$.  Then  $$AQ = A\begin{bmatrix} | & ~ & | \\ {\bf u}_1 & \cdots & {\bf u}_n \\ | & ~ & | \end{bmatrix} = \begin{bmatrix} | & ~ & | \\ \lambda_1{\bf u}_1 & \cdots & \lambda_n{\bf u}_n \\ | & ~ & | \end{bmatrix} = \begin{bmatrix} | & ~ & | \\ {\bf u}_1 & \cdots & {\bf u}_n \\ | & ~ & | \end{bmatrix}\begin{bmatrix} \lambda_1 & ~ & ~ \\ ~ & \ddots & ~ \\ ~ & ~ & \lambda_n \end{bmatrix} = QD.$$  Equivalently, for every symmetric matrix $A$, there is an orthogonal matrix $Q$ and a diagonal matrix $D$ such that  $$A = QDQ^\top \text{ and } D = Q^\top AQ$$  with $Q^\top Q = QQ^\top = I$.  Thus, $A$ can also be written as  $$A = QDQ^\top = \sum_{i = 1}^n \lambda_i {\bf u}_i{\bf u}_i^\top.$$  Note that each ${\bf u}_i{\bf u}_i^\top$ is a projection matrix onto the straight line spanned by ${\bf u}_i$.  Side stories - `LA.eigh`- eigenbasis  Experiments  Exercise 1Let  ```pythonA = np.eye(3) - np.ones((3,3)) / 3vals,vecs = LA.eigh(A)D = np.diag(vals)Q = vecs```<jupyter_code>A = np.eye(3) - np.ones((3,3)) / 3
vals,vecs = LA.eigh(A)
D = np.diag(vals)
Q = vecs
Q
Q.T.reshape(3,3,1)
Q.T.reshape(3,1,3)
np.sum(vals.reshape(3,1,1) * Q.T.reshape(3,3,1) * Q.T.reshape(3,1,3), axis=0)
vals.dot( Q.T.reshape(3,3,1) * Q.T.reshape(3,1,3) )<jupyter_output><empty_output><jupyter_text>1(a)Verify that $A = QDQ^\top$ and $Q^\top Q = QQ^\top = I$.<jupyter_code>### your answer here<jupyter_output><empty_output><jupyter_text>1(b)Let ${\bf u}$ be the $i$-th column of $Q$ and $\lambda$ the $i$-th element of `vals`.  Verify that $A{\bf u} = \lambda{\bf u}$.<jupyter_code>### your answer here<jupyter_output><empty_output><jupyter_text>1(c)Verify that $$A = \sum_i \lambda_i {\bf u}_i{\bf u}_i^\top,$$  where $\lambda_i$ is the $i$-th element of `vals` and ${\bf u}_i$ is the $i$-th column of $Q$.<jupyter_code>### your answer here<jupyter_output><empty_output><jupyter_text>1(d)Let  ```pythonv = np.array([1,1,1])```What are the projections of ${\bf v}$ onto ${\bf u}_0$, ${\bf u}_1$, and ${\bf u}_2$?<jupyter_code>### your answer here<jupyter_output><empty_output><jupyter_text>1(e)Find a matrix $B$ such that  $A{\bf u}_0 = 2{\bf u}_0$  $A{\bf u}_1 = 2{\bf u}_1$  $A{\bf u}_2 = 3{\bf u}_2$.<jupyter_code>### your answer here<jupyter_output><empty_output><jupyter_text>Exercises  Exercise 2Let  ```pythonA = np.eye(3) - 2*np.ones((3,3)) / 3vals,vecs = LA.eigh(A)D = np.diag(vals)Q = vecs```Use `D` and `Q` to find the spectral decomposition of $A$.  Compare your answer with `spec_decom(A)` .<jupyter_code>### your answer here<jupyter_output><empty_output><jupyter_text>Exercise 3Let $E$ be a matrix.  The **Frobenius norm** of $E$ is defined as $\|E\| = \sqrt{\operatorname{tr}(E^\top E)}$.  Let  ```pythonA = np.eye(3) - 2*np.ones((3,3)) / 3vals,vecs = LA.eigh(A)D = np.diag(vals)Q = vecs```  3(a)Pick a column vector ${\bf u}$ of $Q$ and let $P = {\bf u}{\bf u}^\top$.  Find $\|P\|$.<jupyter_code>### your answer here<jupyter_output><empty_output><jupyter_text>3(b)Let  ```pythondist_vals, projs = spec_decom(A)```Pick a matrix $P$ in `projs` and find $\|P\|^2$.  If you look back at `vals`, can you guess the norm of each projection matrix?<jupyter_code>### your answer here<jupyter_output><empty_output><jupyter_text>Exercise 4Let  ```pythonarr = plt.imread('circle.png')vals,vecs = LA.eigh(arr)```and $n = 216$.  Thus, `arr` is an $n\times n$ matrix $A$.  Let $\lambda_0\leq\ldots\leq\lambda_{n-1}$ be the eigenvalues of $A$ and ${\bf u}_0,\ldots {\bf u}_{n-1}$.    4(a)Let  ```pythonmask = (np.abs(vals) > 10)vals_m = vals[mask]vecs_m = vecs[:,mask]```How many eigenvalues of `arr` have their absolute values greater than $10$?<jupyter_code>### your answer here<jupyter_output><empty_output><jupyter_text>4(a)Let $S$ be a subset of $\{0,\ldots, n-1\}$.  We have the inequality  $$\|A - \sum_{i\in S} \lambda_i{\bf u}_i{\bf u}_i^\top\| = \|\sum_{i\notin S}\lambda_i{\bf u}_i{\bf u}_i^\top\|\leq \sum_{i\notin S}\|\lambda_i{\bf u}_i{\bf u}_i^\top\|\leq \sum_{i\notin S}|\lambda_i|.$$  In other words, we can approximate $A$ by $\sum_{i\in S} \lambda_i{\bf u}_i{\bf u}_i^\top$ for some subset $S$.  Let $S = \{i: |\lambda_i| > 10\}$.  Calculate $\sum_{i\in S} \lambda_i{\bf u}_i{\bf u}_i^\top$.<jupyter_code>### your answer here<jupyter_output><empty_output><jupyter_text>4(b)Let `approx` be your previous answer.  Use `plt.imshow(approx, cmap='Greys_r')` to see if the approximation looks good or not.  Note that `arr` occupies $n\times n$ units memory.  In contrast, if $|S| = k$, then $\{\lambda_i:i\in S\}$ occupies $k$ units of memory and $\{{\bf u}_i: i\in S\}$ occupies $n\times k$ units of memory.  In total, `approx` can be stored with $(n+1)\times k$ units of memory.<jupyter_code>### your answer here<jupyter_output><empty_output><jupyter_text>Exercise 5Let  ```pythonA = np.array([[1,2,3],              [0,2,3],              [0,0,3]])vals,vecs = LA.eig(A)D = np.diag(vals)Q = vecs```  5(a)Verify that $A = QDQ^{-1}$.  You may use `LA.inv` to calculate the inverse.<jupyter_code>### your answer here<jupyter_output><empty_output><jupyter_text>5(b)Let ${\bf u}$ be the $i$-th column of $Q$ and $\lambda$ the $i$-th element of `vals`.  Verify that $A{\bf u} = \lambda{\bf u}$.<jupyter_code>### your answer here<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.20314627136590532, 'fraction_numerical': 0.019966722129783693, 'mean_word_length': 4.101851851851852, 'pattern_counts': {'":': 0, '<': 62, '<?xml version=': 0, '>': 65, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '15', 'dir': 'jupyter-structured-clean-dedup', 'id': '324606', 'license': 'MIT', 'n_tokens_mistral': 2731, 'n_tokens_neox': 2640, 'n_words': 681, 'path': 'Mathematics/Linear Algebra/0.0b Supplement of MIT Course - Concept Explanations with Problems_and_Questions to Solve/12-Diagonalization.ipynb', 'repo_name': 'okara83/Becoming-a-Data-Scientist', 'size': '6616'}