Paper accepted at ISIT 2013

Ó. González, I. Santamaría, C. Beltrán, "Finding the Number of Feasible Solutions for Linear Interference Alignment Problems," IEEE Int. Symposium on Information Theory, Istanbul, July 2013.

Abstract
In this paper, we study how many different solutions exist for a feasible interference alignment (IA) problem. We focus on linear IA schemes without symbol extensions for the K-user multiple-input multiple-output (MIMO) interference channel. When the IA problem is feasible and the number of variables matches the number of equations in the polynomial system, the number of solutions is known to be finite. Unfortunately, the exact number of solutions is only known for a few particular cases, mainly single-beam MIMO networks. In this paper, we proof that the number of IA solutions is given by an integral formula that can be numerically approximated using Monte Carlo integration methods. More precisely, the number of solutions is the scaled average over a subset of the solution variety (formed by all triplets of channels, precoders and decoders satisfying the IA polynomial equations) of the determinant of a certain Hermitian matrix related to the geometry of the problem. Our results can be applied to arbitrary interference MIMO networks, with any number of users, antennas and streams per user.