20
$\begingroup$

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!

$\endgroup$
  • 3
    $\begingroup$ That's nice. I do not know the reference. When $p_i=\prod_{k=1}^n H(i_k)$ for certain function $H$ defined on $\{0,1,\ldots\}$, both parts factorize and are equal to the determinant of $\sum_m H(m)A^m$. The functions of such type generate all symmetric functions $i=(i_1,\ldots,i_n)\mapsto p_i$, so the result follows. $\endgroup$ – Fedor Petrov Sep 21 at 22:49
  • $\begingroup$ That sounds cool! What is the name of these functions $H$ and where could I find a proof that they generate all symmetric functions of natural number tuples? (which I think means that any symmetric $p$ can be written as a linear combination of those special $p$'s?) $\endgroup$ – Jules Sep 21 at 23:13
  • 1
    $\begingroup$ At first, the linear span of such functions is the same as the algebra generated by them. Next, it suffices to consider $p$ with a finite support $A$. Then for $H(m)=m+\alpha$ for $m\in A$ (hereafter: and 0 otherwise) we get a function of the form $p_i=(i_1+\alpha)...(i_n+\alpha)$. Varying $\alpha$ and taking linear combinations we get any elementary symmetric polynomial in $i_1,..., i_n$. They generate an algebra of all symmetric polynomials, and any symmetric function on $A$ is represented by a symmetric polynomial. $\endgroup$ – Fedor Petrov Sep 21 at 23:44
  • 1
    $\begingroup$ because the product of two such functions is again such a function. $\endgroup$ – Fedor Petrov Sep 22 at 14:20
  • 2
    $\begingroup$ @FedorPetrov : Perhaps you could collect your comments into an answer even though they don't directly answer the "reference request" part of the question. $\endgroup$ – Timothy Chow Sep 22 at 16:48
9
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ "which in turn may be symmetrized" why? We aren't in characteristic $0$ here. $\endgroup$ – darij grinberg Sep 23 at 12:19
  • $\begingroup$ Thank you @darijgrinberg, I changed the previously incorrect argument. Is it better now? $\endgroup$ – Fedor Petrov Sep 23 at 12:36
  • $\begingroup$ The proof of the lemma looks good now! Not sure how you derive the theorem from it. (I'm not currently at the best of my abilities, hwoever.) $\endgroup$ – darij grinberg Sep 23 at 13:17
  • $\begingroup$ My main problem is that $p_i$ is not a function, it's a constant. Are you talking about $p$ instead? But how does the decomposition into coefficients survive replacement by a different polynomial? And what is the finite set $A$ in your application of the lemma? $\endgroup$ – darij grinberg Sep 23 at 13:21
  • 1
    $\begingroup$ $p_i$ is a function in $i$ $\endgroup$ – Fedor Petrov Sep 23 at 13:51
7
+100
$\begingroup$

Concerning the reference request:

Several text books [1,2] give the theorem and proof for elementary symmetric polynomials $s_k=$ sum of all $k\times k$ principal minors of the $n\times n$ matrix. This also covers the trace ($s_1$) and the determinant ($s_n$).

  1. Matrix Analysis and Applied Linear Algebra by Carl D. Meyer (Equation 7.1.6 on page 494, screenshot)
  2. Matrix Analysis by Roger A. Horn and Charles R. Johnson (Theorem 1.2.12 on page 42, screenshot).

Update: I have searched quite extensively for sources that give the generalized formula for complete homogeneous symmetric polynomials, but without success. The derivation could be analogous to the published derivation for the elementary symmetric polynomials, expanding ${\rm Det}\,(A+xI)^{-1}$ instead of ${\rm Det}\,(A+xI)$, but I have not seen it published.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Thank you! So in terms of the formula, we get $s_k$ on the left hand side if we take $p_i = 1$ if the tuple $i$ has $k$ ones and $n-k$ zeroes, and $p_i = 0$ otherwise. Then some of the $A$'s on the right hand side get raised to the 1st power and some to the 0th power, and after Laplace expansion on the columns that have the 0th power, we get a sum over all $k\times k$ principal minors of $A$. I'll try to get access to those books. Is by any chance the proof by looking at the coefficient of $x^k$ in $\det(A + xI)$? I believe I have seen that proof before. P.S. I loved your lectures at Leiden! $\endgroup$ – Jules Sep 24 at 17:00
  • 1
    $\begingroup$ I added links to screenshots of each proof, and yes, that is the approach. $\endgroup$ – Carlo Beenakker Sep 24 at 20:22
  • $\begingroup$ Thanks a lot for the screenshots! $\endgroup$ – Jules Sep 24 at 22:54
  • $\begingroup$ Nice update! $\det(I - xA)^{-1} = \det(I + xA + x^2 A^2 + \cdots)$. Then expanding this by multilinearity of the determinant, and taking the coefficient of $x^k$ one gets the right hand side of the general formula, and taking the Jordan form of $A$ and using the generating function of complete homogeneous symmetric polynomials one gets the left hand side. Power sum symmetric polynomials are easy too, of course, via the trace. The proof for the general case is not much more difficult than these special cases though :) $\endgroup$ – Jules Oct 5 at 11:47
  • $\begingroup$ Check out: en.wikipedia.org/wiki/MacMahon_Master_theorem $\endgroup$ – Suvrit Oct 18 at 18:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.