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+rrr3pqr = (p+q+r)(pp+qq+rrpqqrrp).
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 kth 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^(n1) + ... a_(n1)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_(n1) + a_2S_(n2) + ... + a_(n1)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_(n1)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_(n1) S_(n2) ...
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(1x_i T,i=1..n)
= sum(S_p T^p/p, p=1..inf) and
(1x_1 T)....(1x_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) 764765.
Return to [Polya
Home Page] [Members]
[Problem Center]
[Inventory]
[Reserve Area]