Vector Spaces

Linear Equations

An expression of the form:

is called a linear combination. The ${a_i \in \reals}$ the combination's coefficients, and the ${x_i \in \reals}$ are the combinaton's variables. Append an equal assign at the end:

and we get a linear equation, where ${b}$ is a constant. For example, these equations are all linear equations:

Linear equations are the bedrock of modern technology. In the world of pure mathematics, we can simply write ${\nil}$ or ${\infty.}$ Computers, however, don't have the same luxury. We must model and approximate these abstractions to realize them physically. For example, the derivative ${\frac{df}{dx}(x)}$ of a differentiable function ${f: \reals \to \reals}$ can be viewed as a linear approximation of ${f.}$

The Solution Set

The set of all values that solve a linear equation is called the equation's solution set. For example, consider the linear equation:

This equation turns out to have infinitely many solutions. Some of these solutions are:

We can express the solution set for the equation above using parametric form:

Linear Systems

If we gather two or more linear equations and treat them as a single collection, we get a linear system (or system of linear equations):

If we can find a set of ${n}$ numbers (specifically, an ${n}$-tuple) that we can plug into each of the ${x_i,}$ such that all of the equations are solved simultaneously, then we call that set the system's solution. If the linear system has at least one solution, we can describe the system as consistent. If the system has no solutions, we describe it as inconsistent.

In the system above, the the subscript ${m}$ is a positive integer, and denotes the row index. The subscript ${n}$ is also a positive integer, and denotes the column index. Much like how rectangles are described with ${\text{length} \times \text{width},}$ linear systems have the property ${m \times n.}$ We call this the linear system's order.

Notice that the row index ${m}$ corresponds to the number of equations we have, and the the column index ${n}$ corresponds to the number of variables. This yields a few more properties about linear systems:

1. If ${m \ltn n,}$ there are more unknowns than equations. In this case, we say the ${m \times n}$ system underspecificed.

2. If ${m \gtn m,}$ there are more equations than unknowns, and we say the ${m \times n}$ system is overspecified.

Matrices

Consider the linear system:

Early on, mathematicians recognized that having to write linear systems over and over again is a pain. Accordingly, they invented a new construct called a matrix, of which there are two types: the coefficient matrix and the augmented matrix. With a coefficient matrix, we can express the system above as:

Each number in the matrix above corresponds to a coefficient in the linear system. There's also the augmented matrix:

This is simply the coefficient matrix, but with a column for the right-hand side of the equality, separated by a vertical bar. By using a matrix, we can give assign the linear system to a variable:

Now comes the cool part — we can then express the linear system as a linear equation:

Matrices also make solution sets easier to write. For example, the linear system:

has the matrix:

and the solution set:

Each "1-column matrix" in the solution set is called a column vector or simply vector. A matrix with a single row is called a row vector (may also be called a vector). Each number in a vector is called a vector component. There's a particularly special vector we'll see often later called the zero vector — a vector whose components are all zeroes:

How did we get that solution? Through a method called Gaussian elimination. Before we get to that topic, let's say a few words about variables. Like other areas of mathematics, linear algebra has certain naming conventions. Matrices are traditionally named with uppercase, bold, Roman letters: ${\bf \A}$, ${\bf \B}$, ${\bf \C}$, ${\bf \Z.}$ Vectors are usually lowercase Roman or Greek letters, either overlined with an or in bold: ${\bf \a}$, ${\bf \b}$, ${\vector{\alpha}}$, ${\vector{\beta}.}$

Gaussian Elimination

Gaussian elimination (also called Gauss's Method) is a method of solving linear systems:

Each of the three operations in Gauss's method is called an elementary row operation. Let's see what each operation does with the system:

Swapping. The first operation in Gauss's method is called swapping. Gauss's method tells us that these two systems have the same solution:

Scaling. The second operation is called swapping. Again, these two systems have the same solution:

Above, we multiplied the system to the right by the constant ${-3.}$

Pivoting. The third operation is called pivoting. This operation is a little more elaborate. Here, we first choose one of the system's equations (which one we choose is a question we'll discuss at length later). Using our example system, let's pick the second:

Then, we scale our equation of choice. Let's use 2 (why we choose 2 is another question we'll save for later).

Next, we choose a second equation (other than what we chose first) and perform the same. Since we only have two equations, we scale the first. Let's use the constant ${-1:}$

Then, we add the scaled equations:

Gauss's method tells us that, if we replace the equation we chose first with the new equation above, we get a linear system whose solution is the same as the original's:

Echelon Form

Suppose ${\L}$ is the linear system to the left, with its corresponding matrix to the right:

The first nonzero entry in each row of ${\L}$ is called the leading entry, and it corresponds to its ${\L}$ equation's leading variable. All the other nonzero entries are called free entries, and correspond their equations' free variables. Using this terminology, we state the formal definition of echelon form:

Let's break this definition down into a checklist. A matrix ${\bf M}$ is in echelon form if, and only if, it satisfies the following properties.

1. ${\bf M}$ is a rectangular matrix.
2. If ${\bf M}$ contains rows with all zeroes (called zero rows) and rows that are not all zeroes (called nonzero rows), then no zero row appears before a nonzero row, from top to bottom.
3. If a row ${R}$ contains a leading entry ${x,}$ then ${x}$ is in a column immediately to the right of the leading entry of the row above ${R.}$
4. If a row ${R}$ contains a leading entry ${x,}$ then for all the rows after ${R,}$ entries in ${x}$'s column are zeros.

If a matrix is in echelon form, we call the matrix an echelon matrix. The word "echelon" is descriptive — the matrix is "steplike." For example, the matrices below are all in echelon form. The symbol ${\square}$ indicates that the entry is a nonzero value, and the symbol ${\star}$ indicates that the entry is any value (zero or nonzero):

Notice how the zeroes form a step-like (echelon) arrangement. Once a matrix is in echelon form, we can apply back substitution solve the system. For example, consider the following linear system, already in echelon form:

The last row tells us that ${x_3 = 2,}$ since ${2x_3 = 4.}$ Plugging ${x_3 = 2}$ into the second row, we get ${3x_2 - 2 = 7,}$ which yields ${x_2 = 3.}$ And plugging ${x_2 = 3}$ and ${x_3 = 2}$ into the first row, we get ${x_1 = 1.}$

Reduced Echelon Form

From the definition of echelon form, we can state the formal definition of reduced echelon form.

Once again, let's break this definition down into a checklist. A matrix ${\bf M}$ is in reduced echelon form if, and only if, the following conditions are met:

1. ${\bf M}$ is in reduced echelon form,
2. If ${\bf M}$ is a nonzero row, then its leading entry is 1.
3. Each leading 1 in ${\bf M}$ is the only nonzero entry in its column.

For example, the following are all reduced echelon matrices:

Now that we've seen the echelon definitions, we state another motivation for Gaussian elimination: Any nonzero matrix can be row reduced — using Gaussian elimination — into some (more than one) echelon matrix. If we reduce a matrix to an echelon matrix, then finding the solution of a linear system becomes much easier because of several facts.

Given a reduced echelon matrix

the first nonzero entry in each row is called the pivot, and each column that contains a pivot is called the pivot column. Once we have pivots, we can apply the row reduction algorithm:

Vector Spaces

vector space. Let ${V}$ be a set of vectors, ${S}$ a set of scalars, ${+}$ the operation of addition, and ${\op}$ the operation of scalar multiplication. Then the algebra ${{\sf V} = \set{V \cup S, \set{+,\op}}}$ is a vector space if, and only if, for all ${\uu, \vv, \ww \in {V}}$ and for all scalars ${c,d \in {S},}$ the following properties hold:

${{\sf V}}$ is closed under vector addition.	${\uu + \vv \in {\sf V}.}$
Vector addition is commutative on ${{\sf V}.}$	${\uu + \vv = \vv + \uu.}$
Vector addition is associative on ${{\sf V}.}$	${(\uu + \vv) + \ww = \vv + (\uu + \ww).}$
For all ${\uu \in {V},}$ there exists an additive identity in ${{\sf V}.}$	${\uu + \mathbf{0} = \uu.}$
For all ${\uu \in {V},}$ there exists an additive inverse in ${{\sf V}.}$	${\uu + (-\uu) = \mathbf{0}.}$
${{\sf F}}$ is closed under scalar multiplication.	${c \op \uu \in {\sf F}.}$
Scalar multiplication is distributive over vector addition on ${{\sf V}.}$	${c \op (\uu + \vv) = (c \op \uu) + (c \op \vv).}$
	${\uu \op (c + d) = (c \op \uu) + (d \op \uu).}$
Scalar multiplication is associative on ${{\sf V}.}$	${c \op (d \op \uu) = (c \op d) \op u.}$
For all ${\uu \in {\sf V},}$ there exists a multiplicative identity in ${{\sf V}.}$	${1(\uu) = \uu.}$

A vector space, in short, is just a very special set. It's members may be lists, vectors, functions, or some other strange object. It's key requirement is that we can meaningfully perform vector addition and scalar multiplication. The properties laid out in the definition above establish what "meaningfully" means. Moreover, notice that we use different fonts to denote a vector space. We do so to emphasize the difference between a field and a vector space. All fields are vector spaces — ${\reals}$ is simply the vector space ${{\sf R}^1;}$ a vector space over itself. Not all vector spaces, however, are fields. To list just one reason, fields require commutativity of multiplication for all its carrier set's members. As we'll see later, that's a very special property, and it's not one that many vector spaces satisfy.

Linear Combinations

linear combination. A vector of the form ${a_1 v_1 + \ldots + a_m v_m}$ where ${a_1, \ldots, a_m \in {\sf F}}$ and ${v_1, \ldots, v_m \in {\sf V}}$ is called a linear combination (a list) of vectors in ${{\sf V}.}$

span. Let ${L}$ be a list of vectors ${v_1,\ldots,v_m,}$ where each vector is a vector in ${{\sf V}.}$ The set of all linear combinations of ${L}$ is called the span of ${L,}$ denoted ${\df{span}(v_1,\ldots,v_m).}$ The span of an empty list is defined to be ${0.}$