[math-fun] Expansion of charpoly's in terms of traces ?
I noticed in Wikipedia's description of eigenvalues, an expansion of the characteristic polynomial of a 3x3 matrix in terms of traces, so I wanted to see if this worked more generally. For a 2x2 matrix, the charpoly is: x^2-x*tr(M)+det(A) = x^2-x*tr(M)+ (tr(M)^2-tr(M^2))/2 For a 3x3 matrix, the charpoly is: x^3-x^2*tr(M)+x*(tr(M)^2-tr(M^2))/2-det(M) = x^3-x^2*tr(M)+x*(tr(M)^2-tr(M^2))/2-(tr(M)^3+2*tr(M^3)-3*tr(M)*tr(M^2))/6 For a 4x4 matrix, the charpoly is: x^4-x^3*tr(M)+x^2*(tr(M)^2-tr(M^2))/2-x*(tr(M)^3+2*tr(M^3)-3*tr(M)*tr(M^2))/6+det(M) Notice that the higher order terms are the same form even though the dimension is higher. Can we continue this indefinitely? What is the general term?
Yes, The key idea are the Newton Identities ( http://en.wikipedia.org/wiki/Newton's_identities ), which give a way of going from the power sums of the roots of a polynomial to the symmetric functions of the roots. For matrices, the power sums of the eigenvalues are the the traces of the powers of the matrix, and the coefficients of the characteristic polynomial are the symmetric functions of the roots (up to sign). Note that it is only necessary to prove this formula when the matrix has all distinct eigenvalues because this set of matrices is Zariski dense in the set of all matrices (i.e. if there is a polynomial equation giving the characteristic polynomial in terms of the traces of the powers of the matrix which holds for matrices with distinct eigenvalues, it must hold for all matrices). Victor On Thu, Dec 3, 2009 at 11:18 AM, Henry Baker <hbaker1@pipeline.com> wrote:
I noticed in Wikipedia's description of eigenvalues, an expansion of the characteristic polynomial of a 3x3 matrix in terms of traces, so I wanted to see if this worked more generally.
For a 2x2 matrix, the charpoly is:
x^2-x*tr(M)+det(A) = x^2-x*tr(M)+ (tr(M)^2-tr(M^2))/2
For a 3x3 matrix, the charpoly is:
x^3-x^2*tr(M)+x*(tr(M)^2-tr(M^2))/2-det(M) =
x^3-x^2*tr(M)+x*(tr(M)^2-tr(M^2))/2-(tr(M)^3+2*tr(M^3)-3*tr(M)*tr(M^2))/6
For a 4x4 matrix, the charpoly is:
x^4-x^3*tr(M)+x^2*(tr(M)^2-tr(M^2))/2-x*(tr(M)^3+2*tr(M^3)-3*tr(M)*tr(M^2))/6+det(M)
Notice that the higher order terms are the same form even though the dimension is higher.
Can we continue this indefinitely?
What is the general term?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Because of the appearance of n! denominators, all this is true only in characteristic zero. As a counterexample, let M be the 2x2 identity matrix in characteristic 2. The charpoly is (x - 1)^2 = x^2 + 1. But tr(M) = tr(M^2) = 0. -- Gene ________________________________ From: victor miller <victorsmiller@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Sent: Thu, December 3, 2009 8:39:55 AM Subject: Re: [math-fun] Expansion of charpoly's in terms of traces ? Yes, The key idea are the Newton Identities ( http://en.wikipedia.org/wiki/Newton's_identities ), which give a way of going from the power sums of the roots of a polynomial to the symmetric functions of the roots. For matrices, the power sums of the eigenvalues are the the traces of the powers of the matrix, and the coefficients of the characteristic polynomial are the symmetric functions of the roots (up to sign). Note that it is only necessary to prove this formula when the matrix has all distinct eigenvalues because this set of matrices is Zariski dense in the set of all matrices (i.e. if there is a polynomial equation giving the characteristic polynomial in terms of the traces of the powers of the matrix which holds for matrices with distinct eigenvalues, it must hold for all matrices). Victor On Thu, Dec 3, 2009 at 11:18 AM, Henry Baker <hbaker1@pipeline.com> wrote:
I noticed in Wikipedia's description of eigenvalues, an expansion of the characteristic polynomial of a 3x3 matrix in terms of traces, so I wanted to see if this worked more generally.
For a 2x2 matrix, the charpoly is:
x^2-x*tr(M)+det(A) = x^2-x*tr(M)+ (tr(M)^2-tr(M^2))/2
For a 3x3 matrix, the charpoly is:
x^3-x^2*tr(M)+x*(tr(M)^2-tr(M^2))/2-det(M) =
x^3-x^2*tr(M)+x*(tr(M)^2-tr(M^2))/2-(tr(M)^3+2*tr(M^3)-3*tr(M)*tr(M^2))/6
For a 4x4 matrix, the charpoly is:
x^4-x^3*tr(M)+x^2*(tr(M)^2-tr(M^2))/2-x*(tr(M)^3+2*tr(M^3)-3*tr(M)*tr(M^2))/6+det(M)
Notice that the higher order terms are the same form even though the dimension is higher.
Can we continue this indefinitely?
What is the general term?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
There are actually formulas which work in the "small" characteristic cases. In your case you'd need to look at tr(M^3). This is related to the decoding of BCH codes (where they work out the formulas in characteristic 2). Victor On Thu, Dec 3, 2009 at 12:09 PM, Eugene Salamin <gene_salamin@yahoo.com>wrote:
Because of the appearance of n! denominators, all this is true only in characteristic zero. As a counterexample, let M be the 2x2 identity matrix in characteristic 2. The charpoly is (x - 1)^2 = x^2 + 1. But tr(M) = tr(M^2) = 0.
-- Gene
________________________________ From: victor miller <victorsmiller@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Sent: Thu, December 3, 2009 8:39:55 AM Subject: Re: [math-fun] Expansion of charpoly's in terms of traces ?
Yes, The key idea are the Newton Identities ( http://en.wikipedia.org/wiki/Newton's_identities ), which give a way of going from the power sums of the roots of a polynomial to the symmetric functions of the roots. For matrices, the power sums of the eigenvalues are the the traces of the powers of the matrix, and the coefficients of the characteristic polynomial are the symmetric functions of the roots (up to sign). Note that it is only necessary to prove this formula when the matrix has all distinct eigenvalues because this set of matrices is Zariski dense in the set of all matrices (i.e. if there is a polynomial equation giving the characteristic polynomial in terms of the traces of the powers of the matrix which holds for matrices with distinct eigenvalues, it must hold for all matrices).
Victor
On Thu, Dec 3, 2009 at 11:18 AM, Henry Baker <hbaker1@pipeline.com> wrote:
I noticed in Wikipedia's description of eigenvalues, an expansion of the characteristic polynomial of a 3x3 matrix in terms of traces, so I wanted to see if this worked more generally.
For a 2x2 matrix, the charpoly is:
x^2-x*tr(M)+det(A) = x^2-x*tr(M)+ (tr(M)^2-tr(M^2))/2
For a 3x3 matrix, the charpoly is:
x^3-x^2*tr(M)+x*(tr(M)^2-tr(M^2))/2-det(M) =
x^3-x^2*tr(M)+x*(tr(M)^2-tr(M^2))/2-(tr(M)^3+2*tr(M^3)-3*tr(M)*tr(M^2))/6
For a 4x4 matrix, the charpoly is:
x^4-x^3*tr(M)+x^2*(tr(M)^2-tr(M^2))/2-x*(tr(M)^3+2*tr(M^3)-3*tr(M)*tr(M^2))/6+det(M)
Notice that the higher order terms are the same form even though the dimension is higher.
Can we continue this indefinitely?
What is the general term?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
What I said is "almost" true. What one really needs to look at is the ring of functions which are generated by all power sums as a subring of the ring of all symmetric functions. As was pointed out, in characteristic 0 (or, more generally anything larger than the degree) they are the same. In small characteristic they are not. There are formulas for the index of the rings (they're related to the theory of modular representations of the symmetric group). Victor On Thu, Dec 3, 2009 at 12:13 PM, victor miller <victorsmiller@gmail.com>wrote:
There are actually formulas which work in the "small" characteristic cases. In your case you'd need to look at tr(M^3). This is related to the decoding of BCH codes (where they work out the formulas in characteristic 2).
Victor
On Thu, Dec 3, 2009 at 12:09 PM, Eugene Salamin <gene_salamin@yahoo.com>wrote:
Because of the appearance of n! denominators, all this is true only in characteristic zero. As a counterexample, let M be the 2x2 identity matrix in characteristic 2. The charpoly is (x - 1)^2 = x^2 + 1. But tr(M) = tr(M^2) = 0.
-- Gene
________________________________ From: victor miller <victorsmiller@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Sent: Thu, December 3, 2009 8:39:55 AM Subject: Re: [math-fun] Expansion of charpoly's in terms of traces ?
Yes, The key idea are the Newton Identities ( http://en.wikipedia.org/wiki/Newton's_identities ), which give a way of going from the power sums of the roots of a polynomial to the symmetric functions of the roots. For matrices, the power sums of the eigenvalues are the the traces of the powers of the matrix, and the coefficients of the characteristic polynomial are the symmetric functions of the roots (up to sign). Note that it is only necessary to prove this formula when the matrix has all distinct eigenvalues because this set of matrices is Zariski dense in the set of all matrices (i.e. if there is a polynomial equation giving the characteristic polynomial in terms of the traces of the powers of the matrix which holds for matrices with distinct eigenvalues, it must hold for all matrices).
Victor
On Thu, Dec 3, 2009 at 11:18 AM, Henry Baker <hbaker1@pipeline.com> wrote:
I noticed in Wikipedia's description of eigenvalues, an expansion of the characteristic polynomial of a 3x3 matrix in terms of traces, so I wanted to see if this worked more generally.
For a 2x2 matrix, the charpoly is:
x^2-x*tr(M)+det(A) = x^2-x*tr(M)+ (tr(M)^2-tr(M^2))/2
For a 3x3 matrix, the charpoly is:
x^3-x^2*tr(M)+x*(tr(M)^2-tr(M^2))/2-det(M) =
x^3-x^2*tr(M)+x*(tr(M)^2-tr(M^2))/2-(tr(M)^3+2*tr(M^3)-3*tr(M)*tr(M^2))/6
For a 4x4 matrix, the charpoly is:
x^4-x^3*tr(M)+x^2*(tr(M)^2-tr(M^2))/2-x*(tr(M)^3+2*tr(M^3)-3*tr(M)*tr(M^2))/6+det(M)
Notice that the higher order terms are the same form even though the dimension is higher.
Can we continue this indefinitely?
What is the general term?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I haven't thought about how the following might be applied to the difficulty raised by Gene, but it might be worth noting that one of the many ways in which mathematicians conventionally complicate their lives is by defining polynomials over finite fields in an avoidably clumsy fashion. Restricting oneself to linear combinations of powers excludes a lot of functions which ought to be polynomial, but fail to do so on account of the Fermat little theorem x^p = x mod p. Suppose instead polynomials are defined as linear combinations of binomial coefficients, where binomial coefficients are in turn defined via Pascal's triangle. Now --- for example --- linear difference equations with constant coefficients all have polynomial solutions modulo a prime, just as they do over the rationals. Fred Lunnon On 12/3/09, victor miller <victorsmiller@gmail.com> wrote:
What I said is "almost" true. What one really needs to look at is the ring of functions which are generated by all power sums as a subring of the ring of all symmetric functions. As was pointed out, in characteristic 0 (or, more generally anything larger than the degree) they are the same. In small characteristic they are not. There are formulas for the index of the rings (they're related to the theory of modular representations of the symmetric group).
Victor
On Thu, Dec 3, 2009 at 12:13 PM, victor miller <victorsmiller@gmail.com>wrote:
There are actually formulas which work in the "small" characteristic cases. In your case you'd need to look at tr(M^3). This is related to the decoding of BCH codes (where they work out the formulas in characteristic 2).
Victor
On Thu, Dec 3, 2009 at 12:09 PM, Eugene Salamin <gene_salamin@yahoo.com>wrote:
Because of the appearance of n! denominators, all this is true only in characteristic zero. As a counterexample, let M be the 2x2 identity matrix in characteristic 2. The charpoly is (x - 1)^2 = x^2 + 1. But tr(M) = tr(M^2) = 0.
-- Gene
________________________________ From: victor miller <victorsmiller@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Sent: Thu, December 3, 2009 8:39:55 AM Subject: Re: [math-fun] Expansion of charpoly's in terms of traces ?
Yes, The key idea are the Newton Identities ( http://en.wikipedia.org/wiki/Newton's_identities ), which give a way of going from the power sums of the roots of a polynomial to the symmetric functions of the roots. For matrices, the power sums of the eigenvalues are the the traces of the powers of the matrix, and the coefficients of the characteristic polynomial are the symmetric functions of the roots (up to sign). Note that it is only necessary to prove this formula when the matrix has all distinct eigenvalues because this set of matrices is Zariski dense in the set of all matrices (i.e. if there is a polynomial equation giving the characteristic polynomial in terms of the traces of the powers of the matrix which holds for matrices with distinct eigenvalues, it must hold for all matrices).
Victor
On Thu, Dec 3, 2009 at 11:18 AM, Henry Baker <hbaker1@pipeline.com> wrote:
I noticed in Wikipedia's description of eigenvalues, an expansion of the characteristic polynomial of a 3x3 matrix in terms of traces, so I wanted to see if this worked more generally.
For a 2x2 matrix, the charpoly is:
x^2-x*tr(M)+det(A) = x^2-x*tr(M)+ (tr(M)^2-tr(M^2))/2
For a 3x3 matrix, the charpoly is:
x^3-x^2*tr(M)+x*(tr(M)^2-tr(M^2))/2-det(M) =
x^3-x^2*tr(M)+x*(tr(M)^2-tr(M^2))/2-(tr(M)^3+2*tr(M^3)-3*tr(M)*tr(M^2))/6
For a 4x4 matrix, the charpoly is:
x^4-x^3*tr(M)+x^2*(tr(M)^2-tr(M^2))/2-x*(tr(M)^3+2*tr(M^3)-3*tr(M)*tr(M^2))/6+det(M)
Notice that the higher order terms are the same form even though the dimension is higher.
Can we continue this indefinitely?
What is the general term?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 12/3/09, Fred lunnon <fred.lunnon@gmail.com> wrote:
I haven't thought about how the following might be applied to the difficulty raised by Gene, but it might be worth noting that one of the many ways in which mathematicians conventionally complicate their lives is by defining polynomials over finite fields in an avoidably clumsy fashion. Restricting oneself to linear combinations of powers excludes a lot of functions which ought to be polynomial, but fail to do so on account of the Fermat little theorem x^p = x mod p.
Suppose instead polynomials are defined as linear combinations of binomial coefficients, where binomial coefficients are in turn defined via Pascal's triangle. Now --- for example --- linear difference equations with constant coefficients all have polynomial solutions modulo a prime, just as they do over the rationals.
Fred Lunnon
I should have been more explicit here --- the second arguments of the binomial coefficients should of course be natural constants. For example over \F_2, n^3 takes the same values as n; nonetheless n_C_3 provides a nontrivial solution of \Delta^4 f(n) = 0, taking values f(n) = 0,0,0,1,0,0,0,1,... for n = 0,1,2,3,4,5,6,7,... WFL
On 12/3/09, victor miller <victorsmiller@gmail.com> wrote:
What I said is "almost" true. What one really needs to look at is the ring of functions which are generated by all power sums as a subring of the ring of all symmetric functions. As was pointed out, in characteristic 0 (or, more generally anything larger than the degree) they are the same. In small characteristic they are not. There are formulas for the index of the rings (they're related to the theory of modular representations of the symmetric group).
Victor
On Thu, Dec 3, 2009 at 12:13 PM, victor miller <victorsmiller@gmail.com>wrote:
There are actually formulas which work in the "small" characteristic cases. In your case you'd need to look at tr(M^3). This is related to the decoding of BCH codes (where they work out the formulas in characteristic 2).
Victor
On Thu, Dec 3, 2009 at 12:09 PM, Eugene Salamin <gene_salamin@yahoo.com>wrote:
Because of the appearance of n! denominators, all this is true only in characteristic zero. As a counterexample, let M be the 2x2 identity matrix in characteristic 2. The charpoly is (x - 1)^2 = x^2 + 1. But tr(M) = tr(M^2) = 0.
-- Gene
________________________________ From: victor miller <victorsmiller@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Sent: Thu, December 3, 2009 8:39:55 AM Subject: Re: [math-fun] Expansion of charpoly's in terms of traces ?
Yes, The key idea are the Newton Identities ( http://en.wikipedia.org/wiki/Newton's_identities ), which give a way of going from the power sums of the roots of a polynomial to the symmetric functions of the roots. For matrices, the power sums of the eigenvalues are the the traces of the powers of the matrix, and the coefficients of the characteristic polynomial are the symmetric functions of the roots (up to sign). Note that it is only necessary to prove this formula when the matrix has all distinct eigenvalues because this set of matrices is Zariski dense in the set of all matrices (i.e. if there is a polynomial equation giving the characteristic polynomial in terms of the traces of the powers of the matrix which holds for matrices with distinct eigenvalues, it must hold for all matrices).
Victor
On Thu, Dec 3, 2009 at 11:18 AM, Henry Baker <hbaker1@pipeline.com> wrote:
I noticed in Wikipedia's description of eigenvalues, an expansion of the characteristic polynomial of a 3x3 matrix in terms of traces, so I wanted to see if this worked more generally.
For a 2x2 matrix, the charpoly is:
x^2-x*tr(M)+det(A) = x^2-x*tr(M)+ (tr(M)^2-tr(M^2))/2
For a 3x3 matrix, the charpoly is:
x^3-x^2*tr(M)+x*(tr(M)^2-tr(M^2))/2-det(M) =
x^3-x^2*tr(M)+x*(tr(M)^2-tr(M^2))/2-(tr(M)^3+2*tr(M^3)-3*tr(M)*tr(M^2))/6
For a 4x4 matrix, the charpoly is:
x^4-x^3*tr(M)+x^2*(tr(M)^2-tr(M^2))/2-x*(tr(M)^3+2*tr(M^3)-3*tr(M)*tr(M^2))/6+det(M)
Notice that the higher order terms are the same form even though the dimension is higher.
Can we continue this indefinitely?
What is the general term?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Fred, can you provide an example of something which ought to be a polynomial, but is not a linear combination of powers? While it is true that a^q = a for all a in F_q, the polynomials x and x^q are distinct elements of the ring F_q[x]. -- Gene ________________________________ From: Fred lunnon <fred.lunnon@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Sent: Thu, December 3, 2009 10:42:43 AM Subject: Re: [math-fun] Expansion of charpoly's in terms of traces ? On 12/3/09, Fred lunnon <fred.lunnon@gmail.com> wrote:
I haven't thought about how the following might be applied to the difficulty raised by Gene, but it might be worth noting that one of the many ways in which mathematicians conventionally complicate their lives is by defining polynomials over finite fields in an avoidably clumsy fashion. Restricting oneself to linear combinations of powers excludes a lot of functions which ought to be polynomial, but fail to do so on account of the Fermat little theorem x^p = x mod p.
Suppose instead polynomials are defined as linear combinations of binomial coefficients, where binomial coefficients are in turn defined via Pascal's triangle. Now --- for example --- linear difference equations with constant coefficients all have polynomial solutions modulo a prime, just as they do over the rationals.
Fred Lunnon
I should have been more explicit here --- the second arguments of the binomial coefficients should of course be natural constants. For example over \F_2, n^3 takes the same values as n; nonetheless n_C_3 provides a nontrivial solution of \Delta^4 f(n) = 0, taking values f(n) = 0,0,0,1,0,0,0,1,... for n = 0,1,2,3,4,5,6,7,... WFL
On 12/3/09, victor miller <victorsmiller@gmail.com> wrote:
What I said is "almost" true. What one really needs to look at is the ring of functions which are generated by all power sums as a subring of the ring of all symmetric functions. As was pointed out, in characteristic 0 (or, more generally anything larger than the degree) they are the same. In small characteristic they are not. There are formulas for the index of the rings (they're related to the theory of modular representations of the symmetric group).
Victor
On Thu, Dec 3, 2009 at 12:13 PM, victor miller <victorsmiller@gmail.com>wrote:
There are actually formulas which work in the "small" characteristic cases. In your case you'd need to look at tr(M^3). This is related to the decoding of BCH codes (where they work out the formulas in characteristic 2).
Victor
On Thu, Dec 3, 2009 at 12:09 PM, Eugene Salamin <gene_salamin@yahoo.com>wrote:
Because of the appearance of n! denominators, all this is true only in characteristic zero. As a counterexample, let M be the 2x2 identity matrix in characteristic 2. The charpoly is (x - 1)^2 = x^2 + 1. But tr(M) = tr(M^2) = 0.
-- Gene
________________________________ From: victor miller <victorsmiller@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Sent: Thu, December 3, 2009 8:39:55 AM Subject: Re: [math-fun] Expansion of charpoly's in terms of traces ?
Yes, The key idea are the Newton Identities ( http://en.wikipedia.org/wiki/Newton's_identities ), which give a way of going from the power sums of the roots of a polynomial to the symmetric functions of the roots. For matrices, the power sums of the eigenvalues are the the traces of the powers of the matrix, and the coefficients of the characteristic polynomial are the symmetric functions of the roots (up to sign). Note that it is only necessary to prove this formula when the matrix has all distinct eigenvalues because this set of matrices is Zariski dense in the set of all matrices (i.e. if there is a polynomial equation giving the characteristic polynomial in terms of the traces of the powers of the matrix which holds for matrices with distinct eigenvalues, it must hold for all matrices).
Victor
On Thu, Dec 3, 2009 at 11:18 AM, Henry Baker <hbaker1@pipeline.com> wrote:
I noticed in Wikipedia's description of eigenvalues, an expansion of the characteristic polynomial of a 3x3 matrix in terms of traces, so I wanted to see if this worked more generally.
For a 2x2 matrix, the charpoly is:
x^2-x*tr(M)+det(A) = x^2-x*tr(M)+ (tr(M)^2-tr(M^2))/2
For a 3x3 matrix, the charpoly is:
x^3-x^2*tr(M)+x*(tr(M)^2-tr(M^2))/2-det(M) =
x^3-x^2*tr(M)+x*(tr(M)^2-tr(M^2))/2-(tr(M)^3+2*tr(M^3)-3*tr(M)*tr(M^2))/6
For a 4x4 matrix, the charpoly is:
x^4-x^3*tr(M)+x^2*(tr(M)^2-tr(M^2))/2-x*(tr(M)^3+2*tr(M^3)-3*tr(M)*tr(M^2))/6+det(M)
Notice that the higher order terms are the same form even though the dimension is higher.
Can we continue this indefinitely?
What is the general term?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
If they were the same, then crypto protocols based on discrete logarithms would be broken. For example, in the Diffie-Hellman key exchange, Norman sends x^n and Marvin sends x^m in the clear (where n,m are their respective secret keys), and each is able to compute x^{nm} while an eavesdropper is not--given the element x^n, it's infeasible to compute the function f(x)=x^n. On Thu, Dec 3, 2009 at 11:04 AM, Eugene Salamin <gene_salamin@yahoo.com> wrote:
Fred, can you provide an example of something which ought to be a polynomial, but is not a linear combination of powers? While it is true that a^q = a for all a in F_q, the polynomials x and x^q are distinct elements of the ring F_q[x].
-- Gene ________________________________ From: Fred lunnon <fred.lunnon@gmail.com>
To: math-fun <math-fun@mailman.xmission.com> Sent: Thu, December 3, 2009 10:42:43 AM Subject: Re: [math-fun] Expansion of charpoly's in terms of traces ?
On 12/3/09, Fred lunnon <fred.lunnon@gmail.com> wrote:
I haven't thought about how the following might be applied to the difficulty raised by Gene, but it might be worth noting that one of the many ways in which mathematicians conventionally complicate their lives is by defining polynomials over finite fields in an avoidably clumsy fashion. Restricting oneself to linear combinations of powers excludes a lot of functions which ought to be polynomial, but fail to do so on account of the Fermat little theorem x^p = x mod p.
Suppose instead polynomials are defined as linear combinations of binomial coefficients, where binomial coefficients are in turn defined via Pascal's triangle. Now --- for example --- linear difference equations with constant coefficients all have polynomial solutions modulo a prime, just as they do over the rationals.
Fred Lunnon
I should have been more explicit here --- the second arguments of the binomial coefficients should of course be natural constants.
For example over \F_2, n^3 takes the same values as n; nonetheless n_C_3 provides a nontrivial solution of \Delta^4 f(n) = 0, taking values f(n) = 0,0,0,1,0,0,0,1,... for n = 0,1,2,3,4,5,6,7,...
WFL
On 12/3/09, victor miller <victorsmiller@gmail.com> wrote: > What I said is "almost" true. What one really needs to look at is the ring > of functions which are generated by all power sums as a subring of the ring > of all symmetric functions. As was pointed out, in characteristic 0 (or, > more generally anything larger than the degree) they are the same. In small > characteristic they are not. There are formulas for the index of the rings > (they're related to the theory of modular representations of the symmetric > group). > > Victor > > On Thu, Dec 3, 2009 at 12:13 PM, victor miller <victorsmiller@gmail.com>wrote: > > > > There are actually formulas which work in the "small" characteristic cases. > > In your case you'd need to look at tr(M^3). This is related to the > > decoding of BCH codes (where they work out the formulas in characteristic > > 2). > > > > Victor > > > > > > On Thu, Dec 3, 2009 at 12:09 PM, Eugene Salamin <gene_salamin@yahoo.com>wrote: > > > >> Because of the appearance of n! denominators, all this is true only in > >> characteristic zero. As a counterexample, let M be the 2x2 identity matrix > >> in characteristic 2. The charpoly is (x - 1)^2 = x^2 + 1. But tr(M) = > >> tr(M^2) = 0. > >> > >> -- Gene > >> > >> > >> > >> > >> ________________________________ > >> From: victor miller <victorsmiller@gmail.com> > >> To: math-fun <math-fun@mailman.xmission.com> > >> Sent: Thu, December 3, 2009 8:39:55 AM > >> Subject: Re: [math-fun] Expansion of charpoly's in terms of traces ? > >> > >> Yes, The key idea are the Newton Identities ( > >> http://en.wikipedia.org/wiki/Newton's_identities ), which give a way of > >> going from the power sums of the roots of a polynomial to the symmetric > >> functions of the roots. For matrices, the power sums of the eigenvalues > >> are > >> the the traces of the powers of the matrix, and the coefficients of the > >> characteristic polynomial are the symmetric functions of the roots (up to > >> sign). Note that it is only necessary to prove this formula when the > >> matrix > >> has all distinct eigenvalues because this set of matrices is Zariski dense > >> in the set of all matrices (i.e. if there is a polynomial equation giving > >> the characteristic polynomial in terms of the traces of the powers of the > >> matrix which holds for matrices with distinct eigenvalues, it must hold > >> for > >> all matrices). > >> > >> Victor > >> > >> On Thu, Dec 3, 2009 at 11:18 AM, Henry Baker <hbaker1@pipeline.com> > >> wrote: > >> > >> > I noticed in Wikipedia's description of eigenvalues, an expansion of the > >> > characteristic polynomial of a 3x3 matrix in terms of traces, so I > >> wanted to > >> > see if this worked more generally. > >> > > >> > For a 2x2 matrix, the charpoly is: > >> > > >> > x^2-x*tr(M)+det(A) = x^2-x*tr(M)+ (tr(M)^2-tr(M^2))/2 > >> > > >> > For a 3x3 matrix, the charpoly is: > >> > > >> > x^3-x^2*tr(M)+x*(tr(M)^2-tr(M^2))/2-det(M) = > >> > > >> > > >> x^3-x^2*tr(M)+x*(tr(M)^2-tr(M^2))/2-(tr(M)^3+2*tr(M^3)-3*tr(M)*tr(M^2))/6 > >> > > >> > For a 4x4 matrix, the charpoly is: > >> > > >> > > >> > > >> x^4-x^3*tr(M)+x^2*(tr(M)^2-tr(M^2))/2-x*(tr(M)^3+2*tr(M^3)-3*tr(M)*tr(M^2))/6+det(M) > >> > > >> > Notice that the higher order terms are the same form even though the > >> > dimension is higher. > >> > > >> > Can we continue this indefinitely? > >> > > >> > What is the general term? > >> > > >> > > >> > _______________________________________________ > >> > math-fun mailing list > >> > math-fun@mailman.xmission.com > >> > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > >> > > >> _______________________________________________ > >> math-fun mailing list > >> math-fun@mailman.xmission.com > >> http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > >> > >> > >> > >> > >> _______________________________________________ > >> math-fun mailing list > >> math-fun@mailman.xmission.com > >> http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > >> > > > > > _______________________________________________ > math-fun mailing list > math-fun@mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike http://reperiendi.wordpress.com
Quoting Henry Baker <hbaker1@pipeline.com>:
I noticed in Wikipedia's description of eigenvalues, an expansion of the characteristic polynomial of a 3x3 matrix in terms of traces, so I wanted to see if this worked more generally.
It looks like you may have noticed Newton's identities, and thereby Krylov's method of getting characteristic equations. Wikipedia, much less God, doesn't know everything. -hvm ------------------------------------------------- www.correo.unam.mx UNAMonos Comunicándonos
Actually, as Victor pointed out earlier, Wikipedia did know this, but in an obscure entry far from the discussion of matrices. It is not attributed to Krylov, however. http://en.wikipedia.org/wiki/Newton%27s_identities "The Newton identities now relate the traces of the powers A^k to the coefficients of the characteristic polynomial of A. Using them in reverse to express the elementary symmetric polynomials in terms of the power sums, they can be used to find the characteristic polynomial by computing only the powers A^k and their traces." At 11:43 AM 12/3/2009, mcintosh@servidor.unam.mx wrote:
Quoting Henry Baker <hbaker1@pipeline.com>:
I noticed in Wikipedia's description of eigenvalues, an expansion of the characteristic polynomial of a 3x3 matrix in terms of traces, so I wanted to see if this worked more generally.
It looks like you may have noticed Newton's identities, and thereby Krylov's method of getting characteristic equations.
Wikipedia, much less God, doesn't know everything.
-hvm
------------------------------------------------- www.correo.unam.mx UNAMonos Comunicándonos
participants (6)
-
Eugene Salamin -
Fred lunnon -
Henry Baker -
mcintosh＠servidor.unam.mx -
Mike Stay -
victor miller