Archive

Archive for March, 2011

On Eigen(patch(ix))values, II - (RWLA,MCT,GT,AM Part IX)

March 22nd, 2011 No comments

So remember my little conjecture from last time, that the number of patch(ix) (kernel) eigenvalues would depend on the number of x terms that composed it?  I started working it out by writing all expressions and trying to substitute them and I got sums of sums of sums and it became nightmarish, and since math is supposed to be elegant, I opted for a different track.  A little proposition did result, but I'm not sure yet if it means what I want it to mean. Haha.

If you recall, last time we figured that

 B_1 = \frac{B_2 \sum_{i=0}^\infty f_2^i(1-y)G_1^{i+1}(y)\vert_0^1}{\lambda - \sum_{i=0}^\infty f_1^i(1-y)G_1^{i+1}(y)\vert_0^1}

and

 B_2 = \frac{B_1 \sum_{i=0}^\infty f_1^i(1-y) G_2^{i+1}(y)\vert_0^1}{\lambda - \sum_{i=0}^\infty f_2^i(1-y) G_2^{i+1}(y)\vert_0^1}

Let's rename the sums by indexing over the subscripts, so that

 \begin{array}{ccc} C_{1,1} & = &\sum_{i=0}^\infty f_1^i(1-y)G_1^{i+1}(y)\vert_0^1 \\ C_{1,2} & = &\sum_{i=0}^\infty f_1^i(1-y) G_2^{i+1}(y)\vert_0^1 \\ C_{2,1} & = &\sum_{i=0}^\infty f_2^i(1-y)G_1^{i+1}(y)\vert_0^1 \\ C_{2,2} & = &\sum_{i=0}^\infty f_2^i(1-y) G_2^{i+1}(y)\vert_0^1 \end{array}

Renaming therefore the constants we get:

 B_1 = \frac{B_2 C_{2,1}}{\lambda - C_{1,1}}

and

 B_2 = \frac{B_1 C_{1,2}}{\lambda - C_{2,2}}

Last time we substituted one equation into the other to figure additional restrictions on  \lambda .  A faster way to do this is to  notice:

 \left( \lambda - C_{1,1} \right)B_1 = B_2 C_{2,1}

and

 \left( \lambda - C_{2,2} \right) B_2 = B_1 C_{1,2}

If we multiply these two expressions we get

 \left( \lambda - C_{1,1} \right)\left( \lambda - C_{2,2} \right) B_1 B_2 = B_1 B_2 C_{1,2} C_{2,1}

Finally, dividing out both  B_1, B_2 we arrive at the quadratic expression on  \lambda of before:

 \left( \lambda - C_{1,1} \right)\left( \lambda - C_{2,2} \right) = C_{1,2} C_{2,1}

Now.  Let's posit that, instead of  a(x) = B_1 f_1(x) + B_2 f_2(x) we have  a^*(x) = B_1 f_1(x) + B_3 f_3(x) .  Then by all the same arguments we should have an expression of  B_1 that is the same, and an expression of  B_3 that is:

 \left( \lambda - C_{3,3} \right) B_3 = B_1 C_{1,3}

with the similar implication that

 \left( \lambda - C_{1,1} \right)\left( \lambda - C_{3,3} \right) = C_{1,3} C_{3,1}

An  a^{**}(x) = B_2 f_2(x) + B_3 f_3(x) would give the implication

 \left( \lambda - C_{2,2} \right)\left( \lambda - C_{3,3} \right) = C_{2,3} C_{3,2}

If we are to multiply all similar expressions, we get

 \left( \lambda - C_{1,1} \right)^2\left( \lambda - C_{2,2} \right)^2 \left( \lambda - C_{3,3} \right)^2 = C_{1,2} C_{2,1}C_{1,3} C_{3,1}C_{2,3} C_{3,2}

or

 \left( \lambda - C_{1,1} \right) \left( \lambda - C_{2,2} \right) \left( \lambda - C_{3,3} \right) = \sqrt{C_{1,2} C_{2,1}C_{1,3} C_{3,1}C_{2,3} C_{3,2}}

In other words, we want to make a pairwise argument to obtain the product of the  \lambda -expressions and a polynomial in  \lambda .  Next I'd like to show the proposition:

 \left( \lambda - C_{1,1}\right) \cdot \left( \lambda - C_{2,2} \right) \cdot \ldots \cdot \left( \lambda - C_{n,n} \right) = \sqrt[n-1]{\prod_{\forall i, \forall j, i \neq j}^n C_{i,j}}

and for this I want to begin with a combinatorial argument.  On the left hand side, the number of pairwise comparisons we can make depends on the number of  \lambda factors of the  \lambda polynomial (or, the highest degree of the  \lambda polynomial).  That is to say, we can make  \binom{n}{2} pairwise comparisons, or  \frac{n!}{(n-2)!2!} = \frac{n (n-1)}{2} comparisons.  Now, I don't know whether anyone has ever noticed this, but this last simplified part looks exceptionally like Gauss's sum of consecutive integers (pyramidal series), so in other words, this last part is in effect  \sum_{i=1}^{n-1} i which I find very cool, because we have just shown, quite accidentally, the equivalence:

 \binom{n}{2} = \binom{n}{n-2} = \sum_{i=1}^{n-1} i

The way I actually figured this out is by noticing that, in our pairwise comparisons, say for the 3rd-degree-polynomial-in- \lambda case, by writing the pairwise comparisons first of the  (\lambda - C_{1,1}) products, then of the  (\lambda - C_{2,2}) (in other words, ordering logically all  \binom{3}{2} products), there were 2 of the first and 1 of the second (and none of the  (\lambda - C_{3,3}) ).  If we do the same for the 4th-degree, there are 3 of the  (\lambda - C_{1,1}) , 2 of the  (\lambda - C_{2,2}) , and 1 of the  (\lambda - C_{3,3}) , with none of the  (\lambda - C_{4,4}) .  In other words, the  \binom{4}{2} pair-products could be written as the sum of the cardinality of the groupings:  3 + 2 + 1 .

Now Gauss's sum of integers formula is already known to work in the general case (just use an inductive proof, e.g.), so the substitution of it into the binomial equivalence needs no further elaboration: it generalizes automatically for all  n .

So if we are to multiply all pairwise comparisons, notice there will be  n - 1 products of each  \lambda -factor: there are  n - 1 products belonging to the  (\lambda - C_{1,1}) grouping (because this first grouping has n-1 entries, from the Gauss formula equivalence), there are  n - 2 products belonging to the  (\lambda - C_{2,2}) PLUS the one already counted in the  (\lambda - C_{1,1}) grouping, for a total of, again,  n - 1 .  The  kth grouping  (\lambda - C_{k,k}) has  n - k products listed for itself PLUS one for each of the previous k - 1 groupings, for a total of  n - k + k - 1 = n - 1, and the k+1th grouping  (\lambda - C_{k+1, k+1}) has  n - (k+1) products listed for itself PLUS one for each of the previous  k groupings, for a total of n - (k+1) + k = n - 1.  We are left in effect with:

 (\lambda - C_{1,1})^{n-1} \cdot(\lambda - C_{2,2})^{n-1} \cdot \ldots \cdot (\lambda - C_{n,n})^{n-1}

The right hand side of each pairwise comparison was nothing more than the simple product on the cross indexes of  C , so it's not difficult to argue then that, if we multiply  \binom{n}{2} such pairs, we get  \prod_{\forall i, \forall j, i \neq j}^n C_{i,j} .   We then take the  n-1 th root on both sides of the equation.

Since the  n + 1 case follows the same basic structure of the argument, we are done with proving our proposition.

What I want this proposition to mean may be very different than what it actually is, I'm hopeful nevertheless but I agree that it requires a bit of further investigation.  As I hinted before, I would like that

 \left( \lambda - C_{1,1}\right) \cdot \left( \lambda - C_{2,2} \right) \cdot \ldots \cdot \left( \lambda - C_{n,n} \right) = \sqrt[n-1]{\prod_{\forall i, \forall j, i \neq j}^n C_{i,j}}

with, for example,  n = 3 represent the constraint on the eigen(patch(ix))values of  a^\circ = B_1 f_1(x) + B_2 f_2(x) + B_3 f_3(x) or, if not that, maybe  a^\circ_\star = a(x) + a^*(x) + a^{**}(x) = 2B_1 f_1(x) + 2 B_2 f_2(x) + 2 B_3 f_3(x) , which brings into question the superposition of functions and their effect on the eigenvalues.  I may be wildly speculating, but hey!  I don't really know better!  I'll do a few experiments and see what shows.

On Eigen(patch(ix))values - (RWLA,MCT,GT,AM Part VIII)

March 16th, 2011 No comments

So in the continuation of this series, I have been thinking long and hard about the curious property of the existence of eigen(patch(ix))values that I have talked about in a previous post.  I began to question whether such eigen(patch(ix))values are limited to a finite set (much as in finite matrices) or whether there was some other fundamental insight, like, if 1 is an eigen(patch(ix))value, then all elements of  \mathbb{R} are too (or all of  \mathbb{R} minus a finite set).  In my latest attempt to understand this, the question comes down to, using the "star" operator, whether

 a(x) \star p(x,y) = \lambda a(x)

has discrete values of  \lambda or, "what values can lambda take for the equation to be true," in direct analogy with eigenvalues when we're dealing with discrete matrices.  I am not using yet "integral transform notation" because this development seemed more intuitive to me, and thus I'm also limiting the treatment to "surfaces" that are smooth and defined on  [0,1] \times [0,1] , like I first thought of them. Thus, the above equation translates to:

 \int_0^1 a(1-y) p(x,y) dy = \lambda a(x)

and, if we recall our construction of the patch (or patchix if we relax the assumption that integrating with respect to x is 1)  p(x,y) = f_1(x) g_1(y) + f_2(x) g_2(y) :

 \begin{array}{ccc} \lambda a(x) & = &\int_0^1 a(1-y) \left(f_1(x) g_1(y) + f_2(x) g_2(y) \right) dy \\ & = & f_1(x) \int_0^1 a(1-y) g_1(y) dy + f_2(x) \int_0^1 a(1-y) g_2(y) dy \\ & = & B_1 f_1(x) + B_2 f_2(x) \end{array}

where  B_1, B_2 are constants.  It is very tempting to divide  \lambda as

 a(x) = \frac{B_1}{\lambda} f_1(x) + \frac{B_2}{\lambda} f_2(x)

must hold provided  \lambda \neq 0 .  So we have excluded an eigen(patch(ix))value right from the start, which is interesting.

We can systematically write the derivatives of  a(x) , as we're going to need them if we follow the algorithm I delineated in one of my previous posts (NB: we assume a finite number of derivatives or periodic ones, or infinite derivatives such that the subsequent sums we'll write are convergent):

 \begin{array}{ccc} a(x) & = & \frac{B_1}{\lambda} f_1(x) + \frac{B_2}{\lambda} f_2(x) \\ a'(x) & = & \frac{B_1}{\lambda} f'_1(x) + \frac{B_2}{\lambda} f'_2(x) \\ a''(x) & = & \frac{B_1}{\lambda} f''_1(x) + \frac{B_2}{\lambda} f''_2(x) \\ \vdots & \vdots & \vdots \\ a^k(x) & = & \frac{B_1}{\lambda} f^k_1(x) + \frac{B_2}{\lambda} f^k_2(x) \\ \vdots & \vdots & \vdots \end{array}

provided, as before,  \lambda \neq 0 .  We want to calculate the constants  B_1, B_2 , to see if they are restricted in some way by a formula, and we do this by integrating by parts as we did in a previous post to obtain the cool "pasquali series." Thus, we have that if  B_1 = \int_0^1 a(1-y) g_1(y) dy , the tabular method gives:

 \begin{array}{ccccc} \vert & Derivatives & \vert & Integrals & \vert \\ \vert & a(1-y) & \vert & g_1(y) & \vert \\ \vert & -a'(1-y) & \vert & G_1^1(y) & \vert \\ \vert & a''(1-y) & \vert & G_1^2(y) & \vert \\ \vert & \vdots & \vert & \vdots & \vert \end{array}

and so,

 \begin{array}{ccc} B_1 & = & \int_0^1 a(1-y) g_1(y) dy \\ & = & a(1-y) G_1^1(y) \vert_0^1 + a'(1-y) G_1^2(y) \vert_0^1 + \ldots \\ & = & \sum_{i = 0}^\infty a^i(1-y) G_1^{i + 1} \vert_0^1 \end{array}

if we remember the alternating sign of the multiplications, and we are allowed some leeway in notation.  Ultimately, this last bit means:  \sum_{i=0}^\infty a^i(0) G_1^{i+1}(1) - \sum_{i=0}^\infty a^i(1) G_1^{i+1}(0) .

Since we have already explicitly written the derivatives of  a(x) , the  a^i(0), a^i(1) derivatives can be written as  \frac{B_1}{\lambda} f_1^i(0) + \frac{B_2}{\lambda} f_2^i(0) and  \frac{B_1}{\lambda} f_1^i(1) + \frac{B_2}{\lambda} f_2^i(1) respectively.

We have then:

 B_1 = \sum_{i=0}^\infty \left( \frac{B_1}{\lambda} f_1^i(0) + \frac{B_2}{\lambda} f_2^i(0) \right) G_1^{i+1}(1) - \sum_{i=0}^\infty \left( \frac{B_1}{\lambda} f_1^i(1) + \frac{B_2}{\lambda} f_2^i(1) \right) G_1^{i+1}(0)

Since we aim to solve for  B_1 , multiplying by  \lambda makes things easier, and also we must rearrange all elements with  B_1 in them, so we get:

 \lambda B_1 = B_1 \sum_{i=0}^\infty \left( f_1^i(0) G_1^{i+1}(1) - f_1^i(1) G_1^{i+1}(0) \right) + B_2 \sum_{i=0}^\infty \left( f_2^i(0) G_1^{i+1}(1) - f_2^i(1) G_1^{i+1}(0) \right)

Subtracting both sides the common term and factoring the constant we endeavor to solve for, we get:

 \left( \lambda - \sum_{i=0}^\infty \left( f_1^i(0) G_1^{i+1}(1) - f_1(1) G_1^{i+1}(0) \right) \right) B_1 = B_2 \sum_{i=0}^\infty \left(f_2^i(0) G_1^{i+1}(1) - f_2^i(1) G_1^{i+1}(0) \right)

or

 B_1 = \frac{B_2 \sum_{i=0}^\infty f_2^i(1-y) G_1^{i+1}(y) \vert_0^1}{\lambda - \sum_{i=0}^\infty f_1^i(1-y) G_1^{i+1}(y) \vert_0^1} = \frac{B_2 D}{\lambda - C}

A similar argument for  B_2 suggests

 B_2 = \frac{B_1 \sum_{i=0}^\infty f_1^i(1-y) G_2^{i+1}(y) \vert_0^1}{\lambda - \sum_{i=0}^\infty f_2^i(1-y) G_2^{i+1}(y) \vert_0^1} = \frac{B_1 E}{\lambda - F}

where the new constants introduced emphasizes the expectation that the sums converge.  Plugging in the one into the other we get:

 B_1 = \frac{\left( \frac{B_1 E}{\lambda - F} \right) D}{\lambda - C} = \frac{B_1 E D}{(\lambda - F) (\lambda - C)}

and now we seem to have additional restrictions on lambda:  \lambda \neq F and  \lambda \neq C .  Furthermore, the constant  B_1 drops out of the equation, suggesting these constants can be anything we can imagine (all of  \mathbb{R} without restriction), but then we have the constraint:

 (\lambda - F)(\lambda - C) = ED

which is extraordinarily similar to its analogue in finite matrix or linear algebra contexts.  Expanding suggests:

 \lambda^2 - (F + C) \lambda + (CF - ED) = 0

which we can solve by the quadratic equation of course, as:

 \lambda_{1,2} = \frac{(F + C) \pm \sqrt{(F-C)^2 + 4ED} }{2}

So not only is  \lambda not equal to a few values, it is incredibly restricted to two of them.

So here's a sort of conjecture, and a plan for the proof.  The allowable values of  \lambda is equal to the number of x terms  a(x) (or  p(x,y) ) carries.  We have already shown the base case, we need only show the induction step, that it works for  k and  k+1 terms.