Linear Algebra Talk
Linear Algebra Talk
Linear Algebra Talk
Matthew Rognlie
Department of Mathematics
Duke University
November 4, 2009
Preliminaries Facts Example
Cautionary Note
I will assume that you all have enough background in linear algebra to
understand the terminology and basic ideas here—rehashing them all
would take far too long, and it is not the purpose of this class. If you’re
having trouble, please:
Cautionary Note
I will assume that you all have enough background in linear algebra to
understand the terminology and basic ideas here—rehashing them all
would take far too long, and it is not the purpose of this class. If you’re
having trouble, please:
The goal of this (short) lecture will be to discuss a few useful ideas,
facts, and examples that you might not have seen in linear algebra class.
Preliminaries Facts Example
Determinants
I assume you know how to calculate determinants; if not, look it up.
Some basic, useful facts include:
Preliminaries Facts Example
Determinants
I assume you know how to calculate determinants; if not, look it up.
Some basic, useful facts include:
Determinants
I assume you know how to calculate determinants; if not, look it up.
Some basic, useful facts include:
Determinants
I assume you know how to calculate determinants; if not, look it up.
Some basic, useful facts include:
Determinants
I assume you know how to calculate determinants; if not, look it up.
Some basic, useful facts include:
Determinants
I assume you know how to calculate determinants; if not, look it up.
Some basic, useful facts include:
Determinants
I assume you know how to calculate determinants; if not, look it up.
Some basic, useful facts include:
Determinants
I assume you know how to calculate determinants; if not, look it up.
Some basic, useful facts include:
Cayley-Hamilton Example
Problem
Let A and B be 2-by-2 matrices, each with determinant 1. Prove that:
B 2 − (tr(B))B + det(B) = 0
AB − (tr(B))A + AB −1 = 0
A Putnam Problem
Problem
Let Z denote the set of points in Rn whose coordinates are 0 or 1. (Thus
Z has 2n elements, which are the vertices of a unit hypercube in Rn .)
Given a vector subspace V of Rn , let Z (V ) denote the number of
members of Z that lie in V . Let k be given, 0 ≤ k ≤ n. Find the
maximum, over all vector subspaces V ⊆ Rn of dimension k, of the
number of points in Z (V ).
Preliminaries Facts Example
A Putnam Problem
Problem
Let Z denote the set of points in Rn whose coordinates are 0 or 1. (Thus
Z has 2n elements, which are the vertices of a unit hypercube in Rn .)
Given a vector subspace V of Rn , let Z (V ) denote the number of
members of Z that lie in V . Let k be given, 0 ≤ k ≤ n. Find the
maximum, over all vector subspaces V ⊆ Rn of dimension k, of the
number of points in Z (V ).
Any guesses?
Preliminaries Facts Example
A Putnam Problem
Problem
Let Z denote the set of points in Rn whose coordinates are 0 or 1. (Thus
Z has 2n elements, which are the vertices of a unit hypercube in Rn .)
Given a vector subspace V of Rn , let Z (V ) denote the number of
members of Z that lie in V . Let k be given, 0 ≤ k ≤ n. Find the
maximum, over all vector subspaces V ⊆ Rn of dimension k, of the
number of points in Z (V ).
Any guesses?
Intuitively, it seems clear that this should be 2k . Certainly in two or three
dimensions, it’s impossible to visualize a k-dimensional subspace that
intersects the unit square or cube in more than 2k places. But how do we
make this rigorous?
Preliminaries Facts Example
A Putnam Problem
Problem
Let Z denote the set of points in Rn whose coordinates are 0 or 1. (Thus
Z has 2n elements, which are the vertices of a unit hypercube in Rn .)
Given a vector subspace V of Rn , let Z (V ) denote the number of
members of Z that lie in V . Let k be given, 0 ≤ k ≤ n. Find the
maximum, over all vector subspaces V ⊆ Rn of dimension k, of the
number of points in Z (V ).
Any guesses?
Intuitively, it seems clear that this should be 2k . Certainly in two or three
dimensions, it’s impossible to visualize a k-dimensional subspace that
intersects the unit square or cube in more than 2k places. But how do we
make this rigorous?
Review: the dimension of a vector space equals the size of the largest set
of linearly independent elements you can find in the vector space.
Preliminaries Facts Example
An awesome solution
Solution
Let V be a k-dimensional subspace. Form the matrix whose rows are the
elements of V ∩ Z . By construction, it has row rank of at most k.
Therefore, it also has column rank of at most k; thus we can choose k
coordinates such that each point of Z ∩ V is determined by k of these
coordinates. Since each coordinate of a point in Z can only take two
values, V ∩ Z can have at most 2k elements. (proof from Catalin Zara)