11
$\begingroup$

Consider the following adjacency matrix of a complete graph: $$A=(e^{-|i-j|})_{1\leq i\neq j\leq n}$$ with 0 on the diagonal. Let $D=diag\{d_1,...,d_n\}$ be the degree matrix where $d_i=\sum_{j\neq i}e^{-|i-j|}$. Then $L=D-A$ is the Laplacian. Let $L^\dagger$ be the Moore-Penrose inverse of the Laplacian. I'm interested in the following quantity $$a_{ij}=|(e_1-e_2)^TL^\dagger(e_i-e_j)|$$ where $e_i=(0,0...,0,1,0,...0)$ with 1 on the ith coordinate. I conjecture that $a_{ij}$ will decay exponentially when both $i$ and $j$ moves away from 1 and 2. Something like $a_{ij}\leq C _1e^{-C_2\min\{i,j\}}$ where $C_1,C_2$ are some constants. From the physics point of view, $a_{ij}$ is the voltage potential difference between $i$ and $j$. It is intuitive that when they are far away from the source, 1 and 2, they should be very small given the structure of the graph.

In fact, my simulation shows that as long as $i,j\neq1,2$, $a_{ij}$ suddenly becomes extremely close to 0. There seems to be no decay, but an acute cut. This phenomenon holds for slight perturbation of $A$, keeping the decaying property.

Is this conjecture true? How can we prove it? What is the rate of decay?

Another quantity that is also interesting is $$\sum_{i\neq j}e^{-|i-j|}a_{ij}$$ which is the weighted average of potential differences. How can we bound this? For this quantity, I conjecture it is bounded by some constant instead of growing with $n$. The physical meaning of this quantity is the sum of all currents in each edge.

(Update)

Enlightened by the discussion with @Abdelmalek Abdesselam below. We have the Neuman series representation: $$a_{ij}=|(e_1-e_2)^TD^{-1/2}\sum_{k\geq0}\left(D^{-1/2}AD^{-1/2}-\alpha D^{1/2}JD^{1/2}\right)^kD^{-1/2}(e_i-e_j)|$$ where $J$ is the matrix of all 1s and $\alpha$ is some constant to be chosen. We want to choose $\alpha$ such that the power of the matrix decays fast. How can we achieve this and bound the entries of $D^{-1/2}AD^{-1/2}-\alpha D^{1/2}JD^{1/2}$? A possible choice is $\alpha=1/tr(D)$.

$\endgroup$
  • 1
    $\begingroup$ I guess one should say for more precision that $C_1,C_2$ must be independent of $n$. I would have to think a bit about the use of the Moore-Penrose inverse. But for a related problem where you would add some positive quantities on the diagonal so that $L$ is invertible and you can use $L^{-1}$ instead of $L^{\dagger}$, a simple Neuman series will do the trick. It is also the Green function of a (jumping) random walk with a positive killing rate. Another idea is to use the Matrix-Tree theorem to express $L^{\dagger}$. $\endgroup$ – Abdelmalek Abdesselam May 22 at 17:16
  • $\begingroup$ Yes. $C_1$ and $C_2$ are independent of $n$ as I posted they are constants. $\endgroup$ – neverevernever May 22 at 17:18
  • $\begingroup$ @AbdelmalekAbdesselam Actually, they may depend on $n$, as long as the bound is sharper than they are constants. It is not clear to me that the optimal bound is independent of $n$. $\endgroup$ – neverevernever May 22 at 17:31
  • 1
    $\begingroup$ This is a very good question BTW. I think the result should be true and the continuum limit of it is basically saying the derivative of Brownian motion is white noise. To see this generalize your conjecture to $A$ which are not equal but rather bounded by exponentials. The particular case or nearest neighbor $A$ amout to showing decorrelation of local increments of a discrete walk trying to become a Brownian motion. $\endgroup$ – Abdelmalek Abdesselam May 22 at 18:20
  • $\begingroup$ If $L$ is replaced by $\lambda I+L$ for $\lambda>0$, the analogous result is proved as Lemma 3, page 10 of arxiv.org/abs/0901.4756 $\endgroup$ – Abdelmalek Abdesselam May 22 at 18:23
3
$\begingroup$

Edit: This turns out to be quite simple. Observe that $a_{1i} / a_{2i} = q$ does not depend on $i \in \{3, 4, \ldots, n\}$. Thus, if $x_1 = 1$, $x_2 = -q$ and $x_i = 0$ for $i \in \{3, 4, \ldots, n\}$, then we clearly have $L x = c e_1 - c e_2$, where $c = \sum_{i=3}^n a_{1i}$. It follows that $$L^\dagger (e_1 - e_2) = c^{-1} x + \operatorname{const}.$$

I leave the previous version of this answer below, as it provides a way to evaluate $L^\dagger$ explicitly.



I cannot say I understand what is really going on here, but at least I have a proof that $a_{ij} = 0$ when $i, j \ge 3$. (I leave my previous comment/answer, as it contains some related stuff that is not included here.)


Notation: Every sum is a sum over $\{1, 2, \ldots, n\}$. We write $q = e^{-1}$ (and actually any $q \in (0, 1)$ will work). Given a vector $x = (x_i)$ we write $$ \Delta x_i = x_{i+1} + x_{i-1} - 2 x_i $$ if $1 < i < n$.


Given a vector $(x_i)$, we have $$ Lx_i = \sum_j q^{|i-j|} (x_i - x_j) = b_i x_i - \sum_j q^{|i-j|} x_j ,$$ where $$ b_i = \sum_j q^{|i-j|} = \frac{1 + q - q^i - q^{n+1-i}}{1 - q} $$ Therefore, when $1 < i < n$, we have $$ \begin{aligned} \Delta Lx_i & = \Delta (b x)_i - \sum_j (q^{|i-j+1|}+q^{|i-j-1|}-2q^{|i-j|}) x_j \\ & = \Delta (b x)_i - (q + q^{-1} - 2) \sum_j q^{|i-j|} x_j + (q^{-1} - q) x_i \\ & = \Delta (b x)_i + (q + q^{-1} - 2) L x_i - (q + q^{-1} - 2) b_i x_i + (q^{-1} - q) x_i \\ & = (q + q^{-1} - 2) L x_i + b_{i+1} x_{i+1} + b_{i-1} x_{i-1} - ((q + q^{-1}) b_i - (q^{-1} - q)) x_i . \end{aligned} $$ A short calculation shows that $$ b_{i+1} + b_{i-1} = ((q + q^{-1}) b_i - (q^{-1} - q)) $$ (which looks somewhat miraculous, but there must be some insightful explanation for that). Thus, $$ \Delta Lx_i = (q + q^{-1} - 2) L x_i + b_{i+1} (x_{i+1} - x_i) + b_{i-1} (x_{i-1} - x_i) . $$ Suppose that $x_i = L^\dagger y_i$ for some vector $(y_i)$ such that $\sum_i y_i = 0$. Then $L x_i = L L^\dagger y_i = y_i$. Write $c = q + q^{-1} - 2$. We then have $$ \Delta y_i - c y_i = b_{i+1} (x_{i+1} - x_i) + b_{i-1} (x_{i-1} - x_i) . $$ In particular, the following claim follows.

Proposition 1: If $1 < i < n$, $y_{i-1} = y_i = y_{i+1} = 0$ and $x_i = x_{i+1}$, then $x_{i-1} = x_i$.

The above result will serve as an induction step. To initiate the induction, we need to study the $i = n$, which is slightly different. In that case: $$ \begin{aligned} Lx_{n-1} - Lx_n & = b_{n-1} x_{n-1} - b_n x_n - \sum_j (q^{|n-j-1|}-q^{|n-j|}) x_j \\ & = b_{n-1} x_{n-1} - b_n x_n - (q^{-1} - 1) \sum_j q^{|n-j|} x_j + (q^{-1} - q) x_n \\ & = b_{n-1} x_{n-1} - b_n x_n + (q^{-1} - 1) L x_n - (q^{-1} - 1) b_n x_n + (q^{-1} - q) x_n \\ & = (q^{-1} - 1) L x_n + b_{n-1} x_{n-1} - (q^{-1} b_n - (q^{-1} - q)) x_n . \end{aligned} $$ This time we have $$ q^{-1} b_n - (q^{-1} - q) = b_{n-1} , $$ and hence $$ Lx_{n-1} - Lx_n = (q^{-1} - 1) L x_n + b_{n-1} (x_{n-1} - x_n) . $$ Again we consider $x_i = L^\dagger y_i$ for some vector $(y_i)$ such that $\sum_i y_i = 0$, and we write $d = q^{-1} - 1$. We then have $$ (y_{n-1} - y_n) - d y_n = b_{n-1} (x_{n-1} - x_n) . $$ As a consequence, we have the following result.

Proposition 2: If $y_{n-1} = y_n = 0$, then $x_{n-1} = x_n$.

For $y = e_1 - e_2 = (1, -1, 0, 0, \ldots)$, we immediately obtain the desired result.

Corollary: If $y = e_1 - e_2$ and $x = L^\dagger y$, then $x_3 = x_4 = x_5 = \ldots = x_n$. Consequently, $a_{ij} = x_i - x_j = 0$ whenever $i, j \ge 3$.


Another consequence of the above result is that if $L^\dagger = (u_{ij})$, then $$u_{i+1,j+1}-u_{i,j+1}-u_{i+1,j}+u_{i,j} = 0$$ whenever $i + 1 < j$ or $j + 1 < i$. Moreover, it should be relatively easy to use Propositions 1 and 2 to evaluate $u_{ij}$ explicitly, and in particular to prove that $$ u_{ij} = v_{\max\{i,j\}} + v_{\max\{n+1-i,n+1-j\}} + \tfrac{1}{4} |i - j| $$ when $i \ne j$, where $(v_i)$ is an explicitly given vector (in terms of products/ratios of $b_i$, I guess).


Final remark: there is a corresponding result in continuous variable: the Green function for the operator $$L f(x) = \int_0^1 e^{-q |x - y|} (f(x) - f(y)) dy$$ has zero mixed second-order derivative. The proof follows exactly the same line, and is in fact somewhat less technical.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is such a miracle! When the entries are not $e^{-|i,j|}$ exactly, for example we only have $e^{-|i-j|}\leq A_{ij}\leq 2e^{-|i-j|}$. Then I think they will not be exactly 0, can we bound $a_{kl}$ using similar arguments? $\endgroup$ – neverevernever May 23 at 23:21
  • $\begingroup$ (1/2) A miracle — indeed, I am completely surprised by this result, and I still do not understand how this is possible. I did once look at the continuous counterpart mentioned in the end of my answer and I noticed some nice explicit expressions, but with a different boundary condition. I am kind of shocked that with this particular definition one can still get explicit expressions. $\endgroup$ – Mateusz Kwaśnicki May 24 at 0:14
  • $\begingroup$ (2/2) Regarding perturbations: I no longer trust my intuition here, but my wild guess would be "no", I think. The above approach seems to heavily use the structure of $e^{-|i-j|}$. $\endgroup$ – Mateusz Kwaśnicki May 24 at 0:16
  • $\begingroup$ Your updated solution is very insightful. It basically says that $e_1-e_2$ is in the span of the first two columns of $L$. When the entries of $L$ is not exactly $e^{-|i-j|}$, it seems intuitive that $e_1-e_2$ should also roughly lie within the span of the first several columns. The importance of each column to form the vector $e_1-e_2$ by linear combination seems to decay somehow. $\endgroup$ – neverevernever May 25 at 15:34
4
$\begingroup$

This is not an answer, but too long for a comment.


Consider a doubly infinite matrix $L = (q_{ij})_{i,j \in \mathbb{Z}}$ with entries $q_{ij} = -e^{-|i - j|}$ when $i \ne j$, and $q_{ii} = 2 e / (1 - e)$; here $i, j \in \mathbb{Z}$. The symbol of this matrix (i.e. the Fourier series with coefficients $e^{-|j|}$, except at $j = 0$) is: $$ \psi(x) = \frac{e^2 - 1}{e^2 - 2 e \cos x + 1} - \frac{e + 1}{e - 1} . $$ The symbol of $L^\dagger$ is thus $1 / \psi(x)$ (in the principal value sense), which has a singularity of type $1 / x^2$ at $x = 0$. It follows that in this case $$ a_{kl} = \frac{1}{2 \pi} \int_{-\pi}^{\pi} \frac{(e^{i x} - e^{2 i x}) (e^{i k x} - e^{i l x})}{\psi(x)} \, dx . $$

In general, the above expression will only have power-type decay as $k,l \to \infty$.

However, for this particular choice of $L$, things simplify a lot. The pseudo-inverse $L^\dagger = (u_{ij})_{i,j \in \mathbb{Z}}$ can be found explicitly, and its entries are $u_{ij} = C_1 - C_2 |i - j|$ when $i \ne j$ and $u_{ii} = C_3$ for appropriate constants $C_1$, $C_2$, $C_3$. Consequently, $a_{kl} = 0$ when $k, l > 2$.


I do not have a clear intuition about what happens in the one-sided case (that is, if we consider an infinite matrix $L$ with entries indexed by $i, j \in \{1, 2, \ldots\}$), let alone the bounded case (with $i, j \in \{1, 2, \ldots, n\}$). My wild guess would be that the symmetry breaks, and there is no hope for any closed-form formula.

However, a quick numerical experiment suggests strongly that we still have $a_{kl} = 0$! More precisely, the entries $u_{ij}$ of $L^\dagger$ apparently satisfy $$ u_{ij} = v_{\max\{i,j\}} + v_{\max\{n+1-i,n+1-j\}}, v_{n-i} + v_j\} + \tfrac{1}{4} |i - j| \qquad (i \ne j) $$ for an appropriate vector $v_i$. I find this extremely surprising!

Here is the code in Octave, in case anyone is interested. First, we construct $L$ and its pseudo-inverse (denoted U here):

n = 10;                                  # size of the matrix
A = toeplitz(exp(-(0:n-1)));
L = diag(A * ones(n,1)) - A;             # matrix L
U = pinv(L);                             # pseudo-inverse L^\dagger

Next, we verify that the mixed second-order difference of $L^\dagger$ is a tri-diagonal matrix:

D = U(1:n-1, 1:n-1) - U(1:n-1, 2:n) ...
    - U(2:n, 1:n-1) + U(2:n, 2:n);       # second-order difference of U

This already shows that $L^\dagger$ has the desired structure, but we can verify this directly. First two lines are to extract the vector $v_i$, the other two define the matrix Z with entries $$ u_{ij} - v_{\max\{i,j\}} - v_{\max\{n+1-i,n+1-j\}}, v_{n-i} + v_j\} - \tfrac{1}{4} |i - j| \qquad (i \ne j) $$ which should be zero except on the diagonal:

X = U - 0.25 * abs(repmat(1:n, n, 1) - repmat(1:n, n, 1)');
V = X(:, 1) - 0.5 * X(n, 1);
I = repmat(1:n,n,1);
Z = X - V(max(I, I')) - V(max(n + 1 - I, n + 1 - I'));
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How did you find the expression of $L^\dagger$ explicitly? $\endgroup$ – neverevernever May 22 at 21:24
  • $\begingroup$ We have $1/\psi(x) = c_1 (e^2 - 2 e \cos x + 1) / (1 - \cos x) = c_2 + c_3 / (1 - \cos x)$; the constant $c_2$ corresponds to $c_2 \delta_{ij}$, and $c_3 / (1 - \cos x)$ corresponds to the Green's function for the simple random walk, $-c_4 |i - j|$. $\endgroup$ – Mateusz Kwaśnicki May 22 at 21:37
  • $\begingroup$ What if the entries of the matrix is not exactly $e^{-|i-j|}$ and the matrix is not Toeplitz, but the entries decay at the same rate. Can we still obtain explicit expression for $L^\dagger$? Is $a_{kl}$ still 0 for $k,l>2$? $\endgroup$ – neverevernever May 22 at 23:10
  • $\begingroup$ I doubt one can get explicit expressions if $L$ is not exactly $(e^{-|i-j|})$. $\endgroup$ – Mateusz Kwaśnicki May 23 at 7:54
  • $\begingroup$ I edited my answer/comment. I am now convinced that your $a_{ij}$ is equal to zero, but I have no clue why. $\endgroup$ – Mateusz Kwaśnicki May 23 at 8:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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