Homework 2: Linear Algebra & Dimensionality Reduction

CS 556-B: Mathematical Foundations of Machine Learning
Homework 2: Linear Algebra & Dimensionality Reduction (100 points)
Note: All solutions methods must be fully explained. If a problem requires you to submit your code, please ensure
that your code (in the form of a jupyter notebook) is developed in a python3 environment and appropriately
commented.
Matrices
.
1. (9 points) Which of the following matrices (without being altered) is in Reduced Row Echelon Form (RREF)?
For matrices that are not in RREF (if any) please state ALL the violations due to which they are not in RREF.
A1 =


1 0 0
0 0 0
0 1 0

 A2 =


1 0 7
0 1 −4
0 0 0

 A3 =


1 0 7
0 1 0
0 0 1


2. (6 points) What is the rank of each matrix below? Demonstrate intermediate steps employed to obtain the
rank?
(a) A1 =


1 0 0
0 1 0
0 0 1


(b) A2 =


3 −1 7
1 4 4
0 0 1


Subspaces & Projections
3. (5 points) If a matrix of dimensions 7 × 9 has rank 5, what are the dimensions of the 4 fundamental subspaces
(i.e., row space, column space, null space, left null space)? What is the sum of all 4 dimensions i.e., add the
dimension of each subspace and report the total?
4. (5 points) If a 3 × 4 matrix has rank 3, what are the dimensions of its columnspace (e.g., which of R
1
,R
2
,...R
n
represents the column space) and left nullspace (i.e., for a matrix Am×n, the left null space is the set of all
vectors x such that AT x = 0)?
5. (10 points) Find the set of vectors that form the null space of the matrix A =


2 2 2 2
4 3 2 1
3 3 4 1


6. (10 points) Find the complete set of solutions for the system of linear equations (Ax=b) defined below:
x1 − 2x2 − 2x3 = b1
2x1 − 5x2 − 4x3 = b2
4x1 − 9x2 − 8x3 = b3
Note: First find the solution(s) that satisfy the column space relationship, then find the set of solutions to the
null space and add the two to obtain the final solution.
7. (10 points) Calculate the Projection of b onto the column space defined by matrix A.
1
(a) A =


1 1
0 1
0 0

 b =


2
3
4


(b) A =


1 1
1 1
0 1

 b =


4
4
6


In each case, also calculate the magnitude of the vector from b perpendicular to the projection.
8. (10 points) Suppose matrix A is defined as follows: A =


1 2 3
−1 0 −3
0 −2 3

 Convert the matrix to form an
equivalent orthonormal basis via. orthogonolization using the Gram-Schmidt procedure.
Eigenvalues & Eigenvectors, PCA & SVD
9. (10 points) Diagonalize the matrix 
6 −1
2 3 
Please arrange the eigenvalues in descending order while constructing the diagonal matrix.
10. (10 points) Calculate the Singular Value Decomposition of matrix A = 
2 3
0 2
.
Demonstrate each step in the computation and order the singular values in descending order in the Σ matrix.
11. (8 points) Recommendation System (SVD)
Rambo Top-Gun Harry Potter Amelie Casablanca
User 1 5.0 4.5 - - 1.0
User 2 - - 2.5 5.0 5.0
User 3 4.0 4.5 - - -
User 4 - 1.5 4.5 - -
User 5 1.0 - - 4.0 5.0
User 6 - - 4.5 - -
Table 1: Rating Matrix
Table 1 showcases user preferences of various movies. The rating scale is from 1 - 5 where 1 indicates a strong
dislike of the movie while 5 indicates that the user has a strong liking for the movie. Some ratings have been
masked (‘-’ symbol) and it is your task to re-create these ratings from the ‘U’,‘V’,‘S’ matrices provided (as
numpy arrays stored on disk to be read and processed via. a python script).
(a) (1 point) What is User 1’s ‘estimated’ rating of the movie Amelie?
(b) (2 point) What is the strength of concept 1 in the SVD decomposition?
(c) (1 point) What is the average rating for Movie 3 across all users in the system (i.e., if actual ratings exist,
use them if not use estimated ratings)?
(d) (1 point) What is the movie with the overall highest rating (i.e., if actual ratings exist, use them if not
use estimated ratings)?
(e) (3 points) Please include your code, as a python3 jupyter notbook file named:
‘<lastname> <firstname> svd.ipynb’. All visualizations and answers should be printed in the notebook
in addition to including only the answers for (a) - (d) in the assignment for this question.
12. (7 points) Calculate the principle component analysis of the Iris dataset using the built-in method from Scikitlearn and showcase the following.
2
(a) (1 point) Include a 2D scatter plot (i.e., PCA with 2 components) where each point is colored by the class
(i.e., category) to which it belongs.
(b) (1 point) What is the total percentage of variance captured by the first 2 components of PCA?
(c) (1 point) What is the strength of each of the two principal components?
(d) (1 point) What is the magnitude of each of the two principal components?
(e) (3 points) Please include your code, as a python3 jupyter notebook file named:
‘<lastname> <firstname> pca.ipynb’. All visualizations and answers should be printed in the notebook
in addition to including only the answers for (b) - (d) in the assignment for this question.
3