18 312 Algebraic Combinatorics Lionel Levine Lecture 5 Lecture date Feb 15 2011 1 Notes by David Witmer Stirling inverse matrices From last class we have the following proposition Proposition 1 n X S n k s k j nj k 0 where S n k are Stirling numbers of the second kind s k j are signed Stirling numbers of the first kind such that s k j 1 k j c k j and nj 1 0 if n j otherwise Example 2 Consider the n 4 case in which S and s are 4 4 matrices S 1 1 1 1 1 0 1 3 7 0 0 1 6 1 0 1 0 0 0 1 1 0 2 3 1 0 1 6 11 6 0 0 s 0 1 Proof Recall these two facts from last class Fact 3 n X c n k xk x x 1 x n 1 k 0 Fact 4 n X S n k x x 1 x k 1 xn k 0 5 1 First we will find an expression analagous to fact 3 in terms of signed Stirling numbers of the first kind n X s n k xk k 0 n X 1 n k c n k xk k 0 1 n n X c n k x k k 0 1 n x x 1 x n 1 x x 1 x n 1 by fact 3 since we have one 1 per factor Now let vector space Vn polynomials in x of degree n with constant term 0 Consider two bases for Vn ei xi and fi x x 1 x i 1 for i from 1 to n Define L Vn Vn to be the linear operator such that L ei fi From above we know that fi i X s i k ek k 0 so the matrix of L in the basis e1 en is s i k ni k 1 Then by fact 4 the matrix of L 1 in the basis f1 fn is S n k ni k 1 That is n X S n k fk ek k 0 Substituting in for fk we get n X S n k n X s k j ej en j 0 k 0 Rearranging we get n n X X j 0 S n k s k j ej en k 0 5 2 Therefore n X S n k s k j nj k 0 2 2 Linear recurrences Recall the following example from last class Example 5 The Fibonacci sequence is defined by the recurrence Fn 2 Fn 1 Fn for n 1 with F1 1 and F2 1 We can write this recurrence in terms of the shift operator E as E 2 E 1 F 0 Factoring we see that E E 0 where 1 5 1 5 1 618 and 0 618 2 2 We can then write Fn a n b n Using the initial conditions F1 F2 1 we find that a 1 5 and b 15 so 1 Fn n n 5 Since n rapidly becomes very small we can say that n Fn 5 For instance F10 55 and 10 5 55 0036 Now we wish to generalize these results We wish to work over an algebraically closed field so we can factor We will use C 5 3 Definition 6 A sequence s s0 s1 s2 C obeys a linear recurrence of order k if there exist a0 a1 ak 1 C such that k 1 X sn k ai sn i i 0 for all n 0 We can therefore write linear recurrences in the form p E s 0 where p is a polynomial in C x of degree k Definition 7 Suppose p factors as p E E 1 E k where 1 k are distinct complex numbers Then s satisfies a simple linear recurrence Theorem 8 The sequence s satisfies the simple linear recurrence p E s 0 if and only if there exist c1 ck C such that sn c1 n1 ck nk That is sn can be expressed as a linear combination of exponential sequences Proof p E C C is a linear operator ker p E s p E s 0 is a subspace i of C Let en ni We want to show that e 1 e k form a basis for ker p E First we need to show that e i ker p E The e i s are eigenvectors of the shift operator i Ee i n en 1 n 1 i ni i e i n i Thus Ee i i e i so e i is an eigenvector of E with eigenvalue i This means that e i ker E i or E i e i 0 Since multiplication commutes we can write p E q E E i for some polynomial q Then we have that p E e i q E E i e i q E 0 0 so e i ker p E 5 4 Next we show that e 1 e k are linearly independent Consider 1 1 1 k 2 i 2k 1 det ej k k 1 det i 1 j 0 k 1 k 1 1 k This is the Vandermonde determinant so we see that Y i det ej k k 1 i j i 1 j 0 i j Since we are dealing with a simple linear recurrence all roots of p must be distinct so this determinant is nonzero This means that there is no linear dependence among the first k terms of the sequences so there is no linear dependence among the sequences Therefore e 1 e k are linearly independent Finally to show that e 1 e k form a basis we need to show that dim ker p E k A sequence s ker p E is determined by its first k terms s0 sk 1 since all subsequent i terms sk sk 1 are determinted by the recurrence Let fj ij for 1 i j k Then f 1 f k form a basis of size k All bases of ker p E must have the same cardinality Therefore e 1 e k form a basis for ker p E 2 Example 9 The sequence sn 3n 2n obeys a linear recurrence Let 1 3 and 2 2 Then p E E 3 E 2 E 2 5E 6 so our recurrence is sn 2 5sn 1 6sn 0 What if p E has repeated roots Example 10 Consider the sequence s such that sn 3 3sn 2 3sn 1 sn Then p E E 3 3E 2 3E 1 E 1 3 D3 where D E 1 is the difference operator One solution is sn 1n 1 However we expect to have two other linearly independent solutions since this a linear recurrence of order 3 These two additional solutions are sn n and sn n2 5 5 D is analagous to the operator to this recurrence is d dt for functions so the corresponding differential equation d dt …