\documentclass[12pt]{article}
\input{../macros.tex}
\begin{document}

\thispagestyle{plain}

\setcounter{session}{11}
\begin{center}
\textbf{Exercises on matrix spaces; rank 1; small world graphs}
\end{center}

\begin{problem} [Optional] (3.5 \#41.  {\em Introduction to Linear Algebra:} Strang) Write the 3 by 3 identity matrix as a combination of the other five permutation matrices. Then show that those five matrices are linearly independent. (Assume a combination gives $c_1 P_1 + \dots + c_5 P_5  = 0$ and check entries to prove $c_i$ is zero.) The five permutation matrices are a basis for the subspace of three by three matrices with row and column sums all equal.
\end{problem}

\solution{ The other five permutation matrices are:
$$P_{21} = \threebythree {} 1 {} 1 {} {} {} {} 1 , P_{31} = \threebythree {} {} 1 {} 1 {} 1 {} {} , P_{32} = \threebythree 1 {} {} {} {} 1 {} 1 {} , $$
$$ P_{32} P_{21} = \threebythree {} 1 {} {} {} 1 1 {} {} \text{ and } P_{21} P_{32} = \threebythree {} {} 1 1 {} {} {} 1 {}.$$

Since $P_{21} + P_{31} + P_{32}$ is the all ones matrix and $P_{32} P_{21} + P_{21} P_{32}$ is the matrix with zeros on the diagonal and ones elsewhere, $$I = P_{21} + P_{31} + P_{32} - P_{32} P_{21} - P_{21} P_{32}.$$ For the second part, setting $c_1P_1 + \cdots + c_5P_5$ equal to zero gives:
$$\threebythreec {c_3} {c_1 + c_4} {c_2 + c_5} {c_1 + c_5} {c_2} {c_3 + c_4} {c_2 + c_4} {c_3 + c_5} {c_1} = 0. $$
So $c_1 = c_2 = c_3 = 0$ along the diagonal, and $c_4 = c_5 = 0$ from the off-diagonal entries.  
}

\begin{problem} (3.6 \#31.) $\mathbf{M}$ is the space of three by three matrices. Multiply each matrix $X$ in $\mathbf{M}$ by: 
$$A = \threebythree 1 0 {-1} {-1} 1 0 0 {-1} 1 $$
Notice that $A \threebyone 1 1 1 = \threebyone 0 0 0$.

\begin{enumerate}[a)]

\item Which matrices $X$ lead to $AX =0?$

\item Which matrices have the form $AX$ for some matrix $X?$

\item  Part (a) finds the ``nullspace" of the operation $AX$ and part (b) finds the ``column space." What are the dimensions of those two subspaces of $\mathbf{M}$? Why do the dimensions add to $(n-r) + r = 9?$
\end{enumerate}
\end{problem}

\solution{
\begin{enumerate}[a)]
\item We can use row reduction or some other method to see that the rows of $\mb A$ are dependent and that $A$ has rank $2$.  Its nullspace has the basis:
$$\threebyone 1 1 1.$$ $AX=0 $ precisely when the columns of $X$ are
in the nullspace of $A$, i.e. when they are multiples of the basis of
$N(A)$. Therefore, if $\mb A \mb X = \mb 0$ then $X$ must have the
form:
$$X = \threebythree a b c a b c a b c.$$

\item On the other hand, the columns of any matrix  of the form $AX$ are linear combinations of the columns of $A.$ That is, they are vectors whose components all sum to 0, so a matrix has the form $AX$ if and only if all of its columns individually sum to 0:
$$AX = B \text{ if and only if } B = \threebythreec a b c d e f {-a-d} {-b-e} {-c-f} .$$

\item The dimension of the ``nullspace" is 3, while the
dimension of the ``column space" is 6. These add up to 9, which is the
dimension of the space of ``inputs" $\vb M$.
\end{enumerate}
}

\end{document}