18.S096 – Problem Set 1
We start by proving that, if is an invertible linear transformation defined over a vector space and is a subspace of , .
Let’s be a basis of . If is a LI set then we have proved that . So let’s assume we have such that . By linearity we will have . If we apply the inverse linear transformation , we get . As the LHS is non-zero because is a basis of , we have a contradiction.
We know that , where is the canonical basic of , is also a basis of because of the previous lemma. If we assume that is a matrix, let’s analyze its effect over every element of that basis:
As spans the range of , if only the first diagonal elements of are nonzero then should be a basis of the range of (they are linearly independent and they span the range). By the previously proved lemma, won’t change that dimension, so we know that is a basis of the range of A. That proves the desired result.
That follows from the singular values being the square roots of the eigenvalues of and the uniqueness of the eigenvalues.
Let’s assume . Then we have
( because it’s a square diagonal matrix.)
So we can only have if is symmetric.
This item asks for the other direction of the proof. Let’s show that symmetric matrices can be diagonalized by an orthogonal matrix inductively.
The one by one case is trivial, so let’s assume that all symmetric matrices of size are diagonalizable by an orthogonal matrix and try to diagonalize a one, .
We know (by solving the characteristic polynomial) that has at least one complex eigenvalue and unit eigenvector . We can start by proving it’s real:
By using the previous equation and the fact that is positive:
Now we want to prove the image of the orthogonal complement of the space generated by is orthogonal to . So let’s assume we have a vector such that . Then we have
If we take an arbitrary orthonormal basis of , , we can extend it by adding to get a basis of . Expressing in that basis:
where the zeroes are due to the previously proved orthogonality and the fact that is an eigenvector.
We know that must be symmetric, because if , we have and .
Using the inductive assumption, is diagonalizable and we have , where is an orthogonal matrix. can be extended to an ortogonal matrix by adding a 1 in the diagonal and padding with zeroes.
By inserting that in the previous expression of and using the fact that the product of orthogonal matrices is orthogonal, we finish the diagonalization.
Let be a SVD of with the singular values in order of decreasing magnitude. Then we have
As only the diagonal entries of are nonzero, the eigenvalues are going to be identical in both cases and equal to the squares of the singular values.
We previously proved that is going to be diagonalizable by an orthogonal matrix. Let’s assume the entry is negative and that is the i-th row of . Then we have
in contradiction with the fact that is positive semi-definite.
If is a diagonal matrix, only can be different from zero. Then we have
So if we want to choose the values of to make as close as possible to , we just have to do:
We will prove by contradiction that must be , where is the solution of the “diagonal A” problem with and . So let’s assume . By expanding A we get
As orthogonal transformations preserve norms,
But if this is true, wouldn’t be a solution to the original problem so we have a contradiction.
We just have to do some name changes to adapt the problem:
As minimizing is the same as minimizing , expressing the norm explicitly we get
exactly the objective function that was asked for.
It’s just a question of using another vector: