The signed permutation matrices (SPMs) are permutation matrices except that you can use -1 instead of 1. Ie. they are matrices with just one non-zero entry in each row and each column and that entry is 1 or -1.
SPMs form a finite group so their eigenvalues must lie on the unit circle.
But what about the sum of two SPMs? Here's a plot of the eigenvalues of the sums of 2 8x8 SPMs.
(Sorry, top and bottom cropped, Mathematica has trouble plotting a million points even though seems like a pretty small number to me.)
Code:
u[d_] := (2 RandomInteger[{0, 1}, d] - 1) IdentityMatrix[d][[
PermutationReplace[Range[d], RandomPermutation[d]]]]
z = Flatten[
Parallelize[
Table[Eigenvalues[u[8] + u[8]/4] // N, {i, 1, 500000}]]];
ListPlot[Transpose[{Re[z], Im[z]}], PlotStyle -> Opacity[0.0025],
AspectRatio -> 1]