This site is devoted to mathematics and its applications. Created and run by Peter Saveliev.

# Linear algebra

## Contents

## Linear subspaces of **R**^{3}

Any subset $U$ of ${\bf R}^3$ that is closed with respect to the operations of ${\bf R}^3$ is called *linear subspace* or simply *subspace*.

**Example.** Suppose u = (0,1,1). Is there a y such that y ∈ S\S_{1}, where S = Span{u}?

Yes, for example v = (1,1,2).

Next compute

S_{2}= Span(u, v) = {αu + βv: α, β ∈R} = {α(0,1,1) + β(1,1,2): α, β ∈R} = {(β,α+β,α+2β): α, β ∈R}

The result is the "parametric solution" of the system. It is plane in the 3-space.

**Theorem 1.4.3** The solution set of a homogeneous linear equation

a_{1}x_{1}+a_{2}x_{2}+a_{3}x_{3}= 0,

with at least one of *a*_{1}, *a*_{2}, *a*_{3} not equal to 0, is a plane passing through the origin.

If *a*_{1} = *a*_{2} = *a*_{3} = 0, the the equation turn into 0 = 0, and the solution set is **R ^{3}**.

**Example.** Given:

u = (1,1,0), v = (1,0,1), w = (3,1,2).

Do they all lie in a 2-dimensional subspace?

Find if w ∈ Span{u, v}? In other words.

w = αu + βv.

Find α, β.

Rewrite the equation:

(3,1,2) = α(1,1,0) + β(1,0,1) (3,1,2) = (α+β, α, β)

Examining each coordinate of this vector equation produces three equations for these numbers:

3 = α + β ______ (1) 1 = α + 0 ______ (2) 2 = 0 + β ______ (3)

Solve it.

There are 2 unknowns but 3 equations. So the solution of any two equations must satisfy the third. From (2) and (3) we have α = 1 and β = 2 which when substituted in (1), we see that (1) is satisfied.

Hence, the solution is w = u + 2v. In other words, u = w - 2v and v = (w - u)/2. The solution set is the plane is x + 2y - z = 0.

**Example.** Given

x_{1}= (1,2,3) x_{2}= (1,2,-3) [it follows that x_{2}∉ Span{x_{1}}] x_{3}= (1,4,0).

Find Span{x_{1}, x_{2}, x_{3}}.

Denote

| 1 2 3| | 1 2 -3| = [A], say. | 1 4 0|

Then

det(A) = 0 - 6 + 12 - 6 + 12 - 0 = 12

Since the determinant is non-zero so the vectors are linearly independent, hence

Span{x_{1}, x_{2}, x_{3}} =R^{3}.

**Example.** Represent the solutions of the (system) equation:

x_{3}= 0

as linear combinations of two fixed vectors.

Consider the solution set of an equation:

S = {x_{3}= 0} = {(*, *, 0)} = {(α, β, 0): α, β ∈R} = {α(1,0,0), β(0,1,0): α, β ∈R}.

Moreover,

(1,0,0) = e_{1}, (0,1,0) = e_{2}form a basis of S.

**Example.** Same problem for:

x_{1}- x_{2}+ x_{3}= 0

Let's guess first:

u = (1, 1, 0), v = (0, 1, 1).

Check

u = λv? (1, 1, 0) = λ(0, 1, 1) (1, 1, 0) = (0, λ, λ)

Clearly there is no solution for non-zero λ.

Without a guess:

x_{1}= 0 implies -x_{2}+ x_{3}= 0, so x_{2}= x_{3}

Pick

x_{3}= 1 then u = (0, 1, 1).

## Single linear equation

Let's start with these examples:

Homogeneous equation: x_{1}+ x_{2}- x_{3}= 0 Non-homogeneous equation: x_{1}+ x_{2}- x_{3}= 1 [The right hand side is any non-zero number]

The solution set S of the second equation is not a subspace.

Indeed, let us assume that the set S be a linear subspace. Let

x = (1,0,0) and y = (3,0,2) be two vectors in S.

For S to be a linear subspace the linear combination of u and v must also be vector in S. Let

z = x + y = (1+3, 0+0, 0+2) = (4,0,2).

Now, take the coordinates of w and substitute them into the equation:

z_{1}+ z_{2}- z_{3}= 4 + 0 - 2 = 2 ≠ 1.

Therefore w ∉ S and so

S is not a linear subspace.

But what about

z = x - y? z = (1-3, 0-0, 0-2) = (-2, 0, -2).

So, z_{1} + z_{2} - z_{3} = -2 + 0 + 2 = 0 ≠ 1. So, in this case too z ∉ S.

But, z = x - y satisfies the homogeneous equation!

This is also true in general case:

if x, y ∈ S = {x_{1}+ x_{2}- x_{3}= 1} then x - y ∈ S' = {x_{1}+ x_{2}- x_{3}= 0}.

Indeed, let x and y be

x = (x_{1}, x_{2}, x_{3}) ∈ S and y = (y_{1}, y_{2}, y_{3}) ∈ S.

Then,

z = x - y = (x_{1}-y_{1}, x_{2}-y_{2}, x_{3}-y_{3}) ∈ S

Now, since u,v ∈ S so

x_{1}+ x_{2}- x_{3}= 0 y_{1}+ y_{2}- y_{3}= 0 _____________________________ (x_{1}-y_{1}) + (x_{2}- y_{2}) - (x_{3}- y_{3}) = 0

Therefore, z ∈ S'.

The S and S' are two parallel planes:

S: x_{1}+ x_{2}- x_{3}= 1, S': x_{1}+ x_{2}- x_{3}= 0.

This means that S' is obtained from S by a shift. Find it.

**Theorem.** Given a non-homogeneous linear equation, its solution set has the form

S = S_{1}+ z,

where S_{1} is the solution set to the corresponding homogeneous equation (subspace) and z is a vector.

**Example.** Consider an equation (solution set S is a plane):

2x_{1}- x_{2}+ 3x_{3}= 5.

Rewrite:

2x_{1}= x_{2}- 3x_{3}+ 5, x_{1}= (1/2)x_{2}- (3/2)x_{3}+ (5/2).

Let x_{2} = α and x_{3} = β be the parameters. Then,

x_{1}= (1/2)α - (3/2)β + (5/2).

A solution is x = (x_{1}, x_{2}, x_{3}) ∈ **R ^{3}**, so

x = ((1/2)α - (3/2)β + (5/2), α, β) where α, β ∈R

S is the set of all such x's. Thus,

x = αx_{1}+ βx_{2}+ z

Here:

z = (0, 0, 5/2), x_{1}= (1, 0, 1/2), x_{2}= (0, 1, -3/2).

This is the answer.

## Two linear equations

Consider a system of two equations:

S_{1}: x_{1}+ x_{2}- x_{3}= 0 S_{2}: x_{1}+ 2x_{2}+ x_{3}= 0

Here the solution to each equation is a subspace. Then, the solution set of the intersection of these two subspaces is their intersection:

S = S_{1}∩ S_{2}.

S may be a line...

Adding the two equations:

2x_{1}+ 3x_{2}= 0, x_{1}= -(3/2)x_{2}.

Substituting in the equation for S_{1}:

-(3/2)x_{2}+ x_{2}- x_{3}= 0 -(1/2)x_{2}- x_{3}= 0 x_{3}= -(1/2)x_{2}

Choose a parameter

x_{2}= α.

Then, the solution set S is given by:

x_{1}= -(3/2)α x_{2}= α x_{3}= -(1/2)α

This solution

S = (-(3/2)α, α, -(1/2)α) represents a straight line inR.^{3}

Also,

S = {αx: α ∈R}, where x = (-3/2, 1, -1/2)

Now what if these equations had a non-zero entries in the right hand sides ("free terms")?

We rewrite the work above and change just a few things:

S*_{1}: x_{1}+ x_{2}- x_{3}= 1, S*_{2}: x_{1}+ 2x_{2}+ x_{3}= 2.

The solution set S is the intersection of these two subspaces:

S* = S*_{1}∩ S*_{2}.

Adding the two equations:

2x_{1}+ 3x_{2}= 3, x_{1}= -(3/2)x_{2}+ (3/2)

Substituting in the equation for S*_{1}:

-(3/2)x_{2}+ (3/2) + x_{2}- x_{3}= 1, -(1/2)x_{2}- x_{3}= -(1/2), x_{3}= -(1/2)x_{2}+ (1/2).

Suppose, x_{2} = α. Then, the solution set is

x_{1}= -(3/2)α + (3/2) x_{2}= α x_{3}= -(1/2)α + (1/2)

In other words,

S* = (-(3/2)α + (3/2), α, -(1/2)α + (1/2)) represents a straight line inR.^{3}

Also,

S* = {αx: α ∈R} + z where x = (-3/2, 1, -1/2) and z = (3/2, 0, 1/2)

Hence, S* = S + z.

Example of two equations but solution set is a plane:

x_{1}+ x_{2}+ x_{3}= 0 2x_{1}+ 2x_{2}+ 2x_{3}= 0.

In this case the second equation is redundant (it's an identical plane).

## Three linear equations

Solution for 3 equations can be

1) Point - when the equations represent planes with no parallel ones; 2) Plane - when the equations represent identical planes; 3) Line - when the equations represent planes that intersect through it; 4)R- when for example the equations are 0 = 0.^{3}

**Example.** Find the solution set of the system:

x_{1}- x_{3}= 3 _____ (1) x_{2}+ 3x_{3}= 5 ______ (2) 2x_{1}- x_{2}- 5x_{3}= 1 ______ (3)

Substituting x_{1} from (1) into (3):

2(x_{3}+ 3) - x_{2}- 5x_{3}= 1 x_{3}- 3x_{2}= -5 _____ (4)

Comparing (4) with (2) it is evident that (4) is a multiple of (2). Comparing (1) with (2) it is evident that (2) is *not* a multiple of (1). Then, the solution set is a line.

Specifically, we have 1 parameter, say, α = x_{3}. Then the solution set is:

1) x_{1}= α + 3 2) x_{2}= -3α + 5 3) x_{3}= α

In other words,

x = (x_{1}, x_{2}, x_{3}) = (α + 3, -3α + 5, α).

Next

S = span{x} + z,

find x and z:

x = (1, -3, 1) and z = (3, 5, 0).

**Example.** Find α_{1}, α_{2}, α_{3} so that

{Solution of α_{1}x_{1}+ α_{2}x_{2}+ α_{3}x_{3}= 0} = Span{x_{1}, x_{2}}, where x_{1}= (1, -1, 1) and x_{2}= (2, 1, 1).

Rewrite:

Span{x_{1}, x_{2}} = {αx_{1}+ βx_{2}: α, β ∈R} = {(α + 2β, -α + β, α + β: α, β ∈R}

Solution:

x_{1}= α + 2β x_{2}= -α + β x_{3}= α + β

Substitute:

α_{1}(α + 2β) + α_{2}(-α + β) + α_{3}(α + β) = 0 α(α_{1}- α_{2}+ α_{3}) + β(2α_{1}+ α_{2}+ α_{3}) = 0

Since α and β are arbitrary, we have

(α_{1}- α_{2}+ α_{3}) = 0 (2α_{1}+ α_{2}+ α_{3}) = 0

Exercise: solve this system.

**Review example.** Given: u = (1,1,0), v = (0,1,1). Is vector (0,1,-1) a linear combination of u and v? In other words, find α and β such that

(0,1,-1) = αx_{1}+ βx_{2}

Rewrite:

(0,1,-1) = α(1,1,0) + β(0,1,1) = (α, α + β, β) 0 = α, 1 = α + β, -1 = β

This is clearly a contradiction.

More generally,

**Theorem.** A system of *m* homogeneous equations with *n* unknowns has infinitely many solutions when *n > m*.

Geometrically,

n= dimension of the space andm= no. of linear subspaces S_{1}, S_{2}, .... S_{m}corresponding to each equation.

The solution set of the system is the intersection of S_{1}, S_{2}, .... S_{m}:

S = S_{1}∩ S_{2}∩ .... ∩ S_{m}

Then S a linear subspace of **R**^{n}.

Observe that 0∈S. Now, if S ≠ 0, then there is x∈S \ {0}. Then there are more solutions:

span{x} ⊂ S.

**Examples.** (1) Solve the system:

x_{1}= 0, x_{3}= 0

Then

S = {(0, α, 0): α ∈R} = line = span{(0, 1, 0)}.

(2) Solve the system:

x_{1}- x_{3}= 0 x_{1}+ x_{3}= 0 ____________ 2x_{1}= 0 x_{1}= 0

Substituting for x_{1} we get x_{3} = 0. The answer is the same as above.

(3) Solve the system:

x_{1}- x_{2}= 0 -x_{1}+ x_{2}= 0.

Then

x_{1}= x_{2}

Find

S = Span{v_{1}, v_{2}}.

Let x_{2} be a parameter α and x_{3} be a parameter β. Then

S = {(α, α, β): α, β ∈R} = {αv_{1}+ βv_{2}: α, β ∈R} = {α(1,1,0) + β(0,0,1): α, β ∈R} S = Span{(1,1,0), (0,0,1)}

Next,

line = intersection of planes P_{1}(equation 1) and P_{2}(equation 2).

**Examples.** Consider these systems:

(1)

x_{1}+ x_{2}+ x_{3}= 1 x_{1}+ x_{2}+ x_{3}= 2

(2)

x_{1}+ x_{2}+ x_{3}= 1 (same equation) 2x_{1}+ 2x_{2}+ x_{3}= 1

Subtracting:

-x_{1}+ x_{2}= 0,

so there are infinitely many solutions.

(3)

x_{1}+ x_{2}= 1 x_{1}+ x_{2}= 1 x_{1}+ x_{2}= 1

So there are infinitely many solutions.

(4)

0∙x_{1}+ 0∙x_{2}+ 0∙x_{3}= 1, then 0 = 1.

So there is no solution.

## Affine subspaces

An *affine subspace* A is a subset given by

A = x + S,

where S is a linear subspace and x is a vector.

Here is what we mean here:

A = x + S = {x + s: s ∈ S} set = vector + set.

Of course, this representation doesn't have to be unique:

A = x_{1}+ S = x_{2}+ S = x_{3}+ S.

What do we know about x?

First,

O ∈S, so 0 + x ∈ A, or x ∈ A.

On the other hand,

if x' ∈ A then x' + S = A.

Suppose, A = x + S = y + T (equal as sets), where S, T are linear subspaces. Then, S = T and y ∈ A.

The converse is also true i.e.

if S = T and y ∈ A then A = y + T = x + S.

Affine subspaces are solution sets of systems of non-homogeneous equations.

**Example.** System of non-homogeneous equations:

x_{1}+ x_{2}+ x_{3}= 1 ________ (1) x_{1}- x_{3}= 2 ________ (2)

Transforming into the corresponding system of homogeneous equations:

x_{1}+ x_{2}+ x_{3}= 0 x_{1}- x_{3}= 0

The solution set to the latter is a linear subspace, say, S and the solution to the former is, say, A. Then

A = S + x.

What is x?

First, x is a solution to the non-homogeneous system:

x∈A.

Suppose we have S, find A. Turns out, all we need is x, i.e., any single solution to the non-homogeneous system.

If x = (3, -3, 1) then A = (3, -3, 1) + S. If x = (2, -1, 0) then A = (2, -1, 0) + S.

The values of x is such that substitution into equation (1) and (2) satisfies both.

**Theorem.** The solution set A of a non-homogeneous system of equations is the sum of the solution set S of the corresponding homogeneous system of equations and any solution x of the non-homogeneous system:

A = x + S.

*Case 1.* Let us consider the case with 2 equations and 3 variables. The solution set corresponds to the intersection of 2 planes in **R**^{3}. This is typically a line and atypically either no intersection (parallel planes) or coincident planes.

*Case 2.* Let us consider the case with 3 equations and 3 variables. The solution set corresponds to the intersection of 3 planes in **R**^{3}. This is typically a point and atypically either no intersection (parallel planes) or a line.

We know that a plane is determined by three points. Or we can use vectors instead:

P = x + S, where S = Span(v_{1}, v_{2}).

To find these vectors:

x = OA, v_{1}= AB, v_{2}= AC.

**Review example.** Find a_{1}, a_{2}, a_{3} so that

{Solution of a_{1}x_{1}+ a_{2}x_{2}+ a_{3}x_{3}} = 0} = Span{x_{1}, x_{2}}, where x_{1}= (1, -1, 1) and x_{2}= (2, 1, 1).

Substituting x_{1} and x_{2}, separately, in the given equation we have

a_{1}×1 + a_{2}×(-1) + a_{3}×1 = 0 _____ (1) a_{1}×2 + a_{2}×1 + a_{3}×1 = 0 _____ (2)

Let' solve the system. Rearranging the equations (1) and (2),

a_{1}- a_{2}+ a_{3}= 0 ______ (3) 2a_{1}+ a_{2}+ a_{3}= 0 ______ (4)

We have a system of 2 equations and 3 unknowns so we need 1 more equation to make the answer unique. Taking

a_{2}= 1,

we can rewrite equations (3) and (4) as

a_{1}+ a_{3}= 1 _____ (5) 2a_{1}+ a_{3}= -1 _____ (6)

Solving (5) and (6), we have

a_{1}= -2, a_{3}= 3.

To verify, back substituting a_{1}, a_{2} and a_{3} into the original equation (3) we have

a_{1}- a_{2}+ a_{3}= 0 -2 - 1 + 3 = 0

Therefore, the answer is (-2, 1, 3).

**Review example.** If

S_{1}= Span{x_{1}, x_{2}} and S_{2}= Span{y_{1}, y_{2}}.

Find z such that P = S_{1} ∩ S_{2}. To rephrase,

S_{1}∩ S_{2}= Span{z}, so z ∈ S_{1}∩ S_{2}, or z ∈ S_{1}and z ∈ S_{2}.

Rewriting the last part:

(z = ) αx_{1}+ βx_{2}= γy_{1}+ δy_{2}.

Find α, β (γ, δ).

## Dimension of vector space

Consider a system of two equations:

x_{1}+ x_{2}- x_{3}= 0 2x_{1}+ 2x_{2}- 2x_{3}= 0

Then

S = Span{u_{1}, u_{2}} = Span{v_{1}, v_{2}}.

It follows:

v_{1}is redundant because v_{1}∈ Span{u_{1}, u_{2}}, v_{2}is redundant because v_{2}∈ Span{u_{1}, u_{2}}.

or

v_{1}is a linear combination of u_{1}and u_{2}, v_{2}is a linear combination of u_{1}and u_{2}.

If S = Span{u, v, w}, is there *redundancy*? In other words can be drop on of them from the list and S remains the same? Yes,

if u = αv + βw (u, v, w ≠ 0).

Rewrite:

αv + βw - u = 0.

Then 0 is a linear combination of v, u, w. We say that they are "linearly dependent".

**Definition.** Vectors x_{1},...., x_{s} are said to be *linearly dependent* if there exists a linear combination, with not all zero coefficients, of them equal to zero. Otherwise, they are said to be *linearly independent*.

**Example.** s = 2. Two vectors x_{1} and x_{2} are linearly dependent when

αx_{1}+ βx_{2}= 0, (α, β ≠ 0)

Solving for x_{1},

x_{1}= -(β/α)x_{2}.

Therefore, x_{1} is a multiple of x_{2} and vice versa.

**Example.** s = 3. Three vectors u, v, w are linearly dependent:

αu + βv + γw = 0,

then we can solve for u:

u = -(βv + γw)/α = -(β/α)v - (γ/α)w

Therefore, u is a linear combination of v and w.

**Example.** Are the vectors u = (1,1,0), v = (0,1,1), w = (1,1,1) linearly independent? To answer the question, we need to find α, β, γ such that

αu + βv + γw = 0.

Rewrite:

α(1,1,0) + β(0,1,1) + γ(1,1,1) = 0

Thus we have 3 equations, for each of the coordinates:

α + γ = 0 α + β + γ = 0 β + γ = 0

We can solve the system, but we only case about this question: is there a non-zero solution. Answer: NO (verify). Hence, u, v and w are linearly independent.

*Illustration here*

Suppose S = Span{u, v, w}. If you can remove the vectors one at a time. Check if it is possible to write

Span{u, v, w} = Span{u, v} = Span{u, w} = Span{u}, etc.

If it is impossible then dim S = 3.

**Example.** Represent

R^{3}= Span{u,v,w} such that u, v, w are linearly independent.

The "standard unit vectors" are:

u = (1, 0, 0), v = (0, 1, 0), w = (0, 0, 1).

We need to prove two things:

1.R= Span{u,v,w}^{3}

Indeed, any vector is representable in terms of these three:

(a, b, c) = au + bv + cw.

Also

2. u, v, w are linearly independent.

Indeed, if

αu + βv + γw = 0

then

α(1,0,0) + β(0,1,0) + γ(0,0,1) = 0

hence

α = β = γ = 0.

**Definition.** Given a vector space (or a linear subspace) S, then vectors v_{1}, v_{2}, ...., v_{n} are called a basis of S if

1) S = Span{v_{1}, v_{2}, ...., v_{n}}, and 2) v_{1}, v_{2}, ...., v_{n}are linearly independent.

We also say that the dimension of S is n (the "the" part needs to be proven.).

**Example.** If S is a linear subspace with one basis {v_{1}, v_{2}}, then show that dim S = 2. Let us suppose there exists another basis {u_{1},... u_{n}} with say n = 3. In particular, it means that

Span{u_{1}, u_{2}, u_{3}} = S.

We need to show that u_{1}, u_{2}, u_{3} are linearly dependent. Since {v_{1}, v_{2}} is a basis, we can write

u_{1}= αv_{1}+ βv_{2}u_{2}= γv_{1}+ δv_{2}u_{3}= λv_{1}+ θv_{2}

Next, we check linear independence u_{1}, u_{2}, u_{3} by investigating existence of scalars a, b, c such that

au_{1}+ bu_{2}+ cu_{3}= 0.

Rewrite:

a(αv_{1}+ βv_{2}) + b(γv_{1}+ δv_{2}) + c(λv_{1}+ θv_{2}) = 0 v_{1}(aα + bγ + cλ) + v_{2}(aβ + bδ + cθ) = 0

But, v_{1} and v_{2} are linearly independent. So,

aα + bγ + cλ = 0 and aβ + bδ + cθ = 0.

Solve this system.

This is a homogeneous system of equations in a, b, c and there is always a solution (0, 0, 0). If this system has a non-zero solutions for a, b, c, then u_{1}, u_{2}, u_{3} are linearly dependent.

The definition implies the following.

**Theorem.** If dimS = n, then any collection of linearly independent vectors has at most n elements.

If a subspace S has a basis {v_{1}, v_{2},.... v_{n}} and also another basis {u_{1}, u_{2},..... u_{m}}, then, by the theorem, m ≤ n but also m = n or m ≥ n. Hence m = n.

**Theorem.** All bases of S must have same number of elements.

This implies that dimension of S is well defined.

Suppose, B = {u_{1}, u_{2},.... u_{n}}is a basis of S .
Further suppose,

x = a_{1}u_{1}+ a_{2}u_{2}+ .... + a_{n}u_{n}______ (1) and also x = b_{1}u_{1}+ b_{2}u_{2}+ .... + b_{n}u_{n}______ (2).

Subtracting both sides of equation (2) from both sides of equation (1), we obtain

(a_{1}- b_{1})u_{1}+ (a_{2}- b_{2})u_{2}+ .... + (a_{n}- b_{n})u_{n}= 0

Since, B = {u_{1}, u_{2},.... u_{n}} is a basis of S so its elements, i.e. u_{1}, u_{2},.... u_{n} must be linearly independent. Therefore,

a_{1}- b_{1}= 0, a_{2}- b_{2}= 0, ...., a_{n}- b_{n}= 0, i.e. a_{1}= b_{1}, a_{2}= b_{2}, ...., a_{n}= b_{n}.

Hence,

**Theorem.** If B is a basis of S then every element of S is represented by a unique linear combination of the elements of B.

For this uniqueness, it makes sense to call a_{1}, a_{2}, ...., a_{n} *the coordinates of x with respect to* B:

x = (a_{1}, a_{2}, ...., a_{n})

**Definition.** If A is an affine subspace then its *dimension* is defined as

dim A = dim S,

when A = z + S and S is a linear subspace.

Recall, if A = z + S = u + T, then S = T. So *the* dimension of A is well defined.

**Theorem.** Suppose, S' is a proper subspace of S. Then, dim S' < dim S.

Indeed, suppose S ≠ S'. Then there is x∈S\S'. Then let

T = Span(S' ∪ {x}).

Therefore according to the theorem, dim S' < dim T (since x ≠ 0).

This idea helps us with the next topic.

## Building a basis

How do we build a basis for a subspace S of **R'**^{n}? This is the procedure:

Pick x_{1}∈S\{0}; Pick x_{2}∈ S \ Span{x_{1}} => dim span{x_{1}, x_{2}} = 2; .. continue (induction) .. Pick x_{k}∈ S \ Span{x_{1}, x_{2},... x_{k-1}} => dim {x_{1}, x_{2},... x_{k}} = k; .. continue .. Pick x_{n}∈ S \ Span{x_{1}, x_{2},... x_{n-1}} => dim {x_{1}, x_{2},... x_{n}} = n. Stop

This happens when we can't pick

x_{n+1}∈ S \ Span{x_{1}, x_{2}, ..... x_{n}}

which is empty.

**Definition.** If S' is an affine subspace of S and dim S' = dim S - 1 then S' is called a *hyperplane* in S.

In **R**^{3}, any plane is a hyperplane.

**Theorem.** S is a hyperplane in **R ^{3}** iff S is the solution of a linear equation

a_{1}x_{1}+ a_{2}x_{2}+ ..... + a_{n}x_{n}= b.

where not all of a_{1}, a_{2},.... a_{n} are zero.

**Review example.** Suppose

S = {(x_{1}, x_{2}, x_{3}): x_{2}= 0}.

Find an equation that represents S. Simple:

S = {(x_{1}, 0, x_{3})}

Now, find an affine subspace A parallel to S and passing through z = (-3, 7, 4). Recall,

A = z + S, for any z ∈ A.

Compute:

A = z + {(x_{1}, 0, x_{3})} = {(-3, 7, 4) + (x_{1}, 0, x_{3})} = {(x_{1}-3, 7, x_{3}+ 4)}.

So, S is shifted 7 units to the right.

How about a different example? Consider functions: {1, x, x^{2}, x^{3}}. Is this set linearly independent?

a_{0}+ a_{1}x + a_{2}x^{2}+ a_{3}x^{3}= 0.

Since this holds for all x, this polynomial is the zero polynomial:

a_{0}= a_{1}= a_{2}= a_{3}.

So, the answer is Yes. For more see Function spaces.