The trace of a matrix is the sum of the eigenvalues and the determinant is the product of the eigenvalues. The fundamental theorem of symmetric polynomials says that we can write any symmetric polynomial of the roots of a polynomial as a polynomial of its coefficients. We can apply this to the characteristic polynomial of a matrix $A$ to write any symmetric polynomial of eigenvalues as a polynomial in the entries of $A$.
I stumbled upon an explicit formula for this. Let $A$ be an $n \times n$ matrix and $a_1, \dots, a_n$ be its eigenvalues. Then we have the following identity, provided the left hand side is a symmetric polynomial:
$$
\sum_{i \in \mathbb{N}^n} p_i a_1^{i_1} \cdots a_n^{i_n} = \sum_{i \in \mathbb{N}^n} p_i \det(A_1^{i_1}, \dots, A_n^{i_n})
$$
The determinant $\det(A_1^{i_1}, \dots, A_n^{i_n})$ on the right hand side is the determinant of a matrix with those column vectors, where $A_i^k$ is the $i$-th column of the $k$-th power of $A$. The left hand side is a symmetric polynomial of the eigenvalues of $A$, and the right hand side is a polynomial of the entries of $A$.
Example: if $A$ is a $2\times 2$ matrix, then $$a_1 a_2^2 + a_1^2 a_2 = \det(A_1, A_2^2) + \det(A_1^2, A_2)$$
Proof. Let $p(A) \in End(\bigwedge^n V^*)$ be given by $p(A)f(v_1,\dots,v_n) = \sum_{i\in \mathbb{N}^n}f(A^{i_1}v_1,\dots,A^{i_n}v_n)$. We have $End(\bigwedge^n V^*) \simeq \mathbb{R}$ and $p(A)$ is the right hand side of the identity under this isomorphism. Since $p(A)$ was defined basis independently, the right hand side is basis independent, and we get the left hand side in the eigenbasis. $\Box$
Link to detailed proof and slight generalization to an identity on several commuting matrices. E.g. for commuting $2\times 2$ matrices $A,B$:
$$a_1 b_1 a_2^2 + a_1^2 a_2 b_2 = \det(AB_1, A_2^2) + \det(A_1^2, AB_2)$$
This identity looks like it should be a few hundred years old, especially since the proof is quite simple, but I have not seen this in linear algebra courses. Is this a well known identity? Where should I look to learn more about these types of identities? Or, maybe I am mistaken and the identity is false? (though I have also empirically tested it with a computer program) I apologize if this question is too basic for mathoverflow; I am only doing pure mathematics for fun. I initially asked elsewhere but was advised to ask here. Thanks!
Best Answer
This is not a reference, but a short proof.
We use the following (probably known, but see later) lemma on representing a symmetric tensor as a linear combination of rank-1 symmetric tensors.
Lemma. Let $A$ be a finite set, $K$ an infinite field. Denote by $\mathcal S$ the set of symmetric functions $p:A^n\to K$. Then $\mathcal S$ is the $K$-span of rank-one functions, that is, the functions of the type $h(x_1)h(x_2)\ldots h(x_n)$, where $h:A\to K$.
Proof. Note that the product of two rank-one functions is a rank-one function. Thus the linear space $\mathcal T$, generated by rank-one functions, coincides with the $K$-algebra generated by them.
We may suppose that $A\subset K$. For $k=0,1,\ldots,n$ denote $e_k(x_1,\ldots,x_n)$ the elementary symmetric polynomial, that is, $\varphi_t(x_1,\ldots,x_n):=\prod(1+tx_i)=\sum_{k=0}^n t^ke_k$. We identify $e_k$ and the corresponding element of $\mathcal S$. Choosing $n+1$ distinct values $t_1,\ldots,t_{n+1}\in K$ and solving the corresponding (Vandermonde's) linear system of equations we represent each $e_k$ as a linear combinations of $\varphi_{t_i}\in \mathcal T$. Thus $e_k\in \mathcal S$ for all $k=0,1,\ldots,n$. It is well known that $e_k$'s generate the algebra of symmetric polynomials (over any field). Thus any symmetric polynomial function belongs to $\mathcal T$. It remains to note that any symmetric function $f\in \mathcal S$ may be represented by a symmetric polynomial. Indeed, a symmetric function $f$ may be represented as $F(e_1,e_2,\ldots,e_n)$ for certain function function $F$ defined on the corresponding finite set (because the values of $e_1,\ldots,e_n$ determine the values of $x_1,\ldots,x_n$ up to permutation). $F$ in turn coincides with a polynomial function on this finite set. $\square$
Now we may prove your theorem for finitely supported function $i\mapsto p_i$. Due to Lemma it may be supposed to have the form $p_i=\prod_{k=1}^n H(i_k)$ for a certain finitely supported function $H$ on $\mathbb{N}$ (as OP, I denote here $\mathbb{N}=\{0,1,\ldots\}$). In this case both parts of your identity are equal to $\det (\sum_m H(m)A^m)$.
Comment. Lemma does not hold for finite fields. For example, if $A=K=\{0,1\}$. Then the function $x+y+z$ is not a linear combination of rank-one functions 1, $xyz$, $(x+1)(y+1)(z+1)$: if $x+y+z=a+bxyz+c(x+1)(y+1)(z+1)$, then for $y=0,z=1,x=a$ we get $0=1$. I must make a warning that in the subject-related paper "Symmetric tensors and symmetric tensor rank" by Pierre Comon, Gene Golub, Lek-Heng Lim, Bernard Mourrain (SIAM Journal on Matrix Analysis and Applications, 2008, 30 (3), pp.1254-1279) this statement, after equation (1.1), is stated for any field, although proved for complex numbers, and the proof uses that a non-zero polynomial has non-zero values.
In any case, you may always enlarge the ground field and safely think that it is infinite.