Putnam Archive — Linear Algebra

Find the minimal value of $k$ such that there exist $k$-by-$k$ real matrices $A_1, \dots, A_{2025}$ with the property that $A_i A_j = A_j A_i$ if and only if $|i-j| \in \{0,1,2024\}$.

For $n \geq 2$, let $A = [a_{i,j}]_{i,j=1}^n$ be an $n$-by-$n$ matrix of nonnegative integers such that

1. (a)
   $a_{i,j} = 0$ when $i+j\leq n$;
2. (b)
   $a_{i+1,j} \in \{a_{i,j}, a_{i,j}+1\}$ when $1 \leq i \leq n-1$ and $1 \leq j \leq n$; and
3. (c)
   $a_{i,j+1} \in \{a_{i,j}, a_{i,j}+1\}$ when $1 \leq i \leq n$ and $1 \leq j \leq n-1$.

Let $S$ be the sum of the entries of $A$, and let $N$ be the number of nonzero entries of $A$. Prove that $$S \leq \frac{(n+2)N}{3}.$$

Let $c_0,c_1,c_2,\dots$ be the sequence defined so that $$\frac{1-3x-\sqrt{1-14x+9x^2}}{4} = \sum_{k=0}^\infty c_k x^k$$ for sufficiently small $x$. For a positive integer $n$, let $A$ be the $n$-by-$n$ matrix with $i,j$-entry $c_{i+j-1}$ for $i$ and $j$ in $\{1,\dots,n\}$. Find the determinant of $A$.

Let $v_1, \dots, v_{12}$ be unit vectors in $\mathbb{R}^3$ from the origin to the vertices of a regular icosahedron. Show that for every vector $v \in \mathbb{R}^3$ and every $\varepsilon > 0$, there exist integers $a_1,\dots,a_{12}$ such that $\| a_1 v_1 + \cdots + a_{12} v_{12} - v \| < \varepsilon$.

Let $n$ be a positive integer. For $i$ and $j$ in $\{1,2,\dots,n\}$, let $s(i,j)$ be the number of pairs $(a,b)$ of nonnegative integers satisfying $ai +bj=n$. Let $S$ be the $n$-by-$n$ matrix whose $(i,j)$ entry is $s(i,j)$. For example, when $n=5$, we have $S = \begin{bmatrix} 6 & 3 & 2 & 2 & 2 \\ 3 & 0 & 1 & 0 & 1 \\ 2 & 1 & 0 & 0 & 1 \\ 2 & 0 & 0 & 0 & 1 \\ 2 & 1 & 1 & 1 & 2 \end{bmatrix}$. Compute the determinant of $S$.

Say that an $n$-by-$n$ matrix $A = (a_{ij})_{1 \leq i,j \leq n}$ with integer entries is very odd if, for every nonempty subset $S$ of $\{1,2,\dots,n\}$, the $|S|$-by-$|S|$ submatrix $(a_{ij})_{i,j \in S}$ has odd determinant. Prove that if $A$ is very odd, then $A^k$ is very odd for every $k \geq 1$.

Let $Q$ be an $n$-by-$n$ real orthogonal matrix, and let $u \in \mathbb{R}^n$ be a unit column vector (that is, $u^T u = 1$). Let $P = I - 2uu^T$, where $I$ is the $n$-by-$n$ identity matrix. Show that if $1$ is not an eigenvalue of $Q$, then $1$ is an eigenvalue of $PQ$.

Let $S_1, S_2, \dots, S_{2^n-1}$ be the nonempty subsets of $\{1,2,\dots,n\}$ in some order, and let $M$ be the $(2^n-1) \times (2^n-1)$ matrix whose $(i,j)$ entry is $$m_{ij} = \begin{cases} 0 & \mbox{if }S_i \cap S_j = \emptyset; \\ 1 & \mbox{otherwise.} \end{cases}$$ Calculate the determinant of $M$.

Let $A$ be a $2n \times 2n$ matrix, with entries chosen independently at random. Every entry is chosen to be 0 or 1, each with probability $1/2$. Find the expected value of $\det(A-A^t)$ (as a function of $n$), where $A^t$ is the transpose of $A$.

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.

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>1$ such that $M^k$ is also in $S$.

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)$.

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$?

Let $A$ be an $m \times n$ matrix with rational entries. Suppose that there are at least $m+n$ distinct prime numbers among the absolute values of the entries of $A$. Show that the rank of $A$ is at least 2.

For $m \geq 3$, a list of $\binom{m}{3}$ real numbers $a_{ijk}$ ($1 \leq i < < j < k \leq m$) is said to be area definite for $\mathbb{R}^n$ if the inequality $$\sum_{1 \leq i < j < k \leq m} a_{ijk} \cdot \mathrm{Area}(\Delta A_i A_j A_k) \geq 0$$ holds for every choice of $m$ points $A_1,\dots,A_m$ in $\mathbb{R}^n$. For example, the list of four numbers $a_{123} = a_{124} = a_{134} = 1$, $a_{234} = -1$ is area definite for $\mathbb{R}^2$. Prove that if a list of $\binom{m}{3}$ numbers is area definite for $\mathbb{R}^2$, then it is area definite for $\mathbb{R}^3$.

Define a function $w: \mathbb{Z} \times \mathbb{Z} \to \mathbb{Z}$ as follows. For $\left| a \right|, \left| b \right| \leq 2$, let $w(a,b)$ be as in the table shown; otherwise, let $w(a,b) = 0$.

For every finite subset $S$ of $\mathbb{Z} \times \mathbb{Z}$, define $$A(S) = \sum_{(\mathbf{s}, \mathbf{s}') \in S \times S} w(\mathbf{s} - \mathbf{s}').$$ Prove that if $S$ is any finite nonempty subset of $\mathbb{Z} \times \mathbb{Z}$, then $A(S) > 0$. (For example, if $S = \{(0,1), (0,2), (2,0), (3,1)\}$, then the terms in $A(S)$ are $12, 12, 12, 12, 4, 4, 0, 0, 0,0,-1,-1,-2,-2,-4,-4$.)

Let $\FF_p$ denote the field of integers modulo a prime $p$, and let $n$ be a positive integer. Let $v$ be a fixed vector in $\FF_p^n$, let $M$ be an $n \times n$ matrix with entries of $\FF_p$, and define $G: \FF_p^n \to \FF_p^n$ by $G(x) = v + Mx$. Let $G^{(k)}$ denote the $k$-fold composition of $G$ with itself, that is, $G^{(1)}(x) = G(x)$ and $G^{(k+1)}(x) = G(G^{(k)}(x))$. Determine all pairs $p, n$ for which there exist $v$ and $M$ such that the $p^n$ vectors $G^{(k)}(0)$, $k=1,2,\dots,p^n$ are distinct.

For which positive integers $n$ is there an $n \times n$ matrix with integer entries such that every dot product of a row with itself is even, while every dot product of two different rows is odd?

In a tournament, 2011 players meet 2011 times to play a multiplayer game. Every game is played by all 2011 players together and ends with each of the players either winning or losing. The standings are kept in two $2011 \times 2011$ matrices, $T = (T_{hk})$ and $W = (W_{hk})$. Initially, $T=W=0$. After every game, for every $(h,k)$ (including for $h=k$), if players $h$ and $k$ tied (that is, both won or both lost), the entry $T_{hk}$ is increased by 1, while if player $h$ won and player $k$ lost, the entry $W_{hk}$ is increased by 1 and $W_{kh}$ is decreased by 1.

Prove that at the end of the tournament, $\det(T+iW)$ is a non-negative integer divisible by $2^{2010}$.

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$.

Let $d_n$ be the determinant of the $n \times n$ matrix whose entries, from left to right and then from top to bottom, are $\cos 1, \cos 2, \dots, \cos n^2$. (For example, $$d_3 = \left| \begin{matrix} \cos 1 & \cos 2 & \cos 3 \\ \cos 4 & \cos 5 & \cos 6 \\ \cos 7 & \cos 8 & \cos 9 \end{matrix} \right|.$$ The argument of $\cos$ is always in radians, not degrees.) Evaluate $\lim_{n\to\infty} d_n$.

Say that a polynomial with real coefficients in two variables, $x,y$, is balanced if the average value of the polynomial on each circle centered at the origin is $0$. The balanced polynomials of degree at most $2009$ form a vector space $V$ over $\mathbb{R}$. Find the dimension of $V$.

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?

Let $Z$ denote the set of points in $\mathbb{R}^n$ whose coordinates are 0 or 1. (Thus $Z$ has $2^n$ elements, which are the vertices of a unit hypercube in $\mathbb{R}^n$.) Given a vector subspace $V$ of $\mathbb{R}^n$, let $Z(V)$ denote the number of members of $Z$ that lie in $V$. Let $k$ be given, $0 \leq k \leq n$. Find the maximum, over all vector subspaces $V \subseteq \mathbb{R}^n$ of dimension $k$, of the number of points in $V \cap Z$. [Editorial note: the proposers probably intended to write $Z(V)$ instead of “the number of points in $V \cap Z$”, but this changes nothing.]

Let $H$ be an $n \times n$ matrix all of whose entries are $\pm 1$ and whose rows are mutually orthogonal. Suppose $H$ has an $a \times b$ submatrix whose entries are all $1$. Show that $ab \leq n$.

Define a sequence $\{ u_n \}_{n=0}^\infty$ by $u_0 = u_1 = u_2 = 1$, and thereafter by the condition that $$\det\begin{pmatrix} u_n & u_{n+1}\\ u_{n+2} & u_{n+3} \end{pmatrix} = n!$$ for all $n \ge 0$. Show that $u_n$ is an integer for all $n$. (By convention, $0! = 1$.)

In Determinant Tic-Tac-Toe, Player 1 enters a 1 in an empty $3 \times 3$ matrix. Player 0 counters with a 0 in a vacant position, and play continues in turn until the $3 \times 3$ matrix is completed with five 1's and four 0's. Player 0 wins if the determinant is 0 and player 1 wins otherwise. Assuming both players pursue optimal strategies, who will win and how?

Let $p$ be a prime number. Prove that the determinant of the matrix $$\begin{pmatrix} x & y & z \\ x^p & y^p & z^p \\ x^{p^2} & y^{p^2} & z^{p^2} \end{pmatrix}$$ is congruent modulo $p$ to a product of polynomials of the form $ax+by+cz$, where $a,b,c$ are integers. (We say two integer polynomials are congruent modulo $p$ if corresponding coefficients are congruent modulo $p$.)

For an integer $n\geq 3$, let $\theta=2\pi/n$. Evaluate the determinant of the $n\times n$ matrix $I+A$, where $I$ is the $n\times n$ identity matrix and $A=(a_{jk})$ has entries $a_{jk}=\cos(j\theta+k\theta)$ for all $j,k$.

For any square matrix $A$, we can define $\sin A$ by the usual power series: $$\sin A = \sum_{n=0}^\infty \frac{(-1)^n}{(2n+1)!} A^{2n+1}.$$ Prove or disprove: there exists a $2 \times 2$ matrix $A$ with real entries such that $$\sin A = \left( \begin{array}{cc} 1 & 1996 \\ 0 & 1 \end{array} \right).$$

Let $x_{1},x_{2},\dots,x_{n}$ be differentiable (real-valued) functions of a single variable $t$ which satisfy

for some constants $a_{ij}>0$. Suppose that for all $i$, $x_{i}(t) \to 0$ as $t \to \infty$. Are the functions $x_{1},x_{2},\dots,x_{n}$ necessarily linearly dependent?

To each positive integer with $n^{2}$ decimal digits, we associate the determinant of the matrix obtained by writing the digits in order across the rows. For example, for $n=2$, to the integer 8617 we associate $\det \left( \begin{array}{cc} 8 & 6 \\ 1 & 7 \end{array} \right) = 50$. Find, as a function of $n$, the sum of all the determinants associated with $n^{2}$-digit integers. (Leading digits are assumed to be nonzero; for example, for $n=2$, there are 9000 determinants.)

Let $A$ and $B$ be $2 \times 2$ matrices with integer entries such that $A, A+B, A+2B, A+3B$, and $A+4B$ are all invertible matrices whose inverses have integer entries. Show that $A+5B$ is invertible and that its inverse has integer entries.

For $n \geq 1$, let $d_n$ be the greatest common divisor of the entries of $A^n - I$, where $$A = \begin{pmatrix} 3 & 2 \\ 4 & 3 \end{pmatrix} \quad \mbox{ and } \quad I = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}.$$ Show that $\lim_{n \to \infty} d_n = \infty$.

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?

Let $\MM$ be a set of real $n \times n$ matrices such that

• (i)
  $I \in \MM$, where $I$ is the $n \times n$ identity matrix;
• (ii)
  if $A \in \MM$ and $B \in \MM$, then either $AB \in \MM$ or $-AB \in \MM$, but not both;
• (iii)
  if $A \in \MM$ and $B \in \MM$, then either $AB = BA$ or $AB = -BA$;
• (iv)
  if $A \in \MM$ and $A \neq I$, there is at least one $B \in \MM$ such that $AB = - BA$.

Prove that $\MM$ contains at most $n^2$ matrices.

Let $\bA$ and $\bB$ be different $n \times n$ matrices with real entries. If $\bA^3 = \bB^3$ and $\bA^2 \bB = \bB^2 \bA$, can $\bA^2 + \bB^2$ be invertible?

If $\mathbf{A}$ and $\mathbf{B}$ are square matrices of the same size such that $\mathbf{ABAB = 0}$, does it follow that $\mathbf{BABA = 0}$?

Let $S$ be a set of $2 \times 2$ integer matrices whose entries $a_{ij}$ (1) are all squares of integers and, (2) satisfy $a_{ij} \leq 200$. Show that if $S$ has more than 50387 ($= 15^4 - 15^2 - 15 + 2$) elements, then it has two elements that commute.

If a linear transformation $A$ on an $n$-dimensional vector space has $n+1$ eigenvectors such that any $n$ of them are linearly independent, does it follow that $A$ is a scalar multiple of the identity? Prove your answer.

For positive integers $n$, let $M_n$ be the $2n+1$ by $2n+1$ skew-symmetric matrix for which each entry in the first $n$ subdiagonals below the main diagonal is 1 and each of the remaining entries below the main diagonal is -1. Find, with proof, the rank of $M_n$. (According to one definition, the rank of a matrix is the largest $k$ such that there is a $k \times k$ submatrix with nonzero determinant.)

One may note that

Let $O_n$ be the $n$-dimensional vector $(0,0,\cdots, 0)$. Let $M$ be a $2n \times n$ matrix of complex numbers such that whenever $(z_1, z_2, \dots, z_{2n})M = O_n$, with complex $z_i$, not all zero, then at least one of the $z_i$ is not real. Prove that for arbitrary real numbers $r_1, r_2, \dots, r_{2n}$, there are complex numbers $w_1, w_2, \dots, w_n$ such that $$\mathrm{re}\left[ M \left( \begin{array}{c} w_1 \\ \vdots \\ w_n \end{array} \right) \right] = \left( \begin{array}{c} r_1 \\ \vdots \\ r_n \end{array} \right).$$ (Note: if $C$ is a matrix of complex numbers, $\mathrm{re}(C)$ is the matrix whose entries are the real parts of the entries of $C$.)

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. (a)
   Each entry $\alpha_{i,j}$ of $A$ is in the set $\{-1,0,1\}$.
2. (b)
   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.

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

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.