TMV035 Analysis and Linear Algebra B, 2005

LECTURE 5.1

In this lecture we present the vector space R^{n}, Gauss elimination method. This covers AMBS Ch 42.3–6, 42.13.

1. The vector space R^{n}

Linear combination. R^{n} is the set of all column vectors of n elements, where each element is a real number:

x = [x_{1} ; x_{2} ; ⋮ ; x_{n}] , x_{1}, x_{2}, …, x_{n} ∈ R.

The algebraic operations addition and multiplication by a scalar are defined elementwise:

x + y = [x_{1} ; ⋮ ; x_{n}] + [y_{1} ; ⋮ ; y_{n}] = [x_{1} + y_{1} ; ⋮ ; x_{n} + y_{n}] , αx = α [x_{1} ; ⋮ ; x_{n}] = [αx_{1} ; ⋮ ; αx_{n}] , α ∈ R.

By combining these operations we can form linear combinations of column vectors:

αx + βy = [αx_{1} + βy_{1} ; ⋮ ; αx_{n} + βy_{n}] , α, β ∈ R.

This is an important way of creating new column vectors. Of course, we can form linear combinations of more than two column vectors:

α_{1}x_{1} + α_{2}x_{2} + ⋯ + α_{m}x_{m}.

The numbers α_{j} are called coefficients.

The zero column vector is

0 = [0 ⋮ 0] .

It satisfies

x + 0 = x.

It is easy to check that all the familiar rules of algebra apply: the commutative and associative laws of addition, and the distributive law.

Notice that if x, y belong to R^{n} then any linear combination of them, αx + βy, also belongs to R^{n}. A set with this property, that it preserves linear combinations, or linear combinations remain inside the set, is called a vector space or linear space (“vektorrum, linjärt rum”). Elements of such a set are called vectors. So R^{n} is a linear space and column vectors are a special kind of vectors.

The set of all row vectors of n real numbers:

x = [x_{1}, …, x_{n}]

is also denoted R^{n}, and it is also a linear space with addition and multiplication by a scalar defined elementwise. We usually work with column vectors.

We will meet other examples of vector spaces and vectors later, i.e., vectors which are not column or row vectors.

Date: November 20, 2005, Stig Larsson, Mathematical Sciences, Chalmers University of Technology.

Let a_{1}, …, a_{j} ∈ R^{n} be j vectors. The set of all linear combinations of the given vectors:

S(a_{1}, …, a_{j}) = {x = α_{1}a_{1} + ⋯ + α_{j}a_{j} : α_{1}, …, α_{j} ∈ R}

is called the space spanned by, or the space generated by, or simply the span of the given vectors. (“Rummet som genereras av de givna vektorerna.”) This is also a vector space.

Theorem. The set S(a_{1}, …, a_{j}) is a linear space.

Proof. We must show that all linear combinations of elements of S(a_{1}, …, a_{j}) remain inside S(a_{1}, …, a_{j}). Let

x = α_{1}a_{1} + ⋯ + α_{j}a_{j}, y = β_{1}a_{1} + ⋯ + β_{j}a_{j}

be two elements of S(a_{1}, …, a_{j}). Form a linear combination of them:

αx + βy = α(α_{1}a_{1} + ⋯ + α_{j}a_{j}) + β(β_{1}a_{1} + ⋯ + β_{j}a_{j})
= (αα_{1}a_{1} + ⋯ + αα_{j}a_{j}) + (β_{1}βa_{1} + ⋯ + β_{j}βa_{j})
= (αα_{1} + ββ_{1})a_{1} + ⋯ + (αα_{j} + ββ_{j})a_{j}.

We see that αx + βy is also a linear combination of a_{1}, …, a_{j}, in other words αx + βy belongs to S(a_{1}, …, a_{j}). □

Note in particular that the zero vector belongs to S(a_{1}, …, a_{j}). Proof: Take all coefficients α_{1} = ⋯ = α_{j} = 0. Then 0 = 0a_{1} + ⋯ + 0a_{j} ∈ S(a_{1}, …, a_{j}). Important: here the zero on the left-hand side is the zero vector, while the zeros on the right-hand side are the number zero:

[0 ⋮ 0] = 0 [a_{11} ; ⋮ ; a_{n1}] + ⋯ + 0 [a_{1j} ; ⋮ ; a_{nj}] .

Since the vector space S(a_{1}, …, a_{j}) is a subset of the vector space R^{n}, S(a_{1}, …, a_{j}) ⊂ R^{n}, we say that S(a_{1}, …, a_{j}) is a subspace of R^{n} (“underrum”). We will often work with this kind of supspace.

Note: in mathematics the word “space” means “a set with some extra structure”. So linear space (vector space) is a set where you can form linear combinations.

1.1. Scalar product. We define the scalar product or innner product of two column vectors (“skalärprodukt”):

(x, y) = ∑_{j=1}^{n} x_{j}y_{j}

The scalar product is also denoted by x · y. Note that it can also be computed as:

(x, y) = y^{T} x = [y_{1}, …, y_{n}] [x_{1} ; ⋮ ; x_{n}]

In Matlab:

>> y'*x

We also define the length or norm of a vector:

∥x∥ = \sqrt{(x, x)} = \sqrt{∑_{j=1}^{n} x_{j}^{2}}

In Matlab: norm(x). Note that this is not the same as abs(x), which is max |x_{j}|. The scalar product has the following properties.

Theorem. If x, y, z ∈ R^{n} and α ∈ R then

(1)  (x, x) \begin{cases}= 0, & if x = 0, \\ > 0, & if x ≠ 0, \end{cases}  \{positive definite\}
(2)  (x, y) = (y, x)  {symmetric}
(3)  (x + y, z) = (x, z) + (y, z)  {linear}
(4)  (αx, y) = α(x, y)  {linear}

Prove them by direct calculation! The next theorem gives a bound for the absolute value of the scalar product.

Theorem. (Cauchy’s inequality) If x, y ∈ R^{n} then

|(x, y)| ≤ ∥x∥∥y∥

Proof. If one of the x, y is the zero vector then both sides of the inequality are equal to zero (the number zero), so the inequality is true that case. We then assume that one of them is not the zero vector, for example, y ≠ 0. Then, for any α ∈ R, we calculate using the properties (2), (3), (4),

0 ≤ ∥x + αy∥^{2} = (x + αy, x + αy) = (x, x) + 2α(x, y) + α^{2}(y, y) = ∥x∥^{2} + 2α(x, y) + α^{2}∥y∥^{2}.

Since y ≠ 0 implies ∥y∥^{2} = (y, y) ≠ 0, see (1), we may choose

α = −\frac{(x, y)}{∥y∥^{2}}

to get

0 ≤ ∥x∥^{2} − 2\frac{(x, y)^{2}}{∥y∥^{2}} + \frac{(x, y)^{2}}{∥y∥^{4}} ∥y∥^{2} = ∥x∥^{2} − \frac{(x, y)^{2}}{∥y∥^{2}}

or

(x, y)^{2} ≤ ∥x∥^{2}∥y∥^{2}

This implies |(x, y)| ≤ ∥x∥∥y∥. □

The norm has the following properties.

Theorem.

∥x∥ \begin{cases}= 0, & if x = 0, \\ > 0, & if x ≠ 0, \end{cases} (5)

∥αx∥ = |α|∥x∥ (6)

(7) ∥x + y∥ ≤ ∥x∥ + ∥y∥ {triangle inequality}

Proof. The first statement (5) is the same as (1). To prove the other two we compute with the square of the norm:

∥αx∥^{2} = (αx, αx) = α^{2}(x, x) = α^{2}∥x∥^{2}

∥x + y∥^{2} = (x + y, x + y) = ∥x∥^{2} + 2(x, y) + ∥y∥^{2} ≤ ∥x∥^{2} + 2∥x∥∥y∥ + ∥y∥^{2} = (∥x∥ + ∥y∥)^{2}

In the last one we used Cauchy’s inequality. □

From Cauchy’s inequality it follows that

−1 ≤ \frac{(x, y)}{∥x∥∥y∥} ≤ 1

so we can define the angle θ between x and y by the equation:

cos(θ) = \frac{(x, y)}{∥x∥∥y∥}

The most important case is when θ = π/2. We say that the vectors x, y are orthogonal (“ortogonala, vinkelräta”) if

(x, y) = 0

2. The Gauss elimination method

We shall solve a linear system of m equations in n unknowns:

{ a_{11}x_{1} + ⋯ + a_{1n}x_{n} = b_{1} ; ⋮ ; a_{m1}x_{1} + ⋯ + a_{mn}x_{n} = b_{m}

We will use the Gauss elimination method, which is a systematic way of eliminating one variable after the other. We explain it by example.

Example.

\{ \begin{matrix}x_{1} & +2 & x_{2} & +3 & x_{3} & +4 & x_{4} & = & 1 \\ 4 & x_{1} & +3 & x_{2} & +2 & x_{3} & + & x_{4} & = & 1 \\ −10 & x_{1} & −5 & x_{2} & +5 & x_{4} & = & − 1 \end{matrix}

We begin by eliminating x_{1} from equations 2 and 3. This is achieved by multiplying equation 1 by −4 and adding it to equation 2. Similarly, we multiply equation 1 by 10 and add it to equation 3.

\{ \begin{matrix}x_{1} & +2 & x_{2} & +3 & x_{3} & +4 & x_{4} & = & 1 \\ 4 & x_{1} & +3 & x_{2} & +2 & x_{3} & + & x_{4} & = & 1 \\ −10 & x_{1} & −5 & x_{2} & +5 & x_{4} & = & − 1 \end{matrix} \begin{aligned}−4 & 10 \\ ↙ \\ & ↙ \end{aligned}

This results in

\{ \begin{matrix}x_{1} & +2 & x_{2} & +3 & x_{3} & +4 & x_{4} & = & 1 \\ −5x_{2} & −10 & x_{3} & −15 & x_{4} & = & − 3 \\ 15 & x_{2} & +30 & x_{3} & +45 & x_{4} & = & 9 \end{matrix} −\frac{1}{5}_{\frac{1}{15}}

Next we clean up by multiplying equation 2 by −\frac{1}{5} and equation 3 by \frac{1}{15}. This results in

\{ \begin{matrix}x_{1} & +2 & x_{2} & +3 & x_{3} & +4 & x_{4} & = & 1 \\ x_{2} & +2 & x_{3} & +3 & x_{4} & = & \frac{3}{5} \\ x_{2} & +2 & x_{3} & +3 & x_{4} & = & \frac{3}{5} \end{matrix}  −1 ; ↙

Finally, we eliminate x_{2} from equation 3 by multiplying equation 2 by −1 and adding it to equation 3:

\{ \begin{matrix}x_{1} & +2 & x_{2} & +3 & x_{3} & +4 & x_{4} & = & 1 \\ x_{2} & +2 & x_{3} & +3 & x_{4} & = & \frac{3}{5} \\ 0 & = & 0 \end{matrix}

We now have

\{ \begin{matrix}x_{1} & +2 & x_{2} & +3 & x_{3} & +4 & x_{4} & = & 1 \\ x_{2} & +2 & x_{3} & +3 & x_{4} & = & \frac{3}{5} \end{matrix}

The boxed terms in the equations are called pivots. This system has the same solutions as the original one. We can easily solve it as follows. The variable associated with pivots, here x_{1} and x_{2} are called bound variables (“bundna variabler”). The other variables, here x_{3}, x_{4} are called free variables. They can be chosen arbitrarily:

x_{3} = s, x_{4} = t

where s, t are arbitrary numbers. We then solve for x_{2} from equation 2:

x_{2} = \frac{3}{5} − 2x_{3} − 3x_{4} = \frac{3}{5} − 2s − 3t

and then x_{1} is given by equation 1:

x_{1} = 1 − 2x_{2} − 3x_{3} − 4x_{4} = −\frac{1}{5} + s + 2t

We conclude

x_{1} = s + 2t − \frac{1}{5}
x_{2} = −2s − 3t + \frac{3}{5}
x_{3} = s
x_{4} = t

where s, t are arbitrary numbers.

Example. The previous calculations are easier to do if we use matrix notation. The system of equations can be written:

[\begin{matrix}1 & 2 & 3 & 4 \\ 4 & 3 & 2 & 1 \\ −10 & −5 & 0 & 1 \end{matrix}] [\begin{matrix}x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \end{matrix}] = [\begin{matrix}1 \\ 1 \\ −1 \end{matrix}]

It is of the form

Ax = b, with A = [\begin{matrix}1 & 2 & 3 & 4 \\ 4 & 3 & 2 & 1 \\ −10 & −5 & 0 & 1 \end{matrix}] , x = [\begin{matrix}x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \end{matrix}] , b = [\begin{matrix}1 \\ 1 \\ −1 \end{matrix}]

The idea is that it is not necessary to keep writing the x’s when we perform the calculations. We form the extended matrix:

[A|b] = [ \begin{matrix}1 & 2 & 3 & 4 & | & 1 \\ 4 & 3 & 2 & 1 & | & 1 \\ −10 & −5 & 0 & 1 & | & −1 \end{matrix}] \begin{aligned}−4 & 10 \\ ↙ \\ & ↙ \end{aligned}

and perform the eliminations in the form of row operations on this matrix. The first step is to multiply row 1 by −4 and add it to row 2. Then we multiply row 1 by 10 and add it to row 3. The result is:

[ \begin{matrix}1 & 2 & 3 & 4 & | & 1 \\ 0 & −5 & −10 & −15 & | & −3 \\ 0 & 15 & 30 & 45 & | & 9 \end{matrix}] −\frac{1}{5}_{\frac{1}{15}}

We then multiply rows 2 and 3 by −\frac{1}{5} and \frac{1}{15}. The result is

[ \begin{matrix}1 & 2 & 3 & 4 & | & 1 \\ 0 & 1 & 2 & 3 & | & −\frac{3}{5} \\ 0 & 1 & 2 & 3 & | & −\frac{3}{5} \end{matrix}]

Next we multiply row 2 by −1 and add it to row 3:

[ \begin{matrix}1 & 2 & 3 & 4 & | & 1 \\ 0 & 1 & 2 & 3 & | & −\frac{3}{5} \\ 0 & 1 & 2 & 3 & | & −\frac{3}{5} \end{matrix}] −1 ; ↙

The result is

[Â|b̂] = [ \begin{matrix}1 & 2 & 3 & 4 & | & 1 \\ 0 & 1 & 2 & 3 & | & −\frac{3}{5} \\ 0 & 0 & 0 & 0 & | & 0 \end{matrix}]

We have now finished the elimination process. The matrix is an echelon matrix (“trappstegsmatris”). The boxed matrix elements are called pivot elements (“pivå-element”). The system Â = b̂ has the same solutions as the original system Ax = b. It is easily solved if we write it out:

\{ \begin{matrix}x_{1} & +2 & x_{2} & +3 & x_{3} & +4 & x_{4} & = & 1 \\ x_{2} & +2 & x_{3} & +3 & x_{4} & = & \frac{3}{5} \end{matrix}

and calculate as before. The result is

x = [\begin{matrix}s + 2t − \frac{1}{5} \\ −2s − 3t + \frac{3}{5} \\ s \\ t \end{matrix}] = s [\begin{matrix}1 \\ −2 \\ 1 \\ 0 \end{matrix}] + t [\begin{matrix}2 \\ −3 \\ 0 \\ 1 \end{matrix}] + [−\frac{1}{5} ; \frac{3}{5} ; 0 ; 0]

There are infinitely many solutions: for each s, t we get a solution. The solutions linear combinations of the three vectors:

v_{1} = [\begin{matrix}1 \\ −2 \\ 1 \\ 0 \end{matrix}] , v_{2} = [\begin{matrix}2 \\ −3 \\ 0 \\ 1 \end{matrix}] , v_{3} = [−\frac{1}{5} ; \frac{3}{5} ; 0 ; 0]

Note the structure of the echelon matrix: there are zeros below the pivot elements. In each step of the algorithm we use a pivot element in order to obtain zeros below it. Therefore the pivot elements must not be zero. It is always possible to make the pivots =1 as in the example, but this is not necessary. It is possible to make the elements above the pivots =0. We show this now:

[ \begin{matrix}1 & 2 & 3 & 4 & | & 1 \\ 0 & 1 & 2 & 3 & | & −\frac{3}{5} \\ 0 & 0 & 0 & 0 & | & 0 \end{matrix}] ↖ ; −2

The result is:

[ \begin{matrix}1 & 0 & −1 & −2 & | & −\frac{1}{5} \\ 0 & 1 & 2 & 3 & | & −\frac{3}{5} \\ 0 & 0 & 0 & 0 & | & 0 \end{matrix}]

An echelon matrix with zeros also above the pivots and with the pivots =1 is said to have row reduced echelon form (“radreducerad trappstegsform”).

In Matlab we have the function rref(). So the previous calculation can done as follows.

>> A=[1 2 3 4; 4 3 2 1; -10 -5 0 1]
>> b=[1; 1; -1]
>> AA = rref([A b])

Note the the extended matrix [A b].

Example. We solve Ax = c with the same matrix A and

c = [\begin{matrix}1 \\ 1 \\ 1 \end{matrix}]

If we apply Gaussian elimination (in Matlab: rref([A c])) we get the row reduced echelon matrix:

[Â|ĉ] = [ \begin{matrix}1 & 0 & −1 & −2 & | & 0 \\ 0 & 1 & 2 & 3 & | & 0 \\ 0 & 0 & 0 & 0 & | & 1 \end{matrix}]

and the system Âx = ĉ:

\{ \begin{matrix}x_{1} & − & x_{3} & −2 & x_{4} & = & 0 \\ x_{2} & +2 & x_{3} & +3 & x_{4} & = & 0 \\ 0 & = & 1 \end{matrix}

Clearly, this has no solution, and hence the original system has no solution either.

Example. We can solve the previous systems Ax = b and Ax = c at the same time if we form the extended matrix [A|b c] and use Gauss elimation (in Matlab: rref([A b c])) to get

[Â|b̂ ĉ] = [ \begin{matrix}1 & 0 & −1 & −2 & | & −\frac{1}{5} & 0 \\ 0 & 1 & 2 & 3 & | & \frac{3}{5} & 0 \\ 0 & 0 & 0 & 0 & | & 0 & 1 \end{matrix}]

Example.

A = [ \begin{matrix}2 & 2 & 4 & 4 \\ 6 & 6 & 4 & 4 \\ 1 & 2 & 0 & 1 \end{matrix}] \begin{aligned}−3 & −2 \\ ↙ \\ & ↙ \end{aligned}

Here we use the first pivot element 2 to get zeros below it:

[ \begin{matrix}2 & 2 & 4 & 4 \\ 0 & 0 & −8 & −8 \\ 0 & 1 & −2 & −1 \end{matrix}]

Now we must interchange the two last rows in order to get a non-zero pivot in the right place:

[ \begin{matrix}2 & 2 & 4 & 4 \\ 0 & 1 & −2 & −1 \\ 0 & 0 & −8 & −8 \end{matrix}]

This matrix is in echelon form with the pivots marked with boxes. If we want the row reduced echelon form we have to continue with a few more row operations. The result is

[ \begin{matrix}1 & 0 & 0 & −1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{matrix}]

Summary of Gauss elimination. In Gauss elimination we perform three kinds of row operations:

• interchange two rows;

• multiply a row by a number;

• add a multiple of one row to another row. By these operations we can obtain an echelon matrix. The corresponding system has the same solutions as the original system. The echelon system can be solved easily.

Problems

Problem 1. Let

x = [\begin{matrix}1 \\ 1 \\ 1 \\ 1 \end{matrix}] , y = [\begin{matrix}1 \\ 2 \\ 1 \\ 2 \end{matrix}]

(a) Compute ∥x∥, ∥y∥, (x, y). (b) Determine a number t so that z = x + ty is orthogonal to x.

Problem 2. Compute the angle between [\begin{matrix}−2 \\ 5 \\ 4 \\ 6 \end{matrix}] and [\begin{matrix}1 \\ 2 \\ −4 \\ 2 \end{matrix}] Problem 3. Prove Pythagoras’ theorem: if x, y are orthogonal then ∥x + y∥^{2} = ∥x∥^{2} + ∥y∥^{2}.

Problem 4. Solve the following systems of equations.

(a) \{ \begin{matrix}x_{1} − 8x_{2} = 3 \\ 2x_{1} + x_{2} = 1 \\ 4x_{1} + 7x_{2} = −4 \end{matrix} (b) \{ \begin{matrix}3x_{1} − 4x_{2} + 5x_{3} = 0 \\ 7x_{1} − 2x_{2} − x_{3} = 0 \\ 2x_{1} + x_{2} − 3x_{3} = 0 \end{matrix} (c) \{ \begin{matrix}2x_{1} + 3x_{2} − x_{3} − x_{4} = 0 \\ x_{1} − x_{2} − 2x_{3} − 4x_{4} = 0 \\ 3x_{1} + x_{2} + 3x_{3} − 2x_{4} = 0 \end{matrix}

(d) \{ \begin{matrix}x_{1} − 2x_{2} + 4x_{3} + x_{4} = 1 \\ 2x_{1} + x_{2} + 3x_{3} − 2x_{4} = 2 \\ x_{1} + 8x_{2} − 6x_{3} − 7x_{4} = 1 \end{matrix}

Answers

1.

(a) ∥x∥ = 2, ∥y∥ = \sqrt{10}, (x, y) = 6.

(b) t = −3

2. arccos(4/45) 4.

(a) no solution.

(b) x = t [\begin{matrix}5 \\ −3 \\ −2 \\ 3 \end{matrix}] (c) x = t [\begin{matrix}7 \\ 19 \\ 11 \end{matrix}] (d) x = s [\begin{matrix}−2 \\ 1 \\ 1 \\ 0 \end{matrix}] + t [\begin{matrix}3 \\ 4 \\ 0 \\ 5 \end{matrix}] + [\begin{matrix}1 \\ 0 \\ 0 \\ 0 \end{matrix}]

/stig