Let's make all this useful

Preface ….

Gauss elimination is for sure the most important method to solve linear systems of equations. During the last course module, and within your homework, you could see that such systems may have

A unique solution,
An infinite number of solutions, or
No solution at all

This leads automatically to the (by now familiar) question of existence and uniqueness of solutions.

We should take this question serious: Isn’t it annoying to waste valuable time to find a solution where there is none?

Or, risking to make yourself quite ridiculous by proudly announcing that you just found the solution of a problem – when there are many other and even better solutions?

A method, or an instrument that allows us to predict the outcome of our calculations would be of great help!

So, if we have a linear system of n equations, how can we predict if a solution exists and if it is unique?

During the following module we will introduce a concept that will allow us to do exactly this. It is called the "rank of a matrix":

Rank of a Matrix. Linear Independence. Vector Space

Before we continue let us introduce and define some new expressions…

Vectors - Dependence and Independence

We know already that a vector can be understood as a matrix consisting of either only one row or only one column, and with more than just one entry (that would be a "scalar" then! ). Let’s look at the following definition:

Definition: Given are n Vectors (of same length, else we cannot add them together at all! See at the very beginning of Linear Algebra!!)

is called a "linear combination"

(It is called "linear" since the terms of the sum contain only scalar multiples of the vectors)

If we have for example the vectors , then a combination such as

would be a thinkable linear combination of these vectors.

(What are they adding up to? , this means that the vector

is a linear combination of …..

Now let’s define "linear independence":

Again, we assume we have some n vectors, . We call these vectors linearly independent when absolutely no non-zero factors can be found that allow us to create a linear combination which adds up to 0:

With other words:

are linearly independent, if we can find only with all , , …, = 0 !

If we can find such factors, then our vectors are linearly dependent.

Example: Three vectors a, b, and c in the same plane:

Obviously there is no non-zero numbers, let’s call them d₁ and d₂ you can multiply a and b with so that , or, for c and b that .

However,

How do we have to understand this in terms of our new definitions? Nothing easier than this:

The vectors a and b are linearly independent
The vectors c and b are linearly independent, too
The vectors a and c are linearly dependent, and

a, b, and c are linearly dependent because a and c are linearly dependent

This usually takes a little while to sink in … you might want to return at the begin of the module here and read it again.

Now, if we have several vectors, let's say n vectors such as , we can create all kinds of "linear combinations" with them. Doing so, of course we will create new vectors. Actually, if we are considering all the possible combinations of our n vectors, we are creating an entire space, a so called "vector space".

The set of all possible linear combinations made out of is called the "span" of these vectors.

Definition: Given n vectors , V is the set of all combinations of these vectors

"span", V is a "vector space".

A Cartesian coordinate system for example is a very familiar "span" of three vectors,

. And for sure you know that with linear combinations of these three vectors you are able to get the coordinates of any point of a three-dimensional space.

Such as, for example, is nothing but the linear combination .

If we now have such a vector space V, the we are able to make certain statements for all the vectors that are contained in V:

V is vector space

Þ for all

for all

means practically that any linear combination of vectors from V again will be element of V - not surprising since this was the method by which we did create the vector space!

And the following rules look very familiar to us, too (remember, a vector is nothing but a special matrix):

and

Now, when we are talking about "space" we usually have dimensions in mind, like "width", height, depth, and eventually even time….

A " space" must have dimensions, therefore the question:

Q: What is the dimension of V?

A: Obviously the max number of linearly independent vectors in V.

Some of you might have thought spontaneously, the dimension of a vector space might be given by counting the number of entries in a vector. But this is wrong!

The dimension of a plane is only 2 although this plane has to be defined in all 3 dimensions of the physical space.

According to what we just said it takes only two linearly independent vectors (and their combinations) to define any point in this plane!

However, these two vectors most likely have more than two entries!

We define now the

Rank of a matrix as the number of linearly independent row vectors of a matrix.

If you did understand the principle of linear independence, this definition does say it all!

If not - well let's think about this: If we consider the rows of a matrix as vectors, some of these vectors (rows) eventually can be expressed by linear combinations of other ones. If this is the case we can also eliminate these rows by subtracting the particular linear combinations - as we did during Gauss elimination!! Let's look at an example:

Example:

has the row vectors (first row)

(second row)

(third row)

(first row)

(second row)

(third row)

We can combine:

( is linear combination of )

Þ rank

Therefore, according to our definition, the "rank" of the matrix is 2 although A was a 3x3 matrix! But it is not only the row vectors, which determine the rank of a matrix, it is the column vectors, too!

Theorem: The rank of a matrix A equals the maximum number of linearly independent column vectors.

Because transposition of a matrix practically means the exchange from column vectors to row vectors, this immediately has the consequence that

Consequently, a matrix has the same number of linear independent row vectors as it has linear independent column vectors.

Now, in case some row vectors are not linear independent, we already have a method to eliminate them: Gauss elimination!

How to determine the rank of a matrix?

Gauss elimination!

Example: Look at this 4x3 matrix. Let us try to make it upper triangular - this has the side effect that linear dependent row vectors will be eliminated: