# 17 Pre-Class Assignment: Decompositions¶

## Readings for this topic (Recommended in bold)¶

## 1. Matrix Decomposition¶

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

```
from IPython.display import YouTubeVideo
YouTubeVideo("-_2he4J6Xxw",width=640,height=360, cc_load_policy=True)
```

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.

Put your answer to the above question here.

## 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**matricesIs

*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?

**Your answer goes here**

## 3. Assignment wrap-up¶

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

Put your answer to the above question here

✅ **QUESTION:** Summarize what you did in this assignment.

Put your answer to the above question here

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

Put your answer to the above question here

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

Put your answer to the above question here

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

Put your answer to the above question here

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

Put your answer to the above question here

✅ **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?

Put your answer to the above question here

✅ **QUESTION:** Do you have any further questions or comments about this material, or anything else that’s going on in class?

Put your answer to the above question here

✅ **QUESTION:** Approximately how long did this pre-class assignment take?

Put your answer to the above question here

Written by Dr. Dirk Colbry, Michigan State University

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.