I am given a finite set of orthogonal matrices $T_1,...,T_m\in\mathrm{O}(n)$, and I wonder how to compute a basis of an invariant subspace, i.e. a subspace $V\subseteq\Bbb R^n$ so that for all $i\in\{1,...,m\}$ we have
$$v\in V\;\implies\; T_iv\in V.$$
Notes
- I am looking for an algorithm to do this computationally!
- Actually, the orthogonal matrices are given to me via a (reducible) linear representation $\rho:G\to\mathrm{GL}(n,\Bbb R)$ of a finit group $G$. So the algorithm might use that the matrices form a matrix group. Especially, I am given $\rho$ as a black box function and $G$ by some generators.
- It would be especially nice if the invariant subspace would be minimal, but as long as it is proper and non-zero I can live with that.
From $n = 5$, the subgroups of $O(n)$ may be very complicated.
Firstly, we can have a look on the common invariant subspaces of $2$ matrices $A,B\in M_n$ where $A$ has simple eigenvalues; yet, the known algorithm (cf. M. Tsatsomeros or A. Georges-K.D. Ikramov) has exponential complexity and works only until $n=12$.
Here you know a generator of $G$ that is constituted with permutations $\sigma$ (if I correctly understand). Then it "suffices" to know how to obtain the invariant spaces of such a permutation matrix $A=[a_{i,j}]$ where $a_{\sigma(i),i}=1$. We can decompose $\sigma=c_1\circ\cdots\circ\sigma_k$ in disjoint cycles (with the cycles of length $1$). Then $\mathbb{R}^n=U_1\oplus\cdots\oplus U_k$ where $U_i$ is generated by the vectors of the canonical basis of indices $support(c_i)$ and, of course, is invariant; moreover $\chi_{A|_{U_i}}=x^l_i-1 $ (characteristic polynomial) where $l_i$ is the length of $c_i$. The eigenvalues of $A_{|U_i}$ are simple; so the invariant (real) subspaces of $A_{|U_i}$ are those generated by the eigenvectors associated to any subset $W$ of $Roots(x^l_i-1)$ under the condition that if $\lambda\in W$, then $\overline{\lambda}\in W$.
Among the invariant subspaces of $A$, there are the direct sums of the above susbspaces; unfortunately we don't obtain the entire set of invariant subspaces of $A$ (except if $k=1$; in particular, the first thing to do is to verify if some generator is a cycle; if yes, then the problem is solved because this generator has only a finite number of invariant spaces). Indeed, there are $2$ problems:
Firstly, the eigenvalue $1$ is common to each $i\leq k$. Then if $k>1$, then there are an infinity of invariant spaces.
Secondly, there may exist other common factors between some of the $\chi_{A|_{U_i}}$ (for example, if $2$ cycles have same length).