Lecture 1

A. Agarwal

December 7, 2012

System of Linear Equations

A system of linear equations is a set of equations, all of which are linear (powers of $x$ and $y$ are at most $1$ ).

\displaystyle\left\{\begin{aligned}\displaystyle 3x&\displaystyle=1\\ \displaystyle x+2y&\displaystyle=3\end{aligned}\right.

There are two ways of interpreting such as system:

1.

Geometric way
2.

Algebraic way

As an example, consider what does $x=1$ represent? Some may say a point, others may say a line.

It is important to consider the ambient space in which the equation(s) are to be considered.

Examples of the object $x=1$ in the ambient spaces $\mathds{R},\mathds{R}^{2},$ and $\mathds{R}^{3}$ .

Consider again the system

\displaystyle\left\{\begin{aligned}\displaystyle 3x&\displaystyle=1\\ \displaystyle x+2y&\displaystyle=3\end{aligned}\right.

(1)

Since there are two variables, we know that the system is in at least two dimensions (maybe more). For now, let us consider the system in two dimensions. What will be the solution?

The equation $3x=1$ represents a line, as does $x+2y=3$ . Figure [x] shows these lines:

Line $3x=1$

Line $x+2y=3$

Once we have this geometric picture of the system, a solution to the system will be a point common to both lines.

This is a geometric picture of the system. We still need some sort of algebraic way of finding the exact solution. In this case, the first equation gives us that $x=1/3$ , and the second equation gives us that

\displaystyle y=\frac{3-x}{2}=\frac{3-\frac{1}{3}}{2}=\frac{8}{6}=\frac{4}{3}

We now have the coordinates of the solution to the equations: $(1/3,4/3)$ . Formally, we can now claim that we have found the solution $(1/3,4/3)$ to the system (1) considered in $\mathds{R}^{2}$ .

In the above example, there is only one solution. We may ask ourselves, given any system, will there always be one solution, can there be more than one solution, or may there not be any solution? It turns out that examining these possibilities through a geometric perspective holds the answer and will allow us to generalize the answer to this question.

Two lines may either intersect at one point (Figure LABEL:fig:lineintersectionsa), yielding a unique solution; never intersect (Figure LABEL:fig:lineintersectionsb), which results in no solutions existing; or be on top of one another (Figure LABEL:fig:lineintersectionsc), which results in infinitely many solutions.

One unique solution.

No solution.

Infinitely many solutions.

The ways in which two lines may or may not intersect.

A natural question is whether it is possible for there to be finitely many solutions, and more than one solution? Geometrically, we can see that since two points define a line, two lines cannot intersect at more than one point without being the same line. The situation in $\mathds{R}^{2}$ seems to be then that we can have either one solution, no solutions, or infinitely many solutions.

It is natural to ask whether we can generalize this to higher dimensions. Let us consider $\mathds{R}^{3}$ .

\displaystyle\left.\begin{aligned}\displaystyle x-y+z&\displaystyle=1\\ \displaystyle 2x-3y+7z&\displaystyle=2\end{aligned}\right\}

In $\mathds{R}^{3}$ , these equations represent planes. If we are given two planes, they may intersect, and if they do, they must intersect in a line, similar to how pages in a book intersect at the spine of the book. In this case, there are infinitely many solutions. Alternatively the planes may not intersect at all, in which case there are no solutions. The planes may also be on top of one another; that is, they are the same plane, in which case there are also infinitely many solutions.

Figure 1: Parallel and intersecting planes.

Can it be that two planes may have a unique solution? It seems to be that the answer is no. But if we are given a third plane, we may have a unique solution. Consider for instance the corner of a room. Here the floor and two walls are meeting at a unique point.

\displaystyle\left.\begin{aligned}\displaystyle 3x-y+z&\displaystyle=7\\ \displaystyle x-y+z&\displaystyle=1\\ \displaystyle 2x-3y+7z&\displaystyle=2\end{aligned}\right\}\qquad\text{A % system consisting of three planes}

This tells us that in $\mathds{R}^{2}$ or $\mathds{R}^{3}$ , there seem to be always either one solution, no solutions, or infinitely many solutions. In fact, we will find that it is always that case that:

The number of solutions in $\mathds{R}^{n}$ of a system of linear equations will be only one of

1.

One solution
2.

Zero solutions
3.

Infinitely many solutions

Right now we cannot conclude this. Later we will, but that proof comes from understanding these systems in more algebraic terms.

Solve system of linear equations

Before we move on to solving systems of linear equations, it is important to note that the variables used in these equations are not the focus of the problem. Consider the following two systems:

\displaystyle\left.\begin{aligned}\displaystyle x-2y&\displaystyle=3\\ \displaystyle 2x+3y&\displaystyle=7\end{aligned}\right\}

\displaystyle\left.\begin{aligned}\displaystyle a-2b&\displaystyle=3\\ \displaystyle 2a+3b&\displaystyle=7\end{aligned}\right\}

The equations in the two systems are identical except for the variables, so in fact they represent the same system.

The important part of these systems are the coefficients of the variables. What we will do is put the coefficients in a matrix:

\displaystyle\left[\begin{matrix}1&-2&3\\ 2&3&7\end{matrix}\right]

In order to preserve the fact that the $3$ and $7$ are on the right-hand-side of the equations, we will put a vertical bar within the matrix:

\displaystyle\left[\begin{matrix}1&-2&3\\ 2&3&7\end{matrix}\right]

This is referred to as an augmented matrix.

\displaystyle\left[\begin{matrix}A&\vec{b}\end{matrix}\right]

\displaystyle=\left[\begin{matrix}1&-2&3\\ 2&3&7\end{matrix}\right]

In general, we say the left part $A$ of the augmented matrix is the coefficient matrix, and the right part $\vec{b}$ is the right-hand-side vector, or the constant vector.

Every system of linear equations can be translated into an augmented matrix, and every augmented matrix can be translated back into a system of linear equations.

This notation saves time and we will be using it a lot.

Row Picture

\displaystyle\left.\begin{aligned}\displaystyle x-2y&\displaystyle=3\\ \displaystyle 2x+3y&\displaystyle=7\end{aligned}\right\}\begin{aligned}% \displaystyle\longleftarrow\\ \displaystyle\longleftarrow\end{aligned}\quad\text{Rows}

Row Picture: Intersection of two lines

Column Picture

\displaystyle x\begin{bmatrix}1\\ 2\end{bmatrix}+y\begin{bmatrix}-2\\ 3\end{bmatrix}=x\begin{bmatrix}3\\ 7\end{bmatrix}

Column Picture: Can $\begin{bmatrix}3\\ 7\end{bmatrix}$ be written as a linear combination of $\begin{bmatrix}1\\ 2\end{bmatrix}$ and $\begin{bmatrix}-2\\ 3\end{bmatrix}$ ?

The advantages of the column picture may not be apparent now, but looking at things in the language in linear combinations will be very useful later.

It is important to note that in the above case, the row and column picture are in the same number of dimensions. Consider instead

\displaystyle\left.\begin{aligned}\displaystyle x-y+z&\displaystyle=21\\ \displaystyle 3x+y-3z&\displaystyle=0\end{aligned}\right\}

\displaystyle\begin{aligned}\displaystyle x\begin{bmatrix}1\\ 3\end{bmatrix}+y\begin{bmatrix}-1\\ 1\end{bmatrix}+z\begin{bmatrix}1\\ -3\end{bmatrix}&\displaystyle=\begin{bmatrix}21\\ 0\end{bmatrix}\end{aligned}

Here the row picture is the intersection of two planes in $\mathds{R}^{3}$ . The column picture is a linear combination of vectors in $\mathds{R}^{2}$ .

These perspectives will be useful, and in particular pay attention to the idea of linear combinations.

Solving a system

Consider the system in $\mathds{R}^{2}$ ,

\displaystyle\left.\begin{aligned}\displaystyle x&\displaystyle=1\\ \displaystyle y&\displaystyle=3\end{aligned}\right\}\qquad\longrightarrow% \qquad\left.\begin{matrix}x&+&0y&=1\\ 0x&+&y&=3\end{matrix}\right\}

We can easily convert the system to and from an augmented matrix:

\displaystyle\left[\begin{matrix}1&0&1\\ 0&1&3\end{matrix}\right]

This is in a sense our ‘Dream augmented matrix’, in that from it we can directly determine the solution to the system. The technical term for this sort of matrix is a row-reduced echelon form matrix.

In some sense then, the row-reduced echelon form matrix is our goal when solving systems of linear equations. The question is, how will we go from a general matrix to a row-reduced echelon form matrix? To do so, we will learn row operations