Complexity of finding fixedpoint

Suppose I have a fixed $n$-dimensional vector space $V$ over a field $F$ and I have a sequence of $n'$-linear transformations $G_i:V\rightarrow V$, $i \leq n'$. Further suppose I know that there is a (unique) subspace $V^*\subseteq V$ (of say dimension $m$) such that for all $i \leq n'$, $G_i|_{V^*}:V^* \rightarrow V^*$, i.e. each $G_i$ maps the subspace $V^*$ to itself.

Are there any good algorithms known for finding $V^*$ and if so what is the best known algorithm (in any of the parameters $n, n', m$) for finding such a $V^*$?

What if we no longer assume $F$ is a field but rather allow any semiring.

Thanks.

-

migrated from crypto.stackexchange.comJul 31 '13 at 14:55

This question came from our site for software developers, mathematicians and others interested in cryptography.

Can you say anything about the connection to cryptography? – D.W. Jul 29 '13 at 23:42
I am going to migrate your question to Math.SE in the hopes of generating more interest and discussion. Hope that helps you. – mikeazo Jul 31 '13 at 14:54

Generically, this should be easy to do, especially knowning that $V^*$ is unique of dimension $m$. A useful tool to address this problem is the Jordan Normal Form of a matrix (see http://en.wikipedia.org/wiki/Jordan_normal_form). The relevant fact is that for any linear transformation $L$, each Jordan block in the Jordan normal form decomposition is invariant by $L$ and conversely each invariant subspace of $L$ is a direct sum of Jordan blocks.

In fact, since your linear transformations are defined over an arbitrary field (non necessarily algebraically closed), some eigenvalues may belong to an extension of basefield. To avoid working with extension fields, you need to use the generalized Jordan form (it is implemented in magma).

Since you have several linear transformations $G_i$ with $V^*$ as invariant subspace, any linear combination of $G_i$s also has $V^*$ as invariant subspace. I would propose the following algorithm: Take $G$ a random linear combination of $G_i$s and compute its generalized Jordan form. With some luck, you obtain a generalized Jordan block of dimension $m$ (invariant under $G$) which is a nice candidate for $V^*$ and can be easily tested.

Caveat: I have not programmed the approach and it is probably possible to devise special cases where $V^*$ will never appear as a single Jordan block, which would complicate things. However, in general, this seems to be a nice and quite efficient solution to your problem.

-
Can the same approach be used in order to identify a map $J:V_k \rightarrow V$ (all elements from the domain map to the same range element) – curious Jul 28 '13 at 19:48
@curious If $V_k$ is not $V$, how do you define an invariant subspace ? – minar Jul 28 '13 at 20:02
Where does "your linear transformations are defined over a finite field" come from? $\hspace{.85 in}$ – Ricky Demer Jul 28 '13 at 20:49
@RickyDemer Sorry, I meant an arbitrary field (not necessarily algebraically closed). If the field is algebraically closed a regular Jordan form is enough. Will fix that. – minar Jul 28 '13 at 21:03
@curious Are your maps linear ? If so, the only possible point $m$ is the origin and the corresponding subspace is the kernel of each $V_k$. If not, may be you could write a different question giving more details. – minar Jul 29 '13 at 7:30