Putnam 2015, Problem A-6

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.

Solution:
First solution: (by Noam Elkies) Using row and column operations, we may construct invertible matrices \(U, V\) such that \(U^{-1}MV\) is a block diagonal matrix of the form
\[
\begin{pmatrix} I & 0 \\ 0 & 0 \end{pmatrix}.
\]
Put \(A' = U^{-1}AU\), \(M' = U^{-1}MV\), \(B' = V^{-1}BV\), \(X' = V^{-1}XU\), so that \(A'M' = M'B'\), \(\det(A - MX) = \det(U^{-1}(A - MX)U) = \det(A' - M'X')\), and \(\det(B - XM) = \det(V^{-1}(B - XM)V) = \det(B' - X'M')\). Form the corresponding block decompositions
\[
A' = \begin{pmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{pmatrix}, \quad B' = \begin{pmatrix} B_{11} & B_{12} \\ B_{21} & B_{22} \end{pmatrix}, \quad X' = \begin{pmatrix} X_{11} & X_{12} \\ X_{21} & X_{22} \end{pmatrix}.
\]
We then have
\[
A'M' = \begin{pmatrix} A_{11} & 0 \\ A_{21} & 0 \end{pmatrix}, \quad M'B' = \begin{pmatrix} B_{11} & B_{12} \\ 0 & 0 \end{pmatrix},
\]
so we must have \(A_{11} = B_{11}\) and \(A_{21} = B_{12} = 0\); in particular, the characteristic polynomial of \(A\) is the product of the characteristic polynomials of \(A_{11}\) and \(A_{22}\), and the characteristic polynomial of \(B\) is the product of the characteristic polynomials of \(B_{11}\) and \(B_{22}\). Since \(A_{11} = B_{11}\), it follows that \(A_{22}\) and \(B_{22}\) have the same characteristic polynomial. Since
\[
X'M' = \begin{pmatrix} X_{11} & 0 \\ X_{21} & 0 \end{pmatrix}, \quad M'X' = \begin{pmatrix} X_{11} & X_{12} \\ 0 & 0 \end{pmatrix},
\]
we conclude that
\[
\det(A - MX) = \det(A' - M'X') = \det \begin{pmatrix} A_{11} - X_{11} & A_{12} - X_{12} \\ 0 & A_{22} \end{pmatrix} = \det(A_{11} - X_{11})\det(A_{22}) = \det(B_{11} - X_{11})\det(B_{22}) = \det \begin{pmatrix} B_{11} - X_{11} & 0 \\ B_{21} - X_{21} & B_{22} \end{pmatrix} = \det(B' - X'M') = \det(B - XM),
\]
as desired. (By similar arguments, \(A - MX\) and \(B - XM\) have the same characteristic polynomial.)

Second solution: We prove directly that \(A - MX\) and \(B - XM\) have the same characteristic polynomial, i.e., for any \(t \in \mathbb{R}\), writing \(A_t = A - tI\), \(B_t = B - tI\), we have
\[
\det(A_t - MX) = \det(B_t - XM).
\]
For fixed \(A, B, M\), the stated result is a polynomial identity in \(t\) and the entries of \(X\). It thus suffices to check it assuming that \(A_t, B_t, X\) are all invertible. Since \(AM = MB\), we also have \(A_tM = MB_t\), so \(A_tMB_t^{-1} = M\). Since \(\det(A_t) = \det(B_t)\) by hypothesis,
\[
\begin{align*}
\det(A_t - MX) &= \det(A_t - A_tMB_t^{-1}X) \\
&= \det(A_t)\det(1 - MB_t^{-1}X) \\
&= \det(A_t)\det(X)\det(X^{-1}B_t - M) \\
&= \det(X)\det(X^{-1}B_t - M) \\
&= \det(B_t - XM).
\end{align*}
\]

Remark: One can also assert directly that \(\det(1 - MB_t^{-1}X) = \det(1 - XMB_t^{-1})\) using the fact that for any square matrices \(U\) and \(V\), \(UV\) and \(VU\) have the same characteristic polynomial; the latter is again proved by reducing to the case where one of the two matrices is invertible, in which case the two matrices are similar.

Third solution: (by Lev Borisov) We will check that for each positive integer \(k\),
\[
\operatorname{Trace}((A - MX)^k) = \operatorname{Trace}((B - XM)^k).
\]
This will imply that \(A - MX\) and \(B - XM\) have the same characteristic polynomial, yielding the desired result. We establish the claim by expanding both sides and comparing individual terms. By hypothesis, \(A^k\) and \(B^k\) have the same characteristic polynomial, so \(\operatorname{Trace}(A^k) = \operatorname{Trace}(B^k)\). To compare the other terms, it suffices to check that for any sequence \(i_1, i_2, \ldots, i_m\) of nonnegative integers,
\[
\operatorname{Trace}(A^{i_1}MXA^{i_2}MX \cdots A^{i_{m-1}}MXA^{i_m}) = \operatorname{Trace}(B^{i_1}XMB^{i_2}XM \cdots B^{i_{m-1}}XMB^{i_m}).
\]
To establish this equality, first apply the remark following the previous solution to write
\[
\operatorname{Trace}(A^{i_1}MXA^{i_2}MX \cdots A^{i_{m-1}}MXA^{i_m}) = \operatorname{Trace}(A^{i_m + i_1}MXA^{i_2}MX \cdots A^{i_{m-1}}MX).
\]
Then apply the relation \(AM = MB\) repeatedly to commute \(M\) past \(A\), to obtain
\[
\operatorname{Trace}(MB^{i_m + i_1}XMB^{i_2}XM \cdots XMB^{i_{m-1}}X).
\]
Finally, apply the remark again to shift \(MB^{i_m}\) from the left end to the right end.

Remark: The conclusion holds with \(\mathbb{R}\) replaced by an arbitrary field. In the second solution, one must reduce to the case of an infinite field, e.g., by replacing the original field with an algebraic closure. The third solution only applies to fields of characteristic 0 or positive characteristic greater than \(n\).

Remark: It is tempting to try to reduce to the case where \(M\) is invertible, as in this case \(A - MX\) and \(B - XM\) are in fact similar. However, it is not clear how to make such an argument work.