The notation "MN" refers to the Matoušek--Nešetříl text
The notation "LIN" refers to the instructor's Linear Algebra notes, currently in progress.
"DO" problems are strongly recommended to check your understanding of the concepts; do not hand them in.
Problems labeled "HW" must be handed in at the beginning of the next class unless expressly stated otherwise.
BONUS PROBLEMS are not mandatory but the same deadline applies as to ordinary homework.
CHALLENGE PROBLEMS have no point value (but they earn you the
instructor's attention) and no deadline (except they expire when
discussed in class). Make sure you hand them in on a separate sheet,
state your name, the fact that this is a challenge problem
solution, and indicate the problem being solved. One further
request: if you hand in a solution to a challenge problem,
send email to the
instructor giving the problem number and a brief indication of the
problem (copied from the problem announcement: like "n+1 numbers"
or "another limit related to the def of "e"" -- no detailed description
needed, this suffices to remind me which problem it was). Such
email will create an easy record and help avoid mistakes in bookkeeping.
REWARD PROBLEMS are challenge problems that you should NOT hand in.
The solution is its own reward. No deadline. Of course you are
welcome to discuss your thoughts with the TA, the instructor,
and your peers.
If you hand in material before its due date, make sure you
put it on a separate sheet since solutions are graded in batches
by their due dates.
16.1 DO: Study Inclusion-Exclusion from MN, including the
chapter "Hatcheck Lady & Co."
16.2 DO (Inclusion-Exclusion, probability version): Let
A1,...,An be events
and let B be the complement of
A1 ∪ ... ∪ An.
Prove: P(B) = S0 - S1 + S2 - ...
where Sk is the sum of the probabilities of
the (n choose k) k-wise intersections
of the Ai. (So what is
S0 ?)
16.3 HW: (Truncated inclusion-exclusion: Bonferroni's
inequalities): With the notation of the previous exercise,
let Ri denote the truncation of the right hand side
of the Inclusion-Exclusion formula at item i, i.e.,
16.4 NOTATION: Let V be a vector space over the field F and
let
e=(e1 , ... , ek)
be a basis of V. Then every vector x ∈ V
can be expressed uniquely as a linear combination
x = ∑ αi ei.
The αi are the
coordinates of x with respect to
the basis e; we write [x]e
to denote the column vector
[α1, ..., αn]T.
(The superscript T indicates the transpose.)
16.5 NOTATION: Let V and W be vector spaces over the same field
F. Recall that a linear map φ : V → W
is a function that satisfies φ(x+y) = φ(x) + φ(y)
and φ(αx) = αφ(x). Let now
e = (e1 , ... , ek)
be a basis in V and
f = (f1 , ... , fm)
be a basis in W. We associate with φ
an m × k matrix A which we denote
by A = [φ]e,f ;
the j-th column of A is
[φ(ej)]f.
16.6 HW (a) Let V be the real plane and
ρα the rotation of V
by α about the origin. Let
e = (e1, e2)
be a pair of orthogonal (perpendicular) unit vectors. Find the
matrix [ρα]e.
Explain your answer.
(b) Let V be the space of polynomials of
degree ≤ 3 over the field F.
Let D : f ↦ f ' (where f '
is the derivative of f).
D is a linear transformation of V.
Determine the matrix [D]e,
where e = (1, x, x2, x3)
is the standard basis of V.
(c) Compute the 4th power of this matrix. Explain
what you found. (5+5+2 points)
16.7 DO (prescribing a linear map on a basis):
Let V, W be vector spaces over the field F.
Let e=(e1 , ... , ek)
be a basis of V. Prove:
(∀ w1 ,..., wk ∈ W)
(∃! a linear map φ : V → W)(∀ i
∈ [k])
(φ(ei) = wi).
(The symbol "(∃! φ)" reads "there exists a unique φ
such that ...")
16.8 HW (Fibonacci shift): (a) Consider the space
V consisting of all infinite sequences
a = (a0, a1, ...)
of real numbers. Let σ denote the left
shift operator: σ(a) =
(a1, a2, ...).
Show that the eigenvectors of σ
are precisely the geometric progressions.
What are the eigenvalues of σ ?
(b) Let W be the subspace if V
consisting of the sequences that satisfy the Fibonacci recurrence
an = an-1 + an-2
(n ≥ 2). Show that the dimension of this
"Fibonacci space" is 2; find a basis consisting of
a sequence beginning with (0, 1, ...) and
a sequence beginning with (1, 0, ...).
(c) Consider the shift operator on W.
This is a linear trasformation of W.
Find the 2 × 2 matrix B corresponding to
this transformation with respect to the basis found in (b).
(d) Determine the eigenvalues of the shift
operator on the Fibonacci space.
(e) Find an eigenbasis of the shift operator
on the Fibonacci space. Each sequence should
start with 1.
(f) Represent the Fibonacci sequece
as a linear combination of the eigenbasis.
Infer the explicit formula for Fibonacci numbers.
(4+4+4+4+4+4 points)
16.9 DO: Let φ : V → W be a linear map. Let
e=(e1 , ... , ek)
be a basis in V and
f=(f1 , ... , fm)
be a basis in W. Prove: for all v ∈ V
we have [φ(v)]f =
[φ]e,f[v]e.
16.10 DO: Let A,B be m × k matrices. Prove:
(a) The conditions x ∈ Fk, x ≠ 0,
and Ax = Bx do not imply A = B.
(b) If (∀ x ∈ Fk )(Ax = Bx)
then A = B.
16.11 DO (change of basis: change of coordinates):
Let e=(e1 , ... , ek)
and e'=(e1' , ... , ek')
be two bases of V (the "old" basis and the "new" basis).
We define the basis change transformation
σ : V → V by setting σ(ei) =
ei'. Let S = [σ]e
(the "basis change matrix"). (a) Prove that S is invertible.
(b) Prove: (∀ v ∈ V)([v]e' =
S -1 [v]e).
16.12 DO (change of bases: change of matrix): Let
φ : V → W. Let e, e' be two bases
of V and f, f' be two bases of W.
Let S be the basis change matrix corresponding to the
basis change e ↦ e' in V and let T
be the basis change matrix corresponding to the basis change
f ↦ f' in W. Let A be the matrix
of φ in the "old bases"
(i.e., A = [φ]e,f) and
A' the matrix of φ in the "new bases"
(i.e., A = [φ]e',f'). Prove:
A' = T-1AS. Hint.
Use Exx. 16.10 and 16.11. Start by writing φ(v) = w.
Translating this to matrix form you get matrix equations of the form
Ax = y (in the old bases) and A'x' = y' (in the new bases)
(explain the meaning of x, x', y, y'). Now
x' = S-1x and y' = T-1y
(by Ex. 16.11).
Therefore
A'S -1x = T-1y,
so TA'S-1x = y = Ax. Now use
Ex. 16.10.
16.14 DO (similar matrices): Recall: the n × n
matrices A and B are similar if
(∃ nonsingular matrix S)(B = S-1AS).
Let us fix a basis e in the n-dimensional space V.
Prove: A and B are similar if and only if there exists
a basis e' of V and a transformation
φ : V → V such that
[φ]e = A and
[φ]e' = B.
16.15 DO: (muliplicativity of determinants) Prove:
det(AB) = det(A)det(B). Hint.
(a) Prove the result when A is a diagonal matrix.
(b) Prove the result when one of the rows of A is all zero.
(c) Perform elementary row operations on A and the same
row operations on AB simultaneously until we reach either
situation (a) or situation (b).
15.1 DO: Prove: if the vector spaces Fn and
Fm are isomorphic then n = m.
(F is a field.)
15.2 DO: Let A be a k × n matrix and
B be an n × k matrix over the field F.
Prove: Tr(AB) = Tr(BA). Here "Tr" denotes the
trace of a square matrix (sum of the diagonal elements).
What are the dimensions of AB and of BA?
15.3 DO: Recall that the matrices A, B ∈ Mn(F)
are similar if there exists a nonsingular matrix
S ∈ Mn(F) such that
B = S -1AS.
Assume A and B are similar.
Prove: (a) det(B) = det(A);
(b) fB(t) = fA(t)
(where fA(t) = det(tI - A) is the
characteristic polynomial); (c) for every eigenvalue
λ, the (c1) geometric (c2) algebraic multiplicity
of λ is the same for A as for B.
(Recall that the algebraic multiplicity of the eigenvalue
λ of the matrix A ∈ Mn(F) is
its multiplicity in the characteristic polynomial of A.
The geometric multiplicity is the nullity of the
matrix λI - A.)
15.4 DO: Let A ∈ Mn(F) and let fA(t)
be its characteristic polynomial. Let
fA(t) =
a0 + a1x + ... + anxn.
Prove:
15.5 HW: Let λ1, ... , λn
be the eigenvalues of A ∈ Mn(F)
with the right (algebraic) multiplicities. Prove:
(a) Tr(A) = ∑ λi ;
(b) det(A) = ∏ λi .
You may use 15.4 without proof. (The sum and the
product are for i = 1,...,n. The λi
belong to the algebraic closure of F.)
(5+5 points)
15.6 DO: Prove: for every eigenvalue λ of A,
the geometric multiplicity of λ
is not greater than its algebraic multiplicity.
15.7 DO: Let A ∈ Mn(F) be an upper triangular matrix
(all elements under the diagonal are zero). Prove that the eignevalues
of A are precisely the diagonal elements, with the right
algebraic multiplicity.
15.8 DO: A diagonal matrix is a square matrix with zeros everywhere
outside the diagonal (diagonal entries may or may not be zero).
For instance the zero matrix and the indentity matrix are diagonal
matrices. A matrix A ∈ Mn(F) is
diagonalizable if it is similar to a diagonal matrix.
Prove: A is diagonalizable if and only if there exists
an eigenbasis for A. (An eigenbasis for
A is a basis of Fn which consists
of eigenvectors of A.)
15.9 HW: Diagonalize Jn ,
the n × n all-ones matrix, i.e.,
find a diagonal matrix similar to Jn.
Prove. (6 points)
15.10 DO: Prove: the matrix A ∈ Mn(F)
is diagonalizable if and only if the sum of the geometric
multiplicities of its eigenvalues is n.
15.11 HW: Show a 2 × 2 matrix over C
that is not diagonalizable. Prove.
State the eigenvalues of your matrix
along with their algebraic and geometric multiplicities.
Prove. (Hint: make your matrix triangular. This will lead
to very short proofs.) (10 points)
14.1 HW: Let Jn denote the n × n
"all ones" matrix (every entry is equal to 1). (a) Compute the characteristic
polynomial of this matrix. Your answer should be a simple closed-form
expression. (b) Determine the roots of the characteristic polynomial
over R along with their multiplicities. (c) Find an
eigenbasis for Jn, i.e., find a basis of
Rn which consists of right eigenvectors of
Jn. (10+5+8 points)
14.2 HW: Let a1,...,an be
distinct elements of the field F. Let
f(x) = (x - a1)...(x - an).
For i = 1,...,n, let
gi(x) = f(x)/(x - ai).
Prove: the polynomials
g1, ... ,gn
are linearly independent over F.
Clearly state what it is that you need to show. Your proof should
be elegant, no more than five lines.
(10 points)
14.3 HW: (a) Study Gaussian elimination. (b)
Let B = (bij) denote the
n × n matrix with entries bij = i+j.
Determine the rank of B over R.
(0+8 points)
14.4 HW: A (0,1)-matrix is a matrix whose entries are zeros
and ones. Construct a 3 × 3 (0,1)-matrix whose columns are
linearly independent over R but linearly dependent over
F2. Prove your answers.
(8 points)
14.5 DO (due Tuesday, Dec 1, before the tutorial): (a) Let A be
an n × n matrix over the field F. Let
v1, ... ,vk be right eigenvectors
of A corresponding to k distinct eigenvalues.
Prove that v1, ... ,vk are
linearly independent. (b) Find an n × n matrix
over the field F wich has an eigenbasis corresponding to just
one eigenvalue (i.e., all the n vectors in the eigenbasis
correspond to the same eigenvalue). (c) Find a 2 × 2
matrix over Z which does not have an eigenbasis over C.
14.6 DO (due Tuesday, Dec 1, before the tutorial): Prove the
second miracle: for every matrix (any shape, over any field),
the row-rank and the column-rank are equal. (Hint: Gaussian
elimination.)
14.7 DO (due Tuesday, Dec 1, before the tutorial): Let
A and B be k × n matrices
over the field F. Prove:
rank( A + B) ≤ rank( A) + rank( B).
14.8 DO (due Tuesday, Dec 1, before the tutorial):
Let F be a field. Prove: (a) if F has characteristic zero
then F contains a subfield isomorphic to Q;
(b) if F has characteristic p
then F contains a subfield isomorphic to
Fp, the field of residue classes mod p.
14.9 CHALLENGE PROBLEM.
Let a0,...,an-1 ∈ C.
The circulant C = C(a0,...,an-1)
is defined as the n × n matrix C = (cij)
where cij = a (i-j) mod n. Find the
eigenvalues of C as simple expressions involving the
ai. - Hint: find a common eigenbasis for all
n × n circulants.
14.10 (irreducibility over Q). (a) REWARD PROBLEM:
Use the Gauss Lemma (about primitive
polynomials) to prove that if an integral polynomial can be
factored nontrivially over the rationals (i.e., into factors of
lower degrees) then it can be factored nontrivially over the integers.
(b) CHALLENGE PROBLEM: Let a1,...,an be
distinct integers. Let
f(x) = (x - a1)...(x - an) - 1.
Prove that f is irreducble over Q.
(c) REWARD PROBLEM: Prove the
Schönemann - Eisenstein irreducibility criterion:
Let
f(x)=a0 + a1x + ... + anxn
be a polynomial over the integers. Let p be a prime number.
Suppose p divides ai for i = 0,...,n-1
but p does not divide an; and further
p2 does not divide a0.
Prove that f is irreducible over the rationals.
(d) DO (based on (c)):
Prove that xn - p is irreducible
over Q for every n ≥ 1 and for every prime p.
(e) CHALLENGE PROBLEM: Prove that xn - 4 is irreducible
over Q for every odd n.
(f) CHALLENGE PROBLEM:
Use the Schönemann - Eisenstein irreducibility criterion
(plus a simple trick) to prove that for every prime p,
the polynomial
1 + x + x2 + ... + xp-1
is irreducible over Q.
13.1 HW: Let A be an n × n complex matrix
and let G = ([n], E) be the associated digraph ( i → j
exactly if aij ≠ 0).
Suppose G is strongly connected and has period d. Prove:
if λ is an eigenvalue of A and ω is a complex
d-th root of unity (i.e., ωd = 1) then
λω is also an eigenvalue. (8 points)
13.2 HW: Prove: if R is a finite integral domain then
R is a field. Recall that an integral domain is a commutative
ring with an identity element that is distinct from zero (so R
has at least two elements) and with no zero-divisors, i.e., if
ab = 0 then a = 0 or b = 0. The only thing
you need to verify is that under the conditions stated, every
nonzero element of R has a (multiplicative) inverse.
(8 points)
Homework set #16 (due Friday, Dec 4, before class)
[for Wednesday, do homework set #15 below!]
R0 = S0 ;
R1 = S0 - S1 ;
R2 = S0 - S1 + S2 ; etc.
Prove: if i is even then P(B) ≤ Ri; and if
i is odd then P(B) ≥ Ri. (12 points)
If W = V then we call φ a
linear transformation of V and use the
notation [φ]e =
[φ]e,e .
(b) Prove that the correspondence
φ ↦ [φ]e,f
described in 16.5 is a bijection between the
V → W linear maps and the m × k
matrices over F.
Homework set #15 (due Wednesday, Dec 2, before class)
(a) an = 1
(b) an - 1 = - Tr(A)
(c) a0 = (-1)n det(A).
Homework set #14 (due Monday, Nov 30, before class; DO exercises due
Tuesday, Dec 1, before the tutorial)
Homework set #13 (due Wednesday, Nov 25, before class; the problems
have been announced in class)
Homework set #12 (due Friday, Nov 20, before class, except where
indicated otherwise). Note that 12.7 requires you to read a
chapter from MN, so even though that problem is only due
Monday, Nov 23, take an early start on it.
12.1 HW (a Ramsey bound): (a) Define the Erdős - Rado arrow
symbol n → (r,s,t). (b) Prove:
17 → (3,3,3). (3+8 points)
(c) CHALLENGE PROBLEM: Prove that (b) is tight, i.e.,
16 ↛ (3,3,3) (16 does not arrow (3,3,3).
Hint: GF(16).
12.2 HW (convergence of a finite Markov Chain): LN 8.1.8. (Prove the convergence of the powers of a certain 2 × 2 stochastic matrix.) State the limit matrix. -- Your proof should be short. Elegance counts. (8 points)
12.3 HW: LN 8.1.17. (Prove that the powers of certain 2 × 2 stochastic matrix do not converge; find a stationary distribution.) (2 + 4 points)
12.4 HW: LN 8.1.24 (if a nonnegative matrix with strongly connected associated digraph has a nonnegative eigenvector then that eigenvector is positive). (A matrix is "nonnegative" if all entries are nonnegative. A matrix is "positive" if all entries are positive. The same definitions apply to vectors [which are 1 × n matrices].) (10 points)
12.5 HW (due Monday, Nov 23): Solve problem 2(e) of the Third Quiz. (Go to the Course home page, then click "Grading, tests" on the banner, then click "third quiz.") The problem asks you to prove a Chernoff-style inequality for the number of occurrences of the substring ABA in a random string over the alphabet {A,B}. State explicitly the values of the constants c,d. -- Your solution should be short and elegant. If you cannot describe the essence of the solution in three lines, you are on the wrong track. (12 points)
12.6 HW (due Monday, Nov 23): Prove: for almost all graphs G we have χ(G) > (α(G))100. (χ denotes the chromatic number, α the independence number. -- The entire solution should take no more than 6 lines.) (8 points)
12.7 HW (due Monday, Nov 23): (a) A graph is planar if it can be drawn in the plane so that the edges don't cross. Study planar graphs from MN (MN2 Chapter 6; MN1, Chapter 5) (MNi: i-th edition of MN). Learn Kuratowski's Theorem and Euler's formula. (b) Understand MN2, Proposition 6.3.3 (MN1, Prop. 5.3.3) - that a planar graph with n ≥ 3 vertices has m ≤ 3n-6 edges. (c) Use (b) to prove that every planar graph has a vertex of degree ≤ 5. (d) Use (c) to prove the "six-color theorem:" every planar graph is 6-colorable. Your proof should be a very short induction. (0 + 0 + 3 + 8 points)
12.8 DO (due Monday, Nov 23): Prove that for all sufficiently large n, the probability that a random graph is planar is less than 2-0.49n2.
12.9 CHALLENGE PROBLEM. Let S3(n) denote the number of those subsets of an n-set whose size is divisible by 3. Prove: |S3(n) - 2n/3| < 1.
11.1 HW: LN 6.2.27 (in a digraph, vertices in the same strong component have the same period) (8 points)
11.2 HW: Prove: if C is a strong component of a
digraph G then the period of any vertex in
C is equal to the gcd of the lengths of all
cycles contained in C. (Note: a cycle has
no repeated vertices.)
(8 points)
Note: 11.1 follows from 11.2. A full
solution to 11.2 also earns you full credit for 11.1
(but no extra credit, if you had a separate solution
to 11.1). A partial solution to 11.2 may earn you
zero credit for 11.1. On the other hand, it is
possible to solve 11.2 using 11.1. Naturally,
such a solution will earn you full credit for 11.2
but no credit for 11.1 (unless you separately solve 11.1).
11.3 DO: A digraph G=(V,E) is Eulerian if
(∀ x ∈ V)(
deg+ (x) = deg- (x))
(the out-degree of x is the same as the in-degree
of x). A digraph is weakly connected
if by ignoring orientation we get a connected graph.
Prove: if G is an Eulerian digraph and
G is weakly connected then G is
strongly connected.
Here is the link to homework sets 1-10.