How to find all orthogonal matrices which commute with a given symmetric matrix? Suppose we have a symmetric matrix $H$. I'd like to find all the orthogonal matrices $S_i$, which commute with it. Particularly I'm interested in the set of $S_i$, which are linearly independent from the others in the set.
Currently to find the first such matrix I just minimize the difference $SH-HS$ with the constraint that $SS^T=I$. But even for not too large matrices like $16\times16$ this takes quite a lot of time to minimize it.
Are there any efficient numerical procedures to find these matrices?
 A: Since $H$ is symmetric (and I'm assuming it has real entries as well), then by the spectral theorem, $H$ can be orthogonally diagonalized; i.e. it has an orthogonal set of eigenvectors such that $H = Q\Lambda Q^T$ where the columns of $Q$ are eigenvectors of $H$ and $\Lambda$ is a diagonal matrix of the corresponding eigenvalues of $H$. The commutator is then
$$ SQ\Lambda Q^T-Q\Lambda Q^TS $$
If you let $S = QM Q^T$ for a diagonal matrix $M$, then the commutator is identically zero. This is from here. I'm not sure this represents all the possible $S$ (as in, I'm not sure if the diagonal entries of $M$ completely parameterize the space of valid $S$, or how you would show that).
A: @ Ruslan , you ask (I am not sure !) for orthogonal matrices $(S_i)$ that are linearly independent, orthogonal and s.t. $S_iH=HS_i$. We may assume that $H=diag(\lambda_1I_{n_1},\cdots,\lambda_kI_{n_k})$ where the $(\lambda_i)$ are real distinct and $n_1+\cdots +n_k=n$. Then $SH=HS$ iff $S=diag(U_1,\cdots,U_k)$ where $U_i$ is orthogonal. We reduce the problem to choose linearly independent elements in $O(n)$.
Note that $\begin{pmatrix}0&1&0\\1&0&0\\0&0&1\end{pmatrix}+\begin{pmatrix}0&1&0\\-1&0&0\\0&0&-1\end{pmatrix}=\begin{pmatrix}0&2&0\\0&0&0\\0&0&0\end{pmatrix}$. Then the pseudo-permutation matrices (and consequently $O(n)$) span $M_n(\mathbb{R})$ and we can choose $n^2$ linearly independent pseudo-permutation matrices. I think that you can find explicitly such a system of matrices for every $n$ ; it is your business.
EDIT. Answer to Ruslan. 1. The $S_i$ are pseudo-permutations  (entries are $\pm 1$).


*among the previous matrices, you can choose $n^2$ that are linearly independent. Now you must find such a model for each value of $n$. For instance, if $n=2$, then you can take $\begin{pmatrix}1&0\\0&1\end{pmatrix},\begin{pmatrix}1&0\\0&-1\end{pmatrix},\begin{pmatrix}0&1\\-1&0\end{pmatrix},\begin{pmatrix}0&1\\1&0\end{pmatrix}$.

A: Try to solve first for $H$ block diagonal, with the blocks on the diagonal scalar matrices.
If you can solve it for this case, you can in general. 
