17 Pre-Class Assignment: Decompositions¶

Readings for this topic (Recommended in bold)¶

Beezer Proof Technique DC pg 600-601

Goals for today’s pre-class assignment¶

Matrix Decomposition
Decompositions
Assignment wrap-up

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¶

image showing how a matris is just a change of basis

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?

Your answer goes here