Putnam preparation (Table of contents)

Linear Algebra

Problem 1

Find an example of a square matrix \(A\) with real entries such that \(A^2=0\) but \(AA^T\neq 0\).

Problem 2

Assume that \(A\) is an \(n\times n\) matrix with real entries \(a_{ij}\) for \(i,j\in\{1,2,\dots n\}\) such that \(a_{ij}=0\) if \(i\geq j\). Prove that \(A^n=0\).

Problem 3

Assume that \(A\) and \(B\) are two quadratic matrices such that \(AB=BA\). Prove that if \(x\) is an eigenvector for \(A\), then \(Bx\) is an eigenvector for \(A\) as well.

Problem 4

Solve the system of recursive equations: \begin{eqnarray*} a_{n+1}&=& 2a_n+2b_n\\ b_{n+1}&=& 3a_n + c_n\\ c_{n+1}&=& -3a_n+c_n, \end{eqnarray*} with the initial conditions \(a_0=2\), \(b_0=-1\), \(c_0=1\).

Problem 5

Let \(A\) and \(B\) be linear transformations on a finite dimensional vector space \(V\). Prove that \(\dim \ker (AB)\leq \dim\ker (A)+\dim\ker (B)\).

\(\ker (A)\) denotes the kernel of \(A\), i.e. \(\ker (A)=\{v: A(v)=0\}\), and \(\dim V\) denotes the dimension of the vector space \(V\).

Problem 6

Given an \(n\times n\) matrix \(M\) with complex entries, let us denote by \(M^*\) its conjugate transpose defined as \(M^*=\overline{M}^T\). The matrix \(M\) is called normal if \(AA^*=A^*A\). A matrix \(U\) is called unitary if \(U^*=U^{-1}\).

  • (a) Prove that if \(M\) is any complex matrix, then there exists a unitary matrix \(U\) and an upper-triangular matrix \(D\) such that \(M=UDU^*\).

  • (b) Prove that if \(M\) is a normal matrix, then \(D\) from part (a) is diagonal.

Problem 7

Does there exist an \(n\times n\) real matrix \(A\) such that \(\mbox{tr }(A)=0\) and \(A^2+A^T=I\)? (\(\mbox{tr }(A)\) is the trace of the matrix \(A\), and \(A^T\) is its transpose).

Problem 8

Let \(\delta > 0\) be given. Assume that \((A_n)_{n=1}^{\infty}\) is a sequence of subsets of a unit cube such that the volume of each \(A_n\) is greater than or equal to \(\delta\). Prove that for each \(\varepsilon > 0\) there are integers \(i\) and \(j\) such that the volume of \(A_i\cap A_j\) is at least \(\delta^2-\varepsilon\).