8
$\begingroup$

This question is cross-posted at Math.StackExchange.com.

I'm trying to find the leading eigenvalue and corresponding left and right eigenvectors of the following infinite matrix, for $\lambda>0$:

$$ \mathrm{A}=\left( \begin{array}{cccccc} 1 &e^{-\lambda} & 0 &0 &0 & \dots\\ 1 &e^{-\lambda} & e^{-2\lambda} &0 &0 & \dots\\ 1 &e^{-\lambda} & e^{-2\lambda} &e^{-3\lambda} &0 & \dots\\ \vdots & \vdots & \vdots & & \ddots \end{array} \right) $$

Note that there are terms above the main diagonal.

I know that in general infinite matrices aren't really a self-consistent idea. However, this problem arises from the infinite-$n$ limit of $n\times n$ matrices with the same values. That is, if $A^{(n)}$ is an $n\times n$ matrix such that $A^{(n)}_{ij}=A_{ij}$ then I'm looking for $\lim_{n\to\infty} \eta^{(n)}$, $\lim_{n\to\infty} u^{(n)}$ and $\lim_{n\to\infty} v^{(n)}$, where $\eta^{(n)}$, $u^{(n)}$ and $v^{(n)}$ are the leading eigenvalue of $A^{(n)}$ and its corresponding left and right eigenvectors.

I hope that the above leads to a consistent definition. I don't know much about the theory of operators on sequence spaces (which I gather is what's required to think about infinite matrix type problems correctly - pointers about how to apply it to my problem would be appreciated), but it seems to me that defining it as the limit of a sequence of finite problems should at least lead to something well-defined.

One thing that might be important is that this arises in a context in where $p_i = u_iv_i$ forms a probability distribution. So it's the per-element product of the left and right eigenvectors that has to be normalisable according to the $L_1$ norm. (This is why I'm not sure which sequence space I should be asking about.)

Of course these limits might not converge, but from investigating the $n\times n$ case numerically using power iteration, it looks like they do. The convergence is slower for smaller values of $\lambda$, and rounding errors become a problem when it gets too small, but it looks like it probably converges for all $\lambda>0$.

Note that I only care about the leading eigenvalue, i.e. the one with the largest magnitude, which should be real and positive. Its corresponding eigenvectors should have only positive entries, due to the Perron-Frobenius theorem.

Alternatively, if it's easier, a solution for the following matrix will be just as useful to me: $$ \mathrm{B}=\left( \begin{array}{cccccc} 1 & 1& 0 &0 &0 & \dots\\ e^{-\lambda} &e^{-\lambda} & e^{-\lambda} &0 &0 & \dots\\ e^{-2\lambda} & e^{-2\lambda} &e^{-2\lambda} &e^{-2\lambda} &0 & \dots\\ \vdots & \vdots & \vdots & & \ddots \end{array} \right) $$

Again note the terms above the diagonal. (The two problems are not equivalent, it's just that either one of them will help me solve a larger problem.)

The problem is, I just don't have much of an idea how to do this. I've tried a variety of naive methods, along the lines of writing the eigenvalue equation $\mathrm{A}\mathbf{x} = \eta \mathbf{x}$ as an system of equations and then trying to find $\{x_i >0\}$ and $\eta>0$ to satisfy them, but this doesn't seem to lead anywhere nice.

It could be that there is no analytical solution. Or even worse it could be that these matrices have unbounded spectra after all (in which case I'd really like to know!), but if anyone has any insight into how to solve one of these two problems I'd really appreciate it.

$\endgroup$
4
  • $\begingroup$ I don't know whether you've already observed that the characteristic polynomial factors in terms of q-binomials (with $q=e^{-\lambda}$) depending on the size of the matrix? I've seen this for even sizes. (Maybe this gives some hint for the eigenvalues, too.) $\endgroup$ Feb 16, 2014 at 12:12
  • $\begingroup$ Is the problem still open? $\endgroup$
    – Fred Hucht
    Jul 18, 2022 at 18:05
  • $\begingroup$ @FredHucht it's still open in that I don't think I ever found a full solution, although now that you've posted your answer I'm wracking my brain trying to remember why I needed it in the first place! $\endgroup$
    – N. Virgo
    Jul 19, 2022 at 1:35
  • $\begingroup$ @N.Virgo Ok, maybe the answer is helpful for you or others. If so, you might consider accepting it. $\endgroup$
    – Fred Hucht
    Jul 19, 2022 at 21:37

5 Answers 5

5
$\begingroup$

The characteristic polynomial of $\mathrm A_n$ can be calculated exactly in the limit $n\to\infty$: As pointed out by @Gottfried, the characteristic polynomial $c_n(x)=\det(\mathrm A_n-x 1)$ can be written in terms of the $q$-binomial as $$ c_n(x)=\sum_{k=0}^{n/2+1}q^{k(k-1)}\binom{n-k+1}{k}_{\!q} \, (-x)^{n-k}, $$ where $q=e^{-\lambda}$. Inserting the definition of the $q$-binomial $$ \binom{n-k+1}{k}_{\!q} \,= \frac{(q;q)_{n-k+1}}{(q;q)_{n-2k+1}(q;q)_{k}}, $$ and dropping $n$-dependent prefactors, we can perform the limit $n\to\infty$ to get $$ c_\infty(x) = \sum_{k=0}^{\infty}q^{k(k-1)} \frac{\left(-x\right)^{-k}}{(q;q)_{k}}. $$ This sum exactly matches the definition of the basic hypergeometric series, or $q$-hypergeometric function, $$ {_r \phi_s}(a;b;q;z)=\sum_{k=0}^\infty \frac{(a_1;q)_k \ldots (a_r;q)_k}{(b_1;q)_k \ldots (b_s;q)_k} \left((-1)^k q^{k(k-1)/2}\right)^{1+s-r} \frac{z^k}{(q;q)_k}. $$ The characteristic polynomial of the matrix $\mathrm A_n$ for $n\to\infty$ then becomes the nice expression $$ c_\infty(x) = {_0 \phi_1}\!\left(;0;q;-x^{-1}\right). $$ After I derived this result, a web search revealed that this function is well known. The case ${_0 \phi_1}(;0;q;-q z)$ is also known as Ramanujan function or $q$-Airy function, see page 27 of these slides and references therein, where also the zeroes of $c_\infty(x)$ are discussed.

$\endgroup$
4
$\begingroup$

In case you've not already seen this, here is a list of the characteristic polynomials for sizes 2,4,6,8 and the generalization-scheme is rather obvious. Perhaps this is of some help. It involves the so-called "q-binomials" with your parameter as base.

  1. For conciseness of notation I've rewritten your expression with the parameter $e^{-\lambda} $ as $z$

  2. For the binomial lets write $(a:b)$

  3. the $n$'th $q$-power to base $z$ is $ \displaystyle z_n={z^n-1 \over z-1} $, let's write the q-factorial as $ \displaystyle z_{n!} = z_n \cdot z_{n-1} \cdot \ldots \cdot z_1 $ and the q-binomial $ \displaystyle (a:b)_q = {z_{a!} \over z_{b!} z_{(a-b)!}} $

then for the fist few even matrix-sizes we get the characteristic polynomials as $$ \begin{array} {r|llllll} \text{size} & \\ \hline\\ 2&c_2(x)=&1x^2&-z^0(2:1)_q x \\ 4&c_4(x)=&1x^4&-z^0(4:1)_q x^3 &+ z^2(3:2)_q x^2 \\ 6&c_6(x)=&1x^6&-z^0(6:1)_q x^5 &+ z^2(5:2)_q x^4 &- z^6(4:3)_q x^3\\ 8&c_8(x)=&1x^8&-z^0(8:1)_q x^7 &+ z^2(7:2)_q x^6 &- z^6(6:3)_q x^5&+ z^{12}(5:4)_q x^4\\ \end{array}$$ (The exponents at the free powers of $z$ are $2$ times the binomials $0,1,3,6,10,...$ . Also I hope I didn't mess up the powers of $z-1$ which might or might not occur additionally in this notation of the q-factorials/q-binomials; I'll check this later)

If we are lucky then this gives some possibility to estimate the largest polynomial root depending on your parameter $\lambda$


[update] This formal description is very useful; we do no more need to compute the matrix - just construct the characteristic polynomial (represented only by a vector of size $n+1$ !) and determine the largest root.

This is the table for matrix-sizes $n \times n$ with $n=2,4,6...,32$; the maximal root approximates well with increasing $n$ for the given $\lambda$ (in the example = $\log(4)$).

lambda=1.3862943611198906188  q=0.25
Table of highest eigenvalue/largest characteristic root for matrix-sizes
size : eigenvalue  (time needed)
---------------------------------------
   2 : 1.2500000000000000000 (0 ms)
   4 : 1.2631849865636825686 (0 ms)
   6 : 1.2631855203241351201 (0 ms)
   8 : 1.2631855203242152061 (0 ms)
  10 : 1.2631855203242152061 (16 ms)
  12 : 1.2631855203242152061 (46 ms)
  14 : 1.2631855203242152061 (78 ms)
  16 : 1.2631855203242152061 (94 ms)
 ...
  26 : 1.2631855203242152061 (312 ms)
  28 : 1.2631855203242152061 (359 ms)
  30 : 1.2631855203242152061 (437 ms)
  32 : 1.2631855203242152061 (515 ms)

[update2]
With an optimized procedure, using Newton-iteration for the (supposed, highest) root I get this table

lambda=1.3862943611198906188  q=0.25 
warning: float precision about 1200 dec digits needed for size n=128 
Table of highest eigenvalue/largest characteristic root for matrix-sizes
highest root computed using Newton-iteration
size : largest root of char.polynomial  (time needed)
--------------------------------------------------------
   2 : 1.2500000000000000000 (  10 ms) 
   4 : 1.2631849865636825686 (  16 ms) 
   8 : 1.2631855203242152061 (  15 ms) 
  16 : 1.2631855203242152061 (  63 ms) 
  32 : 1.2631855203242152061 ( 187 ms) 
  64 : 1.2631855203242152061 ( 702 ms) 
 128 : 1.2631855203242152061 (2168 ms) 
 256 : 1.2631855203242152061 (7286 ms) 

(here the two last computations for the root differ only by the 220'th digit)

$\endgroup$
2
  • $\begingroup$ Numerically, it appears that the reciprocal polynomials $x^{2n}c_{2n}(1/x)$ converge pointwise to a limit, the smallest zero of which would be the leading eigenvalue of interest. Mathematica fails to compute the limit. $\endgroup$
    – Eckhard
    Feb 16, 2014 at 21:02
  • $\begingroup$ Thanks, this is really useful information! I hadn't tried this approach. $\endgroup$
    – N. Virgo
    Feb 17, 2014 at 4:52
2
$\begingroup$

Even though there are some problems with the definition, as both you and @alpha note, I suspect you can get an answer that is probably the correct answer to the precise version of the question.

If you let $\beta=e^{-\lambda}$, and assume $\alpha$ is the eigenvalue, the eigenvector equation is the family of equations $$ \alpha (x_n-x_{n-1})=\beta^n x_{n+1} \text{ for $n\ge 2$}. $$

Making the substitution $Z_n=\beta^{(n-1)(n-2)/2}x_n/\alpha^n$, you arrive at the new family of equations:

$$ Z_{n+1}=Z_n-\beta^{n-3}Z_{n-1}/\alpha \text{ for $n\ge 2$.} $$

I suspect that numerically, this should let you figure out the right value of $\alpha$ by insisting that $Z_n\to 0$ from above. If $\alpha$ is too high, I would expect this to stay positive (you can set $x_1=1$ and obtain values of $Z_1$ and $Z_2$ to get the recurrence going). If $\alpha$ is too low, I would expect it to go negative.

If this works, you would also be able to recover the eigenvector from the $Z$'s.

$\endgroup$
2
  • $\begingroup$ I believe this should be $Z_n/\beta$ in your new equation. I can confirm that your strategy works. $\endgroup$
    – Eckhard
    Feb 17, 2014 at 19:39
  • 1
    $\begingroup$ I should have defined $Z_n=\beta^{n(n-1)/2}x_n/\alpha^n$. Then you get (I hope) $Z_{n+1}=Z_n-\beta^{n-1}Z_{n-1}/\alpha$. $\endgroup$ Feb 17, 2014 at 22:37
1
$\begingroup$
  1. In order for your problem to be well-posed, you have to specify on which infinite dimensional (Banach?) sequence space your operator is acting.

  2. As a row-finite matrix it maps $\omega$ (the Fréchet space of ALL sequences) into itself.

  3. It does not map the perhaps most natural choice $\ell^2$ into itself.

  4. A priori there is no reason to suppose that finite dimensional methods such as use of the characteristic polynomial carry over to this situation.

  5. Simple algebra shows that there are no eigenvalues---just look at the first coordinate in the equation $Bx=\mu x$. This reduces to the equation $$\xi_0+\exp(-\lambda)\xi_1=\mu\xi_0.$$

$\endgroup$
2
  • $\begingroup$ I'm afraid I don't know how to think in terms of operators on sequence spaces (though that's not to say I'm unwilling to learn). This problem arises from the infinite-$n$ limit of an $n\times n$ problem. Isn't it well-posed as long as we specify how we take the limit? (I admit I didn't do that explicitly enough - I will edit - but it's the most obvious way.) Of course the sequence might not converge, but numerically it seems it does: the eigenvalue approaches a constant $\lambda$-dependent value, and the leading eigenvector resembles a sequence that converges to a finite value. $\endgroup$
    – N. Virgo
    Feb 17, 2014 at 4:43
  • 2
    $\begingroup$ By the way I'm not sure what you're getting at with the equation in point 5. It's one equation in 3 unknowns (although we can always let $\xi_0=1$, so really there's only two unknowns), but it's only one equation in a system of simultaneous equations, so the fact that we can't determine $\mu$ from it is unsurprising. This equation is the same in the finite-$n$ case, in which we can work out the value for $\mu$. So I'm not sure how you can conclude that there are no eigenvalues just from this equation. $\endgroup$
    – N. Virgo
    Feb 17, 2014 at 4:50
0
$\begingroup$

This is somehow similar to the answer of Anthony Quas. Setting $q=e^{-\lambda}$ there is always a "Frobenius vector" with coefficients in the ring $\mathbb Z[[q]]$ of formal power series as follows. Consider an arbitrary initial vector $V=(v_0,V_1,\dots)=(1,\dots)\in \mathbb Z^{\mathbb N}$ and iterate the map $V\longmapsto\frac{1}{c_0}AV$ where $c_0$ is the first coefficient of $AV$ and where all arithmetic operations are in the ring of formal power series. This map has a unique fixpoint $\tilde V=(\tilde V_0=1,\tilde V_2,\dots)$ with coefficients given by formal power series. This formal Frobenius vector is formally an eigenvector with eigenvalue $1+q\tilde V_1\in\mathbb Z[[q]]$ having first coefficients $$1+q+q^3-q^4+2 q^5-3 q^6+6 q^7-12 q^8+25 q^9-52 q^{10}+111 q^{11}-241 q^{12}+530 q^{13}-1176 q^{14}+2632 q^{15}-5935 q^{16}+13470 q^{17}-30743 q^{18}+70516 q^{19}\dots $$

The first coefficients of $\tilde V$ start as \begin{eqnarray*}\tilde V_0&=&1\\ \tilde V_1&=&1+q^2-q^3+2q^4-3q^5+6q^6-12q^7+25q^8-52q^9+\dots\\ \tilde V_2&=&1+q^2+q^4-q^5+3 q^6-5 q^7+11 q^8-23 q^9+\dots\\ \tilde V_3&=&1+q^2+2 q^4-2 q^5+5 q^6-8 q^7+18 q^8-36 q^9+\dots\\ \tilde V_4&=&1+q^2+2 q^4-q^5+4 q^6-6 q^7+15 q^8-29 q^9+\dots\\ \tilde V_5&=&1+q^2+2 q^4-q^5+5 q^6-7 q^7+17 q^8-32 q^9+\dots\\ \tilde V_6&=&1+q^2+2 q^4-q^5+5 q^6-6 q^7+16 q^8-30 q^9+\dots\\ \tilde V_7&=&1+q^2+2 q^4-q^5+5 q^6-6 q^7+17 q^8-31 q^9+\dots\\ \tilde V_8&=&1+q^2+2 q^4-q^5+5 q^6-6 q^7+17 q^8-30 q^9+\dots\\ \tilde V_{9}&=&1+q^2+2 q^4-q^5+5 q^6-6 q^7+17 q^8-30 q^9+\dots \end{eqnarray*} The identity $\tilde V_i-\tilde V_{i+1}=O(q^{i+1})$ shows that we have a coefficient-wise limit $\tilde V_\infty=\lim_{i\rightarrow\infty}\tilde V_i$. It is also given by the equation $\tilde V_\infty=\frac{1}{1+q\tilde V_1}\sum_{k=0}^\infty q^k\tilde V_{k}$. The first coefficients of $\tilde V_\infty$ are $$1+q^2+2 q^4-q^5+5 q^6-6 q^7+17 q^8-30 q^9+71 q^{10}-147 q^{11}+334 q^{12}-734 q^{13}+1662 q^{14}-3747 q^{15}+8548 q^{16}-19548 q^{17}+44977 q^{18}-103845 q^{19}+\dots$$

If these series have a non-zero convergency radius (which could be the case considering the above data), you have nice properties for $q$ small enough, otherwise everything remains formal.

I suspect that all these series have a common strictly positive convergency radius yielding the inverse of the largest value $q$ for which there is an eigenvector with bounded coefficients.

Added: There seems to exist an additional sequence $U_0=\tilde V_\infty,U_1,\dots$ of formal power series in $\mathbb Z[[q]]$ such that $$\tilde V_i=U_0+q^{2+i}U_1+q^{6+2i}U_2+q^{12+3i}U_3+\dots.$$ We have moreover seemingly $U_i(0)=(-1)^i$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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