Putnam 2010, Problem B-6

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, \ldots, n+1 \), then \( A^k = A^{[k]} \) for all \( k \geq 1 \).


Solution:
For any polynomial $p(x)$, let $[p(x)]A$ denote the $n \times n$ matrix obtained by replacing each entry $A_{ij}$ of $A$ by $p(A_{ij})$; thus $A^{[k]} = [x^k]A$. Let $P(x) = x^n + a_{n-1}x^{n-1} + \cdots + a_0$ denote the characteristic polynomial of $A$. By the Cayley-Hamilton theorem,
$$0 = A \cdot P(A)$$
$$= A^{n+1} + a_{n-1}A^n + \cdots + a_0 A$$
$$= A^{[n+1]} + a_{n-1}A^{[n]} + \cdots + a_0 A^{[1]}$$
$$= [xp(x)]A.$$

Thus each entry of $A$ is a root of the polynomial $xp(x)$. Now suppose $m \geq n+1$. Then
$$0 = [x^{m+1-n}P(x)]A$$
$$= A^{[m+1]} + a_{n-1}A^{[m]} + \cdots + a_0 A^{[m+1-n]}$$
since each entry of $A$ is a root of $x^{m+1-n}P(x)$. On the other hand,
$$0 = A^{m+1-n} \cdot P(A)$$
$$= A^{m+1} + a_{n-1}A^m + \cdots + a_0 A^{m+1-n}.$$

Therefore if $A^k = A^{[k]}$ for $m+1-n \leq k \leq m$, then $A^{m+1} = A^{[m+1]}$. The desired result follows by induction on $m$.

**Remark.** David Feldman points out that the result is best possible in the following sense: there exist examples of $n \times n$ matrices $A$ for which $A^k = A^{[k]}$ for $k = 1, \ldots, n$ but $A^{n+1} \neq A^{[n+1]}$.