  We study spectral approaches for the MAX-2-LIN(k) problem, in which we are
given a system of $m$ linear equations of the form $x_i - x_j \equiv c_{ij}\mod
k$, and required to find an assignment to the $n$ variables $\{x_i\}$ that
maximises the total number of satisfied equations.
  We consider Hermitian Laplacians related to this problem, and prove a Cheeger
inequality that relates the smallest eigenvalue of a Hermitian Laplacian to the
maximum number of satisfied equations of a MAX-2-LIN(k) instance $\mathcal{I}$.
We develop an $\widetilde{O}(kn^2)$ time algorithm that, for any
$(1-\varepsilon)$-satisfiable instance, produces an assignment satisfying a
$\left(1 - O(k)\sqrt{\varepsilon}\right)$-fraction of equations. We also
present a subquadratic-time algorithm that, when the graph associated with
$\mathcal{I}$ is an expander, produces an assignment satisfying a $\left(1-
O(k^2)\varepsilon \right)$-fraction of the equations. Our Cheeger inequality
and first algorithm can be seen as generalisations of the Cheeger inequality
and algorithm for MAX-CUT developed by Trevisan.
