due Friday, October 30th at 11:59PM
Write your solutions to the following problems either by writing them on a piece of paper or on a tablet and scanning your answers as a PDF. Note that you are not allowed to use LaTeX, Google Docs, or any other digital document creation software to type your answers. Homeworks are due to Pensive by 11:59PM on the due date. See the syllabus for details on the slip day policy.
Homework will be evaluated not only on the correctness of your answers, but on your ability to present your ideas clearly and logically. You should always explain and justify your conclusions, using sound reasoning. Your goal should be to convince the reader of your assertions. If a question does not require explanation, it will be explicitly stated.
Before proceeding, make sure you’re familiar with the collaboration policy.
Total Points: \(6+8+8+12+12+16+20+18=100\)
Remember to look at Chapter 3.6 and Chapter 4 of the course notes while working on the homework!
Review the solutions to Homework 5. Pick two problem parts (for example, Problem 3a) and Problem 5b)) from Homework 5 in which your solutions have the most room for improvement, i.e., where they have unsound reasoning, could be significantly more efficient or clearer, etc. Include a screenshot of your solution to each problem part, and in a few sentences, explain what was deficient and how it could be fixed.
Alternatively, if you think one of your solutions is significantly better than the posted one, copy it here and explain why you think it is better. If you didn’t do Homework 5, choose two problem parts from it that look challenging to you, and in a few sentences, explain the key ideas behind their solutions in your own words.
Suppose \(A=BC\), where \(B\) is an unknown invertible \(2\times2\) matrix and
Find \(B^{-1}\). For full credit, you may only use the formula for the inverse of a \(2\times2\) matrix once; you do not need to find \(B\) first.
Start with \(A=BC\). Multiplying on the left by \(B^{-1}\) gives \(B^{-1}A=C\), and then multiplying on the right by \(A^{-1}\) gives
We only need to use the inverse formula for \(A\):
Therefore,
The order matters: we multiply by \(A^{-1}\) on the right so that \(A\) and \(A^{-1}\) are next to each other.
As we’ve seen, the matrix
rotates vectors in \(\mathbb R^2\) counterclockwise by \(\theta\) radians.
(3 pts) Find \(R_\theta^{-1}\).
Using the \(2\times2\) inverse formula, the denominator is
So
(2 pts) Now, find \(R_{-\theta}\) for a rotation of \(\theta\) radians clockwise, i.e. for \(-\theta\). What do you notice, and why?
Since \(\cos(-\theta)=\cos\theta\) and \(\sin(-\theta)=-\sin\theta\),
This makes sense geometrically: to undo a counterclockwise rotation by \(\theta\), rotate clockwise by the same angle.
(3 pts) A linear transformation \(T:\mathbb R^2\to\mathbb R^2\) first rotates vectors counterclockwise by \(30^\circ\), then multiplies their horizontal coordinates by \(5\) and their vertical coordinates by \(\frac12\). Find the matrix of \(T^{-1}\). Hint: While it’s possible to do this by first finding the matrix for \(T\), that is not necessary!
To undo \(T\), we undo its steps in reverse order. First, multiply the horizontal coordinate by \(1/5\) and the vertical coordinate by \(2\). Then rotate clockwise by \(30^\circ\); remember that regular rotations are counterclockwise, so this is the same as using the rotation matrix for \(-30^\circ\).
The scaling in the inverse transformation acts first — remember \((AB)^{-1}=B^{-1}A^{-1}\) — so the diagonal matrix goes on the right here:
Just to illustrate another way of doing this, we could also find the matrix for \(T\) and invert it. In \(T\), the rotation acts first, so its matrix goes on the right:
Using the \(2\times2\) inverse formula, the denominator is
Therefore, the matrix for \(T^{-1}\) is
which agrees with our first approach.
Let
(6 pts) For each vector below, find coefficients \(c_1,c_2,c_3\) such that \(c_1\vec a_1+c_2\vec a_2+c_3\vec a_3\) equals that vector. Show how you find the coefficients, and write each coefficient vector vertically.
We solve a separate system for each of the three vectors.
Subtract twice the second equation from the first, and three times the second equation from the third:
Subtracting these two equations gives \(c_3=-1\). Then \(c_2-(-1)=0\) gives \(c_2=-1\). Substituting into the original second equation gives \(c_1-2(-1)+3(-1)=0\), so \(c_1=1\). Our coefficient vector is \(\boxed{\begin{bmatrix}1\\-1\\-1\end{bmatrix}}\).
Subtract twice the second equation from the first, and three times the second equation from the third:
Subtracting these two equations gives \(c_3=-1\). Then \(c_2-(-1)=-3\) gives \(c_2=-4\). The original second equation becomes \(c_1-2(-4)+3(-1)=1\), so \(c_1=-4\). Our coefficient vector is \(\boxed{\begin{bmatrix}-4\\-4\\-1\end{bmatrix}}\).
Subtract twice the second equation from the first, and three times the second equation from the third:
Subtracting these two equations gives \(c_3=1\). Then \(c_2-1=1\) gives \(c_2=2\). The original second equation becomes \(c_1-2(2)+3(1)=0\), so \(c_1=1\). Our coefficient vector is \(\boxed{\begin{bmatrix}1\\2\\1\end{bmatrix}}\).
(3 pts) Place your three coefficient vectors in the columns of a matrix \(X\), in the order above. Explain why \(AX=I_3\) and why this means \(X=A^{-1}\). You may use the fact that for square matrices, \(AX=I_3\) also implies \(XA=I_3\).
Putting the coefficient vectors in columns gives
Recall that each column of \(AX\) is \(A\) times the corresponding column of \(X\). We chose these columns so that the three products are the three standard basis vectors, in order. Thus \(AX=I_3\).
Since both matrices are square, the given fact also tells us that \(XA=I_3\). These are exactly the two identities in the definition of an inverse, so \(\boxed{X=A^{-1}}\).
(3 pts) Use your inverse to solve \(A\vec x=\begin{bmatrix}11\\7\\19\end{bmatrix}\). Verify your work by multiplying \(A\vec x\) and checking it is equal to \(\begin{bmatrix}11\\7\\19\end{bmatrix}\).
Multiplying on the left by \(A^{-1}\) gives
Checking in the original system,
as required.
In this problem, we will investigate several \(3\times3\) matrices and see whether they are invertible. Consider the following six matrices:
Before proceeding, open the supplemental Jupyter Notebook. To open the notebook for Homework 6, click this link. Instructions on how to use Google Colab are at math124.org/running-code.
There, we provide instructions on how to compute a matrix’s inverse using np.linalg.inv. For the matrices in this problem, if that function call raises the error LinAlgError: Singular matrix, then the matrix is not invertible!
(4 pts) For all six matrices, try to compute their inverse. Report which ones are invertible and which are not.
For each matrix, we can check if it is invertible by running np.linalg.inv(M).
The invertible matrices are \(\boxed{M_1,M_3,M_6}\). The matrices \(\boxed{M_2,M_4,M_5}\) are not invertible; each raises LinAlgError: Singular matrix.
(4 pts) For the matrices that are invertible, multiply their inverse by the original matrix and show that the result is the identity matrix. In Your PDF: Include a screenshot that contains this check for all invertible matrices.
For \(M_1\), one of the invertible matrices, we can run
M1 @ np.linalg.inv(M1)
and we see the identity matrix:
[[1. 0. 0.]
[0. 1. 0.]
[0. 0. 1.]]
We get the same result for \(M_3\) and \(M_6\).
(4 pts) For each non-invertible matrix, suppose the columns are named \(\vec x\), \(\vec y\), and \(\vec z\), from left to right. Write one column as a linear combination of the other two. For example, you could write \(\vec z=a\vec x+b\vec y\) for specific numbers \(a\) and \(b\), or express \(\vec x\) or \(\vec y\) in terms of the other two columns. The coefficients may be zero. What do all the non-invertible matrices have in common?
The three non-invertible matrices are
We can read the relationships directly from their columns:
For \(M_2\), \(\boxed{\vec y=2\vec x+0\vec z}\), since \(\begin{bmatrix}2\\4\\8\end{bmatrix}=2\begin{bmatrix}1\\2\\4\end{bmatrix}\).
For \(M_4\), \(\boxed{\vec z=\vec x+\vec y}\), since \(\begin{bmatrix}1\\4\\0\end{bmatrix}=\begin{bmatrix}1\\2\\-1\end{bmatrix}+\begin{bmatrix}0\\2\\1\end{bmatrix}\).
For \(M_5\), \(\boxed{\vec y=0\vec x+0\vec z}\), since its second column is the zero vector.
In every case, one column can be written as a linear combination of the others. When we can write one vector as a linear combination of others, we say that the collection of vectors is not linearly independent. This means two different vectors, \(\vec u\) and \(\vec v\), may both have the same output when multiplied by \(A\), so \(A\) cannot be inverted.
For each \(2\times2\) matrix \(A\) below:
Find an LU factorization with ones on the diagonal of \(L\). If necessary, multiply \(A\) by a permutation matrix \(P\), i.e., find \(PA=LU\). If no row swap is needed, use \(P=I\).
Use the same \(L\) and \(U\) to solve \(A\vec x=\vec b_1\) and \(A\vec x=\vec b_2\).
(8 pts)
Write the factors in the required shapes and match entries:
The first row gives \(p=4\), \(q=3\). Next, \(4\ell=8\) gives \(\ell=2\), and \(2(3)+r=9\) gives \(r=3\). No row swap is needed, so
To solve each system, set \(\vec y=U\vec x\). First solve \(L\vec y=\vec b\) by forward substitution, then \(U\vec x=\vec y\) by back substitution.
For \(\vec b_1\): The equation \(L\vec y=\vec b_1\) is
Forward substitution gives \(y_1=11\) and \(2(11)+y_2=25\), so \(\vec y=\begin{bmatrix}11\\3\end{bmatrix}\). Back substitution gives
Thus \(\boxed{\vec x=\begin{bmatrix}2\\1\end{bmatrix}}\).
For \(\vec b_2\): Forward substitution gives \(y_1=5\) and \(2(5)+y_2=19\), so \(\vec y=\begin{bmatrix}5\\9\end{bmatrix}\). Back substitution gives
Thus \(\boxed{\vec x=\begin{bmatrix}-1\\3\end{bmatrix}}\). As checks,
(8 pts)
Without a row swap, the first row of \(U\) would be \(\begin{bmatrix}0&5\end{bmatrix}\). Then the bottom-left entry of \(LU\) would be \(\ell\cdot0=0\), but it needs to be \(6\). So we swap the rows using
The first row of \(P\) selects the second row of \(A\), and the second row of \(P\) selects the first row of \(A\). Thus multiplying on the left by \(P\) swaps the rows:
The matrix \(PA\) is already upper triangular, so \(PA=U\), and \(L\) is just the identity matrix:
To solve \(A\vec x=\vec b\), multiply both sides by \(P\), giving \(LU\vec x=P\vec b\). Set \(\vec y=U\vec x\) and first solve \(L\vec y=P\vec b\). Since \(L=I_2\), this gives \(\vec y=P\vec b\): we swap the entries of the right-hand side too.
For \(\vec b_1\):
Back substitution in \(U\vec x=\vec y\) gives
Thus \(\boxed{\vec x=\begin{bmatrix}2\\3\end{bmatrix}}\).
For \(\vec b_2\): Using the same factors,
Back substitution gives
Thus \(\boxed{\vec x=\begin{bmatrix}3\\-2\end{bmatrix}}\). Checking in the original row order,
We reordered equations, so the entries of \(\vec x\) stay in their original order.
For each \(3\times3\) matrix below, find an LU factorization as in Problem 6, then use \(L\) and \(U\) to solve \(A\vec x=\vec b\) for the given vector \(\vec b\).
(10 pts)
As in lecture, use a lower triangular \(L\) with ones on its diagonal and an upper triangular \(U\). Write placeholders for their unknown entries:
Matching the first row of \(LU\) to \(A\) gives \(u_{11}=3\), \(u_{12}=4\), and \(u_{13}=-2\). Matching the first column next gives \(3\ell_{21}=6\), so \(\ell_{21}=2\), and \(3\ell_{31}=-3\), so \(\ell_{31}=-1\). Now find the second row of \(U\), then the remaining entries:
No row swap is needed. Our factors are
Multiplying these factors gives \(LU=A\). Set \(\vec y=U\vec x\). Forward substitution in \(L\vec y=\vec b\) gives
So \(\vec y=\begin{bmatrix}-4\\4\\12\end{bmatrix}\). Back substitution in \(U\vec x=\vec y\) gives
Our solution and its check are
(10 pts)
If we start without swapping rows, the first row of \(U\) is \(\begin{bmatrix}3&3&0\end{bmatrix}\), and \(\ell_{21}=2\), \(\ell_{31}=1\). Then \(2(3)+u_{22}=6\) gives \(u_{22}=0\). Matching entry \((3,2)\) would require \(1(3)+\ell_{32}(0)=7\), which is impossible. Let’s swap the second and third rows and restart:
The first row of \(U\) is still \(\begin{bmatrix}3&3&0\end{bmatrix}\). Matching the first column now gives \(\ell_{21}=1\) and \(\ell_{31}=2\). Continuing,
Thus
Multiplying these factors gives \(LU=PA\).
The reordered right-hand side is \(P\vec b=\begin{bmatrix}3\\5\\21\end{bmatrix}\). Forward substitution in \(L\vec y=P\vec b\) gives
so \(\vec y=\begin{bmatrix}3\\2\\15\end{bmatrix}\). Back substitution gives
Our solution and its check in the original system are
Five speakers are playing five different songs at the same time, one song per speaker. Five microphones record them, but each microphone picks up a different mixture of all five speakers. The speakers stand in a line, with microphones arranged around them in a circle. The diagram shows which song each speaker plays.
Every microphone picks up all five speakers, but not evenly.
We know the song titles, but do not have access to the original song files – all we have are what our microphones recorded. Our goal is to recover the audio originally depicted by each speaker – i.e., the original songs – from these mixtures.
A digital audio recording stores a sound’s amplitude at regularly spaced instants. Each amplitude is a number that can be positive, negative, or zero. At a sample rate of \(8{,}000\) Hz, there are \(8{,}000\) amplitude measurements per second. Thus, a four-second clip is a vector of \(32{,}000\) numbers.
At a particular instant, let \(x_1,x_2,x_3,x_4,x_5\) be the sound amplitudes coming from the five speakers and \(b_1,b_2,b_3,b_4,b_5\) be the amplitudes recorded by the five microphones. Each microphone records a weighted sum of the speaker amplitudes, using the known weights below. Assume these weights stay fixed throughout the problem.
| Speaker 1 (Song 1) | Speaker 2 (Song 2) | Speaker 3 (Song 3) | Speaker 4 (Song 4) | Speaker 5 (Song 5) | |
|---|---|---|---|---|---|
| Microphone 1 | \(0.9\) | \(0.8\) | \(0.6\) | \(0.5\) | \(0.7\) |
| Microphone 2 | \(0.7\) | \(0.9\) | \(0.8\) | \(0.7\) | \(0.6\) |
| Microphone 3 | \(0.5\) | \(0.6\) | \(0.8\) | \(0.9\) | \(0.8\) |
| Microphone 4 | \(0.8\) | \(0.7\) | \(0.9\) | \(0.8\) | \(0.6\) |
| Microphone 5 | \(0.6\) | \(0.8\) | \(0.7\) | \(0.6\) | \(0.9\) |
For example, Microphone 1 records
Before proceeding, open the supplemental Jupyter Notebook. To open the notebook for Homework 6, click this link. Instructions on how to use Google Colab are at math124.org/running-code.
The notebook provides two four-second recording sessions, using different excerpts of the same five songs. We know the microphone recordings and the weights, but must solve for what each speaker was playing.
(4 pts) Write the five equations relating the speaker amplitudes to the microphone amplitudes at one instant. Then write your system as \(A\vec x=\vec b\), where
State \(A\) and its shape.
Each row of the table gives one equation:
These equations are \(A\vec x=\vec b\), with
Its shape is \(5\times5\): one row per microphone and one column per speaker.
(3 pts) In the notebook, enter your matrix \(A\) and use scipy.linalg.lu to find \(P,L,U\) satisfying \(PA=LU\). The notebook explains how to use SciPy to do this. Verify that \(PA=LU\), and then use \(L\) and \(U\) to solve for the five speaker amplitudes, i.e., \(\vec x\), for the one instant \(\vec b\) selected in the notebook.
In Your PDF: Include a screenshot of the microphone amplitudes and the recovered speaker amplitudes for the one instant provided.
Enter the matrix and compute the factors using the notebook’s convention:
A = np.array([[0.9, 0.8, 0.6, 0.5, 0.7],
[0.7, 0.9, 0.8, 0.7, 0.6],
[0.5, 0.6, 0.8, 0.9, 0.8],
[0.8, 0.7, 0.9, 0.8, 0.6],
[0.6, 0.8, 0.7, 0.6, 0.9]])
Q, L, U = lu(A)
P = Q.T
print(P @ A)
print(L @ U)
print(np.allclose(P @ A, L @ U))
SciPy returns \(A=QLU\), so we use \(P=Q^T\) to get \(PA=LU\). Both displayed products are
and the check returns True. Now solve \(L\vec y=P\vec b\), followed by \(U\vec x=\vec y\):
sample_index = 12345
b = B1[:, sample_index]
y = solve_triangular(L, P @ b, lower=True)
x = solve_triangular(U, y, lower=False)
print(b)
print(x)
At this instant, the amplitudes are approximately
The notebook displays these values rounded to three decimal places.
(3 pts) Recall, in the first four-second clip, there are a total of \(32{,}000\) “instants,” i.e., \(32{,}000\) vectors \(\vec b\), each of which describes the amplitude recorded by each of the five microphones.
Using the LU decomposition from part b), follow the notebook’s instructions to solve all these systems together and recover the five song clips. Listen to the mixtures and the recovered clips.
In Your PDF: Include a screenshot of the code that starts with X1 = and of the five audio players that appear afterwards.
Pass all of B1 to the supplied function, using the same factors:
X1 = solve_with_factors(P, L, U, B1)
print("Recovered recordings shape:", X1.shape)
play_channels(X1, "Session 1: recovered speaker")
The shape is (5, 32000). We are solving \(AX_1=B_1\), one column at a time: each column contains the five speaker amplitudes at one instant. Each row of \(X_1\) is one recovered song clip, in the speaker order given in the problem. The call to play_channels displays five audio players.
(2 pts) In the second session, each speaker plays a different excerpt of its song. Recover these five clips without computing another LU factorization. Check your answer and listen to the recovered clips.
In Your PDF: Include a screenshot of your code and check for the second recording session.
Use the same function with B2:
X2 = solve_with_factors(P, L, U, B2)
print(np.allclose(A @ X2, B2))
play_channels(X2, "Session 2: recovered speaker")
The check returns True: mixing the recovered clips with the original weights reproduces the second set of microphone recordings, up to rounding error. Again, \(X_2\) has shape \(5\times32000\), with one recovered clip in each row.
(6 pts)
(3 pts) Why were we able to use our original \(P\), \(L\), and \(U\) for the second set of recordings without recomputing them?
(3 pts) Suppose only Microphone 1 was working. Could you uniquely recover all five speaker amplitudes at a given instant from its recording alone? Why or why not?
i) The weights stayed fixed, so the coefficient matrix \(A\) stayed fixed. The factors \(P\), \(L\), and \(U\) depend on \(A\), not on the right-hand side. The second recording session changes the microphone amplitudes, so we have new right-hand sides but can reuse the same two triangular solves.
ii) No. One microphone gives just one equation:
We can choose \(x_2,x_3,x_4,x_5\) freely and then set
So there are infinitely many sets of speaker amplitudes with the same microphone recording. For example, increasing \(x_1\) by \(0.8\) and decreasing \(x_2\) by \(0.9\) changes the recorded amplitude by \(0.9(0.8)-0.8(0.9)=0\). There isn’t enough information to recover all five amplitudes uniquely.