Linear Algebra

  1. You’re sitting at a computer terminal into which a function \(f\) has been programmed. You know that \(f\) is a degree-\(n\) polynomial, but you don’t know the explicit formula for \(f.\) Using the computer though, you can evaluate \(f\) at any input value you’d like. How can you figure out an explicit formula for \(f?\)

  2. MIT

    If \(A\) and \(B\) are square matrices of the same size such that \(ABAB = 0,\) does it follow that \(BABA = 0?\)

  3. MIT

    Let \(A\) be a \(2n \times 2n\) skew-symmetric matrix with integer entries. Prove that the determinant of \(A\) is a perfect square. (Hint: prove a polynomial identity.)

  4. MIT

    Calculate the determinant of the \(n \times n\) matrix \(A\) with entries \[ a_{ij} = \cos\biggl(2\pi\frac{i+j}{n}\biggr). \]

  5. MIT

    Determine the unique sequence of real numbers \(a_0, a_1,\dotsc\) such that \(\forall n\! \geq\! 0,\) \[ \operatorname{det}\begin{pmatrix} a_0 & a_1 & \cdots & a_n \\ a_1 & a_2 & \cdots & a_{n+1} \\ \vdots & \vdots & \ddots & \vdots \\ a_n & a_{n+1} & \cdots & a_{2n} \end{pmatrix} = \operatorname{det}\begin{pmatrix} a_1 & a_2 & \cdots & a_n \\ a_2 & a_3 & \cdots & a_{n+1} \\ \vdots & \vdots & \ddots & \vdots \\ a_n & a_{n+1} & \cdots & a_{2n-1} \end{pmatrix} = 1 \]

  6. Putnam & Beyond

    For integers \(a\) and \(b\) such that \(a + b = 2014,\) prove that \(61\) divides \[ \operatorname{det}\begin{pmatrix} a^3 & b^3 & 3ab & -1 \\ -1 & a^2 & b^2 & 2ab \\ 2b & -1 & a^2 & -b^2 \\ 0 & b & -1 & a \end{pmatrix} \]

  7. Putnam 2014 A2

    Let \(A\) be the \(n \times n\) matrix whose entry in the \(i\)-th row and \(j\)-th column is \( \frac{1}{\min(i,j)} \) for \(1 \leq i,j \leq n.\) Compute \(\det(A)\).

  8. Putnam 2010 B6

    Let \(A\) be an \(n \times n\) matrix of real numbers for some \(n \geq 1\). For each positive integer \(k\), let \(A^{[k]}\) be the matrix obtained by raising each entry to the \(k\)th power. Show that if \(A^k = A^{[k]}\) for \(k=1,2,\dots,n+1\), then \(A^k = A^{[k]}\) for all \(k \geq 1\).

  9. Putnam 2008 A2

    Alan and Barbara play a game in which they take turns filling entries of an initially empty \(2008 \times 2008\) array. Alan plays first. At each turn, a player chooses a real number and places it in a vacant entry. The game ends when all the entries are filled. Alan wins if the determinant of the resulting matrix is nonzero; Barbara wins if it is zero. Which player has a winning strategy?

  10. Putnam 1986 B6

    Suppose \(A,B,C,D\) are \(n \times n\) matrices with entries in a field \(F\), satisfying the conditions that \(AB^\mathrm{T}\) and \(CD^\mathrm{T}\) are symmetric and \(AD^\mathrm{T} - BC^\mathrm{T} = I\). Here \(I\) is the \(n \times n\) identity matrix, and if \(M\) is an \(n \times n\) matrix, \(M^\mathrm{T}\) is its transpose. Prove that \(A^\mathrm{T}D - C^\mathrm{T}B = I\).

  11. Putnam 2014 A6

    Let \(n\) be a positive integer. What is the largest \(k\) for which there exist \(n \times n\) matrices \(M_1, \dots, M_k\) and \(N_1, \dots, N_k\) with real entries such that for all \(i\) and \(j\), the matrix product \(M_i N_j\) has a zero entry somewhere on its diagonal if and only if \(i \neq j\)?

  12. Putnam 1992 B5

    Let \(D_n\) denote the value of the \((n-1) \times (n-1)\) determinant \[ \left[ \begin{array}{cccccc} 3 & 1 & 1 & 1 & \cdots & 1 \\ 1 & 4 & 1 & 1 & \cdots & 1 \\ 1 & 1 & 5 & 1 & \cdots & 1 \\ 1 & 1 & 1 & 6 & \cdots & 1 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & 1 & 1 & 1 & \cdots & n+1 \end{array} \right]. \] Is the set \(\left\{ \frac{D_n}{n!} \right\}_{n \geq 2}\) bounded?

  13. Putnam 1992 B6

    Let \(\mathcal{M}\) be a set of real \(n \times n\) matrices such that

    1. \(I \in \mathcal{M}\), where \(I\) is the \(n \times n\) identity matrix;
    2. if \(A \in \mathcal{M}\) and \(B \in \mathcal{M}\), then either \(AB \in \mathcal{M}\) or \(-AB \in \mathcal{M}\), but not both;
    3. if \(A \in \mathcal{M}\) and \(B \in \mathcal{M}\), then either \(AB = BA\) or \(AB = -BA\);
    4. if \(A \in \mathcal{M}\) and \(A \neq I\), there is at least one \(B \in \mathcal{M}\) such that \(AB = - BA\).

    Prove that \(\mathcal{M}\) contains at most \(n^2\) matrices.

  14. Putnam 1986 A4

    A transversal of an \(n\times n\) matrix \(A\) consists of \(n\) entries of \(A\), no two in the same row or column. Let \(f(n)\) be the number of \(n \times n\) matrices \(A\) satisfying the following two conditions:
    1. Each entry \(\alpha_{i,j}\) of \(A\) is in the set \(\{-1,0,1\}\).
    2. The sum of the \(n\) entries of a transversal is the same for all transversals of \(A\).
    An example of such a matrix \(A\) is \[ A = \left( \begin{array}{ccc} -1 & 0 & -1 \\ 0 & 1 & 0 \\ 0 & 1 & 0 \end{array} \right). \] Determine with proof a formula for \(f(n)\) of the form \[ f(n) = a_1 b_1^n + a_2 b_2^n + a_3 b_3^n + a_4, \] where the \(a_i\)’s and \(b_i\)’s are rational numbers.

  15. Putnam 2015 B3

    Let \(S\) be the set of all \(2 \times 2\) real matrices \[ M = \begin{pmatrix} a & b \\ c & d \end{pmatrix} \] whose entries \(a,b,c,d\) (in that order) form an arithmetic progression. Find all matrices \(M\) in \(S\) for which there is some integer \(k\!\gt\!1\) such that \(M^k\) is also in \(S.\)

  16. Putnam 2015 A6

    Let \(n\) be a positive integer. Suppose that \(A\), \(B\), and \(M\) are \(n\times n\) matrices with real entries such that \(AM = MB\), and such that \(A\) and \(B\) have the same characteristic polynomial. Prove that \(\det(A-MX) = \det(B-XM)\) for every \(n\times n\) matrix \(X\) with real entries.

  17. Putnam 1984 B6

    Let \(G\) be a finite set of real \(n\times n\) matrices \(\{M_i\},\) \(1 \leq i \leq r\), which form a group under matrix multiplication. Suppose that \(\sum_{i=1}^r \mathrm{tr}(M_i)=0\), where \(\mathrm{tr}(A)\) denotes the trace of the matrix \(A\). Prove that \(\sum_{i=1}^r M_i\) is the \(n \times n\) zero matrix.