# 17 Pre-Class Assignment: Decompositions¶

## 1. Matrix Decomposition¶

DO THIS: Watch the following video and answer the questions below.

from IPython.display import YouTubeVideo


Consider the following code to calculate the $$A = Q\Lambda Q^{-1}$$ eivendecomposition.

%matplotlib inline
import matplotlib.pylab as plt
import numpy as np
import sympy as sym
sym.init_printing(use_unicode=True)

---------------------------------------------------------------------------
ModuleNotFoundError                       Traceback (most recent call last)
<ipython-input-2-e3122a161773> in <module>
----> 1 get_ipython().run_line_magic('matplotlib', 'inline')
2 import matplotlib.pylab as plt
3 import numpy as np
4 import sympy as sym
5 sym.init_printing(use_unicode=True)

~/REPOS/MTH314_Textbook/MakeTextbook/envs/lib/python3.9/site-packages/IPython/core/interactiveshell.py in run_line_magic(self, magic_name, line, _stack_depth)
2342                 kwargs['local_ns'] = self.get_local_scope(stack_depth)
2343             with self.builtin_trap:
-> 2344                 result = fn(*args, **kwargs)
2345             return result
2346

~/REPOS/MTH314_Textbook/MakeTextbook/envs/lib/python3.9/site-packages/decorator.py in fun(*args, **kw)
230             if not kwsyntax:
231                 args, kw = fix(args, kw, sig)
--> 232             return caller(func, *(extras + args), **kw)
233     fun.__name__ = func.__name__
234     fun.__doc__ = func.__doc__

~/REPOS/MTH314_Textbook/MakeTextbook/envs/lib/python3.9/site-packages/IPython/core/magic.py in <lambda>(f, *a, **k)
185     # but it's overkill for just that one bit of state.
186     def magic_deco(arg):
--> 187         call = lambda f, *a, **k: f(*a, **k)
188
189         if callable(arg):

~/REPOS/MTH314_Textbook/MakeTextbook/envs/lib/python3.9/site-packages/IPython/core/magics/pylab.py in matplotlib(self, line)
97             print("Available matplotlib backends: %s" % backends_list)
98         else:
---> 99             gui, backend = self.shell.enable_matplotlib(args.gui.lower() if isinstance(args.gui, str) else args.gui)
100             self._show_matplotlib_backend(args.gui, backend)
101

~/REPOS/MTH314_Textbook/MakeTextbook/envs/lib/python3.9/site-packages/IPython/core/interactiveshell.py in enable_matplotlib(self, gui)
3511         """
3512         from IPython.core import pylabtools as pt
-> 3513         gui, backend = pt.find_gui_and_backend(gui, self.pylab_gui_select)
3514
3515         if gui != 'inline':

~/REPOS/MTH314_Textbook/MakeTextbook/envs/lib/python3.9/site-packages/IPython/core/pylabtools.py in find_gui_and_backend(gui, gui_select)
278     """
279
--> 280     import matplotlib
281
282     if gui and gui != 'auto':

ModuleNotFoundError: No module named 'matplotlib'

# Here is our input matrix
A = np.matrix([[15,7,-7],[-1,1,1],[13,7,-5]])
sym.Matrix(A)

# Calculate eigenvalues and vectors using Numpy
e, Q = np.linalg.eig(A)
print(e)
sym.Matrix(Q)

#Turn eigenvalues into a diagonal matrix  (there is even a function for that!)
L = np.diag(e)
sym.Matrix(L)

# Calculate A again from Q and L

A2 = Q*L*np.linalg.inv(Q)

sym.Matrix(A2)


DO THIS: Using code, verify that A2 is the same as $$A$$.

# Put your answer here


DO THIS: Turn the above code into a function called eigendecomp which takes in a matrix A and returns Q and L.

# Put your code here


QUESTION: What other decompositions have we covered in the class so far? Make a list and write down a short description on why we use each decomposition.

## 2. Decompositions¶

Animiated Image from Wikipedia: https://wikipedia.org/

In numerical linear algebra, we factorize matrices to facilitate efficient and/or accurate computations (they are also helpful in proofs). There are many possible matrix decompositions. Some, e.g., the eigendecomposition, require the matrix to be square, while others, e.g., the $$QR$$ factorization, exist for arbitrary matrices. Among all possible decompositions (also called factorizations), some common examples include:

• QR Factorization from Gram-Schmidt orthogonization:

• $$A = QR$$

• $$Q$$ has orthonormal columns and $$R$$ is a upper-triangular matrix

• If there are zero rows in $$R$$, we can reduce the number of columns in $$Q$$

• Exists for arbitrary matrices

• LU / LDU Decomposition from Gauss Elimination:

• $$A = LU$$ or $$A = LDU$$

• $$L$$ is lower-triangular, $$U$$ is upper-triangular, and $$D$$ is diagonal

• Exists for all square matrices

• Is related to Gaussian Elimination

• Cholesky Decomposition:

• $$A = R^TR\quad (= LDL^T)$$

• $$R$$ is upper-triangular

• Factorization of $$A$$ into $$R^TR$$ requires $$A$$ be symmetric and positive-definite. The latter simply requires $$x^{T}Ax > 0$$ for every $$x \in \mathbb{R}^n$$. Note that $$x^{T}Ax$$ is always a scalar value (e.g., note that $$x^TA = y^T$$ for some vector $$y\in\mathbb{R}^n$$, and $$y^Tx$$ is the dot product between $$x$$ and $$y$$ and, hence, a real scalar).

• Schur Decomposition:

• $$A = UTU^{T}$$

• $$U$$ is orthogonal and $$T$$ is upper-triangular

• Exists for every square matrix and says every such matrix, $$A$$, is unitarily equivalent to an upper-triangular matrix, $$T$$ (i.e., there exists an orthonomal basis with respect to which $$A$$ is upper-triangular)

• Eigenvalues on diagonal of $$T$$

• Singular Value Decomposition:

• $$A = U\Sigma V^{T}$$

• $$U$$ is orthogonal, $$V$$ is orthogonal, and $$\Sigma$$ is diagonal

• Exists for arbitrary matrices

• Eigenvalue Decomposition:

• $$A = X\Lambda X^{-1}$$

• $$X$$ is invertible and $$\Lambda$$ is diagonal

• Exists for square matrices with linearly independent columns (e.g., full rank)

• Also called the eigendecomposition

QUESTION: What decompositions have we covered in the class so far and how did we use them?

## 3. Assignment wrap-up¶

Assignment-Specific QUESTION: What other decompositions have we covered in the class so far?

QUESTION: Summarize what you did in this assignment.

QUESTION: What questions do you have, if any, about any of the topics discussed in this assignment after working through the jupyter notebook?

QUESTION: How well do you feel this assignment helped you to achieve a better understanding of the above mentioned topic(s)?

QUESTION: What was the most challenging part of this assignment for you?

QUESTION: What was the least challenging part of this assignment for you?

QUESTION: What kind of additional questions or support, if any, do you feel you need to have a better understanding of the content in this assignment?