Todai Entrance Exam: Math 2018 – Problem 1

Problem link

(1) Use Gaussian Elimination to address (i). All the rest can be easily inferred.

(2) Proof by contradiction:

Assume \text{rank}(\bar{A}) = \text{rank}(A) and the solution of the simultaneous linear equation does not exist.

If \text{rank}(\bar{A}) = \text{rank}(A) then \text{rank}(\bar{A}) \leq \min(m, n). However, \bar{A} \in \mathbb{R}^{m \times (n + 1)} and n < n + 1, so \bar{A} is guaranteed to have linearly dependent columns. Therefore, we can always represent b as a linear combination of other column vectors in A. As the solution of the simultaneous linear equation Ax = b is guaranteed to exist, this contradicts the assumption.

So the statement follows.

(3) There are various solutions to this problem. But I am not sure if it is appropriate to apply the normal equation directly.

Let e = \left | b - Ax \right |^{2} = (b - Ax)^{T}(b - Ax). We set the partial derivative of e to be zero to find critical points:

    \[ \frac{\partial e}{\partial x} = 2(b - Ax)^{T}(-A) = 0 \ \Leftrightarrow A^{T}(b - Ax) = 0 \  \Leftrightarrow A^{T}Ax = A^{T}b \]

Given A \in \mathbb{R}^{m \times n}, if \text{rank}(A) = n then \text{rank}(A^{T}A) = n (proof). So A^{T}A is invertible. Therefore, we can write:

    \[ \frac{\partial e}{\partial x} = 0 \Leftrightarrow x = (A^{T}A)^{-1}A^{T}b \]

Now we need to prove that critical point is the local minimum (and also global minimum as we only have one critical point):

    \[ \frac{\partial^{2} e}{\partial x^{2}} = A^{T}A \]

A^{T}A is a positive-semidefinite matrix (as x^{T}A^{T}Ax = \left | Ax \right |^{2} \geq 0), so the found critical point with x = (A^{T}A)^{-1}A^{T}b is the local minimum and also the global minimum.

(4) Let’s formulate the problem:

    \[ \begin{Bmatrix} \text{minimize} & \left | x \right |^{2}\\  \text{subject to} & Ax - b = 0 \end{matrix} \]

We have:

    \[ \begin{matrix} A = \begin{bmatrix}a_{1}^{T}\ …\ a_{i}^{T}\…\a_{m}^{T}\end{bmatrix} & , & b = \begin{bmatrix}b_{1}\ …\ b_{i}\…\b_{m}\end{bmatrix}  \end{matrix} \]

Let:

    \[ \begin{Bmatrix} f(x) = \left | x \right |^{2} \\g_{i}(x) = a_{i}^{T}x - b_{i}, i =1,...,m \\L(x, \lambda) = f(x) - \sum_{i=1}^{m}\lambda_{i}g_{i}(x), \lambda = \begin{bmatrix}\lambda_{1}\\ ... \\\lambda_{i}\\ ... \\\lambda_{m}\end{bmatrix} \end{matrix} \]

We obtain:

    \[ \begin{Bmatrix}  \nabla_{x} L(x, \lambda) = \nabla_{x}f(x) - \sum_{i=1}^{m}\lambda_{i}\nabla_{x}g_{i}(x)\\  \nabla_{\lambda_{i}} L(x, \lambda) = g_{i}(x), i = 1, . . . , m  \end{matrix} \Leftrightarrow \begin{Bmatrix}  \nabla_{x} L(x, \lambda) = 2x - \sum_{i=1}^{m}\lambda_{i}a_{i} = 2x - [ a_{1} . . . a_{n} ]\begin{bmatrix}\lambda_{1}\\ . . . \\\lambda_{m}\end{bmatrix} = 2x - A^{T}\lambda \\  \nabla_{\lambda_{i}} L(x, \lambda) = g_{i}(x), i = 1, . . . , m  \end{matrix} \]

Let’s find \lambda:

    \[ \begin{Bmatrix} \nabla_{x} L(x, \lambda) = 0 \Leftrightarrow 2x^{T} - \lambda^{T}A = 0 \Leftrightarrow 2x = A^{T}\lambda   \\  \nabla_{\lambda} L(x, \lambda) = 0, i = 1, . . . , m \Leftrightarrow Ax - b = 0 \end{matrix} \]

So: \frac{1}{2}AA^{T}\lambda = b. Given A \in \mathbb{R}^{m \times n}, if \text{rank}(A) = m then \text{rank}(AA^{T}) = m. Therefore, AA^{T} is invertible and we can write \lambda = 2(AA^{T})^{-1}b.

Prove that the found critical point is also the constrained local minimum:

    \[ \nabla^{2}_{x} L(x, \lambda) = 2 \]

So, the critical point with x = A^{T}(AA^{T})^{-1}b is the constrained local minimum and also the constrained global minimum.

(5) How can we compute Pseudoinverse for any Matrix? P is the pseudoinverse of A.

(6) P = (A^{T}A)^{-1}A^{T} for (3) and P = A^{T}(AA^{T})^{-1} for (4). I really don’t know what this question is for.


Facebooktwittergoogle_plusredditpinterestlinkedinmail

Leave a Reply

Your email address will not be published. Required fields are marked *