(Added note: Many have noticed that just printing to pdf with the browser print button may be the easiest).
This problem set is in the form of a Julia notebook (using the Jupyter/IJulia browser-based interface to interactive programming). We will be using the Julia language throughout the term for mathematical and computational explorations. Jupyter (an amalgam of Julia/Python/R) is a language agnostic notbeook interface widely used for simple calculations .
You can run this notebook without installing anything by logging in at JuliaBox. Just download the notebook file (a .ipynb file) by clicking the download icon at the upper right, then drag it onto the JuliaBox dashboard to upload it there. (We will be using Julia version 1.0 or later). (Avoid the json format by downloading the link or at least having the ipynb extension.)
Some of the problems are pencil-and-paper (we just happen to use the notebook to describe them), and some of them require you to run the code in the notebook to see what happens and then explain it. To run the code in an input cell, just click on the cell and then type shift-return; see also the "Help" menu in the notebook. When we say, check, we are asking you to run the code, but not necessarily write anything.
When you submit your pset, you may handwrite or type, but submit clearly labeled PDFs. (An app like Tiny Scanner for your phone makes it easier to scan black-and-white documents into legible PDF files using a cell-phone camera.) For printing a notebook to PDF, you may find that the Jupyter Download-as-PDF or printing Print Preview (in the File menu at the top of the notebook interface) produces a nicer file than directly printing from your browser.
Warm up problem. On a clock, 12 unit vectors point to each hour, uniformly spaced. What is the sum of all of these vectors? Why?
Warm up problem. On the neural net, matrix times vector, diagram that we saw in class, if there are p nodes (circles) on the left and q nodes on the right, then how many connections are there in terms of p and q? (In the diagram example there were 15.)
What is the formula for the inverse of the 2x2 matrix $\begin{pmatrix} a & b \\ c & d \end{pmatrix}$? (Answer is on Strang p. 84) On what conditions for a,b,c,d does the inverse exist?
A worked matrix factorization problem is at the end of this notebook.
This is called the 2 x 2 LU factorization: Given $A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$, find a factorization of $A$ in the form $ \begin{pmatrix} 1 & 0 \\ x & 1 \end{pmatrix}\begin{pmatrix} u & v \\ 0 & w \end{pmatrix}$.
(Write down x,u,v,w in terms of a,b,c,d.) On what conditions for a,b,c,d does the LU factorization exist? (This answer is different from that of Problem 3.)
A 2x2 rotation matrix has the form $ \begin{pmatrix} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{pmatrix}$. Remembering $\sin^2 \theta + \cos^2 \theta =1$, what is $ \begin{pmatrix} \cos \theta & \sin \theta \\ -\sin \theta & \cos \theta \end{pmatrix}$ $ \begin{pmatrix} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{pmatrix}$?
This is called the 2x2 QR factorization: Given $A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$, find a factorization of $A$ in the form $ \begin{pmatrix} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{pmatrix}\begin{pmatrix} u & v \\ 0 & w \end{pmatrix}$. The matrix $Q = \begin{pmatrix} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{pmatrix}$ is known as a 2x2 rotation matrix. (Hint1: what are the polar coordinates for the point(a,c)?? You should be able to write a formula for $u,\cos \theta,\sin \theta$ from a and c using only division and square roots. (at least if a and c are not both 0). Hint 2, use what we just mentioned about rotation matrices.)
The 2x2 singular value decomposition: An SVD has the form $A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$ = (rotation 1)(diagonal with non-negative entries)(rotation 2) = $ \begin{pmatrix} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{pmatrix}$ $ \begin{pmatrix} \sigma_1 & 0 \\ 0 & \sigma_2 \end{pmatrix}$ $ \begin{pmatrix} \cos \phi & \sin \phi \\ -\sin \phi & \cos \phi \end{pmatrix}$. We will see in this class that the SVD is very important in data science, biology, and so many fields.
Compute $A$ if $\theta=\pi/6$ and $\phi=\pi/3$ and $\sigma_1=\sigma_2=1$.
# Check your work numerically
θ = π/6
ϕ = π/3
σ₁ = σ₂ = 1
[cos(θ) -sin(θ);sin(θ) cos(θ)] * [1 0;0 1] * [cos(ϕ) sin(ϕ);-sin(ϕ) cos(ϕ)]
n = 5
D = rand(1:9, n, n) # Create a random n x n matrix with the digits 1 through 9
Put your cursor and click on the cell above and use control-enter to run the cell a few times without moving to another cell. If we asked how many numbers are stored in this n by n matrix you would say $n^2$.
using LinearAlgebra
n = 5
D = Diagonal(rand(1:9, n)) # Create a random n x n digonal matrix with the digits 1 through 9
5×5 Diagonal{Int64,Array{Int64,1}}:
9 ⋅ ⋅ ⋅ ⋅
⋅ 4 ⋅ ⋅ ⋅
⋅ ⋅ 3 ⋅ ⋅
⋅ ⋅ ⋅ 4 ⋅
⋅ ⋅ ⋅ ⋅ 7
While this is an n by n matrix, the number of parameters is n (which is what Julia stores in memory.)
B = Bidiagonal(rand(1:9,n), rand(1:9,n-1), :U)
5×5 Bidiagonal{Int64,Array{Int64,1}}:
5 1 ⋅ ⋅ ⋅
⋅ 2 5 ⋅ ⋅
⋅ ⋅ 1 4 ⋅
⋅ ⋅ ⋅ 4 3
⋅ ⋅ ⋅ ⋅ 6
S = SymTridiagonal(rand(1:9,n), rand(1:9,n-1))
5×5 SymTridiagonal{Int64,Array{Int64,1}}:
6 9 ⋅ ⋅ ⋅
9 8 8 ⋅ ⋅
⋅ 8 2 6 ⋅
⋅ ⋅ 6 1 3
⋅ ⋅ ⋅ 3 6
#Example
v = [1,2,3,4,5]
[vi*vj for vi∈v, vj∈v]
5×5 Array{Int64,2}:
1 2 3 4 5
2 4 6 8 10
3 6 9 12 15
4 8 12 16 20
5 10 15 20 25
v = rand(1:9,n)
println(v)
[vi*vj for vi∈v, vj∈v]
[4, 1, 9, 3, 7]
5×5 Array{Int64,2}:
16 4 36 12 28
4 1 9 3 7
36 9 81 27 63
12 3 27 9 21
28 7 63 21 49
(If it helps, you can assume "generically" that the (1,1) entry is not 0.)
v = rand(1:9,3)
w = rand(1:9,4)
println(v)
println(w)
[vi*wj for vi∈v, wj∈w]
[9, 5, 6] [2, 2, 1, 1]
3×4 Array{Int64,2}:
18 18 9 9
10 10 5 5
12 12 6 6
A 2x2 symmetric $A$ has the form $A = \begin{pmatrix} x & y \\ y & z \end{pmatrix}$. Find a factorization of $A$ in the form $ \begin{pmatrix} 1 & 0 \\ a & 1 \end{pmatrix} \begin{pmatrix} d_1 & 0 \\ 0 & d_2 \end{pmatrix} \begin{pmatrix} 1 & a \\ 0 & 1 \end{pmatrix}$. (Solve for $a,d_1,d_2$ in terms of x,y, and z). When does this factorization not exist?
Solution: we can multiply out
$A = \begin{pmatrix} x & y \\ y & z \end{pmatrix}$=$ \begin{pmatrix} 1 & 0 \\ a & 1 \end{pmatrix}
\begin{pmatrix} d_1 & 0 \\ 0 & d_2 \end{pmatrix}
\begin{pmatrix} 1 & a \\ 0 & 1 \end{pmatrix}$ to get
$ \begin{pmatrix} 1 & 0 \\ a & 1 \end{pmatrix}
\begin{pmatrix} d_1 & d_1 a \\ 0 & d_2 \end{pmatrix} =
\begin{pmatrix} d_1 & d_1 a \\ d_1 a & d_1 a^2 + d_2 \end{pmatrix}. $
We immediately see from the (1,1) entry that $d_1=x$.
From the (1,2) or (2,1) entry we see that $d_1a=y$ or $a=y/d_1=y/x$.
There is one entry left, the (2,2) entry which tells us that $z=d_1 a^2 + d_2$ or $d_2 = z-d_1 a^2 = z - y^2/x$.
In summary $a=y/x, d_1=x$ and $d_2 = z-y^2/x$. We have thus concluded that the following factorization always holds unless x=0:
$\begin{pmatrix} x & y \\ y & z \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ y/x & 1 \end{pmatrix}
\begin{pmatrix} x & 0 \\ 0 & z-y^2/x \end{pmatrix}
\begin{pmatrix} 1 & y/x \\ 0 & 1 \end{pmatrix}$
While not at all required by this problem, if you like you can check your work with some numbers. This won't be possible during an exam, but it's nice to do right now.
x,y,z = rand(3)
a = y/x
d₁ = x
d₂ = z - y^2/x
display([x y;y z])
display( [1 0;a 1] * [d₁ 0;0 d₂] * [1 a;0 1] )
2×2 Array{Float64,2}:
0.804518 0.603452
0.603452 0.496319
2×2 Array{Float64,2}:
0.804518 0.603452
0.603452 0.496319
You can use [control enter] a few times in the cell above to test as many cases that would convince you that you are right.