$\newcommand{\ones}{\mathbf 1}$

Linear algebra

Solving a systems of linear equations
Download the file data.mat and load it in MATLAB 
load data
This group of questions refers to solving a system of linear equations $Ax = b$, where $A$ and $b$ are given and $x$ is to be found.
With the matrix $A$ defined in the variable a1, the system is
  1. overdetermined,
    Correct! $A$ is $5\times2$, so that the system has 5 equations and 2 unknowns. Therefore, it is overdetermined.
  2. underdetermined.
    Incorrect.
With the matrix $A$ defined in the variable a1 and $b$ defined in the variable b1, the system has
  1. no solution,
    Correct! The system has a solution if and only if $b$ is not in the image of $A$. This can be checked in many different ways. For example, by computing the least-squares approximation and checking if the residual $\|Ax - b\|$ is numerically zero: 
    x1 = a1 \ b1; norm(b1 - a1 * x1)
    Note that with numerical computations the result that should in theory be zero may be a "small" nonzero number.
  2. has unique solution,
    Incorrect.
  3. has nonunique solution.
    Incorrect.
With the matrix $A$ defined in the variable a1 and $b$ defined in the variable b2, the system has
  1. no solution,
    Incorrect.
  2. has unique solution,
    Correct! Applying the same procedure as in the previous problem, we find that $x = (1,2)$ is an exact solution. It is unique because the null space of $A$ consists of the zero vector only: 
    x2 = a1 \ b2; norm(b2 - a1 * x2), null(a1)
  3. has nonunique solution.
    Incorrect.
With the matrix $A$ defined in the variable a2 and $b$ defined in the variable b2, the system has
  1. no solution,
    Incorrect.
  2. has unique solution
    Incorrect.
  3. has nonunique solution,
    Correct! Applying the same procedure as in the two previous problems, we find that $x = (1,2,0)$ is an exact nonunique solution. All solutions are given by \[(1,2,0) + \alpha (1,1,-2),\] where $\alpha$ is a free parameter. 
    x3 = a2 \ b2; norm(b2 - a2 * x3)
z = null(a2); z = z / z(2)
    The following code generates a new random solution: 
    x4 = x3 + z * rand(size(z, 2), 1)
    Check them out!

Eigenvalues and eigenvector
The eigenvalue decomposition $A = V\Lambda V^{-1}$ is computed in MATLAB with the function eig. Type 
help eig
for explanation of how to use it. In the problems below $A$ is given by the variable a3 and we consider the function $f(x) = Ax$.
Plot $f(\mathcal{U})$, where $\mathcal{U}$ is the unit ball $\{ x \ | \ \|x\| = 1\}$.
  1. solution
    Correct! The image of the unit ball through a linear function is an ellipse centered at the origin with axis given by the eigenvectors of $AA^\top$. This can be verified by plotting the $y^k = Ax^k$ for points $x^k$ on the unit circle 
    t = linspace(0,2 * pi, 50);
y = a3 * [cos(t); sin(t)];
plot(y(1, :), y(2, :))
hold on, axis equal
    Next, adding to the plot the eigenvectors, scaled by the eigenvalues 
    [v, d] = eig(a3 * a3');
v1 = sqrt(d(1, 1)) * v(:, 1);
v2 = sqrt(d(2, 2)) * v(:, 2);
plot([0 v1(1)], [0, v1(2)])
plot([0 v2(1)], [0, v2(2)])
    we obtain the following figure
Find a unit norm $x$ for which $\|f(x)\|$ is maximized.
  1. solution
    Correct! The function $\|Ax\|$ is maximized over the set $\mathcal{U}$ by a normalized eigenvector related to the largest eigenvalue of the matrix $A^\top A$. Let $\lambda_1 < \lambda_2$ be the eigenvalues of $A^\top A$ (note that they are real and nonnegative because $A^\top A$ is symmetric and nonnegative definite), we have that \[\lambda_1 \leq \|Ax\| = \sqrt{x^\top A^\top Ax} \leq \lambda_2\] 
    [v, d]  = eig(a1' * a1);
[d_max, i_max] = max(sqrt(diag(d)));
v_max = v(:, i_max)
    Check the result by generating vectors in random directions 
    x = randn(2, 1); x = x / norm(x); norm(a1 * x) < d_max
With $x(0)$ being a random vector, does the sequence $x(k+1) = f(x(k)) / \|x(k)\|$ converge?
  1. no,
    Incorrect.
  2. yes.
    Correct! Let $v_1$ and $v_2$ be eigenvectors related to the eigenvalues $\lambda_1 < \lambda_2$ of $A^\top A$. If $x(0) = \alpha v_1$ for some $\alpha$, the limit point is $v_1/\|v_1\|$. Otherwise, the limit point is $v_2/\|v_2\|$.