4
$\begingroup$

Consider the discrete second derivative with Dirichlet boundary conditions on $\mathbb C^n$.

Its eigendecomposition is fully known: see wikipedia

It seems like the largest eigenvalue $\lambda_1$ is one with a fast decaying eigenfunction, by this I mean that at the first coordinate $\vert v_{1,1} \vert \le Cn^{-3/2}.$ The first $1$ indicates the eigenfunction, the second one the coordinate.

A priori there is no reason to have this type of decay, at the first coordinate, I guess.

Is there a way to prove this without(!) using that the eigenfunctions are explicitly known?-Thus, can one show this directly from the matrix?

$\endgroup$
6
  • $\begingroup$ Do I understood correctly that the question is about the eigenvectors and eigenvalues of a tri-diagonal matrix $L$ with $-2$ on the main diagonal and $1$ on the neighbouring two diagonals? In this case $-L$ is a totally positive matrix, which automatically tells a lot about the eigenvalues and eigenvectors (e.g. the interlacing property). However, all eigenvectors are just discretised sine waves, so they do not really decay anywhere. Thus, I must be getting something wrong. Can you elaborate a bit? $\endgroup$ Commented Jul 26, 2019 at 20:40
  • $\begingroup$ I elaborated a bit on the question. It is about proving that we have these fixed decay rates for certain entries. But why? $\endgroup$ Commented Jul 26, 2019 at 22:30
  • $\begingroup$ OK, I see now what you mean by decay. Still, I am not sure if you like to get an exact bound $v_{1,1} \sim C n^{-3/2}$ (note that in fact $v_{i,j} \sim C_{i,j} n^{-3/2}$ for any fixed $i$ and $j$), or a softer estimate of the form $|v_{1,1}| \le |v_{i,1}|$ for any $i$. The latter would work for any totally positive matrix, I think. The former requires more assumptions, and I can think of various proofs (for example, if your matrix is a generator of a symmetric nearest-neighbour Markov chain, then a probabilistic argument could work). $\endgroup$ Commented Jul 28, 2019 at 20:46
  • $\begingroup$ @MateuszKwaśnicki I deliberately asked the question a bit open ended cause I was not sure how much can be said. Thanks for looking into this. I think it would be interesting for me to understand first based on a soft argument why the "soft estimate" holds. So if you say this is a general thing for positive matrices, I am curious to hear about it. Then, if you can actually prove the asymptotics using some kind of robust argument, I would be very curious to hear about it. I am grateful for any insights you would like to share about this estimate. $\endgroup$ Commented Jul 29, 2019 at 20:51
  • $\begingroup$ I am afraid I have no time now to elaborate. However, you may like to search for "Dirichlet heat kernel bounds on graphs", there are dozens of papers dealing with these subjects. $\endgroup$ Commented Jul 29, 2019 at 21:04

2 Answers 2

0
$\begingroup$

OK, so here is an extended version of my comment.


By Perron–Frobenius, the first eigenvector $v_1$ is positive, and thus $L v_1 = \lambda_1 v_1 \geqslant 0$ (here $-L$ is the matrix of the discrete Laplacian with Dirichlet boundary conditions, so that $L \geqslant 0$). Let us write $v_{1,0} = v_{1,n+1} = 0$. It follows that $v_1$ is a concave function on $\{0,1,\ldots,n+1\}$. In particular: $$ v_{1,i} \leqslant i v_{1,1} , $$ and hence $$1 = \|v_1\|_2^2 \leqslant v_{1,1}^2 \sum_{i = 1}^n i^2 \le C_1 v_{1,1}^2 n^3.$$ In particular, $$ v_{1,1} \geqslant C_1^{-1/2} n^{-3/2} . \tag{1} $$


The proof of the converse inequality is slightly more complicated.

First, we consider an auxiliary vector $$ x_i = C_2 i (n + 1 - i) ,$$ with $C_2$ such that $$(L x)_i = 1 .$$ Then $\langle L x, x\rangle \leqslant C_3 n^3$ and $\|x\|_2^2 \geqslant C_4 n^4$, which implies that $\lambda_1 \le C_5 n^{-1}$.

We define another auxiliary vector $$ u_i = C_2 \lambda_1 i^2 ,$$ with $C_2$ such that $L u_i = -\lambda_1$. Set $$w = v_1 + v_{1,1} u.$$ Then $$(L w)_i = \lambda_1 (v_{1,i} - v_{1,1}) \geqslant 0$$ as long as $v_{1,i} \geqslant v_{1,1}$; say, for $i = 1, 2, \ldots, m$. It follows that $w$ is a convex function on $\{0, 1, \ldots, m + 1\}$, with $w_0 = 0$ and $w_1 = (1 + C_2 \lambda_1) v_{1,1}$. In particular, $w_{m+1} \geqslant (m + 1) w_1$, that is, $$v_{1,m+1} + C_2 \lambda_1 v_{1,1} (m + 1)^2 \geqslant (m + 1) (1 + C_2 \lambda_1) v_{1,1} .$$ In other words, $$v_{1,m+1} \geqslant (m + 1) v_{1,1} (1 + C_2 \lambda_1 - C_2 \lambda_1 (m + 1)) .$$ By definition of $m$, we either have $m = n$ or $v_{1,m+1} < v_{1,1}$; in the latter case, it follows that $(m + 1) > 1 / (C_2 \lambda_1) > C_6 n$. In either case, $m \geqslant C_6 n$.

For $i = 1, 2, \ldots, C_6 n$ we therefore have $$ v_{1,i} = w_i - v_{1,1} C_2 \lambda_1 i^2 \geqslant i w_1 - v_{1,1} C_2 \lambda_1 i^2 = i (1 + C_2 \lambda_1) v_{1,1} - v_{1,1} C_2 \lambda_1 i^2 , $$ that is, $$ v_{1,i} \geqslant i v_{1,1} (1 + C_2 \lambda_1 - C_2 \lambda_1 i) \geqslant i v_{1,1} (1 - C_7 i / n) . $$ Therefore, $$ 1 = \|v_1\|_2^2 \geqslant v_{1,1}^2 \sum_{i = 1}^{C_8 n} i^2 (1 - i / (C_8 n))^2 \geqslant v_{1,1}^2 C_9 n^3 $$ (with $C_8 = \min\{C_6, 1 / C_7\}$). We conclude that $$ v_{1,1} \leqslant C_1^{-1/2} n^{-3/2} . \tag{2} $$


Estimates (1) and (2) give the desired bound. The above argument should extend to generators of symmetric "uniformly elliptic" random walks on $\{1, 2, \ldots, n\}$. I suppose a much more clean argument can be given, feel free to edit. Finally, similar results are surely known for more general graphs with boundaries, but I do not have a reference off the top of my head.


Regarding totally positive matrices, I may have been too optimistic. Still, let me recommend Ando's 1987 paper Totally positive matrices. Section 6 of this paper gives a nice summary of the properties of eigenvectors of TP matrices; for example, Theorem 6.3 asserts that the nodes of the eigenvectors (extended to piecewise linear functions) are interlacing.

$\endgroup$
3
  • 1
    $\begingroup$ thank you, I am a bit puzzled what you actually use to get the lower bound. It seems your lower bound only uses positivity? Do you agree that you get this lower bound on any graph? Where do you use for example that you have zero potential? Wouldn't this bound also generalize to a model with order on the diagonal?-In which case eigenvectors decay exponentially? $\endgroup$ Commented Jul 30, 2019 at 18:14
  • $\begingroup$ Well, the proof of (1) uses concavity of $v_1$. This is no longer true if you add a scalar potential (unless it has correct sign). Neither it does extend to general graphs with boundaries. The idea is borrowed from the continuous setting, where one typically searches for barriers, which allows one to bound the solution by some kind of comparison principle. (1/2) $\endgroup$ Commented Jul 30, 2019 at 18:28
  • $\begingroup$ For the interval $(0, a)$, these barriers would be $f(x) = c_1 x$ (which has Laplacian equal to zero) and $g(x) = c_2 x - c_3 x^2$ (which has Laplacian equal to $-2c_3$). One shows that the first eigenfunction must be between $f$ and $g$ for appropriately chosen $c_1, c_2, c_3$. The above is a simple discretisation of this argument. (2/2) $\endgroup$ Commented Jul 30, 2019 at 18:29
0
$\begingroup$

I denote $\Delta^{(n)}$ the discrete Laplacien on $\mathbb{C}^n$ (ie the $n\times n $ matrix with diagonal $-2$ and upper/lower diagonal $1$.) Consider the scaling $ v \rightarrow \phi(t) = \sqrt{n} v(\lfloor tn\rfloor)$ defined on $\mathbb{C}^n\rightarrow L^2([0,1])$. I think we have the following heuristic $$ n^2\Delta^{(n)} \rightarrow \Delta$$ $$ v_1^{(n)} \rightarrow \phi_1$$ with $\Delta$ the continuous Laplacien with Dirichlet boundary conditions and $\phi_1$ its first eigenvector and then $$v_{1,1}^{(n)}\approx \frac{1}{\sqrt{n}}\phi_1 (\frac{1}{n})\approx \frac{1}{n^{3/2}}\phi_1'(0) $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .