[Solved] CS596 Homework #1

Problem 1: Consider the matrix

1. a) Find the eigenvalues/eigenvectors of A assuming = 0. Force your eigenvectors to have unit norm. b) Diagonalize A using the eigenvalues/eigenvectors you computed. c) Start now sending
2. What do you observe is happening to the matrices you use for diagonalization as becomes smaller and smaller? So what do you conclude when = 0?

Problem 2: Let A,B be two matrices of the same dimensions k m. a) With direct computation show that trace(AB^|) = trace(B^|A) = trace(BA^|) = trace(A^|B). b) Use question a) to compute E[x^|Ax] where E[] denotes expectation, A is a constant matrix and x is a random vector for which we know that E[xx^|] = Q. Hint: The trace of a scalar is the scalar itself. Trace and expectation are linear operations, so we can change their order of application. c) Using the previous properties show that for any matrix A of dimensions k k we have trace(A) = trace(UAU¹) for any nonsingular matrix U of dimensions kk. In other words that the trace does not change if we apply a similarity transformation. d) Use question c) to prove that if matrix A of dimensions k k is diagonalizable then its trace is equal to the sum of its eigenvalues (actually this is true even if the matrix is not diagonalizable). e) Regarding question d) how do you explain this equality given that when A is real the trace is also real whereas the eigenvalues can be complex? f) Using again question d) what can you say about the coefficient c_k1 of the characteristic polynomial ^k + c_k1^k1 + + c₀ of A. We recall that we already know that c₀ = (1)^k_{1 k} = (1)^k det(A).

Problem 3: A matrix A is called nilpotent if A^r = 0 for some integer r > 1. a) Show that all eigenvalues of A must be equal to 0. b) Is such a matrix diagonalizable? c) Give an example of a 2 2 matrix which is nilpotent. c) If we apply a similarity transformation to a nilpotent is the resulting matrix nilpotent? Apply the previous observation to your example in c) to obtain a second example of a nilpotent matrix.

Problem 4: There is clock and at each period of the clock you obtain a new pair (y_t,X_t) where y_t is scalar and X_t vector. We are interested in modeling y as a cross product of X with a vector A

y_n = X_n^|A + e_n, for n = 1,2,,t

where {e_n} denotes the error term between the model X_n^|A and the target value y_n. At each time t we have available the data (y_t,X_t),(y_t1,X_t1),,(y₁,X₁) and we would like to find the best A the minimizes the sum of the squared errors, namely perform the minimization

t

n=1 n=1

1. At the next time instant t+1 when we receive the new pair (y_t+1,X_t+1) we need to reapply the formula in (2) to compute the new estimate A_t+1. Express the computational complexity in terms of the size k of the vector X_t.
2. Show that we can compute A_t+1 by using the previous A_t and applying the following updating formulas

e_t+1 = y_t+1 X_t|+1A_t, K_t+1 = Q_tX_t+1, _t+1 = 1 + X_t|+1K_t+1,

,

where Q_t = R_t¹. What is the complexity of the algorithm in terms of k? This recursive algorithm is known as Recursive Least Squares (RLS) and is one of the most famous learning algorithms in the literature. Hint: To prove the validity of RLS you need to apply the matrix inversion lemma onto R_t+1 = R_t +X_t+1X_t^|₊₁ in order to compute Q_t+1 in terms of Q_t. From (2) you must also use the fact that Ut+1 = Ut + yt+1Xt+1 and At+1 = Qt+1Ut+1.

There is a meeting on Friday, September 27, at 5PM, in CoRE-101 to discuss YOUR questions. Mr. Anastasios Stathopoulos, our TA, will answer them.

Your reports, in hard copy, are due on Monday, September 30, in CBIM, between 10:00 and 11:00AM. Mr Stathopoulos will collect them.

Please STRICTLY respect the indicated time period because Mr. Stathopoulos has many other tasks, besides TAing. Late/Early submission will NOT be accepted neither by the TA nor by me.