Let $V$ denote a finite set $(v_1, \ldots, v_n)$ and $G=$ $(V, E)$ denote a non-oriented connected graph, i.e., $E \subset V \times V$ and $(v, v^{\prime}) \in E \implies (v^{\prime}, v) \in E$ and for any $v, v^{\prime}$ there always exists a path $(v_0, \ldots, v_N)$ with $v_0=v, v_N=v^{\prime}$ and $(v_i, v_{i+1}) \in E$ for all $i=0, \ldots, N-1$. We introduce the following notations:
- The adjacency matrix $A \in \mathbb{R}^{n \times n}$ is defined by $A_{i j}=1$ if $(v_i, v_j) \in E, 0$ otherwise.
- The degree matrix $D \in \mathbb{R}^{n \times n}$ is the diagonal matrix defined by $D_{i i}=\sum_{j=1}^n A_{i j}$.
- The Laplacian matrix of $G$ is the matrix $L:=D-A \in \mathbb{R}^{n \times n}$.
- Given a square matrix $M \in \mathbb{R}^{n \times n}$, we let $\exp (M):=\sum_{k \geq 0} \frac{M^k}{k!}$ denote the usual exponential of a matrix.
Let $f_0 \in \mathbb{R}^n$ be a $n$-dimensional vector (that can be understood as assigning values on the nodes of $G$). Consider the discrete diffusion equation on $\mathbb{R}^n$ defined as $$\partial_t f(t)=-L f(t)$$ with $f(0)=f_0$. we can easily show that $f(t)=f_0 e^{-t L}$ is a solution of this equation.
Moreover, we also have that $L$ is a symmetric, positive semi-definite matrix.
Problem: How to deduce that for any $t>0$, $K_t:=e^{-t L}$ defines a PSD kernel on $G$ (formally, the kernel is $(v_i, v_j) \mapsto(K_t)_{i j}$). This kernel is called the heat kernel on $G$ with temperature $t$.
I tried to check to properties of a PSD kernel but it doesn’t work. Particularly,
Symmetricity: I said that since $L$ is symmetric then $K_t$ is symmetric.
The second property of kernel: I don’t know how to prove it.
Since you have already shown that $K_t$ is symmetric, showing that $K_t$ is positive semidefinite is a simple matter of showing that its eigenvalues are positive.
The positivity of the eigenvalues of $K_t$ is an immediate consequence of the properties of the matrix exponential: for any matrix $M$, the eigenvalues of $\exp(M)$ are given by $\exp(\lambda)$ for all eigenvalues $\lambda$ of $M$. Because $-tL$ is symmetric, any eigenvalue $\lambda$ of $-tL$ must be real (and in this case non-positive because of the properties of $L$), which means that the corresponding eigenvalue $e^{\lambda}$ of $K_t = \exp(-tL)$ is positive.