(Optional: if you wish to download this notebook as an .ipynb file, use the download button in the upper right and OPTION-click (MAC) or ALT-Click (Linux and Windows ) then "Save Link as.." or "Download Linked File As.." or something similar on your browser.)

Problem 1. Parameter Counting. In this question you are asked to count the number of parameters needed to represent a matrix. Examples we have already seen is that an n x n diagonal requires n parameters, an upper triangular requires n(n+1)/2 parameters, and the identity requires one parameter, the number "n" itself.

a. A unit lower triangular matrix, is lower triangular with ones on the diagonal. How many parameters are needed to represent an n x n unit lower triangular matrix?

A : $1+2+\cdots+(n-1) = \frac{n(n-1)}{2}$ (For lower triangular off-diagonal entries)

b. A vector that shows up in machine learning is the "one hot" vector. It is defined as a vector of length n, which has the kth entry 1, and all other entries 0. (The kth entry is considered "hot".) How many parameters are needed for the "one hot" vector? It is equivalently defined as the kth column of the n x n identity.

A : 2. An integer for the position of one, and another integer for the length.

c. An n x n matrix whose rows add up to 1, and also the columns add up to 1 is called doubly stochastic. How many parameters are required?

A : $(n-1)^2$ (rows adding up to 1 we have n constraints, for columns it is the same until (n-1)th column. For the last column the condition (sum=1) is implied from the sum of the rows, because we know the sum of all the entries of the matrix equals n. So it is total 2n-1 constraints taken away from n^2 parameters, $n^2-2n+1 = (n-1)^2$. We can think it as filling the principal submatrix of size (n-1) by (n-1) and the rest can be deduced from it. )

d. How many parameters in a 2x2 rotation matrix $Q=\begin{pmatrix} \cos \theta & -\sin \theta \\ \sin \theta &\cos \theta \end{pmatrix}$?

A : one for $\theta$

Problem 2. Suppose $A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$ is factored into a 2x2 rotation $Q=\begin{pmatrix} \cos \theta & -\sin \theta \\ \sin \theta &\cos \theta \end{pmatrix}$ times a 2x2 lower triangular matrix $L=\begin{pmatrix} x & 0\\ y & z \end{pmatrix}$. Write $x,y,z$ and $\theta$ in terms of $a,b,c$ and $d$.

A : $\begin{pmatrix} x\cos{\theta}-y\sin{\theta} & -z\sin{\theta} \\ x\sin{\theta}+y\cos{\theta} & z\cos{\theta} \end{pmatrix} = \begin{pmatrix} a & b\\ c & d \end{pmatrix}$

so we have $b^2+d^2 = z^2$ and assuming $z\in\mathbb{R}^+$ for now (so $z = \sqrt{b^2+d^2}$) we get $\cos{\theta} = \frac{d}{\sqrt{b^2+d^2}}$, $\sin{\theta} = -\frac{b}{\sqrt{b^2+d^2}}$.

Using $Q^{-1}A = L$ we have $\begin{pmatrix} \cos{\theta} & \sin{\theta} \\ -\sin{\theta} & \cos{\theta}\end{pmatrix}\begin{pmatrix} a & b\\c & d\end{pmatrix} = \begin{pmatrix}a\cos{\theta}+c\sin{\theta} & b\cos{\theta}+d\sin{\theta} \\ -a\sin{\theta}+c\cos{\theta} & -b\sin{\theta}+d\cos{\theta} \end{pmatrix} = \begin{pmatrix} x & 0 \\ y & z\end{pmatrix}$

Which we have $x = \frac{ad - bc}{\sqrt{b^2+d^2}}, y = \frac{ab+cd}{\sqrt{b^2+d^2}}, z = \frac{b^2+d^2}{\sqrt{b^2+d^2}}, \theta = \cases{\arccos{\frac{d}{\sqrt{b^2+d^2}}}, b\le0\\\arccos{\frac{d}{\sqrt{b^2+d^2}}}+\pi, b>0}$

Or selecting $z = -\sqrt{b^2+d^2}$, we have $\cos{\theta} = -\frac{d}{\sqrt{b^2+d^2}}$, $\sin{\theta} = \frac{b}{\sqrt{b^2+d^2}}$ and using the formula above we get $x = \frac{- ad + bc}{\sqrt{b^2+d^2}}, y = -\frac{ab+cd}{\sqrt{b^2+d^2}}, z = -\frac{b^2+d^2}{\sqrt{b^2+d^2}}, \theta = \cases{\arccos{\frac{d}{\sqrt{b^2+d^2}}}+\pi, b>0\\\arccos{\frac{d}{\sqrt{b^2+d^2}}}, b\le0}$

Finally two sets of $(x, y, z, \theta)$ are,

$x = \frac{ad - bc}{\sqrt{b^2+d^2}}, y = \frac{ab+cd}{\sqrt{b^2+d^2}}, z = \frac{b^2+d^2}{\sqrt{b^2+d^2}}, \theta = \cases{\arccos{\frac{d}{\sqrt{b^2+d^2}}}, b\le0\\\arccos{\frac{d}{\sqrt{b^2+d^2}}}+\pi, b>0}$

$x = \frac{- ad + bc}{\sqrt{b^2+d^2}}, y = -\frac{ab+cd}{\sqrt{b^2+d^2}}, z = -\frac{b^2+d^2}{\sqrt{b^2+d^2}}, \theta = \cases{\arccos{\frac{d}{\sqrt{b^2+d^2}}}+\pi, b>0\\\arccos{\frac{d}{\sqrt{b^2+d^2}}}, b\le0}$

Problem 3. (Inspired by GS 2.1 15-22)

a. What 3x3 matrix turns $\begin{pmatrix} a \\ b \\ c \end{pmatrix}$ into $\begin{pmatrix} b \\ c \\ a \end{pmatrix}$?

A : $\begin{pmatrix} 0 & 1 & 0\\ 0& 0 & 1\\1 & 0 & 0\end{pmatrix}$ ( Think $\begin{pmatrix} b\\c\\a \end{pmatrix}$ as $\begin{pmatrix} 0a+b+0c\\0a+0b+c\\a+0b+0c\end{pmatrix}$ )

b. What 3x3 matrix E turns $\begin{pmatrix} a \\ b \\ c \end{pmatrix}$ into $\begin{pmatrix} a \\ b \\ c-2a \end{pmatrix}$?

A : $\begin{pmatrix} 1 & 0 & 0\\ 0& 1 & 0\\-2 & 0 & 1\end{pmatrix}$

c. Think about undoing the transformation in 3b above and write down the inverse of $E$ without going through length calculations.

A : $\begin{pmatrix} 1 & 0 & 0\\ 0& 1 & 0\\2 & 0 & 1\end{pmatrix}$. (The matrix sending $\begin{pmatrix}a\\b\\c-2a\end{pmatrix}$ to $\begin{pmatrix} a\\b\\c\end{pmatrix}$, we need to add 2 times the first row to the last row so it is same as a matrix sending$\begin{pmatrix}x\\y\\z\end{pmatrix}$ to $\begin{pmatrix} x\\y\\z+2x\end{pmatrix}$. )

d. Write the dot product of $\begin{pmatrix} 1 \\ 4 \\ 5 \end{pmatrix}$ and $\begin{pmatrix} x \\ y \\ z \end{pmatrix}$ as a matrix multiplication $Ax$. The matrix $A$ has one row. Describe geometrically the solutions to $Ax=0$. Thse solutions are perpendicular to which vector?

A : $ \begin{pmatrix} 1 & 4 & 5 \end{pmatrix} \begin{pmatrix} x\\ y\\z\end{pmatrix} $. The solution is a plane perpendicular to a vector $\begin{pmatrix}1\\4\\5\end{pmatrix}$

Problem 4. (GS 2.2 8)

For which three numbers $k$ does elimination break down? Which $k$ no longer breaks down by a row exchange? For each $k$ is the number of solutions $0$, $1$ or $\infty$? Breakdown is defined as the algorithm producing a 0 pivot.

$\begin{eqnarray} kx+3y & = & \ \ 6 \\ 3x+ky & = & -6 \end{eqnarray}$

A : For $k = 0, -3, 3$ elimination breaks down. With row exchange, $k=0$ no longer breaks down. Number of solutions are $1, \infty, 0$ for $k = 0, -3, 3$.

Problem 5. (GS 2.3 3) With Julia or by hand

Which three matrices $E_{21},E_{31}, E_{32}$ put $A$ into triangular form $U$

A = [ 1 1 0; 4 6 1; -2 2 0]

3×3 Array{Int64,2}:
  1  1  0
  4  6  1
 -2  2  0

and $E_{32}E_{31}E_{21}A=U$.

A : $E_{21} = \begin{pmatrix} 1 & 0 & 0\\-4 & 1 & 0\\ 0 & 0 & 1\end{pmatrix}$, $E_{31} = \begin{pmatrix} 1 & 0 & 0\\0 & 1 & 0\\ 2 & 0 & 1\end{pmatrix}$, $E_{32} = \begin{pmatrix} 1 & 0 & 0\\0 & 1 & 0\\ 0 & -2 & 1\end{pmatrix}$

Problem 6. (GS 2.3 17) The parabola $y=a+bx+cx^2$ goes through the points $(x,y)=(1,4)$ and $(2,8)$ and $(3,14)$. Set up a matrix equations for the unknowns $(a,b,c)$ and solve by hand or with Julia.

A : We have three equations, $4 = a + b + c, 8 = a+2b+4c, 14 = a + 3b+9c$. In matrix form,

$\begin{pmatrix} 1 & 1 & 1\\ 1 & 2 & 4\\ 1 & 3 & 9 \end{pmatrix} \begin{pmatrix}a \\b\\c\end{pmatrix} = \begin{pmatrix}4 \\8 \\ 14\end{pmatrix} $. Solving it in Julia, the answer is (2, 1, 1)

[1 1 1;1 2 4;1 3 9]\[4, 8, 14]

3-element Array{Float64,1}:
 2.0
 1.0
 1.0

Problem 7 (GS 2.4 15). True or False.

a. If $A^2$ is defined then $A$ is necessarily square.
b. If $AB$ and $BA$ are defined then $A$ and $B$ are square.
c. If $AB$ and $BA$ are defined then $AB$ and $BA$ are square.
d. If $AB=B$ then $A=I$.

a. true (A is m by n matrix then $A*A$ is defined means n = m)

b. false (A being m by n and B being n by m)

c. true (A is m by n and B is n by p from AB defined, p = m from BA defined. So AB and BA are m by m and n by n square)

d. false (B = zero then A is any matrix)

Problem 8 (GS 2.4 24) By experiment by hand or with Julia and guessing (not proof) predict $A^n$ as a function of $n$ for matrices A₁,A₂,A₃:

A₁ = [ 2 1;0 1]

2×2 Array{Int64,2}:
 2  1
 0  1

#Hint using Julia
[A₁^n for n=1:5]

5-element Array{Array{Int64,2},1}:
 [2 1; 0 1]  
 [4 3; 0 1]  
 [8 7; 0 1]  
 [16 15; 0 1]
 [32 31; 0 1]

A₂ = [ 1 1;1 1]

2×2 Array{Int64,2}:
 1  1
 1  1

[A₂^n for n=1:5]

5-element Array{Array{Int64,2},1}:
 [1 1; 1 1]    
 [2 2; 2 2]    
 [4 4; 4 4]    
 [8 8; 8 8]    
 [16 16; 16 16]

#A₃ requires a symbolic package
import Pkg; Pkg.add("SymPy")
using SymPy

 Resolving package versions...
  Updating `~/.julia/environments/v1.3/Project.toml`
 [no changes]
  Updating `~/.julia/environments/v1.3/Manifest.toml`
 [no changes]

a,b = Sym("a"),Sym("b")

(a, b)

A₃ = [a b ;0 0]

\[\left[ \begin{array}{rr}a&b\\0&0\end{array}\right]\]

[A₃^n for n=1:5]

5-element Array{Array{Sym,2},1}:
 [a b; 0 0]      
 [a^2 a*b; 0 0]  
 [a^3 a^2*b; 0 0]
 [a^4 a^3*b; 0 0]
 [a^5 a^4*b; 0 0]

A : $A_1^n = \begin{pmatrix} 2^n & 2^n-1\\0 & 1\end{pmatrix}$, $A_2^n = \begin{pmatrix} 2^{n-1} & 2^{n-1}\\2^{n-1} & 2^{n-1}\end{pmatrix}$, $A_3^n = \begin{pmatrix} a^n & a^{n-1}b\\0 & 0\end{pmatrix}$

Problem 9. Why can't a matrix with a column of zeros have an inverse?

A : Let's say an $i^{th}$ column of a square matrix $A$ is zero column and assume $A$ is invertible. Then from $A^{-1}A = I$, the $i^{th}$ element on the diagonal of $A^{-1}A$ is zero since it is $i^{th}$ row of $A^{-1}$ and $i^{th}$ column(zero column) of $A$ inner producted. But on the right hand side, it should be 1. So by contradiction $A$ is not invertible.

Problem 10. Suppose v and w are perpendicular in $R^n$. What is ‖v+w‖² in terms of ‖v‖² and ‖w‖²?

A : $||v + w||^2 = (v+w)\cdot(v+w) = (v\cdot v) + (w\cdot w) + 2(w\cdot v)$ and since $(w\cdot v) = 0$, the answer is $||v||^2 + ||w||^2$