CS2900 2021 Past Paper Solution Q1

1. Vector and Matrix Computations

(a) Compute the dot product of the vectors:
$$\left(\begin{array}{c}{1}\ {2}\ {7}\ {-3}\end{array}\right),;\left(\begin{array}{c}{-4}\ {2}\ {1}\ {1}\end{array}\right)$$
[3 marks]
Answer:
$$\mathbf{u} \cdot \mathbf{v} = (1)(-4) + (2)(2) + (7)(1) + (-3)(1) = -4 + 4 + 7 - 3 = \boxed{4}$$

Explanation:
The dot product is calculated by summing the products of corresponding vector components.

(b) Compute the cosine of the angle between the vectors:
$$\left(\begin{array}{c}{1}\ {1}\ {1}\ {\sqrt{2}}\ {\sqrt{2}}\end{array}\right),;\left(\begin{array}{c}{2}\ {-1}\ {0}\ {0}\ {0}\end{array}\right)$$
[6 marks]
Steps:

1. Dot Product:
   $$\mathbf{a} \cdot \mathbf{b} = (1)(2) + (1)(-1) + (1)(0) + (\sqrt{2})(0) + (\sqrt{2})(0) = 2 - 1 = 1$$

2. Magnitudes:
   $$|\mathbf{a}| = \sqrt{1^2 + 1^2 + 1^2 + (\sqrt{2})^2 + (\sqrt{2})^2} = \sqrt{1+1+1+2+2} = \sqrt{7}$$
   $$|\mathbf{b}| = \sqrt{2^2 + (-1)^2 + 0^2 + 0^2 + 0^2} = \sqrt{4 + 1} = \sqrt{5}$$

3. Cosine Similarity:
   $$\cos \theta = \frac{\mathbf{a} \cdot \mathbf{b}}{|\mathbf{a}| |\mathbf{b}|} = \frac{1}{\sqrt{7} \cdot \sqrt{5}} = \boxed{\frac{1}{\sqrt{35}}}$$

Explanation:
The cosine similarity measures the angle between two vectors, with values in $[-1, 1]$.

(c) Construct a unit vector $\underline{\hat{n}}$ for the 4D vector:
$$\underline{n} = \left(\begin{array}{l}{2}\ {1}\ {\sqrt{2}}\ {\sqrt{2}}\end{array}\right)$$
[3 marks]
Steps:

1. Magnitude:
   $$|\mathbf{n}| = \sqrt{2^2 + 1^2 + (\sqrt{2})^2 + (\sqrt{2})^2} = \sqrt{4 + 1 + 2 + 2} = \sqrt{9} = 3$$

2. Unit Vector:
   $$\hat{\mathbf{n}} = \frac{1}{3}\begin{pmatrix}2\1\\sqrt{2}\\sqrt{2}\end{pmatrix} = \boxed{\begin{pmatrix}\frac{2}{3}\\frac{1}{3}\\frac{\sqrt{2}}{3}\\frac{\sqrt{2}}{3}\end{pmatrix}}$$

Explanation:
A unit vector is obtained by dividing each component by the vector’s magnitude.

(d) Compute the projection of $\underline{u} = \left(\begin{array}{c}{0}\ {1}\ {1}\ {-1}\end{array}\right)$ onto $\underline{\hat{n}}$ (from (c)).
[6 marks]
Steps:

1. Scalar Projection:
   $$\text{proj}_{\hat{\mathbf{n}}} \mathbf{u} = \mathbf{u} \cdot \hat{\mathbf{n}} = (0)\left(\frac{2}{3}\right) + (1)\left(\frac{1}{3}\right) + (1)\left(\frac{\sqrt{2}}{3}\right) + (-1)\left(\frac{\sqrt{2}}{3}\right) = \frac{1}{3}$$

2. Vector Projection:
   $$\text{Proj}_{\hat{\mathbf{n}}} \mathbf{u} = \left(\frac{1}{3}\right)\hat{\mathbf{n}} = \boxed{\begin{pmatrix}\frac{2}{9}\\frac{1}{9}\\frac{\sqrt{2}}{9}\-\frac{\sqrt{2}}{9}\end{pmatrix}}$$
   (Note: The last component becomes negative due to the projection’s sign.)

Explanation:
The projection vector lies in the direction of $\hat{\mathbf{n}}$ and has magnitude equal to the scalar projection.

(e) A bird flies along the vector $\left(\begin{array}{c}{9}\ {-6}\end{array}\right)$, where $\binom{1}{0}$ is 100m west and $\binom{0}{1}$ is 100m north. Calculate its traveled distance in the south-west direction using vector notation.
[6 marks]
Steps:

1. South-West Direction:
   Unit vector: $\hat{\mathbf{d}} = \frac{1}{\sqrt{2}}\begin{pmatrix}-1\-1\end{pmatrix}$ (West and South components)

2. Projection:
   $$\text{proj}_{\hat{\mathbf{d}}} \mathbf{v} = \mathbf{v} \cdot \hat{\mathbf{d}} = \frac{1}{\sqrt{2}}[9(-1) + (-6)(-1)] = \frac{1}{\sqrt{2}}[-9 + 6] = -\frac{3}{\sqrt{2}}$$

3. Distance:
   Magnitude of projection: $\left|-\frac{3}{\sqrt{2}}\right| = \frac{3}{\sqrt{2}} \approx 2.12$ units
   Total distance: $2.12 \times 100\ \text{m} = \boxed{212.13\ \text{meters}}$

Explanation:
The bird’s south-west travel is the absolute value of the projection of its path onto the south-west direction.

---

2. Matrix Rank, Python Functions, and Graph Theory

(a) Determine the rank of the matrices:
$$\left(\begin{array}{lll}{1}&{2}&{1}\ {-1}&{2}&{1}\ {0}&{2}&{1}\end{array}\right),;\left(\begin{array}{ll}{1}&{-1}\ {1}&{2}\end{array}\right)$$
[6 marks]

(b) Write a Python function Du that computes the product of a diagonal matrix D and vector u with minimal multiplications.
[6 marks]

(c) Given the adjacency matrix:
$$\mathbf{A} = \left(\begin{array}{lllll}{0}&{1}&{0}&{0}&{0}\ {1}&{0}&{1}&{0}&{1}\ {0}&{1}&{0}&{1}&{1}\ {0}&{0}&{1}&{0}&{1}\ {0}&{1}&{1}&{1}&{0}\end{array}\right)$$
i. Draw the graph. [3 marks]
ii. Is the graph directed? Explain. [3 marks]
iii. List node pairs with exactly one path of length 3. [4 marks]

---

3. Data Fitting and Projections

(a) Fit a least squares line to the points $(1,2)$, $(-1,4)$, and $(0,5)$ using the given SVD decomposition. Compute $(m,c)$ to 2 decimal places.
[12 marks]

(b) Construct a projection matrix for a 2D plane in 4D space spanned by $(0,1,-1,0)$ and $(1,1,1,1)$. Project $\underline{u} = (1,1,0,0)^\intercal$ onto this plane.
[12 marks]

(c) For a web graph:
i. Define its diffusion matrix. [6 marks]
ii. Explain how to update the diffusion matrix for ranking pages. [6 marks]

---

4. Inner Product Spaces and PCA

(a) Determine if the function $\langle \underline{u}, \underline{v} \rangle = \sum_{i=1}^3 \left(\sum_{j,k} \epsilon_{ijk}u_jv_k\right)^2$ (Levi-Civita symbol) forms an inner product.
[8 marks]

(b) For a covariance matrix $\mathbf{C}_X$ decomposed as:
$$\mathbf{C}_X = \frac{1}{99}\mathbf{U}\mathbf{D}\mathbf{V}^\intercal$$
i. What are $M$ (rows) and $F$ (columns) of data matrix $X$? [4 marks]
ii. How are principal components computed? [2 marks]
iii. How many variables capture ~10% precision? [4 marks]