linear algebra vector spaces lecture notes and lecture notes on introduction to linear algebra. what is linear algebra used for in computer science pdf free download
ZackVincent,United Kingdom,Teacher
Published Date:15-07-2017
Your Website URL(Optional)
Comment
MA106 Linear Algebra lecture notes
Lecturers: Martin Bright and Daan Krammer
Warwick, January 2011
Contents
1 Number systems and elds 3
1.1 Axioms for number systems . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Vector spaces 4
2.1 Examples of vector spaces . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3 Linear independence, spanning and bases of vector spaces 6
3.1 Linear dependence and independence . . . . . . . . . . . . . . . . . . . . 6
3.2 Spanning vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.3 Bases of vector spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.4 Existence of a basis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4 Subspaces 10
5 Linear transformations 13
5.1 De nition and examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
5.2 Kernels and images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
5.3 Rank and nullity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
5.4 Operations on linear maps . . . . . . . . . . . . . . . . . . . . . . . . . . 17
6 Matrices 18
7 Linear transformations and matrices 20
7.1 Setting up the correspondence . . . . . . . . . . . . . . . . . . . . . . . . 20
7.2 The correspondence between operations on linear maps and matrices . . 22
7.3 Linear equations and the inverse image problem . . . . . . . . . . . . . . 24
8 Elementary operations and the rank of a matrix 25
8.1 Gauss transformations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
8.2 Elementary row operations . . . . . . . . . . . . . . . . . . . . . . . . . 26
8.3 The augmented matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
8.4 Row reducing a matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
8.5 Elementary column operations . . . . . . . . . . . . . . . . . . . . . . . 29
8.6 The rank of a matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
8.7 The rank criterion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
9 The inverse of a linear transformation and of a matrix 33
9.1 De nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
9.2 Matrix inversion by row reduction . . . . . . . . . . . . . . . . . . . . . 34
9.3 Elementary matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
9.4 Application to linear equations . . . . . . . . . . . . . . . . . . . . . . . 36
110 The determinant of a matrix 37
10.1 De nition of the determinant . . . . . . . . . . . . . . . . . . . . . . . . 37
10.2 The e ect of matrix operations on the determinant . . . . . . . . . . . . 39
10.3 The determinant of a product . . . . . . . . . . . . . . . . . . . . . . . . 42
10.4 Minors and cofactors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
10.5 The inverse of a matrix using determinants . . . . . . . . . . . . . . . . 44
10.6 Cramer's rule for solving simultaneous equations . . . . . . . . . . . . . 45
11 Change of basis and equivalent matrices 45
12 Similar matrices, eigenvectors and eigenvalues 48
12.1 Similar matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
12.2 Eigenvectors and eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . 49
12.3 The scalar product symmetric and orthogonal matrices . . . . . . . . . 54
21 Number systems and elds
We introduce the number systems most commonly used in mathematics.
1. The natural numbersN =f1; 2; 3; 4;:::g.
InN, addition is possible but not subtraction; e.g. 2 362N.
2. The integersZ =f:::; 2; 1; 0; 1; 2; 3;:::g.
InZ, addition, subtraction and multiplication are always possible, but not division;
e.g. 2=362Z.
3. The rational numbersQ =fp=qjp;q2Z; q =6 0g.
In Q, addition, subtraction, multiplication and division (except by zero) are all
p
possible. However, 262Q.
4. The real numbersR. These are the numbers which can be expressed as decimals.
The rational numbers are those with nite or recurring decimals.
In R, addition, subtraction, multiplication and division (except by zero) are still
p
possible, and all positive numbers have square roots, but 162R.
2
5. The complex numbersC =fx +iyjx;y2Rg, where i = 1.
In C, addition, subtraction, multiplication and division (except by zero) are still
possible, and all, numbers have square roots. In fact all polynomial equations with
coecients inC have solutions inC.
1.1 Axioms for number systems
Laws governing the way numbers combine together are called axioms. Any particular
axiom might be true in some number systems but not in others.
Axioms for addition. Let S be a number system.
A1. + = + for all ; 2S.
A2. ( + ) +
= + ( +
) for all ; ;
2S.
A3. There is a number 02S such that + 0 = 0 + = for all 2S.
A4. For each number 2 S there exists a number 2 S such that + ( ) =
( ) + = 0.
These axioms may or may not be satis ed by a given number systemS. For example,
inN, A1 and A2 hold but A3 and A4 do not hold. A1A4 all hold inZ;Q;R andC.
Axioms for multiplication.
M1. : = : for all ; 2S.
M2. ( : ):
= :( :
) for all ; ;
2S.
M3. There is a number 12S such that :1 = 1: = for all 2S.
1
M4. For each number 2 S with 6= 0, there exists a number 2 S such that
1 1
: = : = 1.
InN andZ, M1M3 hold but M4 does not hold. M1M4 all hold inQ;R andC.
3Axiom relating addition and multiplication.
D. ( + ):
= :
+ :
for all ; ;
2S.
De nition. A setS on which addition and multiplication are de ned is called a eld if
it satis es each of the axioms A1, A2, A3, A4, M1, M2, M3, M4, D, and if, in addition,
16= 0.
Roughly speaking, S is a eld if addition, subtraction, multiplication and division
(except by zero) are all possible in S. We shall always use the letter K for a general
eld.
Example. N andZ are not elds, butQ,R andC are all elds.
There are many other elds, including some nite elds. For example, for each prime
number p, there is a eld F =f0; 1; 2;:::;p 1g with p elements, where addition and
p
multiplication are carried out modulo p. Thus, inF , we have 5 + 4 = 2, 5 4 = 6 and
7
1
5 = 3 because 5 3 = 1. The smallest such eld F has just two elements 0 and 1,
2
where 1+1 = 0. This eld is extremely important in Computer Science since an element
ofF represents a bit of information.
2
Various other familiar properties of numbers, such as 0 = 0, ( ) = ( ) =
( ), ( )( ) = , ( 1) = , for all ; 2S, can be proved from the axioms.
Why would we want to do this, when we can see they're true anyway? The point is
that, when we meet a new number system, it is enough to check whether the axioms
hold; if they do, then all these properties follow automatically.
However, occasionally you need to be careful. For example, inF we have 1 + 1 = 0,
2
and so it is not possible to divide by 2 in this eld.
2 Vector spaces
De nition. A vector space over a eld K is a set V which has two basic operations,
addition and scalar multiplication, satisfying certain requirements. Thus for every pair
u; v2 V , u + v2 V is de ned, and for every 2 K, v2 V is de ned. For V to
be called a vector space, the following axioms must be satis ed for all ; 2K and all
u; v2V .
(i) Vector addition satis es axioms A1, A2, A3 and A4.
(ii) (u + v) = u + v;
(iii) ( + )v = v + v;
(iv) ( )v = ( v);
(v) 1v = v.
Elements of the eld K will be called scalars. Note that we will use boldface letters
like v to denote vectors. The zero vector in V will be written as 0 , or usually just 0.
V
This is di erent from the zero scalar 0 = 0 2K.
K
For nearly all results in this course, there is no loss in assuming that K is the eldR
of real numbers. So you may assume this if you nd it helpful to do so. Just occasionally,
we will need to assume K =C the eld of complex numbers.
However, it is important to note that nearly all arguments in Linear Algebra use
only the axioms for a eld and so are valid for any eld, which is why shall use a general
eld K for most of the course.
42.1 Examples of vector spaces
n
1. K =f( ; ;:::; )j 2Kg. This is the space of row vectors. Addition and
1 2 n i
scalar multiplication are de ned by the obvious rules:
( ; ;:::; ) + ( ; ;:::; ) = ( + ; + ;:::; + );
1 2 n 1 2 n 1 1 2 2 n n
( ; ;:::; ) = ( ; ;:::; ):
1 2 n 1 2 n
The most familiar examples are
2 3
R =f(x;y)jx;y2Rg and R =f(x;y;z)jx;y;z2Rg;
which we can think of geometrically as the points in ordinary 2- and 3-dimensional
space, equipped with a coordinate system.
2 3
Vectors inR andR can also be thought of as directed lines joining the origin to
the points with coordinates (x;y) or (x;y;z).
(x;y)
:
0 =(0,0)
Addition of vectors is then given by the parallelogram law.
v + v
1 2
v
2
:
v
1
0
1
Note that K is essentially the same as K itself.
2. Let Kx be the set of polynomials in an indeterminate x with coecients in the
eld K. That is,
n
Kx =f + x + + x jn 0; 2Kg:
0 1 n i
Then Kx is a vector space over K.
3. LetKx be the set of polynomials overK of degree at mostn, for somen 0.
n
Then Kx is also a vector space over K; in fact it is a subspace of Kx.
n
Note that the polynomials of degree exactly n do not form a vector space. (Why
not?)
4. Let K = R and let V be the set of n-times di erentiable functions f : R R
which are solutions of the di erential equation
n n 1
d f d f df
+ + + + f = 0:
0 1 n 1 n
n n 1
dx dx dx
for xed ; ;:::; 2 R. Then V is a vector space over R, for if f(x) and
0 1 n
g(x) are both solutions of this equation, then so are f(x) +g(x) and f(x) for all
2R.
5. The previous example is a space of functions. There are many such examples that
k
are important in Analysis. For example, the set C ((0; 1);R), consisting of all
(k)
functionsf : (0; 1)R such that thekth derivative f exists and is continuous,
is a vector space overR with the usual pointwise de nitions of addition and scalar
multiplication of functions.
5n
6. Any n bits of information can be thought of as a vector in F .
2
Facing such a variety of vector spaces, a mathematician wants to derive useful meth-
ods of handling all these vector spaces. If work out techniques for dealing with a single
3 8
example, sayR , how can we be certain that our methods will also work forR or even
8
C ? That is why we use the axiomatic approach to developing mathematics. We must
use only arguments based on the vector space axioms. We have to avoid making any
other assumptions. This ensures that everything we prove is valid for all vector spaces,
3
not just the familiar ones likeR .
We shall be assuming the following additional simple properties of vectors and scalars
from now on. They can all be deduced from the axioms (and it is a useful exercise to
do so).
(i) 0 = 0 for all 2K
(ii) 0v = 0 for all v2V
(iii) ( v) = ( )v = ( v), for all 2K and v2V .
(iv) if v = 0 then = 0 or v = 0.
3 Linear independence, spanning and bases of vector
spaces
3.1 Linear dependence and independence
De nition. Let V be a vector space over the eld K. The vectors v ; v ;::: v are
1 2 n
said to be linearly dependent if there exist scalars ; ;:::; 2K, not all zero, such
1 2 n
that
v + v + + v = 0:
1 1 2 2 n n
v ; v ;::: v are said to be linearly independent if they are not linearly dependent. In
1 2 n
other words, they are linearly independent if the only scalars ; ;:::; 2 K that
1 2 n
satisfy the above equation are = 0, = 0, :::; = 0:
1 2 n
De nition. Vectors of the form v + v + + v for ; ;:::; 2K are
1 1 2 2 n n 1 2 n
called linear combinations of v ; v ;::: v .
1 2 n
2
Example. Let V =R , v = (1; 3), v = (2; 5).
1 2
Then v + v = ( + 2 ; 3 + 5 ), which is equal to 0 = (0; 0) if and only
1 1 2 2 1 2 1 2
if + 2 = 0 and 3 + 5 = 0. Thus we have a pair of simultaneous equations in
1 2 1 2
; and the only solution is = = 0, so v , v are linearly independent.
1 2 1 2 1 2
2
Example. Let V =Q , v = (1; 3), v = (2; 6).
1 2
This time the equations are + 2 = 0 and 3 + 6 = 0, and there are non-zero
1 2 1 2
solutions, such as = 2, = 1, and so v , v are linearly dependent.
1 2 1 2
Lemma 3.1. v ; v ;:::; v 2V are linearly dependent if and only if either v = 0 or,
1 2 n 1
for some r, v is a linear combination of v ;:::; v .
r 1 r 1
Proof. If v = 0 then by putting = 1 and = 0 fori 1 we get v ++ v =
1 1 i 1 1 n n
0, so v ; v ;:::; v 2V are linearly dependent.
1 2 n
If v is a linear combination of v ;:::; v , then v = v + + v for
r 1 r 1 r 1 1 r 1 r 1
some ;:::; 2 K and so we get v + + v 1 v = 0 and again
1 r 1 1 1 r 1 r 1 r
v ; v ;:::; v 2V are linearly dependent.
1 2 n
Conversely, suppose that v ; v ;:::; v 2 V are linearly dependent, and are
1 2 n i
scalars, not all zero, satisfying v + v + + v = 0. Let r be maximal
1 1 2 2 n n
with 6= 0; then v + v + + v = 0. Ifr = 1 then v = 0 which, by (iv)
r 1 1 2 2 r r 1 1
above, is only possible if v = 0. Otherwise, we get
1
1 r 1
v = v v :
r 1 r 1
r r
In other words, v is a linear combination of v ;:::; v .
r 1 r 1
63.2 Spanning vectors
De nition. The vectors v ;:::; v in V span V if every vector v 2 V is a linear
1 n
combination v + v + + v of v ;:::; v .
1 1 2 2 n n 1 n
3.3 Bases of vector spaces
De nition. The vectors v ;:::; v inV form a basis ofV if they are linearly indepen-
1 n
dent and span V .
Proposition 3.2. The vectors v ;:::; v form a basis of V if and only if every v2V
1 n
can be written uniquely as v = v + v + + v ; that is, the coecients
1 1 2 2 n n
;:::; are uniquely determined by the vector v.
1 n
Proof. Suppose that v ;:::; v form a basis ofV . Then they spanV , so certainly every
1 n
v2 V can be written as v = v + v + + v . Suppose that we also had
1 1 2 2 n n
v = v + v + + v for some other scalars 2K. Then we have
1 1 2 2 n n i
0 = v v = ( )v + ( )v + + ( )v
1 1 1 2 2 2 n n n
and so
( ) = ( ) = = ( ) = 0
1 1 2 2 n n
by linear independence of v ;:::; v . Hence = for all i, which means that the
1 n i i i
are uniquely determined.
Conversely, suppose that every v2V can be written uniquely as v = v + v +
1 1 2 2
+ v . Then v ;:::; v certainly span V . If v + v + + v = 0, then
n n 1 n 1 1 2 2 n n
v + v + + v = 0v + 0v + + 0v
1 1 2 2 n n 1 2 n
and so the uniqueness assumption implies that = = = = 0, and v ;:::; v
1 2 n 1 n
are linearly independent. Hence they form a basis of V .
De nition. The scalars ;:::; in the statement of the proposition are called the
1 n
coordinates of v with respect to the basis v ;:::; v .
1 n
With respect to a di erent basis, v will have di erent coordinates. Indeed, a basis
for a vector space can be thought of as a choice of a system of coordinates.
Examples Here are some examples of bases of vector spaces.
2
1. (1; 0) and (0; 1) form a basis ofK . This follows from Proposition 3.2, because each
2
element ( ; )2K can be written as (1; 0) + (0; 1), and this expression is
1 2 1 2
clearly unique.
3
2. More generally, (1; 0; 0), (0; 1; 0), (0; 0; 1) form a basis ofK , (1; 0; 0; 0), (0; 1; 0; 0),
4
(0; 0; 1; 0), (0; 0; 0; 1) form a basis of K and so on. This is called the standard
n
basis of K for n2N.
n
(To be precise, the standard basis ofK is v ;:::; v , where v is the vector with
1 n i
a 1 in the ith position and a 0 in all other positions.)
n 2
3. There are many other bases of K . For example (1; 0); (1; 1) form a basis of K ,
because ( ; ) = ( )(1; 0) + (1; 1), and this expression is unique. In
1 2 1 2 2
fact, any two non-zero vectors such that one is not a scalar multiple of the other
2
form a basis for K .
4. As we have de ned a basis, it has to consist of a nite number of vectors. Not every
vector space has a nite basis. For example, let Kx be the space of polynomials
in x with coecients in K. Let p (x);p (x);:::;p (x) be any nite collection of
1 2 n
polynomials inKx. Then, ifd is the maximum degree ofp (x);p (x);:::;p (x),
1 2 n
any linear combination of p (x);p (x);:::;p (x) has degree at most d, and so
1 2 n
p (x);p (x);:::;p (x) cannot span Kx. On the other hand, it is possible (with
1 2 n
a little care) to de ne what it means for an in nite set of vectors to be a basis of
2 3 n
a vector space; in fact the in nite sequence of vectors 1;x;x ;x ;:::;x ;::: is a
basis of Kx.
7A vector space with a nite basis is called nite-dimensional. In fact, nearly all of
this course will be about nite-dimensional spaces, but it is important to remember that
these are not the only examples. The spaces of functions mentioned in Example 5. of
Section 2 typically have uncountably in nite dimension.
Theorem 3.3 (The basis theorem). Suppose that v ;:::; v and w ;:::; w are both
1 m 1 n
bases of the vector space V . Then m =n. In other words, all nite bases of V contain
the same number of vectors.
The proof of this theorem is quite tricky and uses the concept of sifting which we
introduce after the next lemma.
De nition. The number n of vectors in a basis of the nite-dimensional vector space
V is called the dimension of V and we write dim(V ) =n.
n
Thus, as we might expect, K has dimension n. Kx is in nite-dimensional, but
2 n
the space Kx of polynomials of degree at most n has basis 1;x;x ;:::;x , so its
n
dimension is n + 1 (not n).
Note that the dimension of V depends on the eld K. Thus the complex numbers
C can be considered as
a vector space of dimension 1 over C, with one possible basis being the single
element 1;
a vector space of dimension 2 over R, with one possible basis given by the two
elements 1;i;
a vector space of in nite dimension overQ.
The rst step towards proving the basis theorem is to be able to remove unnecessary
vectors from a spanning set of vectors.
Lemma 3.4. Suppose that the vectors v ; v ;:::; v ; w span V and that w is a linear
1 2 n
combination of v ;:::; v . Then v ;:::; v span V .
1 n 1 n
Proof. Since v ; v ;:::; v ; w span V , any vector v2V can be written as
1 2 n
v = v + + v + w;
1 1 n n
But w is a linear combination of v ;:::; v , so w =
v + +
v for some scalars
1 n 1 1 n n
, and hence
i
v = ( +
)v + + ( +
)v
1 1 1 n n n
is a linear combination of v ;:::; v , which therefore span V .
1 n
There is an important process, which we shall call sifting, which can be applied to
any sequence of vectors v ; v ;:::; v in a vector space V , as follows. We consider
1 2 n
each vector v in turn. If it is zero, or a linear combination of the preceding vectors
i
v ;:::; v , then we remove it from the list.
1 i 1
3
Example. Let us sift the following sequence of vectors in R .
v = (0; 0; 0) v = (1; 1; 1) v = (2; 2; 2) v = (1; 0; 0)
1 2 3 4
v = (3; 2; 2) v = (0; 0; 0) v = (1; 1; 0) v = (0; 0; 1)
5 6 7 8
v = 0, so we remove it. v is non-zero so it stays. v = 2v so it is removed. v is
1 2 3 2 4
clearly not a linear combination of v , so it stays.
2
We have to decide next whether v is a linear combination of v ; v . If so, then
5 2 4
(3; 2; 2) = (1; 1; 1) + (1; 0; 0), which (fairly obviously) has the solution = 2,
1 2 1
= 1, so remove v . Then v = 0 so that is removed too.
2 5 6
Next we try v = (1; 1; 0) = (1; 1; 1) + (1; 0; 0), and looking at the three compo-
7 1 2
nents, this reduces to the three equations
1 = + ; 1 = ; 0 = :
1 2 1 1
8The second and third of these equations contradict each other, and so there is no solution.
Hence v is not a linear combination of v ; v , and it stays.
7 2 4
Finally, we need to try
v = (0; 0; 1) = (1; 1; 1) + (1; 0; 0) + (1; 1; 0)
8 1 2 3
leading to the three equations
0 = + + 0 = + ; 1 =
1 2 3 1 3 1
and solving these in the normal way, we nd a solution = 1; = 0; = 1. Thus
1 2 3
we delete v and we are left with just v ; v ; v .
8 2 4 7
Of course, the vectors that are removed during the sifting process depends very much
on the order of the list of vectors. For example, if v had come at the beginning of the
8
list rather than at the end, then we would have kept it.
The idea of sifting allows us to prove the following theorem, stating that every nite
sequence of vectors which spans a vector space V actually contains a basis for V .
Theorem 3.5. Suppose that the vectors v ;:::; v span the vector spaceV . Then there
1 r
is a subsequence of v ;:::; v which forms a basis of V .
1 r
Proof. We sift the vectors v ;:::; v . The vectors that we remove are linear combina-
1 r
tions of the preceding vectors, and so by Lemma 3.4, the remaining vectors still span
V . After sifting, no vector is zero or a linear combination of the preceding vectors
(or it would have been removed), so by Lemma 3.1, the remaining vectors are linearly
independent. Hence they form a basis of V .
The theorem tells us that any vector space with a nite spanning set is nite-
dimensional, and indeed the spanning set contains a basis. We now prove the dual
result: any linearly independent set is contained in a basis.
Theorem 3.6. Let V be a vector space over K which has a nite spanning set, and
suppose that the vectors v ;:::; v are linearly independent in V . Then we can extend
1 r
the sequence to a basis v ;:::; v of V , where nr.
1 n
Proof. Suppose that w ;:::; w is a spanning set forV . We sift the combined sequence
1 q
v ;:::; v ; w ;:::; w :
1 r 1 q
Since w ;:::; w spanV , the whole sequence spansV . Sifting results in a basis forV as
1 q
in the proof of Theorem 3.5. Since v ;:::; v are linearly independent, none of them can
1 r
be a linear combination of the preceding vectors, and hence none of the v are deleted
i
in the sifting process. Thus the resulting basis contains v ;:::; v .
1 r
4
Example. The vectors v = (1; 2; 0; 2); v = (0; 1; 0; 2) are linearly independent in R .
1 2
4
Let us extend them to a basis ofR . The easiest thing is to append the standard basis
4
ofR , giving the combined list of vectors
v = (1; 2; 0; 2); v = (0; 1; 0; 2); w = (1; 0; 0; 0);
1 2 1
w = (0; 1; 0; 0); w = (0; 0; 1; 0); w = (0; 0; 0; 1);
2 3 4
which we shall sift. We nd that (1; 0; 0; 0) = (1; 2; 0; 2)+ (0; 1; 0; 2) has no solution,
1 2
so w stays. However, w = v v w so w is deleted. It is clear that w is not a
1 2 1 2 1 2 3
linear combination of v ; v ; w , because all of those have a 0 in their third component.
1 2 1
Hence w remains. Now we have four linearly independent vectors, so must have a basis
3
at this stage, and we can stop the sifting early. The resulting basis is
v = (1; 2; 0; 2); v = (0; 1; 0; 2); w = (1; 0; 0; 0); w = (0; 0; 1; 0):
1 2 1 3
We are now ready to prove Theorem 3.3. Since bases of V are both linearly inde-
pendent and span V , the following proposition implies that any two bases contain the
same number of vectors.
9Proposition 3.7 (The exchange lemma). Suppose that vectors v ;:::; v span V and
1 n
that vectors w ;:::; w 2V are linearly independent. Then mn.
1 m
Proof. The idea is to place the w one by one in front of the sequence v ;:::; v , sifting
i 1 n
each time.
Since v ;:::; v span V , w ; v ;:::; v are linearly dependent, so when we sift, at
1 n 1 1 n
least one v is deleted. We then place w in front of the resulting sequence and sift
j 2
again. Then we put w in from of the result, and sift again, and carry on doing this
3
for each w in turn. Since w ;:::; w are linearly independent none of them are ever
i 1 m
deleted. Each time we place a vector in front of a sequence which spans V , and so the
extended sequence is linearly dependent, and hence at least one v gets eliminated each
j
time.
But in total, we append m vectors w , and each time at least one v is eliminated,
i j
so we must have mn.
Corollary 3.8. Let V be a vector space of dimension n over K. Then any n vectors
which span V form a basis of V , and no n 1 vectors can span V .
Proof. After sifting a spanning sequence as in the proof of Theorem 3.5, the remaining
vectors form a basis, so by Theorem 3.3, there must be precisely n = dim(V ) vectors
remaining. The result is now clear.
Corollary 3.9. Let V be a vector space of dimension n over K. Then any n linearly
independent vectors form a basis of V and no n + 1 vectors can be linearly independent.
Proof. By Theorem 3.6 any linearly independent set is contained in a basis but by
Theorem 3.3, there must be precisely n = dim(V ) vectors in the extended set. The
result is now clear.
3.4 Existence of a basis
Although we have studied bases quite carefully in the previous section, we have not
addressed the following fundamental question. LetV be a vector space. Does it contain
a basis?
Theorem 3.5 gives a partial answer that is good for many practical purposes. Let us
formulate it as a corollary.
Corollary 3.10. If a non-trivial vector spaceV is spanned by a nite number of vectors,
then it has a basis.
In fact, if we de ne the idea of an in nite basis carefully, then it can be proved that
any vector space has a basis. That result will not be proved in this course. Its proof,
which necessarily deals with in nite sets, requires a subtle result in axiomatic set theory
called Zorn's lemma.
4 Subspaces
Let V be a vector space over the eld K. Certain subsets of V have the nice property
of being closed under addition and scalar multiplication; that is, adding or taking scalar
multiples of vectors in the subset gives vectors which are again in the subset. We call
such a subset a subspace:
De nition. A subspace of V is a non-empty subset WV such that
(i) W is closed under addition: u; v2W) u + v2W ;
(ii) W is closed under scalar multiplication: v2W; 2K) v2W .
These two conditions can be replaced with a single condition
u; v2W; ; 2K) u + v2W:
A subspace W is itself a vector space over K under the operations of vector ad-
dition and scalar multiplication in V . Notice that all vector space axioms of W hold
automatically. (They are inherited from V .)
102
Example. The subset ofR given by
2
W =f( ; )2R j = 2 g;
that is, the subset consisting of all row vectors whose second entry is twice their rst
2
entry, is a subspace of R . You can check that adding two vectors of this form always
gives another vector of this form; and multiplying a vector of this form by a scalar always
gives another vector of this form.
For any vector spaceV ,V is always a subspace of itself. Subspaces other thanV are
sometimes called proper subspaces. We also always have a subspacef0g consisting of
the zero vector alone. This is called the trivial subspace, and its dimension is 0, because
it has no linearly independent sets of vectors at all.
Intersecting two subspaces gives a third subspace:
Proposition 4.1. If W and W are subspaces of V then so is W \W .
1 2 1 2
Proof. Let u; v2W \W and 2K. Then u + v2W (because W is a subspace)
1 2 1 1
and u + v2W (becauseW is a subspace). Hence u + v2W \W . Similarly, we get
2 2 1 2
v2W \W , so W \W is a subspace of V .
1 2 1 2
Warning It is not necessarily true that W W is a subspace, as the following
1 2
example shows.
2
Example. Let V =R , let W =f( ; 0)j 2Rg and W =f(0; )j 2Rg. Then
1 2
W ;W are subspaces of V , but W W is not a subspace, because (1; 0); (0; 1)2
1 2 1 2
W W , but (1; 0) + (0; 1) = (1; 1)62W W .
1 2 1 2
Note that any subspace of V that contains W and W has to contain all vectors of
1 2
the form u + v for u2W ; v2W . This motivates the following de nition.
1 2
De nition. LetW ;W be subspaces of the vector space V . Then W +W is de ned
1 2 1 2
to be the set of vectors v2 V such that v = w + w for some w 2 W ; w 2 W .
1 2 1 1 2 2
Or, if you prefer, W +W =fw + w j w 2W ; w 2Wg.
1 2 1 2 1 1 2 2
Do not confuse W +W with W W .
1 2 1 2
Proposition 4.2. If W ;W are subspaces of V then so is W +W . In fact, it is the
1 2 1 2
smallest subspace that contains both W and W .
1 2
Proof. Let u; v2 W +W . Then u = u + u for some u 2 W ; u 2 W and
1 2 1 2 1 1 2 2
v = v +v for some v 2W ; v 2W . Then u+v = (u +v )+(u +v )2W +W .
1 2 1 1 2 2 1 1 2 2 1 2
Similarly, if 2K then v = v + v 2W +W . Thus W +W is a subspace of
1 2 1 2 1 2
V .
Any subspace of V that contains both W and W must contain W +W , so it is
1 2 1 2
the smallest such subspace.
Theorem 4.3. Let V be a nite-dimensional vector space, and let W ;W be subspaces
1 2
of V . Then
dim(W +W ) = dim(W ) + dim(W ) dim(W \W ):
1 2 1 2 1 2
Proof. First note that any subspace W of V is nite-dimensional. This follows from
Corollary 3.9, because a largest linearly independent subset of W contains at most
dim(V ) vectors, and such a subset must be a basis of W .
Let dim(W \W ) =r and let e ;:::; e be a basis of W \W . Then e ;:::; e is
1 2 1 r 1 2 1 r
a linearly independent set of vectors, so by Theorem 3.6 it can be extended to a basis
e ;:::; e ,f ;:::; f ofW where dim(W ) =r +s, and it can also be extended to a basis
1 r 1 s 1 1
e ;:::; e ; g ;:::; g of W , where dim(W ) =r +t.
1 r 1 t 2 2
To prove the theorem, we need to show that dim(W +W ) =r +s +t, and to do
1 2
this, we shall show that
e ;:::; e ; f ;:::; f ; g ;:::; g
1 r 1 s 1 t
is a basis of W +W . Certainly they all lie in W +W .
1 2 1 2
11First we show that they span W +W . Any v2W +W is equal to w + w for
1 2 1 2 1 2
some w 2W ; w 2W : So we can write
1 1 2 2
w = e + + e + f + + f
1 1 1 r r 1 1 s s
for some scalars ; 2K, and
i j
w =
e + +
e + g + + g
2 1 1 r r 1 1 t t
for some scalars
; 2K. Then
i j
v = ( +
)e + + ( +
)e + f + + f + g + + g
1 1 1 r r r 1 1 s s 1 1 t t
and so e ;:::; e ; f ;:::; f ; g ;:::; g span W +W .
1 r 1 s 1 t 1 2
Finally we have to show that e ;:::; e ; f ;:::; f ; g ;:::; g are linearly independent.
1 r 1 s 1 t
Suppose that
e + + e + f + + f + g + + g = 0
1 1 r r 1 1 s s 1 1 t t
for some scalars ; ; 2K. Then
i j k
e + + e + f + + f = g g ()
1 1 r r 1 1 s s 1 1 t t
The left-hand side of this equation lies inW and the right-hand side of this equation lies
1
inW . Since the two sides are equal, both must in fact lie in W \W . Since e ;:::; e
2 1 2 1 r
is a basis of W \W , we can write
1 2
g g =
e + +
e
1 1 t t 1 1 r r
for some
2K, and so
i
e + +
e + g + + g = 0:
1 1 r r 1 1 t t
But, e ;:::; e ; g ;:::; g form a basis of W , so they are linearly independent, and
1 r 1 t 2
hence
= 0 for 1 i r and = 0 for 1 i t. But now, from the equation ()
i i
above, we get
e + + e + f + + f = 0:
1 1 r r 1 1 s s
Now e ;:::; e ; f ;:::; f form a basis ofW , so they are linearly independent, and hence
1 r 1 s 1
= 0 for 1ir and = 0 for 1is. Thus e ;:::; e ; f ;:::; f ; g ;:::; g are
i i 1 r 1 s 1 t
linearly independent, which completes the proof that they form a basis of W +W .
1 2
Hence
dim(W +W ) =r +s +t = (r +s) + (r +t) r = dim(W ) + dim(W ) dim(W \W ):
1 2 1 2 1 2
Another way to form subspaces is to take linear combinations of some given vectors:
Proposition 4.4. Let v ;:::; v be vectors in the vector space V . Then the set of all
1 n
linear combinations v + v + + v of v ;:::; v forms a subspace of V .
1 1 2 2 n n 1 n
The proof of this is completely routine and will be omitted. The subspace in this
proposition is known as the subspace spanned by v ;:::; v .
1 n
De nition. Two subspaces W ;W of V are called complementary if W \W =f0g
1 2 1 2
and W +W =V .
1 2
Proposition 4.5. Let W ;W be subspaces of V . Then W ;W are complementary
1 2 1 2
subspaces if and only if each vector in v2 V can be written uniquely as v = w + w
1 2
with w 2W and w 2W .
1 1 2 2
12Proof. Suppose rst that W ;W are complementary subspaces and let v2 V . Then
1 2
W +W =V , so we can nd w 2W and w 2W with v = w + w . If we also had
1 2 1 1 2 2 1 2
0 0 0 0 0 0
v = w + w with w 2W ; w 2W , then we would have w w = w w . The
1 2 1 2
1 2 1 2 1 2
left-hand side lies in W and the right-hand side lies in W , and so both sides (being
1 2
0
equal) must lie in W \W =f0g. Hence both sides are zero, which means w = w
1 2 1
1
0
and w = w , so the expression is unique.
2
2
Conversely, suppose that every v2V can be written uniquely as v = w + w with
1 2
w 2 W and w 2 W . Then certainly W +W = V . If v was a non-zero vector in
1 1 2 2 1 2
W \W , then in fact v would have two distinct expressions as w + w with w 2W
1 2 1 2 1 1
and w 2W , one with w = v; w = 0 and the other with w = 0; w = v. Hence
2 2 1 2 1 2
W \W =f0g, and W and W are complementary.
1 2 1 2
Examples We give some examples of complementary subspaces.
2
1. As in the previous example, letV =R ,W =f( ; 0)j 2Rg andW =f(0; )j
1 2
2Rg. Then W and W are complementary subspaces.
1 2
3
2. Let V =R , W =f( ; 0; 0)j 2Rg and W =f(0; ; )j ; 2Rg. Then W
1 2 1
and W are complementary subspaces.
2
2
3. Let V =R , W =f( ; )j 2Rg and W =f( ; )j 2Rg. Then W and
1 2 1
W are complementary subspaces.
2
5 Linear transformations
When you study sets, the notion of function is extremely important. There is little to
say about a single isolated set, while functions allow you to link di erent sets. Similarly,
in Linear Algebra, a single isolated vector space is not the end of the story. We have to
connect di erent vector spaces by functions. However, a function having little regard to
the vector space operations may be of little value.
5.1 De nition and examples
Often in mathematics, it is as important to study special classes of functions as it is
to study special classes of objects. Often these are functions which preserve certain
properties or structures. For example, continuous functions preserve which points are
close to which other points. In linear algebra, the functions which preserve the vector
space structure are called linear transformations.
De nition. LetU;V be two vector spaces over the same eldK. A linear transforma-
tion or linear map T from U to V is a function T : UV such that
(i) T (u + u ) =T (u ) +T (u ) for all u ; u 2U;
1 2 1 2 1 2
(ii) T ( u) = T (u) for all 2K and u2U.
Notice that the two conditions for linearity are equivalent to a single condition
T ( u + u ) = T (u ) + T (u ) for all u ; u 2U; ; 2K:
1 2 1 2 1 2
First let us state a couple of easy consequences of the de nition:
Lemma 5.1. Let T : UV be a linear map. Then
(i) T (0 ) = 0 ;
U V
(ii) T ( u) = T (u) for all u2U.
Proof. For (i), the de nition of linear map gives
T (0 ) =T (0 + 0 ) =T (0 ) +T (0 );
U U U U U
and thereforeT (0 ) = 0 . For (ii), just put = 1 in the de nition of linear map.
U V
13Examples Many familiar geometrical transformations, such as projections, rotations,
re
ections and magni cations are linear maps, and the rst three examples below are
of this kind. Note, however, that a nontrivial translation is not a linear map, because it
does not satisfy T (0 ) = 0 .
U V
3 2
1. Let U =R ; V =R and de ne T : UV by T (( ; ;
)) = ( ; ). Then T is a
linear map. This type of map is known as a projection, because of the geometrical
interpretation.
z
v
y
0
- T(v)
X
X
X
X
X
X
x
(Note: In future we shall just write T ( ; ;
) instead of T (( ; ;
)).)
2 2
2. Let U = V = R . We interpret v in R as a directed line vector from 0 to v
(see the examples in Section 2), and let T (v) be the vector obtained by rotating
v through an angle anti-clockwise about the origin.
T (v)
v
1
0
It is easy to see geometrically that T (u + u ) = T (u ) +T (u ) and T ( u) =
1 2 1 2
T (u) (because everything is simply rotated about the origin), and so T is a
linear map. By considering the unit vectors, we have T (1; 0) = (cos; sin) and
T (0; 1) = ( sin; cos), and hence
T ( ; ) = T (1; 0) + T (0; 1) = ( cos sin; sin + cos):
(Exercise: Show this directly.)
2
3. Let U = V = R again. Now let T (v) be the vector resulting from re
ecting v
through a line through the origin that makes an angle =2 with the x-axis.
T (v)
7J
J
J
J
v
:
=2 0
This is again a linear map. We nd that T (1; 0) = (cos; sin) and T (0; 1) =
(sin; cos), and so
T ( ; ) = T (1; 0) + T (0; 1) = ( cos + sin; sin cos):
4. LetU =V =Rx, the set of polynomials overR, and letT be di erentiation; i.e.
0
T (p(x)) =p (x) for p2Rx. This is easily seen to be a linear map.
145. Let U = Kx, the set of polynomials over K. Every 2 K gives rise to two
linear maps, shift S : U U; S (f(x)) = f(x ) and evaluation E : U
K; E (f(x)) =f( ).
The next two examples seem dull but are important
6. For any vector space V , we de ne the identity map I : V V by I (v) = v for
V V
all v2V . This is a linear map.
7. For any vector spacesU;V over the eldK, we de ne the zero map 0 : UV
U;V
by 0 (u) = 0 for all u2U. This is also a linear map.
U;V V
One of the most useful properties of linear maps is that, if we know how a linear
map UV acts on a basis of U, then we know how it acts on the whole of U.
Proposition 5.2 (Linear maps are uniquely determined by their action on a basis).
Let U;V be vector spaces over K, let u ;:::; u be a basis of U and let v ;:::; v be
1 n 1 n
any sequence of n vectors in V . Then there is a unique linear map T : U V with
T (u ) = v for 1in.
i i
Proof. Let u2U. Then, since u ;:::; u is a basis ofU, by Proposition 3.2, there exist
1 n
uniquely determined ;:::; 2K with u = u + + u . Hence, if T exists at
1 n 1 1 n n
all, then we must have
T (u) =T ( u + + u ) = v + + v ;
1 1 n n 1 1 n n
and so T is uniquely determined.
On the other hand, it is routine to check that the map T : U V de ned by the
above equation is indeed a linear map, so T does exist and is unique.
5.2 Kernels and images
To any linear map UV , we can associate a subspace of U and a subspace of V .
De nition. Let T : UV be a linear map. The image of T , written as im(T ), is the
set of vectors v2V such that v =T (u) for some u2U.
De nition. The kernel of T , written as ker(T ), is the set of vectors u2 U such that
T (u) = 0 .
V
If you prefer:
im(T ) =fT (u)j u2Ug; ker(T ) =fu2UjT (u) = 0 g:
V
Examples Let us consider the examples 17 above.
2
In example 1, ker(T ) =f(0; 0;
)j
2Rg; and im(T ) =R .
2
In example 2 and 3, ker(T ) =f0g and im(T ) =R .
In example 4, ker(T ) is the set of all constant polynomials (i.e. those of degree 0),
and im(T ) =Rx.
In example 5, ker(S ) =f0g, and im(S ) = Kx, while ker(E ) is the set of all
polynomials divisible by x , and im(E ) =K.
In example 6, ker(I ) =f0g and im(T ) =V .
V
In example 7, ker(0 ) =U and im(0 ) =f0g.
U;V U;V
Proposition 5.3. Let T : UV be a linear map. Then
(i) im(T ) is a subspace of V ;
(ii) ker(T ) is a subspace of U.
15Proof. For i, we must show that im(T ) is closed under addition and scalar multiplication.
Let v ; v 2 im(T ). Then v =T (u ); v =T (u ) for some u ; u 2U. Then
1 2 1 1 2 2 1 2
v + v =T (u ) +T (u ) =T (u + u )2 im(T )
1 2 1 2 1 2
and
v = T (u ) =T ( u )2 im(T );
1 1 1
so im(T ) is a subspace of V .
Let us now prove ii. Similarly,we must show that ker(T ) is closed under addition
and scalar multiplication. Let u ; u 2 ker(T ). Then
1 2
T (u + u ) =T (0 + 0 ) =T (0 ) = 0
1 2 U U U V
and
T ( u ) = T (u ) = 0 = 0 ;
1 1 V V
so u + u ; u 2 ker(T ) and ker(T ) is a subspace of U.
1 2 1
5.3 Rank and nullity
The dimensions of the kernel and image of a linear map contain important information
about it, and are related to each other.
De nition. let T : UV be a linear map.
(i) dim(im(T )) is called the rank of T ;
(ii) dim(ker(T )) is called the nullity of T .
Theorem 5.4 (The rank-nullity theorem). Let U;V be vector spaces over K with U
nite-dimensional, and let T : UV be a linear map. Then
rank(T ) + nullity(T ) = dim(U):
Proof. Since U is nite-dimensional and ker(T ) is a subspace of U, ker(T ) is nite-
dimensional. Let nullity(T ) =s and let e ;:::; e be a basis of ker(T ). By Theorem 3.6,
1 s
we can extend e ;:::; e to a basis e ;:::; e ; f ;:::; f of U. Then dim(U) =s +r, so
1 s 1 s 1 r
to prove the theorem we have to prove that dim(im(T )) =r.
Clearly T (e );:::;T (e );T (f );:::;T (f ) span im(T ), and since
1 s 1 r
T (e ) = =T (e ) = 0
1 s V
this implies that T (f );:::;T (f ) span im(T ). We shall show that T (f );:::;T (f ) are
1 r 1 r
linearly independent.
Suppose that, for some scalars , we have
i
T (f ) + + T (f ) = 0 :
1 1 r r V
ThenT ( f + + f ) = 0 , so f + + f 2 ker(T ). But e ;:::; e is a basis
1 1 r r V 1 1 r r 1 s
of ker(T ), so there exist scalars with
i
f + + f = e + + e =) f + + f e e = 0 :
1 1 r r 1 1 s s 1 1 r r 1 1 s s U
But we know that e ;:::; e ; f ;:::; f form a basis ofU, so they are linearly independent,
1 s 1 r
and hence
= = = = = = 0;
1 r 1 s
and we have proved that T (f );:::;T (f ) are linearly independent.
1 r
Since T (f );:::;T (f ) both span im(T ) and are linearly independent, they form a
1 r
basis of im(U), and hence dim(im(T )) =r, which completes the proof.
16Examples Once again, we consider examples 17 above. Since we only want to deal
with nite-dimensional spaces, we restrict to an (n + 1)-dimensional space Kx in
n
examples 4 and 5, that is, we consider T : Rx Rx , S : Kx Kx ,
n n n n
and E : Kx K correspondingly. Let n = dim(U) = dim(V ) in 5 and 6.
n
Example rank(T ) nullity(T ) dim(U)
1 2 1 3
2 2 0 2
3 2 0 2
4 n 1 n + 1
5 S n + 1 0 n + 1
4 E 1 n n + 1
6 n 0 n
7 0 n n
Corollary 5.5. Let T : UV be a linear map, and suppose that dim(U) = dim(V ) =
n. Then the following properties of T are equivalent:
(i) T is surjective;
(ii) rank(T ) =n;
(iii) nullity(T ) = 0;
(iv) T is injective;
(v) T is bijective;
Proof. That T is surjective means precisely that im(T ) = V , so (i)) (ii). But if
rank(T ) = n, then dim(im(T )) = dim(V ) so (by Corollary 3.9) a basis of im(T ) is a
basis of V , and hence im(T ) =V . Thus (ii), (i).
That (ii), (iii) follows directly from Theorem 5.4.
Now nullity(T ) = 0 means that ker(T ) =f0g so clearly (iv)) (iii). On the other
hand, if ker(T ) =f0g and T (u ) =T (u ) then T (u u ) = 0, so u u 2 ker(T ) =
1 2 1 2 1 2
f0g, which implies u = u andT is injective. Thus (iii), (iv). (In fact, this argument
1 2
shows that (iii), (iv) is true for any linear map T .)
Finally, (v) is equivalent to (i) and (iv), which we have shown are equivalent to each
other.
De nition. If the conditions in the above corollary are met, then T is called a non-
singular linear map. Otherwise,T is called singular. Notice that the terms singular and
non-singular are only used for linear mapsT : UV for whichU andV have the same
dimension.
5.4 Operations on linear maps
We can de ne the operations of addition, scalar multiplication and composition on linear
maps.
Let T : UV and T : UV be two linear maps, and let 2K be a scalar.
1 2
De nition (Addition of linear maps). We de ne a map
T +T : UV
1 2
by the rule (T +T )(u) =T (u) +T (u) for u2U.
1 2 1 2
De nition (Scalar multiplication of linear maps). We de ne a map
T : UV
1
by the rule ( T )(u) = T (u) for u2U.
1 1
Now let T : UV and T : V W be two linear maps.
1 2
17De nition (Composition of linear maps). We de ne a map
T T : UW
2 1
by (T T )(u) =T (T (u)) for u2U.
2 1 2 1
2 i+1 i
In particular, we de ne T =TT and T =T T for i 2.
It is routine to check thatT +T , T andT T are themselves all linear maps (but
1 2 1 2 1
you should do it).
Furthermore, for xed vector spaces U and V over K, the operations of addition
and scalar multiplication on the set Hom (U;V ) of all linear maps from U toV makes
K
Hom (U;V ) into a vector space over K.
K
Given a vector space U over a eld K, the vector space U = Hom (U;K) plays a
K
special role. It is often called the dual space or the space of covectors of U. One can
think of coordinates as elements of U . Indeed, let e be a basis ofU. Every x2U can
i
be uniquely written as
x = e +::: e ; 2K:
1 1 n n i
The elements depend on x as well as on a choice of the basis, so for each i one can
i
write the coordinate function
i i
e : UK; e (x) = :
i
i i
It is routine to check that e is a linear map, and indeed the functions e form a basis
of the dual space U .
6 Matrices
The material in this section will be familiar to many of you already, at least when K is
the eld of real numbers.
De nition. Let K be a eld and m;n2N. An mn matrix A over K is an mn
rectangular array of numbers (i.e. scalars) in K. The entry in row i and column j is
often written . (We use the corresponding Greek letter.) We writeA = ( ) to make
ij ij
things clear.
For example, we could take
0 1
2 1 0
A
K =R; m = 3; n = 4; A = ( ) = 3 3=2 0 6 ;
ij
10
1:23 0 10 0
10
and then = , = 10 , = 0, and so on.
13 33 34
Having de ned what matrices are, we want to be able add them, multiply them by
scalars, and multiply them by each other. You probably already know how to do this,
but we will de ne these operations anyway.
De nition (Addition of matrices). LetA = ( ) andB = ( ) be twomn matrices
ij ij
over K. We de ne A +B to be the mn matrix C = (
), where
= + for
ij ij ij ij
all i;j.
Example.
1 3 2 3 1 0
+ = :
0 2 1 4 1 2
De nition (Scalar multiplication of matrices). LetA = ( ) be anmn matrix over
ij
K and let 2K be a scalar. We de ne the scalar multiple A to be the mn matrix
C = (
), where
= for all i;j.
ij ij ij
18De nition (Multiplication of matrices). LetA = ( ) be anlm matrix overK and
ij
letB = ( ) be anmn matrix overK. The productAB is anln matrixC = (
)
ij ij
where, for 1il and 1jn,
m
X
= = + + + :
ij ik kj i1 1j i2 2j im mj
k=1
It is essential that the number m of columns of A is equal to the number of rows of B;
otherwise AB makes no sense.
If you are familiar with scalar products of vectors, note also that
is the scalar
ij
product of the ith row of A with the jth column of B.
Example. Let
0 1
2 6
2 3 4
A
A = ; B = 3 2 :
1 6 2
1 9
Then
2 2 + 3 3 + 4 1 2 6 + 3 2 + 4 9 17 54
AB = = ;
1 2 + 6 3 + 2 1 1 6 + 6 2 + 2 9 22 36
0 1
10 42 20
A
8 21 16
BA = :
11 57 22
2 3 1
Let C = . Then AC and CA are not de ned.
6 2 9
1 2 4 15 8
Let D = . Then AD is not de ned, but DA = .
0 1 1 6 2
Proposition 6.1. Matrices satisfy the following laws whenever the sums and products
involved are de ned:
(i) A +B =B +A;
(ii) (A +B)C =AC +BC;
(iii) C(A +B) =CA +CB;
(iv) (A)B =(AB) =A(B);
(v) (AB)C =A(BC).
Proof. These are all routine checks that the entries of the left-hand sides are equal to
the corresponding entries on the right-hand side. Let us do (v) as an example.
LetA,B andC belm,mn andnp matrices, respectively. ThenAB =D = ( )
ij
P
m
is anln matrix with = , andBC =E = (" ) is anmp matrix with
ij is sj ij
s=1
P
n
" =
. Then (AB)C =DC and A(BC) =AE are both lp matrices, and
ij it tj
t=1
we have to show that their coecients are equal. The (i;j)-coecient of DC is
n n m m n m
X XX X X X
= ( )
= (
) = "
it tj is st tj is st tj is sj
t=1 t=1 s=1 s=1 t=1 s=1
which is the (i;j)-coecient of AE. Hence (AB)C =A(BC).
There are some useful matrices to which we give names.
De nition. Themn zero matrix 0 over any eldK has all of its entries equal to
mn
0.
De nition. The nn identity matrix I = ( ) over any eld K has = 1 for
n ij ii
1in, but = 0 when i6=j.
ij
19Example.
0 1
1 0 0
1 0
A
I = (1); I = ; I = 0 1 0 :
1 2 3
0 1
0 0 1
Note that I A =A for any nm matrix A and AI =A for any mn matrix A.
n n
m;n m;n
The set of all mn matrices over K will be denoted by K . Note that K is
itself a vector space over K using the operations of addition and scalar multiplication
de ned above, and it has dimension mn. (This should be obvious is it?)
1;n n
A 1n matrix is called a row vector. We will regardK as being the same asK .
n;1
A n 1 matrix is called a column vector. We will denote the the space K of all
n;1 n;1 n
column vectors by K . In matrix calculations, we will use K more often than K .
7 Linear transformations and matrices
We shall see in this section that, for xed choice of bases, there is a very natural one-one
correspondence between linear maps and matrices, such that the operations on linear
maps and matrices de ned in Chapters 5 and 6 also correspond to each other. This
is perhaps the most important idea in linear algebra, because it enables us to deduce
properties of matrices from those of linear maps, and vice-versa. It also explains why
we multiply matrices in the way we do.
7.1 Setting up the correspondence
Let T : UV be a linear map, where dim(U) =n; dim(V ) =m. Suppose that we are
given a basis e ;:::; e of U and a basis f ;:::; f of V .
1 n 1 m
Now, for 1jn, the vector T (e ) lies in V , so T (e ) can be written uniquely as
j j
a linear combination of f ;:::; f . Let
1 m
T (e ) = f + f + + f
1 11 1 21 2 m1 m
T (e ) = f + f + + f
2 12 1 22 2 m2 m
T (e ) = f + f + + f
n 1n 1 2n 2 mn m
where the coecients 2 K (for 1 i m; 1 j n) are uniquely determined.
ij
Putting it more compactly, we de ne scalars by
ij
m
X
T (e ) = f for 1jn:
j ij i
i=1
The coecients form an mn matrix
ij
0 1
11 12 1n
B C
21 22 2n
B C
A =
B C
. . .
.
. . . .
A
.
. . .
m1 m2 mn
over K. Then A is called the matrix of the linear map T with respect to the chosen
bases ofU andV . In general, di erent choice of bases gives di erent matrices. We shall
address this issue later in the course, in Section 11.
Notice the role of individual columns in A The jth column of A consists of the
coordinates of T (e ) with respect to the basis vf ;:::; f of V .
j 1 m
Theorem 7.1. LetU;V be vector spaces overK of dimensionsn;m, respectively. Then,
for a given choice of bases of U and V , there is a one-one correspondence between the
m;n
set Hom (U;V ) of linear maps UV and the set K of mn matrices over K.
K
20
Advise:Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.
