Link to this document's Jupyter Notebook

In order to successfully complete this assignment you must do the required reading, watch the provided videos and complete all instructions. The embedded survey form must be entirely filled out and submitted on or before 11:59pm on on the day before class. Students must come to class the next day prepared to discuss the material covered in this assignment.

---

Readings for this topic (Recommended in bold)

• Beezer Proof Technique DC pg 600-601

Pre-Class Assignment: Decompositions

Goals for today's pre-class assignment

1. Matrix Decomposition
2. Decompositions
3. 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)

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

$\displaystyle \left[\begin{matrix}15 & 7 & -7\\-1 & 1 & 1\\13 & 7 & -5\end{matrix}\right]$

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

[8. 1. 2.]

$\displaystyle \left[\begin{matrix}0.707106781186548 & 0.577350269189625 & 1.27675647831893 \cdot 10^{-15}\\2.59666420310278 \cdot 10^{-17} & -0.577350269189625 & 0.707106781186546\\0.707106781186547 & 0.577350269189627 & 0.707106781186549\end{matrix}\right]$

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

$\displaystyle \left[\begin{matrix}8.00000000000001 & 0.0 & 0.0\\0.0 & 0.999999999999996 & 0.0\\0.0 & 0.0 & 2.0\end{matrix}\right]$

# Calculate A again from Q and L

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

sym.Matrix(A2)

$\displaystyle \left[\begin{matrix}15.0 & 7.0 & -7.0\\-0.999999999999999 & 1.0 & 1.0\\13.0 & 7.0 & -5.0\end{matrix}\right]$

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

---

3. Assignment wrap-up

Please fill out the form that appears when you run the code below. You must completely fill this out in order to receive credit for the assignment!

Direct Link to Google Form

If you have trouble with the embedded form, please make sure you log on with your MSU google account at googleapps.msu.edu and then click on the direct link above.

✅ 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

from IPython.display import HTML
HTML(
"""
<iframe 
	src="https://cmse.msu.edu/cmse314-pc-survey" 
	width="100%" 
	height="1000px" 
	frameborder="0" 
	marginheight="0" 
	marginwidth="0">
	Loading...
</iframe>
"""
)

---

Congratulations, we're done!

Course Resources:

• MTH314 Course Website

---

Written by Dr. Dirk Colbry, Michigan State University
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

---