ACSE-7 Inversion & Optimisation – Part A (15 pts)
This question covers lecture 1.
Please read the general instructions in README.md first!
Question A
Consider the rectangular matrix
$$A = \begin{pmatrix} 1 & 2 & 5 & -2 \\ -1 & -1 & -3 & 3 \\ 2 & 7 & 16 & -1 \end{pmatrix}. $$
• Convert this matrix into reduced-row-echelon form.
• What is the rank of this matrix? What dimensions are its range and its null space?
• Find the appropriate number of vectors which can be used as a basis to span the null space.
[Hint: one possible pair of null space vectors are $\boldsymbol{n}_1=(-1,-2,1,0)$ and $\boldsymbol{n}_2=(4,-1,0,1)$]
Now consider the right hand side vector $$\boldsymbol{b} = \begin{pmatrix} 12 \\ 0\\ 60 \end{pmatrix}.$$
• Use the pseudo-inverse approach to find a solution to the problem $A\boldsymbol{x}=\boldsymbol{b}$.
• Demonstrate through some examples that adding any multiples of the vectors spanning the null space to this solution (i.e. adding any vector from within the null space) also provides a valid solution to this problem.
• Demonstrate that the solution obtained using the pseudo-inverse is the minimal norm solution to this problem.
• Find the solution that minimises the first two entries of $x$, i.e. if $\boldsymbol{x}=(x_1, x_2, x_3, x_4)$, find the solution to the linear system for which $x_1^2 + x_2^2$ is minimised.
Solution
In [2]:
%matplotlib inline
%precision 6
import numpy as np
import matplotlib.pyplot as plt
import scipy.linalg as sl
import scipy.optimize as sop
from pprint import pprint
from mpl_toolkits.mplot3d import Axes3D
• Convert this matrix into reduced-row-echelon form.
The RREF is
$$ \begin{pmatrix} 1 & 0 & 1 & -4 \\ 0 & 1 & 2 & 1 \\ 0 & 0 & 0 & 0 \end{pmatrix} $$
• What is the rank of this matrix? What dimensions are its range and its null space?
This is formed of two linearly independent columns (and equivalently of only two independent rows) so its rank is 2. This is less that the minimum of $m$ and $n$ and so the matrix is not full rank.
To check this using numpy:
In [3]:
# compute the rank of the matrix in original form
A = np.array([[1, 2, 5, -2], [-1, -1, -3, 3], [2, 7, 16, -1]])
pprint(A)
print(np.linalg.matrix_rank(A))
# compute the rank of the matrix in a form after we’ve performed row operations
Arref = np.array([[1, 0, 1, -4], [0, 1, 2, 1], [0, 0, 0, 0]])
pprint(Arref)
print(np.linalg.matrix_rank(Arref))
array([[ 1, 2, 5, -2],
[-1, -1, -3, 3],
[ 2, 7, 16, -1]])
2
array([[ 1, 0, 1, -4],
[ 0, 1, 2, 1],
[ 0, 0, 0, 0]])
2
The dimension of the range of $A$ is two.
Now consider the augmented matrix representing three linear equations in four unknowns (the RHS vector is all zero)
$$ \left( \begin{array}{cccc|c} 1 & 2 & 5 & -2 & 0 \\ -1 & -1 & -3 & 3 & 0 \\ 2 & 7 & 16 & -1 & 0 \end{array} \right)$$
The RREF is
$$ \left( \begin{array}{cccc|c} 1 & 0 & 1 & -4 & 0 \\ 0 & 1 & 2 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{array} \right)$$
so any vector for which $v_1 + v_3 – 4v_4=0$ and $v_2 + 2v_3 + v_4=0$ will be a solution of $A\boldsymbol{v} = \boldsymbol{0}$ and thus will lie in the null space of $A$.
If we chose arbitrary values for the variables that appear more than once, say $v_3 = \alpha$ and $v_4 = \beta$, then we obtain $v_1 = – \alpha + 4\beta$ and $v_2=-2\alpha-\beta$.
Therefore note that the solution for $v$ in the null space can be written as
$$\boldsymbol{v} = \alpha \begin{pmatrix} -1 \\ -2\\ 1\\ 0 \end{pmatrix} +\beta \begin{pmatrix} 4 \\ -1\\ 0\\ 1 \end{pmatrix} $$
That is, any vector in the null space of $A$ can be written as a linear combination of the two vectors above. This null space is a two-dimensional plane within $\mathbb{R}^4$. The null space thus forms a sub-space of $\mathbb{R}^4$.
• Find the appropriate number of vectors which can be used as a basis to span the null space.
The basis to span the null space are: $$ \begin{pmatrix} -1 \\ -2\\ 1\\ 0 \end{pmatrix} , \begin{pmatrix} 4 \\ -1\\ 0\\ 1 \end{pmatrix} $$
In [9]:
A = np.array([[1, 2, 5, -2], [-1, -1, -3, 3], [2, 7, 16, -1]])
null_vecs = sl.null_space(A)
print(null_vecs)
# check that A@ these vectors yields the zero vector
#print(‘A@null_vecs = 0?’,np.allclose( A@null_vecs, np.array( [0,0,0] )))
# is this the same as we obtained above – let’s normalise it and multiply it by the length of the vector above
print((sl.null_space(A) / sl.norm(sl.null_space(A))) * sl.norm(np.array([-1, -2, 1, 0])) )
[[-0.933969 0.264595]
[-0.228747 -0.880113]
[ 0.205439 0.361762]
[-0.182132 0.156589]]
[[-1.617681 0.458291]
[-0.396201 -1.5244 ]
[ 0.355832 0.62659 ]
[-0.315462 0.27122 ]]
• Use the pseudo-inverse approach to find a solution to the problem $A\boldsymbol{x}=\boldsymbol{b}$.
Now consider the problem $A\boldsymbol{x}=\boldsymbol{b}$ :
$$ \begin{pmatrix} 1 & 2 & 5 & -2 \\ -1 & -1 & -3 & 3 \\ 2 & 7 & 16 & -1 \end{pmatrix} \begin{pmatrix} x_1\\ x_2\\ x_3\\ x_4 \end{pmatrix} = \begin{pmatrix} 12\\ 0\\ 60 \end{pmatrix} $$
In [19]:
A = np.array([
[1, 2, 5, -2],
[-1, -1, -3, 3],
[2, 7, 16, -1]])
b = np.array([12, 0, 60])
U, S, VT = sl.svd(A,full_matrices=False)
pprint(np.allclose(A, U @ np.diag(S) @ VT))
# note that there are only two non-zero entries, so p=2
p=2
# form the compact SVD
Sp = S[:p]
# and form the corresponding diagonal matrix
SSp = np.diag(Sp)
# pull out first p columns to find the compact form and U and V
Up = U[:,:p]
Vp = VT.T[:,:p]
# check our compact SVD
pprint(np.allclose(A, Up @ SSp @ Vp.T))
# could just invert the diagonal entries in SSp of course, but let’s be lazy and use sl.inv
invAgen = Vp @ sl.inv(SSp) @ Up.T
# note that numpy as a pseudoinverse function – check our result against this:
# https://docs.scipy.org/doc/numpy/reference/generated/numpy.linalg.pinv.html
pprint(np.allclose(invAgen, np.linalg.pinv(A)))
x = invAgen @ b
pprint(x)
True
True
True
array([-0.461538, 1.846154, 3.230769, 3.692308])
• Demonstrate through some examples that adding any multiples of the vectors spanning the null space to this solution (i.e. adding any vector from within the null space) also provides a valid solution to this problem.
The solution for $v$ in the null space can be written as
$$\boldsymbol{v} = \alpha \begin{pmatrix} -1 \\ -2\\ 1\\ 0 \end{pmatrix} +\beta \begin{pmatrix} 4 \\ -1\\ 0\\ 1 \end{pmatrix} $$
One particular solution to $A\boldsymbol{x}=\boldsymbol{b}$ is
$$\boldsymbol{x}_{\text{part}} = \begin{pmatrix} -0.461538\\ 1.846154\\ 3.230769\\ 3.692308 \end{pmatrix} $$
We can add to this solution any vector from the null space and by linearity it will be another solution, e.g.
$$\boldsymbol{x} = \begin{pmatrix} -0.461538\\ 1.846154\\ 3.230769\\ 3.692308 \end{pmatrix} + 2 \begin{pmatrix} -2 \\ -3\\ 1\\ 0 \end{pmatrix} +3 \begin{pmatrix} -1 \\ -1\\ 0\\ 1 \end{pmatrix} = \begin{pmatrix} -6 \\ -7\\ 3\\ 5 \end{pmatrix}$$
If $\alpha = 1, \beta = 0$ $$ v_1 = \begin{pmatrix} -1 \\ -2\\ 1\\ 0 \end{pmatrix} $$
If $\alpha = 0, \beta = 1$ $$ v_2 = \begin{pmatrix} 4 \\ -1\\ 0\\ 1 \end{pmatrix} $$
If $\alpha = 1, \beta = 1$ $$ v_3 = \begin{pmatrix} 3 \\ -3\\ 1\\ 1 \end{pmatrix} $$
In [ ]:
pprint(np.allclose(Ax, np.linalg.pinv(A)))
• Demonstrate that the solution obtained using the pseudo-inverse is the minimal norm solution to this problem.
In [ ]:
• Find the solution that minimises the first two entries of $x$, i.e. if $\boldsymbol{x}=(x_1, x_2, x_3, x_4)$, find the solution to the linear system for which $x_1^2 + x_2^2$ is minimised.
In [ ]:
One particular solution to $A\boldsymbol{x}=\boldsymbol{b}$ is
$$\boldsymbol{x}_{\text{part}} = \begin{pmatrix} -0.461538\\ 1.846154\\ 3.230769\\ 3.692308 \end{pmatrix} $$
We can add to this solution any vector from the null space and by linearity it will be another solution, e.g.
$$\boldsymbol{x} = \begin{pmatrix} 1 \\ 2\\ 1 \\ 2 \end{pmatrix} + 2 \begin{pmatrix} -2 \\ -3\\ 1\\ 0 \end{pmatrix} +3 \begin{pmatrix} -1 \\ -1\\ 0\\ 1 \end{pmatrix} = \begin{pmatrix} -6 \\ -7\\ 3\\ 5 \end{pmatrix}$$
So the presence of a null space leads to non-uniqueness of solutions.
Solution
The RREF is
$$ \begin{pmatrix} 1 & 0 & 1 & -4 \\ 0 & 1 & 2 & 1 \\ 0 & 0 & 0 & 0 \end{pmatrix} $$
This is formed of two linearly independent columns (and equivalently of only two independent rows) so its rank is 2. This is less that the minimum of $m$ and $n$ and so the matrix is not full rank.
Now consider the augmented matrix representing three linear equations in four unknowns (the RHS vector is all zero)
$$ \left( \begin{array}{cccc|c} 3 & 1 & 9 & 4 & 0 \\ 2 & 1 & 7 & 3 & 0 \\ 5 & 2 & 16 & 7 & 0 \end{array} \right)$$
The RREF is
$$ \left( \begin{array}{cccc|c} 1 & 0 & 2 & 1 & 0 \\ 0 & 1 & 3 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{array} \right)$$
so any vector for which $v_1 + 2v_3 + v_4=0$ and $v_2 + 3v_3 + v_4=0$ will be a solution of $A\boldsymbol{v} = \boldsymbol{0}$ and thus will lie in the null space of $A$.
If we chose arbitrary values for the variables that appear more than once, say $v_3 = \alpha$ and $v_4 = \beta$, then we obtain $v_1 = -2\alpha – \beta$ and $v_2=-3\alpha-\beta$.
Therefore note that the solution for $v$ in the null space can be written as
$$\boldsymbol{v} = \alpha \begin{pmatrix} -2 \\ -3\\ 1\\ 0 \end{pmatrix} +\beta \begin{pmatrix} -1 \\ -1\\ 0\\ 1 \end{pmatrix} $$
That is, any vector in the null space of $A$ can be written as a linear combination of the two vectors above. This null space is a two-dimensional plane within $\mathbb{R}^4$. The null space thus forms a sub-space of $\mathbb{R}^4$.
Note that the number of independent vectors that must be linearly combined to form the null space is equal to the number of non-pivot columns in the RREF.
Now consider the problem $A\boldsymbol{x}=\boldsymbol{b}$ where
$$\boldsymbol{b} = \begin{pmatrix} 22 \\ 17\\ 39 \end{pmatrix} $$
One particular solution to this is
$$\boldsymbol{x}_{\text{part}} = \begin{pmatrix} 1 \\ 2\\ 1 \\ 2 \end{pmatrix} $$
We can add to this solution any vector from the null space and by linearity it will be another solution, e.g.
$$\boldsymbol{x} = \begin{pmatrix} 1 \\ 2\\ 1 \\ 2 \end{pmatrix} + 2 \begin{pmatrix} -2 \\ -3\\ 1\\ 0 \end{pmatrix} +3 \begin{pmatrix} -1 \\ -1\\ 0\\ 1 \end{pmatrix} = \begin{pmatrix} -6 \\ -7\\ 3\\ 5 \end{pmatrix}$$
So the presence of a null space leads to non-uniqueness of solutions.
In [ ]: