POLYA005:  Traces 1, 2, 3, ... (proposed by Stephen C. Locke, 11/13/01).
Suppose that A is a 3 by 3 real matrix with trace(A)=1, trace(A^2)=2, trace(A^3)=3. What is trace(A^4)?

Discussion. [JPE, 11/13/01]: As the eigenvalues p,q,r of A verify p + q + r =1, p^2 + q^2 + r^2 = 2, p^3 + q^3 + r^3 = 3, the characteristic polynomial is x^3 - x^2 - x/2 -1/6 and  tr(A^4) = p^4 + q^4 + r^4 = 25/6. Of course, this exercise can be easily generalized.

[PY, 11/13/01]: I believe you have found the characteristic polynomial by calculating the elementary symmetric functions. In this case it is easy.
pq + qr + rp = [(p+q+r)^2 - (pp+qq+rr)]/2, and pqr can be obtained from ppp+qqq+rrr-3pqr = (p+q+r)(pp+qq+rr-pq-qr-rp).
Multiplying the characteristic polynomial by x, substituting x = p, q, r, and adding, we obtain p^4+q^4+r^4 = (p^3+q^3+r^3) +(p^2+q^2+r^2)/2 + (p+q+r)/6.
Hence your answer 25/6.

An obvious generalization is of course to determine tr(A^(n+1)) given tr(A), tr(A^2), ..., tr(A^n) for an n by n matrix A.Equivalently, given the sums of the k-th powers of the roots of a degree n polynomial for k = 1,2,..., n, to determine the sum of their (k+1)-st power. Is there a way of doing this without going through the elementary symmetric functions, at least not explicitly?

[PY, 11/13/01]: Now I recall that there is a set of Newton's relations to find these elementary symmetric functions, or equivalently the polynomial. If S_1, S_2, ..., S_n are the sums of the 1st, 2nd, ..., nth powers of the roots of the polynomial a_0x^n + a_1x^(n-1) + ... a_(n-1)x + a_n, then

a_0S_1 + a_1 = 0,
a_0S_2 + a_1S_1 + 2a_2 = 0,
a_0S_3 + a_1S_2 + a_2S_3 + 3a_3 = 0,
...
a_0S_n + a_1S_(n-1) + a_2S_(n-2) + ... + a_(n-1)S_1 + na_n = 0.

Multiplying the equation by x, substituting x = each of the roots, and adding, we obtain an extra equation

a_0S_(n+1) + a_1S_n + a_2S_(n+1) + ... + a_(n-1)S_2 + a_nS_1 = 0.

Now, we have (n+1) homogeneous linear equations in n+1 unknowns a_0, a_1, ..., a_n. From these, we have the determinantal equation
 

|S_1     1                                                  |
|S_2     S_1      2                                      |
|S_3     S_2      S_1     3                           | = 0.
|...                                                             |
|S_n     S_(n-1) S_(n-2) ...      S_1    n      |
|S_(n+1) S_n     S_(n+1) ...      S_2    S_1|

Now, is there an easy way of evaluating this determinant to find S_(n+1), or  at least in the special case  S_1 = 1, S_2 = 2, ... S_n = n?

[JPE, 11/14/01]: It is possible to get in the general case S_(n+1) in terms of S_1,...,S_n using, for instance, formal power series. Putting S_k = x_1^k + ... + x_n^k, we have sum(ln(1-x_i T,i=1..n) = -sum(S_p T^p/p, p=1..inf) and
(1-x_1 T)....(1-x_n T) = exp [-sum(S_p T^p/p, p=1..inf)] =  sum (-1)^k (S_1 T/1)^a_1...(S_i T/i)^a_i..../a_1!/a_2!..  where a_1 + a_2 + ... = k.
Looking at the coefficient of T^(n+1) (which must be 0), we get
S_(n+1) = (n+1)sum [(-S_1/1)^a_1 (-S_2/2)^a_2...(-S_n/n)^a_n/(a_1!a_2!...a_n!),  a_1+2 a_2+...+n a_n = n+1]
Of course, it is not a very nice formula, but it is the only one (uniqueness of the decomposition).

May be, in the particular case S_k = k, for k = 1...n, we can get a nice expression for S_(n+1) = (n+1) sum [(-1)^(a_1+..+a_n)/(a_1!....a_n!), a_1+2 a_2+...+n a_n = n+1], but I didn't find.

Bibliography. [1] S.R.Conrad and O.G.Ruehr, Problem E2487 (attributed to D.J.Newman), American Mathematical Monthly, 81 (1974) 776; solution 82 (1975) 764--765.

Return to [Polya Home Page] [Members] [Problem Center] [Inventory] [Reserve Area]