Discrete mathematics

Bernadett Aradi

2019 Fall

Information on the course, teaching materials:

[Link]

Bernadett Aradi Discrete mathematics 2019 Fall 1 / 85

Table of contents
1 Introduction: sets, functions, notation
2 The set of natural numbers, mathematical induction
3 The set of integers
Divisors, divisibility
Prime numbers
Congruence
4 Complex numbers
5 Polynomials
6 Combinatorics
7 Linear algebra
Vector spaces
Matrices, determinants
Systems of linear equations
Linear transformations
Euclidean vector spaces
Bernadett Aradi Discrete mathematics 2019 Fall 2 / 85
Introduction: sets

Set, element of a set (notation: ∈, negation: ∈):

/ basic concepts.
Defining a set: by enumeration, e.g., {1, 2, 3},
or with the help of a defining property T concerning the elements of
a given set S in the way {x ∈ S | T (x)}, e.g.,

{x ∈ N | 1 ≤ x ≤ 5}.

Emptyset: the unique set, that doesn’t have any element.

Notation: ∅.
Notation of the subset relation: ⊂.
Two sets are equal or coincide if their elements are the same.
Equivalently, if they are each others’ subsets:

A=B ⇐⇒ A ⊂ B and B ⊂ A.

Bernadett Aradi Discrete mathematics 2019 Fall 3 / 85

Cardinality of sets, power set
Definition
The power set of a given set S is the set of all subsets of S. Notation:
P(S) or 2S .

E.g., in the case of S = {0, 1, 2, 3}:

P(S) ={∅, {0}, {1}, {2}, {3}, {0, 1}, {0, 2}, {0, 3}, {1, 2}, {1, 3}, {2, 3},
{0, 1, 2}, {0, 1, 3}, {0, 2, 3}, {1, 2, 3}, S}
Definition
If a set has a finite number of elements, then this number is called the
cardinality of the set. Notation for a given set S: #S.
In this case we say that S is a finite set.

Theorem
If S has cardinality of n, then the power set of S has cardinality of 2n , that
is
#(P(S)) = 2#S .
Bernadett Aradi Discrete mathematics 2019 Fall 4 / 85
Fundamental operations on sets
The complement of a set A: A.
The union of two sets: A ∪ B.
The intersection of two sets: A ∩ B.
The (set-theoretic) difference of two sets: A \ B.
The symmetric difference of two sets, notation: 4.
A4B = (A ∪ B) \ (A ∩ B) = (A \ B) ∪ (B \ A)
E.g., if A = {0, 1, 2, 3, 4}, B = {2, 4, 6, 8, 10} what is A4B =?
The Cartesian product of two sets, notation: ×.
A × B = {(a, b) | a ∈ A, b ∈ B}
E.g., if A = {0, 1, 2}, B = {1, 2} what is A × B =?

Theorem – De Morgan’s laws

If A and B are arbitrary sets, then
(A ∪ B) = A ∩ B and (A ∩ B) = A ∪ B.
Furthermore, these identities hold for arbitrary number of sets.
Bernadett Aradi Discrete mathematics 2019 Fall 5 / 85
Notation

Special sets of numbers:

N = {1, 2, 3, . . . }: the set of natural numbers (to be defined later)
Z = {. . . , −2, −1, 0, 1, 2, . . . }: the set of integers
Q: the set of rational numbers
R: the set of real numbers
C: the set of complex numbers (to be defined later)
Quantifiers:
∃: ’there exists’ (existential quantifier)
∀: ’for all’ (universal quantifier)
E.g., ∃n ∈ N : 2n = 6, but @n ∈ N : 2n = 7
∀m ∈ N : m ∈ Z, but 6 ∀m ∈ Z : m ∈ N

Bernadett Aradi Discrete mathematics 2019 Fall 6 / 85

Introduction: functions

Function: an association rule, assignment or correspondence x 7→ f (x)

If the function f accomplishes a correspondence between the set D (the

domain of the function) and the set R (the range of the function), then we
can view the function as pairs (x, f (x)), where x ∈ D and f (x) ∈ R.
f : D → R, x 7→ f (x)
That is, the function is a subset of the Cartesian product D × R, such that
if
f : x 7→ y1 and f : x 7→ y2 ,
then necessarily y1 = y2 .

Bernadett Aradi Discrete mathematics 2019 Fall 7 / 85

Examples of functions

x ∈ R, x 7→ f (x) := x 2
x ∈ R+ , x 7→ f (x) := {a number with square x}
Not a function!
n ∈ N, n 7→ f (n) := {an odd number such that it’s a divisor of n}
Not a function!
n ∈ N, n 7→ f (n) := {the greatest positive divisor of n}
Function!

Notation
The meaning of := is: definition, prescribing a value, ’let it be equal with’

Notation
The meaning of different arrows: →, 7→, ⇒, ⇔

Bernadett Aradi Discrete mathematics 2019 Fall 8 / 85

Basic functions

constant: f (x) = c
first order (linear): f (x) = mx + b
second order: f (x) = ax 2 + bx + c √ (a 6= 0)  √ 
−b+ b 2 −4ac −b− b 2 −4ac
factored form: f (x) = a · x − 2a · x− 2a
polynomial
exponential: f (x) = ax (a > 0, a 6= 1)
logarithmic: f (x) = loga x (a > 0, a 6= 1)
trigonometric functions
absolute value function
sign function or signum function

Bernadett Aradi Discrete mathematics 2019 Fall 9 / 85

Properties of functions
Let us consider an arbitrary function

f : D → R, x 7→ f (x).

Definition
The function f is injective if f (a) = f (b) implies a = b.

That is, in this case the function f assigns a different value to each
element.
Definition
The function f is surjective if for every element y in R there exists an
element x ∈ D such that f (x) = y .

That is, f is surjective if all elements of R become an image of an element.

Definition
The function f is bijective if it is injective and surjective.
Bernadett Aradi Discrete mathematics 2019 Fall 10 / 85
Reasoning with mathematical induction

Let us assume that we want to prove a proposition (for example, the

relation below) for all natural numbers:

1 + 3 + 5 + · · · + (2n − 1) = n2 , ∀n ∈ N.

Then we can use the following reasoning:

(1) We prove the proposition for n = 1. (By trial and error.)

(2a) We assume that the proposition is true for an arbitrary natural
number k,
(2b) then we prove it for the natural number k + 1.

(2a): inductive hypothesis

Bernadett Aradi Discrete mathematics 2019 Fall 11 / 85

The set of natural numbers
For the axiomatic introduction of this set we use the so-called Peano
axioms.
Definition – Peano axioms
(P1) 1 is a natural number.
(P2) For every natural number n there exists uniquely a successor natural
number.
(P3) There is no natural number whose successor is 1.
(P4) If two natural numbers have the same successors, then the two
natural numbers coincide.
(P5) Axiom of induction: if A is a set such that
I it contains the natural number 1,
I for every element of A its successor is also in A,
then A contains all the natural numbers.
The conditions (P1)–(P5) uniquely determine a set, which is called the set
of natural numbers. Notation: N.
Bernadett Aradi Discrete mathematics 2019 Fall 12 / 85
Remarks on the Peano axioms

(P2) For every natural number n it is possible to provide a ’greater by 1’

natural number, which is called the successor of n.
n + 1, S(n) (S: successor function)
(P4) If two natural numbers have the same successors, then the two
natural numbers coincide.
In other words: the successor function is injective.
(P5) Axiom of induction: if A is a set such that
it contains the natural number 1,
for every element of A its successor is also in A,
then A contains all the natural numbers.
In other words: A is an inductive set. ⇒ N is the smallest inductive set.
Another example for inductive sets: the set of positive numbers (R+ ).

Bernadett Aradi Discrete mathematics 2019 Fall 13 / 85

The Peano axioms with mathematical formalism

Definition – Peano axioms

Let N be a set satisfying the following conditions:
(P1) 1 ∈ N
(P2) ∀n ∈ N : ∃S(n) ∈ N, S(n) =: n + 1
or: ∃S : N → N so-called successor function
(P3) @n ∈ N : S(n) = 1
(P4) n, m ∈ N : S(n) = S(m) ⇒ n = m
(P5) 
1∈A
=⇒ N ⊂ A
n ∈ A ⇒ S(n) ∈ A
Then N is uniquely determined, and it is called the set of natural numbers.

Bernadett Aradi Discrete mathematics 2019 Fall 14 / 85

Proof by induction
Based on the definition the elements of N are:
1, S(1), S(S(1)), S(S(S(1))), . . . , S(S(. . . (S(1)) . . . )), . . .
S(1) = 1 + 1 =: 2
S(S(1)) = S(1) + 1 =: 3
The axiom of induction expresses that all the natural numbers can be
given with the help of the special natural number 1 and the successor
function S. Thus, if we want to prove a proposition (for example, a
relation below) for all natural numbers, then we can apply the reasoning of
mathematical induction:
(1) We prove the proposition for n = 1. (By trial and error.)
(2a) We assume that the proposition is true for an arbitrary natural
number k,
(2b) then we prove it for the natural number k + 1.

(2a): inductive hypothesis

Bernadett Aradi Discrete mathematics 2019 Fall 15 / 85
Examples for proof by induction
n(n+1)
1 The sum of the first n natural numbers is 2 . We can apply
induction here. X
1
2 x+ x ≥ 2, ∀x > 0. We cannot apply induction for this!
3 Prove that

1 + 3 + 5 + · · · + (2n − 1) = n2 , ∀n ∈ N.

4 Prove that
n(n + 1)(2n + 1)
12 + 22 + 32 + · · · + n2 = , n ∈ N.
6

Notation
n
X n
Y
sum, product
i=1 i=1

Bernadett Aradi Discrete mathematics 2019 Fall 16 / 85

The set of integers

We introduce the set of integers with the help of the already defined set of
natural numbers. All integers can be written as the difference of two
natural numbers:
Z = {n − m | n, m ∈ N}.
The integers are: classes of these types of differences, e.g.,
3 is represented by the class {4 − 1, 5 − 2, 6 − 3, . . . , 72 − 69, . . . }
0 is represented by the class {1 − 1, 2 − 2, 3 − 3, . . . , 51 − 51, . . . }
−5 is represented by the class {1 − 6, 2 − 7, 3 − 8, . . . , 100 − 105, . . . }

Bernadett Aradi Discrete mathematics 2019 Fall 17 / 85

Divisors, divisibility
Let a, b ∈ Z.
Definition
We say that b is a divisor of a, or a is a multiple of b, or a is divisible by b
if there exists c ∈ Z such that a = b · c.
Notation: b|a

Theorem – the properties of divisibility

1 ∀a 6= 0, a ∈ Z : a|0, 1|a, a|a
2 If a|b and c ∈ Z, then a|bc. (a|b ∧ c ∈ Z ⇒ a|bc)
3 If a|b1 and a|b2 , then a|(b1 + b2 ).
4 If a|b and b|c, then a|c.
5 If a|b and b|a, then a = ±b.
2 és 3 ⇒ If a|bi , i = 1, 2, . . . , n and c1 , c2 , . . . , cn ∈ Z, then
a|(b1 c1 + b2 c2 + · · · + bn cn ).
Bernadett Aradi Discrete mathematics 2019 Fall 18 / 85
Divisibility rules
A∈N⇒

A = an · 10n + an−1 · 10n−1 + · · · + a2 · 102 + a1 · 10 + a0 ,

ai ∈ {0, 1, . . . , 9}, an 6= 0.

Divisibility by 2
A = (an · 10n−1 + an−1 · 10n−2 + · · · + a2 · 10 + a1 ) · 10 + a0
2|10, thus if 2|a0 , then 2|A
Divisibility by 5: A =as above
5|10, thus if 5|a0 , then 5|A
Divisibility by 4: 46 | 10, but 4|100
A = (an · 10n−2 + an−1 · 10n−3 + · · · + a2 ) · 100 + a1 · 10 + a0
4|100, so if 4|(a1 · 10 + a0 ), then 4|A
Divisibility by 25: analogously to 4, since 25|100.
Bernadett Aradi Discrete mathematics 2019 Fall 19 / 85
Divisibility rules
Divisibility by 8: 86 | 100, however 8|1000 ⇒
8|A ⇐⇒ 8|(100a2 + 10a1 + a0 )
100a2 + 10a1 + a0 is the remainder when dividing A by 1000.
Divisibility by 3 and 9: 10k − 1 = 99 . . . 9 ⇒ 3|(10k − 1), 9|(10k − 1)
A = an · 10n + an−1 · 10n−1 + · · · + a2 · 102 + a1 · 10 + a0 =
= an (10n − 1) + an−1 (10n−1 − 1) + · · · + a1 (10 − 1)+
+ an + an−1 + · · · + a1 + a0
⇒ A is divisible by 3 or 9 if the sum of its digits is divisible by 3 or 9
Divisibility by 11: 101 + 1 = 11, 102 − 1 = 99, 103 + 1 = 1001,
104 − 1 = 9999, . . . We can prove that
11|(10k + 1) if k is odd and 11|(10k − 1) if k is even.
A = a0 + a1 (101 + 1) − a1 + a2 (102 − 1) + a2 + · · · =
= (a1 (101 + 1) + a2 (102 − 1) + . . . ) + (a0 − a1 + a2 − a3 + . . . )
⇒ A is divisible by 11 if the alternating sum of its digits is divisible by 11
Bernadett Aradi Discrete mathematics 2019 Fall 20 / 85
Definition
We say that d ∈ N is the greatest common divisor of the integers a and b
d|a and d|b,
for all d¯ ∈ N such that d|a
¯ and d|b,
¯ the relation d|d ¯ also holds.
Notation: d = gcd(a, b).
Furthermore d ∈ N is the greatest common divisor of a1 , a2 , . . . , an ∈ Z if
d|ai , i ∈ {1, . . . , n},
for every d¯ ∈ N such that d|a
¯ i (i ∈ {1, . . . , n}), the relation d|d
¯ also
holds.
Definition
The integers a and b are called relatively prime or coprime numbers if
gcd(a, b) = 1.
Definition
We say that k ∈ N is the least common multiple of a1 , a2 , . . . , an ∈ Z if
ai |k, i ∈ {1, . . . , n},
for all k̄ ∈ N such that ai |k̄ (i ∈ {1, . . . , n}), the property k|k̄ also
holds.
Notation: k = lcm(a1 , a2 , . . . , an ).
Bernadett Aradi Discrete mathematics 2019 Fall 21 / 85
The Euclidean algorithm
Theorem – Euclidean division
Given arbitrary a, b ∈ Z, b 6= 0 numbers there uniquely exist integers
q, r ∈ Z such that
a = b · q + r , 0 ≤ r < |b|.
The Euclidean algorithm (or Euclid’s algorithm)
a, b ∈ Z, b 6= 0, theorem above ⇒ q, r ∈ Z, let us denote them by q0 , r0
this time:
a = b · q0 + r0
Let us repeat the Euclidean division with b and r0 ⇒ q1 , r1 ∈ Z,
then with r0 and r1 (⇒ q2 , r2 ∈ Z):
b = r0 · q1 + r1
r0 = r1 · q2 + r2 .

By continuing the procedure in this manner (each time with the obtained
remainders) we finish in finite steps, since
|b| > r0 > r1 > r2 > · · · > ri > · · · ≥ 0.
Bernadett Aradi Discrete mathematics 2019 Fall 22 / 85
Theorem
When applying the Euclidean algorithm for the integers a and b 6= 0, the
last non-zero remainder is the greatest common divisor of a and b.
Furthermore, if d := gcd(a, b), then the equation
ax + by = d

can be solved among integers. That is, there exist x, y ∈ Z solutions.

Example: gcd(1227, 216) =?, gcd(−1227, −216) =?

Definition
Equations of the form ax + by = c (where a, b, c ∈ Z are known, x, y ∈ Z
are unknown) are called linear Diophantine equations.

Theorem
The linear Diophantine equation ax + by = c is solvable if, and only if,
gcd(a, b)|c.
Example: Solve the Diophantine equation 147x + 69y = 3.
Bernadett Aradi Discrete mathematics 2019 Fall 23 / 85
Prime numbers
Every n > 1, n ∈ N has two positive divisors: 1 and n, these are called the
trivial divisors of n. All the other divisors are called non-trivial divisors.
Definition
Natural numbers which are greater than 1 and has only trivial divisors are
called prime numbers or primes. Natural numbers with also non-trivial
divisors are called composite numbers. 1 is a unit.
Theorem
An integer p > 1 is prime if, and only if, p|ab implies p|a or p|b.
Example: 15|60
Theorem – the fundamental theorem of arithmetic
(also called unique-prime-factorization theorem)
Every natural number greater than 1 is either a prime itself or is the
product of prime numbers. Furthermore, this product is unique up to the
order of the factors. The obtained unique product is called the canonical
representation or the standard form of n, which is n = p1α1 p2α2 . . . prαr ,
where p1 , p2 , . . . , pr are pairwise different primes, α1 , α2 , . . . , αr ∈ N.
Bernadett Aradi Discrete mathematics 2019 Fall 24 / 85
Number of divisors
Theorem
The number of positive divisors of a natural number n = p1α1 p2α2 . . . prαr is
d(n) = (α1 + 1)(α2 + 1) . . . (αr + 1).

Example: 1,455,300 = 22 · 33 · 52 · 72 · 11 and 185,130 = 2 · 32 · 5 · 112 · 17

Theorem
There are infinitely many prime numbers.
Proof: Suppose that there are only finitely many prime numbers, let them
be p1 , p2 , . . . , pk . Consider the number b = p1 · p2 · · · · · pk + 1. Then
b 6= 1 and b is a composite Q number, thus for some index i ∈ {1, 2, . . . , k}
we have pi |b. But pi | pj as well, thus pi |1, which is a contradiction.

Remark
The integers a and b are coprime numbers if there are no common prime
factors in their canonical representation.

Bernadett Aradi Discrete mathematics 2019 Fall 25 / 85

Congruence
Let a, b ∈ Z, m ∈ N.
Definition
We say that a and b are congruent modulo m if m|(a − b).
Notation: a ≡ b (mod m), m: is the modulus of the congruence.
Example: for m = 4 we have 3 ≡ 11 (mod 4)
The integers a, b ∈ Z are congruent modulo m if they provide the same
remainder when divided by m.
Theorem
The congruence modulo m is a so-called equivalence relation:
reflexive, symmetric, transitive.
Definition
Let us consider the class of integers which are congruent with each other
modulo m. The obtained classes are called the congruence classes or
residue classes modulo m. The residue classes are represented by the
integers 0, 1, . . . , m − 1. Thus, there are m residue classes modulo m.
Bernadett Aradi Discrete mathematics 2019 Fall 26 / 85
The properties of congruence
Proposition – the properties of congruence
Let m ∈ N (m ≥ 2) and a, b, c, d ∈ Z.
1 If a ≡ b and c ≡ d (mod m), then
a ± c ≡ b ± d (mod m) and a · c ≡ b · d (mod m).
2 If a · c ≡ b · c (mod m) and gcd(c, m) = 1, then a ≡ b.
Example: 15 ≡ 63 (mod 8) and 10 ≡ 18 (mod 8)
Definition
Any set of m integers, no two of which are congruent modulo m, is called
a complete residue system modulo m. The set of integers
{0, 1, 2, . . . , m − 1} is called the least residue system modulo m.
Example: for m = 5 the set {5, 6, 12, 28, 9} is a complete residue system,
while {0, 1, 2, 3, 4} is the least residue system.
Proposition
If a ≡ b (mod m), then gcd(a, m) = gcd(b, m).
Bernadett Aradi Discrete mathematics 2019 Fall 27 / 85
Reduced residue system
Definition
A residue class is a member of the reduced residue system if its members
are coprime to the modulus. Notation: the number of elements of a
reduced residue system modulo m is denoted by ϕ(m). That is
ϕ(m) = #{a ∈ {1, . . . , m} | gcd(a, m) = 1}.
The name of the function ϕ: Euler’s ϕ function or Euler’s totient function.
By definition, ϕ(1) = 1.
Examples: cardinality of the reduced residue system:
m complete reduced ϕ(m)
m=2 0,1 1 ϕ(2) = 1
m=3 0,1,2 1,2 ϕ(3) = 2
m=4 0,1,2,3 1,3 ϕ(4) = 2
m=5 0,1,2,3,4 1,2,3,4 ϕ(5) = 4
m=6 0,1,2,3,4,5 1,5 ϕ(6) = 2
m=7 0,1,2,3,4,5,6 1,2,3,4,5,6 ϕ(7) = 6
Bernadett Aradi Discrete mathematics 2019 Fall 28 / 85
Euler’s ϕ function
Proposition
If p is a prime, then ϕ(p) = p − 1.
Theorem
The value of Euler’s ϕ function can be calculated by the formula
r  
Y 1
ϕ(m) = m · 1− ,
pi
i=1

where m has canonical representation m = p1α1 p2α2 . . . prαr .

Example: m = 24, ϕ(24) =?
Theroem – Euler’s theorem
If gcd(a, m) = 1, then aϕ(m) ≡ 1 (mod m).
Corollary – Fermat’s little theorem
If p is a prime and p6 | a, then ap−1 ≡ 1 (mod p).
Example: what is the remainder when dividing 22019 by 15?
Bernadett Aradi Discrete mathematics 2019 Fall 29 / 85
Congruence equations

Theorem
The (linear) congruence equation ax ≡ b (mod m) is solvable among
integers if, and only if, gcd(a, m)|b.
Proof: we can derive a Diophantine equation from the congruence
equation:

ax ≡ b (mod m) ⇔ m|(ax − b) ⇔
⇔ ∃y ∈ Z : my = ax − b ⇔ ax − my = b

Remark: if c ∈ Z is a solution, then so is c + km.

Example: 13x ≡ 5 (mod 29)

Bernadett Aradi Discrete mathematics 2019 Fall 30 / 85

Complex numbers
Looking for solutions of equations in different sets:
N: 5 + x = 3 ⇒ not solvable
Z: 5 · x = 3 ⇒ not solvable
Q: x 2 = 3 ⇒ not solvable
R: x 2 = −3 ⇒ not solvable
√
Let’s extend” R with −1.
”
Notation, definition
√
The symbol i := −1 is the imaginary unit.

Definition
Numbers of the form a + bi where a, b ∈ R and i 2 = −1, are called
complex numbers. The set of complex numbers is denoted by C.

Let z = a + bi ∈ C. This is called the algebraic form of z.

a = <(z): real part of z
b = =(z): imaginary part of z.
Bernadett Aradi Discrete mathematics 2019 Fall 31 / 85
Operations with complex numbers, visual representation
Operations in C
If z = a + bi and w = c + di are complex numbers, then
z + w := (a + c) + (b + d)i,
z · w := (ac − bd) + (ad + bc)i.

Visual representation: on the complex plane.

A complex number z = a + bi is uniquely determined by a and b, but by
two other values as well: √
the absolute value of z: r := |z| := a2 + b 2
the argument of z: ϕ. We choose this such that it satisfies
a = r · cos ϕ,
b = r · sin ϕ.
With the help of these we can write z as
z = r · (cos ϕ + i · sin ϕ),
which form is unique if r > 0 and ϕ ∈ [0, 2π[. This is called the
trigonometric form of z.
Bernadett Aradi Discrete mathematics 2019 Fall 32 / 85
Operations with the trigonometric form
Examples:
1 What is the algebraic form of the complex number which has absolute
value 3 and argument π4 ?
√
2 What is the trigonometric form of z = 3 − i?
Definition
The conjugate of z = a + bi is z̄ = a − bi.
Then z · z̄ = (a + bi)(a − bi) = a2 + b 2 = |z|2 .
Let
z1 = r1 · (cos ϕ1 + i · sin ϕ1 ) and z2 = r2 · (cos ϕ2 + i · sin ϕ2 ).


Multiplication: z1 · z2 = r1 r2 · cos(ϕ1 + ϕ2 ) + i · sin(ϕ1 + ϕ2 )
Division: zz21 = rr12 · cos(ϕ1 − ϕ2 ) + i · sin(ϕ1 − ϕ2 )

Powers: if z = r · (cos ϕ + i · sin ϕ) and n ∈ Z, then

z n = r n · cos(nϕ) + i · sin(nϕ)


(Moivre’s formula).
√
Example: z = 3 − i, z 60 =?
Bernadett Aradi Discrete mathematics 2019 Fall 33 / 85
Determining the nth roots in C
√
n
z =?
The equation x n = z (where x is the unknown parameter) has solutions as
the nth roots of z, and there are n of them. w0 , w1 , . . . , wn−1
If w = % · (cos ψ + i · sin ψ) is an nth root of z, then
√
%n = r ⇒ % = n r (uniquely determined positive real number),
nψ ≈ ϕ ⇒ nψ = ϕ + 2kπ.

Theorem – nth roots of a complex number

If z = r · (cos ϕ + i sin ϕ) and n ∈ N, then the equation x n = z has exactly
n solutions, these are
√
 
n ϕ + 2kπ ϕ + 2kπ
wk = r · cos + i · sin , k = 0, 1, . . . , n − 1.
n n
√ √
Example: z = 3 − i, 3 z =?
Bernadett Aradi Discrete mathematics 2019 Fall 34 / 85
Roots of unity
Definition
The nth roots of the (complex) number 1 are called the nth roots of unity.
Thus, these are the solutions of the equation x n = 1.

Since
z = 1 = 1 + 0 · i = cos 0 + i · sin 0,
and the nth roots of a complex number are given by the formula
√
 
n ϕ + 2kπ ϕ + 2kπ
r · cos + i · sin , k = 0, 1, . . . , n − 1,
n n
the nth roots of unity are

2kπ 2kπ
+ i · sin
εk = cos , k = 0, 1, . . . , n − 1.
n n
Remark: ∀n ∈ N we have ε0 = 1.
Examples: what are the nth roots of unity in the cases n = 2, n = 3 and
n = 4? Plot them on the complex plane.
Bernadett Aradi Discrete mathematics 2019 Fall 35 / 85
Polynomials
Definition
Let x be a so-called indeterminate (or variable, a symbol). The expression
X n
p(x) = ai x i = a0 + a1 x + a2 x 2 + · · · + an x n ,
i=0
where ai ∈ R, is called a polynomial.
The set of polynomials with real coefficients is denoted by R[x].
If an 6= 0, then n is the degree or order of the polynomial. Notation:
deg(p) = n.
The real numbers ai are called the coefficients of the polynomial.
If p(x) = a0 , then it is a zero-order or constant polynomial.
Examples:
p1 (x) = 3 + 2x + x 4 + 3x 5 → degree 5 polynomial
p2 (x) = 2 + x 3 + 3x 4 + 0 · x 5 → degree 4 polynomial
Bernadett Aradi Discrete mathematics 2019 Fall 36 / 85
Operations with polynomials
Definition
Let us consider the polynomials
p(x) = a0 + a1 x + · · · + an x n and q(x) = b0 + b1 x + · · · + bm x m .
The two polynomials are equal if n = m and ai = bi , i = 0, 1, . . . , n.
The sum of the two polynomials if, e.g., n > m, is
(p + q)(x) :=p(x) + q(x) = (a0 + b0 ) + (a1 + b1 )x + · · · +
+ (am + bm )x m + am+1 x m+1 + · · · + an x n .

The product of the two polynomials is

(p · q)(x) :=p(x) · q(x) = (a0 · b0 ) + (a0 b1 + a1 b0 )x+
+ (a0 b2 + a1 b1 + a2 b0 )x 2 + · · · + an bm x m+n .
Thus:
deg(p + q) = max{deg(p), deg(q)}
deg(p · q) = deg(p) + deg(q)
Bernadett Aradi Discrete mathematics 2019 Fall 37 / 85
Euclidean division for polynomials
Theorem – Euclidean division for polynomials
If
p(x) = an x n + · · · + a1 x + a0 ,
s(x) = bm x m + · · · + b1 x + b0 ,

where an 6= 0, bm 6= 0 and m < n, then there exist uniquely polynomials

q(x) and r (x) such that
p(x) = s(x) · q(x) + r (x), deg(q) = n − m, deg(r ) < m = deg(s).

Example: p(x) = x 4 + 3x 2 − 4, s(x) = x 2 + 2x

Definition
If in the previous theorem p(x) = s(x) · q(x), that is, r (x) = 0, then s(x)
is a divisor of p(x), which we denote by s(x)|p(x).

Example: p(x) = x 5 − 3x 4 + 4x + 1, s(x) = x 2 + x + 1

Bernadett Aradi Discrete mathematics 2019 Fall 38 / 85
The roots of polynomials
Definition
Let p(x) be a polynomial with real (or complex) coefficients, that is,
p(x) ∈ R[x] (or p(x) ∈ C[x]). The number b ∈ C is a root or solution of
p(x) if p(b) = 0.

Remark: If b is a root of p(x), then (x − b)|p(x).

For second-order polynomials:
ax 2 + bx + c = a(x − x1 )(x − x2 )
p(x) = x 3 + x 2 − 2x − 8, since p(2) = 0, x0 = 2 is a root
Definition
The multiplicity of the root b in the polynomial p(x) is k if (x − b)k |p(x),
but (x − b)k+16 | p(x). If k = 1, then b is a simple root, if k > 1, then it is
a multiple root of p(x).
E.g: What is the multiplicity of x0 = 1 in the polynomial below?
p(x) = 2x 5 − 4x 4 + 6x 3 − 14x 2 + 16x − 6
Bernadett Aradi Discrete mathematics 2019 Fall 39 / 85
The Fundamental Thm of Algebra and its consequences
Theorem – the Fundamental Theorem of Algebra
Let p(x) ∈ C[x] be a non-constant polynomial. Then ∃x0 ∈ C : p(x0 ) = 0,
that is, p(x) has a complex root.

Remark: Let p(x) ∈ C[x] be a polynomial of degree n (n ≥ 1) and let

x0 ∈ C be a root of it. Then (x − x0 )|p(x), thus:
p(x) = (x − x0 ) · q(x), ahol deg(q) = n − 1.
But the Fundamental Thm of Algebra holds also for q(x), so there exists a
root x1 ∈ C of it, which implies the form q(x) = (x − x1 ) · q1 (x), and that
p(x) = (x − x0 ) · (x − x1 ) · q1 (x); ...
Corollaries
A degree n polynomial with complex coefficients has, counted with
multiplicity, exactly n complex roots.
A degree n polynomial with real coefficients has exactly n complex
and at most n real roots.
Bernadett Aradi Discrete mathematics 2019 Fall 40 / 85
The factored form of polynomials (over R)
p(x) = an (x − x1 )α1 . . . (x − xk )αk · (x 2 + b1 x + c1 )β1 . . . (x 2 + bl x + cl )βl

where (x − xi )αi : linear (or first-order) factors

and (x 2 + bj x + cj )βj : second-order factors,
they cannot be factorized over R
non-real (complex) roots are here,
which are pairwise conjugate
n = deg(p) = α1 + · · · + αk + 2β1 + · · · + 2βl
If n is odd, then ∃αi 6= 0, so in this case xi ∈ R is a root.
One more corollary of the Fundamental Thm of Algebra
If p(x) is an odd degree polynomial with real coefficients, then it has
a real root.
The factored form over C:
p(x) = an (x − x1 )α1 . . . (x − xj )αj , where n = α1 + · · · + αj .
Bernadett Aradi Discrete mathematics 2019 Fall 41 / 85
Horner’s method
Horner’s method is an efficient algorithm for the evaluation of a
polynomial. Efficient = fewer number of arithmetic operations.
Let p(x) = an x n + an−1 x n−1 + · · · + a2 x 2 + a1 x + a0 .
Note that
p(x) = . . . ((an x + an−1 ) · x + an−2 ) · x + · · · + a1 ) · x + a0 .
Example.
p(x) = 2x 5 − 4x 4 + 6x 3 − 14x 2 + 16x − 6, p(−2) =?, p(1) =?

Number of arithmetic operations to perform without Horner’s

method: n − 1 + n = 2n − 1 multiplications and n additions
Number of arithmetic operations to perform with Horner’s method: n
multiplications, n additions

Theorem
The integer roots of a polynomial with real coefficients divide the constant
term of the polynomial.
Bernadett Aradi Discrete mathematics 2019 Fall 42 / 85
Combinatorics – Permutation of distinct elements

Definition
Let A be a set with n distinct elements. By a permutation of A we mean
an arrangement of all the members of A into some sequence.

Theorem
The number of all permutations of a set of n distinct elements is
Pn = n! = n(n − 1)(n − 2) . . . 2 · 1.
Other notation: P(n, n) = n!.

Examples:
(1) There are 10 participants at a running competition. How many
different orders can they finish in?
(2) How many 5 digit numbers can be formed from the digits 3,4,5,7,9, if
each digit can be listed only once?
What if we consider the digits 2,2,2,7,7?

Bernadett Aradi Discrete mathematics 2019 Fall 43 / 85

Permutation of multisets or ordering with identical items
How many 5 digit numbers can be formed from the digits 2,2,2,7,7?
Solution: If we treat all the 2’s and 7’s as different numbers, then we had
5! possible orders. But by changing the orders of the 2’s, for example, we
get the same 5-digit number. ⇒ We have to divide 5! by the possible
orders of identical elements, so the result is:
5!
= 10.
2! · 3!
Theorem
If we consider n elements of k type, `1 from the first type, `2 from the
second type, etc. (so `1 + `2 + · · · + `k = n), then the number of all
permutations of these n elements is
n!
Pn`1 ,...,`k =
`1 ! . . . `k !

Example: We have 2 red, 1 orange and 3 yellow flowers, which we want to

put in our window. How many possibilities do we have for the order of the
flowers?
Bernadett Aradi Discrete mathematics 2019 Fall 44 / 85
Partial permutations or k-permutations of n
Definition and theorem
In the case of a k-permutation of n or partial permutation we consider
arrangements of a fixed length k of elements taken from a given set of size
n. Here each element can occur at most once. The number of these
arrangements is
n!
P(n, k) = nPk = = n · (n − 1) . . . (n − k + 1).
(n − k)!
Here necessarily n ≥ k.
So we choose k elements out of n and arrange them into some order
ordered selections without repetition
Examples: (1) There are 10 participants at a running competition. How
many possibilities are there for the podium (that is, for the first 3 places)?
(2) There is a game, where there are 5 different prizes and they choose the
winners from 200 participants randomly. How many possibilities are there
for choosing the winners if everyone can win at most 1 prize?
What if the participants can be chosen more than once?
Bernadett Aradi Discrete mathematics 2019 Fall 45 / 85
Permutations with repetition
Definition and theorem
By permutations with repetition we mean ordered arrangements of the
elements of a set of size n of length k where repetition is allowed. These
are also called k-tuples. The number of all arrangements of this type is

P(n, k)rep = nk .

So we choose k elements and arrange them into some order, the elements
can occur more than once. Thus here n < k is possible as well.
ordered selections with repetition
Examples: (1) In how many ways can one fill a toto coupon? (14 matches,
3 possible results: 1, 2, or X)
(2) How many subsets does a set with n elements have?
The subsets are in a one-to-one correspondence with binary sequences of
length n: 100101 . . . 110.
P(2, n)rep = 2n possibilities.
Bernadett Aradi Discrete mathematics 2019 Fall 46 / 85
Combination without repetition
Definition and theorem
A combination is a way of selecting items from a collection, such that
(unlike permutations) the order of selection does not matter. So we choose
a subset of k elements of a set with n elements. The number of all ways
to select k items out of n elements without regard to order of selection is:
 
n! n
C (n, k) = nCk = =: .
k!(n − k)! k
By definition 0! = 1.
Here necessarily n ≥ k.
Examples:
(1) Find the number of possible fillings of a lottery coupon (5 numbers
from 90).
(2) There is a game, where there are 5 alike prizes and they choose the
winners from 200 participants randomly. How many possibilities are there
for choosing the winners if everyone can win at most 1 prize?
What if the participants can be chosen more than once?
Bernadett Aradi Discrete mathematics 2019 Fall 47 / 85
Combination with repetition
Definition and theorem
A k-combination with repetitions, or k-multicombination, or multisubset
of size k from a set S is given by a sequence of k not necessarily distinct
elements of S, where order is not taken into account. The number of all
ways to select k items out of n elements without regard to order of
selection is:  n  n + k − 1
C (n, k)rep = = .
k k
Here n < k is possible as well.
Examples: (1) In how many ways can we distribute 10 (similar) apples
among 4 children?
(2) If we roll 3 (alike) dice, how many possible ways are there for the
results (distribution of the thrown numbers)?
Proposition
Let k, n ∈ N ∪ {0}, n ≥ k. Then
   
n n
= .
k n−k
Bernadett Aradi Discrete mathematics 2019 Fall 48 / 85
Binomial theorem or binomial expansion
Theorem – binomial theorem
Let x, y ∈ C, n ∈ N. Then
     
n n n n n−1 n
(x + y ) = x + x y+ x n−2 y 2 +
n n−1 n−2
    n  
n n−1 n n X n k n−k
+ ··· + xy + y = x y .
1 0 k
k=0

Definition
n


The expression k is called a binomial coefficient.

Proposition
For all n ∈ N, 0 < k < n, we have
     
n n−1 n−1
= + .
k k −1 k
Corollaries: Pascal’s triangle; number of subsets of a set with n elements.
Bernadett Aradi Discrete mathematics 2019 Fall 49 / 85
Linear algebra, vector spaces
Definition
A non-empty set V is called a vector space over R and the elements of V
are called vectors if there are two operations
vector addition: V × V → V , (v , w ) 7→ v + w ,
scalar multiplication: R × V → V , (λ, v ) 7→ λv ,
satisfying the conditions below:
Vector addition:
(a) commutativity, that is ∀v , w ∈ V : v + w = w + v ;
(b) associativity, that is ∀u, v , w ∈ V : (u + v ) + w = u + (v + w );
(c) there exists a zero vector: 0 ∈ V , such that v + 0 = v (∀v ∈ V );
(d) ∀v ∈ V there exists a so-called additive inverse,
a vector denoted by −v , such that v + (−v ) = 0.
Scalar multiplication:
(a) ∀λ, µ ∈ R, v ∈ V : (λ + µ)v = λv + µv ;
(b) ∀λ ∈ R, v , w ∈ V : λ(v + w ) = λv + λw ;
(c) ∀λ, µ ∈ R, v ∈ V : λ(µv ) = (λµ)v ;
(d) ∀v ∈ V : 1v = v .
Bernadett Aradi Discrete mathematics 2019 Fall 50 / 85
Examples for vector spaces, linear subspace

Examples:
1 R2 : the vectors of the plane. Elements: ordered pairs (x, y ), x, y ∈ R.
2 Rn , its elements: ordered n-tuples: (x1 , x2 , . . . , xn ), xi ∈ R.
Definition
A non-empty subset W of the vector space V is called a linear subspace
(or simply a subspace) of V if it is a vector space itself, that is, W is
closed under vector addition and scalar multiplication.
Examples:
1 {0} and V are linear subspaces of V , called trivial subspaces.
2 In R2 the elements of the form (x, 0) constitute a subspace (x ∈ R).
3 If v is a fixed vector is R2 , then W = {λv ∈ V | λ ∈ R} is a subspace.

Bernadett Aradi Discrete mathematics 2019 Fall 51 / 85

Linear combination
Definition
Let v1 , v2 , . . . , vn be vectors in V . The linear combinations of them are
vectors of the form
λ1 v1 + λ2 v2 + · · · + λn vn ; λ1 , λ2 , . . . , λn ∈ R.
Remark: The zero vector can always be obtained as a linear combination.
This is called the trivial linear combination.
Examples:
1 V = R2 , v = (2, 1), w = (0, 3).

Which vectors in R2 can be obtained as linear combinations of v and

w?
2 Let us fix a vector v 6= 0, linear combinations: vectors of the form λv .

Theorem and definition

Let v1 , v2 , . . . , vn be vectors in V . Then the set of all linear combinations
of these vectors form a linear subspace of V , called the subspace spanned
or generated by v1 , v2 , . . . , vn .
Notation: L(v1 , . . . , vn ).
Bernadett Aradi Discrete mathematics 2019 Fall 52 / 85
Linearly dependent and independent vectors
Definition
Let v1 , v2 , . . . , vn be vectors in V . We say that these vectors are linearly
dependent if there exist scalars λ1 , λ2 , . . . , λn ∈ R not all 0, such that
λ1 v1 + λ2 v2 + · · · + λn vn = 0.
(Thus if the zero vector can be obtained as a non-trivial linear
combination of the vectors.) Otherwise we say that the vectors are linearly
independent.
Remark: So in case of linear independence the condition
λ1 v1 + λ2 v2 + · · · + λn vn = 0
implies that λi = 0, ∀i ∈ {1, . . . , n}.
Example: V = R2 , v = (2, 1), w = (0, 3), are v and w linearly
independent?
Proposition
A set of vectors is linearly dependent if, and only if, some of the vectors
can be obtained as a linear combination of the rest of the vectors.
Bernadett Aradi Discrete mathematics 2019 Fall 53 / 85
Proposition
Consider a fixed set of vectors in a vector space.
1 If two (or more) of the vectors are the same, then the vectors are
linearly dependent.
2 If one of the vectors is a scalar multiple of another vector, then the
vectors are linearly dependent.
3 If the zero vector is among the vectors, then the vectors are linearly
dependent. That is, a linearly independent set of vectors cannot
contain the zero vector.
4 If a subset of the vectors is linearly dependent, then the entire set is
linearly dependent.

Bernadett Aradi Discrete mathematics 2019 Fall 54 / 85

Basis
Definition
Let G be a set of vectors of V . We say that G generates the vector space
V if the spanned subspace of G is the whole vector space. In this case all
vectors of V can be obtained as a linear combination of elements of G.

Example: V = R2 , v = 21 , w = 03 . Then {v , w } generates R2 . Let

u = 10 . Then {u, v , w } generates R2 as well, however, this set is linearly

dependent, since 6u − 3v + w = 0. ⇒ A vector of R2 can be expressed as

a linear combination of {u, v , w } in more than one ways, e.g.,
 
2 4
= v + w = 2u + w .
4 3

Definition
A basis of V is a linearly independent set of vectors which generate V .

Bernadett Aradi Discrete mathematics 2019 Fall 55 / 85

Basis, dimension
Basis: linearly independent set of vectors spanning the whole vector space.

If B is a basis, then all elements of V can be uniquely expressed as a

linear combination of the elements of B.
There are infinitely many bases of V .
Theorem and definition
Given a vector space V , all of its bases have the same cardinality (consist
of the same number of vectors). This number is called the dimension of
the vector space. Notation: dim(V ). Remark: if V = {0}, then
dim(V ) = 0.

Examples:
1 Rn : vector space of n-tuples. (Vector addition, scalar multiplication

element-wise.) A basis: {e1 , e2 , . . . , en }, it is called the natural (or

canonical) basis. ⇒ dim(Rn ) = n.
2 R2 : special case of previous example (n = 2). Natural basis: {e , e },
1
2
where e1 = 10 , e2 = 01 . Another basis: {v , w }, v = 21 , w = 03 .

Bernadett Aradi Discrete mathematics 2019 Fall 56 / 85

Coordinates with respect to a basis
Theorem
If we find n linearly independent vectors in an n-dimensional vector space,
then it is a basis.
Definition
Let V be a vector space, B = {b1 , . . . , bn } is one of its basis. Then all
v ∈ V can be uniquely expressed as a linear combination of the elements
of B, thus there exist unique scalars λ1 , λ2 , . . . , λn , such that
v = λ1 b1 + · · · + λn bn .
These scalars are called the coordinates of v with respect to the basis B.
Then in the basis B the vector v has the form:
 
λ1
 λ2 
v =  . .
 
.
 . 
λn
Bernadett Aradi Discrete mathematics 2019 Fall 57 / 85
The rank of a set of vectors
Definition
Let A be a set of vectors. The rank of A is the dimension of the
generated vector space:
rank(A) = dim(L(A)).
Example: V = R3 , let A = {u, v , w }, where
     
1 1 3
u =  1 , v =  3 , w =  5 .
1 0 2
Since w = 2u + v , w is in the subspace spanned by u and v . But u and v
are linearly independent, thus rank(A) = 2.
Remark: Let V be an n-dimensional vector space, A = {v1 , . . . , vm } ⊂ V .
Then rank(A) ≤ n and rank(A) ≤ m.
Theorem
The rank of a set of vectors doesn’t change if we add the linear
combination of some of the vectors to a vector.
Bernadett Aradi Discrete mathematics 2019 Fall 58 / 85
Matrices
Definition
A matrix is a rectangular array of numbers. An m × n (m-by-n) matrix has
m rowsand n columns. 
a11 a12 . . . a1n
 a21 a22 . . . a2n 
A= . elements of A : aij A = (aij )
 
. .. .. 
 . . . 
am1 am2 . . . amn
The set of all m × n matrices is denoted by Mm×n .

Definition
If n = m, then the matrix is a square matrix.
The main diagonal of a matrix is formed by the elements
(a11 , a22 , a33 , . . . ).
The identity matrix of size n is the n × n matrix such that the
elements on the main diagonal are equal to 1 and all other elements
are zero. Notation: In .
Bernadett Aradi Discrete mathematics 2019 Fall 59 / 85
Matrix operations
1. Matrix addition
We can only add matrices of the same type.
If A = (aij ) and B = (bij ) are m × n matrices, then we calculate the sum
entrywise: C = A + B, where cij = aij + bij ; i = 1, . . . , m, j = 1, . . . , n.

2. Scalar multiplication
We do the scalar multiplication entrywise. That is, let λ ∈ R,
A = (aij ) ∈ Mm×n , λA = (λaij ) ∈ Mm×n .

3. Matrix multiplication
Let A = (aij ) be an m × k and B = (bij ) be a k × n matrix. Then the
product of A and B is the m × n matrix C = (cij ), such that
k
X
cij = air brj .
r =1

Bernadett Aradi Discrete mathematics 2019 Fall 60 / 85

Theorem – properties of matrix multiplication
If A is an m × n matrix, then Im · A = A and A · In = A.
If A, B, C are such matrices that AB and BC exist, then
(AB)C = A(BC ). The matrix multiplication is associative.
If A and B are of the same size and AC exists, then BC exists as well
and (A + B)C = AC + BC .
Matrix multiplication is not commutative, that is, in general
AB 6= BA.

Definition
Let A be an m × n matrix. The n × m matrix, which has rows as the
columns of A is denoted by AT and it is called the transpose of A.

Proposition – properties of transposition

(AT )T = A
Transposition and matrix multiplication: (AB)T = B T · AT .

Bernadett Aradi Discrete mathematics 2019 Fall 61 / 85

Definition
Let A be a square matrix of order n.
A is symmetric if AT = A,
A is skew-symmetric if AT = −A.

Examples:
   
2 −3 4 0 2 1
A =  −3 −1 7  B =  −2 0 −5 
4 7 0 −1 5 0

Here A is symmetric, B is skew-symmetric.

Bernadett Aradi Discrete mathematics 2019 Fall 62 / 85

The inverse of a matrix
Definition
We say that a square matrix A of order n is invertible or that it has an
inverse if there exists a square matrix B of order n, such that
AB = BA = In .
Theorem
If A is invertible, then its inverse is uniquely determined. Notation: A−1 .
Example:    
4 3 −1 −5 3
A= A =
7 5 7 −4

Proposition – properties of matrix inverse

If A is invertible, then so is A−1 , and (A−1 )−1 = A.
If A and B are invertible and AB exists, then (AB)−1 = B −1 A−1 .
If A is invertible, then so is AT , and (A−1 )T = (AT )−1 .
Bernadett Aradi Discrete mathematics 2019 Fall 63 / 85
Determinants
Definition
Let n ∈ N and let σ denote a permutation of the set {1, 2, . . . , n}, that is,
let
σ : {1, 2, . . . , n} → {1, 2, . . . , n}, i 7→ σ(i)
be a bijective function. (Here σ(i) denotes the ith element in the
permutation.) We say that in the permutation σ the elements i and j are
in inversion if i < j but σ(i) > σ(j). The permutation σ is called even if
the number of pairs being in inversion in σ is even, and odd if this number
is odd.
Examples: {1, 2, 3, 4},
σ1 = (1, 3, 4, 2) Number of inversions: 2
σ2 = (1, 2, 3, 4) Number of inversions: 0
σ3 = (4, 3, 2, 1) Number of inversions: 6
σ4 = (2, 3, 4, 1) Number of inversions: 3
Bernadett Aradi Discrete mathematics 2019 Fall 64 / 85
Determinants
Definition
Let A = (aij ) be a square matrix. Let us choose n elements of A such that
we choose exactly one element from each row and each column. The
chosen elements: a ,a ,...,a .
1σ(1) 2σ(2) nσ(n)
The determinant of A is X
det(A) = |A| = ε(σ)a1σ(1) a2σ(2) . . . anσ(n) .
 σ
1, if σ is even,
Here ε(σ) =
−1, if σ is odd.
There are n! terms in the sum above.
Example:
1 n = 2: det(A) = |A| = a a
11 22 − a12 a21 .
2 n = 3: det(A) = . . . .

Theorem
If A and B are square matrices of the same size, then
det(AB) = det(A) · det(B).
Bernadett Aradi Discrete mathematics 2019 Fall 65 / 85
Determinant of matrices of special form
Proposition
For any n ∈ N the determinant of the identity matrix is 1.

det(In ) = 1

Proposition
Let A be an upper triangular matrix, that is, a square matrix with zeros
underneath its main diagonal:
 
a11 a12 a13 . . . a1n
 0 a22 a23 . . . a2n 
 
A= 0 0 a33 . . . a3n .
 
 .. .. .. 
 . . . 
0 0 0 ... ann

Then the determinant of A is the product of the elements in the main

diagonal.
Bernadett Aradi Discrete mathematics 2019 Fall 66 / 85
Geometric meaning of the determinant
2-by-2 determinants: it’s absolute value is the area of the
parallelogram determined by the rows of the determinant, as vectors

a b
|A| = = ad − bc
c d

3-by-3 determinants: it’s absolute value is the volume of the

parallelepiped determined by the rows of the determinant, as vectors
Bernadett Aradi Discrete mathematics 2019 Fall 67 / 85
Proposition – properties of the determinant
det(A) = det(AT )
If A has a row full of zeros, then det(A) = 0.
If we interchange 2 rows of A, then the sign of the determinant
changes.
If one row of A is a scalar multiple of another row, then det(A) = 0.
If we multiply a row of A by a real number λ, then the obtained
matrix has determinant λ · det(A).
If we multiply each row of A by a real number λ, then the obtained
matrix has determinant λn · det(A).
The determinant doesn’t change if we add a scalar multiple of a row
to another row.
If a row of A is the linear combination of the other rows, then
det(A) = 0.
The properties above are true if we consider columns instead of rows.
Corollary
If det(A) 6= 0, then the rows (or columns) of A are linearly independent
vectors. Then is A is of size n × n: its rows form a basis of Rn .
Bernadett Aradi Discrete mathematics 2019 Fall 68 / 85
Determinant and matrix inverse

Definition
We say that the square matrix A is regular if det(A) 6= 0.
Otherwise A is said to be singular.

Theorem
A matrix is invertible if, and only if, it is regular. (That is, it’s determinant
is non-zero.)

Proposition
If A is invertible, then

det(A)−1 = det(A−1 ).

Bernadett Aradi Discrete mathematics 2019 Fall 69 / 85

How to calculate the determinant?
1 The rule of Sarrus: only for 2 × 2 and 3 × 3 determinants
2 Gaussian elimination (or row reduction): The modifications below
doesn’t change the determinant. With the help of them we try to
make our determinant to be upper triangular, then the determinant is
the product of the elements in the main diagonal.
I If we multiply the determinant by a non-zero scalar, instead of
multiplying all elements of a fixed row by the same scalar.
I If we add a scalar multiple of a a row to another row.
I If we interchange two rows, the determinant changes sign.
3 Laplace expansion: We choose an arbitrary row or column of the
determinant. E.g., if we choose the i th row, then
n
X
det(A) = |A| = aij Cij , where
j=1
I Cij is the cofactor of A corresponding to the element aij , that is,
Cij = (−1)i+j Aij ,
I Aij is the (n − 1) × (n − 1) determinant obtained from A by deleting
the i th row and j th column of A.
Bernadett Aradi Discrete mathematics 2019 Fall 70 / 85
Systems of linear equations
Definition
The system of equations
a11 x1 + a12 x2 + · · · + a1n xn = b1
a21 x1 + a22 x2 + · · · + a2n xn = b2
.. ..
. .
am1 x1 + am2 x2 + · · · + amn xn = bm
where the real numbers aij (i ∈ {1, . . . , m}, j ∈ {1, . . . , n}) and bk
(k ∈ {1, . . . , m}) are known, the variables x1 , . . . , xn are unknown, is
called a system of linear equations.
aij : the coefficients of the system of linear equations
bk : the constant terms
the coefficient matrix and the augmented matrix:
   
a11 . . . a1n a11 . . . a1n b1
 a21 . . . a2n   a21 . . . a2n b2 
A= . and A|b =  .
   
. . ..
 .. ..   .. ..
 
. 
am1 . . . amn am1 . . . amn bm
Bernadett Aradi Discrete mathematics 2019 Fall 71 / 85
Solvability of systems of linear equations
The corresponding matrix equation: Ax = b.
Definition
The system of linear equations is
solvable if there exists at least one solution, that is, an x ∈ Rn such
that Ax = b holds;
I determined if there is exactly 1 solution;
I undetermined if there are more than 1 solutions;
overdetermined if it doesn’t have a solution.
Definition
The rank of a matrix is the rank of the system of column vectors of the
matrix. Notation: rank(A).
Theorem – condition on solvability
A system of lin. eq.s is solvable if, and only if rank(A) = rank(A|b).
If it is solvable and rank(A) = n (where n is the number of unknown
parameters), then the system is determined, if rank(A) < n, then
undetermined.
Bernadett Aradi Discrete mathematics 2019 Fall 72 / 85
Solutions of a system of linear equations
Definition
A system of linear equations is homogeneous if b = 0, thus then the matrix
equation has the form Ax = 0. Otherwise it’s called nonhomogeneous.
Remark: 0 is a solution of any homogenous system of linear equations.
Proposition – solutions of a homogeneous system of linear equations
The solutions of a homogeneous system of linear equations form a vector
subspace of Rn with dimension n − rank(A).

Proposition – solutions of a nonhomogeneous system of linear

equations
The solution set of a (solvable) nonhomogeneous system of linear
equations Ax = b is of the form x0 + H, where
x0 is a particular solution of the system of linear equations;
H is the solution set of the corresponding homogeneous system of
linear equation, that is Ax = 0.
Bernadett Aradi Discrete mathematics 2019 Fall 73 / 85
Solving a system of linear equations with Gaussian elimination
The set of solutions of a system of linear equations does not change, if we
multiply an equation by a nonzero constant;
add a scalar multiple of an equation to another equation;
interchange two equations;
discard an equation which is a scalar multiple of another equation.
We annihilate the numbers under the main diagonal with the modifications
above. The resulting system is easier to solve.

6 0), then the

If during the process we obtain a row like (0 . . . 0| =
system of linear equations is overdetermined.
If at the end of the process there are n number of rows, then the
system is determined, if fewer number of rows remains, then
undetermined. (Here n is the number of the unknown parameters.)

Bernadett Aradi Discrete mathematics 2019 Fall 74 / 85

Linear transformations
Definition
Let V be a vector space. ϕ : V → V is a linear transformation if it is
additive, that is ∀u, v ∈ V : ϕ(u + v ) = ϕ(u) + ϕ(v );
homogeneous, that is ∀v ∈ V , λ ∈ R: ϕ(λv ) = λϕ(v ).
Remark: linear transformations map the zero vector to the zero vector.
Examples:
Rotations, reflections, uniform scaling.
Projections, e.g., onto a fixed plane of R3 .
Identity transformation: ϕ(v ) = v , ∀v ∈ V .
Proposition
A linear transformation is uniquely determined by its action on a basis of
V , that is, if B = (b1 , b2 , . . . , bn ) is a basis of V , and w1 , w2 , . . . , wn are
arbitrary vectors, then there uniquely exists a linear transformation ϕ such
that ϕ(bi ) = wi . Furthermore, if v = λ1 b1 + λ2 b2 + · · · + λn bn , then its
image by ϕ is
ϕ(v ) = λ1 w1 + λ2 w2 + · · · + λn wn .
Bernadett Aradi Discrete mathematics 2019 Fall 75 / 85
The matrix of a linear transformation
Definition
Let V be an n-dimensional vector space, B = (b1 , b2 , . . . , bn ) a basis of V ,
and consider a linear transformation ϕ : V → V .
Then the matrix of ϕ with respect to B is the n × n matrix, such that in its
i th column there are the coordinates of ϕ(bi ) with respect to the basis B.
Example: Let ϕ : R2 → R2 , (x, y ) 7→ ϕ(x, y ) = (2x − y , −12x + 3y ).
The matrix of ϕ in the natural basis. ϕ(e1 ) = ϕ(1, 0) = (2, −12),
ϕ(e2 ) = ϕ(0, 1) = (−1, 3), thus the matrix of ϕ in this basis is
 
2 −1
Aϕ =
−12 3
The matrix of ϕ w.r.t. the basis b1 = (1, 1), b2 = (0, −1). Then
ϕ(b1 ) = (1, −9) and ϕ(b2 ) = (1, −3). These vectors in the basis (b1 , b2 ):
ϕ(b1 ) = (1, −9) = 1 · b1 + 10 · b2 , ϕ(b2 ) = (1, −3) = 1 · b1 + 4 · b2 .
So the sought-for matrix:  
1 1
[Aϕ ](b1 ,b2 ) = .
10 4
Bernadett Aradi Discrete mathematics 2019 Fall 76 / 85
Application of the matrix of a linear transformation
Proposition
The determinant and the rank of the matrix of a linear transformation is
independent of the chosen basis.

Proposition
If the matrix of ϕ with respect to the basis B is A, then ϕ(v ) = Av .

Examples: Rotations and reflections in R2 (with respect to the natural

basis):
   
cos α − sin α cos(2α) sin(2α)
rotα = reflα =
sin α cos α sin(2α) − cos(2α)

So if we rotate the vector v = 26 by 60◦ counter-clockwise about the

origin:
1
√ !
3
! √ !
cos 60◦ − sin 60◦ − −
  
2 2 1 3 3
◦ ◦ = √2 2
= √ .
sin 60 cos 60 6 3 1 6 3+3
2 2

Bernadett Aradi Discrete mathematics 2019 Fall 77 / 85

Eigenvectors and eigenvalues of a linear transformation
Definition
Let ϕ : V → V be a linear transformation. A non-zero vector v ∈ V is
called the eigenvector of ϕ if ∃λ ∈ R: ϕ(v ) = λv . Then λ is the
eigenvalue of ϕ associated with v .
Examples: eigenvectors of rotations, reflections, scalings.
Remarks:
If v is an eigenvector of ϕ, then the associated eigenvalue is uniqely
determined.
If λ is an eigenvalue, then the corresponding eigenvectors form a
vector subspace of V :
Lλ := {v ∈ V | ϕ(v ) = λv } : the eigenspace of ϕ associated with λ.
Definition and theorem
The characteristic polynomial of ϕ is the n-degree polynomial
det(A − λIn ), where n is the dimension of V and A is a matrix of ϕ with
respect to any basis. Its roots are just the eigenvalues of ϕ.
Bernadett Aradi Discrete mathematics 2019 Fall 78 / 85
Example to determine the eigenvalues and eigenvectors
Determine the eigenvalues and eigenvectors of the linear transformation
below.
ϕ : R2 → R2 , (x, y ) 7→ ϕ(x, y ) = (2x − y , −12x + 3y )

As
 we have seen,
 the matrix of ϕ w.r.t. the natural basis is
2 −1
. Thus the characteristic polynomial of ϕ is
−12 3
     
2 −1 1 0 2 − λ −1
det(A − λIn ) = −λ =
−12 3 0 1 −12 3 − λ
= (2 − λ)(3 − λ) − (−1)(−12) = λ2 − 5λ − 6 = (λ + 1)(λ − 6).

So the eigenvalues are λ1 = −1 and λ2 = 6. The corresponding

eigenvectors of λ2 = 6:
     
2x − y = 6x −4x − y = 0 x 1
⇒ ⇒ =t · , t ∈ R.
−12x + 3y = 6y −12x − 3y = 0 y −4

Bernadett Aradi Discrete mathematics 2019 Fall 79 / 85

Euclidean vector spaces
Definition
Let V be a vector space over R and assume there exists a map
h , i: V × V → R
(thus we assign to each pair of vectors v , w a real number denoted by
hv , w i), such that it is
(a) additive in its first variable: hu + v , w i = hu, w i + hv , w i;
(b) homogeneous in its first variable: hλv , w i = λhv , w i;
(c) symmetric: hw , v i = hv , w i;
(d) positive definite: ∀v ∈ V : hv , v i ≥ 0, and (hv , v i = 0 ⇔ v = 0).
Then the number hv , w i is called the scalar (or inner) product of v and w .
The vector space V endowed with the scalar product h , i : V × V → R is
called a Euclidean vector space. Notation: E = (V , h , i).

(a)+(b) ⇒ the scalar product is linear in its first variable

. . . +(c) ⇒ the scalar product is linear also in its second variable
Scalar product: positive definite symmetric bilinear form.
Bernadett Aradi Discrete mathematics 2019 Fall 80 / 85
Examples of Euclidean vector spaces
(1) V = R2 , |v |: the length of v
hv , w i = |v ||w | cos ∠ ⇒ h , i scalar product on R2
(2) V = Rn ,
let us fix a basis.
Consider v = (v1 , v2 , . . . , vn ), w = (w1 , w2 , . . . , wn ).
hv , w i = v1 w1 + v2 w2 + · · · + vn wn ⇒ scalar product over Rn
In the case of n = 2 and the choice of the natural basis we get (1).
(3) V = R3 , let us fix a basis.
Let v = (v1 , v2 , v3 ), w = (w1 , w2 , w3 ).
hv , w i = v1 w1 + 2v2 w2 + 3v3 w3 ⇒ scalar product over R3
⇒ There are more possible scalar products on a vector space.

Definition
The scalar product in (2) is called the canonical or natural scalar product
of Rn .
Bernadett Aradi Discrete mathematics 2019 Fall 81 / 85
The norm of vectors
Definition
Let E = (V , h , i) be a Euclidean vector space. The norm or length of a
vector v ∈ V is p
kv k := hv , v i.

Remark.: positive definiteness makes the square root possible.

q
Example: for the canonical scalar product of R2 : kv k = v12 + v22 = |v |.

Theorem – properties of the norm

Let E = (V , h , i) be a Euclidean vector space, k · k is the norm derived
from the scalar product. Then the following conditions hold:
∀v ∈ V : kv k ≥ 0, furthermore kv k = 0 ⇔ v = 0;
k · k is absolute homogeneous: ∀v ∈ V and λ ∈ R: kλv k = |λ|kv k;
it satisfies the triangle inequality: ∀v , w ∈ V : kv + w k ≤ kv k + kw k.
Here we have equality if, and only if, v and w are non-negative scalar
multiples of each other.
Bernadett Aradi Discrete mathematics 2019 Fall 82 / 85
Theorem – Cauchy–Schwarz inequality
Let v and w be vectors of the Euclidean space E = (V , h , i). Then
|hv , w i| ≤ kv k · kw k.
Equality holds if, and only if, v = λw , λ ∈ R.
Example: for the canonical scalar product of R2 :
q q
|v1 w1 + v2 w2 | ≤ v12 + v22 · w12 + w22 .

Definition
Let v and w be non-zero vectors of E. Then the angle of v and w is
hv , w i
arccos
kv k · kw k
π
If v or w is the zero vector, then their angle is arccos 0 = 2 by definition.

Remark.: due to the Cauchy–Schwarz inequality

hv , w i
−1 ≤ ≤ 1.
kv k · kw k
Bernadett Aradi Discrete mathematics 2019 Fall 83 / 85
Orthogonal vectors
Definition
We say that v and w are orthogonal if hv , w i = 0. Notation: v ⊥w .
A vector v ∈ V is called a unit vector if kv k = 1.
v
Remark.: ∀v ∈ V , v 6= 0 we have that kv k is a unit vector.

Proposition
Let u be a unit vector and v ∈ V arbitrary. Then the orthogonal projection
of v onto u (or the vector component of v in direction u) is hv , uiu.

Definition
A set {v1 , v2 , . . . , vn } of vectors is called orthogonal if it consists of
pairwise orthogonal vectors, that is, hvi , vj i = 0 whenever i 6= j.
The set is orthonormal if it consists of pairwise orthogonal unit
vectors.

Bernadett Aradi Discrete mathematics 2019 Fall 84 / 85

An example
Let us consider the vectors v and w in R2 :
   
−1 0
v= and w = .
1 −1

If we choose the canonical scalar product of R2 then

√
hv , w i = −1 · 0 + 1 · (−1) = −1, kv k = 2, kw k = 1.

However, if we choose the scalar product

   
v1 w1
hv , w i = 2v1 w1 +v1 w2 +v2 w1 +v2 w2 , for v = and w = ,
v2 w2

then

hv , w i = 2·(−1)·0+(−1)(−1)+1·0+1·(−1) = 0, kv k = 1, kw k = 1.

So {v , w } form an orthonormal set in R2 endowed with the latter scalar

product.
Bernadett Aradi Discrete mathematics 2019 Fall 85 / 85