18.06 Pset 2

Due Friday Feb 18 at 11am on Canvas. Submit PDF(s) of your handwritten solutions along with your (clearly labeled) Julia code.

using LinearAlgebra

Problem 1 (10 points)

Suppose that $A$ is a $4\times 4$ matrix: $$ A = \begin{pmatrix} 1 & 3 & 2 & 5 \\ -2 & 1 & 1 & \\ 4 & 2 & & \\ -1 & & & \end{pmatrix} $$ In Julia:

A = [ 1 3 2 5
     -2 1 1 0
      4 2 0 0
     -1 0 0 0 ]

This is similar to an upper-triangular matrix, except that it is "flipped" horizontally. It doesn't matter in principle — we can still solve $Ax=b$ "bottom to top" similar to backsubstitution — but in practice it is often better to rewrite things in "standard" upper- or lower-triangular form because that's what all of the computer software is written to handle.

(a) Convert $A$ into a standard lower triangular matrix, of the form $$ L = \begin{pmatrix} a & & & \\ b & c & & \\ d & e & f & \\ g & h & i & j \end{pmatrix} = \mbox{products of permutation matrix/matrices with }A $$ as a product of $A$ with one or more permutation matrices on the left and/or right.

… and enter your answer in Julia as a check:

L = # your answer here as a product of A with some other matrix/matrices

(b) Suppose that we want to solve $Ax = b$ for $b = [26,-1,10,-1]$. Using your answer from (a), write $x = A^{-1} b$ in the following form:

1. $y = $ something easy with $b$?
2. forward-substitution solve of $Lz = y$
3. $x = $ something easy with $z$?

(c) Implement your answer from (b) in Julia and check it by filling in the outline below:

using LinearAlgebra

b = [26, -1, 10, -1]

y = # something easy with b
z = LowerTriangular(L) \ y    # tells Julia to use forward-substitution
x = # something easy with z

# compare it to naive solution:
A \ b

Problem 2 (15 points)

Suppose that we have the equation $$ YX+XZ = \underbrace{\begin{pmatrix} 1 & 2 \\ -3 & 4 \end{pmatrix}}_{Y} \underbrace{\begin{pmatrix} a & b \\ c & d \end{pmatrix}}_X + X \underbrace{\begin{pmatrix} 5 & -6 \\ 7 & 8 \end{pmatrix}}_Z = \underbrace{\begin{pmatrix} -7 & 21 \\ -3 & 3 \end{pmatrix}}_{B} $$ for the unknown $2\times 2$ matrix $X$.

(a) Explain why the left-hand side $YX+XZ$ is a linear operation (according to the definition in lecture 1) on $X$, where $X$ is viewed as a "vector" in the vector space of $2 \times 2$ matrices.

(b) If we re-arrange the 4 unknowns into a column vector $x = [a,b,c,d]$, write down a $4\times 4$ matrix equation $Ax = b$ for $x$, i.e. write down the matrix $A$ and the vector $b$.

(c) Enter your $A$ and $b$ in Julia and solve for $x$. Using your x, form the matrix $X$ and check that $YX + XZ = B$ (up to roundoff errors).

A = # your matrix here
b = # your vector here
x = A \ b

X = # your solution here, in terms of x above.  e.g [ x[1] x[3]; x[4] x[2] ] or whatever

Y = [1 2; -3 4]
Z = [5 -6; 7 8]
B = [-7 21; -3 3]

Y*X + X*Z ≈ B # should return "true"

(d) If $X,Y,Z,B$ were all $n \times n$ matrices and you followed the above strategy, solving $Ax=b$ with ordinary Gaussian elimination and not taking advantage of any special structure of $A$, how would the computational cost scale with $n$? i.e. proportional to $n^2,n^3,n^4,\ldots$?

In fact, this is called a Sylvester equation and there are fancier ways to solve it (not covered in 18.06) that require $\sim n^3$ operations. The following Julia code should give the same answer $X$ up to roundoff errors:

using LinearAlgebra # in case you didn't load this yet

X_fast = sylvester(Y, Z, -B) # solves YX+XZ = B for X much more efficiently than above

Problem 3 (12 points)

Which of the following sets are vectors spaces (with the usual definition of $\pm$ and multiplication by real scalars), and why?

1. The set of 4-component vectors whose components sum to 1.
2. The set of 2-component vectors whose components have product 0.
3. The union of two subspaces $S$ and $T$: all vectors that are in either $S$ or $T$.
4. The intersection of two subspaces $S$ and $T$: all vectors that are in both $S$ and $T$.
5. Given a subspace $V$ of $\mathbb{R}^n$ and an $m\times n$ matrix $A$, the set of all vectors $Ax$ for all $x\in V$.
6. The set of all functions $f(x)$ such that the integral $\int_{-\infty}^\infty e^{-x^2} f(x) dx$ is zero.

Problem 4 (10 points)

(From Strang, section 3.2, problem 30.)

How is the nullspace $N(C)$ related to $N(A)$ and $N(B)$ if $C = \begin{pmatrix} A \\ B \end{pmatrix}$? ($A$ is $m \times n$ and $B$ is $p \times n$.)

Problem 5 (10 points)

Explain why $N(B)$ must be a subspace of $N(AB)$ for any $m \times n$ matrix $A$ and any $n \times p$ matrix $B$.

Problem 6 (10 points)

In lecture 6, I said that in writing $$ b = A\begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} 2 \\ 0 \\ 0 \end{pmatrix} x_1 + \begin{pmatrix} 1 \\ 3 \\ 0 \end{pmatrix} x_2 + \begin{pmatrix} 0 \\ 2 \\ 0 \end{pmatrix} x_3 $$ the third vector $[0,2,0]$ is redundant.

Explain how, for any $[x_1,x_2,x_3]$ above, we can write the same vector $b$ as: $$ b = A\begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} 2 \\ 0 \\ 0 \end{pmatrix} x_1' + \begin{pmatrix} 1 \\ 3 \\ 0 \end{pmatrix} x_2' $$ for some $[x_1', x_2']$. That is, give a formula for $[x_1', x_2']$ in terms of $[x_1,x_2,x_3]$.

Problem 7 (12 points)

(a) Find the special solutions (a basis for the null space) for the matrix $$ A = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 2 & 4 & 6 \\ 0 & 0 & 1 & 2 \end{pmatrix} . $$

(b) How does your answer change if you insert a column of 0's between the 1st and 2nd columns of $A$ (so that $A$ now has 5 columns, one of which is all 0's)?

(c) How does your answer change if you insert a row of zeros between the 1st and 2nd rows (so that $A$ now has 4 rows, one of which is all zeros)?