International College of Economics and Finance

LECTURE NOTES
IN
LINEAR ALGEBRA

0 1
↵11 12 13 14 "15
B ⇣21 ⌘22 ✓23 ◆24 25 C
B C
B 31 µ32 ⌫33 ⇠34 o35 C
B C
@ ⇡41 ⇢42 43 ⌧44 45
A
'51 52 53 !54 ,

ICEF MOSCOW 2011

CONTENTS CONTENTS

Contents
Preface 5

1 Systems of linear equations 7

1.1 A few introductory examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Transformations of matrix rows . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3 Gauss elimination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4 Geometric interpretation of SLE . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2 Linear vector space 13

2.1 Cartesian product of sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Linear vector space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3 Linear independence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.4 Linear hull and bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.5 Dimension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3 Fundamental set of solutions 21

3.1 Homogeneity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2 Rank of a matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.3 Fundamental set of solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

4 The determinant and its applications 26

4.1 Special cases 2⇥2 and 3⇥3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.2 Properties of the determinant . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.3 Formal definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.4 Laplace’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.5 Minors and ranks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.6 Cramer’s rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

5 Matrix algebra 35
5.1 Matrix operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.2 Inverse matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5.3 Inverse matrix by Gauss elimination . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.4 Inverse matrix by algebraic complements . . . . . . . . . . . . . . . . . . . . . . 40
5.5 Matrix equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
5.6 Elementary transformations matrices . . . . . . . . . . . . . . . . . . . . . . . . 43
5.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

3
CONTENTS CONTENTS

6 Linear operators 48
6.1 Matrix of a linear operator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
6.2 Change of base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
6.3 Eigenvectors and eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
6.4 Diagonalizable matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
6.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

7 Quadratic forms 59
7.1 Matrix of a quadratic form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
7.2 Change of base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
7.3 Canonical diagonal form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
7.4 Sylvester’s criterion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
7.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

8 Euclidean vector spaces 66

8.1 Linear spaces with dot product . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
8.2 Gram-Schmidt orthogonalization . . . . . . . . . . . . . . . . . . . . . . . . . . 68
8.3 Projection of a vector on a linear subspace . . . . . . . . . . . . . . . . . . . . . 70
8.4 Orthogonal complement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
8.5 Intersection and sum of vector spaces . . . . . . . . . . . . . . . . . . . . . . . . 74
8.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

9 Answers to problems 82

10 Sample Midterm Exam I 90

11 Sample Midterm Exam II 95

12 Sample Midterm Exam III 100

13 Sample Final Exam I 105

14 Sample Final Exam II 110

15 Sample Final Exam III 115

Index 119

4
CONTENTS CONTENTS

Preface
This study guide is based on the lecture notes taken by a group of students in my Linear
Algebra class at ICEF in 2009. Several handwritten lecture notes were compiled into one big
piece with the addition of numerical exercises and extended explanation to the parts of lecture
notes that were not explained clearly in the class. Numerical exercises are listed at the end
of each chapter, and their main purpose is to help you master your algebraic skills as well as
achieve enough confidence that you worked out each individual topic well enough. The pieces
missing from the original lecture notes were, in most cases, theorems’ proofs, which I had to
skip mostly due to time constraints, and which are now included here. They are still essential
for students who are used to study mathematics with proofs. Additionally, I included six full-
length practice exams (three midterm exams and three final exams) to give you an idea of what
will be in the the end of the course and also to help you get prepared and pass these important
academic checkpoints.
It is very important for you to keep in mind that this study guide is not a replacement for
the attendance of lectures and seminars, but rather a manual containing a detailed inventory
of all class topics, which you can use in case if you missed something in the class or simply
if you need an extra piece of explanation to the topic. This manual was not designed to be
a textbook, and you should not use it as a textbook. But you can use it as lecture notes (in
its original sense) and you can also take advantage of the additional problems to check your
performance. Each chapter contains a number of “typical” problems which occur frequently in
exams. These problems are discussed in detail in examples, which are followed by a plenty of
exercises. I strongly recommended that every student go through these exercises before each
exam.
Some students complained on the technical nature of problems in this study guide and on
the lack of economically-oriented examples. Here I have to remind that the class of Linear
Algebra was designed to be an instrumental complement to the other quantitative subjects
studied at ICEF. In this light, and also taking into account the very strict time frame we have
for teaching this class, obtaining numerical proficiency becomes our first priority, at least for the
range of topics we discuss here. Since we teach you very basic matrix techniques, the numerical
details of these techniques is what actually matters, and that’s why we ask you to work without
any aid of computers at home and on exams, and that’s why it becomes very technical. As to
economic applications and examples, the most of them are related to optimization problems
and differential equations, which are the objectives of study in other classes, ones which the
class of Linear Algebra is complementing. I thus refer you to the other quantitative subjects

5
CONTENTS CONTENTS

since they have better opportunity to provide you with entertaining and relevant economic
examples.
I would like to acknowledge the efforts of all students who took lecture notes, helped me
to typeset this study guide in LATEX, and participated in hunting for typos. I decided not to
publish the list of names here because it either has to be too long to include everyone, or be
unfair. Once again, I thank everyone who contributed to this manual and hope that ICEF
readership will appreciate our work. However, even after extensive checks, some typos might
be skip our collective attention, and I encourage you to send your comments, suggestions, or
simply questions to the lecturer of the class by email.

D.D. Pervouchine

December 4, 2011

6
 1 SYSTEMS OF LINEAR EQUATIONS

1 Systems of linear equations

1.1 A few introductory examples
Many problems in mathematics stem from the technique for solving systems of simultaneous
linear equations. This technique, called Gauss elimination, is one of the most frequently used
methods in Linear Algebra.

Example 1.1. Find the set of solutions to the following system of linear equations
⇢
2x + y = 3
.
x + 3y = 4

Solution. By expressing x from the first equation and substituting into the second equation,
we get
x = 4 3y
2(4 3y) + y = 3
8 6y 6=3
y = 1, x = 1.
Essentially, we solved this problem by using equivalent transformations of linear equations.

Example 1.2. Solve the following system of linear equations.

8
< x + 2y + 3z = 6
2x + y + z = 4
:
x y+z =1

Solution. Again, we express x and substitute into the second and the third equation.

x=6 2y 3z,
⇢
2(6 2y 3z) + y + z = 4
,
6 2y 3z y + z = 1
⇢
12 3y 5z = 4
,
6 3y 2z = 1
⇢
3y + 5z = 8
,
3y + 2z = 5
3z = 3, z = 1, x = 1, y = 1.

7
1.2 Transformations of matrix rows 1 SYSTEMS OF LINEAR EQUATIONS

One could notice that all these operations apply only to the coefficients at x, y, and z. We
thus can save some paper and ink by writing the system of the linear equations (SLE) in the
following extended matrix form 0 1
1 2 3 6
@ 2 1 1 4 A,
1 1 1 1
in which the coefficients at x, y, and z form a square table, with the free terms being attached
to the right after a vertical bar.
In principle, matrices are rectangular tables of numbers. From now on, we reserve the
capital Latin letters (typically, from the beginning of the alphabet) to be matrix names, such
as 0 1
a11 a12 . . . a1n
B a21 a22 . . . a2n C
B C
A = B .. .. .. .. C ,
@ . . . . A
am1 am2 . . . amn
while the corresponding small letters denote matrix elements. The same notation is abbreviated
by A = (aij ), where i and j are running indices which denote the position of the element aij in
the matrix (i and j are not equal to any number). The element aij is located in the intersection
of the ith row and the j th column.

1.2 Transformations of matrix rows

In what follows we will use the following types of transformations which are applied to matrix
rows.

I. The j th row is multiplied by some constant c and added to the ith row.

II. The ith row is multiplied by a non-zero constant c.

III. The ith row and the j th row are interchanged.

Type I transformations will be denoted by the expression [i] 7! [i] + [j] ⇥ c. For instance,
[2] 7! [2] [1] ⇥ 2 means that the first row, multiplied by 2, is subtracted from the second
row1 . Note that in every Type I transformation only the ith row is affected, while the j th row
is unchanged. For instance, in [2] 7! [2] [1] ⇥ 2, the first row stays unchanged.
Type II transformations will be denoted by [i] 7! [i] ⇥ c. For instance, [2] 7! [2] ⇥ ( 1)
means that the second row is multiplied by 1. Multiplication of a row by a constant means
that every element of that row is multiplied by the constant.
Similarly, Type III transformations are denoted by [i] $ [j]. The three types of transfor-
mations and their application to systems of linear equations will be exemplified further in the
next section.
1
Recall that the addition or subtraction of two rows means that their components sum up subtract at the
respective positions.

8
1.3 Gauss elimination 1 SYSTEMS OF LINEAR EQUATIONS

1.3 Gauss elimination

The Gauss elimination algorithm is used very frequently for solving systems of linear equations
and other related problems. The strategy of Gauss elimination is to create zeroes under the
matrix’s main diagonal2 , thereby transforming the matrix into so called upper-triangular form.
The elements below the diagonal of an upper-triangular matrix must be equal to zero. Similarly,
all elements above the diagonal of a lower-triangular matrix must be equal to zero. The matrix
which is both upper-triangular and lower-triangular is called diagonal matrix. All elements
outside of the diagonal of a diagonal matrix are equal to zero. The n⇥n diagonal matrix
with the numbers 1 , . . . , n on the diagonal will be denoted by diag( 1 , . . . , n ). The upper-
triangular matrix is transformed further to obtain the vector of solutions, as will be shown
below.
The essential steps of Gauss elimination are illustrated by the following examples. Note
that the elementary transformations described in section 1.2 do not change the set of solutions
to the system of linear equations and, thus, create equivalent system of equations at each step.

Example 1.3. Solve the following system of linear equations (same as in example 1.2)
8
< x + 2y + 3z = 6
2x + y + z = 4 .
:
x y+z =1

Solution. 0 1 0 1
1 2 3 6 1 2 3 6
[2]7![2] [1]⇤2 [2]7![2]⇤( 1)
@ 2 1 1 4 A ! @ 0 3 5 8 A !
1 1 1 1 1 1 1 1
0 1 0 1
1 2 3 6 1 2 3 6
[3]7![3] [1] [3]7![3]+[2]
@ 0 3 5 8 A ! @ 0 3 5 8 A !
1 1 1 1 0 3 2 5
0 1 0 1
1 2 3 6 1 2 3 6
[3]7![3]/3 [1]7![1] [3]⇤3
@ 0 3 5 8 A ! @ 0 3 5 8 A !
0 0 3 3 0 0 1 1
0 1 0 1
1 2 0 3 1 2 0 3
[2]7![2] [3]⇤5 [2]7![2]/3
@ 0 3 5 8 A ! @ 0 3 0 3 A !
0 0 1 1 0 0 1 1
0 1 0 1
1 2 0 3 1 0 0 1
@ 0 1 0 1 A [1]7![1] [2]⇤2 !@ 0 1 0 1 A.
0 0 1 1 0 0 1 1

2
The main diagonal of a matrix goes south-east from the upper left corner.

9
1.3 Gauss elimination 1 SYSTEMS OF LINEAR EQUATIONS

That is, the strategy of Gauss elimination is the following.

• Look at the first column and, if necessary, use a type III transformation to make the
left-upper-corner element be non-zero. This non-zero element will be called leading or
pivot element. Proceed to the second column if all elements of the first column are equal
to zero.

• For each of the rows below the row containing the leading element, use type I transfor-
mations with suitable constants to make all elements below the pivot element be equal
to zero.

• Proceed to the second column and, if necessary, use a type III transformation to make
the element in the position (2, 2) be non-zero. It will now be next pivot element. If all
the elements of the second column below the pivot element are equal to zero, proceed to
the next column.

• Repeat these steps with other columns until the matrix is in the upper-triangular form.

When transformed to the upper-triangular form, the matrix of a system of linear equations
does not immediately give you the set of solutions. For that we need backward steps of Gauss
elimination, which can be applied to the matrix with non-zero elements of the diagonal.

• Since we assumed that all the elements on the diagonal are non-zero, the element in the
position (n, n) is also non-zero. Therefore, a type II transformation can make it equal to
one. Then, we can apply type I transformations with suitable ’s to make all elements
above the pivot element be equal to zero.

• Similarly, we can make all the elements outside of the diagonal be equal to zero, and
all elements on the diagonal be equal to one. Then, the set of solutions appears in the
column of free terms. Note that this strategy works only when all the diagonal elements
after the forward Gauss elimination were non-zero.

The following example shows that the pivot element does not have to be always equal to one,
although it is very convenient not to deal with fractions in Gauss elimination.

Example 1.4. Solve the following system of linear equations

8
< 2x + 3y + z = 3
3x y + 2z = 5 .
:
2x + 2y + z = 3

Solution. 0 1 0 1
2 3 1 3 [2]7![2] [1]⇤ 32
2 3 1 3
[3]7![3] [1]
@ 3 1 2 5 A ! @ 0 11 1 1 A !
2 2 2
2 2 1 3 2 2 1 3

10
1.4 Geometric interpretation of SLE 1 SYSTEMS OF LINEAR EQUATIONS

0 1 0 1
2 3 1 3 2 3 1 3
[2]$[3] [2]7![2]⇤( 1)
@ 0 11 1 1 A !@ 0 1 0 0 A !
2 2 2
11 1 1
0 1 0 0 0 2 2 2
0 1 0 1
2 3 1 3 2 3 1 3
[3]7![3]+[2]⇤ 11 [37![3]⇤2
@ 0 1 0 0 A !@ 0 1 0 0 A
2
!
11 1 1 1 1
0 2 2 2
0 0 2 2
0 1 0 1
2 3 1 3 2 3 0 2
[1]7![1] [3] [1]7![1] [2]⇤3
@ 0 1 0 0 A !@ 0 1 0 0 A !
0 0 1 1 0 0 1 1
0 1 0 1
2 0 0 2 1 0 0 1
[1]7![1]/2
@ 0 1 0 0 A ! @ 0 1 0 0 A.
0 0 1 1 0 0 1 1

1.4 Geometric interpretation of SLE

The geometry standing behind the systems of linear equations is very simple and natural.
Consider the system in example 1.1. The first equation, 2x + y = 3, defines a line in xy-plane.
The second equation, x + 3y = 4, defines another line. The set of solutions to the SLE is the
set of points in xy-plane satisfying both equations, i.e., the intersection of the two lines. In
principle, there are three options in the mutual positioning of two lines: intersecting (generic
case), parallel, or coinciding. Thus a SLE with two variables may have either one, or zero,
or infinitely many solutions. Similarly, the set of solutions to the SLE with three variables
shown in example 1.3 is the intersection of three planes in 3-D space. The generic case is again
when three planes intersect by one point (the intersection of two planes is a line, and that line
intersects the third plane at one point), but there are cases with infinitely many solutions (the
three planes have a common line or coincide) or no solutions (parallel planes or lines). Some
of these arrangements are shown in Figure 1.
Repeating the same argument for arbitrary number of variables (or reasoning by induction),
we arrive to the following conclusion.

Theorem 1. A system of linear equations can have either no solutions, or just one solution,
or infinite number of solutions.

The proof of this statement is not very difficult. However, we will need to introduce the
notion of a linear vector space to talk more generally about the set of solutions to an arbitrary
system of linear equations. We will do it in the next section.
In both example 1.3 and example 1.4 we dealt with SLE with the unique solution, and thus
the final matrix of such SLE was diagonal. This is not true for degenerate systems (i.e., with
no or infinitely many solutions). However, Gauss elimination is also applicable to degenerate
systems.

11
1.5 Exercises 1 SYSTEMS OF LINEAR EQUATIONS

(a) 1 solutions (b) only 1 solution

(c) no solutions (d) also no solutions

Figure 1: The intersection of three planes in 3D may consist of zero, one, or infinitely many
points.

Example 1.5. Solve the following system of linear equations

⇢
2x + 3y + z = 3
.
2x + 3y + 2z = 6

Solution.
✓ ◆ ✓ ◆ ✓ ◆
2 3 1 3 [2]7![2] [1] 2 3 1 3 [1]7![1] [2] 2 3 0 0
! ! .
2 3 2 6 0 0 1 3 0 0 1 3

We have x3 = 3 and x1 = 3
x.
2 2
Here x2 can be considered as a parameter, and x1 can be
found when x2 is known.

Note that at the second step the matrix is also upper-triangular, but this time one “step” of
the “ladder” is longer than in the former examples. This type of representation, in which the
first non-zero element of each row appears to the right and down of the first non-zero element
of the previous row, is called matrix’s echelon form.

1.5 Exercises
Problem 1.1. Solve the following systems of linear equations.

12
 2 LINEAR VECTOR SPACE

8 8
>
> 3x1 + 3x3 = 3 >
> 5x1 2x2 + 4x3 + 3x4 = 14
< <
x1 + 2x2 + 2x4 = 8 3x1 4x2 4x3 = 10
(a) (b)
>
> 2x2 + 2x3 2x4 = 8 >
> 5x1 + 4x2 + 4x3 4x4 = 18
: :
8 2x1 + 4x2 2x3 + 2x4 = 0 2x2 + 3x3 + x4 = 1
> 4x1 x2 + 2x3 3x4 x5 = 10 8
>
> > 4x1 + 3x2 4x3 + 3x4 = 3
>
< x2 + 2x3 3x4 + x5 = 10 >
<
4x1 3x2 + 3x4 = 21
(c) 2x1 5x2 + 2x3 4x4 + 2x5 = 14 (d)
>
> >
> x1 + 2x2 + 4x3 + 3x4 = 1
>
> 3x 1 + 4x2 + 2x3 x4 + 4x5 = 16 :
: 5x1 4x2 x3 + 4x4 = 28
8 x1 + 4x2 5x3 x4 4x5 = 13 8
>
> 3x1 5x2 + 3x3 + 4x4 = 27 >
> 3x1 + 3x3 x4 = 3
< <
4x1 3x2 2x3 3x4 = 0 3x1 2x2 2x3 + 4x4 = 20
(e) (f)
>
> 4x1 4x2 + 3x4 = 18 >
> 4x1 + 4x2 + 2x3 + 3x4 = 25
: :
8 x1 3x4 = 7 8 4x1 + 2x2 4x3 x4 = 39
>
> x1 2x2 + 2x3 5x4 = 4 >
> 3x1 + 11x2 + 7x3 9x4 = 1
< <
9x1 + 2x2 10x3 6x4 = 10 12x1 + 10x2 x3 + 4x4 = 8
(g) (h)
>
> 3x1 + 5x2 3x3 + 3x4 = 11 >
> 12x1 + 3x2 x4 = 3
: :
8 11x1 + 5x2 + 10x4 = 0 84x1 + 2x2 + x3 + 2x4 = 10
>
> 5x1 + 10x2 + 11x3 + 9x4 = 10 >
> x1 + 12x3 2x4 = 1
< <
5x1 4x2 + 12x3 + 6x4 = 3 5x1 8x2 + 10x3 + x4 = 8
(i) (j)
>
> 3x1 + 5x2 3x3 + 3x4 = 6 >
> x1 4x2 4x3 + 10x4 = 1
: :
6x1 + 3x2 5x3 + 5x4 = 7 10x1 8x2 8x3 x4 = 5

2 Linear vector space

2.1 Cartesian product of sets
Let A and B be two sets (not necessarily sets of numbers). We define the union A [ B,
intersection A \ B, difference A\B, and symmetric difference A4B of A and B to be

A [ B = {x | x 2 A or x 2 B},

A \ B = {x | x 2 A and x 2 B},
A\B = {x | x 2 A and x 2
/ B},
A4B = (A\B) [ (B\A).
Additionally, we define another operation on elementary sets called Cartesian product, which
describes the set that is composed of all ordered pairs of elements of A and B:

A ⇥ B = {(x, y) | x 2 A, y 2 B}.

For instance, if A = B = [0, 1] then A ⇥ B can be thought of as a square in xy-plane formed

by the pairs (x, y) such that 0  x, y  1. If A = R and B = [0, 1] then A ⇥ B is a horizontal
stripe of width 1 in y-direction. If A = R and B = Z then A ⇥ B is a grid of horizontal lines
crossing y-axis at every integer number. Following this definition, the set formed by n-tuples

13
2.2 Linear vector space 2 LINEAR VECTOR SPACE

of real numbers, {(x1 , . . . , xn ) | 8i : xi 2 R}, is exactly the same set as Rn = R ⇥ · · · ⇥ R.

Previously, we did not define functions assuming that a function is a “genuine” object which
doesn’t need a definition. In fact, one can use Cartesian product to give a rigorous definition
of a function. This is achieved in two steps.
First, let us assume we are given two sets, X and Y , called the domain set and the image
set, respectively. We define a relation F on X and Y to be a generic subset of X ⇥ Y . For
instance, the set B2 (1) = {(x, y) | x2 + y 2  1}, which corresponds to a circle on the plane,
can be considered to be a relation. However, it differs from our conventional understanding of
a function because for each given x such that (x, y) 2 F , y can take more than one value. Now
we will define a function or, more generally, a mapping3 , to be a relation F on X and Y such
that (x, y1 ) 2 F and (x, y2 ) 2 F necessarily implies y1 = y2 . Restricting this construction on
a subset of X, if necessary, we can also assume that for every x 2 X there exists y 2 Y such
that (x, y) 2 F . This fact is denoted by F : X ! Y , which spells as “the function F maps the
set X to the set Y ”.
The definition of a function ensures that there is one and only one y for every x such that
(x, y) 2 F . As you know, this y is denoted by y = F (x). It is a link from the formal set-
theoretic construct, which defines a function to be a special class of relations, whereas in our
colloquial understanding a function is the rule, which appoints to every value of x from the
domain one and only one value of y from the image. Functions can be of different nature,
and the same set-theoretic formalism also allows defining functions of several variables. For
instance, a function of two variables, x1 and x2 , both from the set X, and taking values in the
set Y can be thought of as F : X ⇥ X ! Y . We need functions to give a formal definition of a
linear vector space.

2.2 Linear vector space

Definition 1. A vector space over the field of real numbers consists of three objects: (i) a
set V called the ground set, (ii) the mapping f : V ⇥ V ! V , which is a binary operation,
and (iii) the mapping g : R ⇥ V ! V . The mapping f is called addition; the mapping g is
called multiplication by scalars. The mapping f (x, y) is usually denoted by the + sign, i.e.,
f (x, y) = x + y, while x and y could be objects which you don’t normally add to each other (for
instance, students or teachers). Similarly, the mapping g( , x) is often denoted by g( , x) = x,
although it might have nothing to do with the conventional multiplication. The elements of V
will be referred to as vectors although they might not be geometric vectors. The object (V, +, ⇤)
with the attached operations must obey the following axioms.
1. 8x, y 2 V : x + y = y + x
2. 8x, y, z 2 V : (x + y) + z = x + (y + z)
3. 90 2 V : 8x 2 V : x + 0 = 0 + x = x
4. 8x 2 V 9( x) 2 V : x + ( x) = ( x) + x = 0
3
Speaking rigorously, the term “function” means a mapping which takes numeric values, while for general
mappings the image can be any set.

14
2.2 Linear vector space 2 LINEAR VECTOR SPACE

5. 8x, y 2 V, 8 2 R : (x + y) = x + y
6. 8x 2 V, 8 , µ 2 R : (µx) = ( µ)x
The following examples can give you the idea which sets do form linear vector spaces, and
which sets do not.
1. The set R forms a linear vector space with respect to conventional addition of numbers
and multiplication by scalars.
2. The set R2 = {(x, y)} forms a linear vector space with respect to the component-wise
addition and multiplication by scalars, i.e., (x1 , x2 ) + (y1 , y2 ) = (x1 + y1 , x2 + y2 ) and
(x1 , x2 ) = ( x1 , x2 ).
3. Similarly, the set Rn forms a linear vector space with respect to component-wise addition
and multiplication by scalars, i.e., (x1 , . . . , xn )+(y1 , . . . , yn ) = (x1 +y1 , x2 +y2 , . . . , xn +yn )
and (x1 , . . . , xn ) = ( x1 , . . . , xn );
4. The set Pdeg=n of n-th degree polynomials is not a linear vector space because 0 2
/ Pdeg=n .
5. The set Pdegn of all polynomials with the degree not greater than n does form a linear
vector space
6. The set C[a, b] of all continuous functions defined on [a, b] does form a linear vector space
(the sum of continuous functions is again a continuous function).
7. The set C n [a, b] of all real functions on the segment [a, b] which are continuous up to their
n-th derivative (in particular, n could be 1) forms a linear vector space.
Note that in most cases the operation comes logically from the naturally existing addition and
multiplication by scalars, while being or not being a linear vector space depends on whether or
not these operations stay within the same set V , i.e., whether or not f (x, y) still belongs to V .
This motivates the following definition.
Definition 2. Let (V, +, ⇤) the linear vector space. The subset4 U ✓ V is called a subspace
of V if (U, +, ⇤) forms a linear vector space with respect to the operations + and ⇤ that are
inherited from V (by restriction on the smaller domain U ). In other words, U is a subspace of
V if x, y 2 U =) x + y 2 U , x 2 U =) ( x) 2 U , and 2 R, x 2 U =) x 2 U.
Examples of subspaces of linear vector spaces are given below.
1. R ⇢ R2 can be considered as a linear subspace.
2. Pdegn ⇢ C( 1, +1) is a linear subspace.
3. C n+1 [a, b] ⇢ C n [a, b] is a linear subspace.
4. The set B2 (1) defined on page 14 is not a linear subspace of R2 .

4
Please pay attention: U ✓ V means that U is a subset of V , while U ⇢ V means that U is a proper subset
of V , i.e., U ✓ V but U 6= V . Note that the difference is similar to “” and “<”.

15
2.3 Linear independence 2 LINEAR VECTOR SPACE

2.3 Linear independence

In this section we introduce the notion of linear dependence and linear independence, which
are critical to understand the rest of the course.
Definition 3. Let V be a linear vector space over the set of real numbers and let x1 , x2 , . . . , xn
be its vectors. Let also 1 , 2 , . . . , n be a set of real numbers. The expression 1 x1 + 2 x2 +
· · · + n xn is called linear combination of vectors x1 , x2 , . . . , xn with factors 1 , 2 , . . . , n . The
linear combination is called trivial if 1 = 2 = · · · = n = 0.

Definition 4. Let x1 , x2 , . . . , xn be a set of vectors in a linear space V . The set x1 , x2 , . . . , xn

is called linearly dependent if there exist numbers 1 , 2 , . . . , n , not all equal to zero, such that
1 x1 + 2 x2 + · · · + n xn = 0. In other words, the set x1 , x2 , . . . , xn is linearly dependent if
some non-trivial linear combination of x1 , x2 , . . . , xn is equal to zero. The set of vectors that is
not linearly dependent is called linearly independent.

Example 2.1. Consider the following three vectors, x1 = (1, 2, 3), x2 = (0, 1, 2), x3 = (1, 4, 7).
We need to check whether or not they are linearly independent. They are linearly dependent
if there exist numbers 1 , 2 , 3 such that 1 x1 + 2 x2 + 3 x3 = 0. That is, ( 1 , 2 1 , 3 1 ) +
(0, 2 , 2 ) + ( 3 , 4 3 , 7 3 ) = (0, 0, 0). This happens if and only if
8
< 1+ 3=0
2 1+ 2+4 3 =0 .
:
3 1+2 2+7 3 =0
Solving this SLE by Gauss elimination, we get
0 1 0 1
1 0 1 0 1 0 1 0
[2]7![2] [1]⇤2 [3]7![3] [1]⇤3
@ 2 1 4 0 A ! @ 0 1 2 0 A !
3 2 7 0 3 2 7 0
0 1 0 1
1 0 1 0 [3]7![3]⇤ 12
1 0 1 0
[3]7![3] [2]
@ 0 1 2 0 A ! @ 0 1 2 0 A !
0 2 4 0 0 1 2 0
0 1
1 0 1 0
@ 0 1 2 0 A
0 0 0 0
As you can see, the third equation degenerates to the equation 0 = 0, i.e., effectively we
have only two equations. This implies that SLE has infinitely many solutions. Hence, there
exists at least one non-trivial solution. Thus, we conclude that x1 , x2 , x3 is a linearly dependent
set of vectors.
Definition 5. We say that the vector x is expressed linearly through the vectors x1 , x2 , . . . , xn
if x = 1 x1 + 2 x2 + · · · + n xn for some 1 , 2 , . . . , n 2 R. In other words, x is expressed
linearly through x1 , x2 , . . . , xn if x is equal to a linear combination of these vectors.

16
2.4 Linear hull and bases 2 LINEAR VECTOR SPACE

Theorem 2. The set x1 , x2 , . . . , xn is linearly dependent if and only if one of x1 , x2 , . . . , xn is

expressed linearly through the combination of other vectors.

Proof. Assume that xi is expressed linearly through x1 , . . . , xi 1 , xi+1 , . . . , xn . That is, xi =

1 x1 + · · · + i 1 xi 1 + i+1 xi+1 + · · · + n xn . But then it means that 1 x1 + · · · + i 1 xi 1
xi + i+1 xi+1 + · · · + n xn = 0, i.e., at least one non-trivial (the factor at xi is equal to 1)
linear combination of x1 , . . . , xn is equal to zero.
Conversely, let 1 x1 + 2 x2 + · · · + n xn = 0 be a non-trivial linear combination, i.e.,
i 6= 0 for some i. Then ix = 1 x1 + · · · + i 1 xi 1 + i+1 xi+1 + · · · + n xn , and thus
xi = 1i x1 + · · · + i i1 xi 1 + i+1i xi+1 + · · · + ni xn , i.e., xi is expressed linearly through
x1 , . . . , xi 1 , xi+1 , . . . , xn .
Let us comment on the properties of linearly dependent vectors.

1. If the set of vectors x1 , x2 , . . . , xn 1 is linearly dependent, then the set x1 , x2 , . . . , xn 1 , xn

is also linearly dependent.

2. If the set of vectors x1 , x2 , . . . , xn contains a zero vector then it is linearly dependent.

3. If the set of vectors x1 , x2 , . . . , xn is linearly independent, then the set x1 , x2 , . . . , xn 1

also must be linearly independent.

Spend some time with paper and pencil to prove these properties.

2.4 Linear hull and bases

Definition 6. Consider x1 , x2 , . . . , xn , a set of vectors in a linear vector space V . The set
L(x1 , x2 , . . . , xn ) = { 1 x1 + 2 x2 + · · · + n xn | 1 , 2 , . . . , n 2 R} is called the linear hull of
x1 , x2 , . . . , xn . In other words, the linear hull of x1 , x2 , . . . , xn is the set of all their possible
linear combinations.

Definition 7. The set x1 , x2 , . . . , xn of vectors in a linear vector space V is said to generate V

if L(x1 , x2 , . . . , xn ) = V . In other words, x1 , x2 , . . . , xn generates V if every vector of V can be
expressed linearly through x1 , x2 , . . . , xn .

Remark. Note that the notion of linear independence defined in the previous section was not
related to the enveloping vector space, i.e., the property of linear independence of a set of
vectors is their internal business. In contrast, the property to generate V has a lot to do with
the enveloping vector space.

Definition 8. The set x1 , x2 , . . . , xn of vectors of a linear vector space V is said to be a base

in V if it generates V and is linearly independent. Sometimes a base is also called a basis.

Theorem 3. Let the sets x1 , x2 , . . . , xn and y1 , y2 , . . . , ym be two bases in a linear vector space
V . Then n = m.

17
2.4 Linear hull and bases 2 LINEAR VECTOR SPACE

Proof. Assume the contrary, i.e., n 6= m. Without loss of generality, n > m. Then, every vector
x1 , x2 , . . . , xn can be expressed linearly through y1 , y2 , . . . , ym , as y1 , y2 , . . . , ym is a base. That
is,
x1 = c11 y1 + c12 y2 + · · · + c1m ym ,
x2 = c21 y1 + c22 y2 + · · · + c2m ym ,
...
xn = cn1 y1 + cn2 y2 + · · · + cnm ym .
Consider now an arbitrary linear combination of x1 , x2 , . . . , xn that is equal to zero. We get
1 x1 + 2 x2 + · · · + n xn = 1 (c11 y1 + c12 y2 + · · · + c1m ym ) + 2 (c21 y1 + c22 y2 + · · · + c2m ym ) + · · · +
n (cn1 y1 +cn2 y2 +· · ·+cnm ym ) = (c11 1 +c21 2 +· · ·+cn1 n )y1 +(c12 1 +c22 2 +· · ·+cn2 n )y2 +
· · · + (c1m 1 + c2m 2 + · · · + cnm n )ym = 0. This condition is equivalent to the following SLE
8
< c11 1 + c21 2 + . . . + cn1 n = 0
c12 1 + c22 2 + . . . + cn2 n = 0 ,
:
c1m 1 + c2m 2 + . . . + cnm n = 0

which must have at least one non-zero solution since m < n by our supposition. This implies
that x1 , x2 , . . . , xn cannot be linearly independent. Thus m = n.
Corollary 3.1. Let x = 1 x1 + 2 x2 + · · · + n xn = µ1 x1 + µ2 x2 + · · · + µn xn be two linear
decompositions of the same vector x in the base x1 , x2 , . . . , xn . Then 8i : i = µi . That is, the
coefficients of a linear decomposition of a vector x in a given base are defined uniquely. These
coefficients are called the coordinates of the vector x in that base. Note that the coordinates
depend on the order, in which x1 , x2 , . . . , xn are written.
Example 2.2. Find the coordinates of the vector x = (1, 2, 3) in the base e1 = (1, 1, 0),
e2 = (1, 0, 1), and e3 = (0, 1, 1).
Solution. From now on we will follow the notation, in which the components of a vector are
written in columns, not rows. It helps to save space on the page and also makes sense in terms
of the formal framework, in which a row and a column are considered to be a particular case
of rectangular matrix. By definition, we get
0 1 0 1 0 1 0 1 0 1
1 1 1 0 1+ 2
@ 2 A = 1@ 1 A + 2@ 0 A + 3@ 1 A = @ 1 + 3 A.
3 0 1 1 2+ 3

We thus have the following SLE 8

< + 1 2 =1
1+ 3 =2 ,
:
2+ 3 =3
which is solved by Gauss elimination
0 1 0 1 0 1
1 1 0 1 1 1 0 1 1 1 0 1
@ 1 0 1 2 A!@ 0 1 1 1 A ! @ 0 1 1 1 A!
0 1 1 3 0 1 1 3 0 0 1 2

18
2.5 Dimension 2 LINEAR VECTOR SPACE

0 1 0 1
1 1 0 1 1 0 0 0
@ 0 1 0 1 A ! @ 0 1 0 1 A.
0 0 1 2 0 0 1 2
Thus, the coordinates of x in e1 , e2 , e3 are (0, 1, 2). Indeed, x = 0 · e1 + 1 · e2 + 2 · e3 .

Example 2.3. Find the coordinates of the function f (x) = x2 5x+61

considered as a vector in
the respective linear vector space with the base e1 = x 2 and e2 = x 3 .
1 1

Solution.
1 1 2 1 (x 3) + 2 (x 2)
= + = .
x2 5x + 6 x 2 x 3 x2 5x + 6
In order for this to hold, the sum of free terms of the polynomial in the right-hand side of
the equation must be equal to the free term of the polynomial in the right-hand side of the
equation, and the same must hold for the terms containing x. That is,
⇢
1+ 2 = 0
.
3 1 2 2=1

Thus, we have ✓ ◆ ✓ ◆ ✓ ◆
1 1 0 1 1 0 1 0 1
! ! .
3 2 1 0 1 1 0 1 1
Thus, the coordinates of f (x) in e1 , e2 are ( 1, 1).

2.5 Dimension
The notion of dimension also plays a key role in many branches of mathematics. The intuitive
meaning of dimension is that the line is 1-dimensional, the plane is 2-dimensional, the space is
3-dimensional. A bit of generalization takes us to a 4-D space if we agree to include time as
the fourth dimension. The dimensions five and higher are more difficult to imagine. However,
in all cases the quantity standing behind the notion of dimension is the number of independent
directions you can go in your vector space.

Definition 9. The dimension of a vector space V is the number of vectors in its every base
(see theorem 3). The dimension of a vector space V is denoted by dim(V ).

The dimension of a vector space can be either finite or infinite. In this course we deal with
only finite-dimensional spaces. For instance, the set of (not more than) quadratic polynomials
is three-dimensional because it spans over {1, x, x2 }. The dimension of C[a, b], in contrast, is
infinite because the set {1, x, . . . , xn } is linearly independent for an arbitrarily large n.

Theorem 4. Let U and V be finite-dimensional vector spaces such that U ✓ V . Then,

dim(U )  dim(V ) and dim(U ) = dim(V ) if and only if U = V .

19
2.6 Exercises 2 LINEAR VECTOR SPACE

Proof. By theorem 3, if dim(U ) = dim(V ) then every base e1 , e2 , . . . , en of U is also the base
of V . Then, we have U ✓ V and V ✓ U , i.e., U = V . Now consider the case when U ✓ V
and U 6= V . Let e1 , e2 , . . . , en be the base of U . Since V \U 6= ;, there exists at least one
y 2 V \U . At that, e1 , e2 , . . . , en and y is linearly independent because otherwise either y 2 U
or e1 , e2 , . . . , en are linearly dependent. We now get the linear space U1 = L(e1 , e2 , . . . , en , y).
Similarly, if U1 6= V then there exists z 2 V which is not a linear combination of e1 , e2 , . . . , en ,
and y, so we now obtain U2 = L(e1 , e2 , . . . , en , y, z). For some k we will get Uk = V because
dim(V ) is finite and the growing chain of subspaces must end at some point. Thus, the base of
V consists of e1 , e2 , . . . , en and some other vectors, i.e., dim(U ) < dim(V ).
The procedure described in this theorem is known as complementation or completion of
bases. It says that if one vector space is contained in another, then every base of the smaller
vector space can be complemented to be the base of the bigger vector space. Note that it
doesn’t work for infinite-dimensional vector spaces as, for instance, Pdegn ⇢ C( 1, +1), but
their dimensions are both infinite.

2.6 Exercises
Problem 2.1. Determine which of the following sets of vectors are linearly independent. If the
set is linearly dependent, chose a set of base vectors and express the rest of the vectors through
the base chosen.

0 1 0 1 0 1 0 1
2 2 3 4
B 0 C B 3 C B 5 C B 1 C
(a) a1 = B
@
C , a2 = B C, a =B C B C
@ 4 A , a4 = @ 4 A
3 A @ 1 A 3
1 5 1 4
0 1 0 1 0 1 0 1
3 3 1 2
B 0 C B 1 C B 1 C B 0 C
B C B C B C B C
(b) a1 = B
B 4 C , a2 = B
C
B 5 C
C, a3 = B 4 C , a4 = B
B C
B 5 C
C
@ 1 A @ 3 A @ 1 A @ 3 A
1 3 1 4
0 1 0 1 0 1 0 1
3 1 4 1
(c) a1 = @ 4 A , a2 = @ 3 A, a3 = @ 3 A , a4 = @ 1 A
3 4 3 4
0 1 0 1 0 1 0 1 0 1
4 2 3 5 5
B 1C B 1C B C B C B 4C
(d) a1 = B C , a2 = B C , a3 = B 4 C , a4 = B 2 C , a5 = B C.
@ 2A @ 4A @2 A @ 2A @ 2A
4 3 2 3 1

Problem 2.2. Find the coordinates of the vector x in the corresponding bases

20
 3 FUNDAMENTAL SET OF SOLUTIONS

0 1 0 1 0 1 0 1
1 1 1 3
(a) e 1 = @ 2 A, e 2 = @ 1 A, e 3 = @ 2 A, x = @ 5 A
7 1 8 1
0 1 0 1 0 1 0 1
6 9 4 0
(b) e1 = @ 3 A, e2 = @ 4 A, e3 = @ 2 A, x = @ 1 A
4 8 3 4
0 1 0 1 0 1 0 1 0 1
3 5 1 4 7
B4C B C B C B C B C
(c) x=B C, e1 = B 1 C, e2 = B 4 C, e3 = B 2 C, e4 = B 1 C
@6A @2A @ 5A @ 1A @ 6A
5 2 0 1 2
0 1 0 1 0 1 0 1 0 1
6 3 3 7 4
B 2C B C B C B C B C
(d) x=B C, e 1 = B 1 C, e 2 = B 1 C, e 3 = B 2 C, e 4 = B 1 C
@ 1A @4A @ 1A @ 0A @ 2A
1 4 3 5 2
0 1 0 1 0 1 0 1 0 1
1 3 5 3 1
B 2C B5C B 6C B4C B 1C
(e) x=B C B C B C B C B
@ 4 A, e 1 = @ 2 A, e 2 = @ 2 A, e 3 = @ 5 A, e 4 = @ 7 A
C

3 7 7 8 3

3 Fundamental set of solutions

3.1 Homogeneity
We will now give a formal overview of the method for solving arbitrary systems of linear
equations. Consider a system of linear equations with n variables and m equations of the
following general form.
8
>
> a11 x1 + a12 x2 + . . . + a1n xn = b1
>
< a21 x1 + a22 x2 + . . . + a2n xn = b2
.. .. .. .. .. ,
>
> . . . . .
>
: a x + a x + ... + a x = b
m1 1 m2 2 mn n m

which is written in the extended matrix form as

0 1
a11 a12 . . . a1n b1
B a21 a22 . . . a2n b2 C
B C
B .. .. .. .. .. C.
@ . . . . . A
am1 am2 . . . amn bm
Definition 10. A system of linear equations is called homogeneous if b1 = b2 = · · · = bn = 0.
Otherwise, it is called non-homogeneous. Homogeneous and non-homogeneous systems of linear
equations will be abbreviated as HSLE and NHSLE, respectively.

21
3.2 Rank of a matrix 3 FUNDAMENTAL SET OF SOLUTIONS

Theorem 5. The set of solutions to a homogeneous system of linear equations is a linear vector
space.

Proof. Let x = (x1 , . . . , xn ) and y = (y1 , . . . , yn ) be two solutions to a HSLE. Since ai1 (x1 +
y1 ) + · · · + ain (xn + yn ) = (ai1 x1 + · · · + ain xn ) + (ai1 y1 + · · · + ain yn ) = 0 + 0 = 0 for all i, then
x + y is a solution, too. Similarly, x = ( x1 , . . . , xn ) and 0 = (0, . . . , 0) are also solutions
to the same SLE. Therefore, the set of solutions to a homogeneous system of linear equations
forms a linear vector space.
We will sometimes refer to a general solution to the system of linear equations as an expres-
sion describing all possible solutions, as it may have many, while a particular solution refers to
one particularly chosen solution.

Theorem 6. A general solution to NHSLE can be expressed as a particular solution to NHSLE

+ general solution to the respective HSLE.

Proof. This statement follows from the observation that if x = (x1 , . . . , xn ) and y = (y1 , . . . , yn )
are two solutions to the NHSLE, then x y is a solution to the HSLE. Indeed, ai1 (x1
y1 ) + · · · + ain (xn yn ) = (ai1 x1 + · · · + ain xn ) (ai1 y1 + · · · + ain yn ) = bi bi = 0 for all
i. Similarly, if x = (x1 , . . . , xn ) is a solution to NHSLE and y = (y1 , . . . , yn ) is a solution
to HSLE, then x + y is a solution to NHSLE because ai1 (x1 + y1 ) + · · · + ain (xn + yn ) =
(ai1 x1 + · · · + ain xn ) + (ai1 y1 + · · · + ain yn ) = bi + 0 = bi .

3.2 Rank of a matrix

Recall that by theorem 5 in the previous section, the set of solutions to a homogeneous system
of linear equations is a linear vector space. The dimension of this vector space is related to the
dimension of the vector space generated by the rows of the matrix of SLE.

Definition 11. Let A be a m⇥n matrix. The maximum number of linearly independent rows
of A is called the rank of matrix A and is denoted by rk(A).

It follows immediately from this definition and from the Gauss elimination method that the
rank of a matrix is equal to the number of non-zero rows in the matrix echelon form (page 12).

Definition 12. Let A be a m⇥n matrix. The transpose to A is the matrix AT which is obtained
by writing the columns of A as rows or, equivalently, by writing the rows of A as columns. That
is, 0 1 0 1
a11 a12 . . . a1n a11 a21 . . . am1
B a21 a22 . . . a2n C B a12 a22 . . . am2 C
B C B C
.. C , where A = B ..
T
A = B .. .. . . .. . . .. C .
@ . . . . A @ . . . . A
am1 am2 . . . amn a1n a2n . . . amn

It turns out that the maximum number of linearly-independent rows and the maximum
number of linearly-independent columns are the same. That is, rk(A) is independent of trans-
position of rows and columns, i.e., rk(AT ) = rk(A).

22
3.2 Rank of a matrix 3 FUNDAMENTAL SET OF SOLUTIONS

Consider a set of vectors a1 = (a11 , a12 , . . . , a1n ), a2 = (a21 , a22 , . . . , a2n ), am = (am1 , am2 , . . . , amn )
in Rn formed by the rows of matrix A. Then, rk(A) = dimL(a1 , a2 , . . . , am ). The following is
the fundamental theorem about the rank of a matrix, which defines SLE, and the dimension of
the solution space.
Theorem 7. Let V be the linear space of solutions to the HSLE defined by the matrix A. Then,
dim(V ) = n rk(A).
Before we proceed with the proof of the theorem, let us consider the following example.
Example 3.1. Describe the set of solutions of
⇢
x1 + 2x2 + x4 = 0
.
x1 + x2 x3 = 0

Solution. The Gauss elimination

✓ ◆ ✓ ◆ ✓ ◆
1 2 0 1 0 1 1 1 0 0 1 0 2 1 0
! !
1 1 1 0 0 0 1 1 1 0 0 1 1 1 0

brings us to the SLE defined by

⇢
x1 2x3 x4 = 0
.
x2 + x3 + x4 = 0

Note that the variables x3 and x4 are “free”, i.e., they can take any values without restrictions,
while x1 and x2 can be expressed through x3 and x4 as the underlined coefficients are not equal
to zero. We thus can use the following strategy: give to one of the free variables, x3 or x4 ,
the value of 1, and set the other free variables to zero. Then, x1 and x2 can be found from
the matrix of SLE. Namely, the values of x1 and x2 stand in the corresponding column of the
matrix, up to multiplication by -1. This is illustrated by the following schema.

x1 2 1
x2 1 1
.
x3 1 0
x4 0 1

Theorem 7 says that dim(V ) = n rk(A) = 4 2 = 2. On the other hand, the two vectors
found above, e1 = (2, 1, 1, 0) and e2 = (1, 1, 0, 1) are linearly independent by construction.
Therefore, the set of solutions spans on e1 and e2 , i.e., every solution to the original system of
linear equations can be expressed as a linear combination of e1 and e2 , i.e.,
0 1 0 1
2 1
B 1 C B C
x = 1B C + 2B 1 C.
@ 1 A @ 0 A
0 1

23
3.3 Fundamental set of solutions 3 FUNDAMENTAL SET OF SOLUTIONS

Proof of theorem 7. First, note that elementary transformations of rows do not affect the set of
solutions because they give an equivalent SLE’s on each step. It is enough to consider the case
of under-defined system (m < n), as the statement of the theorem is trivial for the defined and
over-defined systems. Essentially, the idea of the proof follows the previous example, where we
used Gauss elimination to transform the matrix A to the form
0 1 0 1
a11 a12 . . . a1m . . . a1n ⇤ ⇤ ... ⇤ ⇤ ... ⇤
B a21 a22 . . . a2m . . . a2n C B 0 ⇤ ... ⇤ ⇤ ... ⇤ C
B C B C
B . . . . .. C ,
C ! B .. .. . . . .. ..
B a31 a32 . . . a3m . . . a3n C
B
B .. . C
.. . . .. .. C B C
@ . . . . . A @ 0 0 ... ⇤ ⇤ ... ⇤ A
am1 am2 . . . amm . . . amn 0 0 ... 0 0 ... 0
if necessary exchanging the order of variables. Then, the dimension of the solution space is
exactly the number of free variables, which is equal to the total number of variables minus the
number of equations in the transformed matrix. The number of variables is equal to n, and the
number of equations in the transformed matrix is equal to rk(A), i.e., dim(V ) = n rk(A).

3.3 Fundamental set of solutions

The technique explained in example 3.1 in the previous section gave rise to an algorithm called
fundamental system of solutions. First, the matrix of a SLE is transformed to the echelon form.
At that, the element of the matrix that were used to create zeros in other rows are called pivoting
elements. The columns which do not contain pivoting elements are declared to correspond to
free variables. Then, one by one, we give the value of 1 to each of the free variables and assign
zero to the rest of the free variables; the dependent variables are calculated from these data.
Taking into account the conclusion of theorem 6, this also allows solving NHSLE, as we show
below.

Example 3.2. Find the fundamental set of solutions to

⇢
x1 + 2x2 + x3 x4 + x5 = 4
.
x1 + x2 x3 + 2x4 x5 = 2

Solution. ✓ ◆ ✓ ◆
1 2 1 1 1 4 1 2 1 1 1 4
! !
1 1 1 2 1 2 0 1 2 3 2 2
✓ ◆
1 0 3 5 3 0
0 1 2 3 2 2
e1 e2 e3 N HSLE
x1 3 5 3 0
x2 2 3 2 2
x3 1 0 0 0
x4 0 1 0 0
x5 0 0 1 0

24
3.4 Exercises 3 FUNDAMENTAL SET OF SOLUTIONS

First, we set x3 = 1, x4 = 0, and x5 = 0, and compute x1 and x2 . The values for x1 and x2 are
opposite to the numbers in the third column of the transformed matrix. Then, we set x3 = 0,
x4 = 1, and x5 = 0, and compute x1 and x2 again. This time, x1 and x2 are the numbers that
are opposite to those in the fourth column. When we need a particular solution to NHSLE,
we can set x3 = 0, x4 = 0, and x5 = 0 and compute x1 and x2 again, this time by using the
numbers to the right of the bar. Finally,
0 1 0 1 0 1 0 1
3 5 3 0
B 2 C B 3 C B 2 C B 2 C
B C B C B C B C
x = 1B C B C B
B 1 C + 2B 0 C + 3B 0 C + B 0 C.
C B C
@ 0 A @ 1 A @ 0 A @ 0 A
0 0 1 0
.

3.4 Exercises
Problem 3.1. Find ranks of the following matrices
0 1 0 1
4 8 4 16 8 2 10 10 2 4
B 1 2 1 4 2 C B 2 10 10 2 4 C
(a)B
@ 3
C (b)B C
6 3 12 6 A @ 1 5 5 1 2 A
2 4 2 8 4 2 10 10 2 4
0 1 0 1
9 10 16 11 3 12 2 3 12 2
B 9 8 8 7 1 C B 12 8 3 12 4 C
(c)B
@ 22
C (d)B C
18 20 15 11 A @ 20 0 3 20 4 A
4 3 1 12 10 12 12 9 12 0
0 1 0 1
4 8 4 16 12 0 1 3 1 4
B 4 8 4 16 12 C B 16 16 4 0 8 C
(e)B
@ 3
C (f)B C
6 3 12 9 A @ 16 13 13 3 4 A
3 6 3 12 9 8 6 8 2 4
0 1 0 1
14 14 4 22 14 3 3 9 15 9
B 8 16 20 4 8 C B 3 3 9 15 9 C
(g)B
@ 0
C (h)B C
14 13 5 0 A @ 5 5 15 25 15 A
6 16 11 13 6 2 2 6 10 6
0 1 0 1
5 2 4 4 4 10 14 2 6 4
B 12 9 16 8 14 C B 19 11 5 21 4 C
(i)B
@ 1
C (j)B C
8 12 4 8 A @ 15 8 4 17 3 A
9 12 20 4 16 13 13 3 11 4

Problem 3.2. Find the fundamental system of solutions to the following systems of linear
equations
⇢
x1 x2 + 5x3 13x4 = 3
(a)
x1 + x2 x3 + x4 = 3

25
 4 THE DETERMINANT AND ITS APPLICATIONS

⇢
3x1 5x2 3x3 + 13x4 = 10
(b)
2x1 x2 + 5x3 + 4x4 = 5
⇢
2x1 x2 2x3 5x4 = 7
(c)
2x1 + x2 6x3 + x4 = 1
8
< 3x1 + x2 + x3 + 6x5 = 6
(d) 2x1 + 3x2 + 2x3 4x4 + 5x5 = 4
:
3x1 + 3x2 + 5x3 + 8x4 16x5 = 6
8
< 2x2 + x3 7x4 4x5 = 7
(e) x1 + 2x2 x3 + x4 2x5 = 7
:
3x1 + 4x2 2x3 4x4 10x5 = 14
8
< x1 6x2 3x3 17x4 17x5 = 1
(f) 5x2 + 7x3 8x4 17x5 = 5
:
3x2 + 5x3 8x4 15x5 = 3
⇢
2x1 + x2 + 9x3 15x4 = 9
(g)
x1 + 2x3 6x4 + x5 = 1
⇢
x1 + x2 + 2x3 + 2x4 2x5 = 0
(h)
x2 + 4x3 + 7x4 5x5 = 2
⇢
3x1 5x2 + 18x3 + x4 3x5 = 2
(i)
x1 + x2 2x3 + 11x4 x5 = 6
⇢
x1 x2 3x3 + 7x5 = 0
(j)
x1 + 2x3 x4 + 7x5 = 1

4 The determinant and its applications

The determinant of a n⇥n matrix A is a value that can be obtained by multiplying certain
sets of entries of A, and adding and subtracting such products, according to the rules that are
discussed below.

4.1 Special cases 2⇥2 and 3⇥3

The determinant det(A) of a 2⇥2 matrix A is defined by

a11 a12
det(A) = = a11 a22 a12 a21 .
a21 a22

The vectors (a11 , a12 ) and (a21 , a22 ) form a parallelogram in the xy-plane with vertices at
(0, 0), (a11 , a12 ), (a21 , a22 ), and (a11 + a21 , a21 + a22 ). The absolute value of a11 a22 a12 a21 is the

26
4.2 Properties of the determinant 4 THE DETERMINANT AND ITS APPLICATIONS

area of the parallelogram. That is, the determinant of a 2⇥2 matrix is somewhat similar to the
area. The absolute value of the determinant together with the sign becomes the oriented area
of the parallelogram. The oriented area is the same as the usual area, except that it changes
its sign when the two vectors forming the parallelogram are interchanged.
The determinant det(A) of a 3⇥3 matrix
0 1
a11 a12 a13
A = @ a21 a22 a23 A
a31 a32 a33

is defined by det(A) = a11 a22 a33 + a12 a23 a31 + a21 a32 a13 a31 a22 a13 a12 a21 a33 a11 a23 a32 .
Similarly to the 2⇥2 case, the geometric interpretation of the determinant is the volume of a
cuboid spanning the vectors (a11 , a12 , a13 ), (a21 , a22 , a23 ), and (a31 , a32 , a33 ). Again, the absolute
value of the determinant together with the sign gives the oriented volume of the cuboid.
The determinant expression grows rapidly with the size of the matrix (an n⇥n matrix
contributes n! terms). In the next section we give the formal expression for det(A) for arbitrary
size matrices, which subsumes these two cases, while for now we list the properties of the
determinant, which actually determine it as a function uniquely, and continue the sequence of
term “length-area-volume” to something that can be called n-dimensional volume.
✓ ◆
1 2
Example 4.1. det =1⇥4 2⇥3=4 6= 2
3 4
0 1
1 2 3
Example 4.2. det @ 4 5 6 A = 1⇥5⇥9+4⇥8⇥3+2⇥6⇥7 7⇥5⇥3 4⇥2⇥9 1⇥8⇥6 =
7 8 9
45 + 96 + 84 105 72 48 = 0

4.2 Properties of the determinant

Recall the three types of transformations we introduced to operate with matrices of linear
equations (page 8). In type I transformation, the j th row is multiplied by some constant c
and added to the ith row. In type II transformation, the ith row is multiplied by a non-zero
constant c. Type III transformation interchanges the ith row and the j th row of the matrix.
The following are the properties of the determinant.

1. det(A) doesn’t change under type I transformations, i.e., the addition of a row (or column),
factored by a number, to another row (or column) doesn’t change det(A).

2. det(A) is multiplied by c under type II transformations, i.e., if a row or column is factored

by a number, then det(A) is multiplied by the same number.

3. det(A) is multiplied by -1 under type III transformations, i.e., det(A) changes sign if two
rows or two columns are interchanged.

27
4.3 Formal definition 4 THE DETERMINANT AND ITS APPLICATIONS

These three properties hold for the area of a parallelogram and for the volume of a cuboid.
They must also hold for higher-dimensional analogs of these measures, and these requirements
define det(A) uniquely up to a constant factor. If we additionally require that det(E) = 1,
where 0 1
1 0 ... 0
B 0 1 ... 0 C
B C
E = B .. .. . . .. C
@ . . . . A
0 0 ... 1
is the n⇥n identity matrix, then with the requirements (1)-(3) above it can be used as a
definition of the determinant.

4.3 Formal definition

We define a permutation (i1 , i2 , . . . , in ) of the set of integer numbers (1, 2, . . . , n) as a mapping
f : (1, 2, . . . , n) ! (1, 2, . . . , n) such that no pair of numbers i and j are mapped to the same
number, i.e., f (i) = f (j) implies i = j. It means that i1 , i2 , . . . , in is the same set of number
as 1, 2, . . . , n, simply written in a different order. For instance, the permutation (2, 3, 1, 4) of
numbers (1, 2, 3, 4) is the mapping f such that f (1) = 2, f (2) = 3, f (3) = 1, and f (4) = 4,
whereas if f (1) = f (2) then f is not a permutation.
Each permutation (i1 , i2 , . . . , in ) contains orders and inversions. For instance, (2, 3, 1, 4)
contains four orders, (2, 3),(2, 4), (3, 4), and (1, 4) and two inversions, (2, 1) and (3, 1). An
inversion happens when a bigger number precedes a smaller number; all other pairs are called
orders. We define the sign of a permutation, (i1 , i2 , . . . , in ) be equal to 1 to the power of the
number of inversions. For instance, (2, 3, 1, 4) = 1 and (2, 1, 3, 4) = 1.
The determinant of an arbitrary n⇥n matrix is defined by
0 1
a11 a12 . . . a1n
B a21 a22 . . . a2n C X
B C
det B .. .. . .. . C
.. A = (i1 , i2 , . . . , in )a1i1 a2i2 . . . anin ,
@ . . (i1 ,i2 ,...,in )
am1 am2 . . . amn

where the sum runs over all possible permutations of the set (1, 2, . . . , n). Clearly, there are
n! = 1 · 2 · · · · · n such permutations and, thus, the general determinant expression contains n!
terms. One can also say that the determinant of a matrix A = (aij ) is the sum of products of
matrix elements such that in every product term one and only one element is taken from each
row and column.

Theorem 8. The determinant of an upper-triangular square matrix is equal to the product of

its diagonal entries.

28
4.4 Laplace’s theorem 4 THE DETERMINANT AND ITS APPLICATIONS

Proof. Let A be an upper-triangular matrix, i.e.,

0 1
a11 a12 a13 . . . a1n
B 0 a22 a23 . . . a2n C
B C
B . . . a3n C
A=B 0 0 a33 C.
B .. .. .. .. .. C
@ . . . . . A
0 0 0 . . . ann
The sum of products of matrix elements such that one and only one element is taken from
each row and column always contains an element located below the diagonal, all of which are
equal to zero, with the exception of the term which is the product of the diagonal entries, i.e.,
a11 a22 . . . ann . This completes the proof.

4.4 Laplace’s theorem

The minor Mi,j of a matrix
0 1
a11 . . . a1 j 1 a1 j a1 j+1 ... a1n
B .. ..
.
.. .. .. .. C
B . . . . . C
B C
B ai 1 1 . . . ai 1 j 1 ai 1 j ai 1 j+1 . . . ai 1 n C
B C
A = B ai1 . . . ai j 1 ai j ai j+1 . . . ai n C
B C
B ai+1 1 . . . ai+1 j 1 ai+1 j ai+1 j+1 . . . ai+1 n C
B . .. .. .. .. .. C
@ .. . . . . . A
an1 . . . an j 1 an j an j+1 . . . ann
is defined to be the determinant of the (n-1)⇥(n-1) matrix that is obtained from A by removing
the ith row and the jth column:
0 1
a11 . . . a1 j 1 a1 j+1 . . . a1n
B .. ... .. .. .. C
B . . . . C
B C
B ai 1 1 . . . ai 1 j 1 ai 1 j+1 . . . ai 1 n C
Mij = det B C
B ai+1 1 . . . ai+1 j 1 ai+1 j+1 . . . ai+1 n C
B . .. .. .. .. C
@ .. . . . . A
an1 . . . an j 1 an j+1 . . . ann
The expression Mij is also known as algebraic complement to aij . Then the determinant of A
is given by the following Laplace’s formula.
Theorem 9.
n
X
det(A) = ( 1)i+j aij Mij (decomposition by the j-th column)
i=1
n
X
det(A) = ( 1)i+j aij Mij (decomposition by the i-th row)
j=1

29
4.5 Minors and ranks 4 THE DETERMINANT AND ITS APPLICATIONS

The Laplace’s theorem gives a useful tool for the calculation of determinants, one in which
the nth order determinant is expressed through lower order minors recursively. Below we go
through examples of these recursive calculations.
1 0 1 2
2 1 1 1 1 2
2 0 1 1
Example 4.3. = ( 1)1+2 ⇥ 0 ⇥ 1 3 1 + ( 1)2+2 ⇥ 0 ⇥ 1 3 1 +
1 1 3 1
2 1 2 2 1 2
2 0 1 2
1 1 2
( 1)2+3 ⇥ ( 1) ⇥ 2 1 1 + 0 = 2 + 2 + 4 4 1 = 1
2 1 2
This example shows that the Laplace’s formula is most useful for decomposition by a column
or a row which contains many zeros. If there is no such row or column, you may to create it
by using type I transformations as they don’t affect the determinant.
1 1 1 1 1 1 1 1
2 1 1 2 1 0 0 3
Example 4.4. = = 1 ⇥ ( 1)2+1 ⇥
3 1 1 1 3 1 1 1
5 2 1 1 5 2 1 1
1 1 1 1 1 1 1 1 1 1 1 1
2+2 2+3 2+4
⇥ 1 1 1 +0⇥( 1) 3 1 1 +0⇥( 1) 3 1 1 +3⇥( 1) 3 1 1 =
2 1 1 5 1 1 5 2 1 5 2 1
2 + 30 = 28.

4.5 Minors and ranks

The notion of a minor can be used to assess the rank of an arbitrary n⇥m matrix. Consider two
sets of indices, 1  i1  i2  · · ·  ik  n and 1  j1  j2  · · ·  jk  m, and consider the
submatrix of A which consists of the elements located on the intersection of rows i1 , i2 , . . . ik
and j1 , j2 , . . . jk : 0 1
ai1 j1 ai1 j2 . . . ai1 jk
B ai j ai j . . . ai j C
B 21 2 2 2 k C
B .. .. . . .. C .
@ . . . . A
ai k j 1 ai k j 2 . . . a i k j k
Its determinant is called a kth order minor of the matrix A. For instance, if
0 1
1 1 8 1 2
B 0 8 4 5 6 C
A=B @ 6
C,
9 0 6 1 A
2 1 2 3 6
(i1 , i2 , i3 ) = (1, 2, 4), and (j1 , j2 , j3 ) = (2, 3, 5), then the corresponding 3rd order minor is
1 8 2
8 4 6 = 24 48 + 32 + 8 + 6 + 384 + 12 = 418.
1 2 6

30
4.6 Cramer’s rule 4 THE DETERMINANT AND ITS APPLICATIONS

Theorem 10. Let A be a n⇥m matrix. If at least one kth order minor of A is not equal to zero
then rk(A) k. If all kth order minors of A are equal to zero then rk(A) < k.
Example 4.5. 0 1
2 1 0 0 3 7 2
rk @ 1 0 1 0 1 2 1 A =?
3 0 0 1 2 3 1

1 0 0
Solution. The matrix contains the minor 0 1 0 = 1 6= 0. Since the identity matrix has
0 0 1
rank three, the rank of the original matrix is not smaller than three. Hence, it is equal to three.

4.6 Cramer’s rule

Consider the general form of a system of n linear equations with n variables
8
>
> a11 x1 + a12 x2 + . . . + a1n xn = b1
>
< a21 x1 + a22 x2 + . . . + a2n xn = b2
.. .. .. .. ,
>
>
> . . . .
: a x + a x + ... + a x = bn
n1 1 n2 2 nn n
0 1
a11 a12 . . . a1n
B a21 a22 . . . a2n C
B C
and denote = det B .. .. .. .. C ,
@ . . . . A
an1 an2 . . . ann
0 1 0 1
b1 a12 . . . a1n a11 b1 . . . a1n
B b2 a22 . . . a2n C B a21 b2 . . . a2n C
B C B C
1 = det B .. .. . . .. C , 2 = det B .. .. . . .. C , and so on for all
@ . . . . A @ . . . . A
bn an2 . . . ann an1 bn . . . ann
columns, where the b-column replaces the ith column in i .
Theorem 11 (Cramer’s rule). Let (x1 , x2 , . . . , xn ) be a solution to the system of linear equations
given above. If 6= 0 then (x1 , x2 , . . . , xn ) is unique and xi = i for all i.
Example 4.6. Consider the system of linear equations given by
✓ ◆
2 3 5
2 1 1

Solution.
2 3
= = 2 6= 8,
2 1
5 3
1 = = 5 3= 8,
1 1

31
4.6 Cramer’s rule 4 THE DETERMINANT AND ITS APPLICATIONS

2 5
2 = =2 10 = 8,
2 1
8 8
x1 = 1
= 8
= 1, x2 = 2
= 8
= 1.

Example 4.7. Consider the system of linear equations given by

8
< x1 + 2x2 + x3 = 3
x1 x2 + 2x3 = 0
:
3x1 x2 + 7x3 = 2

Solution. 0 1
1 2 1 3
@ 1 1 2 0 A
3 1 7 2
1 2 1
= 1 1 2 = 7 + 12 1+4 14 + 2 = 5,
3 1 7
3 2 1
1 = 0 1 2 = 21 + 8 + 0 + 2 0+6= 11 + 6 = 5,
2 1 7
1 3 1
2 = 1 0 2 = 0 + 18 + 2 0 21 4= 5,
3 2 7
1 2 3
3 = 1 1 0 = 2+0 3+9 4 0 = 0,
3 1 2
1 5
x1 = = = 1,
5
2 5
x2 = = = 1,
5
3 0
x3 = = = 0.
5
An extension of the Cramer’s rule is sometimes used to distinguish between the case of
no solutions and the case of infinitely many solutions when the system of linear equations is
degenerate.
⇢
x1 + x2 = 2
Example 4.8.
x1 + x2 = 3

32
4.6 Cramer’s rule 4 THE DETERMINANT AND ITS APPLICATIONS

Solution. This system of linear equations has no solutions since 2 6= 3. Look what happens
when we apply Cramer’s rule. ✓ ◆
1 1 2
1 1 3
= 0,
2 1
1 = 6= 0.
3 1
This situation corresponds to having two parallel lines, x1 + x2 = 2 and x1 + x2 = 3, which
“intersect” at x = 1, and thus the Cramer’s rule gives 1 / = 1 /0 = 1.
⇢
x1 + x2 = 1
Example 4.9.
2x1 + 2x2 = 2
Solution. This system of linear equations has infinitely many solutions since x1 + x2 = 1 and
2x1 + 2x2 = 2 have the same set of solutions. Then,
✓ ◆
1 1 1
2 2 2

= 0,
1 1
1 = 2 = =0
2 2
Thus, we have infinitely many solutions, as hinted by the formal application of Cramer’s rule,
which gives “x = 0/0”.

Theorem 12 (Kronecker-Capelli). A system of linear equations has a solution if and only if

the rank of the coefficient matrix A is equal to the rank of the extended matrix (A|b).

Proof. Assume that the system of linear equations has at least one solution. It means that b
is expressed as a linear combination of columns of A and, thus, rk(A|b) must be the same as
rk(A) since linear combination doesn’t change the rank. Vice versa, assume that rk(A|b) =
rk(A) = k. It means that the last equation in the echelon form of the extended matrix is
ak xk + ak+1 xk+1 + · · · + an xn = bk . We can set xk+1 = · · · = xn = 0 and use theorem 11 to find
the solution for x1 , . . . , xk as rk(A) = k and the corresponding minor is non-zero.

Corollary 12.1. Consider the notation of theorem 11. If = 0 but i 6= 0 for some i then
the system of linear equations has no solutions.

The connection between the number of solutions to a system of linear equations and the
determinant of the matrix that system leads us to the following important definition

Definition 13. A square n⇥n matrix A is called regular (or non-degenerate) if det(A) 6= 0.
Otherwise, it is called singular (or degenerate).

33
4.7 Exercises 4 THE DETERMINANT AND ITS APPLICATIONS

Out of these four terms, we will preferentially use the term non-degenerate when describing
the properties of matrix determinant. The term itself stems from the property of the system of
linear equations, which degenerates when some its equations become linearly dependent. If you
pick a set of n2 numbers at random and put them into a square table, in “most cases” (that is,
with probability 1) it will give a non-degenerate matrix because a set of 3D planes in general
position intersects by one point, but “sometimes” (with probability 0) it will become special,
i.e. singular, and give many or no solutions. This explains the other pair of terms. It follows
immediately from definition 13 and theorem 12 that
Corollary 12.2. A system of linear equations with n variables and n equations has a unique
solution if and only if its matrix is non-degenerate.
Corollary 12.3. A n⇥n matrix A is non-degenerate if and only if A has the maximum possible
rank, i.e., if rk(A) = n.
Corollary 12.4. A n⇥n matrix A is non-degenerate if and only if its rows (or columns) are
linearly independent.

4.7 Exercises
Problem 4.1. Evaluate the following determinants

4 4 0 0 4
6 3 12 8 4 9 7 2 9 4 1
(a) 0 9 12 0 0 (b) 10 12 2 (c) 12 4 4
6 4 12 8 2 4 11 1 12 0 12
12 6 12 12 0
1 4 11 9 4
1 4 2 6 0 0 0 6 2 11 1
(d) 9 4 2 2 0 (e) 1 1 8 (f) 1 9 8
8 1 5 7 4 10 2 4 2 6 10
7 4 11 5 0
0 3 0 11 1
12 2 2 10 2 8 2 1 10 4 0
(g) 6 3 0 7 4 (h) 9 3 12 (i) 1 7 1
6 4 1 12 7 12 3 3 7 10 2
6 2 1 10 10
7 10 4 4 3 4 0 6
5 11 7
1 12 8 6 12 1 0 2
(j) (k) 2 3 10 (l)
3 6 12 6 12 2 0 0
4 4 10
5 8 12 8 6 10 4 1

Problem 4.2. Evaluate ranks of the following matrices by any appropriate methods.

34
 5 MATRIX ALGEBRA

0 1 0 1
12 0 7 5 4 20 10 13 1 13
B 24 0 14 10 8 C B 12 9 12 0 9 C
(a)B
@
C (b)B C
8 16 2 6 0 A @ 12 4 5 1 7 A
12 6 8 4 5 20 10 15 5 5
0 1 0 1
16 18 6 5 8 3 2 4 2 0
B 16 18 6 8 14 C B 10 2 8 4 2 C
(c)B
@
C (d)B C
19 12 8 3 8 A @ 19 6 4 2 8 A
5 9 17 14 3 17 12 4 2 10
0 1 0 1
15 11 9 0 16 12 8 16 5 11
B 8 10 6 2 8 C B 6 2 11 2 2 C
(e)B
@
C (f)B C
22 12 12 2 24 A @ 10 6 18 8 10 A
5 14 6 5 4 3 11 1 4 17
Problem 4.3. Solve the following SLE’s by using the Cramer’s rule, when possible.
8 8
< x1 + 3x2 + 2x3 = 6 < 3x1 + 4x2 5x3 = 2
(a) 4x1 + x2 + 3x3 = 7 (b) 4x1 2x2 5x3 = 7
: :
5x1 + x2 x3 = 10 8 4x 1 + x2 5x3 = 25
8 > 5x1 3x2 + 2x3 3x4 = 11
< x1 + x2 + 2x3 = 5 >
<
2x1 + x2 + 4x3 + 2x4 = 10
(c) 4x1 + 3x2 5x3 = 12 (d)
: >
> 4x1 4x2 x3 + 4x4 = 26
4x1 5x2 = 11 :
8 5x1 + 4x2 + 2x3 + 2x4 = 8
8
> 3x2 5x3 2x4 = 24
>
< < 4x1 4x2 5x3 = 6
3x1 + x2 + 3x3 + 2x4 = 1
(e) (f) 3x1 + 2x2 5x3 = 13
>
> 5x1 + x2 3x3 3x4 = 7 :
: x1 3x2 + x3 = 12
4x1 + x2 + 2x3 5x4 = 22 8
8 > 3x1 x2 5x3 + 4x4 = 2
< 4x1 2x3 = 4 >
<
x1 3x2 3x3 = 4
(g) 3x1 2x2 3x3 = 1 (h)
: >
> x 2 4x3 5x4 = 11
x1 2x2 + x3 = 3 :
2x1 + x2 x3 + 3x4 = 2

5 Matrix algebra
5.1 Matrix operations
The set of n⇥m matrices Mn,m (R) is naturally equipped with the structure of a linear vector
space with respect to the operation of matrix addition that is defined below. Let A, B 2
Mn,m (R), 0 1 0 1
a11 a12 . . . a1m b11 b12 . . . b1m
B a21 a22 . . . a2m C B b21 b22 . . . b2m C
B C B C
A = B .. .. . . .. C , B = B .. .. . . .. C.
@ . . . . A @ . . . . A
an1 an2 . . . anm bn1 bn2 . . . bnm

35
5.1 Matrix operations 5 MATRIX ALGEBRA

The matrices A + B and A are defined by component-wise addition of elements of A and

B and component-wise multiplication of elements of A by , respectively, i.e.,
0 1
a11 + b11 a12 + b12 . . . a1m + b1m
B a21 + b21 a22 + b22 . . . a2m + b2m C
B C
A+B =B .. .. . . .. C ,
@ . . . . A
an1 + bn1 an2 + bn2 . . . anm + bnm
0 1
a11 a12 . . . a1m
B a21 a22 . . . a2m C
B C
A=B .. .. . . .. C
@ . . . . A
an1 an2 . . . anm

Example 5.1.
✓ ◆ ✓ ◆ ✓ ◆
0 1 2 2 1 0 2 2 2
A= , B= , A+B = .
3 4 5 0 0 1 3 4 6

The following properties of matrix addition and scaling are evident.

1. 8A, B, C 2 Mn,m (R) (A + B) + C = A + (B + C)

2. 90 2 Mn,m (R) : 8A 2 Mn,m (R) A + 0 = 0 + A = A

3. 8A 2 Mn,m (R) 9( A) 2 Mn,m (R) : A + ( A) = ( A) + A = 0

4. A + B = B + A for 8A, B 2 Mn,m (R)

5. 8 2 R 8A, B 2 Mn,m (R) (A + B) = A + B

6. 8 , µ 2 R 8A 2 Mn,m (R) ( µ)A = (µ)A

Thus, Mn,m (R) is a linear vector space5 with dim Mn,m (R) = nm. In contrast to matrix
addition, matrix multiplication is generally defined for matrices of different sizes.
Let A 2 Mn,k (R) and B 2 Mk,m (R). Note that the number of columns of the first matrix is
equal to the number of rows of the second matrix. Such matrices are called compatible. Then,
the matrix C = A ⇥ B = (cij ) is defined by the formula
k
X
cij = ais ⇥ bsj .
s=1

Example 5.2. ✓ ◆ ✓ ◆
1 2 1 2 3
A= , B=
3 4 4 5 6
5
Can you find a natural base in this space?

36
5.2 Inverse matrix 5 MATRIX ALGEBRA

2
X
c11 = a1s bs1 = a11 b11 + a12 b21 = 1 ⇥ 1 + 2 ⇥ 4 = 9,
s=1
2
X
c12 = a1s bs2 = a11 b12 + a12 b22 = 1 ⇥ 2 + 2 ⇥ 5 = 12,
s=1
...
2
X
c23 = a2s bs3 = a21 b13 + a22 b23 = 3 ⇥ 3 + 4 ⇥ 6 = 33,
s=1
✓ ◆
9 12 15
A⇥B = .
19 26 33
Matrix multiplication is a binary operation which can be though of as a mapping f :
Mn,k (R) ⇥ Mk,m (R) ! Mn,m (R) with the following properties.

1. 8A 2 Mn,k (R) 8B 2 Mk,l (R) 8C 2 Ml,m (R) (A ⇥ B) ⇥ C = A ⇥ (B ⇥ C)

2. 8A 2 Mn,k (R) 8B, C 2 Mk,m (R) A ⇥ (B + C) = A ⇥ B + A ⇥ C

3. 8 2 R 8A 2 Mn,k (R) 8B 2 Mk,m (R) ( A) ⇥ B = (A ⇥ B)

Note that, in general, A⇥B 6= B ⇥A, i.e., matrix multiplication is not commutative. This is the
most striking difference of matrix multiplication from the multiplication of numbers. So, from
now on we will pay special attention to the order of terms in matrix products. For instance,
we distinguish between left and right multiplication, where A multiplied by B from the right
means A ⇥ B, while A multiplied by B from the left means B ⇥ A.

Example 5.3.
✓ ◆ ✓ ◆ ✓ ◆ ✓ ◆
0 1 0 0 0 1 0 0
A= B= A⇥B = B⇥A=
0 0 0 1 0 0 0 0

Lemma 13. (A ⇥ B)T = B T ⇥ AT

P
Proof. Consider A ⇥ B = C = (cij ). That is, cij = k aik bkj . Then, C
T
= (cji ) and
P P P
cji = k ajk bki = k bki ajk = k b̃ik ãkj , where b̃ij and ãij are the elements of B T and AT ,
respectively. Therefore, C T = B T ⇥ AT .

5.2 Inverse matrix

In this section we consider only square matrices. Let A 2 Mnn (R) be such a matrix. The notion
of inverse matrix is very similar to the notion of inverse (reciprocal) number. The reciprocal

37
5.3 Inverse matrix by Gauss elimination 5 MATRIX ALGEBRA

to x is x 1 , which is defined as a number such that x ⇥ x 1 = 1. For matrices, the role of 1 is

played by the identity matrix
0 1
1 0 ... 0
B 0 1 ... 0 C
B C
En = B .. .. . . .. C 2 Mnn (R),
@ . . . . A
0 0 ... 1

which is the neutral element of matrix multiplication, i.e., A ⇥ E = E ⇥ A = A for every

A 2 Mnn (R).
Definition 14. Let A be a square n⇥n matrix. The matrix A 1 2 Mnn (R) is called the inverse
matrix for A if A ⇥ A 1 = A 1 ⇥ A = E, where E is the identity matrix.

Lemma 14. (A ⇥ B) 1
=B 1
⇥ A 1.
Proof. (B 1 ⇥ A 1 ) ⇥ (A ⇥ B) = B 1
⇥ (A 1 ⇥ A) ⇥ B = B 1
⇥ B = E. Similarly, (A ⇥ B) ⇥
(B 1 ⇥ A 1 ) = A ⇥ (B ⇥ B 1 ) ⇥ A 1
= A ⇥ A 1 = E.
Lemma 15. (AT ) 1
= (A 1 )T .
Proof. According to lemma 13, (A 1 )T ⇥AT = (A⇥A 1 )T = E and AT ⇥(A 1 )T = (A 1 ⇥A)T =
E. Thus, (A 1 )T is the inverse to AT .

5.3 Inverse matrix by Gauss elimination

The following theorem gives the necessary and sufficient condition of existence of the inverse
matrix.
Theorem 16. A 1
exists if and only if det(A) 6= 0
Proof. The necessary part follows from the definition: det(A ⇥ A 1 ) = det(A) det(A 1 ) = 1
and, therefore, det(A) cannot be equal to zero.
Now we prove the sufficient condition. Assume that
0 1 0 1
a11 a12 . . . a1m b11 b12 . . . b1m
B a21 a22 . . . a2n C B b21 b22 . . . b2n C
B C 1 B C
A = B .. .. . . .. C , A = B .. .. . . .. C ,
@ . . . . A @ . . . . A
an1 an2 . . . ann bn1 bn2 . . . bnn

and C = A ⇥ B. We need C = E. Thus, for the first column of C we get

c11 = a11 b11 + a12 b21 + · · · + a1n bn1 = 1,

c21 = a21 b11 + a22 b21 + · · · + a2n bn1 = 0,

cn1 = an1 b11 + an2 b21 + · · · + ann bn1 = 0,

38
5.3 Inverse matrix by Gauss elimination 5 MATRIX ALGEBRA

That is, in order to solve for b11 , . . . , bn1 , we have to solve the SLE
0 1
a11 a12 . . . a1n 1
B a21 a22 . . . a2n 0 C
B C
B .. .. . . .. C
@ . . . . 0 A
an1 an2 . . . ann 0
Similarly, the second column of C gives

c12 = a11 b12 + a12 b22 + · · · + a1n bn2 = 0,

c22 = a21 b12 + a22 b22 + · · · + a2n bn2 = 1,

cn2 = an1 b12 + an2 b22 + · · · + ann bn2 = 0,
i.e., in order to get b12 , . . . , bn2 , we need to solve for
0 1
a11 a12 . . . a1n 0
B a21 a22 . . . a2n 1 C
B C
B .. .. . . .. C.
@ . . . . 0 A
an1 an2 . . . ann 0

A similar SLE can be written for b1n , . . . , bnn . Note that all these SLEs have the same matrix
and differ only by the column of free terms. Thus, we can solve them all simultaneously
because the sequence of operations that are applied to the matrix of SLE will be the same for
each column in the right-hand side. In other words, we can write
0 1
a11 a12 . . . a1n 1 0 . . . 0
B a21 a22 . . . a2n 0 1 . . . 0 C
B C
B .. .. . . .. .. .. . . C,
@ . . . . . . . 0 A
an1 an2 . . . ann 0 0 . . . 1

or, shortly, (A|E) and apply Gauss elimination procedure to transform A to E. Then, the
matrix on the right of the vertical bar will be A 1 . According to theorem 11, if det(A) 6= 0
then the solution (A|E) exists and is unique.
Remark. The proof of this theorem can be used to calculate A 1
numerically.
✓ ◆
2 3
Example 5.4. Given A = , compute A 1
3 5
Solution.
✓ ◆ ✓ ◆ ✓ ◆
2 3 1 0 1 2 1 1 1 2 1 1
! ! !
3 5 0 1 2 3 1 0 0 1 3 2
✓ ◆ ✓ ◆ ✓ ◆
1 2 1 1 2 3 1 0 1 0 5 3
! !
0 1 3 2 3 5 0 1 0 1 3 2

39
5.4 Inverse matrix by algebraic complements 5 MATRIX ALGEBRA

✓ ◆ ✓ ◆ ✓ ◆
2 3 5 3 1 0
Verify by multiplication: ⇥ = .
✓ ◆3 5 3 2 0 1
5 3
That is, A 1 = .
3 2
0 1
2 1 1
Example 5.5. Given A = @ 1 1 2 A, find A 1 .
0 3 1
Solution. 0 1 0 1
2 1 1 1 0 0 1 1 2 0 1 0
@ 1 1 2 0 1 0 A!@ 0 3 3 1 2 0 A!
0 3 1 0 0 1 0 3 1 0 0 1
0 1 0 1
1 1 2 0 1 0 1 1 0 1 1 1
@ 0 1 1 13 2
0 A!@ 0 1 0 1 1 1 A
!
3 6 3 2
0 0 1 12 1 1
2
0 0 1 1
2
1 1
2
0 5 2 1
1
1 0 0 6 3 2
@ 0 1 0 1 1 1 A.
6 3 2
1 1
0 0 1 2
1 2
Check: 0 1 0 1 0 1
5 2 1
2 1 1 6 3 2
1 0 0
@ 1 1 2 A⇥@ 1 1 1 A = @ 0 1 0 A ..
6 3 2
1 1
0 3 1 2
1 2
0 0 1

5.4 Inverse matrix by algebraic complements

In this section we discuss the algorithm for calculation of A 1 which is based on the use of
determinants. The inverse matrix can be calculated in five steps.

1. Calculate det(A). Proceed to the next step unless det(A) = 0.

2. For each i and j, compute the value of algebraic complement Mij (see definition in sec-
tion 4.4 on page 29) and collect them in a new matrix.

3. Transpose the matrix obtained in step 2.

4. Multiply each element of the transpose matrix by ( 1)i+j , i.e., change signs according to
the chess-board pattern: 0 1
+ + +
B + + C
B C
@ + + + A
+ +

5. Divide each element of the obtained matrix by det(A)

40
5.5 Matrix equations 5 MATRIX ALGEBRA

1 0
1 2 1
Example 5.6. Find the inverse matrix for A = @ 2 1 0 A
1 0 3
Solution. 1. det A= 3+0+0-1-12-0=-10

2. Compute algebraic complements (also called cofactor matrix)

1 0
M11 = = 3, M12 = 6, M13 = 1
0 3

2 1
M21 = = 6, M22 = 2, M23 = 2
0 3

2 1
M31 = = 1, M32 = 2, M33 = 3
1 0

3. Transpose
0 1T 0 1
3 6 1 3 6 1
@ 6 2 2 A =@ 6 2 2 A.
1 2 3 1 2 3

4. Change signs 0 1
3 6 1
@ 6 2 2 A.
1 2 3

5. Divide each element by det(A)

0 1
0.3 0.6 0.1
A 1
=@ 0.6 0.2 0.2 A ..
0.1 0.2 0.3

6. Check: 0 1 0 1 0 1
1 2 1 0.3 0.6 0.1 1 0 0
@ 2 1 0 A⇥@ 0.6 0.2 0.2 A = @ 0 1 0 A .
1 0 3 0.1 0.2 0.3 0 0 1

5.5 Matrix equations

A matrix equation is written similarly to a numeric equation, like AX = B, with the exception
that A and B are matrices, and the unknown X is a matrix, too (for simplicity of notation, we
omit the multiplication sign, ⇥, as we often do for multiplication of numbers). When you solve
numeric equations, for instance 2x = 3, you simply divide the right-hand side by the factor in
the left-hand side, i.e., x = 3/2. Division is not that easy for matrices, because it is equivalent

41
5.5 Matrix equations 5 MATRIX ALGEBRA

to multiplication by the inverse matrix, which can be done from the right or from the left, each
with different outcomes.
In order to “cancel out” the matrix A in the left-hand side, one needs to multiply the matrix
equation AX = B by A 1 from the left, not from the right. Then A 1 AX = EX = X = A 1 B.
Similarly, the solution to the equation XA = B is X = XAA 1 = BA 1 .

Example 5.7. Solve the matrix equation

0 1 0 1
5 1 3 2 4
@ 5 0 4 AX = @ 4 6 A.
6 1 4 6 0

Solution. First, we calculate the inverse matrix

0 1
4 1 4
A = 1 @ 4 2 5 A.
5 1 5

Then, 0 1 0 1 0 1
4 1 4 2 4 28 22
X = A 1B = @ 4 2 5 A⇥@ 4 6 A=@ 30 28 A .
5 1 5 6 0 36 26
One can check by direct calculation that
0 1 0 1 0 1
5 1 3 28 22 2 4
@ 5 0 4 A⇥@ 30 28 A = @ 4 6 A.
6 1 4 36 26 6 0

There is another way to solve matrix equations, one that is based on the direct calculations.
Consider, for instance, the matrix equation AX = B. Similarly to what we have been doing
in section 5.3, the matrix product of A with the first column of X gives the following linear
equations 8
< a11 x11 + a12 x21 + . . . + a1n xn1 = b11
a21 x11 + a22 x21 + . . . + a2n xn1 = b21 .
:
an1 x11 + an2 x21 + . . . + ann xn1 = bn1
Thus, in order to solve for the first column of X, we need to solve SLE with the matrix
0 1
a11 a12 . . . a1n b11
B a21 a22 . . . a2n b21 C
B C
B .. .. .. .. .. C .
@ . . . . . A
an1 an2 . . . ann bn1

42
5.6 Elementary transformations matrices 5 MATRIX ALGEBRA

Similarly, to solve for the second column of X, we need to solve the equations
8
< a11 x12 + a12 x22 + ... + a1n xn2 = b12
a21 x12 + a22 x22 + ... + a2n xn2 = b22 ,
:
an1 x12 + an2 x22 + ... + ann xn2 = bn2

which yields SLE matrix, which differs from the previous one only by the column of free terms
0 1
a11 a12 . . . a1n b12
B a21 a22 . . . a2n b22 C
B C
B .. .. ... .. .. C .
@ . . . . A
an1 an2 . . . ann bn2

We can solve all these systems simultaneously by writing all b-terms to the right of the vertical
bar a(s in section 5.3) and applying Gauss elimination
0 1
..
B a11 a12 . . . a1n b11 b12 .. b1m C
B C
B a21 a22 . . . a2n b21 b22 .. b2m C
B . .. .. .. .. .. . . .. C .
B .. . . . . . . . C
@ A
.
an1 an2 . . . ann bn1 bn2 .. bnm

Example 5.8. Solve the matrix equation from the example 5.7 by Gauss elimination.

Solution.
0 1 0 1
5 1 3 2 4 1 0 1 8 4
[3]7![3] [1] [2]7![2] [1]⇥5
@ 5 0 4 4 6 A !@ 5 1 3 2 4 A !
6 1 4 6 0 5 0 4 4 6
0 1 0 1
1 0 1 8 4 1 0 1 8 4
[3]7![3] [1]⇥5 [1]7![1] [3]
@ 0 1 2 42 24 A ! @ 0 1 2 42 24 A !
5 0 4 4 6 0 0 1 36 26
0 1 0 1
1 0 0 28 22 1 0 0 28 22
[2]7![2] [3]⇥2
@ 0 1 2 42 24 A !@ 0 1 0 30 28 A .
0 0 1 36 26 0 0 1 36 26

5.6 Elementary transformations matrices

All of the transformations discussed in section 1.2 can be expressed in terms of matrix multi-
plication with the aid of special matrices called elementary transformation matrices.

43
5.6 Elementary transformations matrices 5 MATRIX ALGEBRA

The Type I transformation, in which the j th row is multiplied by some constant and added
to the ith row is equivalent to the multiplication (from the left) of the original matrix by the
matrix 0 1
1 0 ... 0
B 0 1 0 ... 0 C
B C
B C
Uij ( ) = B 0 0 1 . . . 0 C ,
B .. .. .. . . .. C
@ . . . . . A
0 0 0 ... 1
where is located in the intersection of the ith row and j th column, for instance in the case of
3⇥3 matrices, 0 1
1 0
U13 ( ) = @ 0 1 0 A .
0 0 1
The Type II transformation, in which the ith row is multiplied by a non-zero constant , is
equivalent to the multiplication (again, from the left) of the original matrix by
0 1
1 0 0 ... 0
B 0 1 0 ... 0 C
B C
B ... 0 C
Pi ( ) = B 0 0 C,
B .. .. .. . . .. C
@ . . . . . A
0 0 0 ... 1

where is located in the ith row on the diagonal, for instance,

0 1
1 0 0
P2 ( ) = @ 0 0 A.
0 0 1
The Type III transformation, in which the ith row and the j th row of the original matrix
are interchanged, can be expressed as multiplication (again, from the left) by
0 1
1 0 ... 0 0 ... 0
B 0 1 ... 0 0 ... 0 C
B . . .. C
B . . . . . .. .. C
B . . . . . C
B C
Tij ( ) = B 0 0 . . . 0 1 . . . 0 C ,
B C
B 0 0 ... 1 0 ... 0 C
B . . .. .. . . .. C
@ .. .. . . . . A
0 0 ... 0 0 ... 1
where the interchanged 1’s are located in the intersection of the ith and j th row and ith and j th
column, for instance 0 1
0 1 0
T12 = @ 1 0 0 A .
0 0 1

44
5.6 Elementary transformations matrices 5 MATRIX ALGEBRA

Example 5.9. Let A be a 3⇥3 matrix of the general form

0 1
a11 a12 a13
A = @ a21 a22 a23 A ,
a31 a32 a33

then U13 ( ) ⇥ A =
0 10 1 0 1
1 0 a11 a12 a13 a11 + a31 a12 + a32 a13 + a33
= @ 0 1 0 A @ a21 a22 a23 A = @ a21 a22 a23 A,
0 0 1 a31 a32 a33 a31 a32 a33
0 10 1 0 1
1 0 0 a11 a12 a13 a11 a12 a13
P2 ( ) ⇥ A = @ 0 0 A @ a21 a22 a23 A = @ a21 a22 a23 A , and
0 0 1 a31 a32 a33 a31 a32 a33
0 10 1 0 1
0 1 0 a11 a12 a13 a21 a22 a23
T12 ⇥ A = @ 1 0 0 A @ a21 a22 a23 A = @ a11 a12 a13 A .
0 0 1 a31 a32 a33 a31 a32 a33

Similarly, one can show that the multiplication from the right by Uji ( ), Pi ( ), and Tij
leads to Type I, Type II, and Type III transformations of columns, respectively6 . Note that
the multiplication by Uij ( ) doesn’t change det(A) because it is a type I transformation, while
the multiplication by Tij leads to the change of sign of det(A). Then, we will sometimes use
the matrix 0 1
1 0 ... 0 0 ... 0
B 0 1 ... 0 0 ... 0 C
B . . .. C
B . . . . . .. .. C
B . . . . . C
B C
Rij = B 0 0 . . . 0 1 ... 0 C,
B C
B 0 0 ... 1 0 ... 0 C
B . . .. .. . . .. C
@ .. .. . . . . A
0 0 ... 0 0 ... 1
where the 1 and -1 are located in the intersection of the ith and j th row and ith and j th column.
Its important feature is that the multiplication of a matrix by Rij from the left or right doesn’t
change its determinant. We will use the elementary transformation matrices to prove the
following theorem.

Theorem 17.
det(A ⇥ B) = det(A) det(B)

Proof. First, the proof is trivial when A or B is a degenerate matrix. Indeed, if A or B is

degenerate then A ⇥ B is degenerate, too, because its rows are linear combinations of a linearly
dependent set of vectors and we get both det(A ⇥ B) and det(A) det(B) equal to zero.
6
Spend some time with paper and pencil to check that it is, indeed, true!

45
5.7 Exercises 5 MATRIX ALGEBRA

Next, we prove this statement for the particular case when both A and B are upper-
triangular matrices. Assume that
0 1 0 1
a11 a12 a13 . . . a1n b11 b12 b13 . . . b1n
B 0 a22 a23 . . . a2n C B 0 b22 b23 . . . b2n C
B C B C
B 0 a33 . . . a3n C B C
A=B 0 C, B = B 0 0 b33 . . . b3n C.
B .. .. .. . . .. C B .. .. .. . . .. C
@ . . . . . A @ . . . . . A
0 0 0 . . . ann 0 0 0 ... bnn

Then, by definition of the matrix multiplication, we get

0 1
a11 b11 ⇤ ⇤ ... ⇤
B 0 a22 b22 ⇤ ... ⇤ C
B C
B 0 0 a b . . . ⇤ C
B 33 33 C,
B .. .. .. . .. .. C
@ . . . . A
0 0 0 . . . ann bnn

and, since the determinant of an upper-triangular matrix is the product of its diagonal en-
tries (theorem 8), we get det(A ⇥ B) = a11 b11 a22 b22 . . . ann bnn = a11 a22 . . . ann b11 b22 . . . bnn =
det(A) det(B).
The general case can be reduced to the case of upper-triangular matrices by elementary
transformations of rows, for the matrix A, and by elementary transformations of columns, for
the matrix B. Indeed, the matrix A can be represented as a product A = A1 ⇥A2 ⇥· · ·⇥Ak ⇥X,
where Ai is one of the matrices Uij ( ) or Rij which don’t affect the determinant, while X is
an upper-triangular matrix such that det(A) = det(X). Similarly, we can transform B by
elementary transformations of columns to the form Y ⇥ Bl ⇥ · · · ⇥ B2 ⇥ B1 , where Bj are
matrices Uij ( ) or Rij and Y is also an upper-triangular matrix such that det(B) = det(Y ).
Then, det(A ⇥ B) = det(A1 ⇥ A2 ⇥ · · · ⇥ Ak ⇥ X ⇥ Y ⇥ Bl ⇥ · · · ⇥ B2 ⇥ B1 ) = det(X ⇥ Y ) =
det(X) det(Y ) = det(A) det(B).

5.7 Exercises
Problem 5.1. Find the inverse matrix for each of the following matrices
0 1
1 2 4 11 2 0 1
B 4 C 2 0 7 1
B 0 9 7 3 C B 0 0 1 0 C
(a)B
B 0 1 1 8 0 CC (b)B@
C
@ 5 5 3 9 2 A
1 12 3 5 A
12 5 3 5
4 0 9 9 4
0 1 0 1
6 7 7 6 7 4 6 3
B 1 2 0 C
0 C B 4 2 2 1 C
(c)B
@ 6 (d)B C
7 8 6 A @ 12 6 9 5 A
2 3 1 1 10 3 5 4

46
5.7 Exercises 5 MATRIX ALGEBRA

0 1
0 1 11 11 10 10
3 2 4 B 0 1 1 1 C
(e)@ 2 1 3 A (f)B
@ 3
C
5 4 5 A
6 3 8
7 4 4 3
0 1
0 1 3 10 1 0 1
11 10 6 B 4 12 1 0 1 C
B C
(g)@ 6 5 3 A (h)B
B 1 2 3 0 2 C
C
10 8 5 @ 1 0 5 1 2 A
0 3 7 1 3
0 1 0 1
3 7 11 7 5 1 2 1 1 2
B 7 1 11 8 3 C B 1 8 10 0 5 C
B C B C
(i)B
B 5 2 5 6 3 C
C (j)B
B 1 1 2 4 2 C
C
@ 5 1 12 5 1 A @ 1 0 2 6 2 A
1 4 12 1 2 1 2 5 6 3

Problem 5.2. Solve the following matrix equations

0 1 0 1
3 3 5 1 5 4
(a) @ 1 1 2 AX = @ 3 2 2 A
7 6 10 1 2 2
0 1 0 1
6 4 1 6 1 1 0 4
B 5 4 1 6 C B 4 5 4 2 C
(b) B
@ 8
CX = B C
3 1 4 A @ 2 2 2 1 A
10 0 1 1 1 2 1 3
0 1
0 3 11 0 9 0 1
B 1 0 3 1 3
B 1 0 5 1 3 C
C B 4 1 3 2 3 C
(c) X B
B 1 0 5 2 5 C B
C=@ 4 1
C
@ A 4 1 4 A
1 4 2 3 3
2 4 1 0 3
1 5 2 5 1
0 1
0 1 1 2 3
7 6 8 B 1 2 3 C
B C
(d) X @ 1 1 B
1 A=B 4 3 2 C
C
3 2 3 @ 4 1 3 A
1 5 5
0 1 0 1
3 3 1 4 2 1
(e) @ 2 1 0 AX = @ 2 0 2 A
4 3 1 3 3 1

47
 6 LINEAR OPERATORS

0 1 0 1
8 12 1 0 2 3 2 2 4
B 3 7 2 1 C B 4 3 1 1 4 C
(f) B
@
CX = B C
7 6 2 2 A @ 5 3 2 2 4 A
0 5 3 2 3 4 2 5 2

6 Linear operators
The notion of a linear operator is very general and has many applications in all parts of
mathematics, including calculus, statistics, and optimization theory. Commonly used synonyms
of a linear operator are linear map, linear mapping, linear transformation, or linear function.

Definition 15. Let V and W be linear vector spaces. The mapping f : V ! W is said to be
a linear operator if
1. 8x, y 2 V f (x + y) = f (x) + f (y)

2. 8x 2 V, 8 2 R f ( x) = f (x),
i.e., f preserves the operations of vector addition and scalar multiplication. Below we discuss
several examples of mapping which are (or are not) linear operators.
1. f : R ! R, f (x) = cx is a linear operator as c(x + y) = cx + cy and c( x) = (c )x.

2. f : R ! R, f (x) = x2 is NOT a linear operator because (x + y)2 6= x2 + y 2 .

3. f : R ! R, f (x) = x + 1 is NOT a linear operator because (x + 1) + (y + 1) 6= (x + y) + 1.

4. The linear operator of differentiation by x, i.e., @x @

: C 1 [a, b] ! C 1 [a, b] such that
@
@x
(f ) = f (x), which is defined on the set of infinitely smooth functions (page 15) is a
0

linear operator.

5. The linear operator of integration over a segment [a, b], i.e., I : C[a, b] ! R such that
Rb Rb Rb Rb
I(f ) = a f (x)dx is a linear operator as a (f + g)(x)dx = a f (x)dx + a g(x)dx and
Rb Rb
a
( f )(x)dx = a
f (x)dx.

6. The linear operator of expected value acts on the linear space of random numbers to R
so that E(X + Y ) = E(X) + E(Y ) and E( X) = E(X).

7. f : R2 ! R2 , f (x, y) = (y, x) is a linear operator of symmetry with respect to the bisector

line of the first quadrant, as the vector symmetric to a sum of two vectors is equal to the
sum of their symmetric images (the same is true for scaling).

8. f : R2 ! R2 , f (x, y) = (y, x) is a linear operator of rotation 90 counterclockwise (check

it!), as the rotated sum of two vectors is equal to the sum of rotations.

9. f : R2 ! R, f (x, y) = x is a linear operator of projection onto the x-axis, because the

projection of the sum of two vectors is equal to the sum of their projections.

48
6.1 Matrix of a linear operator 6 LINEAR OPERATORS

p
10. f : R2 ! R, f (x, y) = x2 + y 2 is NOT a linear operator, because the length of the sum
of two vectors is not equal to the sum of their lengths.

6.1 Matrix of a linear operator

We now explore the connection between linear operators and matrices. It turns out, that
each linear operator can be described with a matrix, but the problem is that this matrix is
basis-dependent.
Consider a vector space V with a base e1 , e2 , . . . , en . Since each vector of V can be expressed
as a linear combination of e1 , e2 , . . . , en , we get x = x1 e1 + x2 e2 + · · · + xn en , where x1 , x2 , . . . , xn
are the coordinates of x in the base e1 , e2 , . . . , en . If A : V ! W is a linear operator then A(x) =
A(x1 e1 +x2 e2 +· · ·+xn en ) = x1 A(e1 )+x2 A(e2 )+· · ·+xn A(en ). Here, A(e1 ), A(e2 ), . . . , A(en ) are
the images of base vectors under the map f . Note that they are the same for all vectors x. Chose
the base f1 , f2 , . . . , fm in the vector space W and decompose vectors A(e1 ), A(e2 ), . . . , A(en ) by
that base7 .
A(e1 ) = a11 f1 + a21 f2 + . . . + am1 fm ,
A(e2 ) = a12 f1 + a22 f2 + . . . + am2 fm ,
A(en ) = a1n f1 + a2n f2 + . . . + amn fm .
We have A(x) = x1 A(e1 )+x2 A(e2 )+· · ·+xn A(en ) = x1 (a11 f1 +a21 f2 +· · ·+am1 fm )+x2 (a12 f1 +
a22 f2 + · · · + am2 fm ) + · · · + xn (a1n f1 + a2n f2 + · · · + amn fm ) = (a11 x1 + a12 x2 + · · · + a1n xn )f1 +
(a21 x1 + a22 x2 + · · · + a2n xn )f2 + . . . (am1 x1 + am2 x2 + · · · + amn xn )fm . Thus, we can write the
action of y = A(x) by using matrix multiplication as
0 1 0 1 0 1
y1 a11 a12 . . . a1n x1
B y2 C B a21 a22 . . . a2n C B x2 C
B C B C B C
B .. C = B .. .. .. .. C ⇥ B .. C ,
@ . A @ . . . . A @ . A
ym am1 am2 . . . a1mn xn

where x1 , x2 , . . . , xn are the coordinates of x in the base e1 , e2 , . . . , en and y1 , y2 , . . . , ym are the

coordinates of A(x) in the base f1 , f2 , . . . , fm . Note that it is the same base which gave rise to
the matrix (aij ) of the coordinates of f (ei ). The matrix formed by (aij ) will be called the matrix
of the linear operator A and will be denoted by the same capital letter as the linear operator.
Its matrix is specific to the bases e1 , e2 , . . . , en and f1 , f2 , . . . , fm . In order to construct the
matrix of a linear operator, one needs to take images of all base vectors of the space V , find
their coordinates in the base of the space W , and write down the coordinates as columns. This
gives the matrix of a linear operator.
Example 6.1. Let A : R2 ! R2 be the linear operator of rotation 90 counterclockwise on the
plane. Consider e1 = f1 = (1, 0) and e2 = f2 = (0, 1). Then, A(e1 ) = f2 = 0 · f1 + 1 · f2 and
A(e2 ) = f1 = ( 1) · f1 + 0 · f2 . Therefore, the matrix of A in these bases is
✓ ◆
0 1
A= .
1 0
7
Please pay attention to the notation of indices, which changed to make a more convenient expression below.

49
6.2 Change of base 6 LINEAR OPERATORS

Example 6.2. Let V be the vector space of polynomials of degree 2 or less and let A : V ! V
be the operator of differentiation by x. Consider the bases e1 , e2 , e3 and f1 , f2 , f3 such that
e1 = f1 = 1, e2 = f2 = x, and e3 = f3 = x2 . Then, A(e1 ) = 0 = 0 · f1 + 0 · f2 + 0 · f3 ,
A(e2 ) = f1 = 1 · f1 + 0 · f2 + 0 · f3 , and A(e3 ) = 2f2 = 0 · f1 + 2 · f2 + 0 · f3 . Hence, the matrix
of A is 0 1
0 1 0
A = @ 0 0 2 A.
0 0 0

Example 6.3. Let A : R3 ! R3 be the linear operator of rotation in 3D which induces a cyclic
permutation of the axes x, y, and z. In other words, it is a rotation around the line x = y = z by
120 clockwise when looking at the origin from the first octant8 . Consider e1 = f1 = (1, 0, 0),
e2 = f2 = (0, 1, 0), and e3 = f3 = (0, 0, 1). Then, A(e1 ) = f2 = 0 · f1 + 1 · f2 + 0 · f3 ,
A(e2 ) = f3 = 0 · f1 + 0 · f2 + 1 · f3 , and A(e3 ) = f1 = 1 · f1 + 0 · f2 + 0 · f3 . Therefore, the matrix
of A in these bases is 0 1
0 0 1
A = @ 1 0 0 A.
0 1 0

6.2 Change of base

In the previous section we considered two different vector spaces, V and W , each endowed
with its own base. Consider now a linear vector space V with two bases, e1 , e2 , . . . , en and
e01 , e02 , . . . , e0n . In what follows, they will be called the old base and the new base, respectively,
reflecting our intention to change from the old base to the new base. Let x = x1 e1 + x2 e2 +
· · · + xn en = x01 e01 + x02 e02 + · · · + x0n e0n be two coordinate decompositions of x over the old and
the new base. Assume that the vectors of the old base are decomposed by the new base

e1 = c11 e01 + c21 e02 + . . . + cn1 e0n ,

e2 = c12 e01 + c22 e02 + . . . + cn2 e0n ,
en = c1n e01 + c2n e02 + . . . + cnn e0n .

Then, we get x = x1 e1 + x2 e2 + · · · + xn en = x1 (c11 e01 + c21 e02 + · · · + cn1 e0n ) + x2 (c12 e01 + c22 e02 +
· · · + cn2 e0n ) + · · · + xn (c1n e01 + c2n e02 + · · · + cnn e0n ) = (x1 c11 + x2 c12 + · · · + xn c1n )e01 + (x1 c21 +
x2 c22 + · · · + xn c2n )e02 + · · · + (x1 cn1 + x2 cn2 + · · · + xn cnn )e0n = x01 e01 + x02 e02 + · · · + x0n e0n . Since
the coordinates of a vector in a base are defined uniquely, we have
8 0
< x1 = c11 x1 + c12 x2 + . . . + c1n xn
x0 = c12 x1 + c22 x2 + . . . + c2n xn
: 02
xn = c1n x1 + cn2 x2 + . . . + cnn xn

Thus, the change of bases incurs the change of coordinates, which has the form

x0 = Cx,
8
Can you rigorously show that the rotation angle if 120 ?.

50
6.3 Eigenvectors and eigenvalues 6 LINEAR OPERATORS

where x0 is the column-vector of coordinates in the new base, x is the column-vector of coor-
dinates in the old base, and the (square) matrix C contains the coordinates of the old base
vectors in the new base. The backward transformation of coordinates is expressed by using the
inverse matrix, i.e.,
x = C 1 x0 .
The matrix C is called the transition matrix from the base e1 , e2 , . . . , en to the base e01 , e02 , . . . , e0n .
Consider now a linear operator A : V ! V with the matrix A in the old base (which plays
the role of both ei and fi in the definition of a matrix of a linear operator) and with the matrix
A0 in the new base. That is, y = Ax and y 0 = A0 x0 . Besides that, x0 = Cx and y 0 = Cy with
the same transition matrix C. Thus, y 0 = Cy = A0 x0 = A0 Cx, and then y = C 1 A0 Cx = Ax.
Since the matrix of a linear operator is defined uniquely by construction, we get
A=C 1
A0 C, or A0 = CAC 1
.
This is the rule, by which the matrix of a linear operator is transformed under the change of
base.
Definition 16. Two n⇥n matrices, A and B, are called conjugate if there exists a non-
degenerate matrix C such that B = CAC 1 .
Thus, the matrix of a linear operator looks differently in different bases. Two matrices of the
same linear operator in different bases are conjugate to each other. An obvious question is to
what “standard” form can one transform the matrix of a linear operator by using conjugation.
An incomplete, but still a reasonable answer to this question will be given in the next sections.

6.3 Eigenvectors and eigenvalues

Definition 17. Let V be a vector space and let A : V ! V be a linear operator. The vector
x 6= 0 is said to be an eigenvector of A with the eigenvalue if A(x) = x. In other words, A
acts on x as multiplication by scalars.
Definition 18. Let A be a n⇥n matrix. The non-zero vector x 2 Rn is called the eigenvector
of A with the eigenvalue if Ax = x.
Theorem 18. The number 2 R is an eigenvalue of the matrix A if and only if det(A E) =
0.
Proof. Assume is an eigenvalue of the matrix A. Then, for some x 6= 0 we have Ax = x,
i.e., 8
>
> a11 x1 + a12 x2 + . . . + a1n xn = x1
<
a21 x1 + a22 x2 + . . . + a2n xn = x2
>
> ...
:
an1 x1 + an2 x2 + . . . + ann xn = xn
That is, 8
< (a11 )x1 + a12 x2 + ... + a1n xn = 0
a21 x1 + (a22 )x2 + . . . + a2n xn = 0 ,
:
an1 x1 + an2 x2 + ... + (ann )xn = 0

51
6.3 Eigenvectors and eigenvalues 6 LINEAR OPERATORS

which in matrix form is (A E)x = 0. The latter is a homogeneous system of linear equations,
which already has one solution x = 0. In order to have a non-zero solution, it must be degenerate
(theorem 11), i.e., det(A E) = 0.
Conversely, if det(A E) = 0 then (A E)x = 0 is degenerate and must have a non-zero
solution x. Then, we have Ax x = 0, concluding that x is the eigenvector of A with the
eigenvalue .
Note that the final result of the decomposition of det(A E) is a polynomial, i.e.,

(a11 ) a12 ... a1n

a21 (a22 ) ... a2n
.. .. .. .. =
. . . .
an1 an2 . . . (ann )

= (a11 )(a22 )(a33 ) . . . (ann ) a12 a21 (a33 ) . . . (ann ) + · · · = ( 1)n n

+
cn 1 n 1
+ cn 2 n 2
+ c1 1
+ c0 .
Definition 19. The polynomial function fA ( ) = det(A E) is called the characteristic
polynomial of the matrix A.

Theorem 19. Characteristic polynomials of conjugate matrices are equal.

Proof. Let B be the matrix that is conjugate to A, i.e., B = CAC 1 . Then, by the properties
of matrix multiplication fB ( ) = det(CAC 1 E) = det(CAC 1 CEC 1 ) = det(C(A
E)C 1 ) = det(C) det(A E) det(C 1 ) = det(A E) = fA ( ).
Corollary 19.1. The sum of diagonal elements of a matrix doesn’t change under conjugation.
Proof. Note that the entire characteristic polynomial doesn’t change under conjugation. In
particular, the factor cn 1 at n 1 doesn’t change, too. In fact, the product of n 1 copies of
can only appear from the term (a11 )(a22 )(a33 ) . . . (ann ) because the other terms
contain to the power of n 2 or less. Then, cn 1 n 1
= ( 1) n 1 n 1
(a11 + a22 + · · · + ann ).
Thus, the sum of diagonal elements of a matrix doesn’t change under conjugation.
Definition 20. The sum of matrix’s diagonal elements is called its trace and is denoted by
tr(A).

Example 6.4. Find eigenvectors and eigenvalues of the matrix

✓ ◆
3 4
A= .
5 2
✓ ◆ ✓ ◆ ✓ ◆ ✓ ◆ ✓ ◆
3 4 1 0 3 4 0 3 4
Solution. A E = = = .
5 2 0 1 5 2 0 5 2
3 4
Thus, we get = (3 )(2 ) 20 = 2 5 14 = 0. Solving the quadratic
5 2

52
6.3 Eigenvectors and eigenvalues 6 LINEAR OPERATORS

equation, we get 1 = 2 and 2 = 7.

Case 1: 1 = 7. ◆ ✓
4 4
A 7E =
5 5
✓ ◆✓ ◆ ✓ ◆
4 4 x1 0
=
5 5 x2 0
✓ ◆ ✓ ◆
4 4 0 [1]7![1]/( 4) 1 1 0 [2]7![2] [1]⇥5
! ! 1 1 0
5 5 0 5 5 0
✓ ◆
1
There exists a non-zero solution, i.e., the vector x = (and all the vectors that are
1
proportionate to it) are eigenvectors with the eigenvalue 1 = 7.
Case 2: 2 = 2.
✓ ◆
5 4
A E=
5 4
Similarly, we get ✓ ◆✓ ◆ ✓ ◆
5 4 x1 0
= ,
5 4 x2 0
✓ ◆
4
and the vector y = is the eigenvector with the eigenvalue 2 = 2.
5
Example 6.5. Find eigenvectors and eigenvalues of the matrix
0 1
5 7 7
@ 8 3 2 A
8 1 2

Solution. 0 1
5 7 7
det @ 8 3 2 A=
8 1 2
= (5 )⇥(3 )⇥(2 ) 7⇥8⇥2+8⇥1⇥7+8⇥7⇥(3 ) 8⇥7⇥(2 ) 1⇥2⇥(5 )=
(5 ) ⇥ (1 ) ⇥ (4 ) = 0.
Case 1: 1 = 5. 0 1
0 7 7
A E=@ 8 2 2 A
8 1 3
0 1 0 1 0 1
0 7 7 0 1 1 0 1 1 ✓ ◆
@ 8 A @ A @ A 0 1 1
2 2 ! 8 2 2 ! 8 0 4 !
2 0 1
8 1 3 8 1 3 8 0 4

53
6.3 Eigenvectors and eigenvalues 6 LINEAR OPERATORS

0 1
1
Then, letting x3 = 2 we get x2 = 2 and x1 = 1. The first eigenvector is x = @ 2 A.
2
Case 2: 1 = 1. 0 1
4 7 7
A E=@ 8 2 2 A
8 1 1
0 1 0 1 0 1
4 7 7 4 7 7 0 7 7 ✓ ◆
@ 1 0 0
8 2 2 A!@ 8 2 2 A!@ 0 1 A 1! .
0 1 1
8 1 1 1 0 0 1 0 0
0 1
0
Letting x3 = 1 we get x2 = 1 and x1 = 0. The second eigenvector is y = @ 1 A.
1
Case 3: 1 = 4. 0 1
1 7 7
A E=@ 8 1 2 A
8 1 2
0 1
1 7 7 ✓ ◆ ✓ ◆ ✓ ◆
@ 8 1 7 7 1 7 7 1 7 7
1 2 A! ! !
8 1 2 0 57 54 0 19 18
8 1 2
Guessing
0 that
1 x3 = 19, we get x2 = 18 and x1 = 7. Therefore, the last eigenvector is
7
z = @ 18 A.
19
In the example above, one could probably notice that the transition matrix
0 1
1 0 7
C = @ 2 1 18 A ,
2 1 19

which is obtained from the vectors x, y, and z by attaching their coordinates to each other,
transforms matrix A by the rule C 1 AC to the diagonal matrix
0 1 0 1 0 1 0 1
1 7 7 5 7 7 1 0 7 5 0 0
@ 2 5 4 A⇥@ 8 3 2 A ⇥ @ 2 1 18 A = @ 0 1 0 A,
0 1 1 8 1 2 2 1 19 0 0 4

where the diagonal entries are the eigenvalues of A. It happens because x, y, and z are linearly
independent and form a base in R3 , while the matrix of a linear operator in a base that consists
of eigenvectors must always be diagonal (by definition).

Theorem 20. Let A be a n⇥n matrix. Eigenvectors of A corresponding to different eigenvalues

are linearly independent.

54
6.4 Diagonalizable matrices 6 LINEAR OPERATORS

Proof. Let x1 , x2 , . . . , xk be the eigenvectors corresponding to the eigenvalues 1 , 2 , . . . , k . We

need to prove that if 8i 6= j i 6= j then x1 , x2 , . . . , xk are linearly independent.
The proof of this statement is by induction on k. The base of the induction (k = 1) is
obvious because every eigenvector is non-zero by definition and, therefore, forms a linearly
independent set by itself. Assume that we have proven the statement for every set of k 1
eigenvectors with different eigenvalues, and now want to proceed to k eigenvectors.
Suppose, on the contrary, that x1 , x2 , . . . , xk are linearly dependent, i.e., there exist coeffi-
cients µ1 , µ2 , . . . , µk , some of which are non-zero, such that
µ1 x1 + µ2 x2 + · · · + µn xn = 0.
By applying A to both sides of the equation, we get A(µ1 x1 + µ2 x2 + · · · + µn xn ) = A(µ1 x1 ) +
A(µ2 x2 )+· · ·+A(µn xn ) = µ1 A(x1 )+µ2 A(x2 )+· · ·+µn A(xn ) = µ1 1 x1 +µ2 2 x2 +· · ·+µn n xn .
This, in combination with the linear combination of x1 , x2 , . . . , xk multiplied by 1 , gives
⇢
µ1 1 x 1 + µ2 2 x 2 + · · · + µn n x n = 0
,
µ1 1 x 1 + µ2 1 x 2 + · · · + µn 1 x n = 0
which implies that
µ2 ( 2 1 )x2 + µ3 ( 3 1 )x3 + · · · + µn ( n 1 )xn = 0.
Thus, we have a linear combination of x2 , . . . , xn which consists of k 1 vectors and is linearly
dependent. By induction, it is possible only if such linear combination is trivial, i.e., if µ2 ( 2
1 ) = µ3 ( 3 1 ) = · · · = µn ( n 1 ) = 0. Since all ’s are different, we have i 1 6= 0 and,
therefore, µ2 = µ3 = · · · = µn = 0.
Repeating the same argument with multiplication of the linear combination of x1 , x2 , . . . , xk
by 2 instead of 1 leads to the conclusion that µ1 = 0, too. Therefore, µ1 = µ2 = · · · = µn = 0
and the linear combination we chose is trivial, i.e., x1 , x2 , . . . , xk are linearly independent.

6.4 Diagonalizable matrices

The property of a linear operator to have a base consisting of eigenvectors (example 6.5) is very
useful. Such “good” linear operators play an important role in many applications, for instance,
in linear ordinary differential equations and in linear differential-difference equations.
Definition 21. The linear operator A : V ! V is called diagonalizable if its matrix is diagonal
in some base of V . Equivalently, one can find a base of V which consists of eigenvectors of A.
Definition 22. A n⇥n matrix A is called diagonalizable9 if there exist a non-degenerate matrix
C and a diagonal matrix D such that CAC 1 = D.
Obviously, a linear operator is diagonalizable if and only if its matrix (in some base) is
diagonalizable. Considering that the characteristic polynomial of fA ( ) has the degree n and,
therefore, can have at most n roots, the following statement follows immediately from theo-
rem 20.
9
Note that the statements CAC 1 = D and C 1 AC = D are equivalent up to the difference between C and
C 1
. Since the transition matrix C is not specified in this definition, we ignore this difference from now on.

55
6.4 Diagonalizable matrices 6 LINEAR OPERATORS

Theorem 21. A n⇥n matrix which has n distinct real eigenvalues is diagonalizable.

However, this sufficient condition is not necessary, i.e., there exist diagonalizable matrices
with coinciding eigenvalues.

Example 6.6. 0 1
1 0 0
A = @ 0 1 0 A.
0 0 1
det(A E) = (1 )3 , i.e., = 1. However, A E = 0, so every vector in R3 is an
eigenvector for A, i.e., one can find a base consisting of eigenvectors of A. That is, A is
diagonalizable (already in the diagonal form).
0 1
2 1 0
Example 6.7. The matrix A = @ 0 2 1 A is not diagonalizable. Indeed, det(A E) =
0 0 2
(2 )3 , i.e., = 2. Then, all eigenvectors of A must satisfy the SLE given by
✓ ◆
0 1 0 0
.
0 0 1 0

However, all its solutions are proportional to the vector x = (1, 0, 0) and thus cannot form a
base in R3 . Therefore, A is not diagonalizable.

The problem with the matrix A in the example 6.7 is that the multiplicity of the root
is equal to three, i.e., the characteristic polynomial contains three copies of the corresponding
linear term, while the corresponding SLE has only one-dimensional subspace of eigenvectors.
In example 6.6, the multiplicity of the root was also equal to three, but the corresponding SLE
had a three-dimensional space of solutions.
For each eigenvalue 0 of a matrix, there are two numbers measuring, roughly speaking, the
number of eigenvectors corresponding to 0 . These numbers are called multiplicities of 0 .

Definition 23. Let 0 be a root of the characteristic polynomial for an n⇥n matrix A. The
algebraic multiplicity of 0 is the highest power k such that ( 0 ) is a factor of fA ( ). The
k

geometric multiplicity of 0 is the number of linearly independent solutions to (A 0 E)x = 0,

i.e., the geometric multiplicity is equal to n rk(A 0 E).

Lemma 22. The algebraic multiplicity of a root is greater or equal to its geometric multiplicity.

Theorem 23. A n⇥n matrix is diagonalizable if and only if all roots of fA ( ) are real and
their algebraic multiplicities are equal to their geometric multiplicities.

Proof of these two statements falls beyond the scope of this chapter.

56
6.4 Diagonalizable matrices 6 LINEAR OPERATORS

Diagonalizable matrixes are very special because they are conjugate to diagonal matrices.
Geometrically, a diagonalizable matrix is an inhomogeneous dilation: it scales the vector space,
as does a homogeneous dilation, but by a different factor in each dimension, determined by the
scale factors on each axis (diagonal entries).
Diagonalization can be used to compute the powers of a matrix A, provided that the matrix
is diagonalizable. Suppose we have found that
1
A = CDC ,

and we need to compute Ak . Diagonal matrices are especially easy to handle: their eigenvalues
and eigenvectors are known and one can raise a diagonal matrix to a power by simply raising
the diagonal entries to the same power, i.e., if D = diag( 1 , . . . , n ) then Dk = diag( k1 , . . . , kn ).
Then,
Ak = CD(C 1 C)D(C 1 . . . C)DC 1 = CDk C 1 .
That is, in order to power a diagonalizable matrix, one needs to transform it to the diagonal
form, take the desired power of the diagonal form, and transform back by using the same
transition matrix.
0 1
5 5 8
Example 6.8. Compute A20 for A = @ 8 2 8 A.
1 5 2

Solution. First, since A has three distinct eigenvalues ( 1 = 3, 2 = 2, 3 = 6), it is

diagonalizable. Next, we find the diagonalization
0 1 0 1 0 1 0 1
5 5 8 1 1 2 3 0 0 1 1 0
@ 8 2 8 A=@ 0 1 2 A⇥@ 0 2 0 A⇥@ 2 1 2 A.
1 5 2 1 1 1 0 0 6 1 0 1

Finally, 0 1 0 20 1 0 1
1 1 2 3 0 0 1 1 0
A20 =@ 0 1 2 A ⇥ @ 0 220 0 A ⇥ @ 2 1 2 A.
1 1 1 0 0 620 1 0 1
Computation of matrix’s power can be extended to define a function of a matrix for every
analytical real function10 . Let
X1
'(k) (0) k
'(x) = x
k=0
k!
be such a function. Then, having defined the convergence of matrix series, we can define
1
X '(k) (0)
'(A) = Ak ,
k=0
k!
10
A function is called analytical if it is equal to its (absolutely converging) Mc’Laurin series.

57
6.5 Exercises 6 LINEAR OPERATORS

since matrix addition and matrix multiplication are correctly defined. Additionally, if A is
diagonalizable then A = CDC 1 and
1 1
!
X ' (k)
(0) X ' (k)
(0)
'(A) = '(CDC 1 ) = (CDC 1 )k = C Dk C 1 .
k=0
k! k=0
k!

If D = diag( 1 , 2, . . . , n) then '(D) = diag('( 1 ), '( 2 ), . . . , '( n )) and

1
'(A) = C ⇥ diag('( 1 ), '( 2 ), . . . , '( n )) ⇥C .
0 1
7 8 8
Example 6.9. Compute exp(A) for A = @ 4 5 4 A.
2 4 1
Solution. First, we compute eigenvalues 1 = 1, 2 = 3, 3 = 1 and note that A is
diagonalizable because it has three distinct eigenvalues. Next,
0 1 0 1 0 1
4 2 3 1 0 0 1 2 1
A=@ 2 1 2 A⇥@ 0 3 0 A⇥@ 0 1 2 A , and
1 0 1 0 0 1 1 2 0
0 1 0 1 1 0 1
4 2 3 e
0 0 1 2 1
exp(A) = @ 2 1 2 A ⇥ @ 0 e13 0 A ⇥ @ 0 1 2 A.
1 0 1 0 0 e 1 2 0

6.5 Exercises
Problem
✓ 6.1.
◆ Find eigenvalues
✓ of the following
◆ matrices
✓ ◆ ✓ ◆
5 2 7 6 4 8 8 1
(a) (b) (c) (d)
0 1 8 1 8 70 14 8 0 6 31
1 7 7 6 2 4 5 2 2
(e)@ 7 5 1 A (f)@ 8 3 2 A (g)@ 8 1 2 A
7 7 1 4 2 6 8 8 5
0 1 0 1
4 4 4 4 8 7 1 3 0 1
B 0 C B 2 C 6 0 4
2 5 5 1 2 4
(h)B@ 2
C
A (i)B
@
C
A (j)@ 24 6 44 A
4 7 5 4 4 1 1
8 0 6
2 4 6 4 4 4 6 6
Problem 6.2. Find eigenvalues and eigenvectors of the following matrices and perform diag-
onalization,
✓ when
◆ possible. ✓ ◆ ✓ ◆ ✓ ◆
3 6 5 4 6 2 6 14
(a) (b) (c) (d)
04 7 1 0 7 0 1 3 1 0 0 81
2 6 2 3 8 3 7 0 10
(e) @ 2 2 2 A (f) @ 3 2 3 A (g) @ 0 7 4 A
2 6 2 2 8 4 0 0 3

58
 7 QUADRATIC FORMS

0 1 0 1 0 1
2 5 8 4 2 2 3 7 3
(h) @ 2 1 8 A (i) @ 1 7 2 A (j) @ 3 1 3 A
6 6 1 1 2 3 5 7 1
0 1 0 1
3 2 3 2 0 6 1 8
B 2 6 0 2 C B 8 8 1 0 C
(k) B
@
C (l) B C
2 8 2 2 A @ 6 0 7 2 A
3 6 3 2 3 3 4 5

7 Quadratic forms
Let x1 , x2 , . . . , xn be a set of variables. A monomial is a product of non-negative integer powers
of x1 , x2 , . . . , xn . For instance, x21 x2 x43 is a monomial. The degree of a monomial with respect
to the variable xi is the power, at which xi occurs in it. For instance, the degree of x21 x2 x43 with
respect to x1 is equal to two. The total degree of the monomial is the sum of its degrees with
respect to all the variables. For instance, the total degree of x21 x2 x43 is equal to seven.
A homogeneous polynomial is the sum of monomials, whose terms have the same total degree.
For example, x51 + 2x31 x22 + 9x52 is a homogeneous polynomial of degree five. The polynomial
x31 + 3x21 x32 + x72 is not homogeneous, because the sum of exponents does not match from term
to term.
A quadratic form is a homogeneous polynomial of degree two in n variables. Quadratic forms
play an important role in many branches of mathematics, including calculus and optimization
theory.

7.1 Matrix of a quadratic form

Each quadratic form in n variables can be written in a canonical form which involves matrix
notation. For instance, Q(x1 , x2 ) = x21 + 6x1 x2 + 5x22 can be written as matrix product
✓ ◆✓ ◆ ✓ ◆
1 3 x1 x1 + 3x2
(x1 , x2 ) = (x1 , x2 ) = x21 + 6x1 x2 + 5x22 .
3 5 x2 3x1 + 5x2

Note that the matrix product contains two copies of the monomial 3x1 x2 , which sum up to
6x1 x2 . In general, the matrix product of this form can be transformed as
0 10 1
a11 a12 . . . a1n x1
B a21 a22 . . . a2n C B x2 C
B CB C
(x1 x2 . . . xn ) B .. .. ... .. C B .. C =
@ . . . A @ . A
an1 an2 . . . ann xn
0 1
a11 x1 + a12 x2 + · · · + a1n xn
B a21 x1 + a22 x2 + · · · + a2n xn C
B C
= (x1 x2 . . . xn ) B .. C=
@ . A
an1 x1 + an2 x2 + · · · + ann xn

59
7.1 Matrix of a quadratic form 7 QUADRATIC FORMS

= x1 (a11 x1 + a12 x2 + · · · + a1n ) + x2 (a21 x1 + a22 x2 + · · · + a2n xn ) + · · · + xn (an1 x1 + an2 x2 + · · · +

ann xn ) = a11 x21 + (a12 + a21 )x1 x2 + · · · + a22 x22 + · · · + (a1n + an1 )x1 xn + · · · + ann x2n . Since the
coefficients aij are yet to be defined, it is convenient to assume that aij = aji and to include
the factor of 2 in the general expression of a quadratic form:
n
X X
Q(x1 , x2 , . . . , xn ) = aii x2i + 2 aij xi xj .
i=1 i<j

Definition 24. A n⇥n matrix A = (aij ) is called symmetric (anti-symmetric) if 8i, j aij = aji
(8i, j aij = aji ). In other words, A is symmetric (anti-symmetric) if A = AT (A = AT ).

Thus, every symmetric matrix defines a quadratic form and vice versa, every quadratic form
can be defined by a symmetric matrix by the identity

Q(x) = xT Ax,

where x = (x1 x2 . . . xn )T is a column vector. As a rule, one must put the full square coefficients
in the diagonal of the matrix, while the coefficients at the cross-product terms are divided by
two and placed in the corresponding cells, one above and one below the diagonal.
0 1
1 0 2
Example 7.1. Q(x1 , x2 , x3 ) = x21 + 2x22 + 3x23 + 4x1 x3 = @ 0 2 0 A
2 0 3
0 1
0 2 1
Example 7.2. Q(x1 , x2 , x3 ) = 4x1 x2 + 2x1 x3 + 10x2 x3 = @ 2 0 5 A
1 5 0

Definition 25. A quadratic form Q(x1 , x2 , . . . , xn ) is called positive definite11 if Q(x1 , x2 , . . . , xn ) >
0 for every non-zero vector (x1 , x2 , . . . , xn ) 2 Rn . Similarly, Q(x1 , x2 , . . . , xn ) is called negative
definite (positive semidefinite, negative semidefinite) if Q(x1 , x2 , . . . , xn ) < 0 (Q(x1 , x2 , . . . , xn )
0, Q(x1 , x2 , . . . , xn )  0, respectively). Otherwise, a quadratic form is called not definite.

Figure 2 gives a simple and intuitive explanation of what is a positive definite quadratic
form. First of all, if z = f (x, y) is a quadratic form then its planar sections z(y) = f (0, y) and
z(x) = f (x, 0) both have to be quadratic functions.
For instance, the 3D-graph of z = x2 + y 2 shown in part (a) is a surface with concave up
planar cross-sections for both x = 0 (z = y 2 ) and y = 0 (z = x2 ). The quadratic form z = x2 +y 2
is positive definite because it takes only positive values for non-zero pairs (x, y) and is equal to
zero if and only if both x and y are equal to zero. Now, if we don’t require z be non-zero for every
non-zero pair (x, y) then we get a non-positive definite quadratic form whose surface is shown in
part (b). An example of such function would be the function z = x2 2xy + y 2 = (x y)2 0,
which is zero for x = y = 1. Similarly, the negative-definite quadratic function z = x2 y 2
has planar cross-sections for both x = 0 (z = y 2 ) and y = 0 (z = x2 ) but this time the cross-
sections are concave down (figure 2 (c)). A non-definite quadratic form is such that some of its

60
7.2 Change of base 7 QUADRATIC FORMS

(a) (b)

(c) (d)

Figure 2: 3D shapes of (a) positive definite, (b) non-negative definite, (c) negative-definite, and
(d) not definite quadratic functions.

cross-sections are are concave up, while others are concave down. For instance, the quadratic
form z = x2 + y 2 is non-definite as z = x2 for y = 0 and z = y 2 for x = 0.
One characteristic spot on the surface of a non-definite quadratic function is called saddle
point. Saddle point has zero slope, but the surface is concave up in one direction and concave
down in the other direction. It is the point located right in the middle of the surface shown
in figure 2 (d). One can think of a saddle point as of unstable equilibrium, where it is a local
minimum in one cross-section but at the same time it is a local maximum in another cross-
section. Generic surfaces may have various numbers of maxima, minima, and saddle points, and
quadratic forms are often used as a tool to approximate the local behavior of generic surfaces.
For instance, the surface shown in figure 7.1(a) can be described as two hills (or mountains)
and two respective valleys. The ’best’ path from one valley to the other passes through the
saddle point. Saddle points play an important role in multi-dimensional calculus and in the
theory of ordinary differential equations.

7.2 Change of base

We have seen in section 6.2 that the matrix of a linear operator changes according to the rule
A 7! CAC 1 under the linear transformation of the vector space induced by the matrix C.
In this section we investigate how does the matrix of a quadratic form change under a similar
11
Do not confuse the adjective définite with the past participle defíned.

61
7.2 Change of base 7 QUADRATIC FORMS

(a) (b)

(c) (d)

Figure 3: Examples of extreme points on generic surfaces. (a) two local maxima separated by
a saddle-point, (b) a local maximum and a local minimum, no saddle point in between, (c)
one local minimum and degenerate local maxima and minima, (d) four local maxima, one local
minimum, and four saddle points.

transformation.
Consider two bases, e1 , e2 , . . . , en and e01 , e02 , . . . , e0n of the vector space V and let x = x1 e1 +
x2 e2 + · · · + xn en = x01 e01 + x02 e02 + · · · + x0n e0n be two coordinate decompositions of the vector
x over these two bases. In section 6.2 we saw that the new coordinates are expressed through
the old coordinates as
8 0
< x1 = c11 x1 + c12 x2 + . . . + c1n xn
x0 = c12 x1 + c22 x2 + . . . + c2n xn ,
: 02
xn = c1n x1 + cn2 x2 + . . . + cnn xn
where matrix C consists of the coordinates of old base vectors in the new base, i.e., x0 = Cx.
Let A and A0 be the matrices of a quadratic form in the old and new base, respectively. We
have
Q(x) = (x0 )T A0 x0 = (Cx)T A0 Cx = xT (C T A0 C)x = xT Ax.
Therefore, the matrix of a quadratic form transforms as A 7! C T AC, where C is a transition
matrix12 . In the next section we will ask to what standard form can one transform a quadratic
form by a change of base.
12
Perhaps, we should be more careful with notation because the matrix C here is inverse to the matrix C
discussed in the previous paragraph. However, since C is unknown anyway, we will keep using C instead of C 1
for simplicity of notation.

62
7.3 Canonical diagonal form 7 QUADRATIC FORMS

7.3 Canonical diagonal form

Theorem 24. Let Q(x) be a quadratic form in n variables. There exists a change of base such
that in the new base

Q(x) = x21 + x22 + · · · + x2k x2k+1 x2k+2 ··· x2k+l .

P
n P
Proof. Assume that Q(x1 , x2 , . . . , xn ) = aii x2i + 2 aij xi xj and suppose that a11 6= 0. We
i=1 i<j
will look for the change of coordinates of the form x1 = p1 y1 + p2 y2 + · · · + pn yn and xi = yi for
P
n P
i 2. We get Q(x1 , x2 , . . . , xn ) = a11 x21 + 2a12 x1 x2 + · · · + 2a1n x1 xn + aii x2i + 2 aij xi xj =
i=2 2i<j
a11 x21 + 2x1 (a12 x2 + · · · + a1n xn ) + R(x2 , . . . , xn ), where R(x2 , . . . , xn ) is a quadratic form in the
n 1 variables.
Then, Q(y) = a11 (p1 y1 +p2 y2 +· · ·+pn yn )2 +2p1 y1 (a12 y2 +· · ·+a1n yn )+R1 (y2 , . . . , yn ), where
the terms containing y2 , . . . , yn went to R1 (y2 , . . . , yn ). Then, Q(y) = a11 (p21 y12 + 2p1 p2 y1 y2 +
2p1 p3 y1 y3 + · · · + 2p1 pn y1 yn ) + 2(p1 a12 y1 y2 + p1 a13 y1 y3 + · · · + p1 a1n y1 yn ) + R2 (y2 , . . . , yn ), where
R2 (y2 , . . . , yn ) contains
p all the terms with y2 , . . . , yn . If we set p2 = a12 , p3 = a13 , . . . , pn =
a1n and p1 = |a11 | then Q(y) = ±y12 + R1 (y2 , . . . , yn ), where the sign at y12 is the same as
the sign of a11 .
Now consider the case when a11 = 0 but at least one of a1i 6= 0. Without loss of generality,
assume that a12 6= 0. Consider the change of coordinates of the form x1 = y1 + y2 , x2 = y1 y2 ,
and xi = yi for i 3. We are now back to the case when a11 6= 0 because Q(y) = (y1 + y2 )(y1
y2 ) + · · · = y12 y22 + . . . contains y12 .
Finally, if a1i = 0 for all i, we can proceed to a quadratic form with fewer number of
variables.
The pair of numbers (k, l), which are the number of positive and negative terms in the
canonical representation, respectively, is defined uniquely and will be called the signature of
the quadratic form. When there are no zero terms in the canonical form (i.e., k + l = n) and
the dimension n of the enveloping vector space is known, it is enough to know the difference
k l, which is sometimes also called signature13 . For instance, the signature (3, 1) in R4 (also
known as Minkowski space) is also called “signature 2”. We will no longer pay any attention to
the distinction between these two formulations.
The proof of this theorem contains the procedure called the completion of full squares, which
can be used to find the canonical base.

Example 7.3. Find the canonical form of

Q(x1 , x2 , x3 ) = x21 4x1 x2 + 2x1 x3 + 6x22 + 2x23

13
This second notation is found frequently in physics books

63
7.4 Sylvester’s criterion 7 QUADRATIC FORMS

Solution. Q(x1 , x2 , x3 ) = (x21 4x1 x2 +4x22 )+2x1 x3 +2x22 +2x23 = (x1 2x2 )2 +2x1 x3 +2x22 +2x23 .
Denote y1 = x1 2x2 , y2 = x2 , and y3 = x3 . Then, x1 = y1 + 2y2 and we get Q(y1 , y2 , y3 ) =
y12 +2(y1 +2y2 )y3 +2y22 +2y32 = y12 +2y1 y3 +4y2 y3 +2y22 +2y32 = (y12 +2y1 y3 +y32 )+4y2 y3 +2y22 +y32 =
(y1 + y3 )2 + 4y2 y3 + 2y22 + y32 . Now denote y1 + y3 = z1 , y2 = z2 , and y3 = z3 . We get
Q(z1 , z2 , z3 ) = z12 + 2z22 + 4z2 z3 + z32 = z12 + 2(z22 + 2z2 z3 + z32 ) z32 = z12 + 2(z2 + z3 )2 z32 .
Finally, denote t1 = z1 , t2 = z2 + z3 , and t3 = z3 . We get Q(z1 , z2 , z3 ) = t21 + 2t22 t23 . Thus,
the signature of this quadratic form is (2, 1).

Theorem 25. A quadratic form Q(x1 , x2 , . . . , xn ) is positive definite (negative definite, positive
semidefinite, negative semidefinite) if and only if its signature is (n, 0) (its signature is (0, n),
(k, 0), and (0, k), respectively, where k < n). A quadratic form Q(x1 , x2 , . . . , xn ) is not definite
if and only if its signature is (k, l), where k > 0 and l > 0.

Proof follows immediately from the definition.

7.4 Sylvester’s criterion

Sometimes the completion of least squares is not the most convenient way to check whether
or not the quadratic form is positive definite. The following theorem helps to compute the
signature of a quadratic form without cumbersome coordinate changes.

Theorem 26 (Sylvester’s criterion). Let Q(x) = xT Ax be a quadratic form in n variables where

A = AT . The form Q(x) is positive definite if and only if all upper left corner k⇥k minors of
A are positive, i.e.,
1 = a11 > 0,

a11 a12
2 = > 0,
a21 a22
a11 a12 a13
3 = a21 a22 a23 > 0, . . .
a31 a32 a33
a11 a12 . . . a1n
a21 a22 . . . a2n
= .. .. .. . > 0.
. ..
n
. .
an1 an2 . . . ann

This theorem follows from the following lemma.

Lemma 27. Let x1 = p1 y1 + p2 y2 + · · · + pn yn and xi = yi for i 2 be the change of variables

in the proof of theorem 24. All upper-left corner k⇥k minors of A do not change if p1 = 1.

Corollary 27.1. Let Q(x) = xT Ax be a quadratic form in n variables and let 1 x21 + 2 x22 +
· · · + n x2n be its diagonal representation obtained by a series of full square completion steps of

64
7.4 Sylvester’s criterion 7 QUADRATIC FORMS

the form x1 = p1 y1 + p2 y2 + · · · + pn yn , xi = yi for i 2 with p1 = 1. Assume that i 6= 0 for

all i. Then,
i
i = ,
i 1
where 0 = 1.
Example 7.4. Consider Q(x1 , x2 , x3 ) = x21 4x1 x2 + 2x1 x3 + 6x22 + 2x23 .
0 1
1 2 1
A=@ 2 6 0 A,
1 0 2

1 2
1 = 1, 2 = =6 4 = 2,
2 6
1 2 1
3 = 2 6 0 = 12 6 8= 2,
1 0 2
2 2
1 = 1,
= 2, 3 = 2 =
= 1,
1 2
in accordance with the canonical form obtained in example 7.3.
Note that every positive definite quadratic form Q(x1 , x2 , . . . , xn ) is turned into a neg-
ative definite quadratic form when multiplied by 1 (indeed, if Q(x1 , x2 , . . . , xn ) > 0 for
(x1 , x2 , . . . , xn ) 6= 0 then Q(x1 , x2 , . . . , xn ) < 0 for (x1 , x2 , . . . , xn ) 6= 0). Considering that
the matrix of a quadratic form is also multiplied by 1,
a11 a12 . . . a1n a11 a12 . . . a1n
a21 a22 . . . a2n n2
a21 a22 . . . a2n
n = .. .. .. .. = ( 1) .. .. .. .. ,
. . . . . . . .
an1 an2 . . . ann an1 an2 . . . ann
2
we get that n ( Q) = ( 1)n n (Q) = ( 1)n n (Q) because n2 is an even number if and
only if n also is. We thus get the following re-formulation of theorem 26 for negative-definite
quadratic forms.
Theorem 28. Let Q(x) = xT Ax be a quadratic form in n variables where A = AT . The form
Q(x) is negative definite if and only if the upper left corner k⇥k minors of A form an alternating
series starting with a negative number, i.e., 1 < 0, 2 > 0, 3 < 0, . . . etc.
Note that Sylvester’s criterion is a useful tool for the analysis of quadratic forms, but it is
not always applicable because some of the upper left corner minors can be equal to zero. In
the latter case one should use least squares completion.
Example 7.5. Consider Q(x1 , x2 ) = x1 x2 . The Sylvester’s criterion cannot be used as 1 = 0.
However, the linear transformation x1 = y1 y2 and x2 = y1 +y2 gives Q(y1 , y2 ) = (y1 y2 )(y1 +
y2 ) = y12 y22 , and we can safely conclude that the quadratic form Q(x1 , x2 ) is not definite.

65
7.5 Exercises 8 EUCLIDEAN VECTOR SPACES

7.5 Exercises
Problem 7.1. Use the completion of full squares to find the canonical representation of the
following quadratic forms.
(a) 4x21 + 8x1 x2 + 10x1 x3 2x22 10x2 x3 5x23

(b) x21 6x1 x2 2x1 x3 + 4x22 + 8x2 x3 + 2x23

(c) 5x21 4x1 x2 + 10x1 x3 2x22 + 10x2 x3 5x23

(d) x21 + 4x1 x2 + 10x1 x3 + 2x22 + 8x2 x3 + 5x23

(e) 2x21 4x1 x2 + 8x1 x3 4x1 x4 x22 + 4x2 x3 + 4x2 x4 x23 2x3 x4

(f) x21 6x1 x2 6x1 x3 8x1 x4 + 5x22 + 6x2 x4 + 3x23 + 6x3 x4 + 4x24

(g) x21 4x1 x2 2x1 x3 + 5x22 4x2 x3 + 4x2 x4 x23 4x3 x4 + 4x24

(h) 2x21 + 6x1 x2 2x1 x3 8x1 x4 3x22 6x2 x3 + x23 + 8x3 x4 + 5x24

Problem 7.2. Use Sylvester’s criterion to find signatures of the following quadratic forms
(a) 5x21 6x1 x2 6x1 x3 + 3x22 + 6x2 x3 + 3x23

(b) 3x21 6x1 x2 + 8x1 x3 + x22 6x2 x3 + 4x23

(c) 3x21 6x1 x2 + 6x1 x3 + 6x2 x3 + x23

(d) x21 + 8x1 x2 8x1 x3 4x22 + 8x2 x3 x23

(e) x21 2x1 x2 8x1 x3 6x1 x4 2x22 + 2x2 x3 + 4x23 + 6x3 x4 3x24

(f) 2x21 4x1 x2 4x1 x3 + 2x22 + 4x2 x3 8x2 x4 + x23 10x3 x4 + x24

(g) x21 2x1 x3 4x22 8x2 x4 3x23 4x3 x4 9x24

(h) 4x22 + 16x2 x4 3x23 20x24

8 Euclidean vector spaces

The notion of a bilinear form occupies central place in the theory of Eucledian vector spaces.
Definition 26. A bilinear form on a real vector space V is the mapping b : V ⇥ V ! R such
that
1. 8x1 , x2 , y 2 V b(x1 + x2 , y) = b(x1 , y) + b(x2 , y),

2. 8x, y1 , y2 2 V b(x, y1 + y2 ) = b(x, y1 ) + b(x, y2 ),

66
8.1 Linear spaces with dot product 8 EUCLIDEAN VECTOR SPACES

3. 8x, y 2 V, 2 R b( x, y) = b(x, y) = b(x, y).

In other words, b(x, y) is a linear function of both its arguments. The bilinear form b(x, y) is
called symmetric if
4. 8x, y 2 V b(x, y) = b(y, x).
The bilinear form b(x, y) is called positive definite if
5. 8x 2 V b(x, x) 0 and b(x, x) = 0 only if x = 0.
Similarly to what was discussed in the previous section, each bilinear form admits the
coordinate representation, in which it is expressed by using matrix products:

b(x, y) = xT By,

where x, y 2 Rn , and B is a n⇥n matrix, which is called the matrix of a bilinear form. Obviously,
the bilinear form is symmetric if and only if its matrix is symmetric. The change of base
for bilinear forms occurs similarly to what we saw for quadratic forms. If x = Cx0 then
b(x, y) = xT By = (x0 )T C T BCx0 , i.e., the matrix of a bilinear form also transforms by the rule
B 7! C T BC.
Each symmetric bilinear form b(x, y) defines a quadratic form with the same matrix by
the identity Q(x) = b(x, x). Conversely, if Q(x) = xT Ax is a quadratic form then we can
define a bilinear form by using the same matrix, i.e., b(x, y) = xT Ay. This can be done
even without matrices because since b(x + y, x + y) = b(x, x) + b(x, y) + b(y, x) + b(y, y) =
Q(x) + Q(y) + 2b(x, y) = Q(x + y) and
1
b(x, y) = (Q(x + y) Q(x) Q(y)) .
2
Thus, each quadratic form defines a symmetric bilinear form and, vice versa, each symmetric
bilinear form defines a quadratic form.

8.1 Linear spaces with dot product

A symmetric, positive definite bilinear form b(x, y) on a real vector space V is called dot product
(also called scalar product). By theorem 24, there is a base in V such that the corresponding to
b(x, y) quadratic form Q(x) (one with the same symmetric matrix) has the form x21 +x22 +· · ·+x2n ,
i.e., in some base of V , the matrix of Q(x) is the identity matrix. In the same base the matrix
of b(x, y) must also be the identity matrix, i.e., the bilinear form is expressed as14

b(x, y) = xT y = x1 y1 + x2 y2 + · · · + xn yn .

A linear vector space, along with a dot product defined on it, is called a Euclidean vector space.
The scalar product in the Euclidean vector space can be considered as a “source of geometry”.
Indeed, the colloquial dot product of vectors can be used to define lengths (by setting l(x) =
14
Note that the product of a 1⇥n (row) and n⇥1 (column) matrices gives a 1⇥1 matrix, i.e. a number.

67
8.2 Gram-Schmidt orthogonalization 8 EUCLIDEAN VECTOR SPACES

p p
Q(x) = b(x, x)) and angles (by setting the angle between vectors x and y be equal to
b(x,y)
↵(x, y) = cos 1 l(x)l(y) ).
In what follows we will discuss well-known Euclidean vector spaces with a dot product which
is so “standard” that we omit the name of the function, i.e., instead of b(x, y) we write (x, y).
Example 8.1. The n-dimensional real vector space Rn is a Euclidean vector space with respect
to the dot product defined by
(x, y) = x1 y1 + x2 y2 + · · · + xn yn .
Example 8.2. The vector space C[a, b] of continuous real functions defined on [a, b] is a Eu-
clidean vector space with respect to the dot product defined by
Zb
(f, g) = f (x) · g(x)dx.
a

Indeed, it is linear, symmetric, and positive definite because

Zb
(f, f ) = f 2 (x)dx 0,
a

and it could be equal to zero only if f (x) differs from zero on a zero-measure set, which implies
that f (x) = 0 for a continuous function.
Example 8.3. Consider the space V of discrete random numbers (a random number consists
of a finite collection of values, each endowed with a number called probability, such that all
probabilities are positive and sum up to 1). It is a linear vector space with respect to the addition
of random numbers and multiplication by scalars. There is a linear operator of expected value
acting on V . It is used to introduce variance and covariance as follows:
cov(X, Y ) = E(X · Y ) E(X) · E(Y ),
var(X) = cov(X, X) = E(X 2 ) E 2 (X).
Here, cov(X, Y ) brings Euclidean structure to the vector space V , thus establishing an associa-
tion betweenpvectors and random
p numbers, one in which the length of a random number (as of
a vector) is cov(X, X) = var(X) = (X), i.e., the length is somewhat similar to standard
deviation, while the cosine of the angle between two random numbers is their correlation. Here,
independent random numbers, which necessarily should have zero covariance, turn out to be
orthogonal, i.e., the angle between them is 90 .

8.2 Gram-Schmidt orthogonalization

Definition 27. Vectors x and y of a Euclidean vector space are called orthogonal if their dot
product is equal to zero, i.e. if (x, y) = 0. A base of V consisting of vectors e1 , e2 , . . . , en such
that (ei , ej ) = 0 for i 6= j is called an orthogonal base. An orthogonal base is called orthonormal
if, additionally, (ei , ei ) = 1 for all i.

68
8.2 Gram-Schmidt orthogonalization 8 EUCLIDEAN VECTOR SPACES

An orthogonal base consists of vectors that are perpendicular to each other. The vectors
forming an orthonormal base are, in addition to this, each of length one. Obviously, each
orthogonal base can be transformed to the orthonormal base by dividing its vector by their
lengths. It is very convenient to deal with an orthonormal base because the components of the
vector x = x1 e1 + x2 e2 + · · · + xn en in this base can be conveniently calculated by using the dot
product:
(x, ei ) = (x1 e1 + x2 e2 + · · · + xn en , ei ) = 0 + · · · + xi (ei , ei ) + · · · + 0 = xi .
If e1 , e2 , . . . , en is a (not necessarily orthogonal) base in V then the matrix G = (gij ), where
gij = (ei , ej ) is called the Gram matrix of this base. Each Gram matrix is symmetric and positive
definite because so is the dot product. The Gram matrix of an orthogonal base is diagonal;
the Gram matrix of an orthonormal base is the identity matrix. That is, if e1 , e2 , . . . , en is an
orthonormal base then (ei , ej ) = ij , where ij is so called Kronecker’s symbol such that ij = 1
if i = j and ij = 0 otherwise.
Let e1 , e2 , . . . , en be a base in V which is not orthogonal. The procedure below, called Gram-
Schmidt orthogonalization process, can be used to transform (e1 , e2 , . . . , en ) to an orthonormal
base (f1 , f2 , . . . , fn ) so that the flags of linear hulls generated by these two bases coincide, i.e.
for all i
L(e1 ) = L(f1 ),
L(e1 , e2 ) = L(f1 , f2 ),
L(e1 , . . . , ei ) = L(f1 , . . . , fi )
for all i. We will construct (f1 , f2 , . . . , fn ) in a series of steps. First, let f1 = e1 . Assume
that f1 , f2 , . . . , fk 1 have been constructed and we want to find fk such that f1 , f2 , . . . , fk are
pairwise orthogonal and L(f1 , . . . , fk ) = L(e1 , . . . , ek ). We will search for fk in a form of linear
combination of ek and already constructed vectors, i.e.,
fk = e k 1 f1 2 f2 ··· k 1 fk 1 .

We need that (fk , f1 ) = (fk , f2 ) = · · · = (fk , fk 1 ) = 0. Then,

(ek 1 f1 2 f2 ··· k 1 f k 1 , f1 ) = (ek , f1 ) 1 (f1 , f1 ) = 0,
(ek 1 f1 2 f2 ··· k 1 f k 1 , f2 ) = (ek , f2 ) 1 (f2 , f2 ) = 0,
(ek 1 f1 2 f2 ··· k 1 f k 1 , fk 1 ) = (ek , fk 1 ) 1 (fk 1 , fk 1 ) = 0.
That is,
(ek , fi )
i = .
(fi , fi )
Example 8.4. Use Gram-Schmidt orthogonalization process to find an orthogonal base in the
linear hull of the following system of vectors
0 1 0 1 0 1
1 3 1
e1 = @ 1 A , e2 = @ 1 A , e3 = @ 4 A
1 0 0

69
8.3 Projection of a vector on a linear subspace 8 EUCLIDEAN VECTOR SPACES

1 0
1
Solution. As explained above, we first set f1 = @ 1 A. Then, we look for f2 in the following
1
form
f2 = e2 1 f1 .

We have (f2 , f10

) = (e21
, f1 ) 1 (f1 , f1 ) = 0. Then, (e2 , f1 ) = 4, (f1 , f1 ) = 3, 1 = 4
3
, and
5
3
f2 = e2 4
f
3 1
=@ 1
3
A. One may want to stretch f2 three times to obtain integer components,
4
0 1 3
5
f 2 = @ 1 A.
4
Next, we look for f3 as f3 = e3 1 f1 2 f2 . Then, (f3 , f1 ) = (e3 , f1 ) 1 (f1 , f1 )
2 (f2 , f1 ) = (e3 , f1 ) 1 (f1 , f1 ) = 0. We have (e3 , f1 ) = 3, (f1 , f1 ) = 3. Therefore, 1 =
1. Similarly, (f3 , f2 ) = (e3 , f2 ) 1 (f1 , f2 ) 2 (f2 , f2 ) = (e3 , f2 ) 2 (f2 , f2 ) = 0. Here,

0 and 12 = 9/42 = 3/14. 0Then,1we have f3 = e3 + f1

3
(e
03 , f2 ) 1= 9,0(f2 ,15f2 )1= 42, 14 2
f =
13
2 14 14
1
@ 3 A @ 3 A = @ 39 A, which gives f3 = @ 3 A after stretching 14/13 times.
14 14
12 26
1 14 14
2

8.3 Projection of a vector on a linear subspace

In many parts of mathematics appears the problem of the optimal solution or, more naı̈vely, the
problem of approximation or finding the “closest point”. For instance, the linear regression in
Statistics deals with fitting a line through the points which are not on the same line; still, there
exists the “optimal” line, which the the closest one among all lines in the plane with respect to
the given set of measurements.
Below we provide a general framework in the context of Euclidean space. Suppose you
have a vector x in the Euclidean space V and a vector subspace U ✓ V generated by a set of
vectors, U = L(a1 , a2 , . . . , ak ). If x 2
/ U then it cannot be represented as a linear combination
1 a1 + 2 a2 +· · ·+ k ak . However, one can ask when the length of the difference x 1 a1 2 a2
··· k ak is minimal. This can happen if and only if the vector x 1 a1 2 a2 ··· k ak
is orthogonal15 to the subspace U . Denote the difference vector by n, i.e.,

n=x 1 a1 2 a2 ··· k ak .

It will be called the normal vector16 . The normal vector must be orthogonal to each of the
15
Can you explain, why? Note that your colloquial reasoning such as “the shortest path is the perpendicular”
in general fails to work.
16
Here “normal” is the opposite to “tangent”.

70
8.3 Projection of a vector on a linear subspace 8 EUCLIDEAN VECTOR SPACES

vectors in U , including a1 , a2 , . . . , ak . Then, we have

8
> (n, a1 ) = (x, a1 )
> 1 (a1 , a1 ) 2 (a2 , a1 ) ··· n (ak , a1 ) =0
<
(n, a2 ) = (x, a2 ) 1 (a1 , a2 ) 2 (a2 , a2 ) ··· n (ak , a2 ) =0
.
>
> . . .
:
(n, ak ) = (x, ak ) 1 (a1 , ak ) 2 (a2 , ak ) ··· n (ak , ak ) =0
Therefore, 8
>
> 1 (a1 , a1 ) + + · · · + n (ak , a1 ) = (x, a1 )
2 (a2 , a1 )
<
2 (a2 , a2 ) + · · · + n (ak , a2 ) = (x, a2 )
1 (a1 , a2 ) +
,
>
> ...
:
1 (a1 , ak ) + 2 (a2 , ak ) + · · · + n (ak , ak ) = (x, ak )
that is, the set of coefficients 1 , 2 , . . . , k is obtained from solving the system of linear equa-
tions whose matrix is the Gram matrix of a1 , a2 , . . . , ak and the column of free terms consists
of dot products of x with a1 , a2 , . . . , ak .
Example 8.5. For the vectors x, e1 , and e2 below, find the projection of the vector x onto the
linear hull of e1 and e2 . Evaluate the distance between the endpoint of x and the linear hull.
0 1 0 1 0 1
1 2 2
x = @ 7 A , e1 = @ 1 A , e2 = @ 0 A
1 2 6
Solution. Compute the Gram matrix: (e1 , e1 ) = 9, (e1 , e2 ) = 16, (e2 , e2 ) = 40, (x, e1 ) = 11,
(x, e2 ) = 8. Then,
✓ ◆ ✓ ◆ ✓ ◆
9 16 11 2 8 14 1 4 7
! ! !
16 40 8 16 40 8 16 40 8
✓ ◆ ✓ ◆ ✓ ◆
1 4 7 1 4 7 1 0 3
! ! .
0 104 104 0 1 1 0 1 1
Therefore, 1 = 3, 2 = 1, and
0 1 0 1 0 1
2 2 4
1 e1 + 2 e2 = 3@ 1 A @ 0 A = @ 3 A.
2 6 0
0 1 0 1 0 1
1 4 3
n = @ 7 A @ 3 A = @ 4 A,
1 0 1
and d2 = 32 + 42 + 12 = 26.
Example 8.6. For the vectors x, e1 , e2 , and e3 below, find the projection of the vector x onto
the linear hull of e1 , e2 , and e3 . Evaluate the distance between the endpoint of x and the linear
hull. 0 1 0 1 0 1 0 1
1 2 4 3
B 6 C B C B C B C
x=B C , e1 = B 2 C , e2 = B 4 C , e3 = B 4 C .
@ 1 A @ 1 A @ 3 A @ 3 A
1 3 5 5

71
8.4 Orthogonal complement 8 EUCLIDEAN VECTOR SPACES

Solution. Compute the Gram matrix: (e1 , e1 ) = 18, (e1 , e2 ) = 34, (e1 , e3 ) = 32, (e2 , e2 ) = 66,
(e2 , e3 ) = 62,(e3 , e3 ) = 59, (x, e1 ) = 8, (x, e2 ) = 18, (x, e3 ) = 19. Then,
0 1 0 1
18 34 32 8 9 17 16 4
@ 34 66 62 18 A ! @ 17 33 31 9 A 2[1] [2] ! ...
32 62 59 19 32 62 59 19
0 1 0 1
1 0
B 2 C B 4 C
1 e1 + 2 e2 + 3 e3 =B
@
C, n = B C , and
3 A @ 2 A
1 2
d2 = 24.

Example 8.7. For the function y = x3 , find its projection onto the linear space generated by
1, x and x2 with respect to Euclidean structure defined by

Z1
(f, g) = f (x)g(x)dx
0
.
R1 R1
Solution. (1, 1) = 1, (1, x) = 0 xdx = 1/2, (x, x) = (1, x2 ) = 0 x2 dx = 1/3, (1, x3 ) =
R1 R1 R1
(x, x2 ) = 0 x3 dx = 1/4, (x2 , x2 ) = (x, x3 ) = 0 x4 dx = 1/5, (x2 , x3 ) = 0 x5 dx = 1/6.
0 1 0 1 0 1
1 12 13 14 12 6 4 3 12 6 4 3
@ 1 1 1 1 A ! @ 30 20 15 12 A ! @ 30 20 15 10 A ! . . .
2 3 4 5
1 1 1 1
3 4 5 6
40 30 24 20 1 1 .9 .8

1 = .05, 1 = .6, 2 = 1.5,

i.e., the projection of y = x3 onto the linear space generated by 1, x and x2 is y = .05 .6x+1.5x2 .
Spend some time with your graphic calculator to draw graphs of these two functions.

8.4 Orthogonal complement

Euclidean structure on a linear vector space gives rise to the notion of orthogonal subspaces,
which in our colloquial understanding corresponds to perpendicular planes. Let V be a Eu-
clidean vector space and let U ✓ V be its subspace.

Definition 28. The orthogonal complement to U in V is a subset

U ? = {x 2 V |8y 2 U : (x, y) = 0},

i.e., U ? consists of all vectors of V that are orthogonal to every vector in U .

72
8.4 Orthogonal complement 8 EUCLIDEAN VECTOR SPACES

For instance, if U is the line defined by x = y in R2 then U ? is the line x + y = 0, which is

perpendicular to the original line. If U is the line defined by x = y = z in R3 then U ? is the
plane that passes through the origin at 90 to the original line.
It follows immediately from this definition that U ? is a correctly defined subspace of V
because if x1 and x2 are such that 8y 2 U : (x1 , y) = (x2 , y) = 0 then x1 ± x2 also have the
same property due to linear nature of the dot product.
Theorem 29.
dim(U ) + dim(U ? ) = dim(V )
Proof. One can choose an arbitrary base e1 , . . . , ek , where k = dim(U ), in U and complement
it by vectors ek+1 , . . . , en so that e1 , . . . , en is a base of V . Applying the Gram-Schmidt or-
thogonalization procedure, we get an orthogonal base e01 , . . . , e0n of V such that L(e01 , . . . , e0k ) =
L(e1 , . . . , ek ) = U . Let x be a vector that is orthogonal to all vectors in U and let x =
x1 e01 + x2 e02 + · · · + xn e0n be its decomposition over the base of V . Then, (x, e0i ) = xi = 0 for all
1  i  k. Therefore, x = xk+1 e0k+1 + · · · + xn e0n , i.e., e0k+1 , . . . , e0n is the base of U ? . Therefore,
dim(U ? ) = n k = n dim(U ).
?
Corollary 29.1. U ? =U
?
⇣ It is ⌘obvious that U is a subset of U
Proof. . By the previous theorem, we get that
?

? ?
dim U ? = dim(V ) dim(U ? ) = dim(V ) (dim(V ) dim(U )) = dim(U ), i.e., U = U ? .

Theorem 30. If U1 ✓ U2 then U2? ✓ U1? .

Proof. If x 2 U2? then (x, y) = 0 for all y 2 U2 . Since every vector of U1 also belongs to U2 , we
have x 2 U1? , i.e., U2? ✓ U1? .
Example 8.8. Find the 0 orthogonal
1 complement
0 to the linear vector space generated by e1 and
1
1 5
e2 in R3 , where e1 = @ 3 A and e2 = @ 1 A.
2 10
Solution. If x = (x1 , x2 , x3 ) be a vector in the orthogonal complement, then
⇢
x1 + 3x2 2x3 = 0
,
5x1 x2 10x3 = 0
as x must be orthogonal to both e1 and e2 . We get
✓ ◆ ✓ ◆ ✓ ◆ ✓ ◆
1 3 2 1 3 2 1 3 2 1 0 2
! ! ! .
5 1 10 0 16 0 0 1 0 0 1 0
The free variable is x3 . By setting x3 = 1, we get x1 = 2 and x2 = 0. Hence, the vectors
that belong to the orthogonal complement 0 must
1 be proportionate to x, i.e., the orthogonal
2
complement is the line generated by x = @ 0 A.
1

73
8.5 Intersection and sum of vector spaces 8 EUCLIDEAN VECTOR SPACES

8.5 Intersection and sum of vector spaces

Given two linear subspaces, U1 and U2 , of a vector space V , one may want to consider their
union and intersection, U1 [ U2 and U1 \ U2 . While the latter is a correctly defined linear
subspace (if x, y 2 U1 \ U2 then x, y 2 U1 and x, y 2 U2 , and thus x + y 2 U1 and x + y 2 U2 ,
i.e., x + y 2 U1 \ U2 ), the former is not a linear subspace because x 2 U1 and y 2 U2 does not
imply that x + y belongs to either of the two subspaces.
However, one can define the sum U1 + U2 of two linear subspaces to be not precisely the
union, but the linear hull of U1 [ U2 . This way we “force” it to be a linear subspace. Following
this definition, U1 + U2 is a bigger set than U1 [ U2 , but it is the smallest of all linear subspaces
of V that contain U1 [ U2 .
If U1 and U2 are defined by their bases, it is easy to find the base of U1 + U2 . Indeed, if U1 =
L(e1 , e2 , . . . , ek ) and U2 = L(f1 , f2 , . . . , fl ) then U1 +U2 is generated by e1 , e2 , . . . , ek , f1 , f2 , . . . , fl .
If they are not linearly independent, we already know how to select a base (section 2.4).

Example
0 1 8.9. Find
0 the sum
1 of the
0 vector
1 spaces U1 = e2 ) and U2 = L(f1 , f2 ), where
0L(e1 ,1
2 0 1 2
B 1 C B 1 C B 1 C B 1 C
e1 = B C B C B C B
@ 1 A, e2 = @ 1 A, f1 = @ 2 A, and f2 = @ 3 A.
C

0 1 1 2
Solution. The problem is equivalent to building a base from a set vectors, i.e., we have to
examine whether or not e1 , e2 , f1 , f2 are linearly independent and, if not, choose a base of their
linear hull. 0 1 0 1
2 0 1 2 1 1 1 1
B 1 1 1 1 C B 4 C
B C!B 0 2 1 C!
@ 1 1 2 3 A @ 0 2 1 4 A
0 1 1 2 0 1 1 2
0 1 0 1
1 1 1 1 1 1 1 1
B 0 1 1 2 C B 2 C
!B C!B 0 1 1 C.
@ 0 0 1 0 A @ 0 0 1 0 A
0 0 3 0 0 0 0 0
In this case, the vectors e1 , e2 , f1 , f2 are linearly dependent, but e1 , e2 , f1 form a base, so the
sum of two 2-dimensional subspaces U1 and U2 is a three dimensional subspace spanned on
e1 ,e2 , and f1 . It means that U1 and U2 are “planes” in 4D situated so that they have a common
“line” and U1 + U2 is three-dimensional.

Theorem 31.
dim(U1 + U2 ) = dim(U1 ) + dim(U2 ) dim(U1 \ U2 ).

Proof. Chose a base in U1 \ U2 . One can add vectors to this base to make it the base of U1 since
U1 \ U2 ✓ U1 . Similarly, one can add vectors to the base of U1 \ U2 to make it the base of U2
as U1 \ U2 ✓ U2 , too. If we now combine the two bases, but without counting the base vectors
of U1 \ U2 twice, we get the base of U1 + U2 , which implies that dim(U1 + U2 ) + dim(U1 \ U2 ) =
dim(U1 ) + dim(U2 ).

74
8.5 Intersection and sum of vector spaces 8 EUCLIDEAN VECTOR SPACES

In the particular case when dim(U1 \ U2 ) = 0, which is possible only when U1 \ U2 = {0},
i.e., the zero vector is the only intersection of U1 and U2 , the sum of vector spaces is called
a direct sum and is denoted by U1 U2 . For the direct sum of vector spaces, the dimension
formula becomes
dim(U1 U2 ) = dim(U1 ) + dim(U2 ).
Computations are not that straightforward for the intersection. Indeed, if U1 and U2 are
the same as in example 8.9, the base vectors of U1 \ U2 could be neither of e1 ,e2 , f1 , or f2 .
However, it can be found very easily by using orthogonal complements and corollary 8.4.
Theorem 32.
(U1 + U2 )? = U1? \ U2? .
Proof. Since U1 ✓ U1 [U2 ✓ U1 +U2 , we have (U1 +U2 )? ✓ U1? . Similarly, we have (U1 +U2 )? ✓
U2? and, therefore, (U1 + U2 )? ✓ U1? \ U2? . On the other hand, if x 2 U1? \ U2? then (x, y1 ) = 0
for every y1 2 U1 and also (x, y2 ) = 0 for every y2 2 U2 . Therefore, U1? \ U2? ✓ (U1 + U2 )? , i.e.,
it is actually an equality.
Theorem 33.
(U1 \ U2 )? = U1? + U2? .
Proof. Similar to the proof of theorem 8.5.
Example 8.10. Find the intersection of vector spaces U1 = L(e1 , e2 ) and U2 = L(f1 , f2 ), where
e1 , e2 , f1 , and f2 are the same as in example 8.9.
Solution. First, let us find U1? and U2? .
✓ ◆ ✓ ◆ ✓ 1
◆
2 1 1 0 2 0 2 1 1 0 1
! ! 2
0 1 1 1 0 1 1 1 0 1 1 1
0 1 0 1
1 1
B 1 C B 2 C
The base of U1? is a1 = B C B C
@ 1 A and a2 = @ 0 A. Similarly,
0 2
✓ ◆ ✓ ◆
1 1 2 1 1 1 2 1
! !
2 1 3 2 0 3 1 4
✓ ◆ ✓ ◆
3 3 6 3 3 0 5 1
!
0 3 1 4 0 3 1 4
0 1 0 1
5 1
B 1 C B C
The base of U2? is b1 = B C B 4 C
@ 3 A and b2 = @ 0 A. Now we find the base of their sum and,
0 3
? ?
simultaneously, the base of U1 + U2 .
?
0 1 0 1 0 1
1 1 1 0 1 1 1 0 1 1 1 0
B 1 2 0 2 C B 1 2 C B 2 C
B C!B 0 1 C!B 0 1 1 C!
@ 5 1 3 0 A @ 0 6 2 0 A @ 0 0 8 12 A
1 4 0 3 0 3 1 3 0 0 2 3

75
8.6 Exercises 8 EUCLIDEAN VECTOR SPACES

0 1
2 2 2 0 0 1 0 1
B 0 C 2 2 0 3 2 0 0 2
2 2 4 C
!B
@ 0 ! @ 0 2 0 1 A ! @ 0 2 0 1 A.
0 2 3 A
0 0 2 3 0 0 2 3
0 0 0 0
0 1
2
? B 1 C
Thus, the base of U1? + U2? = U1 \ U2 is x = B @ 3
C, which is the same as the vector
A
2
f2 , and which turns out to be the direction vector of the line that is common to both U1 and
U2 .

8.6 Exercises
Problem 8.1. Use Gram-Schmidt orthogonalization process to find an orthogonal base in the
linear hull of the following system of vectors
0 1 0 1 0 1
1 1 4
(a) e1 = @ 1 A, e2 = @ 1 A, e3 = @ 2 A
3 4 1
0 1 0 1 0 1
3 1 1
(b) e1 = @ 2 A, e2 = @ 1 A, e3 = @ 2 A
1 3 1
0 1 0 1 0 1
3 1 0
(c) e1 = @ 2 A, e2 = @ 1 A, e3 = @ 3 A
2 3 1
0 1 0 1 0 1
2 4 3
(d) e1 = @ 1 A, e2 = @ 0 A, e3 = @ 2 A
0 1 1
0 1 0 1 0 1
2 2 1
B 2 C B 3 C B 2 C
(e) e1 = B C B C B
@ 3 A, e2 = @ 3 A, e3 = @ 2 A
C

1 2 2
0 1 0 1 0 1
3 4 4
B 4 C B 1 C B 2 C
(f) e1 = B C B C B C
@ 1 A, e2 = @ 3 A, e3 = @ 3 A
2 3 1

76
8.6 Exercises 8 EUCLIDEAN VECTOR SPACES

0 1 0 1 0 1 0 1
3 0 1 2
B 1 C B 1 C B 1 C B 4 C
B C B C B C B C
(g) e1 = B
B 3 C, e 2 = B
C B 4 C, e 3 = B
C B 1 C, e 4 = B
C B 3 C
C
@ 1 A @ 1 A @ 0 A @ 2 A
1 3 3 4
0 1 0 1 0 1 0 1
1 4 3 2
B 0 C B 4 C B 2 C B 3 C
B C B C B C B C
(h) e1 = B
B 1 C, e 2 = B
C B 2 C, e 3 = B
C B 3 C, e 4 = B
C B 2 C
C
@ 3 A @ 2 A @ 1 A @ 1 A
3 4 2 0
Problem 8.2. Find the Gram matrix of the following vectors
0 1 0 1 0 1
3 1 2
(a) e1 = @ 1 A, e 2 = @ 1 A, e 3 = @ 1 A
1 2 3
0 1 0 1 0 1
2 1 2
(b) e1 = @ 2 A, e 2 = @ 0 A, e 3 = @ 1 A
2 1 1
0 1 0 1 0 1
1 3 0
(c) e1 = @ 3 A, e 2 = @ 2 A, e 3 = @ 1 A
1 1 0
0 1 0 1 0 1
1 3 3
(d) e1 = @ 1 A, e 2 = @ 2 A, e 3 = @ 1 A
2 2 1
0 1 0 1 0 1 0 1
3 2 1 3
B 2 C B C B C B C
(e) e1 = B C, e 2 = B 2 C, e 3 = B 1 C, e 4 = B 1 C
@ 2 A @ 2 A @ 4 A @ 3 A
2 1 1 3
0 1 0 1 0 1 0 1
1 1 0 1
B 2 C B C B C B C
(f) e1 = B C, e 2 = B 3 C, e 3 = B 2 C, e 4 = B 2 C
@ 4 A @ 2 A @ 0 A @ 3 A
3 1 1 3
0 1 0 1 0 1 0 1
0 3 2 1
B 1 C B C B C B C
(g) e1 = B C, e 2 = B 1 C, e 3 = B 1 C, e 4 = B 1 C
@ 3 A @ 3 A @ 2 A @ 4 A
2 3 1 4

77
8.6 Exercises 8 EUCLIDEAN VECTOR SPACES

0 1 0 1 0 1 0 1
2 4 0 3
B 4 C B 2 C B 1 C B 0 C
(h) e1 = B C, e 2 = B
@ 1 A @
C, e 3 = B C, e 4 = B C
3 A @ 2 A @ 1 A
1 0 2 1
Problem 8.3. For the vectors x, e1 , e2 , . . . , ek below, find the projection of the vector x onto
the linear hull of e1 , e2 , . . . , ek . Evaluate the distance between the endpoint of x and the linear
hull.
0 1 0 1 0 1
1 1 2
(a) x = @ 6 A, e1 = @ 0 A, e2 = @ 1 A
2 0 1
0 1 0 1 0 1
2 4 1
(b) x = @ 7 A, e1 = @ 2 A, e2 = @ 1 A
4 4 1
0 1 0 1 0 1
3 3 2
(c) x = @ 3 A, e1 = @ 3 A, e2 = @ 1 A
3 0 1
0 1 0 1 0 1
4 1 0
(d) x = @ A
2 , e1 = @ A
5 , e2 = @ 1 A
3 4 1
0 1 0 1 0 1 0 1
3 4 1 2
B 4 C B 0 C B 3 C B 5 C
(e) x = B C B C B
@ 4 A, e1 = @ 3 A, e2 = @ 3 A, e3 = @ 4 A
C B C

2 3 3 4
0 1 0 1 0 1 0 1
1 5 0 3
B 6 C B C B C B C
(f) x = B C, e 1 = B 2 C, e 2 = B 1 C, e 3 = B 2 C
@ 3 A @ 1 A @ 1 A @ 0 A
3 3 3 4
0 1 0 1 0 1 0 1
4 4 5 1
B 2 C B C B C B C
(g) x = B C, e 1 = B 1 C, e 2 = B 4 C, e 3 = B 4 C
@ 0 A @ 5 A @ 5 A @ 0 A
2 4 5 1
0 1 0 1 0 1 0 1
5 2 2 1
B 4 C B C B C B C
(h) x = B C, e 1 = B 4 C, e 2 = B 1 C, e 3 = B 5 C
@ 3 A @ 3 A @ 3 A @ 3 A
4 0 0 0

Problem 8.4. Find the orthogonal complement to the linear vector space generated by the
following vectors in R4

78
8.6 Exercises 8 EUCLIDEAN VECTOR SPACES

0 1 0 1
3 1
B 1 C B 1 C
(a) a1 = B
@
C, a = B C
5 A 2 @ 1 A
3 7
0 1 0 1
1 1
B 1 C B 2 C
(b) a1 = B
@
C , a2 = B C
6 A @ 12 A
7 8
0 1 0 1
1 1
B 2 C B C
(c) a1 = B C , a2 = B 5 C
@ 5 A @ 2 A
4 11
0 1 0 1
4 2
B 3 CC B 1 C
(d) a1 = B
@ A , a2 = B
@
C
18 4 A
5 5
0 1 0 1 0 1
10 2 2
B 5 C B C B C
(e) a1 = B C , a2 = B 2 C , a3 = B 4 C
@ 4 A @ 1 A @ 5 A
8 8 8
0 1 0 1 0 1
7 7 3
B 8 C B 8 C B 1 C
(f) a1 = B
@
C, a = B C, a = B C
4 A 2 @ 5 A 3 @ 5 A
13 16 17

Problem 8.5. Find the intersection of linear vector spaces U1 = L(e1 , e2 , . . . , ek ) and U2 =
L(f1 , f2 , . . . , fl ) for the vector sets listed below.
0 1 0 1
9 7
(a) a1 = @ 0 A, a2 = @ 8 A,
0 91 0 31
4 4
b1 = @ 2 A, b2 = @ 6 A
3 11
0 1 0 1
1 5
(b) a1 = @ 3 A, a2 = @ 5 A,
0 31 0 3 1
0 1
b1 = @ A
0 , b2 = @ 3 A
1 2

79
8.6 Exercises 8 EUCLIDEAN VECTOR SPACES

0 1 0 1
3 1
(c) a1 = @ 1 A, a2 = @ 3 A,
0 31 0 11
7 10
b1 = @ 9 A, b2 = @ 2 A
5 10
0 1 0 1
1 2
(d) a1 = @ 9 A , a2 = @ 6 A ,
0 7 1 0 1 1
4 0
b1 = @ 4 A, b2 = @ 4 A
1 5
0 1 0 1 0 1
1 1 4
B C
4 C B C B C
(e) a1 = B , a = B 0 C , a3 = B 5 C ,
@ 5 A 2 @ 3 A @ 9 A
4 4 6
0 1 0 1 0 1
10 6 0
B 11 C B C B C
b1 = B C, b2 = B 5 C, b3 = B 4 C
@ 6 A @ 3 A @ 1 A
12 7 1
0 1 0 1 0 1
2 1 4
B 4 C B C B C
(f) a1 = B C, a2 = B 6 C, a3 = B 4 C,
@ 0 A @ 1 A @ 2 A
4 3 3
0 1 0 1 0 1
5 4 3
B 4 C B C B C
b1 = B C, b2 = B 4 C, b3 = B 4 C
@ 6 A @ 6 A @ 2 A
2 12 8
0 1 0 1 0 1
8 8 4
B 4 C B C B C
(g) a1 = B C, a2 = B 7 C, a3 = B 8 C,
@ 1 A @ 1 A @ 4 A
1 5 8
0 1 0 1 0 1
0 8 10
B 2 C B C B 4 C
b1 = B C, b2 = B 7 C, b3 = B C
@ 1 A @ 1 A @ 5 A
2 5 4
0 1 0 1 0 1
2 7 4
B 4 C B C B C
(h) a1 = B C, a2 = B 4 C, a3 = B 1 C,
@ 2 A @ 4 A @ 5 A
6 4 1

80
8.6 Exercises 8 EUCLIDEAN VECTOR SPACES

0 1 0 1 0 1
10 11 4
B 1 C B 1 C B 2 C
b1 = B
@ 4 A
C, b2 = B
@
C, b 3 = B C
0 A @ 3 A
6 10 1

81
 9 ANSWERS TO PROBLEMS

9 Answers to problems

[1.1] (a) x1 = 2, x2 = 2, x3 = 1, x4 = 5. (b) x1 = 2, x2 = 3, x3 = 1, x4 = 2. (c)

x1 = 2, x2 = 0, x3 = 1, x4 = 4, x5 = 4. (d) x1 = 0, x2 = 4, x3 = 0, x4 = 3. (e) x1 = 1,
x2 = 2, x3 = 2, x4 = 2. (f) x1 = 4, x2 = 2, x3 = 4, x4 = 3. (g) x1 = 0, x2 = 4, x3 = 1,
x4 = 2. (h) x1 = 0, x2 = 0, x3 = 4, x4 = 3. (i) x1 = 3, x2 = 0, x3 = 1, x4 = 4. (j)
x1 = 3, x2 = 3, x3 = 0, x4 = 1.
[2.1] No answer given.
[2.2] (a) 1 = 16, 2 = 1, 3 = 14. (b) 1 = 3, 2 = 2, 3 = 0. (c) x1 = 3, x2 = 1,
x3 = 1, x4 = 1. (d) x1 = 1, x2 = 1, x3 = 2, x4 = 2. (e) x1 = 2, x2 = 5, x3 = 8,
x4 = 6.
[3.1] (a) 1 (b) 1 (c) 4 (d) 2 (e) 1 (f) 2 (g) 2 (h) 1 (i) 2 (j) 2
[3.2]
0 1 0 1 0 1
0 2 6
B 3 C B 3 C B 7 C
(a) x = B C B
@ 0 A+ 1@ 1 A+ 2@ 0 A
C B C

0 0 1
0 1 0 1 0 1
5 4 1
B 5 C B C B C
(b) x = B C+ 1B 3 C+ 2B 2 C
@ 0 A @ 1 A @ 0 A
0 0 1
0 1 0 1 0 1
2 2 1
B 3 C B C B C
(c) x = B C+ 1B 2 C+ 2B 3 C
@ 0 A @ 1 A @ 0 A
0 0 1
0 1 0 1 0 1
2 0 3
B 0 C B 4 C B 5 C
B C B C B C
(d) x = B C B
B 0 C+ 1B 4 C+ 2B 8 C
C B C
@ 0 A @ 1 A @ 0 A
0 0 1
0 1 0 1 0 1
0 6 6
B 2 C B 6 C B 1 C
B C B C B C
(e) x = B 3 C + 1 B 5 C + 2 B
B C B C
B 2 C
C
@ 0 A @ 1 A @ 0 A
0 0 1

82
 9 ANSWERS TO PROBLEMS

0 1 0 1 0 1
7 5 5
B 1 C B 4 C B 5 C
B C B C B C
(f) x = B
B 0 C B
C+ 1B 4 C B
C+ 2B 6 C
C
@ 0 A @ 1 A @ 0 A
0 0 1
0 1 0 1 0 1 0 1
1 2 6 1
B 7 C B 5 C B 3 C B 2 C
B C B C B C B C
(g) x = B
B 0 C+
C
B
1B 1 C
C + 2
B 0 C+ 3B 0
B C B
C
C
@ 0 A @ 0 A @ 1 A @ 0 A
0 0 0 1
0 1 0 1 0 1 0 1
2 2 5 3
B 2 C B C
4 C B C B C
B C B B 7 C B 5 C
(h) x = B
B 0 C+ 1B
C
B 1 C+ 2B 0 C+ 3B
C B C
B 0 C
C
@ 0 A @ 0 A @ 1 A @ 0 A
0 0 0 1
0 1 0 1 0 1 0 1
4 1 7 1
B 2 C B 3 C B 4 C B 0 C
B C B C B C B C
(i) x = B C
B 0 C+
B
1B 1 C B C
C+ 2B 0 C+ 3B 0
B C
C
@ 0 A @ 0 A @ 1 A @ 0 A
0 0 0 1
0 1 0 1 0 1 0 1
1 2 1 7
B 1 C B 5 C B 1 C B 0 C
B C B C B C B C
(j) x = B C
B 0 C+
B
1B 1 C
C + 2
B 0 C+ 3B 0
B C B
C
C
@ 0 A @ 0 A @ 1 A @ 0 A
0 0 0 1

[4.1] (a) 1152 (b) 4 (c) 96 (d) 288 (e) 48 (f) 6 (g) 240 (h) 9 (i) 4 (j) 48 (k) 10 (l) 144

[4.2] (a) 2 (b) 2 (c) 4 (d) 2 (e) 2 (f) 3

[4.3] (a) x1 = 1, x2 = 1, x3 = 4. (b) x1 = 3, x2 = 2, x3 = 3. (c) x1 = 4, x2 = 1,
x3 = 5. (d) x1 = 2, x2 = 4, x3 = 2, x4 = 5. (e) x1 = 5, x2 = 0, x3 = 4, x4 = 2. (f)
x1 = 1, x2 =03, x3 = 2. (g) x1 = 1, x2 =1 2, x3 = 0. (h) x1 = 1, x2 = 2, x3 = 1, x4 = 1.
2 3 11 7 12 0 1
B 9 C 5 1 5 3
B 9 12 5 5 C B 1 8 2 1 C
[5.1] (a)B
B 1 1 5 3 5 CC (b)B
@
C
A
@ 1 0 1 0 0
1 1 1 0 A
11 5 10 6
2 3 2 2 1
0 1 0 1
4 11 2 12 1 1 2 2
B 2 6 1 6 CC B 10 1 7 1 C
(c)B
@ 1 A (d)B@
C
0 1 0 8 1 5 0 A
3 4 2 5 0 3 4 6

83
 9 ANSWERS TO PROBLEMS

0 1
0 1 1 2 1 1
1 4 2 B 10 12 11 11 C
(e)@ 2 0 1 A (f)B
@ 3
C
1 4 3 A
0 3 1
7 10 7 8
0 1
0 1 3 1 6 10 10
1 2 0 B 2 1 3 5 5 C
B C
(g)@ 0 5 3 A (h)B
B 5 3 5 8 8 CC
2 12 5 @ 8 6 5 5 6 A
7 4 7 12 12
0 1 0 1
3 9 6 10 7 6 2 12 1 8
B 2 9 5 6 2 C B 2 2 1 7 6 C
B C B C
(i)B
B 1 0 0 1 2 C
C (j)B
B 2 1 2 2 3 C
C
@ 1 5 4 4 2 A @ 1 1 0 3 3 A
0 11 5 11 3 2 1 8 7 2
0 1
0 1 3 6 4 6
1 12 10 B 1 23 36 57 C
[5.2] (a)@ 12 12 28 A (b)B
@ 27 45 18 26 A
C
8 1 10
2 17 23 37
0 1
0 1 2 4 3
4 17 26 22 20 B 2 16
B 1 C
1 14 14 18 14 C B C
(c)B
@
C B
(d)B 2 9 3 CC
8 39 27 37 25 A @ 1 7 6 A
9 48 70 61 55
4 3 8
0 1
0 1 7 19 0 20 12
1 1 2 B 7 15 2 15 10 C
(e)@ 0 2 2 A (f)B
@ 26
C
31 22 22 28 A
7 7 13
20 11 29 2 18

[6.1] (a) 1 = 7, 2 = 6 (b) 1 = 1, 2 = 1 (c) 1 = 0, 2 = 4 (d) 1 = 6, 2 = 5

(e) 1 = 1, 2 = 6, 3 = 2 (f) 1 = 2, 2 = 7, 3 = 6 (g) 1 = 7, 2 = 3, 3 = 5
(h) 1 = 4, 2 = 2, 3 = 2, 4 = 1 (i) 1 = 4, 2 = 1, 3 = 5, 4 = 2 (j) 1 = 6,
2 = 2, 3 = 2
[6.2]
✓ ◆ ✓ ◆ ✓ ◆ ✓ ◆
1 1 3 6 3 1 1 0
(a) ⇥ ⇥ =
2 3 4 7 2 1 0 3
✓ ◆ ✓ ◆ ✓ ◆ ✓ ◆
1 2 5 4 1 2 5 0
(b) ⇥ ⇥ =
0 1 0 7 0 1 0 7
✓ ◆ ✓ ◆ ✓ ◆ ✓ ◆
3 2 6 2 1 2 4 0
(c) ⇥ ⇥ =
1 1 3 1 1 3 0 3
✓ ◆ ✓ ◆ ✓ ◆ ✓ ◆
1 0 6 14 1 0 6 0
(d) ⇥ ⇥ =
0 1 0 8 0 1 0 8

84
 9 ANSWERS TO PROBLEMS

0 1 0 1 0 1 0 1
1 0 1 2 6 2 2 1 1 0 0 0
(e) @ 1 1 1 A⇥@ 2 2 2 A⇥@ 1 1 0 A=@ 0 2 0 A
0 1 1 2 6 2 1 1 1 0 0 4
0 1 0 1 0 1 0 1
1 1 1 3 8 3 1 1 1 2 0 0
(f) @ 1 1 0 A⇥@ 3 2 3 A⇥@ 1 0 1 A=@ 0 6 0 A
1 0 1 2 8 4 1 1 2 0 0 1
0 1 0 1 0 1 0 1
1 0 0 7 0 10 1 0 0 7 0 0
(g) @ 0 0 1 A⇥@ 0 7 4 A⇥@ 0 1 1 A=@ 0 3 0 A
0 1 1 0 0 3 0 1 0 0 0 7
0 1 0 1 0 1 0 1
2 2 1 2 5 8 2 1 3 1 0 0
(h) @ 2 1 2 A⇥@ 2 1 8 A⇥@ 2 1 2 A=@ 0 3 0 A
1 1 0 6 6 1 1 0 2 0 0 4
0 1 0 1 0 1 0 1
71 65 6 4 2 2 24 1 142 5 0 0
(i) @ 1 2 2 ⇥A @ 1 7 A
2 ⇥ @ 25 1 148 A = @ 0 4 0 A
12 11 1 1 2 3 13 1 77 0 0 5
0 1 0 1 0 1 0 1
1 0 1 3 7 3 3 1 1 2 0 0
(j) @ 1 1 0 A⇥@ 3 1 3 A⇥@ 3 0 1 A=@ 0 6 0 A
3 1 3 5 7 1 2 1 1 0 0 1
0 1 0 1 0 1 0 1
1 1 0 1 3 2 3 2 1 1 1 1 2 0 0 0
B 1 2 1 0 C B 2 6 0 C B
2 C B 1 0 0 C B
1 C B 0 1 0 0 C
(k) B C B C
@ 0 1 1 0 A⇥ @ 2 8 2
⇥
2 A @ 1 0 1
=
1 A @ 0 0 2 0 A
1 2 0 1 3 6 3 2 3 1 1 2 0 0 0 4
0 1 0 1 0 1
2 3 3 2 0 6 1 8 0 1 7 1
B 5 1 6 13 C B 0 C B 5 C
(l) B C⇥B 8 8 1 C⇥B 1 1 8 C=
@ 1 0 1 2 A @ 6 0 7 2 A @ 2 1 8 7 A
1 1 1 1 3 3 4 5 1 1 7 4
0 1
6 0 0 0
B 0 1 0 0 C
=B@ 0 0 0
C
0 A
0 0 0 5

[7.1]

(a) 2x21 + x22 5x23

(b) 5x21 2x22 + x23

(c) 5x21 3x22 + 3x23

(d) x21 2x22 + 2x23

85
 9 ANSWERS TO PROBLEMS

(e) 2x21 3x22 + 3x23 5x24

(f) 5x21 4x22 + x23 + 3x24

(g) 3x21 + 2x22 + 3x23 + 2x24

(h) x21 3x22 + 4x23 + x24

[7.2] (a) n+ = 2, n = 0, positive semidefinite (b) n+ = 1, n = 2, not definite (c) n+ = 2,

n = 1, not definite (d) n+ = 2, n = 1, not definite (e) n+ = 1, n = 3, not definite (f)
n+ = 1, n = 3, not definite(g) n+ = 0, n = 4, negative definite(h) n+ = 0, n = 3, negative
semidefinite
[8.1]
0 1 0 1 0 1
1 23 1
(a) f1 = @ 1 A, f2 = @ 1 A, f 3 = @ 7 A
3 8 2
0 1 0 1 0 1
3 2 1
(b) f1 = @ 2 A, f2 = @ 1 A, f3 = @ 2 A
1 4 1
0 1 0 1 0 1
3 4 8
(c) f1 = @ 2 A, f2 = @ 31 A, f3 = @ 7 A
2 37 5
0 1 0 1 0 1
2 4 1
(d) f1 = @ 1 A, f2 = @ 8 A, f3 = @ 2 A
0 5 4
0 1 0 1 0 1
2 2 43
B 2 C B 4 C B 4 C
(e) f1 = B C B C B
@ 3 A, f2 = @ 3 A, f3 = @ 30 A
C

1 5 4
0 1 0 1 0 1
3 9 9
B 4 C B 14 C B 3 C
(f) f1 = B C B C B
@ 1 A, f2 = @ 13 A, f3 = @ 13 A
C

2 8 26
0 1 0 1 0 1 0 1
3 15 12 7
B 1 C B 2 C B 13 C B 26 C
B C B C B C B C
(g) f1 = B 3 C, f2 = B 13 C, f3 = B 18 C, f4 = B
B C B C B C
B 9 C
C
@ 1 A @ 12 A @ 2 A @ 14 A
1 16 29 8

86
 9 ANSWERS TO PROBLEMS

0 1 0 1 0 1 0 1
1 3 3 30
B 0 C B 4 C B 10 C B 16 C
B C B C B C B C
(h) f1 = B
B 1 C, f 2 = B
C B 3 C, f 3 = B
C B 12 C, f4 = B
C B 15 C
C
@ 3 A @ 1 A @ 4 A @ 17 A
3 1 1 2

[8.2]
0 1
11 2 8
(a) @ 2 6 5 A
8 5 14
0 1
12 0 4
(b) @ 0 2 1 A
4 1 6
0 1
11 4 3
(c) @ 4 14 2 A
3 2 1
0 1
6 5 2
(d) @ 5 17 5 A
2 5 11
0 1
21 4 9 11
B 4 13 3 13 C
(e) B C
@ 9 3 19 7 A
11 13 7 28
0 1
30 6 1 2
B 6 15 7 8 C
(f) B C
@ 1 7 5 1 A
2 8 1 23
0 1
14 2 3 19
B 2 28 16 2 C
(g) B C
@ 3 16 10 3 A
19 2 3 34
0 1
22 3 8 6
B 3 29 4 15 C
(h) B C
@ 8 4 9 0 A
6 15 0 11

[8.3]

87
 9 ANSWERS TO PROBLEMS

0 1
1
(a) p = @ 2 A, d2 = 32
2
0 1
5
(b) p = @ 3 A, d2 = 26
3
0 1
2
(c) p = @ 2 A, d2 = 3
4
0 1
1
(d) p = @ 1 A, d2 = 27
0
0 1
3
B 4 C
(e) p = B
@
C, d2 = 18
1 A
1
0 1
1
B 2 C
(f) p = B
@
C, d2 = 24
5 A
1
0 1
1
B 2 C
(g) p = B
@
C, d2 = 18
0 A
1
0 1
5
B 4 C
(h) p = B
@
C, d2 = 16
3 A
0
[8.4]
0 1 0 1
3 2
B 4 C B 9 C
(a) b1 = B
@
C, b2 = B
A @
C
1 0 A
0 1
0 1 0 1
0 6
B 6 C B 1 C
(b) b1 = B
@
C, b = B C
1 A 2 @ 0 A
0 1

88
 9 ANSWERS TO PROBLEMS

0 1 0 1
3 6
B 1 C B 1 C
(c) b1 = B
@
C, b2 = B C
1 A @ 0 A
0 1
0 1 0 1
3 1
B 2 C B 3 C
(d) b1 = B
@
C, b2 = B C
1 A @ 0 A
0 1
0 1
8
B 8 C
(e) b = B
@
C
8 A
1
0 1
1
B 1 C
(f) b = B
@
C
3 A
1

[8.5]
0 1 0 1 0 1 0 1
4 1 5 0
(a) c=@ 2 A (b) c = @ 3 A (c) c = @ 1 A (d) c = @ 4 A
3 3 5 5
0 1 0 1
2 2
B 1 C B 3 C
(e) c1 = B
@ 1 A,
C c2 = B
@
C
2 A
2 2
0 1 0 1
4 3
B 4 C B 2 C
(f) c1 = B
@ 2 A,
C c2 = B
@
C
1 A
3 1
0 1 0 1
2 4
B 4 C B 1 C
(g) c1 = B
@ 2 A,
C c2 = B
@
C
3 A
4 3
0 1 0 1
4 5
B 1 C B 1 C
(h) c1 = B
@ 5 A,
C c2 = B
@
C
1 A
1 3

89
 10 SAMPLE MIDTERM EXAM I

10 Sample Midterm Exam I

S E C T I O N I: M U L T I P L E C H O I C E

Directions: Each of the following problems is followed by five choices. Select the best choice and put
the corresponding mark in your answer sheet. Calculators may NOT be used at any part of the
exam.

1. Which of the following statements are true for any pair of non-degenerate n ⇥ n matrices
A and B?

I. (AB)T = AT B T
II. (AB)T = B T AT
III. (AT ) 1
= (A 1 )T

(A) I only
(B) II only
(C) I and III
(D) II and III
(E) None of the above options

2. Let A = (aij ) be a 5⇥5 matrix such that a11 = 1, a22 = 2, and det A = 0. The largest
(by absolute value) third-order minor of A is

(A) 0
(B) 1
(C) 2
(D) 3
(E) Could be any number

3. Let {a, b} and {c, d} be two sets of vectors, both linearly independent. Which of the
following MUST be true?

I. {a, b, c, d} is also linearly independent.

II. Both {a, c} and {b, d} are linearly independent
III. Either {a, c} or {b, d} is linearly independent

(A) I
(B) II
(C) III
(D) All are true
(E) Neither is true

90
 10 SAMPLE MIDTERM EXAM I

4. Let A be a matrix such that A · B = 0 for any compartible matrix B. Which of the
following MUST be true?
I. det A = 0
II. A = 0
III. Rows of A are linearly dependent
(A) I
(B) II
(C) III
(D) I & III
(E) II & III

5. Let (x1 , x2 , x3 ) be a solution to the following SLE

8
< 7x1 + 5x2 = 0
3x1 + x2 + x3 = 5
:
3x1 + 2x2 x3 = 5
Then x3 is
(A) 3
(B) -3
(C) 5
(D) -5
(E) None of these

1 12 8
6. The determinant 0 4 8 is equal to
0 8 8
(A) 0
(B) 4
(C) 52
(D) 64
(E) None of these

0 1
6 5 2
7. Let A be the matrix that is inverse to @ 1 0 1 A. Then a22 =
2 2 1
(A) 1
(B) 2
(C) 3
(D) 5
(E) None of these

91
 10 SAMPLE MIDTERM EXAM I

8. Let A be a 3⇥4 matrix and B be a 4⇥5 matrix. rk(A · B) is not greater than
(A) 0
(B) 3
(C) 4
(D) 5
(E) Could be any number

9. Let A, B, and C be square matrices such that A · B = E and B · C = E, where E is the

identity matrix. Which of the following MUST be true?

I. det(A) = det(C)
II. A = C
III. If A = B then | det(A)| = 1

(A) I
(B) II
(C) III
(D) I & II
(E) I, II, and & III

0 1
2 0 12 6
10. The rank of the matrix @ 3 0 2 3 A is
7 4 4 1
(A) 0
(B) 1
(C) 2
(D) 3
(E) 4

92
 10 SAMPLE MIDTERM EXAM I

S E C T I O N I I: F R E E R E S P O N S E

Directions: Show all your work. Indicate clearly the methods you use because you will be graded on
the correctness of your methods as well as on the accuracy of your results and explanations. You may
use the back of this sheet for writing.

1. Evaluate the following determinant using row or column decomposition.

12 4 12 2
7 10 4 1
6 3 16 1
13 18 16 2

2. Solve the following matrix equation. Explain all steps in your calculations.
0 1 0 1
9 11 10 3 4
@ 9 10 9 AX = @ 5 4 A
8 9 8 1 1

3. Find the fundamental set of solutions to the following system of linear equations. Indicate
the dimension of the solution space.
8
< x1 + 2x2 2x3 17x4 3x5 = 0
3x1 5x2 + 2x3 11x4 x5 = 14
:
x1 4x2 7x4 x5 = 10

93
 10 SAMPLE MIDTERM EXAM I

ANSWERS

Multiple Choice:

1. D

2. E

3. E

4. E

5. D

6. E

7. B

8. B

9. E

10. D

Free Response:

1. det = 60
0 1
14 5
2. @ 49 41 A
41 41
0 1 0 1 0 1
2 7 1
B 2 C B 0 C B 0 C
B C B C B C
3. For instance, x = B
B 1 C+
C
B
1B 5 C+
C
B
2B 1 C
C
@ 0 A @ 1 A @ 0 A
0 0 1
dim = 2
Note: the answer is not unique.

94
 11 SAMPLE MIDTERM EXAM II

11 Sample Midterm Exam II

S E C T I O N I: M U L T I P L E C H O I C E

Directions: Each of the following problems is followed by five choices. Select the best choice and put
the corresponding mark in your answer sheet. Calculators may NOT be used at any part of the
exam.

1. Which of the following sets form linear vector spaces with respect to the function addition
operation?

I. {y = f (x) | f 0 (0) = 1}
II. {y = f (x) | f 0 (1) = 0}
III. {y = f (x) | f 0 (0) = f 0 (1)}

(A) I
(B) II
(C) I & II
(D) II & III
(E) I, II, and III

2. Let A = (aij ) be a 4⇥4 matrix such that a11 = 1, a22 = 2, and det A = 0. The smallest
(by absolute value) third-order minor of A is

(A) 0
(B) 1
(C) 2
(D) 3
(E) Could be any number

3. Which of the following sets form linear vector spaces with respect to matrix addition?

I. The set of all 2⇥2 matrices that are equal to their transpose
II. The set of all 3⇥3 matrices with the property det A = 0
III. The set of all 4⇥4 matrices with the property det A = 1.

(A) I
(B) II
(C) III
(D) I & II
(E) I and III

95
 11 SAMPLE MIDTERM EXAM II

4. Let A = (aij ) be a 3⇥4 matrix such that a11 = 0. Whe rank of A could be each of the
following EXCEPT

(A) 0
(B) 1
(C) 2
(D) 3
(E) 4

5. Let a, b, and c be vectors in R3 that are linearly independent. Which of the following
MUST be true?

I. Vectors a and b also form a linearly independent set of vectors

II. The set of vectors {a, b, c} is full in R3
III. The set {a, b, c, d} is linearly dependent for any vector d 2 R3

(A) I
(B) II
(C) I & II
(D) I & III
(E) I, II and III

6. Let A and B be non-degenerate 6⇥6 matrices. Which of the following MUST be true?

I. (A · B) 1
=A 1
·B 1

II. (A · B) 1
=B 1
·A 1

III. The transpose to A 1

is the inverse to AT .

(A) I
(B) II
(C) I & III
(D) I & II
(E) II & III

7. Let (x1 , x2 , x3 ) be a solution to the following SLE

8
< 2x1 7x2 5x3 = 4
x1 + x2 + 2x3 = 7
:
6x1 5x2 + 5x3 = 12

Then x1 is
(A) -7

96
 11 SAMPLE MIDTERM EXAM II

(B) -4
(C) 0
(D) 7
(E) None of these

3 0 12
8. The determinant 4 1 1 is equal to
11 2 1
(A) 0
(B) 10
(C) 18
(D) 27
(E) None of these
0 1
5 2 2
9. If A is the matrix inverse to @ 9 5 3 A then a13 =
4 1 2
(A) 4
(B) -4
(C) 11
(D) -11
(E) None of these
0 1
10 0 6 4
10. The rank of the matrix @ 5 10 1 4 A is
5 10 1 4
(A) 0
(B) 1
(C) 2
(D) 3
(E) 4

97
 11 SAMPLE MIDTERM EXAM II

S E C T I O N I I: F R E E R E S P O N S E

Directions: Show all your work. Indicate clearly the methods you use because you will be graded on
the correctness of your methods as well as on the accuracy of your results and explanations. You may
use the back of this sheet for writing.

1. Evaluate the following determinant using row or column decomposition.

10 5 18 4
11 5 17 2
2 0 13 3
11 10 10 1

2. Solve the following matrix equation. Explain all steps in your calculations.
0 1
3 11 11 ✓ ◆
2 4 3
X@ 1 2 3 A=
5 3 2
1 4 4

3. Find the fundamental set of solutions to the following system of linear equations. Indicate
the dimension of the solution space.
8
< x1 + 5x2 + 5x3 + x4 5x5 = 1
x1 5x2 7x3 + 13x4 + x5 = 3
:
2x2 + 5x3 5x4 9x5 = 6

98
 11 SAMPLE MIDTERM EXAM II

ANSWERS

Multiple Choice:

1. D

2. A

3. A

4. E

5. E

6. E

7. A

8. D

9. B

10. C

Free Response:

1. det = 100
✓ ◆
6 1 15
2.
27 5 71
0 1 0 1 0 1
1 6 5
B 2 C B 0 C B 3 C
B C B C B C
3. For instance, x = B
B 2 C+
C
B
1B 1 C+
C
B
2B 3 C
C
@ 0 A @ 1 A @ 0 A
0 0 1
dim = 2
Note: the answer is not unique.

99
 12 SAMPLE MIDTERM EXAM III

12 Sample Midterm Exam III

S E C T I O N I: M U L T I P L E C H O I C E

Directions: Each of the following problems is followed by five choices. Select the best choice and put
the corresponding mark in your answer sheet. Calculators may NOT be used at any part of the
exam.
0 1
4 3 5
1. Let A be the inverse matrix for @ 1 1 2 A. Then a13 =
3 3 5
(A) 1
(B) 0
(C) -1
(D) 3
(E) None of these

2. Let A and B be two 7⇥7 matrices such that rk(A) = 2 and rk(B) = 3. Which of the
following COULD be true?

I. rk(A + B) = 0
II. rk(A + B) = 1
III. rk(A + B) = 6

(A) I only
(B) II only
(C) I and II
(D) I, II, and III
(E) None

7 1 4
3. The determinant 6 0 6 is equal to
10 3 15
(A) 6
(B) 12
(C) 36
(D) 48
(E) None of these

4. Let a, b, c, and d be four vectors such that {a, b, c} is linearly dependent and {b, c, d} is
also linearly dependent. Which of the following MUST be true?

I. {a, b, d} is linearly dependent

II. dim L(a, b, c, d)  2

100
 12 SAMPLE MIDTERM EXAM III

III. d a can be expressed as a linear combination of b and c

(A) I only
(B) I and II
(C) I, II, and III
(D) III only
(E) None

5. The rank of the following matrix is equal to

0 1
3 2 2 1 4
@ 9 6 6 3 12 A
15 10 10 5 20

(A) 1
(B) 2
(C) 3
(D) 4
(E) 5

6. Let a, b, c, and d be four vectors such that {b, c} is linearly independent, {a, b, c} is
linearly dependent, and {b, c, d} is also linearly dependent. Which of the following MUST
be true?

I. {a, b, d} is linearly dependent

II. dim L(a, b, c, d)  2
III. d a can be expressed as a linear combination of b and c

(A) I
(B) I and II
(C) I, II, and III
(D) III only
(E) None
✓ ◆ ✓ ◆
1 4 2 3
7. If A = , B= , and C = B T ⇥ A, then c21 =
3 1 1 0
(A) 1
(B) 9
(C) -3
(D) 12
(E) -1

8. The dimension of the space of solutions of x1 + 3x2 + 15x3 + 12x4 + 15x5 = 0 is

(A) 1
(B) 2
(C) 3

101
 12 SAMPLE MIDTERM EXAM III

(D) 4
(E) 5

9. Let (x1 , x2 , x3 ) be a solution to the following SLE

8
< 8x1 + 7x2 3x3 = 2
9x1 + 3x2 + 4x3 = 12
:
x1 3x2 5x3 = 8

Then x1 + x2 + x3 =
(A) -2
(B) 0
(C) 2
(D) 10
(E) None of these

10. Which of the following statements are true for any pair of non-degenerate n ⇥ n matrices
A and B?

I. (B 1 AB) 1
= B 1A 1B
II. (AT B T ) 1
= (A 1 B 1 )T
III. (AT B T ) 1
= (B 1 A 1 )T

(A) I
(B) I and II
(C) I and III
(D) III only
(E) None is true

102
 12 SAMPLE MIDTERM EXAM III

S E C T I O N I I: F R E E R E S P O N S E

Directions: Show all your work. Indicate clearly the methods you use because you will be graded on
the correctness of your methods as well as on the accuracy of your results and explanations. You may
use the back of this sheet for writing.

1.
3 0 7 1 7
6 0 0 0 0
7 0 1 0 4
9 1 0 5 4
2 1 5 6 2

2. Solve the following matrix equation. Explain each step in your solution.
0 1 0 1
3 1 1 2 0
@ 0 1 1 AX = @ 2 6 A
1 2 3 7 1

3. Find the fundamental set of solutions to the following system of linear equations. Indicate
the dimension of the solution space.
8
< 5x1 7x2 8x3 7x4 21x5 + 7x6 = 10
3x1 4x2 4x3 + 2x4 10x5 + 6x6 = 3
:
4x1 5x2 3x3 + 22x4 5x5 + 14x6 = 7

103
 12 SAMPLE MIDTERM EXAM III

ANSWERS

Multiple Choice:

1. A

2. B

3. D

4. E

5. A

6. C

7. C

8. D

9. B

10. B

Free Response:

1. det = 42
0 1
2 28
2. X = @ 3 45 A
5 39
0 1 0 1 0 1 0 1
5 6 2 2
B 9 C B 5 C B 3 C B 3 C
B C B C B C B C
B 6 C B 9 C B 4 C B 3 C
3. x = B C
B 0 C+ 1B
B C+
C
B
2B
C+
C
B
3B
C
C
B C B 1 C B 0 C B 0 C
@ 0 A @ 0 A @ 1 A @ 0 A
0 0 0 1

104
 13 SAMPLE FINAL EXAM I

13 Sample Final Exam I

S E C T I O N I: M U L T I P L E C H O I C E

Directions: Each of the following problems is followed by five choices. Select the best choice and put
the corresponding mark in your answer sheet. Calculators may NOT be used at any part of the
exam.
0 1
5 0 0
1. Let A be a 3⇥3 matrix and let B = @ 0 1 0 A. If A is multiplied by B from the left
0 0 1
then

(A) The 1st column of A is multipled by 5

(B) The 1st row of A is multipled by 5
(C) The 1st column of A is divided by 5
(D) The 1st row of A is divided by 5
(E) None of these

2. The signature of the quadratic form 10x21 6x1 x2 + 6x1 x3 x22 + 2x2 x3 x23 is

(A) -2
(B) -1
(C) 0
(D) 1
(E) 2

3. Let A be a 3⇥3 matrix with eigenvalues 1 , 2 , and 3 such that 1 6= 2, 1 6= 3, and

2 6= 3 . Which of the following MUST be true?

I If a and b are eigenvectors corresponding to 1 then the set {a, b} is linearly depen-
dent
II. If a1 and a2 are eigenvectors corresponding to 1 and 2, respectively, then {a1 , a2 }
is linearly independent
III. det(A) 6= 0

(A) I
(B) II
(C) III
(D) I and II
(E) II and III

105
 13 SAMPLE FINAL EXAM I

0 1
2 4 4
4. Which of the following could be the set of eigenvalues of @ 2 2 2 A?
2 4 0
(A) 1 = 2, 2 = 4, 3 = 2
(B) 1 = 2, 2 = 4, 3 = 2
(C) 1 = 2, 2 = 4, 3 = 2
(D) 1 = 2, 2 = 4, 3 = 2
(E) None of these

5. The quadratic form 8x21 + 16x1 x2 + 16x1 x3 + 4x22 + 8x2 x3 + 8x23 is

(A) positively definite

(B) negatively definite
(C) non-positively definite
(D) non-negatively definite
(E) not definite

6. Let d be the0
distance
1 between
0 the endpoint
1 0of vector
1 x and the linear space generated by
13 2 4
vectors x = @ 1 A, e1 = @ 2 A, e2 = @ 3 A Then, d2 =
3 4 1
(A) 1
(B) 16
(C) 27
(D) 32
(E) None of these

7. Let A be a 3⇥3 matrix. Which of the following MIGHT be true?

I. A has no real eigenvalues

II. A is diagonalizable but A2 is not
III. A2 is diagonalizable but A is not

(A) I
(B) II
(C) III
(D) I and II
(E) I and III
0 1
3 3 1 1
B 0 5 1 0 C
8. Which of the following is NOT an eigenvalue of A = B
@
C?
0 0 4 0 A
0 3 3 2
(A) -2

106
 13 SAMPLE FINAL EXAM I

(B) -3
(C) -4
(D) -5
(E) -6
0 1 0 1 0 1
0 4 1
9. The element g12 of the Gram matrix of e1 = @ 1 A, e2 = @ 2 A, e3 = @ 0 A is
3 1 2
(A) 5
(B) 6
(C) -5
(D) 21
(E) None of these

10. Let A be a 3⇥3 matrix with the property A = A2 . Which of the following MUST be
true?

I det(A) = 0
II. det(A) = 1
III. A is the identity matrix

(A) I
(B) II
(C) III
(D) II and III
(E) None is true

107
 13 SAMPLE FINAL EXAM I

S E C T I O N I I: F R E E R E S P O N S E

Directions: Show all your work. Indicate clearly the methods you use because you will be graded on
the correctness of your methods as well as on the accuracy of your results and explanations. You may
use the back of this sheet for writing.

1. [6 pts] For the following matrix A find matrices C and C 1

such that C 1
AC is diagonal
and write a product expression for eA . Show your work.
0 1
1 3 1
A=@ 2 5 2 A
2 3 4

2. [4 pts] Use Gram-Schmidt orthogonalization process to find an orthogonal base in the

linear0hull 1
of the following
0 1system 0
of vectors.
1 Show your work.
1 3 1
B 4 C B 4 C B 1 C
e1 = B C B C B C
@ 3 A, e 2 = @ 1 A, e 3 = @ 1 A
3 1 0

3. [4 pts] For the vectors x, e1 , e2 , and e3 below, find the projection of the vector x onto
the linear hull of e1 , e2 , and e3 . Evaluate the distance between the endpoint of x and the
linear
0hull. 1 0 1 0 1 0 1
4 3 2 0
B 14 C B C B C B C
x=B C, e1 = B 4 C, e2 = B 0 C, e3 = B 2 C
@ 0 A @ 3 A @ 1 A @ 1 A
6 5 5 3

108
 13 SAMPLE FINAL EXAM I

ANSWERS

Multiple Choice:

1. B

2. B

3. D

4. A

5. E

6. C

7. C

8. E

9. A

10. E

Free Response:
0 1 0 1 0 1 0 1
4 1 3 1 3 1 1 4 1 2 0 0
1. @ 1 0 1 A⇥@ 2 5 2 A⇥@ 0 1 1 A=@ 0 3 0 A
1 1 1 2 3 4 1 5 1 0 0 5
0 1 0 1 0 1
1 2 8
B 4 C B C B 4 C
2. f1 = B C, f 2 = B 2 C, f3 = B C
@ 3 A @ 1 A @ 3 A
3 1 11
0 1
4
B 10 C 2
3. p = B
@
C, d = 112
4 A
2

109
 14 SAMPLE FINAL EXAM II

14 Sample Final Exam II

S E C T I O N I: M U L T I P L E C H O I C E

Directions: Each of the following problems is followed by five choices. Select the best choice and put
the corresponding mark in your answer sheet. Calculators may NOT be used at any part of the
exam.
0 1
1 0 0
1. Let A be a 3⇥3 matrix and let B = @ 0 3 0 A. If A is multiplied by B from the left
0 0 1
then

(A) The 2nd column of A is multipled by 3

(B) The 2nd row of A is multipled by 3
(C) The 2nd column of A is divided by 3
(D) The 2nd row of A is divided by 3
(E) None of these

2. The signature of the quadratic form 4x21 8x1 x2 + 16x1 x3 + 9x22 16x2 x3 + 10x23 is

(A) -2
(B) -1
(C) 0
(D) 1
(E) 2

3. Let A be a 3⇥3 matrix with eigenvalues 1 , 2 , and 3 such that 1 6= 2, 1 6= 3, and

2 6= 3 . Which of the following MUST be true?

I There exists a basis of R3 that consists of eigenvectors of A

II. A is diagonalizable
III. Rows of A are linearly independent

(A) I
(B) II
(C) I and II
(D) II and III
(E) I and III

110
 14 SAMPLE FINAL EXAM II

0 1
5 3 3
4. Which of the following could be the set of eigenvalues of @ 3 5 3 A?
3 1 1
(A) 1 = 2, 2 = 1, 3 = 2
(B) 1 = 2, 2 = 1, 3 = 2
(C) 1 = 2, 2 = 1, 3 = 2
(D) 1 = 2, 2 = 1, 3 = 2
(E) None of these

5. The quadratic form 8x21 2x1 x2 + 2x1 x3 + x22 2x2 x3 7x23 is

(A) positively definite

(B) negatively definite
(C) non-positively definite
(D) non-negatively definite
(E) not definite

6. Let d be the distance between 0 the endpoint

1 of vector
0 1x and the
0 linear
1 space generated by
2 2 2
vectors e1 , and e2 , where x = @ 7 A, e1 = @ 3 A, e2 = @ 1 A Then, d2 =
11 3 1
(A) 2
(B) 4
(C) 8
(D) 16
(E) None of these
0 1
3 0 0 0
B 3 0 0 0 C
7. Which of the following is NOT an eigenvalue of A = B
@ 5
C?
5 5 4 A
0 0 0 3
(A) -5
(B) -3
(C) 0
(D) 3
(E) 5

8. Let A be a 4⇥4 matrix with det(A) 6= 0. Which of the following MIGHT be true?

I. A has no real eigenvalues

II. = 0 is an eigenvalue of A
III. A and A2 have the same set of eigenvalues

111
 14 SAMPLE FINAL EXAM II

(A) I
(B) II
(C) III
(D) I and II
(E) I and III
0 1 0 1 0 1
2 2 3
9. The element g32 of the Gram matrix of e1 = @ 3 A, e2 = @ 1 A, e3 = @ 4 A is
0 1 1
(A) -11
(B) 1
(C) 6
(D) 13
(E) None of these

10. Let A be a 3⇥3 matrix whose characteristic polynomial f ( ) = 1 + 2 3

. Which
of the following MUST be true?

I rk(A E) = 3 for some

II. A 1
exists
III. A is NOT diagonalizable

(A) I
(B) II
(C) I and II
(D) II and III
(E) I, II, and III

112
 14 SAMPLE FINAL EXAM II

S E C T I O N I I: F R E E R E S P O N S E

Directions: Show all your work. Indicate clearly the methods you use because you will be graded on
the correctness of your methods as well as on the accuracy of your results and explanations. You may
use the back of this sheet for writing.

1. [6 pts] For the following matrix A find matrices C and C 1 such that C 1
AC is diagonal
and write a product expression for A100 . Show your work.
0 1
1 5 3
A=@ 3 3 3 A
3 1 1

2. [4 pts] Use Gram-Schmidt orthogonalization process to find an orthogonal base in the

linear0hull 1
of the following
0 1system 0
of vectors.
1 Show your work.
1 3 0
B 2 C B 0 C B 3 C
e1 = B C B C B
@ 1 A, e 2 = @ 3 A, e 3 = @ 3 A
C

3 1 1

3. [4 pts] For the vectors x, e1 , e2 , and e3 below, find the projection of the vector x onto
the linear hull of e1 , e2 , and e3 . Evaluate the distance between the endpoint of x and the
linear
0hull.
1 0 1 0 1 0 1
3 4 2 3
B 2 C B 4 C B 2 C B 2 C
x=B C B C B
@ 2 A, e1 = @ 4 A, e2 = @ 1 A, e3 = @ 3 A
C B C

1 0 4 1

113
 14 SAMPLE FINAL EXAM II

ANSWERS

Multiple Choice:

1. B

2. D

3. C

4. D

5. E

6. C

7. E

8. E

9. A

10. C

Free Response:
0 1 0 1 0 1 0 1
3 4 3 1 5 3 1 1 1 0 0 0
1. @ 1 3 2 A⇥@ 3 3 3 A⇥@ 1 0 3 A=@ 0 2 0 A
1 1 1 3 1 1 2 1 5 0 0 1
0 1 0 1 0 1
1 7 10
B 2 C B 1 C B C
2. f1 = B C B C, f3 = B 15 C
@ 1 A, f 2 = @ 7 A @ 13 A
3 4 9
0 1
1
B 0 C 2
3. p = B C
@ 2 A, d = 12
1

114
 15 SAMPLE FINAL EXAM III

15 Sample Final Exam III

S E C T I O N I: M U L T I P L E C H O I C E

Directions: Each of the following problems is followed by five choices. Select the best choice and put
the corresponding mark in your answer sheet. Calculators may NOT be used at any part of the
exam.

1. The quadratic form x21 2x1 x2 4x1 x3 + 4x22 + 4x2 x3 + 4x23 is

(A) positive semi-definite
(B) positive definite
(C) negative semi-definite
(D) negative definite
(E) not definite

2. Let A and B be n⇥n matrices such that B · A · B = E. Which of the following COULD
be true?

I. det(A)  0
II. rkA < rkB
III. A · B 6= B · A

(A) I only
(B) II only
(C) III only
(D) II and III
(E) None could be true

3. If d is the distance between the endpoint of vector x = ( 2, 7, 1) and the linear hull of
vectors e1 = (1, 0, 0) and e2 = (1, 3, 3), then d2 =
(A) 4
(B) 16
(C) 32
(D) 48
(E) None of these

4. Let A : R3 ! R3 be a linear operator and let e1 , e2 , e3 be some of its eigenvectors. Given

that e1 , e2 , e3 are linearly independent, which of the following MUST be true?

I. A is diagonalizable
II. The eigenvalues corresponding to e1 , e2 , and e3 are different
III. A 1
is diagonalizable, if exists

115
 15 SAMPLE FINAL EXAM III

(A) I only
(B) I and II
(C) I and III
(D) I, II, and III
(E) None

5. Let A be a n⇥n matrix and let B be the matrix defined by B = AT · A. Which of the
following are true statements?

I. Regardless of A, matrix B is always symmetric

II. B is the matrix of a positive semi-definite quadratic form
III. B is the matrix of a positive definite quadratic form if and only if det(A) 6= 0

(A) I only
(B) I and II
(C) I and III
(D) II and III
(E) I, II, and III

6. Let A be the linear operator acting on infinite-differentiable real functions according to

2
the rule A(f ) = @@xf2 + f . Which of the following is an eigenvector of A?
(A) f (x) = cos 2x
(B) f (x) = sin 3x
(C) f (x) = e 4x
(D) All of the above
(E) None of the above

7. Which of the following matrix equations, where X and Y are the unknown matrices,
MUST have no solutions?

I. X 2 = E
II. X T · X = E
III. X · Y Y ·X =E

(A) I only
(B) I and III
(C) III only
(D) II and III
(E) I, II, and III only
0 1
3 7 7
8. Which of the following numbers is NOT an eigenvalue of the matrix A = @ 7 5 7 A?
1 7 5
(A) -5

116
 15 SAMPLE FINAL EXAM III

(B) 2
(C) 7
(D) -4
(E) All are eigenvalues
8
< ax1 x2 + 2x3 = 11
9. The SLE 2x1 + 9x2 4x3 = 0 has no solutions when (A) a = 5
:
2x1 5x2 + 3x3 = 7
(B) a = 6
(C) a = 0
(D) a = 5
(E) There is no such a

10. Let e1 , e2 , and e3 be three distinct eigenvectors of a linear operator A : R3 ! R3 . If e1 ,

e2 , and e3 are linearly dependent, which of the following MUST be true?

I. det(A) = 0
II. At least two of the eigenvalues corresponding to e1 , e2 , e3 must be equal to each
other
III. A is not diagonalizable

(A) I only
(B) II only
(C) II and III
(D) I, II, and III
(E) None

117
 15 SAMPLE FINAL EXAM III

S E C T I O N I I: F R E E R E S P O N S E

Directions: Show all your work. Indicate clearly the methods you use because you will be graded on
the correctness of your methods as well as on the accuracy of your results and explanations. You may
use the back of this sheet for writing.

1. [3 pts] Find the fundamental set of solutions to the following system of linear equations.
Indicate the dimension of the solution space.
⇢
x1 + 2x2 + 5x3 + 5x4 + 8x5 = 2
x1 + x2 + 6x3 + 4x4 = 5

2. [4 pts] For the following matrix A find matrices C and C 1

such that C 1
AC is diagonal
and write a product expression for An . Show your work.
0 1
5 1 2
@ 2 2 4 A
1 1 6

3. [3 pts] Use Gram-Schmidt orthogonalization process to find an orthogonal base in the

linear0hull 1
of the following
0 1 system
0 of vectors.
1 Show your work.
0 1 0
B 1 C B 1 C B 0 C
e1 = B C B C B
@ 1 A, e2 = @ 4 A, e3 = @ 1 A .
C

1 2 3

118
 15 SAMPLE FINAL EXAM III

ANSWERS

Multiple Choice:

1. A

2. E

3. C

4. C

5. E

6. D

7. D

8. C

9. B

10. B

Free Response:
0 1 0 1 0 1 0 1
8 7 3 8
B 3 C B 1 C B 1 C B 8 C
B C B C B C B C
1. x = B 0 C + 1 B 1 C + 2 B
B C B C
B 0 C+
C
B
3B 0 C,
C
@ 0 A @ 0 A @ 1 A @ 0 A
0 0 0 1
dim = 3.
0 1 0 1 0 1 0 1
2 3 4 5 1 2 1 2 1 4 0 0
2. @ 1 1 1 A⇥@ 2 2 4 A⇥@ 1 0 2 A = @ 0 4 0 A,
1 1 2 1 1 6 0 1 1 0 0 5
which is also correct.
0 1 0 1 0 1
0 3 8
B 1 C B 4 C B 22 C
3. f1 = B C B C B
@ 1 A, f2 = @ 5 A, f3 = @ 15 A
C

1 1 37
Note: some answers are not unique.

119
Index
Addition, 15 Homogeneous polynomial, 59
Anti-symmetric matrix, 60
Area, 27 Identity matrix, 28, 38
Inhomogeneous dilation, 57
Base, orthogonal, 69 Integration, 48
Base, orthonormal, 69 Inverse matrix, 38
Inversion, 29
Cartesian product, 13
Characteristic polynomial, 52 Kronecker’s symbol, 69
Cofactor matrix, 41
Commutative operation, 37 Laplace’s formula, 29
Compatible matrices, 37 Leading element, 10
Complementation of bases, 20 Linear combination, 16
Completion of bases, 20 Linear dependence, 16
Completion of full squares, 64 Linear expression, 16
Conjugate matrices, 51 Linear function, 48
Cuboid, 27 Linear independence, 16, 23, 55
Linear map, 48
Determinant, 27, 29 Linear mapping, 48
Diagonal matrix, 9 Linear operator, 48
Differentiation, 48 Linear space, 13
Direct sum of vector spaces, 75 Linear subspace, 70
Linear transformation, 48
Echelon form, 12 Linear vector space, 13, 15
Eigenvalue, 55 Linear vector space over the field of real num-
Eigenvector, 55 bers, 15
Elementary transformation matrices, 43 Linear vector subspace, 16
Euclidean space, 70 Lower-triangular matrix, 9
Expected value, 48
Extended matrix, 8 Mapping, 14
Matrix, 8
Factorial of an integer, 29 Matrix conjugation, 51
Factors, 16 Matrix multiplication, 37
Function, 14 Matrix of a quadratic form, 60
Function of several variables, 14 Matrix of the linear operator, 49
Fundamental set of solutions, 24 Matrix, anti-symmetric, 60
Gauss elimination, backward steps, 10 Matrix, degenerate, 34
Gram matrix, 69 Matrix, diagonal, 9
Gram-Schmidt orthogonalization, 69 Matrix, lower-triangular, 9
Ground set, 15 Matrix, non-degenerate, 34
Matrix, regular, 34
Homogeneous dilation, 57 Matrix, singular, 34

120
INDEX INDEX

Matrix, symmetric, 60 Signature of a quadratic form, 64

Matrix, transpose, 22 SLE, 8
Matrix, upper-triangular, 9 Subspace, 15
Minkowski space, 63 Sum of vector spaces, 74
Monomial, 59 Sylvester’s criterion, 64, 65
Multiplication by scalars, 15 Symmetric matrix, 60
Multiplicity, algebraic, 56 Symmetry, 48
Multiplicity, geometric, 56 System of the linear equations, 8
Multiplicity, of a root, 56
Trace of a matrix, 52
Negative definite, 60 Transformations of columns, 28
Negative semidefinite, 60 Transformations of rows, 8, 28
Neutral element, 38 Transition matrix, 51
Normal vector, 70 Transpose matrix, 22
Not definite, 60 Transposition of a matrix, 22
Trivial linear combination, 16
Optimization problem, 70
Order, 29 Upper-left corner minor, 64
Ordered pairs, 13 Upper-triangular matrix, 9
Orthogonal base, 69
Orthogonal complement, 72 Vector space, 13, 15
Orthogonalization, 69 Volume, 27
Orthonormal base, 69 Volume n-dimensional, 27

Parallelogram, 27
Permutation, 29
Pivot element, 10
Pivoting element, 24
Polynomial, 59
Positive definite, 60
Positive semidefinite, 60
Projection, 48, 70

Quadratic form, 59
Quadratic form, negative definite, 60
Quadratic form, negative semidefinite, 60
Quadratic form, not definite, 60
Quadratic form, positive definite, 60
Quadratic form, positive semidefinite, 60

Rank of a matrix, 23
Relation, 14
Rotation, 48

Saddle point, 61

121