Exponentiating similar Laplacians

123 Views Asked by At

Let $L_c$ be the $n\times n$ Laplacian matrix of the complete graph, and $L$ be the $n\times n$ Laplacian of any simple, connected graph possessing a vertex $k$ of maximum degree $d_k=n-1$. Clearly, there is a column of $L$ that looks like the corresponding column of $L_c$.

Now, consider the exponential matrices $e^{-itL_c}$ and $e^{-itL}$, where $t>0$ is a real parameter. Is the equality of the same columns preserved? I've been playing around with this in Mathematica and haven't come up with a counterexample.

Edit. Here are a few examples. For the star graph we obtain with $n=5$ the following matrix: $$\left( \begin{array}{ccccc} \frac{1}{5} \left(1+4 e^5\right) & \frac{1}{5} \left(1-e^5\right) & \frac{1}{5} \left(1-e^5\right) & \frac{1}{5} \left(1-e^5\right) & \frac{1}{5} \left(1-e^5\right) \\ \frac{1}{5} \left(1-e^5\right) & \frac{1}{20} \left(4+15 e+e^5\right) & \frac{1}{20} \left(4-5 e+e^5\right) & \frac{1}{20} \left(4-5 e+e^5\right) & \frac{1}{20} \left(4-5 e+e^5\right) \\ \frac{1}{5} \left(1-e^5\right) & \frac{1}{20} \left(4-5 e+e^5\right) & \frac{1}{20} \left(4+15 e+e^5\right) & \frac{1}{20} \left(4-5 e+e^5\right) & \frac{1}{20} \left(4-5 e+e^5\right) \\ \frac{1}{5} \left(1-e^5\right) & \frac{1}{20} \left(4-5 e+e^5\right) & \frac{1}{20} \left(4-5 e+e^5\right) & \frac{1}{20} \left(4+15 e+e^5\right) & \frac{1}{20} \left(4-5 e+e^5\right) \\ \frac{1}{5} \left(1-e^5\right) & \frac{1}{20} \left(4-5 e+e^5\right) & \frac{1}{20} \left(4-5 e+e^5\right) & \frac{1}{20} \left(4-5 e+e^5\right) & \frac{1}{20} \left(4+15 e+e^5\right) \\ \end{array} \right)$$ where clearly the first column is the same as the first column of the exponential of $L_c$, given by $$\left( \begin{array}{ccccc} \frac{1}{5} \left(1+4 e^5\right) & \frac{1}{5} \left(1-e^5\right) & \frac{1}{5} \left(1-e^5\right) & \frac{1}{5} \left(1-e^5\right) & \frac{1}{5} \left(1-e^5\right) \\ \frac{1}{5} \left(1-e^5\right) & \frac{1}{5} \left(1+4 e^5\right) & \frac{1}{5} \left(1-e^5\right) & \frac{1}{5} \left(1-e^5\right) & \frac{1}{5} \left(1-e^5\right) \\ \frac{1}{5} \left(1-e^5\right) & \frac{1}{5} \left(1-e^5\right) & \frac{1}{5} \left(1+4 e^5\right) & \frac{1}{5} \left(1-e^5\right) & \frac{1}{5} \left(1-e^5\right) \\ \frac{1}{5} \left(1-e^5\right) & \frac{1}{5} \left(1-e^5\right) & \frac{1}{5} \left(1-e^5\right) & \frac{1}{5} \left(1+4 e^5\right) & \frac{1}{5} \left(1-e^5\right) \\ \frac{1}{5} \left(1-e^5\right) & \frac{1}{5} \left(1-e^5\right) & \frac{1}{5} \left(1-e^5\right) & \frac{1}{5} \left(1-e^5\right) & \frac{1}{5} \left(1+4 e^5\right) \\ \end{array} \right).$$ It's easy enough to see that this works for a generic $n$, as the dependance of the coefficients on $n$ is straightforward. A simpler example is the path graph on three vertices, which gives $$\left( \begin{array}{ccc} \frac{1}{6} \left(2+3 e+e^3\right) & \frac{1}{3} \left(1-e^3\right) & \frac{1}{6} \left(2-3 e+e^3\right) \\ \frac{1}{3} \left(1-e^3\right) & \frac{1}{3} \left(1+2 e^3\right) & \frac{1}{3} \left(1-e^3\right) \\ \frac{1}{6} \left(2-3 e+e^3\right) & \frac{1}{3} \left(1-e^3\right) & \frac{1}{6} \left(2+3 e+e^3\right) \\ \end{array} \right)$$ to be compared with the $3\times 3$ $e^{L_c}$ matrix.

1

There are 1 best solutions below

9
On BEST ANSWER

Okay, so after fiddling around with it for a bit, I got a proof. It can perhaps be made a little bit shorter. Also, everything should go through with the $-it$ term, but I didn't include this in the proof.

We begin with a lemma which provides a necessary condition on the first column of $A$ in $B$.

Lemma Let $A$ and $B$ be symmetric matrices with the same first column, denoted $v = A e_1 = B e_1$. If $A v = B v = \alpha v$ for some $\alpha \in \mathbb{R}$, then $\exp(A)$ and $\exp(B)$ have the same first column.

Proof Recall that the matrix exponential is defined as $$\exp (A) = I + A + \frac{1}{2} A^2 + \frac{1}{6} A^3 + \dots = \sum_{k=0}^\infty \frac{1}{k!} A^k$$ Using this, we have that the first column of $\exp(A)$ is given by $$ \exp (A) e_1 = \sum_{k=0}^\infty \frac{1}{k!} A^k e_1 = I e_1 + \sum_{k=1}^\infty \frac{1}{k!} A^k e_1 = e_1 + \sum_{k=1}^\infty \frac{1}{k!} A^{k-1} v .$$ The same argument may be used to obtain the first column of $\exp(B)$. Note that the first term $e_1$ is independent of the matrix being exponentiated. Thus, by canceling this common term, we have that the first column of $\exp(A)$ is equal to the first column of $\exp(B)$ if and only if $$ \sum_{k=1}^\infty \frac{1}{k!} A^{k-1} v = \sum_{k=1}^\infty \frac{1}{k!} B^{k-1} v $$ We now show that the corresponding terms in both series are equal by induction on $k$. The base case of $k=1$ follows as $$A^{k-1} v = A^{0} v = I v = B^{0} v = B^{k-1} v.$$ Suppose that for each $k \leq r$, $A^{k-1} v = B^{k-1} v$. Then for $k=r+1$ with $r \geq 1$, \begin{align} A^{(r+1)-1} v &= A^{r} v \\ &= A^{r-1} (A v) \\ &= A^{r-1} (\alpha v) &\text{(By assumption, $Av = \alpha v$)}\\ &= \alpha (A^{r-1} v) \\ &= \alpha (B^{r-1} v) &\text{(inductive hypothesis)}\\ &= B^{r-1} (\alpha v) \\ &= B^{r-1} B v &\text{(By assumption, $Bv = \alpha v$)}\\ &= B^r v\\ &= B^{(r+1)-1} v \end{align} Thus, we have shown that all terms in the series are equal, so that the first columns of $\exp(A)$ and $\exp(B)$ are equal. $\square$

The last thing we need is the following claim, which makes use of Laplacian matrices. I'll leave it as an exercise to prove since it's very similar to the fact that the all ones vector $\mathbf{1}$ is an eigenvector with eigenvalue $0$.

Claim If $L$ is a Laplacian matrix whose first row/column is $v = \begin{pmatrix} n-1, & -1, & -1, & \dots, & -1 \end{pmatrix}$, then $L v = n \cdot v$.