COMP3670/6670: Introduction to Machine Learning Semester 2, 2022 Assignment 4

Question 1                                      Permutation Matrix                                        (5+5=10 credits) A permutation  matrix  is a square matrix that has exactly a single 1 in every row and column, and

Let P be an arbitrary | ↓ | permutation matrix.

1.  Prove that P is always invertible.

2.  Prove that PT  is a permutation matrix.

Question 2                 Distinct eigenvalues and linear independence                   (20+5 credits)

Let A be a | ↓ | matrix.

1.  Suppose that A has | distinct eigenvalues λ 1 |．．．| λn, and corresponding non-zero eigenvectors x1 |．．．| xn . Prove that #x1 |．．．| xn} is linearly independant.

Hint: You may use without proof the following property: If #y1 |．．．| ym} is linearly dependent then there exists some p such that 1 女 p 长 m, yp+1  ∈ span#y1 |．．．| yp} and #y1 |．．．| yp} is linearly independent.

2. Hence, or otherwise, prove that for any matrix B  ∈ Rn xn , there can be at most | distinct eigenvalues for B.

Question 3                          Properties of Upper Triangular                           (10+15=25 credits)

1.  Prove the set of all lower triangular matrices is closed under matrix multiplication.

2. Let U be an square | ↓ | lower triangular matrix. Prove that the determinant of U is equal to the product of the diagonal elements of U.

Question 4                              Eigenvalues of symmetric matrices                               (15 credits)

1. Let A be a symmetric matrix. Let v1 be an eigenvector of A with eigenvalue λ 1 , and let v2 be an eigenvector of A with eigenvalue λ2 . Assume that λ 1  λ2 . Prove that v1 and v2 are orthogonal. (Hint: Try proving λ 1v1(T)v2 = λ2v1(T)v2 . Recall the identity aT b = bT a．)

Question 5                     Computations with Eigenvalues                      (3+3+3+3+3=15 credits)

Let A = ┌3(6)   5(4)┐ .

1.  Compute the eigenvalues of A.