[Solved] CS596 Midterm

Problem 1: Let V denote the space of all polynomials p(x) of order up to some fixed integer value n.

1. a) Show that V is a vector space. Specify the addition and multiplication. b) Is V finite dimensional? If yes what is its dimension? c) Define a straightforward basis. d) Define at least three linear subspaces of V.
2. e) If p(x) = p₀ + p₁x + p₂x² + + p_nxⁿ there is a one-to-one correspondence between p(x) and the vector [p₀ p₁ p_n]^| of its coefficients. Using this correspondence define an inner product for V and then use it to define a norm for polynomials of order up to n.

Problem 2: If Q is a real symmetric matrix of dimensions k k, with eigenvalues _{1 2 k}, which are real, then we recall that we have already proved that for any real vector X we have

.

1. a) Using the special eigen-decomposition of real symmetric matrices, extend the previous inequalities to complex vectors X as follows

,

where X denotes the conjugate of X. b) If A is a square matrix of dimensions k k with real elements, denote with ₁,,_k its eigenvalues that may be complex numbers (and the corresponding eigenvectors complex vectors) and with _{1 2 k} its singular values which are real and nonnegative. Using question a) show that all eigenvalues _i satisfy

₁ |_i| _k.

Hint: The _i² are the eigenvalues of the symmetric matrix A^|A.

Problem 3: A square matrix P is called a projection if P² = P. a) Show that the eigenvalues of P are either 0 or 1. b) Show that if P is a projection so is I P where I the identity matrix. c) If P is also symmetric P^| = P then P is called an orthogonal projection. Prove that for an orthogonal projection P and any vector X we have that X PX and PX are orthogonal. d) If the two matrices A,B have the same dimensions m n then show that P = A(B^|A)¹B^| is a projection matrix. What is the condition on the dimensions m,n and on the product B^|A for this P to be well defined ? When is this matrix an orthogonal projection? e) If b is a fixed vector of length m and b some arbitrary vector, we are interested in minimizing the square distance min_b kbbk² where kk is the Euclidean norm. To avoid the trivial solution we constrain

b to satisfy b = AX where A is a matrix of dimensions m n with m > n and X an arbitrary vector of length n. Show that the optimum b is the orthogonal projection of b with some proper projection matrix which you must identify.

Problem 4: As discussed in the class, the space of all random variables constitutes a vector space. We can also define an inner product (also mentioned in class) between two random variables x,y using the expectation of the product

<x,y>= E[xy].

Consider now the random variables x,z,w. We are interested in linear combinations of the form x = az + bw where a,b are real deterministic quantities. a) By using the orthogonality principle find the x (equivalently the optimum coefficients a,b) that is closest to x in the sense of the norm induced by the inner product. b) Compute the optimum (minimum) distance and its optimum approximation x in terms of E[xz],E[xw],E[z²],E[zw],E[w²].