More Problems

Problem of the month (probability): Let m < n be postiive integers. Calculate a good lower bound for the probability p(m,n) that a collection of m random n-bit binary vectors is linearly independent (over the rational numbers Q).

For example, when n = 2 and m = 2, there are (4 choose 2) = 6 collections of such vectors: {(0,0),(0,1)}, {(0,0),(1,0)}, {(0,0),(1,1)}, {(0,1),(1,0)}, {(0,1),(1,1)}, {(1,0),(1,1)}. Of these, only 1/2 of them are linearly independent, so p(2,2) = 1/2.

Problem of the month (sums of squares):

Every positive integer is the sum of 4 squares of integers (Lagrange). Prove that there are univariate integer polynomials f in Z[x] which can be written as a sum of 5 squares in Z[x], but not of 4.

Problem of the month (abelian groups):

Let p be a prime number and set A = Z/pZ x Z/p²Z to be the abelian group which is the product of cyclic groups Z/pZ and Z/p²Z.

Construct explicitly the group of automorphisms of A. Is it commutative? Find the order of this group.

Problem of the month (matrices, determinants):

Let A be an n-by-n matrix with integer entries such that each column is a permutation of the first column of A.
Prove that the sum of the entries of this column divides the determinant of A. For instance, if A is the matrix

6 5 9
5 9 5
9 6 6

then, one checks that det(A) = -240 which is divisible by 6 + 5 + 9 = 20.

Problem of the month (Graph Theory):


Characterize those simple graphs G with the following two properties: between each
pair of vertices u and v in G we have that (1) there exist a pair of vetex-disjoint
paths, and (2) any set of vertex-disjoint paths betweeen u and v has at
most two elements.

(Note: simple means no loops and at most one edge joining any pair of distinct
vertices in the graph. Also, P₁,...,P_n are vetex-disjoint paths between u and v if they
are paths from u to v and if no two of them share a vertex except for u,v).

Problem of the month (matrix theory):

Let A and B be positive semidefinite matrices (symmetric matrices with all nonnegative eigenvalues).
Show that if trace(AB) = 0, then in fact AB = 0.

Problem of the month (elementary group theory):

Find two groups A and B such that there is a surjective
homomorphism from each one to the other, but there
is no isomorphism between them.

Problem of the month (plane geometry):

Take a triangle ABC and a point P strictly inside it.
Draw the lines AP, BP, and CP passing from vertices through P.
These lines intersect the triangle ABC at points A', B',
and C', respectively.

(a) Prove that the area of triangle A'B'C' is less than 1/2 that of ABC.

(b) Can you do better than 1/2?

[Note: (b) was solved by Corey Irving]

Problem of the month (convex linear recurrences):

Let r(1),...,r(k) be nonnegative real numbers summing to 1
and let a(1),...,a(k) be arbitrary complex numbers. For n > k,
define

a(n) = r(1)a(n-1) + .... + r(k)a(n-k).

Furthermore, suppose that there exists a consecutive
pair r(i) and r(i+1) with nonzero product.

(a) Prove that the limit of a(n) as n goes to infinity exists.

(b) If k = 2 and r(1) = r(2) = 1/2, what is the limit in terms of
a(1) and a(2)?

(c) Can you determine this limit in general?

(d) Are the supplimental hypotheses necessary for this
limit to exist?

Problem of the month (minimal cardinality group generators):

Let G be a finite group of size |G|.

(a) Prove that the smallest number of elements of G
necessary to generate it is less than or equal to log |G|.
(Hint: Assume S is a set of k generators and consider
the chain of subgroups that they induce).

(b) Is the bound in (a) tight?