Old AMM problem I am working on an old AMM problem:

Suppose $A,B$ are $n\times n$ real symmetric matrices with $\operatorname{tr} ((A+B)^k)= \operatorname{tr}(A^k) + \operatorname{tr}(B^k) $ for every positive integer $k>0$. Prove that $AB=0$.

I've done the following:


*

*denote $(\lambda_i),(\mu_i),(\eta_i)$ the eigenvalues of $A,B,A+B$, respectively. They are real since $A,B$ are symmetric. Moreover, since $A,B$ are diagonalizable, if all $\lambda_i$ or all $\mu_j$ are zero, then $A$ or $B$ is zero and $AB=0$.

*suppose there exist some non-zero eigenvalues; then the identity given translates in  $$ \sum_{i=1}^n \lambda_i^k +\sum_{i=1}^n \mu_i^k=\sum_{i=1}^n \eta_i^k \qquad \forall k >0 $$
from here I can prove that any non-zero eigenvalue $\eta_i$ can be found in the LHS also with the same multiplicity (divide by the one with the greatest absolute value and take the limits $k \to \infty$, $k$ odd and $k \to \infty$, $k$ even). And therefore in the LHS there are at least $n$ eigenvalues equal to zero.

*so $A$ has $p$ zero eigenvalues and $B$ has $n-p$ zero eigenvalues.
I feel like it is not long until the end, but I can't get any further ideas. How to proceed from here?
 A: Update: A solution appears on page 167 of  the February 2012 issue of the American Mathematical Monthly. 
There were only three solvers, so we can deduce that this question was unusually difficult for a Monthly problem. 
A: Lemma: Let $X$ and $Y$ be real symmetric $n \times n$ matrices, where the eigenvalues of $X$, $Y$ and $X+Y$ are $\alpha_1 \geq \alpha_2 \geq \cdots \geq \alpha_n$, $\beta_1 \geq \beta_2 \geq \cdots \geq \beta_n$ and $\gamma_1 \geq \gamma_2 \geq \cdots \geq \gamma_n$ respectively. Then $\sum_{i=1}^k \alpha_i + \sum_{i=1}^k \beta_i \geq \sum_{i=1}^k \gamma_i$. Moreover, if we have equality, then we can change bases so that $X$ and $Y$ are simultaneously block diagonal with blocks of size $k \times k$ and $(n-k) \times (n-k)$, and the eigenvalues of the first blocks are $(\alpha_1, \ldots, \alpha_k)$ and $(\beta_1, \ldots, \beta_k)$.
Remark: Note that I have deliberately used different variable names than Beni. One of the things that made this problem tricky for me was that I had to apply this lemma in several different ways, with different matrices playing the roles of $X$ and $Y$.
Proof: Thinking of $X$ and $Y$ as quadratic forms, it makes sense to restrict them to subspaces of $\mathbb{R}^n$. With this understanding, we have $\sum_{i=1}^k \alpha_i = \max_{V \in G(k,n)} \mathrm{Tr} X|_V$, where the max ranges over $k$-dimensional subspaces of $\mathbb{R}^n$. Moreover, the maximum is achieved precisely when $X \cdot V = V$, and the eigenvalues of $X|_V$ are $(\alpha_1, \ldots, \alpha_k)$. When all the $\alpha$'s are distinct, this can be expressed more easily by saying that $V$ is the span of the eigenvectors associated to the largest $k$ eigenvalues.
We want to show that 
$$\max_{V \in G(k,n)} \mathrm{Tr} X|_V + \max_{V \in G(k,n)} \mathrm{Tr} Y|_V \geq \max_{V \in G(k,n)} \mathrm{Tr} \left( X+Y \right)_V$$
or, equivalently,
$$\max_{(V,W) \in G(k,n)^2} \mathrm{Tr} \left( X|_V + Y_W \right) \geq \max_{V \in G(k,n)} \mathrm{Tr} \left( X|_V +Y|_V \right)$$
But this is obvious, because the right hand maximum is over a larger set.
Moreover, if we have equality, then there is some $k$-plane $V$ with $XV=YV =V$ and where the eigenvalues of $X|_V$ and $Y|_V$ are $(\alpha_1, \ldots, \alpha_k)$ and $(\beta_1, \ldots, \beta_k)$. This is precisely the required claim about being block diagonal. $\square$
Let $A$ and $B$ be as in the problem. Let the eigenvalues of $A$ be $\lambda^{+}_1 \geq \cdots \geq \lambda^{+}_{p^{+}} > 0 =0=\cdots=0 > \lambda^{-}_{1} \geq \cdots \geq \lambda^{-}_{p_{-}}$. Define $\mu^{+}_i$, $\mu^{-}_i$, $q^{+}$ and $q^{-}$ similarly. Then, as Beni explains, we have $p^{+}+p^{-} + q^{+} + q^{-} \leq n$, and the eigenvalues of $X+Y$ are the concatenation of the $\lambda^{\pm}_i$'s, the $\mu^{\pm}_i$'s, and $n-p^{+}-p^{-} - q^{+} - q^{-}$ copies of $0$.
Apply the lemma with $k=p^{+}+q^{+}$, $X=A$ and $Y=B$. This shows that we can split into two smaller problems, one where all the $\lambda$'s and $\mu$'s are positive and another where they are all nonpositive. We will focus on the first block; the second block is similar.
So we are reduced to the case that $A$ and $B$ have no negative eigenvalues.
Now, we use induction on $n$. The base case $n=1$ is easy. Without loss of generality, let $\lambda^{+}_1 \geq \mu^{+}_1$. So $\lambda^{+}_1$ is the greatest eigenvalue of both $A$ and $A+B$. 
Apply the lemma with $k=1$, $X=A+B$ and $Y=-B$. The greatest eigenvalue of $-B$ is $0$. So the greatest eigenvalue of $(A+B)+(-B)$ is the sum of the greatest eigenvalues of $A+B$ and $-B$, and we conclude that we can split off a $1 \times 1$ block from $A+B$ and $-B$, where the block of $-B$ is zero. 
The product of the $1 \times 1$ blocks is $0$, and by induction the product of the other blocks is $0$ as well.
A: define $
M=\left[
\begin{array}{cc}
A+B & O_n\\ 
O_n & O_n
\end{array}\right]
$ and $
N=\left[
\begin{array}{cc}
A & O_n\\ 
O_n & B
\end{array}\right]
$.
$ (\forall k \in \mathbb{N}^*,Tr((A+B)^k)=Tr(A^k)+Tr(B^k))$ $\Leftrightarrow$ $ (\forall k \in \mathbb{N},Tr(M^k)=Tr(N^k))$ $\Leftrightarrow \chi_M=\chi_N$ where $\chi_S$ is the characteristic polynomial of the matrix S.
then the problem is equivalent to :
$X^n.\chi_{A+B}(X)=\chi_A(X).\chi_B(X) $.
denote $ \alpha=\{\alpha_1,\alpha_2,...,\alpha_p\} $  ($ \beta=\{\beta_1,\beta_2,...,\beta_q \} $ and $ \gamma=\{\gamma_1,\gamma_2,...,\gamma_r\} $) the non-zero eigenvalues of $A$ ($B$ and $A+B$ ) (not necessarily distinct). then $\gamma = \alpha \cup \beta $ and $r=p+q$. 
In addition, we have $Im(A+B)=Im(A)\oplus Im(B)$ (where $Im(S)$ is the range of a given matrix $S$), since we can consider just the restriction of $A$, $B$ and $A+B$ to the subspace $Im(A+B)$, then we can may assume that $Im(A+B)=\mathbb{R}^n$.
let $a=\{a_1,...,a_p\}$ ($b=\{b_1,...,b_q\}$ and $c=\{c_1,...,c_r\}$) an orthonormal basis of $Im(A)$ ($Im(B)$ and $Im(C)$) that consists of eigenvectors of $A$ ($B$ and $C$), that is $Aa_i=\alpha_i a_i$ ($Bb_i=\beta_i b_i$ and $Cc_i=\gamma_i c_i$) and let $
D_a=diag(\alpha_1,...,\alpha_p)
$ and $D_b=diag(\beta_1,...,\beta_q)$.
then the matrix $A+B$ can be written in the basis $c$ as $
F_1=\left[
\begin{array}{cc}
D_a & O\\ 
O & D_b
\end{array}\right]
$.
denote now $S=(s_{ij})_{i,j}$ where $s_{ij}=<a_i | b_j>$ for $1 \le i \le p$ and $1 \le j \le q$.
then the matrix $A+B$ can be written in the basis $a\cup b$ as $F_2=\left[
\begin{array}{cc}
D_a & D_a S \\ 
D_b S^T  & D_b
\end{array}\right]=\left[
\begin{array}{cc}
D_a & O \\ 
O  & D_b
\end{array}\right]\left[
\begin{array}{cc}
I &  S \\ 
S^T  & I
\end{array}\right]
$, but $F_1$ and $F_2$ ar similar, then $det(F_1)=det(F_2)$ $\Rightarrow$ $det(I-S^T S)=det \left[
\begin{array}{cc}
I &  S \\ 
S^T  & I
\end{array}\right]=1$. 
on the other hand, consider $ 1 \le j \le q$; $n_j=b_j - \sum_{i=1}^{p}s_{ij}a_i$, then $<n_i | n_j>=(I-S^T S)_{ij}$, therefore the matrix $I-S^T S $ is a gramian matrix, it follows that $I-S^T S $ is symmetric positive matrix, denote $ 0 \le \theta_1 \le \theta_2 \le ... \le \theta_q $ its eigenvalues.
then by the arithmetic mean geometric mean inequality: $q-\sum_{i=1}^{p}\sum_{j=1}^{q}s_{ij}^2 = Tr(I- S^T S)=\sum_{i=1}^{q}\theta_i \ge q \sqrt[q]{\prod_{i=1}^{q} \theta_i}=q$ which gives $\sum_{i=1}^{p}\sum_{j=1}^{q}s_{ij}^2 \le 0$, that is, $S=O$.
it follows that for $ 1 \le i \le p $; $Ba_i=\sum_{j=1}^{q}s_{ij} \beta_j b_j = 0$ and for $ 1 \le j \le q $; $Ab_j=\sum_{i=1}^{p}s_{ij} \alpha_i a_i = 0$
therefore we deduce easily $AB=BA=O$.
