the Sneddon matrix problem

The Sneddon Matrix Problem PhL 12.12.10 In his Chapter 4, Sneddon presents a method of solving dual integral equations which I have interpreted in terms of matrix linear algebra. As outlined in the meta notes for that chapter, the key idea is this claim: 1. The Problem Given two invertible matrices S1 and S2 , it is possible to find two triangular matrices I and K such that IS1 = KS2 ≡ S and matrix S will be invertible. Matrix K is upper triangular and I is lower triangular. The problem is to show that the claim is true, and to come up with the matrices I and K to make it work. 2. Matrix Decomposition Forms After some initial attempts to solve this little problem, I decided it better to review matrix theorems which might be relevant. I have some notes on triangular matrices on page 3 of section 7 of my matrix binder, but the notes don't clearly state the theorems they are about, so here is a web shot: (1) First, here is the LU decomposition idea: There are slightly obscure conditions on matrix A such that LU exists (quoted later in this doc). (2) The next idea is this: (3) A third idea is this: Wiki on permutation matrices notes that P-1 = PT which is just some other permutation matrix, so you could write A = PLU But it turns out you can also say (as a general form) A = LUP Here are comments from another wiki location: This claims that every square matrix A has an LUP (but may not have an LU). I think I could prove these claims using my notes. 3. Do these decompositions help me solve my problem? IS1 = KS2 ≡ S Let's reframe the problem with different symbols: LA = UB ≡ C where L and U of course mean upper and lower triangular, and A and B are invertible. Given A and B, we are supposed to find L and U such that LA = UB. So we could write A = LaUaPa B = LbUbPb C = LcUcPc We know the Xa matrices, we don't know the Xc matrices or L and U. But let's make the ansatz that matrix C exists such that LA = UB ≡ C, and see where that leads us. We have three basic unknowns in our problem: L, U, C. And we have already listed all usable information except A and B are invertible. Fact A: If we knew U, we could compute L as follows (and vice versa on the right) L = UBA-1 U = LAB-1 All we know about BA-1 is that it is some invertible matrix, maybe call that M. Then we have L = UM U = LN The claim is that, given any invertible M, you can find a U that converts M to an L. That seems rather amazing. And similarly for U = LN. If we wrote out N we can then say U = L LnUnPn = Ln'UnPn Using the LUP decomposition does not seem very useful here. So consider U = LN by brute force U = LN Uij = Σk=1n LikNkj (*) This is n2 equations which involve the 2n2 unknowns Uij and Lik. But we have more information: Uij = 0 if i > j Lij = 0 if i < j So from (*) we may write 0 = Σk=1n LikNkj for i > j But since L is triangular as well, the sum is only partial and we can write 0 = Σk=1i LikNkj for i > j (**) We are trying to find Lik to make this work. Aside: The number of off diagonal elements in a square matrix is n2-n, so each side has n(n-1)/2 elements. Thus, a triangular matrix has (n2-n)/2 + n = n2/2 + n/2 = n(n+1)/2 elements. In (**), matrix Lik has n(n+1)/2 elements (all unknowns). How many equations do we have in (**)? We have one equation for each pair i,j such that i>j. That number must be the same as the number of elements on a side, which is n(n-1)/2. Thus, we have n(n-1)/2 equations in n(n+1)/2 unknowns, and the difference is n, so we should be able to arbitrarily set n elements of Lik and then find the other elements from these equations. That is to say, we are underdetermined by n degrees of freedom. So why not set all the diagonal elements of Lik to 1, that would soak up our degrees of freedom. OK, suppose this works and we make L have ones on the diagonal. Then, given N, we have found a matrix L such that LN is upper triangular: U = LN Since we have 1's on the diagonal, we know that L-1 exists, so we can write L-1U = N I am pretty sure that the inverse of a triangular matrix is a triangular matrix of the same type, but might not have one's on the diagonal, so let's call L-1 = L'. Then we have L'U = N This seems to claim that ANY matrix N can be written as an LU decomposition, so we have somewhere lost our condition! Maybe our set of simultaneous equations cannot be solved in certain situations. Go back to these equations. After we set 1's on the diagonals, we have n(n-1)/2 equations in the same number of unknowns. But in a Cramer's Rule sense, every one of these equations has 0 for the RHS. 0 = Σk=1i LikNkj for i > j (**) What do these equations look like ? Suppose n = 3 to be concrete. Then we have i > j 2 > 1 0 = L21N11 + L22N21 3 > 1 0 = L31N11 + L32N21+ L33N31 3 > 2 0 = L31N12 + L32N22 + L33N32 Our L matrix has 32 = 9 elements in general, but since triangular, only has 6 non-zero elements. Of these, only 5 appear in our equations, L11 does not appear. If we set the diagonals to 1 we get 2 > 1 0 = L21N11 + N21 3 > 1 0 = L31N11 + L32N21+ N31 3 > 2 0 = L31N12 + L32N22 + N32 So here we have 3 equations in 3 unknowns which are L21 , L31 and L32. Rewrite as N11 L21 = -N21 L31N11 + L32N21 = -N31 L31N12 + L32N22 = -N32 = The matrix on the left we can call S. We need detS ≠ 0 to have our solution. But this says N11 det ≠ 0 If N11 = 0 we cannot solve except: if N21 happens to be 0, then any L21 is OK. 4. Restate what we think we have shown. Matrices A and B are invertible, and we want to find L and U such that LA = UB Rewrite this as U = L(AB-1) U = LN where N = AB-1 is an invertible matrix. Assume for the moment that L is invertible, so we can write L'U = N where L' = L-1 Now assume further that we set the diagonal elements of L' all to one. This L' will be invertible for sure, and its inverse is our L. Now, as long as N is a "reasonable" matrix, it has a unique L'U decomposition where L' has unit diagonal elements, You see here stated what I mean by "reasonable": principle minors are all non-zero. This is not necessarily true for an invertible matrix, where all we know is that a certain sum of these minors is not zero, so this condition is more stringent than the condition of just being invertible. So here is how we solve our problem: (1) write out AB-1 in the unique decomposition AB-1 = L'U where L' has ones on the diagonal. Just assume that AB-1 is a "reasonable" matrix and therefore has such a decomposition. (2) We know that L' is invertible into another L-type matrix, so write L'-1 = L which defines L. We then have U and L such that LAB-1 = U But this then says LA = UB and that is the problem we were trying to solve. U is the unique U that arises in the decomposition AB-1 = L'U, and L is L'-1. (3) Question: is the resulting matrix C invertible? C = LA C-1 = (LA)-1 = A-1L-1 = A-1L'. Yes it is! (4) Now, to complete our little picture, suppose you had [AΨ]1 = f1 [BΨ]2 = g2 where 1 and 2 now refer to some simple partition of the index range i = 1..n. These are our "dual integral equations". We have f = (f1,f2) and similarly for g, so we know that in the full matrix sense AΨ = f BΨ = g but we don't know Ψ or f2 or g1. The trick then is to make use of our solution LA = UB. Apply L to the first and U to the second: LAΨ = Lf UBΨ = Ug Which we can write as CΨ = Lf CΨ = Ug Now we know that Lf = = => [C Ψ]1 = L11 f1 Ug = = => [C Ψ]2 = U22 g2 Putting there two pieces together, we get CΨ = But we know f1 and g2 and we know L and U, so the RHS is completely known. Then Ψ = C-1 and so Ψ is then known. But then AΨ = f BΨ = g and we know A,B and Ψ, so we know f and g which means we know f2 and g1. All done! 5. What happens when we take the matrix dimension to be infinite? Somehow, when we go to the continuum, our matrix AB-1 = N must come out being "reasonable" all the time. Matrices A and B are modified Hankel transforms, Sη,α { f(r); μ } = 2α μ-α !Syntax Error, Idx x1-α J2η+α(μx) f(x) and matrix U=K and L=I are certain Erdelyi-Kober transforms Iη,α F(x) = 2 / Γ(α) * x-2α-2η !Syntax Error, Idt t2η+1F(t) [x2 - t2] α-1 Kη,αF(x) = 2 / Γ(α) * x2η !Syntax Error, Idt t-2η-2α+1F(t) [t2 - x2] α-1 which are diagonal due to their Volterra endpoints. To be a little more specific, we have the following infinite dimensional matrices: Aμx = [Sη,α]μx = 2α μ-α x1-α J2η+α(μx) = [S1]μx α,η = α1, η1 Bμx = [Sη,α]μx = 2α μ-α x1-α J2η+α(μx) = [S2]μx α,η = α2, η2 Uxt = [Kη,α]xt = 2 / Γ(α) * x2η t-2η-2α+1[t2 - x2] α-1 θ(t-x) α,η = αK, ηK Lxt = [Iη,α]xt = 2 / Γ(α) * x2η t-2η-2α+1[t2 - x2] α-1 θ(t-x) α,η = αI, ηI We are given the first two A and B, and we have shown in our finite stuff above that U and L can be found and are not really unique. Sneddon produces certain K and I which are candidates for U and L and he shows that these candidates have the proper triangularity and in fact work in the sense IS1 = KS2. Notice that in general all four sets of α,η labels will be different, and that these things are NOT the matrix indices, so don't confuse that!