↩

Homework 11

Table of Contents

The following assignment is due Thursday 12/05 by 11:59 PM. You should submit all your written solutions to Gradescope as a single pdf. Follow the instructions in the programming problem for code solutions.

1. Analytic Geometry

\begin{align*} \mathbf{u} = \begin{bmatrix} 1 \\ -1 \\ 5 \\ 7 \\ 4 \end{bmatrix} \qquad \mathbf{v} = \begin{bmatrix} 3 \\ 0 \\ 3 \\ -5 \\ -7 \end{bmatrix} \end{align*}

For all the following parts, you must show all of your work and do all calculations by hand unless otherwise specified.

1.1. (2 points)

Compute the norm of \(\mathbf{v}\).

1.2. (3 points)

Find the unit vector in the direction of \(\mathbf{u}\).

1.3. (3 points)

Compute the distance between \(\mathbf{u}\) and \(\mathbf{v}\) (i.e., between the points at the tips of each vector).

1.4. (3 points)

Compute approximately the angle between \(\mathbf{u}\) and \(\mathbf{v}\) (you may use a computer).

1.5. (3 points)

Using the values you have computed so far, and without using the formula given in class, determine approximately the angle between \(\mathbf{v}\) and \(\mathbf{u} - \mathbf{v}\). Justify your answer.

2. Orthogonality and Subspaces

2.1. (2 points)

Determine a vector which is orthogonal to every vector in the solution set of \(2x_1 + 3x_2 - 4x_3 + 5\textcolor{red}{x_4} = 0\).

2.2. (3 points)

\begin{align*} \mathbf{u} = \begin{bmatrix} 1 \\ 2 \\ 1 \\ -2 \end{bmatrix} \qquad \mathbf{v} = \begin{bmatrix} -3 \\ -6 \\ -2 \\ 2 \end{bmatrix} \end{align*}

In this part, we will be using a very nice fact we didn't cover in class: every vector in \(\mathsf{Nul}(A^T)\) is orthogonal to every vector in \(\mathsf{Col}(A)\) (it's not too difficult to prove). Use this to determine two linearly independent vector with integer entries that are orthogonal to every vector in \(\mathsf{span}\{\mathbf u, \mathbf v\}\).

2.3. (3 points)

In this part, we use an even nicer fact: \(\mathsf{rank}(A) + \mathsf{dim}(\mathsf{Nul}(A^T)) = m\) for any matrix \(A \in \mathbb R^{m \times n}\). Use this to show that \(\mathsf{rank}(A) = \mathsf{rank}(A^T)\). Justify your answer.

3. Gram-Schmidt

\begin{align*} \mathbf v_1 = \begin{bmatrix} 2 \\ 1 \\ 0 \\ -1 \end{bmatrix} \qquad \mathbf v_2 = \begin{bmatrix} 3 \\ 0 \\ 0 \\ 0 \end{bmatrix} \qquad \mathbf v_3 = \begin{bmatrix} -4 \\ 9 \\ 0 \\ -11 \end{bmatrix} \qquad \mathbf u = \begin{bmatrix} 2 \\ -2 \\ \textcolor{red}{0} \\ -5 \end{bmatrix} \end{align*}

You must show all of your work and do all calculations by hand unless otherwise specified.1

3.1. (2 points)

Find the component of \(\mathbf v_2\) orthogonal to \(\mathbf v_1\) (that is, find the vector \(\mathbf z\) such that \(\mathbf v_2 = \hat{\mathbf v_2} + \mathbf z\) where \(\hat{\mathbf v_2}\) is the orthogonal projection of \(\mathbf v_2\) onto \(\mathbf v_1\)). We will refer to this as \(\mathbf v_2'\) below.

3.2. (2 points)

Find the component of \(\mathbf v_3\) orthogonal to \(\mathbf v_1\). We will refer to this as \(\mathbf v_3'\) below.

3.3. (2 points)

Find the component of \(\mathbf v_3'\) orthogonal to \(\mathbf v_2'\). We will refer to this as \(\mathbf v_3''\) below.

3.4. (2 points)

Demonstrate that \(\{\mathbf v_1, \mathbf v_2', \mathbf v_3''\}\) is an orthogonal set.

3.5. (2 points)

Find \([\mathbf u]_{\mathcal B}\) where \(\mathcal B = \{\mathbf v_1, \mathbf v_2', \mathbf v_3''\}\) without solving any systems of linear equations, or row-reducing any matrices.

4. Semantle (Programming)

(10 points) During the heyday of the game Wordle (early 2022) a number of variants were created, including one called Semantle. In this variant of the game, you have an unlimited number of chances to guess a hidden word, which could be any word in the English language. Each guess you make is given a number value based on how similar it is to the correct word. This number is determined using cosine similarity and Word2vec. In rough terms, Word2vec is a technique for building models which represent words as vectors in a high-dimensional vector space. Given two words \(a\) and \(b\), with corresponding vectors in \(v_a\) and \(v_b\) in this space, we can determine how similar they are by finding the cosine of the angle between them (using the formula we learned in class). If the value is close to \(1\) then \(a\) and \(b\) are very similar. If it's close to \(-1\) then they are very dissimilar. For example, in the model we will use for this assignment, the words "algebra" and "geometry" have similarity value \(0.68\) whereas "algebra" and "tuna" have value \(-0.32\).

You are given starter code in the file hw11.py. Don't change the name of this file when you submit. Also don't change the names of any functions included in the starter code. The only changes you should make are to fill in the provided TODO items. You are also given a file semantle.py along with some data files you will need in order for semantle.py to run. You are required to implement the following functions.

  • similarity which determines the cosine similarity of two words
  • most_similar_words which determines the closest words to a given word

See the docstrings in the starter code for more details. You'll upload a single file hw11.py to Gradescope, where you can verify that it passes some (but not all) autograder tests.

We will use pretrained models from the GloVe project (thank you Stanford) and a file conisting of common English words from a random git repo (thank you stranger).

Footnotes:

1

The Gram-Schmidt process is an algorithm for converting a basis into an orthogonal basis. We won't have time to cover Gram-Schmidt in full detail in this course, but this problem details how the procedure works for three vectors.