Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have asked this question previously at Math.stackexchange, but it seems to receive little attention there.

In my efforts (somewhere on the boundary of discrete mathematics and theoretical computer science), I have come upon the necessity of solving (or at least finding out some of the solution's properties) infinite systems of difference (NOT differential) equations (linear, autonomous, first-order). Solving countable systems is sufficient for my purpose.

However, I have almost no idea about how to solve such systems (and what are the solvability conditions). I have a feeling that a possible approach is to seek generalizations of the finite-dimensional method to infinite-dimensional spaces via the spectral theory of linear operators, but I have no idea about the details.

So my question is whether there are any resources that deal systematically with infinite systems of difference equations. I would be grateful either for a resource that can be read also without a knowledge of advanced mathematics (that is something readable for non-mathematicians) or, alternatively, for a more advanced resource with a recommendation where to learn the prerequisities. My mathematical background is unfortunately quite basic (I am a computer science major): possibly relevant fields I have a background in are calculus, linear algebra, some fundamentals of modern analysis, difference/differential equations, and basics of functional analysis (however I have very poor knowledge of spectral theory).

I would appreciate any resources dealing with this issue, as well as any recommendations about which parts of mathematics I am supposed to learn (preferably with some recommended resources). I am willing to invest a considerable amount of time into the study, but I would like to follow some recommended path that leads to the goal. In the case that the theory of infinite systems of differential equations is similar, I would appreciate also resources dealing with them.

share|improve this question
    
Is your system linear ? –  Thomas Richard Jul 20 '13 at 8:30
    
@ThomasRichard Yes, linear and autonomous. –  042 Jul 20 '13 at 9:47
    
Sorry I read too fast... –  Thomas Richard Jul 20 '13 at 15:58

2 Answers 2

up vote 1 down vote accepted

If your equations look like $x_{i+1} = Ax_i$, where each $x_j$ is an element of a (possibly infinite dimensional) vector space and $A$ is a linear operator thereon, then the general solution is $x_j = A^j x_0 = \exp(j\log(A))x_0$, with $x_0$ specifying the initial conditions. The properties of $A^j$, or equivalently $\exp(j\log(A))$, can be deduced from a knowledge of the spectrum and invariant subspaces of $A$. This is precisely spectral theory. So I guess you just have to bite the bullet and start reading up on spectral theory.

The easiest situation is when the $x_j$ are vectors in a Hilbert space and $A$ is a bounded self-adjoint operator. This case is covered in essentially every introductory book on functional analysis. There is a long list of references of introductory and higher level reference books on Wikipedia.

If your $A$ is not of the above form, then you need to be more specific about the structure of your difference equation to get a more relevant suggestion.

share|improve this answer
    
Thank you for your answer, this sounds good... My equations are exactly of the form $x_{i+1} = Ax_i$, however $A$ need not be self-adjoint. In my basic setting, $A$ is a bounded operator on $\ell^{\infty}$ that can be viewed as an infinite matrix that is $k$-diagonal for some constant $k$. However, there may be a possibility to transform a problem to a more usual space $\ell^2$. –  042 Jul 20 '13 at 16:55
    
I have one more question... By $\exp(A)$ do you denote $e^A$? Because this sounds to me more like a solution to a differential equation than to a difference equation. But I am surely missing something... –  042 Jul 20 '13 at 17:01
    
You're right, I didn't think the formula completely through when I wrote it. It's fixed now. But it doesn't really change the rest of the answer. –  Igor Khavkine Jul 20 '13 at 23:08
    
@042, if you can find a linear transformation $T$ (which does not destroy too much structure of your equation) and $B = T A T^{-1}$ is self-adjoint, then you could solve the equivalent equation $y_{j+1} = B y_j$, with $y_j = Tx_j$. If $A$ cannot be made self-adjoint in this way, you need the more general spectral theory for operators on Banach spaces. Unfortunately, I don't know of a good modern reference, but some information on that can be found in Ch.XI of Functional Analysis by Riesz and Sz.-Nagy. –  Igor Khavkine Jul 20 '13 at 23:32
    
Thank you for the extensive comment. This seems like a path to follow. However, I shall try to leave this question open for some time, mainly in order to seek some other reference on the general theory you have mentioned. –  042 Jul 21 '13 at 12:21

There is a branch of mathematics called difference algebra. It deals systematically with quite general (possibly infinite) systems of algebraic difference equations. The Wikipedia entry will give you some idea. A recently appeared monograph is

A. Levin, Difference algebra, Springer, 2008.

In difference algebra, there is an analog of Hilbert's basis theorem, which, roughly speaking, states that for every infinite system of difference equations, there exists a finite subsystem having precisely the same set of solutions.

However, different people have a different idea of what actually is a difference equation and it is quite crucial to specify where one is looking for the solutions. I am afraid the above reference is actually way too general to be really useful for you and your problem, but it definitely is a resource that deals systematically with infinite systems of difference equations.

share|improve this answer
    
Just to be clear, an infinite system of equations to which the Hilbert basis theorem applies contains only finitely many dependent variables at each time step. It seems the OP is interested in the case with infinitely many dependent variables at each time step. –  Igor Khavkine Jul 21 '13 at 0:58
    
You are right, the basis theorem of course only applies to finitely many dependent variables. Considering the title, I figured the above reference is a resource that ought to be mentioned. However, (re)considering the special situation of 042 it appears to be off-topic. –  anonymous Jul 21 '13 at 10:43
    
@anonymous Thank you for your answer. To be honest, I am not very knowledgeable in this algebraic stuff, so I am not able to figure out, if it is relevant to me or not. However, the number of dependent variables at each time step is in deed infinite. Anyway, this seems like an interesting stuff, but I am afraid that more for experts than for people like me. –  042 Jul 21 '13 at 12:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.