I am looking for a (hint of) a proof for the following relation:
let $\mathbf{M} = \begin{pmatrix} \mathbf{I}-\epsilon\mathbf{L} & -\epsilon\mathbf{L}\\ \epsilon\mathbf{L} & \mathbf{I} \end{pmatrix},$
if $\epsilon\le\frac{1}{\max(\text{eig}\left(\mathbf{L}\right))}$, then all the eigenvalues of $\mathbf{M}$ are on or within the unit circle.
$\mathbf{L}$ is the graph Laplacian of a communication graph (here undirected and connected), $\mathbf{I}$ is the identity matrix of the same dimension than $\mathbf{L}$, $0\le\epsilon\le1$ is a scalar, and $\text{eig}\left(\mathbf{L}\right)$ is the list of eigenvalues of $\mathbf{L}$.
If I set $\epsilon$ larger than this bound, then some eigenvalues of $\mathbf{M}$ are outside the unit circle. If I set $\epsilon$ lower than this bound, the largest eigenvalue(s) of $\mathbf{M}$ are on the unit circle. I found this result playing with numerical values in Matlab, and tested it for numerous $\mathbf{L}$ and $\epsilon$. However I fail to prove this relation mathematically. Any hint?
The eigenvalues of $\mathbf{L}$ are real, those of $\mathbf{M}$ are complex.
I tried by defining $\mathbf{A}=\begin{pmatrix}\mathbf{L} & \mathbf{L} \\ -\mathbf{L} &\mathbf{0}\end{pmatrix}$, knowing that $\text{eig}(\mathbf{M})=-\epsilon\cdot \text{eig}(\mathbf{A})+1$, and applying the rules for block-matrix determinant, but I am stuck at $\text{det}(\mathbf{A}-\lambda\mathbf{I})=\text{det}(-\lambda\mathbf{L}+\lambda^2 \mathbf{I}+\mathbf{L}^2)=0$.
Starting from your last point, I believe $L$ is symmetric positive semidefinite so that it is diagonalizable, write
$$ L = PDP^{-1}$$
then you can write
$$ A-\lambda I = \left(\begin{array}{cc}P & \\ & P\end{array}\right)\left(\begin{array}{cc}D-\lambda I&D\\-D&-\lambda I\end{array}\right)\left(\begin{array}{cc}P^{-1} & \\ & P^{-1}\end{array}\right)$$
(the $I$ on the lhs and on the RHS have appropriate dimensions) then the determinant simplifies since the matrix on the right and on the left are inverse so that you're left with the determinant of what's in the middle.
Looking up properties of determinant of block matrices (I must admit I checked on wikipedia), we are in the case where all the blocks are of the same size and the upper left and bottom right one commute so that the determinant of $A-\lambda I$ is actually equal to
$$\det(A-\lambda I) = \det ((D-\lambda I)(-\lambda I) + D^2)$$
on the rhs we have a diagonal matrix so that the determinant is simply the product of entries or:
$$ \prod_i ( d_i^2 + \lambda^2 - \lambda d_i) $$
where $d_i$ are the eigenvalues of $L$. The eigenvalues are therefore
$$ {d_i(1 \pm \sqrt{3}i)\over 2}$$
the modulus of the factor is ... 1 and I think that's it.