% DEFINE some information that will be populated throughout the course notes.
\def \coursename {Linear Algebra}
\def \coursecode {MATH 2221}
\def \courseterm {Winter 2020}
\def \instructorname {Nathan Johnston}
% END DEFINITIONS


% IMPORT the course note formatting and templates
\input{course_notes_template}
% END IMPORT
	
	
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setcounter{chapter}{4} % Set to one less than the week number
\chapter{Systems of Linear Equations}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

{\large This week we will learn about:
	
	\begin{itemize}
		\item Systems of linear equations,
		\item Elementary row operations and Gaussian elimination, and
		\item The (reduced) row echelon form of a matrix.
	\end{itemize}\bigskip\bigskip
	
	\noindent Extra reading and watching:
	\begin{itemize}
		\item Section 2.1 in the textbook
		\item Lecture videos \href{https://www.youtube.com/watch?v=vkAODMUCx1Y&list=PLOAf1ViVP13jmawPabxnAa00YFIetVqbd&index=17}{17}, \href{https://www.youtube.com/watch?v=LIBRGoIhsNs&list=PLOAf1ViVP13jmawPabxnAa00YFIetVqbd&index=18}{18}, \href{https://www.youtube.com/watch?v=CWO2qcC3Wds&list=PLOAf1ViVP13jmawPabxnAa00YFIetVqbd&index=19}{19}, \href{https://www.youtube.com/watch?v=KB26QVozvbM&list=PLOAf1ViVP13jmawPabxnAa00YFIetVqbd&index=20}{20}, and \href{https://www.youtube.com/watch?v=vNddfcsVB7M&list=PLOAf1ViVP13jmawPabxnAa00YFIetVqbd&index=21}{21} on YouTube
		\item \href{http://en.wikipedia.org/wiki/System_of_linear_equations}{System of linear equations} at Wikipedia
		\item \href{http://en.wikipedia.org/wiki/Gaussian_elimination}{Gaussian elimination} at Wikipedia
	\end{itemize}\bigskip\bigskip
	
	\noindent Extra textbook problems:
	\begin{itemize}
		\item[$\star$] 2.1.1, 2.1.2, 2.1.4, 2.1.5
		\item[$\star \, \star$] 2.1.7--2.1.9, 2.1.11, 2.1.15--2.1.17, 2.1.25, 2.1.26
		\item[$\star\star\star$] 2.1.18, 2.1.23, 2.1.24, 2.1.27--2.1.29
		\item[$\skull$] none this week
	\end{itemize}}


\newpage

\section*{(Systems of) Linear Equations}

Much of linear algebra is about solving and manipulating the simplest types of equations that exist---linear equations:

\begin{definition}[Linear Equations]
	A \textbf{linear equation} in $n$ variables $x_1, x_2, \ldots, x_n$ is an equation that can be written in the form
	\begin{align*}
	a_1x_1 + a_2x_2 + \cdots + a_nx_n = b,
	\end{align*}
	where $a_1, a_2, \ldots, a_n$ and $b$ are constants.
\end{definition}

\exx[8]{Examples of linear and non-linear equations.}
% make sure to throw in some weird linear ones like pi*x + sin(3)*y = (1-sqrt(2))z
% Make up some and ask students to guess
% include x*y + z = 1 as a non-linear example (or one like it)

The point is that an equation is linear if each variable is only multiplied by a constant: variables cannot be multiplied by other variables, they can only be raised to the first power, and they cannot have other functions applied to them. \\

You (hopefully) learned how to manipulate linear equations quite some time ago, and then you ``ramped up'' to non-linear equations (like $x^2 = 2$ or $2^x = 8$). In this course, we instead ``ramp up'' in a different direction: we work with multiple linear equations simultaneously.


\newpage


\begin{definition}[Systems of Linear Equations]
	A \textbf{system of linear equations} (or a \textbf{linear system}) is a finite set of linear equations, each with the same variables $x_1, x_2, \ldots, x_n$.
\end{definition}


\noindent Some more terminology:
\begin{itemize}
	\item A \textbf{solution} of a system of linear equations is a vector $\x = (x_1,x_2,\ldots,x_n)$ whose entries satisfy \emph{all} of the linear equations in the system.
	
	\item The \textbf{solution set} of a system of linear equations is the set of \emph{all} solutions of the system. \\
\end{itemize}


% END OF CLASS 13


\exx[7]{Solving a linear system geometrically.}
% Ask students for a system of two equations in two unknowns with SMALL coefficients. eg 2x-y = 3, x + 3y = 5. Find a solution. Find something that satisfies one equation but not the other, and is thus not a solution.
% Do not find the solution algebraically, but instead graph the solution as the intersection of the two lines and eye-ball it. Then plug it back into the equations and see that it works.
% Make sure the example you pick has a unique solution (easy to see by inspection)

\exx[5]{Two more (weirder!) systems of linear equations.}
% Plot the systems of equations x-y = 2, 2x-2y = 4, and x-y=1, x-y=3. These are the infinite solutions and no solutions cases.
% Better yet: do this same thing, except take the first equation from the student-created example on the previous page. E.g., if they choose 2x-y = 3 as their first equation, then the infinite solutions system would be 2x-y=3 and 4x-2y=6, and the no solutions system could be 2x-y=3 and 2x-y=1.


\newpage


\horlines{5}

The above examples show that systems of linear equations can have no solutions, exactly one solution, or infinitely many solutions. We will show shortly that these are the only possibilities. \\

Note that we can also visualize systems of linear equations with 3 variables in 3 dimensions, but it's a bit tougher:

\horlines{4}
% Insert week5/lin_sys_3d.png
% make note of how many solutions each system has


\section*{Matrix Equations}

One of the primary uses of matrices is that they give us a way of working with linear systems much more compactly and cleanly. In particular, any system of linear equations...

\horlines{4}
% a_{1,1}x_1 + a_{1,2}x_2 + ... + a_{1,n}x_n = b_1
% a_{2,1}x_1 + a_{2,2}x_2 + ... + a_{2,n}x_n = b_2
% ...
% a_{m,1}x_1 + a_{m,2}x_2 + ... + a_{m,n}x_n = b_m


\newpage


\noindent can be rewritten as a single matrix equation:

\horlines{6}
% Ax = b
% where A, x, b are defined entry-wise in the obvious ways.
% Clarify that A and b are full of constants given ahead of time, and x is a vector of variables.
% Note that A is called the "coefficient matrix"


\exx[3]{Write the following system of linear equations as a single matrix equation:}
% Maybe do one of the 2x2 earlier examples.


The advantage of writing linear systems in this way (beyond the fact that it requires less writing) is that we can now make use of the various properties of matrices and matrix multiplication that we already know to help us understand linear systems a bit better. For example, we can now prove the observation that we made earlier: every linear system has either $0$, $1$, or infinitely many solutions.

\begin{theorem}[Trichotomy for Linear Systems]
	Every system of linear equations has either
	\begin{enumerate}[label=\alph*)]
		\item no solutions, 
		
		\item exactly one solution, or
		
		\item infinitely many solutions.
	\end{enumerate}
\end{theorem}


\newpage


\begin{proof}
	We just need to show that if a linear system has at least two different solutions, then it has infinitely many solutions.
	
	\horlines{8}\vspace*{-1.3cm}
% Suppose two solutions x1 and x2. Then for any scalar c, we have A((1-c)x1 + x2) = (1-c)Ax1 + cx2 = (1-c)b + cb = b, so (1-c)x1 + x2 is a solution, so there are infinitely many solutions if there are 2.
\end{proof}


When a system of linear equations has at least one solution (i.e., in cases~(b) and~(c) of the theorem), it is called \textbf{consistent}. If it has no solutions (i.e., in case~(a) of the theorem), it is called \textbf{inconsistent}.

% Go back to the three systems we looked at in R^2 and label them as consistent and inconsistent, as appropriate.


\section*{Solving Linear Systems}

Let's now discuss how we might find the solutions of a system of linear equations. If the linear system has a certain special form, then solving it is fairly intuitive.

\exx[6]{Solve the following system of linear equations: ${}\quad \begin{aligned}x+3y-2z & = 5 \\ 2y - 6z & = 4 \\ 3z & = 6\end{aligned}$\vspace*{-0.6cm}}
% Solve with back substitution. (x,y,z) = (-15,8,2)


\newpage


The procedure that we used to solve the previous example is called \textbf{back substitution}, and it worked because of the ``triangular'' nature of the equations. We were able to easily solve for $z$, which we then could plug into the second equation and easily solve for $y$, which we could plug into the first equation and easily solve for $x$.\\

\noindent So let's try to put \emph{every} system of equations into this triangular form! We start by

\horlines{3}
% eliminating the variable $x$ from the second and third equations, and then we eliminate the variable $y$ from the third equation (and then to actually \emph{solve} the system, we do back substitution like before). \\

To reduce the amount of writing we have to do when solving the linear system $A\x = \b$, we typically use the block matrix $[ \, A \ | \ \b \, ]$.

\exx[9]{Solve the following (much uglier) system of linear equations: \begin{align*}x+3y-2z & = 5 \\ 3x + 5y + 6z & = 7 \\ 2x + 4y + 3z & = 8 \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad {}\end{align*}\vspace*{-0.6cm}}
% IMPORTANT: DO two columns of calculations here. Left side: linear system. Right side: augmented matrix. Emphasize same thing, different notation.
% Solve via Gaussian elimination (but don't call it that yet). First get rid of x in (2,1) and (3,1)-entries, then y in (3,2)-entry. Should get exactly the triangular system from before (maybe rows will be off by scalar multiples, but close enough), so the solution is (x,y,z) = (-15,8,2), just like before.


% END OF CLASS 14


\newpage


\horlines{8}

There were three basic types of operations that we performed on the matrix when solving the previous system of linear equations. These are called the \textbf{elementary row operations}:
\begin{enumerate}
	\item Adding a multiple of a row to another row ($R_i + cR_j$).
	
	\vspace*{-0.2cm}\horlines{2}\vspace*{-0.4cm}
	% Do a simple 2x2 matrix example.
	
	\item Multiplying a row by a non-zero constant ($cR_i$).
	
	\vspace*{-0.2cm}\horlines{2}\vspace*{-0.4cm}
	% Do a simple 2x2 matrix example.
	
	\item Interchanging rows ($R_i \leftrightarrow R_j$).
	
	\vspace*{-0.2cm}\horlines{2}\vspace*{-0.4cm}
	% Do a simple 2x2 matrix example.
\end{enumerate}

These are the only operations we will ever need to solve a linear system!


\newpage


As mentioned before, our goal when solving these systems of equations is to first make the matrix ``triangular.'' We now make this a bit more precise.

\begin{definition}[(Reduced) Row Echelon Form]
	A matrix is in \textbf{row echelon form} if it satisfies both of these properties:
	\begin{enumerate}
		\item All rows consisting entirely of zeros are below the non-zero rows.
		
		\item In each non-zero row, the first non-zero entry (called the \textbf{leading entry}) is to the left of any leading entries below it.
	\end{enumerate}
	
	\noindent If the matrix also satisfies the following additional constraints, then it is in \textbf{reduced row echelon form} (\textbf{RREF}):
	\begin{enumerate}
		\item[c)] The leading entry in each non-zero row is $1$.
		
		\item[d)] Each leading $1$ is the only non-zero entry in its column.
	\end{enumerate}
\end{definition}


\exx[8]{Some matrices that are and are not in (reduced) row echelon form.}
% Do some examples. Give examples of matrices that are in RREF, regular REF but not RREF, and neither.

To solve a system of linear equations, we use elementary row operations to bring it into row echelon form. Once it is in this form, we can easily solve it via back-substitution.


\newpage


Alternatively, we can use elementary row operations to bring a matrix all the way into reduced row echelon form. Once an augmented matrix is in this form, the solutions of the associated linear system can be read directly from the entries of the matrix.

\exx[7]{Find the solutions of the systems of equations represented by the following augmented matrices:}
% One in REF, one in RREF



The process of using elementary row operations to bring a matrix into a row echelon form is called \textbf{row reduction}. The process of using row reduction to find a row echelon form, and then back substitution to solve the system of linear equations, is called \textbf{Gaussian elimination}.

\exx[4]{Use Gaussian elimination to solve the following system of linear equations: \[ \systeme{x+2y-4z = -4, 2x+4y = 0, -x+y+3z = 6} \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad {} \]}
% Put into augmented matrix and get into REF. Then back-substitute.
% Maybe mention the term "pivot" here.
% Mention that you should work left-to-right, top-down.
% Solution: (x,y,z) = (-2,1,1)


\newpage


\horlines{6}

\noindent Some notes about row echelon form and elementary row operations are in order:
\begin{itemize}
	\item The elementary row operations are reversible: if there is an elementary row operation that transforms $A$ into $B$, then there is an elementary row operation that transforms $B$ into $A$.
	
	\item Is the row echelon form of a matrix \quad \textbf{unique} \quad or \quad \textbf{not unique}? % NOT unique. Cross out unique, circle not unique.
	
	\item Two matrices are called \textbf{row equivalent} if one can be converted to the other via elementary row operations.
\end{itemize}

The process of using row reduction to find a \emph{reduced} row echelon form, and hence solve the system of linear equations, is called \textbf{Gauss--Jordan elimination}.

\exx[6]{Use Gauss--Jordan elimination to solve the following linear system: \[ \systeme{x+2y-4z = -4, 2x+4y = 0, -x+y+3z = 6} \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad {} \]}
% Same system as previous page. Already have in REF. Just go further to get RREF. Should get same answer as last time.
% Mention that you should work right-to-left, bottom-up.
% RREF:
% 1   0   0  -2
% 0   1   0   1
% 0   0   1   1


\newpage


\horlines{5}

\noindent Some notes about reduced row echelon form and Gauss--Jordan elimination are in order:
\begin{itemize}
	
	\item Neither Gaussian elimination nor Gauss--Jordan elimination is a ``better'' method than the other. Which one you use is typically just based on personal preference.
	
	\item Is the reduced row echelon form of a matrix \quad \textbf{unique} \quad or \quad \textbf{not unique}? % UNIQUE. Cross out not unique, circle unique.
	
	\item To check if two matrices are row equivalent, check whether or not they have the same reduced row echelon form.
\end{itemize}


\section*{Free Variables and Systems Without Unique Solutions}

Recall that systems of linear equations do not always have a unique solution: they might have no solutions or infinitely many solutions. Identifying systems with no solutions is intuitive enough...

\exx[3]{Solve the following system of linear equations: \[ \systeme{x+2y-2z = -4, 2x+4y+z = 0, x+2y+7z = 2} \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad {} \]}
% Create the augmented matrix and find an REF.
% RREF (any REF is fine though):
% 1   2   0   0
% 0   0   1   0
% 0   0   0   1
% Last row means 0x + 0y + 0z = 1, which is impossible.


\newpage


\horlines{4}


The behaviour in the previous example is what happens in general: a linear system has no solutions if and only if the row echelon forms of its augmented matrix $[ \, A \ | \ \b \, ]$ have a row consisting of zeros in the left ($A$) block and a non-zero entry in the right ($\b$) block. \\

Things are somewhat more complicated when a system of equations has infinitely many solutions, though. After all, how can we even \emph{describe} all of the solutions in this case? We illustrate the method with a couple more examples:

% END OF CLASS 15

\exx[9]{Solve the following system of linear equations: \[ \systeme{v - 2w + 2z = 3, x - 3z = 7, y + z = 4} \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad {} \]}
% Already in RREF. The point is v, x, and y can be expressed in terms of w and z, but that's it. Cannot specify w and z -- they can be anything. Introduce terms "free" and "leading" variables.


\newpage


\exx[12]{Solve the following system of linear equations: \[ \systeme{w - x - y + 2z = 1, 2w - 2x - y + 3z = 3, -w + x - y = -3} \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad {} \]}
% Create the augmented matrix and find the RREF.
% RREF:
% 1  -1   0   1   2
% 0   0   1  -1   1
% 0   0   0   0   0
% We get w and y as leading variables
% We can write leading variables in terms of free variables:
% w - x + z = 2, so w = 2+x-z
% y - z = 1, so y = 1+z

Again, the behaviour in the previous example is completely general: variables corresponding to columns that have a leading entry in the row echelon form are called \textbf{leading variables}, and we write these variables in terms of the non-leading variables (called \textbf{free variables}). \\

Each free variable corresponds to one ``dimension'' or ``degree of freedom'' in the solution set. For example, if there is one free variable then the solution set is a line, if there are two then it is a plane, and so on.

\horlines{1}
% Note that the previous example has a 2-dimensional solution set, which is a plane
\end{document}