fredholms first minor R2

Fredholm's First Minor, Round 2 PhL 3.28.09 1. Preliminaries from Integral Equation Theory 1 2. Definition of Fredholm's First Minor 1 3. Attempting the Direct Method for finding Nij 3 4. Using a recursion method to "discover" the nature of the Nij series 5 5. An Induction Proof of the Nij series 7 6. A restatement of the correct series for Nij 11 This first section is a repeat of what appears at the start of Fredholm Determinant Round 2. 1. Preliminaries from Integral Equation Theory Our Neumann form integral equation is this φ = f + λKφ and the solution can be expressed in this manner: φ = (1 - λK)-1f. = (1 + λK + λ2K2 + ....) f = f + Σm=1λmKm f = (1 + Γ) f All we did was use the high school algebra formula for 1/(1-x) as a series, and then defined this object Γ = Σm=1λmKm = "the resolvent" The first few terms here are Γ ≈ λK + λ2K2 so if λ<<1, we have Γ ≈ λK so Γ is of order λ in general. In all this, I like to think of K as a finite dimensional matrix and take the ∞ limit later on. So the object Km is just the product of K matrices multiplied together. Looking at the above, we of course have φ = f + Γf (1 - λK)-1 = 1 + Γ from which last we quickly conclude that Γ = λK + λKΓ = λK + λΓK We also know the following fact from very elementary matrix theory, (1 - λK)-1 = [ cof (1-λK) ]T /det( 1 - λK) = 1 + Γ 2. Definition of Fredholm's First Minor In the previous section we found that the resolvent can be written as: Γ = (1 - λK)-1 - 1 = [ cof (1-λK) ]T /det( 1 - λK) - 1 which we regard as a matrix equation with these matrix elements Γij = (1 - λK)-1ij - δi,j = [cof (1-λK)]ji /det( 1 - λK) - δi,j The RHS of this equation can be written as { [cof (1-λK)]ji - det( 1 - λK) δi,j } / det(1-λK) and it is traditional to define the quantity in {..} as Nij, Nij ≡ [cof (1-λK)]ji - det( 1 - λK) δi,j Thus, we have Γij = Nij / det(1-λK) or [Γij/λ] = [Nij/λ] / det(1-λK) (*) We now assign these names: [Nij/λ] ≡ Fredholm's First Minor, det(1-λK) ≡ The Fredholm Determinant. There may be some ambiguity in the definition of the resolvent. Here are two choices Γij = "the resolvent" and is order λ1 Γij/λ = "the resolvent" and is order λ0 In the continuum notation we rewrite (*) as [Γ(x,y;λ) /λ] = [N(x,y;λ) /λ]/ det(1-λK) where the fact that Γ and N depend on λ is shown explicitly. A standard notation people use is this: D1(x,y; λ) ≡ [N(x,y;λ) /λ] Fredholm's First Minor (some people erroneously drop /λ) D(λ) ≡ det(1-λK) The Fredholm Determinant and then the resolvent is given as Γ(x,y;λ) /λ = D1(x,y; λ)/ D(λ) // some people erroneously drop /λ So, if we know D1 and D, then we know the resolvent and our integral equation is solved according to φ = f + Γf as shown in Section 1 above. Note Added: We shall learn below that Nij = λKij – λ2 Σk detik;jk + (λ3/2!) Σab detiab;jab - ... => [Nij/λ] = Kij – λ Σk detik;jk + (λ2/2!) Σab detiab;jab - ... We already saw in Section 1 that Γij ≈ λKij for λ << 1 and of course det(1-λK) ≈ 1. Thus, our equation above [Γij/λ] = [Nij/λ] / det(1-λK) becomes Kij ≈ Kij. This is just to show that we have all our λ's in the right place. Then D1 and D are order λ0 and that is why D1 is defined as it is. We already have an expansion for D(λ) as a power series in λ which is useful in problems when λ is small. That expansion is this (we are now back in matrix notation for a long time) D(λ) = det( 1 - λK) = 1 + Σn=1N (-λ)n /n! Σi1,i2,i3... in=1N deti1 i2 i3...in which is derived in our document on Fredholm Determinant, Version 2. Our goal is to find a corresponding power series expansion for D1(x,y; λ) which, in matrix notation, means we need a power series expansion in λ for Nij . At first glance, this does not seem an immensely hard problem. We have Nij = [cof (1-λK)]ji - det( 1 - λK) δi,j 3. Attempting the Direct Method for finding Nij Our problem is simply to write Nij as a power series in λ, where Nij = [cof (1-λK)]ji - det( 1 - λK) δi,j It turns out that finding this power series in λ is a much harder problem than one would think. In our document on subdeterminants of a matrix, we know that [cof (1-λK)]ji = (-1)i+j minor(1-λK)ji = (-1)i+j detrows≠j;cols≠i where the det notation is the N-1 x N-1 subdeterminant you get by crossing out row j and column i. It is convenient at this point to set -λK = B and then when we are done we can replace B by -λK to get our result. Thus, we are interested in Nij = [cof (1+B)]ji - det(1+B) δi,j [cof (1+B)]ji = (-1)i+j minor(1+B)ji = (-1)i+j detrows≠j;cols≠i where detrows≠j;cols≠i is the N-1 x N-1 subdeterminant of the matrix (1+B) where we have crossed out row j and column i. We assume of course that B is an NxN matrix. It would seem that all we have to do is compute things like: " all terms in detrows≠j;cols≠i which are of order Bn " that is, all terms which have n factors of Bab in them, since these would become λn terms in our power series expansion. With a large amount of painful effort, I was able to show that, if we write minor(1+B)ji = detrows≠j;cols≠i = B0 term + B1 terms + ( B2 and higher terms), then we get B0 term: δi,j B1 terms: {Bj,i (-1)i+j+1}(1 - δi,j) + { tr(B) - Bii}δi,j = tr(B) δi,j – (-1)i+j Bj,i Meanwhile, if we expand det(1+B) and keep only terms of B0 and B1 order we get det(1+B) ≈ 1 + tr(B) as we well know by now. Using all this information we find that Nij = [cof (1+B)]ji - det(1+B) δi,j = (-1)i+j minor(1+B)ji - det(1+B) δi,j ≈ (-1)i+j { δi,j + tr(B) δi,j – (-1)i+j Bj,i } - {1 + tr(B)} δi,j = -Bik So the reward we get from all this work is this: Nij = – Bij + order(B2) and higher. One might wonder why these calculations are so hard (as claimed by your friendly writer). It seems to relate to the difficulty of dealing with detrows≠j;cols≠i where the set "rows" is all integers 1 to N except the integer j, and "cols" is all integers 1 to N except the integer i. For each case of j and i, it almost seems to be a completely separate problem you have to go ponder. For example, consider: N = 6 j = 2 i = 4 want to know: det13456; 12356 We can use our general formula for subdeterminants which says detrows;cols = detr1 r2..rn; c1 c2..cn = Σi1,i2,..in {c1 c2 ..cn} (1+B)r1,i1 (1+B)r2,i2 (1+B)r3,i3... (1+B)rn,in εi1 i2 ..in with εc1 c2 ..cn = 1 and rows,cols both assumed to be in natural order This is not a "diagonal" subdeterminant as we encountered with the Fredholm Determinant. So we write this out as det13456; 12356 = Σi1,i2,..i5 {12356} (1+B)1,i1 (1+B)3,i2 (1+B)4,i3... (1+B)6,i5 εi1 i2 ..i5 with ε12356 = 1 Then we have to partition all the terms into B0 and B1 and B2 and B3 and so on, which is a similar problem to what we faced in the Fredholm determinant situation, but worse since things are non-diagonal. Even if we do all this work, we have only obtained results for the N42. I hope the reader is at least convinced it is a messy approach. There is a better way. The problem is that the above method deals with the scalar object Nij and we really need a method that deals with N as a matrix entity. 4. Using a recursion method to "discover" the nature of the Nij series We know from our earlier work above (see Sections 1 and 2) that N = det(1-λK) Γ = det(1-λK) (Γ + 1) - det(1-λK) = det(1-λK) (1-λK)-1 - det(1-λK) Therefore [ N + det(1-λK) ] (1-λK) = det(1-λK) N - λNK + det(1-λK) (1-λK) = det(1-λK) N - λNK - det(1-λK)λK = 0 This says that N must satisfy the above matrix equation. Let's write our series solution as N = Σn=0M(n)λn where the M(n) are matrices. We then get ΣnM(n)λn – λK det(1-λK) – ΣnM(n)λn+1K = 0 or Σn=0M(n)λn – λK { Σn=0N (-λ)n /n! Σi1,i2,i3... in=1N deti1 i2 i3...in } – Σn=0M(n)λn+1K = 0 Rewrite the first sum as Σm=-1 M(m+1)λm+1 = Σn=-1 M(n+1)λn+1 = M(0) + Σn=0 M(n+1)λn+1 . Then we can combine the three sums on n to get M(0) + Σn=0 λn+1 { M(n+1) – (-1)n/n! Σi1,i2,i3... in=1N deti1 i2 i3...in K– M(n)K} = 0 This tells us that M(0) = 0 and that we have this recursion relation M(n+1) = M(n)K + (-1)n/n! * Σi1,i2,i3... in=1N deti1 i2 i3...in K For n = 0 this says: M(1) = M(0)K + 1 K = 0K + K = K For n =1 we then get M(2) = M(1)K – Σi1=1N deti1 = M(1)K – K tr(K) = K2 – Ktr(K) which says M(2)ij = (K2)ij - Kij tr(K) = Σk KikKkj - Kij Σk Kkk = Σk{ KikKkj – Kij Kkk } = – Σk detik;jk Thus, we have already found the first three terms of our series Nij = Σn=0M(n)ij λn = λ0 0 + λ1Kij – λ2 Σk detik;jk For n = 2 we get M(3) = M(2)K + (-1)2/2! Σi1,i2=1N deti1 i2 K M(3)ij = ΣkM(2)ikKkj + (1/2) Σi1,i2=1N deti1 i2 Kij = – Σk Σa detia;ka Kkj + (1/2)Σi1,i2=1N deti1 i2 Kij = – Σab detia;ba Kbj + (1/2) Σab detab;ab Kij Now anticipating the result, let's consider detiab;jab . If we "expand this going down the first column" we get the following: ( later we present a general formula for writing out this expansion) detiab;jab = Kij detab;ab – Kajdetib;ab + Kbj detia;ab If we now sum this on ab, the last two terms turn out to be equal and we get Σab detiab;jab = Kij Σab detab;ab - 2! Σab detib;abKaj which we can solve to get Kij Σab detab;ab = Σab detiab;jab + 2! Σab detib;abKaj Therefore from above we have M(3)ij = – Σab detia;ba Kbj + (1/2)Σab detab;ab Kij = – Σab detia;ba Kbj + (1/2)Σab detiab;jab + Σab detib;abKaj = – Σab detib;ab Kaj + (1/2) Σab detiab;jab + Σab detib;abKaj = (1/2) Σab detiab;jab Thus our series so far is Nij = Σn=0 λn M(n)ij = λKij – λ2 Σk detik;jk + (λ3/2!) Σab detiab;jab - ... This leads us to conjecture that the full series is this: Nij/λ = Kij – λ Σk detik;jk + (λ2/2!) Σab detiab;jab – (λ3/3!) Σabc detiabc;jabc + ... = Kij + Σn=1∞ (-λ)n/ n! * [ Σk1,k2...kn deti k1 k2...kn ; j k1 k2...kn ] This is of course the correct known result. But if we did not know the correct result, this recursion method would have led us to the correct result. The general formula for M(n)ij must be M(3)ij = (1/2) Σab detiab;jab = (1/2!) Σk1,k2 deti k1 k2;j k1 k2 M(n+1)ij = (-1)n/n! * [ Σk1,k2...kn deti k1 k2...kn ; j k1 k2...kn ] or M(n)ij = (-1)n-1/(n-1)! * [ Σk1,k2...kn-1 deti k1 k2...kn-1 ; j k1 k2...kn-1 ] 5. An Induction Proof of the Nij series We can now show "by induction" that our conjectured series is indeed correct.. Assume that the above is true for n; M(n)ij = (-1)n-1/(n-1)! * [ Σk1,k2...kn-1 deti k1 k2...kn-1 ; j k1 k2...kn-1 ] We have our recursion relation as follows: M(n+1) = M(n)K + (-1)n/n! * Σi1,i2,i3... in=1N deti1 i2 i3...in K which we first rewrite showing matrix elements, and then we install M(n)ij from above with j=k: M(n+1)ij = Σk {M(n)ik}Kkj + (-1)n/n! * Σi1,i2,i3... in in=1N deti1 i2 i3...in in Kij = Σk { (-1)n-1/(n-1)! * [ Σk1,k2...kn-1 deti k1 k2...kn-1 ; k k1 k2...kn-1 ]} Kkj + (-1)n/n! * Σi1,i2,i3... in=1N deti1 i2 i3...in Kij = { (-1)n/n!* Σk [ – n Σk1,k2...kn-1 deti k1 k2...kn-1 ; k k1 k2...kn-1 ]} Kkj + (-1)n/n! * Σi1,i2,i3... in =1N deti1 i2 i3...in Kij The desired induction result is this (copying from end of previous section) M(n+1)ij = (-1)n/n! * [ Σk1,k2...kn deti k1 k2...kn ; j k1 k2...kn ] We conclude our induction proof of the general form of the series if we can show that [ Σk1,k2...kn deti k1 k2...kn ; j k1 k2...kn ] = Σk [ – n Σk1,k2...kn-1 deti k1 k2...kn-1 ; k k1 k2...kn-1 ] Kkj + Σi1,i2... in deti1 i2...in Kij (*) As we did in one of our lower terms above, we need to do a "first column expansion" of this determinant: deti k1 k2...kn ; j k1 k2...kn We now write down some general rules for doing one of these expansions: First column expansion theorem rules: (1) alternate signs as usual (2) the Kab factors are as follows: first index sequences through row group, second index is always first of col group (3) on the new dets, the col group is always the same: last of the original col group. (4) on the new dets, the row group is obtained by deleting, one at a time, one digit from the original row group. So here we go, deti k1 k2...kn ; j k1 k2...kn = Kij det k1 k2...kn ; k1 k2...kn + other terms Let's ignore the "other terms" for the moment. If we apply Σk1,k2...kn to both sides of this equation we immediately generate our desired term (*) above, which I now rewrite as + Σi1,i2... in deti1 i2...in; i1 i2...in Kij (*) where I expand the notation for the "diagonal" subdeterminants. Therefore, now we have only to show that: Σk1,k2...kn (other terms) = -n Σk [ Σk1,k2...kn-1 deti k1 k2...kn-1 ; k k1 k2...kn-1 ] Kkj (**) If we can show this, our induction proof is complete. Using our "first column expansion rules" , First column expansion theorem rules: (1) alternate signs as usual (2) the Kab factors are as follows: first index sequences through row group, second index is always first of col group (3) on the new dets, the col group is always the same: last of the original col group. (4) on the new dets, the row group is obtained by deleting, one at a time, one digit from the original row group, we now write out these "other terms". We assume that n is some large integer, and we will write out the first 5 of the "other terms" with the understanding that there are really n "other terms". This will clearly show the pattern that develops. So: deti k1 k2...kn ; j k1 k2...kn - Kk1,j det i ** k2 k3 k4 k5...kn ; k1 k2 k3...kn 1 + Kk2,j det i k1 ** k3 k4 k5...kn ; k1 k2 k3...kn 2 - Kk3,j det i k1 k2 ** k4 k5...kn ; k1 k2 k3...kn 3 + Kk4,j det i k1 k2 k3 ** k5...kn ; k1 k2 k3...kn 4 - Kk5,j det i k1 k2 k3 k4 **...kn ; k1 k2 k3...kn 5 Each term has a complete summation Σk1 k2 k3....kn but we are suppressing this summation symbol. We mark the "deleted" row group index with **. To verify the above list, the reader will have to read the column expansion rules above. Remember that we are not writing the very first term in the expansion because we have already dealt with it. Now let's swap two k summation indices on each of lines 2,3,4,5 such that the leading K factor is always Kk1,j . Then just rewrite: deti k1 k2...kn ; j k1 k2...kn What we did - Kk1,j det i ** k2 k3 k4 k5...kn ; k1 k2 k3 k4 k5...kn 1 + Kk1,j det i k2 ** k3 k4 k5...kn ; k2 k1 k3 k4 k5...kn 2 2 ↔ 1 - Kk1,j det i k3 k2 ** k4 k5...kn ; k3 k2 k1 k4 k5...kn 3 3 ↔ 1 + Kk1,j det i k4 k2 k3 ** k5...kn ; k4 k2 k3 k1 k5...kn 4 4 ↔ 1 - Kk1,j det i k5 k2 k3 k4 **...kn ; k5 k2 k3 k4 k1...kn 5 5 ↔ 1 Notice that these swaps affect both the row group and the column group. In the column group we actually do a swap. In the row group, one of the two swapees is missing, so we just do 1→2, 1→3 etc. so it is only the first k index of the row group that is affected. At this point we are still free to relabel the summation indices k2,k3...kn any way we want. So let's do that now: deti k1 k2...kn ; j k1 k2...kn line # What we did - Kk1,j det i ** k2 k3 k4 k5...kn ; k1 k2 k3 k4 k5...kn 1 + Kk1,j det i k2 ** k3 k4 k5...kn ; k2 k1 k3 k4 k5...kn 2 nothing - Kk1,j det i k2 k3 ** k4 k5...kn ; k2 k3 k1 k4 k5...kn 3 k2,k3→k3.k2 + Kk1,j det i k2 k3 k4 ** k5...kn ; k2 k3 k4 k1 k5...kn 4 k4,k2,k3→ k2,k3,k4 - Kk1,j det i k2 k3 k4 k5 **...kn ; k2 k3 k4 k5 k1...kn 5 5,2,3,4 → 2,3,4,5 At this point, the row groups are all the same! To make the column groups the same, we have to shift k1 to the left a number of places equal to line number - 1. The even numbered lines like 2 and 4 pick up a minus sign because we do an odd number of adjacent swaps to achieve the required shift. The odd numbered lines maintain their sign. Doing this, we get deti k1 k2...kn ; j k1 k2...kn line # - Kk1,j det i ** k2 k3 k4 k5...kn ; k1 k2 k3 k4 k5...kn 1 – Kk1,j det i k2 ** k3 k4 k5...kn ; k1 k2 k3 k4 k5...kn 2 - Kk1,j det i k2 k3 ** k4 k5...kn ; k1 k2 k3 k4 k5...kn 3 - Kk1,j det i k2 k3 k4 ** k5...kn ; k1 k2 k3 k4 k5...kn 4 - Kk1,j det i k2 k3 k4 k5 **...kn ; k1 k2 k3 k4 k5...kn 5 Now all lines are exactly the same!!! It seems pretty clear that this proof method extends to however many "lines" there are when we do our column expansion. In our example here our starting subdeterminant dimension was n+1 so there will be n "lines" which are all equal. Thus we can just represent all these lines as n times the first line. So, deti k1 k2...kn ; j k1 k2...kn // "other terms" part = - n * Kk1,j deti k2 k3...kn; k1 k2 k3...kn Remember that this has the implied summation Σk1 k2 k3....kn . Let's now rename these dummy summation indices as follows: k1 k2 k3....kn → k k1 k2....kn-1 so the above becomes: = - n * Σk k1 k2....kn-1 Kk,j deti k1 k2...kn-1; k k1 k2...kn-1 But this is seen to exactly match (**) above, so that concludes this somewhat gory induction proof! We have thus proven that the correct series for Nij is this: [Nij/λ] = Kij – λ Σk detik;jk + (λ2/2!) Σab detiab;jab – (λ3/3!) Σabc detiabc;jabc + ... = Kij + Σn=1∞ (-λ)n/ n! * [ Σk1,k2...kn deti k1 k2...kn ; j k1 k2...kn ] 6. A restatement of the correct series for Nij We have already proven the formula above for the correct series Nij in terms of K. Here I will first write this solution series in terms of B = -λK, then return later to K. Here is the solution to our problem, where we assume that B is NxN : – Nij = – [cof (1+B)]ji + det(1+B) δi,j = Bij + Σk detik;jk + (1/2!) Σkm detikm;jkm + (1/3!) Σkmn detikmn;jkmn + etc = Bij + Σn=1N-1 1/ n! * [ Σk1,k2...kn deti k1 k2...kn ; j k1 k2...kn ] where the det objects appearing here are standard subdeterminants of the B matrix as we discussed in our separate document on subdeterminants. You can see that at least I got the first term right in my painful manual analysis of the B0 and B1 terms. This is certainly faint praise, since most of the interest lies in the remaining terms. We can now set B = -λK as discussed above to get the actual power series result of interest. Note that deti k1 k2...kn ; j k1 k2...kn is order Bn+1 so we are going to get -Nij = -λKij + Σn=1∞ (-λ)n+1/ n! * [ Σk1,k2...kn deti k1 k2...kn ; j k1 k2...kn ] where now the dets are of K, not B. We can rewrite this as (and this is what we proved above) [Nij/λ] = Kij + Σn=1∞ (-λ)n/ n! * [ Σk1,k2...kn deti k1 k2...kn ; j k1 k2...kn ] and the thing on the right is then the Fredholm's First minor expansion D1ij(λ). We can write this out in graphical notation as [Nij/λ] = Kij – λΣk + (λ2/2!) Σkm – (λ3/3!) Σkmn +. detik;jk detikm;jkm detikmn;jkmn You can see the "economy" of the det notation compared to writing everything out, where you can easily make an index error. In the continuum sense we would write this as D1(x,y;λ) = k(x,y) + Σn=1∞ (-λ)n/ n! * ∫ds1ds2..dsn detx s1 s2...sn; y s1 s2 ...sn = k(x,y) – λ∫ds1 + (λ2/2!) ∫ds1ds2 – ... detx s1; y s1 detx s1 s2; y s1 s2 Here is how this result appears in one book: = detx1 x2...xn; y1 y2 ...yn This author uses a capital K for the kernel function whereas I use lower case k.