Mathematical Toolkit Autumn 2021

Lecture 1: September 28, 2021

Lecturer: Madhur Tulsiani

The primary goal of this course is to collect a set of basic mathematical tools which are often
useful in various areas of computer science. We will mostly focus on various applications
of linear algebra and probability. Please see the course webpage for a more detailed list of
topics.
The course will be evaluated on the basis of the following:

• Homeworks: 60% (five homeworks contributing 12% each)

• Midterm: 15%
• Final: 25%

We will spend 3-4 of lectures reviewing some of the basic concepts of linear algebra before
we move on to some of the applications.
Here’s a couple of problems to think about if you are already familiar with the contents
of this lecture. These are from the excellent book “Thirty Three Miniatures” by Jiřı́ Ma-
toušek [Mat10], both which I highly recommend for many more fun applications of Linear
Algebra (you can find a link in the “resources” section of the course webpage.)
√
Problem 0.1 Show that a rectangle with sides 1 and 2 cannot be tiled with a√finite number of
non-overlapping squares. In fact, you can try to prove that this is the case when 2 is replaced by
any irrational number x.

Problem 0.2 Let Kn denote the complete graph on the vertex set [n] = {1, . . . , n}. Also, for
disjoint S, T ⊆ [n], let KS,T denote the complete bipartite graph with the edge set
ES,T = {{i, j} | i ∈ S, j ∈ T } .
Show that if (S1 , T1 ), . . . , (Sm , Tm ) are such that each edge of Kn is present in exactly one of the
graphs KSi ,Ti , then m ≥ n − 1. Is this tight?

1 Fields

A field, often denoted by F, is simply a nonempty set with two associated operations +
and · mapping F × F → F, which satisfy:

1
 - commutativity: a + b = b + a and a · b = b · a for all a, b ∈ F.

- associativity: a + (b + c) = ( a + b) + c and a · (b · c) = ( a · b) · c for all a, b, c ∈ F.

- identity: There exist elements 0F , 1F ∈ F such that a + 0F = a and a · 1F = a for all

a ∈ F.

- inverse: For every a ∈ F, there exists an element (− a) ∈ F such that a + (− a) = 0F .

For every a ∈ F \ {0F }, there exists a−1 ∈ F such that a · a−1 = 1F .

- distributivity of multiplication over addition: a · (b + c) = a · b + a · c for all a, b, c ∈

F.

Example 1.1 Q, R and C with the usual definitions of addition and multiplication over these
fields.

Example 1.2 Consider defining addition and multiplication on Q2 as

( a, b) + (c, d) = ( a + c, b + d) and ( a, b) · (c, d) = ( ac + bd, ad + bc) .

These operations do not define a field. While various properties of addition are indeed satisfied,
inverses may not always exist for multiplication as defined above. Check that the multiplicative
identity needs to be (1, 0) but then the element (1, −1) has no multiplicative inverse.
However, for any prime p, the following operations do define a field

( a, b) + (c, d) = ( a + c, b + d) and ( a, b) · (c, d) = ( ac + pbd, ad + bc) .

√
This is equivalent to taking F = a + b p | a, b ∈ Q with the same notion of addition and


multiplication as for real numbers. Alternatively, one can also define a field by taking ( a, b) ·
(c, d) = ( ac − bd, ad + bc) (why?)

Example 1.3 For any prime p, the set F p = {0, 1, . . . , p − 1} (also denoted as GF(p)) is a field
with addition and multiplication defined modulo p. Also, check that defining addition and multi-
plication modulo a composite number (say modulo 6) does not give a field.
√ √
Exercise 1.4 Show that the set { a + b 3 2 + c 3 4 | a, b, c ∈ Q} is a field.

2 Vector Spaces

A vector space V over a field F is a nonempty set with two associated operations + :
V × V → V (vector addition) and · : F × V → V (scalar multiplication) which satisfy:

2
 - commutatitivity of addition: v + w = w + v for all v, w ∈ V.

- associativity of addition: u + (v + w) = (u + v) + w ∀u, v, w ∈ V.

- pseudo-associativity of scalar multiplication: a · (b · v) = ( a · b) · v ∀ a, b ∈ F, v ∈ V.

- identity for vector addition: There exists 0V ∈ V such that for all v ∈ V, v + 0V = v.

- inverse for vector addition:∀v ∈ V, ∃(−v) ∈ V such that v + (−v) = 0V .

- distributivity: a · (v + w) = a · v + a · w and ( a + b) · v = a · v + b · v for all a, b ∈ F

and v, w ∈ V.

- identity for scalar multiplication: 1F · v = v for all v ∈ V.

Example 2.1 Any field F is a vector space over itself.

Example 2.2 R is a vector space over Q.

Example 2.3 Let R[ x ] denote the space of polynomials in one variable x, with real coefficients i.e.,
( )
t
R[ x ] : = ∑ ci · x i | t ∈ N, c0 , . . . , ct ∈ R .
i =0

Then, R[ x ] is a vector space over R. Similarly, the space R≤d [ x ] of polynomials with degree at most
d, defined as ( )
t
R≤ d [ x ] : = ∑ ci · x i | t ∈ N, t ≤ d, c0 , . . . , ct ∈ R ,
i =0

is also a vector space over R.

Example 2.4 C ([0, 1], R) = { f : [0, 1] → R | f is continuous} is a vector space over R.

f ∈ RN | f (n) = f (n − 1) + f (n − 2) ∀n ≥ 2 is a vector space over R.


Example 2.5 Fib =

Definition 2.6 (Linear Dependence) A set S ⊆ V is linearly dependent if there exist distinct
v1 , . . . , vn ∈ S and c1 , . . . , cn ∈ F not all zero, such that ∑in=1 ci · vi = 0V . A set which is not
linearly dependent is said to be linearly independent. A sum of the form ∑in=1 ci · vi is referred to as
a linear combination of the vectors v1 , . . . , vn .
n √ √ o
Example 2.7 The set 1, 2, 3 is linearly independent in the vector space R over the field Q.

3
Exercise 2.8 Let a1 , . . . , an ∈ R be distinct and let g( x ) = ∏in=1 ( x − ai ). Define
g( x )
fi (x) =
x − ai
= ∏( x − a j ) ,
j 6 =i

where we extend the function at point ai by continuity. Prove that f 1 , . . . , f n are linearly indepen-
dent in the vector space R[ x ] over the field R.

3 Span and Bases

Definition 3.1 Given a set S ⊆ V, we define its span as

( )
n
Span (S) = ∑ ai · vi | a1 , . . . , an ∈ F, v1 , . . . , vn ∈ S, n ∈ N .
i =1

Note that we only include finite linear combinations. Also, since linear combinations of vectors are
still in V, we have Span (S) ⊆ V. In fact, you can check that Span (S) is also a vector space. Such
a subset of V, which is also a vector space, is called a subspace of V.

Remark 3.2 Note that the definition above and the previous definitions of linear dependence and
independence, all involve only finite linear combinations of the elements. Infinite sums cannot be
said to be equal to a given element of the vector space without a notion of convergence or distance,
which is not necessarily present in an abstract vector space.

Definition 3.3 A set B is said to be a basis for the vector space V if B is linearly independent and
Span ( B) = V.

We will say that a set B ⊆ V is a maximal linearly independent set if B is linearly inde-
pendent and for all v ∈ V \ B, B ∪ {v} is linearly dependent. It is often useful to use the
following alternate characterization of a basis.

Proposition 3.4 A set B ⊆ V is a basis for V if and only if B is a maximal linearly independent
set.

Proof: We will prove the “if” part and leave the other part as an exercise. If B is a
maximal linearly independent set, then we already know that it is linearly independent,
and only need to show that Span ( B) = V. By the maximality property, we have that
for all v ∈ V \ B, the set B ∪ {v} is linearly dependent. Thus, for some n ∈ N, there
exist v1 , . . . , vn ∈ B ∪ {v} and c1 , . . . , cn ∈ F such that ∑in=1 ci · vi = 0V . Also, v must
be one of the vectors v! , . . . , vn with a non-zero coefficient (otherwise we have a linear
dependency in B itself). Thus, v can be written as a linear combination of the other vi s and
we have v ∈ Span ( B) for all v ∈ V \ B. Since it is also true that B ⊆ Span ( B), we get that
V = Span ( B).

4
References

[Mat10] Jiřı́ Matoušek, Thirty-three miniatures: Mathematical and algorithmic applications of

linear algebra, vol. 53, American Mathematical Soc., 2010. 1