Consider the equation $ABx=b$, given by: $$ \underbrace{\begin{pmatrix} 2 & 1 & 2 \\ & -1 & 2 \\ & & 1 \end{pmatrix}}_A \underbrace{\begin{pmatrix} -1 & 1 & 2 & 1 \\ 3 & -2 & -5 & -1 \\ 0 & 1 & 1 & 2 \end{pmatrix}}_B x = \underbrace{\begin{pmatrix} 17 \\ 19 \\ 7 \end{pmatrix}}_b $$
(a) Give bases for the nullspaces $N(A)$, $N(B)$, and $N(AB)$. (Hint: you should only have to do Gaussian elimination once.)
(b) Give the complete solution $x$ to $ABx=b$, and show how you can do this without ever multiplying $A$ and $B$ together to explicitly form the matrix $AB$.
(a) $A$ has rank 3 and is $3 \times 3$. That is, $A$ is an invertible matrix. So the nullspace $N(A)$ is the trivial vector space $\{[0~0~0]\}$. A basis for this vector space is the empty set.
To find $N(B)$, we do Gaussian elimination on $B$ to get $U$.
$$\begin{pmatrix} -1 & 1 & 2 & 1 \\ 3 & -2 & -5 & -1 \\ 0 & 1 & 1 & 2 \end{pmatrix} \xrightarrow{r_2+3r_1} \begin{pmatrix} -1 & 1 & 2 & 1 \\ 0 & 1 & 1 & 2 \\ 0 & 1 & 1 & 2 \end{pmatrix}\xrightarrow{r_3-r_2} \begin{pmatrix} -1 & 1 & 2 & 1 \\ 0 & 1 & 1 & 2 \\ 0 & 0 & 0 & 0 \end{pmatrix}=U. $$We see that there are 2 free columns of $U$, so $N(B)$ has dimension 2. To find $N(B)$, we use the strategy from lecture with
$$U_0 = \begin{pmatrix} -1 & 1\\ 0& 1\end{pmatrix} \quad \text{and} \quad F=\begin{pmatrix} 2 & 1\\ 1 & 2 \end{pmatrix}. $$A vector $x=[p_1~p_2~f_1~f_2]$ is in $N(B)$ exactly if
$$ U_0 \begin{pmatrix}p_1\\p_2 \end{pmatrix}= - F\begin{pmatrix}f_1\\f_2 \end{pmatrix}$$that is, if
\begin{align*} -p_1 + p_2 &=-2f_1 -f_2\\ p_2&= -f_1 -2f_2. \end{align*}To find a basis for $N(B)$, we solve this system of equations when $[f_1~f_2]=[1~0]$ and when $[f_1~f_2]=[0~1]$. When $[f_1~f_2]=[1~0]$, we get
\begin{align*} -p_1 + p_2 &=-2\\ p_2&= -1, \end{align*}so $p_2=-1$ and $p_1=1$ and the element of the nullspace is $v_1=[1~-1~1~0]$. When $[f_1~f_2]=[0~1]$, we get
\begin{align*} -p_1 + p_2 &=-1\\ p_2&= -2, \end{align*}so $p_2=-2$ and $p_1=-1$. The element of the nullspace is $v_2=[-1~-2~0~1]$.
A basis of $N(B)$ is $\{v_1, v_2\}$.
To find the nullspace of $N(AB)$, we could do the matrix multiplication $AB$ and repeat the steps we did above to find $N(B)$. But there's a much easier way. Because $A$ is invertible, a vector $x$ satisfies $ABx=0$ exactly when $Bx=A^{-1}0$. Since $A^{-1}0=0$, this means that $x$ is in $N(AB)$ only if $x$ is in $N(B)$. That is, $N(AB)=N(B)$, so a basis of $N(AB)$ is $\{v_1, v_2\}$.
(b) Remember that to find the complete solution to $ABx=b$, we first find a particular solution $x_p$. Then the complete solution will be $x_p + \alpha_1 v_1 + \alpha_2 v_2$, where $\alpha_1, \alpha_2$ are any scalars.
To find a particular solution without doing any matrix multiplication, rewrite the equation as $Bx_p=A^{-1}b$ (which you can do because $A$ is invertible). Now, remember that $A^{-1}b$ should be interpreted as "the vector $y$ such that $Ay=b$". We can solve for $y$ using back-subsitition and get $y=[4~-5~7]$. So now we want a solution to
$$ Bx_p=\begin{pmatrix}-1\\5\\7\end{pmatrix}. $$To solve this, we do Gaussian elimination again, this time doing the same row operations to both sides of the equation. We get
$$ \begin{pmatrix} -1 & 1 & 2 & 1 \\ 0 & 1 & 1 & 2 \\ 0 & 0 & 0 & 0 \end{pmatrix}\begin{pmatrix} p_1\\p_2\\f_1\\f_2\end{pmatrix}=\begin{pmatrix}4\\7\\0\end{pmatrix}. $$To find a particular solution, we set $f_1=f_2=0$ and then solve for $p_1$ and $p_2$. Doing the matrix multiplication, we get the equations \begin{align*} -p_1 + p_2&=4\\ p_2&= 7. \end{align*} So we have $x_p=[3~7~0~0]$. The complete solution is $x_c=x_p + \alpha_1 v_1 + \alpha_2 v_2$.
$Ax = b_1$ has no solution, and the complete solution to $Ax=b_2$ is: $$ x = \begin{pmatrix} 1\\2 \\3\\4 \end{pmatrix} + \alpha_1 \begin{pmatrix} 1\\1 \\0\\-1 \end{pmatrix} + \alpha_2 \begin{pmatrix} -2\\0 \\1\\-2 \end{pmatrix} $$ for all possible scalars $\alpha_1$ and $\alpha_2$.
Give one example of a possible matrix $A$ (with all nonzero entries) and possible right-hand sides $b_1$ and $b_2$ (with any entries you want) that are consistent with the above facts. (The same $A$ for both $b_1$ and $b_2$.)
Hint: start by thinking about possible sizes and ranks for $A$, and then think how the columns are/aren't linearly dependent.
$A$ must have 4 columns, since $x$ is $4 \times 1$. Since $x$ is the complete solution to $Ax=b_2$, we know that $N(A)$ has dimension 2. The rank of $A$ is the number of columns minus the dimension of $N(A)$, so the rank of $A$ is 2. This means that $A$ must have at least 2 rows. If $A$ has exactly 2 rows, it would have full row rank and solutions to $Ax=b$ would exist for all $b$. We don't want this to happen, so we should make $A$ have more than 2 rows. So we will look for a rank 2 $A$ with 4 columns and 3 rows.
Let the columns of $A$ be $c_1, c_2, c_3$ and $c_4$. A basis for $N(A)$ is $\{[1 ~ 1~0~-1], [-2~0~1~-2]\}$. We can simply read off a linear relation involving columns 1,2,4 from the vector $[1 ~ 1~0~-1]$ in $N(A)$. Since
$$A \begin{pmatrix} 1\\1 \\0\\-1 \end{pmatrix}=c_1+c_2-c_4 =0 $$we have that $c_2= -c_1 + c_4$. We can also read off a linear relation involving columns 1, 3, 4: since
$$ A\begin{pmatrix} -2\\0 \\1\\-2 \end{pmatrix}= -2c_1 + c_3 -2c_4 =0 $$we have that $c_3=2c_1 +2c_4$. So, for any choice of $c_1$ and $c_4$, we can determine $c_2$ and $c_3$. (In fact these nullspace vectors are exactly in the form of the "special solutions" from class: we can interpret $c_2$ and $c_3$ as the "free" columns of $A$, and $c_1$ and $c_4$ as the pivot columns.)
So to choose $A$, we just need to pick linearly independent vectors $c_1, c_4$ in $\mathbb{R}^3$ (to make $A$ rank 2!) with nonzero entries as required by the problem (and we need to make sure that $c_2$ and $c_3$ also have nonzero entries). One choice is
$$ c_1=\begin{pmatrix} 1\\1 \\1 \end{pmatrix} \quad \text{and} \quad c_4=\begin{pmatrix} 3\\2 \\2 \end{pmatrix}. $$Using the relations we determined above to solve for $c_2$ and $c_3$, we get
$$ A=\begin{pmatrix}1&2&8&3\\1&1&6&2\\1&1&6&2\end{pmatrix}. $$Now, $b_2=Ax$, where $x$ is given in the problem. So
$$b_2=\begin{pmatrix}1&2&8&3\\1&1&6&2\\1&1&6&2\end{pmatrix} \begin{pmatrix}1\\2\\3\\4\end{pmatrix}=\begin{pmatrix} 41\\29\\29\end{pmatrix}. $$Now we find $b_1$, which is any vector not in the column span of $A$. Notice that the final two rows of $A$ are identical. This means that the second and third entry of $Ax$ are always equal. That is, a vector $$y=\begin{pmatrix}y_1\\y_2\\y_3\end{pmatrix} $$ cannot be in the column span of $A$ unless $y_2=y_3$. So any vector with $y_2 \neq y_3$ will work as $b_1$; for example,
$$b_1=\begin{pmatrix}0\\1\\0\end{pmatrix} $$would work.
Consider the vectors: $$ a_1 = \begin{pmatrix} 0\\0\\0\\0\\0 \end{pmatrix}, \qquad a_2 = \begin{pmatrix} 1\\2\\3\\4\\5 \end{pmatrix}, \qquad a_3 = \begin{pmatrix} 1\\1\\5\\4\\9 \end{pmatrix}, \qquad a_4 = \begin{pmatrix} 1\\3\\1\\4\\1 \end{pmatrix}. $$
Give a basis for the orthogonal complement of the subspace (of $\mathbb{R}^5$) spanned by:
(a) $a_1$
(b) $a_2$
(c) $a_1,a_2,a_3,\mbox{ and }a_4$.
(Hint: this is a basis for $C(\_\_)^\perp = \_\_\_\_$.)
General strategy: as you saw in lecture, $C(A)^\perp=N(A^T)$. So if $V$ is a vector space, to find a basis of $V^\perp$, write down a matrix $B$ whose rows span $V$ ($V = C(B^T)$) and find a basis for $N(B)$.
(a) The subspace spanned by $a_1$ is the trivial subspace (just the zero vector). We don't need to use the hint to find a basis for the orthogonal complement of this subspace; $\{\vec{0}\}^\perp$ is the whole vector space $\mathbb{R}^5$, so a basis is $\{e_1, e_2, e_3, e_4\}$ (the columns of the $5\times 5$ identity matrix $I$, i.e. the Cartesian basis).
(b) Following the general strategy, we write down
$$B=\begin{pmatrix} 1 & 2& 3& 4& 5\end{pmatrix}. $$We need to compute a basis for $N(B)$. In this situation, $U_0= (1)$ is $1 \times 1$, and $F= \begin{pmatrix}2& 3& 4& 5\end{pmatrix}$ is $1 \times 4$. So $N(B)$ is 4-dimensional. To find a basis for $N(B)$, we solve $$U_0 p = -F f $$ for $p$, letting $f$ run over the standard basis for $\mathbb{R}^4$.
If $f=e_1$, the above equation gives $$p= -\begin{pmatrix}2& 3& 4& 5\end{pmatrix}\begin{pmatrix}1\\0\\0\\0\end{pmatrix}=-2 $$ so one basis vector for $N(B)$ is $$\begin{pmatrix}-2\\1\\0\\0\\0\end{pmatrix}. $$
Repeating this computation for $f=e_2, e_3, e_4$ gives the basis
$$\left\{ \begin{pmatrix}-2\\1\\0\\0\\0\end{pmatrix}, \begin{pmatrix}-3\\0\\1\\0\\0\end{pmatrix},\begin{pmatrix}-4\\0\\0\\1\\0\end{pmatrix},\begin{pmatrix}-5\\0\\0\\0\\1\end{pmatrix} \right\}. $$(c) Following the general strategy, we write down
$$B=\begin{pmatrix} 1&1&5&4&9\\ 1&2&3&4&5\\ 1&3&1&4&1\\ 0&0&0&0&0\\ \end{pmatrix}. $$To find a basis for $N(B)$, we do Gaussian elimination:
$$\begin{pmatrix} 1&1&5&4&9\\ 1&2&3&4&5\\ 1&3&1&4&1\\ 0&0&0&0&0\\ \end{pmatrix} \xrightarrow{r_2-r_1, r_3-r_1} \begin{pmatrix} 1&1&5&4&9\\ 0&1&-2&0&-4\\ 0&2&-4&0&-8\\ 0&0&0&0&0\\ \end{pmatrix}\xrightarrow{r_3-2r_2} \begin{pmatrix} 1&1&5&4&9\\ 0&1&-2&0&-4\\ 0&0&0&0&0\\ 0&0&0&0&0\\ \end{pmatrix}. $$Columns 1 and 2 are pivot columns; the rest are free. So $N(B)$ is 3-dimensional. To find a basis of $N(B)$ we solve \begin{align*} U_0 p &= -F f\\ \begin{pmatrix} 1 & 1\\ 0& 1 \end{pmatrix} p &= \begin{pmatrix} -5&-4&-9\\ 2&0&4 \end{pmatrix}f \end{align*} for $p$ when $f=e_1, e_2, e_3$.
When $f=e_1$, the above equation becomes $$\begin{pmatrix} 1 & 1\\ 0& 1\end{pmatrix} \begin{pmatrix} p_1\\ p_2 \end{pmatrix} = \begin{pmatrix} -5\\ 2 \end{pmatrix}. $$
By back substitution, $p_2=2$ and $p_1=-7$. The corresponding basis vector of $N(B)$ is $(-7 \ 2 \ 1\ 0\ 0)$.
Repeating this computation for $f=e_2, e_3$, we obtain the following basis of $N(B)$:
$$\left\{ \begin{pmatrix}-7\\ 2\\1\\0\\0\end{pmatrix},\begin{pmatrix}-4\\ 0\\0\\1\\0\end{pmatrix}, \begin{pmatrix}-13\\ 4\\0\\0\\1\end{pmatrix} \right\}. $$