Loading [MathJax]/jax/output/HTML-CSS/jax.js

Tuesday, July 30, 2013

Characteristic polynomial - 2: gen func vs matrix

I do not actually understand how it appears over and over again. But, I see two ways to get it. Suppose an equation an+1=3an+2. You can get an using generating functions.

In generating functions

Let 0anxn=a(x). Then, left hand turns into 0an+1xn=0an+1xn+1x=1anxnx=0anxna0x=(a(x)a0)/x and 2+2x+2x2+=20xn=21x.

That is, recurrence an+1=3an+2 turns into

a(x)a0x=3a(x)+21x

or

a(x)=113x(2x1x+a0)=a0+113x11x=(a0+1)03nxn0xn

which determines an=(a0+1)3n1.

Please note that we had characteristic polynomial (13x)(1x) in the denominator. The eignevalues are also obvious from the system graph:


Feedback s=3 exponentiates the node a while feedback s=1 keeps input 2 constant. But, though 2/(1x) comes up from the very beginning, we had to solve for a(x) for the second eigenvalue, 13x to appear in the equation.


As matrix eigenvalues


Alternatively, xn+1=3xn+2 can be written as a system

[x21]=[3201]=[x11]=s[x11]

The eigenvalues, s, can be found solving

|3s201s|=0=(3s)(1s)
yeilding two eigenvalues. With corresponding eigenvectors,  [10] and [11], we can form the eigenmatrix S=[1101] and its inverse S1=[1101]. This allows to compute n-th vector quickly:

[xn1]=Xn=[3201]nX0=SΛnS1X0=

=[1101][3n001n][1101]X0=[3n3n101n][x01]

 This gives the same result, xn=x03n+3n1=(x0+1)3n1 you've seen above.

This time, characteristic polynomial appeared because of AλI matrix determinant.


Analysys

In either case we have obtained an=(a0+1)3n1n. This corresponds to the idea that solution is a combination of eigenvalues, xn=x01λn1+x02λn2+, similarly to n-th order matrix, xn=Anx0=An[x01e1+x02e2+]= =x01λn1e1+x02λn2e2+=SΛnS1x0.  . I've used x0i for coefficients in order to highlight that they are determined by initial value). The polynomials are not exactly equal, though.  The polynomial (1-3x)(1-x), which appears in the denominator of generating function a(x)is not equal to the determinant of the matrix, (3−s)(1−s). The roots x, 1/3 and 1, are reciprocal of the real eigenvalues s = 3 and 1.  The coefficients  next to x are the  eigenvalues. GENERATING FUNCTIONS by MIGUEL A. LERMA  calls the (1-3x)(1-x) = 1-4x+3x² a reciprocal of the characteristic polynomial 3-4s+2s². The reference is worth to read because it provides a way of spotting the sequence an generating function instead of building it. The reciprocal polynomials are also called (clique or dependence polynomials) You get it by (3-4s+2s²)x² = (3-4x⁻¹+2x⁻²)x² = 3x²-4x¹+2.

If the characteristic polynomial is a determinant of the matrix |A-sI|, the reciprocal polynomial is determinant of the matrix |I-xA|.

No comments: