\documentclass{article}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{enumerate}

\usepackage{hyperref}

\usepackage{ifthen}
\usepackage{ulem} % for strikethrough \sout{...} command
\usepackage{color}

\usepackage{wasysym}

\usepackage{tikz} % diagram package

\usetikzlibrary{calc}

%\pagestyle{empty}

\setlength{\unitlength}{0.1in}

\setlength{\oddsidemargin}{-0.25in}
\setlength{\evensidemargin}{-0.25in}
\setlength{\topmargin}{-0.45in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\topskip}{0.0in}
\setlength{\textheight}{9.6in}
\setlength{\textwidth}{7in}

%\newcommand{\comp}{ \,{\scriptstyle \stackrel{\circ}{}}\, } 
%\newcommand{\nullset}{\mathrm{O}\!\!\!\!\big/\,}

%\def\myfrac#1#2{
%    \hspace{3pt}\!\!\!$^{#1}\!\!\hspace{1pt}/\hspace{2pt}\!\!_{#2}$\!\!\!\hspace{3pt}
%} 

\newcommand{\bdot}{\, {\scriptstyle{\bullet}} \,}
\newcommand{\B}[1]{{\bf {#1}}}
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}

\newcommand{\myspace}{\parbox[c][0.25in]{0.25in}{\hfill}}
\newcommand{\varspace}[2]{\mbox{\parbox[c][#1]{#2}{\hfill}}}
\newcommand{\force}{{\noindent $\mbox{\;}$}}

\newcommand{\diagquotient}[2]{\displaystyle{{#1 \atop \;}\hspace*{-0.1in} \mbox{\put(0,0){\line(2,1){2}}} \hspace*{0.1in} {\; \atop #2}}}

\newcommand{\F}{\mathbb{F}}
\newcommand{\K}{\mathbb{K}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\C}{\mathbb{C}}

\newcommand{\LEMMA}{\vspace{0.1in} \noindent \fbox{\large\bf Lemma:}  }
\newcommand{\COR}{\vspace{0.1in} \noindent \fbox{\large\bf Corollary:}  }
\newcommand{\PROP}{\vspace{0.1in} \noindent \fbox{\large\bf Proposition:}  }
\newcommand{\DEF}{\vspace{0.1in} \noindent \fbox{\large\bf Definition:}  }
\newcommand{\THM}{\vspace{0.1in} \noindent \fbox{\large\bf Theorem:}  }
\newcommand{\EX}{\vspace{0.1in} \noindent \fbox{\large\bf Example:}  }
\newcommand{\bproof}{\vspace{0.05in} \noindent {\bf Proof:} }
\newcommand{\eproof}{$\blacksquare$ \vspace{0.05in}}

\newcommand{\vsp}{\vspace{0.05in}}

\newcommand{\HEAD}[1]{\vspace{0.05in} \noindent {\large\bf #1} \vspace{0.05in}}

\definecolor{ignoreGray}{rgb}{0.75,0.75,0.75}
\newcommand{\ig}{\color{ignoreGray}}

\newcommand{\E}[2]{\B e_{#1}\B e_{#2}^T}

\begin{document}

\noindent
{\bf Math 2240}
\hfill {\Large \bf The Linear Correspondence Between Columns} \hfill 
{\bf Linear Algebra}

\vspace{0.05in}

It will be extremely useful to notice that when we preform elementary row operations on a matrix, the linear relationships between the columns of that matrix do not change. But first, what is meant by {\it linear relationships}?

\vspace{0.05in}

\HEAD{Linear Relationships:}

Without being too formal, when we say {\it scalar} we will just mean a real number and when we refer to {\it vectors} we mean objects that we can add and scale (by scalars). A {\bf linear combination} of vectors is a finite sum of scalar multiples of vectors. For example, suppose $\B u$, $\B v$, and $\B w$ are vectors and $r$, $s$, and $t$ are scalars. Then $r\B u+s\B v+t\B w$ is a linear combination of the vectors $\B u$, $\B v$, and $\B w$. When we refer to a {\it homogeneous linear relationship} we are referring to an equality between two linear combinations or a linear combination set equal to zero. In particular,  $r\B u+s\B v+t\B w = \B 0$ and $r\B u+s\B v=t\B w$ are examples of homogeneous linear relationships.

\vspace{0.05in}

\HEAD{The Linear Correspondence:}

As we perform row operations, the columns of our matrix are never mixed. This means that any homogeneous linear relationship among the columns of our original matrix will still hold among the corresponding columns of that matrix after we have performed a bunch of row operations. In particular, say $\B a$, $\B b$, and $\B c$ are columns of a matrix $A$, and suppose we perform some row operations and 
get $A'$ whose corresponding columns are $\B a'$, $\B b'$, and $\B c'$. In this context we have: \[ x\B a+y\B b+z\B c=\B 0 \qquad \mathrm{if\;and\;only\;if} \qquad x\B a'+y\B b'+z\B c'=\B 0 \]
for real numbers $x$, $y$, and $z$. This also holds for bigger or smaller collections of columns. Why? Essentially, since we are preforming {\bf row} operations,
the relationships between {\bf columns} are unaffected -- we aren't ``mixing'' the columns together. 

Formally, if $A$ is row equivalent to $B$, then there exists an invertible matrix $P$ such that $PA=B$ (this will be discussed in detail later). A homogeneous relation among the columns can be written as $A\B c = \B 0$ (multiplying a matrix by a vector yields a linear combination of columns of that matrix). Notice that if $A\B c=\B 0$ then $PA\B c = P\B 0$ so that $B\B c=\B 0$. Conversely if $B\B c = \B 0$, then $P^{-1}B\B c=P^{-1}\B 0$ so that $A\B c=\B 0$. Therefore, the (homogeneous) relations among the columns of $A$ also hold among the columns of $B$ (and vice-versa).

\EX

\vspace{-0.1in}

\[ \begin{bmatrix}  0 &  1 & -1 \\
                   -1 &  0 & -2 \\
                    2 &  1 &  3 \end{bmatrix} \stackrel{R1 \leftrightarrow R2}{\widetilde{\qquad}}
   \begin{bmatrix} -1 &  0 & -2 \\
                    0 &  1 & -1 \\
                    2 &  1 &  3 \end{bmatrix} \stackrel{2R1 + R3}{\widetilde{\qquad}}
   \begin{bmatrix} -1 &  0 & -2 \\
                    0 &  1 & -1 \\
                    0 &  1 & -1 \end{bmatrix} \stackrel{-R2 + R3}{\widetilde{\qquad}}
   \begin{bmatrix} -1 &  0 & -2 \\
                    0 &  1 & -1 \\
                    0 &  0 &  0 \end{bmatrix} \stackrel{-1 \times R1}{\widetilde{\qquad}}
   \begin{bmatrix}  1 &  0 &  2 \\
                    0 &  1 & -1 \\
                    0 &  0 &  0 \end{bmatrix} \]

\noindent
In the RREF (on the far right) we have that the final column is 2 times the first column plus $-1$ times the second column.
\[ 2 \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} -1 \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 2 \\ -1 \\ 0 \end{bmatrix} \]
So this must be true for all of the other matrices as well. In particular, we have that the third column of the original matrix is
2 times the first column plus $-1$ times the second column:
\[ 2 \begin{bmatrix} 0 \\ -1 \\ 2 \end{bmatrix} -1 \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix} = \begin{bmatrix} -1 \\ -2 \\ 3 \end{bmatrix} \]

\HEAD{Why is this so important?} 


First, Gauss-Jordan elimination typically requires a lot of computation. This correspondence gives you a way to check that you have row-reduced correctly! In some cases, the linear relations among columns are {\it obvious} and we can just {\it write down the RREF without performing Gaussian elimination at all!} We will see other applications of this correspondence later in the course.

\EX Let $A = \begin{bmatrix} 3 & -6 \\ -2 & 4 \end{bmatrix}$. Notice that the first column is nonzero (it will be our first pivot column). In our RREF this becomes $\begin{bmatrix} 1 \\ 0 \end{bmatrix}$. The second column is just $-2$ times the first, so the second column of our RREF must be $-2\begin{bmatrix} 1 \\ 0 \end{bmatrix} = \begin{bmatrix} -2 \\ 0 \end{bmatrix}$. Therefore, the RREF of $A$ is $\begin{bmatrix} 1 & -2 \\ 0 & 0 \end{bmatrix}$.


\EX Let $B$ be a $3 \times 3$ matrix whose RREF is $\displaystyle{\begin{bmatrix} 1 & 0 & -1 \\ 0 & 1 & 2 \\ 0 & 0 & 0 \end{bmatrix}}$.
Suppose the first column of $B$ is $\displaystyle{\begin{bmatrix} 1 \\ 4 \\ 7 \end{bmatrix}}$ and the second is
$\displaystyle{\begin{bmatrix} 2 \\ 5 \\ 8 \end{bmatrix}}$. Then, by the linear correspondence, we know the third column must be
$\displaystyle{-1 \cdot \begin{bmatrix} 1 \\ 4 \\ 7 \end{bmatrix} + 2 \cdot \begin{bmatrix} 2 \\ 5 \\ 8 \end{bmatrix}
=\begin{bmatrix} 3 \\ 6 \\ 9 \end{bmatrix}}$. 

\vspace{-0.1in}

\noindent
Therefore, the mystery matrix is
$\displaystyle{B = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix}}$.

%\vspace{0.1in}

\EX Let $C$ be a matrix whose RREF is $\displaystyle{\begin{bmatrix} 0 & 1 & 2 & 0 & 3 \\ 0 & 0 & 0 & 1 & -2 \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix}}$.  Suppose we know the first {\bf pivot} column (i.e. the second column) of $C$ is $\displaystyle{\begin{bmatrix} 2 \\ -1 \\ 3 \end{bmatrix}}$ and the second pivot column (i.e. the fourth column)
is $\displaystyle{\begin{bmatrix} -1 \\ 4 \\ 2 \end{bmatrix}}$. Then, by the linear correspondence, we know the third and fifth columns must be\dots

\vspace{-0.1in}

\[ 2 \cdot \begin{bmatrix} 2 \\ -1 \\ 3 \end{bmatrix} = \begin{bmatrix} 4 \\ -2 \\ 6 \end{bmatrix} \qquad \mbox{and} \qquad
   3 \cdot \begin{bmatrix} 2 \\ -1 \\ 3 \end{bmatrix} -2 \cdot \begin{bmatrix} -1 \\ 4 \\ 2 \end{bmatrix} = \begin{bmatrix} 8 \\ -11 \\ 5 \end{bmatrix} \]
Therefore, the mystery matrix is
$\displaystyle{C = \begin{bmatrix} 0 & 2 & 4 & -1 & 8 \\ 0 & -1 & -2 & 4 & -11 \\ 0 & 3 & 6 & 2 & 5 \end{bmatrix}}$.

%\vspace{0.05in}

\HEAD{Homework Problems:}

\vspace{-0.05in}

\begin{enumerate}  %\setcounter{enumi}{4}
\item Look back at the RREF handout exercises and examples as well as other Gaussian elimination exercises and verify that the linear correspondence holds between the each matrix, its REF, and its RREF.

\item I just finished row reducing the matrix $\displaystyle{\begin{bmatrix} 1 & 2 & 3 \\ 0 & 1 & -1 \\ 1 & 5 & 0 \end{bmatrix}}$ and
    got $\displaystyle{\begin{bmatrix} 1 & 0 & 3 \\ 0 & 1 & -1 \\ 0 & 0 & 0 \end{bmatrix}}$. Something's wrong. Just using the linear 
    correspondence explain how I know something's wrong and then find the real RREF (without row reducing).
    
\item A certain matrix has $\displaystyle{\begin{bmatrix} 1 & 2 & 0 & -1 & 2 \\ 0 & 0 & 1 & 1 & 3 \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix}}$ as its RREF.
    The first column of this matrix is $\displaystyle{\begin{bmatrix} 2 \\ 0 \\ 1 \end{bmatrix}}$ and the third column is 
    $\displaystyle{\begin{bmatrix} -1 \\ 1 \\ 2 \end{bmatrix}}$. Find the matrix.

\item A certain matrix has $\displaystyle{\begin{bmatrix} 1 & 2 & 0 & 5 & -2 \\ 
                                                                                                                   0 &  0 & 1 & 3 & 1 \\ 
                                                                                                                   0 &  0 & 0 & 0 & 0 \\ 
                                                                                                                   0 &  0 & 0 & 0 & 0 \end{bmatrix}}$ as its RREF.
    The second column of this matrix is $\displaystyle{\begin{bmatrix} 2 \\ 4 \\ 6 \\ 8 \end{bmatrix}}$ and the last column is $\displaystyle{\begin{bmatrix} 4 \\ 4 \\ 4 \\ 4 \end{bmatrix}}$. Find the matrix.

\vspace{-0.1in}

\item A certain matrix has $\displaystyle{\begin{bmatrix} 1 & -5 & 0 & 3 & 0 & -1 \\ 
                                                                                                                   0 &  0 & 1 & 2 & 0 & 4 \\ 
                                                                                                                   0 &  0 & 0 & 0 & 1 & 2 \end{bmatrix}}$ as its RREF.
    The first pivot column of this matrix is

$\displaystyle{\begin{bmatrix} 3 \\ -1 \\ 2 \end{bmatrix}}$, the second pivot column is
    $\displaystyle{\begin{bmatrix} 1 \\ -1 \\ 1 \end{bmatrix}}$, and the third pivot column is $\displaystyle \begin{bmatrix} 2 \\ 3 \\ 1 \end{bmatrix}$. 
    Find the matrix.

\item $2 \times 2$ matrices can row reduce to either $\displaystyle \begin{bmatrix} 0 & 0 \\ 0 & 0 \end{bmatrix}$, $\displaystyle \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}$, $\displaystyle \begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix}$, or $\displaystyle \begin{bmatrix} 1 & c \\ 0 & 0 \end{bmatrix}$ for some $c \in \mathbb{R}$.

\noindent
What can be said about the original matrices in each of these cases?
\end{enumerate}

\newpage

\HEAD{Answers:}

\vspace{-0.05in}

\begin{enumerate} %\setcounter{enumi}{4}

\item If you would like a particular example worked out, just ask!

\item According to the linear correspondence, the final column of my matrix should be 3 times the first pivot column minus the second pivot column. However, $\displaystyle 3 \cdot \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix} - 1 \cdot \begin{bmatrix} 2 \\ 1 \\ 5 \end{bmatrix} = \begin{bmatrix} 3-1 \\ 0-1 \\ 3-5 \end{bmatrix} = \begin{bmatrix} 2 \\ -1 \\ -2 \end{bmatrix}$ which does not match the third column of my original matrix. So the RREF must be wrong.

Let's find $a$ and $b$ so that $a$ times column 1 plus $b$ times column 2 is column 3. In the final column of the original matrix, the second entry is ``$-1$''. So we must have $b=-1$. Thus $a \cdot$(column 1) $=$ (column 2) $+$ (column 3). Adding those columns together, we get $\displaystyle \begin{bmatrix} 5 \\ 0 \\ 5 \end{bmatrix}$. This is 5 times the first column. So $a=5$. Therefore, the correct RREF is $\displaystyle{\begin{bmatrix} 1 & 0 & 5 \\ 0 & 1 & -1 \\ 0 & 0 & 0 \end{bmatrix}}$. 

\item According to the RREF, the second column is 2 times the first column, the fourth column is obtained by subtracting the first column from the third column (i.e. the second pivot column), and the last column is twice the first column plus 3 times the third column. This gives us 
$\displaystyle \begin{bmatrix} 2 & 4 & -1 & -3 & 1 \\
                                                  0 & 0 & 1 & 1 & 3 \\
                                                  1 & 2 & 2 & 1 & 8 \end{bmatrix}$.

\item According to the RREF, the second column is twice the first column. Thus the first column must be $\displaystyle \begin{bmatrix} 1 \\ 2 \\ 3 \\ 4 \end{bmatrix}$. The last column is $-2$ times the first column plus the second pivot column (i.e. column 3). Thus the second pivot column must be $\displaystyle \begin{bmatrix} 4 \\ 4 \\ 4 \\ 4 \end{bmatrix} + 2 \cdot \begin{bmatrix} 1 \\ 2 \\ 3 \\ 4 \end{bmatrix} = \begin{bmatrix} 6 \\ 8 \\ 10 \\ 12 \end{bmatrix}$. And finally, the fourth column is 5 times the first column plus 3 times the third column. So we get 
$\displaystyle \begin{bmatrix} 1 & 2 &   6  & 23 & 4 \\
                                                  2 & 4 &   8 & 34 & 4 \\
                                                  3 & 6 & 10 & 45 & 4 \\
                                                  4 & 8 & 12 & 56 & 4 \end{bmatrix}$.

\item The second column is $-5$ times the first, the fourth column is $3$ times column 1 plus $2$ times column 3 (the second pivot column), and the sixth column is $-1$ times the first column, $4$ times the third column, and $2$ times the fifth column (the third pivot column). Thus we get
$\displaystyle \begin{bmatrix} 3 & -15 &  1 & 11 & 2 & 5 \\
                                                -1 &    5 & -1 & -5  & 3 & 3 \\
                                                 2 & -10 &   1 &  8 &  1 & 4 \end{bmatrix}$.

\item If your RREF is the zero matrix, you must have started with the zero matrix (the result of doing or undoing any row operation on a zero matrix yields a zero matrix): $\begin{bmatrix} 0 & 0 \\ 0 & 0 \end{bmatrix}$. 

If your RREF is the identity matrix $\left(\mbox{i.e.} \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}\;\right)$, then the linear correspondence guarantees both columns of the original matrix are non-zero and they must not be multiples of each other. For example, $\begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}$.

If your RREF is the third option, then the first column of your original matrix was zeros and the second column was nonzero. For example, $\begin{bmatrix} 0 & 1 \\ 0 & 2 \end{bmatrix}$.

Finally, in the last case, the second column of the original matrix must be $c$ times the (nonzero) first column (the second column is a multiple of a nonzero first column). For example, $\begin{bmatrix} 1 & c \\ 2 & 2c \end{bmatrix}$.
\end{enumerate}


\end{document}
