Dear Peter!

Many thanks for your voting.

I'm running now a research on efficient ways to solve multivariable polynomial equations over finite fields. If an efficient method to compute all the small invariant subsapces of a matrix A could be found, then I can show an efficient way to solve multivariable polynomial equations, by means of reduction. This way seems to be more efficient than computing Grobner bases, because it starts from bottom-up (but it is only an intuition).

If you want to join this research - I will be happy!

I'm running now a research on efficient ways to minimum number of H-free graphs, one can show an efficient way to compute efficeintly all the invariant small subspaces of a matrix A over a finite field . You can be proved that an eigenvector of the matrix restricted to the invariant subspace is an eigenvector of the full matrix.

Recall the following fact.  Let A be a linear operator on a vector space V (over any field), and let v be a nonzero vector in V. Then A-cyclic subspace Lv is the smallest A-invariant subspace that contains v.

I see Prof. Wiwat gave you an option. You can use the "Lemma of the kernels "=Lemme des noyaux, i.e. find the characteristic polynomial or the minimal one, then decompose it to a product of powers of primes over the finite field you deal with, then you get a dircet sum of invariant spaces, form that you can extract all invariant spaces according to their dimensions.

of course the problem will appear with the decomposition  over a finite field, it is not easy enough. 

Dear Wiwat and dear Hanifa !

Many thanks for your helpful answers.

Following your answers, I have the next questions:

Is it true that any invariant subspace is generated by a single vector ?

If yes, how can one find efficiently (i.e. without passing over all the vectors in the vector space) such a vector for any invariant subspace with dimension not exceeding n_{0} ? (where n_{0}

Dear Peter !

Many thanks for your answers.

But, I dont understand: what if the given finite field is not algebraically closed ?

Then, the characteristic polynomial of A might be a prime polynomial and there is no eigenvalue in the given field. Does it says that there are no invariant subspaces except the trivial ones, in that case ?

For example, take a 3X3 matrix A with charcteristic polynomial x^{3}+x+1 over F_{2}.

You claim that auch matrix A would not have any invariant subspace execpt {(0,0,0)^{T}} and F_{2}^{3} !?

Again, many thanks for your help !

Dear Yossi,

Form your above questions: Is it true that any invariant subspace is generated by a single vector ?

No, it is not true, see for example; p.507, Theorem 1 (e) of the following attachment.

http://www.sciencedirect.com/science/article/pii/002437959090358J

Dear Peter and dear Wiwat !

For A=[0 0 1;0 1 1;1 1 1] over F_{2} we have x^{3}+x+1 as characteristic polynomial and indeed the only invariant subspaces are {0} and F_{2}^{3}. There are no eigenvalues and no eigenspaces.

Let me now sharpen my question (thanks to you guys I am able to do that):

Is it true that the smallest invariant suspaces (in terms of inclusion) are the cyclic subspaces ?

Is it true that any invariant subspace is a direct sum of cyclic subspaces ?

I would appreciate it of you could supply some references for your answers.

Many Thanks For Your Help !