The common invariant subspace problem: an approach via Grobner bases

Let A be an n x n matrix. It is a relatively simple process to construct a homogeneous ideal (generated by quadrics) whose associated projective variety parametrizes the one-dimensional invariant subspaces of A. Given a finite collection of n x n matrices, one can similarly construct a homogeneous ideal (again generated by quadrics) whose associated projective variety parametrizes the one-dimensional subspaces which are invariant subspaces for every member of the collection. Grobner basis techniques then provide a finite, rational algorithm to determine how many points are on this variety. In other words, a finite, rational algorithm is given to determine both the existence and quantity of common one-dimensional invariant subspaces to a set of matrices. This is then extended, for each d, to an algorithm to determine both the existence and quantity of common d-dimensional invariant subspaces to a set of matrices. (C) 2004 Published by Elsevier Inc.