Determinant of a symmetric zero-diagonal matrix I am trying to write an algorithm which computes determinants of $n\times n$ real-symmetric matrices of the form 
$$\mathbf S = \begin{pmatrix}
0 & a_{1,1} & a_{1,2} & a_{1,3} & \cdots  &a_{1,n-1}\\
a_{1,1} & 0 & a_{2,1} & a_{2,2} & \cdots& a_{2,n-2}\\
a_{1,2} & a_{2,1} & 0 & a_{3,1} & \cdots& a_{3,n-3}\\
a_{1,3} & a_{2,2} & a_{3,1} & 0& \cdots& a_{4,n-4}\\
\vdots & \vdots & \vdots& \vdots& \ddots &\vdots\\
a_{1,n-1}&a_{2,n-2}& a_{3,n-3} & a_{4,n-4} & \dots &0
\end{pmatrix}$$
which are to be encoded in the form $\{\{a_{1,1},a_{1,2},\dots,a_{1,n-1}\},\{a_{2,1},a_{2,2},\dots,a_{2,n-2}\},\dots,\{a_{n-1,1}\}\}$.
For example, the encoding {{1,2,3},{4,5},{6}} corresponds to the $4\times 4$ matrix
$$ \begin{pmatrix}
0&1&2&3\\
1&0&4&5\\
2&4&0&6\\
3&5&6&0
\end{pmatrix}.
$$
Is there a way of efficiently finding the eigenvalues of $\mathbf S$, or, alternatively, finding the number of distinct eigenvalues, by taking advantage of its symmetric properties?
The only way I've managed so far is to compute is to evaluate $\det(\mathbf S - \mu \mathbf I)$ by treating $a_{i,j} = a_{j,i}$, but this is still $O(\frac{n^2}{2})$, i.e. $O(n^2)$.
 A: You won't be able to do anything that's asymptotically better than an algorithm for computing general determinants (which is $O(n^3)$ the easy way, though there are algorithms that are $O(n^k)$ for $k \approx 2.373$). The reason for this is that a special case of your problem is finding the determinant of a block matrix of the form
$$ \begin{bmatrix} 0 & A \\ A^T & 0\end{bmatrix} = \begin{bmatrix} 0 & 0 & \cdots & 0 &a_{1,n/2} & a_{1,n/2+1} & \dots & a_{1,n-1} \\ 
0 & 0 & \cdots & 0 & a_{2,n/2} & a_{2,n/2+1} & \dots & a_{2,n-1} \\
\vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & 0 & a_{n/2,n/2} & a_{n/2, n/2+1} & \cdots & a_{n/2, n-1} \\
a_{1,n/2} & a_{2,n/2} & \cdots & a_{n/2,n/2} & 0 & 0 & \cdots & 0 \\
a_{1,n/2+1} & a_{2,n/2+1} & \cdots & a_{n/2, n/2+1} & 0 & 0 & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\
a_{1,n-1} & a_{2,n-1} & \cdots & a_{n/2,n-1} & 0 & 0 & \cdots & 0\end{bmatrix}$$
and this determinant simplifies to $(-1)^n \det(A)^2$, so computing it is as hard as computing the determinant of $A$, an arbitrary $\frac n2 \times \frac n2$ matrix.
