  In this paper, we consider the feasibility of linear interference alignment
(IA) for multiple-input multiple-output (MIMO) channels with constant
coefficients for any number of users, antennas and streams per user; and
propose a polynomial-time test for this problem. Combining algebraic geometry
techniques with differential topology ones, we first prove a result that
generalizes those previously published on this topic. Specifically, we consider
the input set (complex projective space of MIMO interference channels), the
output set (precoder and decoder Grassmannians) and the solution set (channels,
decoders and precoders satisfying the IA polynomial equations), not only as
algebraic sets but also as smooth compact manifolds. Using this mathematical
framework, we prove that the linear alignment problem is feasible when the
algebraic dimension of the solution variety is larger than or equal to the
dimension of the input space and the linear mapping between the tangent spaces
of both smooth manifolds given by the first projection is generically
surjective. If that mapping is not surjective, then the solution variety
projects into the input space in a singular way and the projection is a
zero-measure set. This result naturally yields a simple feasibility test, which
amounts to checking the rank of a matrix. We also provide an exact arithmetic
version of the test, which proves that testing the feasibility of IA for
generic MIMO channels belongs to the bounded-error probabilistic polynomial
(BPP) complexity class.
