• Linear Algebra: #9 Invertible Matrices

Let f : V → W be a linear mapping, and let {v₁, . . . , v_n} ⊂ V and {w₁, . . . , w_m} ⊂ W be bases for V and W, respectively. Then, as we have seen, the mapping f can be uniquely described by specifying the values of f(v_j), for each j = 1, . . . , n. We have

 And the resulting matrix A (as given above) is the matrix describing f with respect to these given bases.


A particular case 
This is the case that V = W. So we have the linear mapping f : V → V. But now, we only need a single basis for V. That is, {v₁, . . . , v_n} ⊂ V is the only basis we need. Thus the matrix for f with respect to this single basis is determined by the specifications

A trivial example
For example, one particular case is that we have the identity mapping

f = id : V → V. 

Thus f(v) = v, for all v ∈ V. In this case it is obvious that the matrix of the mapping is the n × n identity matrix I_n.


Regular matrices
Let us now assume that A is some regular n × n matrix. As we have seen in theorem 23, there is an isomorphism f : V → V, such that A is the matrix representing f with respect to the given basis of V. According to theorem 17, the inverse mapping f⁻¹ is also linear, and we have f⁻¹◦ f = id. So let f⁻¹ be represented by the matrix B (again with respect to the same basis {v₁, . . . , v_n}). Then we must have the matrix equation

B · A = I_n

Or, put another way, in the multiplication system of matrix algebra we must have B = A⁻¹. That is, the matrix A is invertible.


Theorem 24
Every regular matrix is invertible.

Definition
The set of all regular n×n matrices over the field F is denoted GL(n, F).


Theorem 25
GL(n, F) is a group under matrix multiplication. The identity element is the identity matrix.

Proof
We have already seen in an exercise that matrix multiplication is associative. The fact that the identity element in GL(n, F) is the identity matrix is clear. By definition, all members of GL(n, F) have an inverse. It only remains to see that GL(n, F) is closed under matrix multiplication. So let A, C ∈ GL(n, F). Then there exist A⁻¹, C⁻¹ ∈ GL(n, F), and we have that C⁻¹ · A⁻¹ is itself an n × n matrix. But then

(C⁻¹A⁻¹ )AC = C⁻¹(A⁻¹ A)C = C⁻¹I_nC = C⁻¹C = I_n

Therefore, according to the definition of GL(n, F), we must also have AC ∈ GL(n, F).


Simplifying matrices using multiplication with regular matrices


Theorem 26
Let A be an m × n matrix. Then there exist regular matrices C ∈ GL(m, F) and D ∈ GL(n, F) such that the matrix A' = CAD⁻¹ consists simply of zeros, except possibly for a block in the upper left-hand corner, which is an identity matrix. That is

(Note that A' is also an m × n matrix. That is, it is not necessarily square.)

Proof
A is the representation of a linear mapping f : V → W, with respect to bases {v₁, . . . , v_n} and {w₁, . . . , w_m} of V and W, respectively. The idea of the proof is to now find new bases {x₁, . . . , x_n} ⊂ V and {y₁, . . . , y_m} ⊂ W, such that the matrix of f with respect to these new bases is as simple as possible.

So to begin with, let us look at ker(f) ⊂ V. It is a subspace of V, so its dimension is at most n. In general, it might be less than n, so let us write dim(ker(f)) = n − p, for some integer 0 ≤ p ≤ n. Therefore we choose a basis for ker(f), and we call it

{x_p+1, . . . , x_n} ⊂ ker(f) ⊂ V. 

Using the extension theorem (theorem 12), we extend this to a basis

{x₁, . . . , x_p, x_p+1, . . . , x_n}

for V.

Now at this stage, we look at the images of the vectors {x₁, . . . , x_p} under f in W. We find that the set {f(x₁), . . . , f(x_p)} ⊂ W is linearly independent. To see this, let us assume that we have the vector equation

for some choice of the scalars a_i. But that means that the summation in bracket in the right-most hand side of the above equation ∈ ker(f). However {x_p+1, . . . , x_n} is a basis for ker(f). Thus we have

for appropriate choices of scalars b_j. But {x₁, . . . , x_p, x_p+1, . . . , x_n} is a basis for V. Thus it is itself linearly independent and therefore we must have a_i = 0 and b_j = 0 for all possible i and j. In particular, since the a_i’s are all zero, we must have the set {f(x₁), . . . , f(x_p)} ⊂ W being linearly independent.

To simplify the notation, let us call f(x_i) = y_i  for each i = 1, . . . , p. Then we can again use the extension theorem to find a basis

{y₁, . . . , y_p, y_p+1, . . . , y_m}

of W.

So now we define the isomorphism g : V → V by the rule

g(x_i) = v_i , for all i = 1, . . . , n. 

Similarly the isomorphism h : W → W is defined by the rule

h(y_j) = w_j , for all j = 1, . . . , m. 

Let D be the matrix representing the mapping g with respect to the basis {v₁, . . . , v_n} of V, and also let C be the matrix representing the mapping h with respect to the basis {w₁, . . . , w_m} of W.

Let us now look at the mapping

h · f · g⁻¹ : V → W.

For the basis vector v_i ∈ V, we have

This mapping must therefore be represented by a matrix in our simple form, consisting of only zeros, except possibly for a block in the upper left-hand corner which is an identity matrix. Furthermore, the rule that the composition of linear mappings is represented by the product of the respective matrices leads to the conclusion that the matrix A' = CAD⁻¹ must be of the desired form.

• Linear Algebra: #8 Systems of Linear Equations

We now take a small diversion from our idea of linear algebra as being a method of describing geometry, and instead we will consider simple linear equations. In particular, we consider a system of m equations in n unknowns.

We can also think about this as being a vector equation. That is, if

then our system of linear equations is just the single vector equation

A · x = b 

But what is the most obvious way to solve this system of equations? It is a simple matter to write down an algorithm, as follows. The numbers a_ij and b_k are given (as elements of F), and the problem is to find the numbers x_i.

1. Let i : = 1 and j : = 1.
2. if a_ij = 0 then if a_kj = 0 for all i < k ≤ m, set j : = j + 1. Otherwise find the smallest index k > i such that a_kj ≠ 0 and exchange the i-th equation with the k-th equation. kj
3. Multiply both sides of the (possibly new) i-th equation by a_ij^—1. Then for each i < k ≤ m, subtract a_ij times the i-th equation from the k-th equation. Therefore, at this stage, after this operation has been carried out, we will have a_kj = 0, for all k > i. 
4. Set i : = i + 1. If i ≤ n then return to step 2.

So at this stage, we have transformed the system of linear equations into a system in step form.

The next thing is to solve the system of equations in step form. The problem is that perhaps there is no solution, or perhaps there are many solutions. The easiest way to decide which case we have is to reorder the variables — that is the various x_i — so that the steps start in the upper left-hand corner, and they are all one unit wide. That is, things then look like this:

(Note that this reordering of the variables is like our first elementary column operation for matrices.)

So now we observe that:

• If b_l ≠ 0 for some k +1 ≤ l ≤ m, then the system of equations has no solution. 


• Otherwise, if k = n then the system has precisely one single solution. It l is obtained by working backwards through the equations. Namely, the last equation is simply x_n = b_n , so that is clear. But then, substitute b_n for x_n in the n−1-st equation, and we then have x_n-1 = b_n-1 − a_n-1nb_n. By this method, we progress back to the first equation and obtain values for all the x_j, for 1 ≤ j ≤ n. 


• Otherwise, k < n. In this case we can assign arbitrary values to the variables x_k+1, . . . , x_n, and then that fixes the value of x_k. But then, as before, we progressively obtain the values of x_k-1, x_k-2 and so on, back to x₁. 

This algorithm for finding solutions of systems of linear equations is called “Gaussian Elimination”.

All of this can be looked at in terms of our matrix notation. Let us call the following m×n+1 matrix the augmented matrix for our system of linear equations:

Then by means of elementary row and column operations, the matrix is transformed into the new matrix which is in simple step form

Finding the eigenvectors of linear mappings

Definition
Let V be a vector space over a field F, and let f : V → V be a linear mapping of V into itself. An eigenvector of f is a non-zero vector v ∈ V (so we have v ≠ 0) such that there exists some λ ∈ F with f(v) = λv. The scalar λ is then called the eigenvalue associated with this eigenvector.

So if f is represented by the n ×n matrix A (with respect to some given basis of V), then the problem of finding eigenvectors and eigenvalues is simply the problem of solving the equation

Av = λv. 

But here both λ and v are variables. So how should we go about things? Well, as we will see, it is necessary to look at the characteristic polynomial of the matrix, in order to find an eigenvalue λ. Then, once an eigenvalue is found, we can consider it to be a constant in our system of linear equations. And they become the homogeneous system
(That is, all the b_i are zero. Thus a homogeneous system with matrix A has the form Av = 0)

which can be easily solved to give us the (or one of the) eigenvector(s) whose eigenvalue is λ.

Now the n × n identity matrix is

Thus we see that an eigenvalue is any scalar λ ∈ F such that the vector equation (A − λE)v = 0 has a solution vector v ∈ V, such that v ≠ 0.

[Given any solution vector v, then clearly we can multiply it with any scalar κ ∈ F, and we have

(A − λE)(κv) = κ(A − λE)v = κ0 = 0. 

Therefore, as long as κ ≠ 0, we can say that κv is also an eigenvector whose eigenvalue is λ.]

• Linear Algebra: #7 Matrix Transformations

Matrices are used to describe linear mappings f : V → W with respect to particular bases of V and W. But clearly, if we choose different bases than the ones we had been thinking about before, then we will have a different matrix for describing the same linear mapping. Later on in these lectures we will see how changing the bases changes the matrix, but for now, it is time to think about various systematic ways of changing matrices — in a purely abstract way.


Elementary Column Operations 
We begin with the elementary column operations. Let us denote the set of all n×m matrices of elements from the field F by M(m × n, F). Thus, if

then it contains n columns which, as we have seen, are the images of the basis vectors of the linear mapping which is being represented by the matrix. So The first elementary column operation is to exchange column i with column j, for i ≠ j. We can write

So this column operation is denoted by S_ij. It can be thought of as being a mapping S_ij : M(m × n, F) → M(m × n, F).

Another way to imagine this is to say that S is the set of column vectors in the matrix A considered as an ordered list. Thus S ⊂ F^m. Then S_ij is the same set of column vectors, but with the positions of the i-th and the j-th vectors interchanged. But obviously, as a subset of F^m, the order of the vectors makes no difference. Therefore we can say that the span of S is the same as the span of S_ij. That is [S] = [S_ij].

The second elementary column operation, denoted S_i(a), is that we form the scalar product of the element a ≠ 0 in F with the i-th vector in S. So the i-th vector

All the other column vectors in the matrix remain unchanged.

The third elementary column operation, denoted S_ij(c) is that we take the j-th column (where j ≠ i) and multiply it with c ≠ 0, then add it to the i-th column. Therefore the i-th column is changed to

All the other columns — including the j-th column — remain unchanged.


Theorem 20

[S] = [S_ij] = [S_i(a)] = [S_ij(c)], where i ≠ j and a ≠ 0 ≠ c. 

Proof
Let us say that S = {v₁, . . . , v_n} ⊂ F^m. That is, v_i is the i-th column vector of the matrix A, for each i. We have already seen that [S] = [S_ij] is trivially true. But also, say v = x₁v₁ + · · · + x_nv_n is some arbitrary vector in [S]. Then, since a ≠ 0, we can write

v = x₁v₁ + · · · + a^—1x_i(av_i) + · · · + x_nv_n .

Therefore [S] ⊂ [S_i(a)]. The other inclusion, [S_i(a)] ⊂ [S] is also quite trivial so that we have [S] = [S_i(a)].

Similarly we can write

Therefore [S] ⊂ [S_ij(c)], and again, the other inclusion is similar.

Let us call [S] the column space (Spaltenraum), which is a subspace of F^m. Then we see that the column space remains invariant under the three types of elementary column operations. In particular, the dimension of the column space remains invariant


Elementary Row Operations
Again, looking at the m×n matrix A in a purely abstract way, we can say that it is made up of m row vectors, which are just the rows of the matrix. Let us call them w₁, . . . , w_m ∈ Fⁿ. That is,

Again, we define the three elementary row operations analogously to the way we defined the elementary column operations. Clearly we have the same results. Namely if R = {w₁, . . . , w_m} are the original rows, in their proper order, then we have [R] = [R_ij] = [R_i(a)] = [R_ij(c)].

But it is perhaps easier to think about the row operations when changing a matrix into a form which is easier to think about. We would like to change the matrix into a step form (Zeilenstufenform).


Definition
The m × n matrix A is in step form if there exists some r with 0 ≤ r ≤ m and indices 1 ≤ j₁< j₂< · · · < j_r ≤ m with a_iji = 1 for all i = 1, . . . , r and a_st = 0 for all s, t with t < j_s or s > j_r. That is:

Theorem 21
By means of a finite sequence of elementary row operations, every matrix can be transformed into a matrix in step form.

Proof
Induction on m, the number of rows in the matrix. We use the technique of “Gaussian elimination”, which is simply the usual way anyone would go about solving a system of linear equations. This will be dealt with in the next section. The induction step in this proof, which uses a number of simple ideas which are easy to write on the blackboard, but overly tedious to compose here (so it`s currently not available here).

Now it is obvious that the row space (Zeilenraum), that is [R] ⊂ Fⁿ, has the dimension r, and in fact the non-zero row vectors of a matrix in step form provide us with a basis for the row space. But then, looking at the column vectors of this matrix in step form, we see that the columns j₁, j₂, and so on up to  j_r are all linearly independent, and they generate the column space.

Definition
Given an m×n matrix, the dimension of the column space is called the column rank; similarly the dimension of the row space is the row rank.

So, using theorem 21 and exercise 6.3, we conclude that:


Theorem 22
For any matrix A, the column rank is equal to the row rank. This common dimension is simply called the rank — written Rank(A) — of the matrix.

Definition
Let A be a quadratic n×n matrix. Then A is called regular if Rank(A) = n, otherwise A is called singular.


Theorem 23
The n × n matrix A is regular ⇔ the linear mapping f : Fⁿ → Fⁿ, represented by the matrix A with respect to the canonical basis of Fⁿ is an isomorphism.

Proof
‘⇒’ If A is regular, then the rank of A — namely the dimension of the column space [S] — is n. Since the dimension of Fⁿ is n, we must therefore have [S] = Fⁿ. The linear mapping f : Fⁿ → Fⁿ is then both an injection (since S must be linearly independent) and also a surjection.

‘⇐’ Since the set of column vectors S is the set of images of the canonical basis vectors of Fⁿ under f, they must be linearly independent. There are n column vectors; thus the rank of A is n.

• Linear Algebra: #6 Linear Mappings and Matrices

This last example of a linear mapping of ℜ² into itself — which should have been simple to describe — has brought with it long lines of lists of coordinates which are difficult to think about. In three and more dimensions, things become even worse! Thus it is obvious that we need a more sensible system for describing these linear mappings. The usual system is to use matrices.

Now, the most obvious problem with our previous notation for vectors was that the lists of the coordinates (x₁, . . . , x_n) run over the page, leaving hardly any room left over to describe symbolically what we want to do with the vector. The solution to this problem is to write vectors not as horizontal lists, but rather as vertical lists. We say that the horizontal lists are row vectors, and the vertical lists are column vectors. This is a great improvement! So whereas before, we wrote  

v = (x₁, . . . , x_n),

now we will write

It is true that we use up lots of vertical space on the page in this way, but since the rest of the writing is horizontal, we can afford to waste this vertical space. In addition, we have a very nice system for writing down the coordinates of the vectors after they have been mapped by a linear mapping.

To illustrate this system, consider the rotation of the plane through the angle φ, which was described in the last section. In terms of row vectors, we have (x₁, x₂) being rotated into the new vector(x₁ cos φ − x₂ sin φ, x₁ sin φ + x₂ cos φ). But if we change into the column vector notation, we have

A · v = f(v)

That is, matrix multiplication gives the result of the linear mapping.

Expressing f : V → W in terms of bases for both V and W 
The example we have been thinking about up till now (a rotation of ℜ²) is a linear mapping of ℜ² into itself. More generally, we have linear mappings from a vector space V to a different vector space W (although, of course, both V and W are vector spaces over the same field F).

So let {v₁, . . . , v_n} be a basis for V and let {w₁, . . . , w_m} be a basis for W. Finally, let f : V → W be a linear mapping. An arbitrary vector v ∈ V can be expressed in terms of the basis for V as

The question is now, what is f(v)? As we have seen, f(v) can be expressed in terms of the images f(v_j) of the basis vectors of V. Namely

But then, each of these vectors f(v_j) in W can be expressed in terms of the basis vectors in W, say

for appropriate choices of the “numbers” c_ij ∈ F. Therefore, putting this all together, we have

In the matrix notation, using column vectors relative to the two bases {v₁, . . . , v_n} and {w₁, . . . , w_m}, we can write this as

When looking at this m×n matrix which represents the linear mapping f : V → W, we can imagine that the matrix consists of n columns. The i-th column is then

That is, it represents a vector in W, namely the vector v_i = c_1iw₁+ · · · + c_miw_m.

But what is this vector u_i? In the matrix notation, we have

where the single non-zero element of this column matrix is a 1 in the i-th position from the top. But then we have

 

Therefore the columns of the matrix representing the linear mapping f : V → W are the images of the basis vectors of V.


Two linear mappings, one after the other
Things become more interesting when we think about the following situation. Let V, W and X be vector spaces over a common field F. Assume that f : V → W and g : W → X are linear. Then the composition f ◦ g : V → X, given by

f ◦ g(v) = g(f(v)) 

for all v ∈ V is clearly a linear mapping. One can write this as

Let {v₁, . . . , v_n} be a basis for V, {w₁, . . . , w_m} be a basis for W, and {x₁, . . . , x_r} be a basis for X. Assume that the linear mapping f is given by the matrix

and the linear mapping g is given by the matrix

There are so many summations here! How can we keep track of everything? The answer is to use the matrix notation. The composition of linear mappings is then simply represented by matrix multiplication. That is, if

then we have

So this is the reason we have defined matrix multiplication in this way. Recall that if A is an m x n matrix and B is an r x m matrix, then the product BA is an r x n matrix whose kj-th element is the summation of d_kic_ij with i from 1 to m.

• Linear Algebra: #5 Linear Mappings

Definition
Let V and W be vector spaces, both over the field F. Let f : V → W be a mapping from the vector space V to the vector space W. The mapping f is called a linear mapping if

f(au + bv) = af(u) + bf(v) 

for all a, b ∈ F and all u, v ∈ V.

By choosing a and b to be either 0 or 1, we immediately see that a linear mapping always has both f(av) = af(v) and f(u + v) = f(u) + f(v), for all a ∈ F and for all u and v ∈ V. Also it is obvious that f(0) = 0 always.

Definition
Let f : V → W be a linear mapping. The kernel of the mapping, denoted by ker(f), is the set of vectors in V which are mapped by f into the zero vector in W.


Theorem 15
If ker(f) = {0}, that is, if the zero vector in V is the only vector which is mapped into the zero vector in W under f, then f is an injection (monomorphism). The converse is of course trivial.

Proof
That is, we must show that if u and v are two vectors in V with the property that f(u) = f(v), then we must have u = v. But

f(u) = f(v) ⇒ 0 = f(u) − f(v) = f(u − v). 

Thus the vector u − v is mapped by f to the zero vector. Therefore we must have u − v = 0, or u = v.

Conversely, since f(0) = 0 always holds, and since f is an injection, we must have ker(f) = {0}.


Theorem 16
Let f : V → W be a linear mapping and let A = {w₁, . . . , w_m} ⊂ W be linearly independent. Assume that m vectors are given in V, so that they form a set B = {v₁, . . . , v_m} ⊂ V with f(v_i) = w_i , for all i. Then the set B is also linearly independent.

Proof
Let a₁, . . . , a_m ∈ F be given such that a₁v₁ + · · · + a_mv_m = 0. But then

0 = f(0) = f(a₁v₁ + · · · + a_mv_m) = a₁f(v₁)+ · · · + a_mf(v_m) = a₁w₁ + · · · + a_mw_m

Since A is linearly independent, it follows that all the a_i`s must be zero. But that implies that the set B is linearly independent.

Remark
If B = {v₁, . . . , v_m} ⊂ V is linearly independent, and f : V → W is linear, still, it does not necessarily follow that {f(v₁), . . . , f(v_m)} is linearly independent in W. On the other hand, if f is an injection, then {f(v₁), . . . , f(v_m)} is linearly independent. This follows since, if a₁f(v₁)+ · · · + a_mf(v_m) = 0, then we have

0 = a₁f(v₁)+ · · · + a_mf(v_m) = f(a₁v₁ + · · · + a_mv_m) = f(0)

But since f is an injection, we must have a₁v₁ + · · · + a_mv_m = 0. Thus a_i = 0 for all i.

On the other hand, what is the condition for f : V → W to be a surjection (epimorphism)? That is, f(V) = W. Or put another way, for every w ∈ W, can we find some vector v ∈ V with f(v) = w? One way to think of this is to consider a basis B ⊂ W. For each w ∈ B, we take

f^-1(w) = {v ∈ V : f(v) = w } 

Then f is a surjection if f^-1(w) ≠ ∅, for all w ∈ B.


Definition
A linear mapping which is a bijection (that is, an injection and a surjection) is called an isomorphism. Often one writes V ≅ W to say that there exists an isomorphism from V to W.


Theorem 17
Let f : V → W be an isomorphism. Then the inverse mapping f^-1 : W → V is also a linear mapping.

Proof
To see this, let a, b ∈ F and x, y ∈ W be arbitrary. Let f (x) = u ∈ V and f^-1(y) = v ∈ V, say. Then

 f(au + bv) = (f(af^-1(x) + bf^-1(y)) = af(f^-1(x)) + bf(f^-1(y)) = ax + by

 Therefore, since f is a bijection, we must have

f^-1(ax + by) = au + bv = af^-1(x) + bf^-1(y)

Theorem 18
Let V and W be finite dimensional vector spaces over a field F, and let f : V → W be a linear mapping. Let B = {v₁, . . . , v_n} be a basis for V. Then f is uniquely determined by the n vectors {f(v₁), . . . , f(v_n)} in W.

Proof
Let v ∈ V be an arbitrary vector in V. Since B is a basis for V, we can uniquely write

v = a₁v₁ + · · · + a_nv_n 

with a_i ∈ F, for each i. Then, since the mapping f is linear, we have

Therefore we see that if the values of f(v₁), . . . , f(v_n) are given, then the value of f(v) is uniquely determined, for each v ∈ V.

On the other hand, let A = {u₁, . . . , u_n} be a set of n arbitrarily given vectors in W. Then let a mapping f : V → W be defined by the rule

f(v) = a₁u₁ + · · · + a_nu_n

for each arbitrarily given vector v ∈ V, where v = a₁v₁ + · · · + a_nv_n. Clearly the mapping is uniquely determined, since v is uniquely determined as a linear combination of the basis vectors B. It is a trivial matter to verify that the mapping which is so defined is also linear. We have f(v_i) = u_i for all the basis vectors v_i ∈ B.


Theorem 19
Let V and W be two finite dimensional vector spaces over a field F. Then we have

V ≅ W ⇔ dim(V) = dim(W). 

Proof
“⇒” Let f : V → W be an isomorphism, and let B = {v₁, . . . , v_n} ⊂ V be a basis for V. Then, as shown in our Remark above, we have A = {f(v₁), . . . , f(v_n)} ⊂ W being linearly independent. Furthermore, since B is a basis of V, we have [B] = V. Thus [A] = W also. Therefore A is a basis of W, and it contains precisely n elements; thus dim(V) = dim(W).

“⇐” Take B = {v₁, . . . , v_n} ⊂ V to again be a basis of V and let A = {w₁, . . . , w_n} ⊂ W be some basis of W (with n elements). Now define the mapping f : V → W by the rule f(v_i) = w_i , for all i. By theorem 18 we see that a linear mapping f is thus uniquely determined. Since A and B are both bases, it follows that f must be a bijection.

This immediately gives us a complete classification of all finite-dimensional vector spaces. For let V be a vector space of dimension n over the field F. Then clearly Fⁿ is also a vector space of dimension n over F. The canonical basis is the set of vectors {e₁, . . . , e_n}, where

e_i = {0, . . . ,0, 1 , 0, . . . ,0} with the 1 in the i-th position

for each i. Therefore, when thinking about V, we can think that it is “really” just Fⁿ. On the other hand, the central idea in the theory of linear algebra is that we can look at things using different possible bases (or “frames of reference” in physics). The space Fⁿ seems to have a preferred, fixed frame of reference, namely the canonical basis. Thus it is better to think about an abstract V, with various possible bases.


Examples 
For these examples, we will consider the 2-dimensional real vector space ℜ², together with its canonical basis B = {e₁, e₂} = {(1, 0), (0, 1)}.

• f₁ : ℜ² → ℜ² with f₁(e₁) = (−1, 0) and f₁(e₂) = (0, 1). This is a reflection of the 2-dimensional plane into itself, with the axis of reflection being the second coordinate axis; that is the set of points (x₁, x₂) ∈ ℜ² with x₁ = 0.



• f₂ : ℜ² → ℜ² with f₂(e₁) = e₂ and f₁(e₂) = e₁. This is a reflection of the 2-dimensional plane into itself, with the axis of reflection being the diagonal axis x₁ = x₂ .



• f₃ : ℜ² → ℜ² with f₃(e₁) = (cos φ, sin φ) and f₁(e₂) = (−sin φ, cos φ), for some real number φ ∈ ℜ. This is a rotation of the plane about its middle point, through an angle of φ.
  
  (In analysis, we learn about the formulas of trigonometry. In particular we have
  
  cos(θ + φ) = cos(θ) cos(φ) − sin(θ) sin(φ), 
  sin(θ + φ) = sin(θ) cos(φ) − cos(θ) sin(φ). 
  Taking θ = π/2, we note that cos(φ + π/2) = −sin(φ) and sin(φ + π/2) = cos(φ).)
  
  For let v = (x₁, x₂) be some arbitrary point of the plane ℜ². Then we have
  
  

Looking at this from the point of view of geometry, the question is, what happens to the vector v when it is rotated through the angle φ while preserving its length? Perhaps the best way to look at this is to think about v in polar coordinates. That is, given any two real numbers x₁ and x₂ then, assuming that they are not both zero, we find two unique real numbers r ≥ 0 and θ ∈ [0, 2π), such that

x₁ = r cos θ and x₂ = r sin θ, 

where r = √(x₁²+ x₂²). Then v = (r cos θ, r sin θ). So a rotation of v through the angle φ must bring it to the new vector (r cos(φ + θ), r sin(φ + θ)) which, if we remember the formulas for cosines and sines of sums, turns out to be

(r(cos(θ) cos(φ) − sin(θ) sin(φ)), r(sin(θ) cos(φ) − cos(θ) sin(φ)). 

But then, remembering that x₁ = r cos θ and x₂ = r sin θ, we see that the rotation brings the vector v into the new vector

(x₁ cos φ − x₂ sin φ, x₁ sin φ + x₂ cos φ), 

 which was precisely the specification for f₃(v).

• Linear Algebra: #4 Linear Independence and Dimension

Definition
Let v₁, . . . , v_n ∈ V be finitely many vectors in the vector space V over the field F. We say that the vectors are linearly dependent if there exists an equation of the form

a₁· v₁ + · · · + a_n· v_n = 0, 

such that not all a_i ∈ F are simply zero. If no such non-trivial equation exists, then the set {v₁, . . . , v_n} ⊂ V is said to be linearly independent.

This definition is undoubtedly the most important idea that there is in the theory of linear algebra!

Examples 

• In ℜ² let v₁ = (1, 0), v₂ = (0, 1) and v₃ = (1, 1). Then the set {v₁, v₂, v₃} is linearly dependent, since we have
  
  
  v₁ + v₂ - v₁ = 0 
  
  On the other hand, the set {v₁, v₂} is linearly independent.


• In C₀([0, 1], ℜ), let f₁ : [0, 1] → ℜ be given by f₁(x) = 1 for all x ∈ [0, 1]. Similarly, let f₂ be given by f₂(x) = x, and f₃ is f₃(x) = 1 − x. Then the set {f₁, f₂, f₃} is linearly dependent. 

Now take some vector space V over a field F, and let S ⊂ V be some subset of V. (The set S can be finite or infinite here, although we will usually be dealing with finite sets.) Let v₁, . . . , v_n ⊂ S be some finite collection of vectors in S, and let a₁, . . . , a_n∈ F be some arbitrary collection of elements of the field. Then the sum

a₁· v₁ + · · · + a_n· v_n  

is a linear combination of the vectors v₁, . . . , v_n in S. The set of all possible linear combinations of vectors in S is denoted by span(S), and it is called the linear span of S. One also writes [S]. S is the generating set of [S]. Therefore if [S] = V, then we say that S is a generating set for V . If S is finite, and it generates V, then we say that the vector space V is finitely generated.


Theorem 5
Given S ⊂ V, then [S] is a subspace of V.

Proof
A simple consequence of theorem 2.

Examples

• For any n ∈ ℕ, let
  
  
  Then S = {e₁, e₂ ,. . . , e_n} is a generating set for ℜⁿ
  
• On the other hand, the vector space C₀([0, 1], ℜ) is clearly not finitely generated. (In general such function spaces — which play a big role in quantum field theory, and which are studied using the mathematical theory of functional analysis — are not finitely generated. However in this lecture, we will mostly be concerned with finitely generated vector spaces. )

So let S = {v₁, . . . , v_n} ⊂ V be a finite set. From now on in these discussions, we will assume that such sets are finite unless stated otherwise.


Theorem 6
Let w = a₁v₁ + · · · + a_nv_n be some vector in [S] ⊂ V, where a₁, . . . , a_n are arbitrarily given elements of the field F. We will say that this representation of w is unique if, given some other linear combination, w = b₁v₁ + · · · + b_nv_n , then we must have b_i = a_i for all i = 1, . . . , n. Given this, then we have that the set S is linearly independent ⇔ the representation of all vectors in the span of S as linear combinations of vectors in S is unique.

Proof.
‘⇐’ We certainly have 0v₁ + · · · + 0v_n= 0. Since this representation of the zero vector is unique, it follows S is linearly independent.

‘⇒’ Can it be that S is linearly independent, and yet there exists a vector in the span of S which is not uniquely represented as a linear combination of the vectors in S? Assume that there exist elements a₁, . . . , a_n and b₁, . . . , b_n of the field F, where a_j ≠ b_j , for at least one j between 1 and n, such that

shows that S cannot be a linearly independent set.


Definition
Assume that S ⊂ V is a finite, linearly independent subset with [S] = V. Then S is called a basis for V.


Lemma
Assume that S = {v₁, . . . , v_n} ⊂ V is linearly dependent. Then there exists some j ∈ {1, . . . , n}, and elements a_i ∈ F, for i ≠ j, such that

 

 Proof
Since S is linearly dependent, there exists some non-trivial linear combination of the elements of S, summing to the zero vector,

such that b_j ≠ 0, for at least one of the j. Take such a one. Then



Corollary
Let S = {v₁, . . . , v_n} ⊂ V be linearly dependent, and let v_j be as in the lemma above. Let S' = {v₁, . . . , v_j-1 ,v_j+1 , . . . ,v_n} be S, with the element v_j removed.



Theorem 7
Assume that the vector space V is finitely generated. Then there exists a basis for V.

Proof
Since V is finitely generated, there exists a finite generating set. Let S be such a finite generating set which has as few elements as possible. If S were linearly dependent, then we could remove some element, as in the lemma, leaving us with a still smaller generating set for V. This is a contradiction. Therefore S must be a basis for V.


Theorem 8
Let S = {v₁, . . . , v_n} be a basis for the vector space V, and take some arbitrary non-zero vector w ∈ V. Then there exists some j ∈ {1, . . . , n}, such that

S' = {v₁, . . . , v_j-1 , w, v_j+1 , . . . ,v_n}

is also a basis of V.

Proof
Writing w = a₁v₁ + · · · + a_nv_n, we see that since w ≠ 0, at least one  a_j ≠ 0. Taking that j, we write

We now prove that [S'] = V. For this, let u ∈ V be an arbitrary vector. Since S is a basis for V, there exists a linear combination u = b₁v₁ + · · · + b_nv_n. Then we have

This shows that [S'] = V.

In order to show that S' is linearly independent, assume that we have

for some c, and c_i ∈ F. Since the original set S was assumed to be linearly independent, we must have ca_i + c_i = 0, for all i. In particular, since c_j = 0, we have ca_j = 0. But the assumption was that a_j ≠ 0. Therefore we must conclude that c = 0. It follows that also c_i = 0. , for all i ≠ j. Therefore, S' must be linearly independent.


Theorem 9 (Steinitz Exchange Theorem)
Let S = {v₁, . . . , v_n} be a basis of V and let T = {w₁, . . . , w_m} ⊂ V be some linearly independent set of vectors in V. Then we have m ≤ n. By possibly re-ordering the elements of S, we may arrange things so that the set

U = {w₁, . . . , w_m , v_m+1 , . . . ,v_n} 

is a basis for V.

Proof
Use induction over the number m. If m = 0 then U = S and there is nothing to prove.

Therefore assume m ≥ 1 and furthermore, the theorem is true for the case m − 1. So consider the linearly independent set T' = {w₁, . . . , w_m-1}. After an appropriate re-ordering of S, we have U' = {w₁, . . . , w_m-1, v_m , . . . ,v_n} being a basis for V. Note that if we were to have n < m, then T' would itself be a basis for V. Thus we could express w_m as a linear combination of the vectors in T'. That would imply that T was not linearly independent, contradicting our assumption. Therefore, m ≤ n.

Now since U' is a basis for V, we can express w_mas a linear combination

w_m = a₁w₁ + · · · + a_m-1w_m-1 + a_mv_m + · · · + a_nv_n

If we had all the coefficients of the vectors from S being zero, namely
 

a_m = a_m+1 = · · · = a_n = 0,

then we would have w_m being expressed as a linear combination of the other vectors in T. Therefore T would be linearly dependent, which is not true. Thus one of the a_j ≠ 0, for j ≥ m. Using theorem 8, we may exchange w_m for the vector v_j in U', thus giving us the basis U.


Theorem 10 (Extension Theorem)
Assume that the vector space V is finitely generated and that we have a linearly independent subset S ⊂ V. Then there exists a basis B of V with S ⊂ B.

Proof
If [S] = V then we simply take B = S. Otherwise, start with some given basis A ⊂ V and apply theorem 9 successively.


Theorem 11
Let U be a subspace of the (finitely generated) vector space V. Then U is also finitely generated, and each possible basis for U has no more elements than any basis for V.

Proof
Assume there is a basis B of V containing n vectors. Then, according to theorem 9, there cannot exist more than n linearly independent vectors in U. Therefore U must be finitely generated, such that any basis for U has at most n elements.


Theorem 12
Assume the vector space V has a basis consisting of n elements. Then every basis of V also has precisely n elements.

Proof
This follows directly from theorem 11, since any basis generates V, which is a subspace of itself.


Definition
The number of vectors in a basis of the vector space V is called the dimension of V, written dim(V).

Definition
Let V be a vector space with subspaces X, Y ⊂ V. The subspace X + Y = [X ∪ Y ] is called the sum of X and Y. If X ∩ Y = {0}, then it is the direct sum, written X ⊕ Y.


Theorem 13 (A Dimension Formula)
Let V be a finite dimensional vector space with subspaces X, Y ⊂ V. Then we have

dim(X + Y) = dim(X) + dim(Y) − dim(X ∩ Y).

Corollary
dim(X ⊕ Y) = dim(X) + dim(Y).

Proof of Theorem 13
Let  S = {v₁, . . . , v_n} be a basis of X ∩ Y. According to theorem 10, there exist extensions  T = {x₁, . . . , x_m} and  U = {y₁, . . . , y_r}, such that S ∪ T is a basis for X and S ∪ U is a basis for Y. We will now show that, in fact, S ∪ T ∪ U is a basis for X + Y.

To begin with, it is clear that X+Y = [S ∪T ∪U]. Is the set S ∪T ∪U linearly independent? Let

Then we have y = −v − x. Thus y ∈ X. But clearly we also have, y ∈ Y. Therefore y ∈ X ∩ Y. Thus y can be expressed as a linear combination of vectors in S alone, and since S ∪ U is is a basis for Y , we must have c_k = 0 for k = 1, . . . , r. Similarly, looking at the vector x and applying the same argument, we conclude that all the b_j are zero. But then all the a_i must also be zero since the set S is linearly independent.

Putting this all together, we see that the dim(X) = n +m, dim(Y) = n +r and dim(X ∩ Y) = n. This gives the dimension formula.


Theorem 14
Let V be a finite dimensional vector space, and let X ⊂ V be a subspace. Then there exists another subspace Y ⊂ V, such that V = X ⊕ Y.

Proof
Take a basis S of X. If [S] = V then we are finished. Otherwise, use the extension theorem (theorem 10) to find a basis B of V, with S ⊂ B. Then Y = [B \ S] satisfies the condition of the theorem. (The notation B \ S denotes the set of elements of B which are not in S)

• Linear Algebra: #3 Subspaces

Let V be a vector space over a field F and let W ⊂ V be some subset. If W is itself a vector space over F, considered using the addition and scalar multiplication in V, then we say that W is a subspace of V. Analogously, a subset H of a group G, which is itself a group using the multiplication operation from G, is called a subgroup of G. Subfields are similarly defined.


Theorem 2
Let W ⊂ V be a subset of a vector space over the field F. Then

W is a subspace of V ⇔ a · v + b · w  ∈ W,

for all v, w ∈ W and a, b ∈ F.

Proof. 
The direction ‘⇒’ is trivial.

For ‘⇐’, begin by observing that 1 · v + 1 · w = v + w ∈ W, and a · v + 0 · w = a · v ∈ W, for all v, w ∈ W and a ∈ F. Thus W is closed under vector addition and scalar multiplication.

Is W a group with respect to vector addition? We have 0 · v = 0 ∈ W, for v ∈ W; therefore the neutral element 0 is contained in W. For an arbitrary v ∈ W we have

Therefore (−1) · v is the inverse element to v under addition, and so we can simply write (−1) · v = −v.

The other axioms for a vector space can be easily checked.

The method of this proof also shows that we have similar conditions for subsets of groups or fields to be subgroups, or subfields, respectively.


Theorem 3
Let H ⊂ G be a (non-empty) subset of the group G. Then H is a subgroup of G ⇔ ab⁻¹ ∈ H, for all a, b ∈ H.

Proof
The direction ‘⇒’ is trivial. As for ‘⇐’, let a ∈ H. Then aa^-1 = e ∈ H. Thus the neutral element of the group multiplication is contained in H. Also ea^-1 = a^-1 ∈ H. Furthermore, for all a, b ∈ H, we have a(b^-1)^-1 = ab ∈ H. Thus H is closed under multiplication. The fact that the multiplication is associative (a(bc) = (ab)c for all a, b and c ∈ H follows since G itself is a group; thus the multiplication throughout G is associative.


Theorem 4
Let U, W ⊂ V be subspaces of the vector space V over the field F. Then U ∩ W is also a subspace.

Proof 
Let v, w ∈ U ∩ W be arbitrary vectors in the intersection, and let a, b ∈ F be arbitrary elements of the field F. Then, since U is a subspace of V, we have a · v + b · w ∈ U. This follows from theorem 2. Similarly a · v + b · w ∈ W. Thus it is in the intersection, and so theorem 2 shows that U ∩ W is a subspace.