# Full text of "Interference alignment for the MIMO interference channel"

## See other formats

Interference alignment for the MIMO interference channel Guy Bresler, Dustin Cartwright, David Tse Abstract — We study vector space interference alignment for the MIMO interference channel with no time or frequency diversity. We prove both necessary and sufficient conditions for alignment. In particular, we characterize the feasibility of alignment for the symmetric three-user channel where all transmitters have M antennas and all receivers have N antennas, as well as feasibility of alignment for the fully symmetric (M — N) channel with arbitrary number of users. An implication of our results is that the total degrees of freedom available in a K-user interference channel, using only spatial diversity from the multiple antennas, is at most 2. This is in sharp contrast to the y degrees of freedom shown to be possible by Cadambe and Jafar with arbitrary large time or frequency diversity. Moving beyond the question of feasibility, we addition- ally discuss computation of the number of solutions using Schubert calculus in cases where there are a finite number of solutions. Index Terms — interference channel, interference align- ment, feasibility of alignment, algebraic geometry I. Introduction Interference is a key bottleneck in wireless com- munication networks of all types: whenever spectrum is shared between multiple uncoordinated users, each user must deal with undesired signals. Current wireless systems avoid interference by either orthogonalizing the users across time or frequency or sharing the same resource while treating other users' signals as noise. If there are K users in the system, these approaches This work was presented in part at the Information Theory Work- shop (ITW) |1] and the Allerton conference |2|, both in 2011. G.B. and D.T have been supported by the Center for Science of Information (CSol), an NSF Science and Technology Center, under grant agreement CCF-0939370. D.C. began work on this project while he was a postdoc at the Mittag-Leffler institute during the program on "Algebraic geometry with a view towards applications." Since then, he has been supported by NSF grant DMS- 1103856. G.B. is currently at LIDS, Dept. of EECS, MIT. Most of the work in this paper was done when he was at UC Berkeley, (email: gbresler @ mit.edu) D.C. is currently at the Dept. of Mathematics, Yale, (email: dustin.cartwright@yale.edu) D.T. is at Wireless Foundations, Dept. of EECS, UC Berkeley, (email: dtse@eecs.berkeley.edu) result in (at best) a fraction 1/K oi the total resource being available to each user. Interference alignment is one recent development (among others, such as hier- archical MIMO [3]) that has opened the possibility of significantly better performance in interference-limited communications than traditionally thought possible. The basic idea of interference alignment is to align multiple interfering signals at each receiver in order to reduce the effective interference. Interference alignment was first introduced by Maddah-Ali et al. |4] for the multiple-input multiple-output (MIMO) X channel and subsequently by Cadambe and Jafar in the context of the iT-user interference channel, which is also the subject of our paper. Candambe and Jarfar established the suprising result that y degrees of freedom are achievable for the K-user Gaussian interference channel, assuming the channels have unbounded diversity in the form of time or frequency variation Q. Most practical systems are also equipped with mul- tiple antennas and thus have spatial diversity. Multiple antennas are known to greatly increase the degrees of freedom of point-to-point systems. In this paper we focus on how spatial diversity helps to deal with in- terference by studying interference alignment for the MIMO inteference channel. In order to focus on the effect of spatial diversity, we assume there is no time or frequency diversity, i.e. the channel is constant over time and frequency. We assume that we have K transmitter-receiver pairs, which we will call users, and each transmitter wishes to communicate with its opposite receiver. We let and Ni denote the number of antennas of the ith trans- mitter and the ith receiver respectively Like [5], we study vector space strategies for interference alignment. In this case, the alignment problem reduces to finding vector spaces Ui C C M ' and Vi C C^' where dim f/j = dimVi is denoted di, and such that HMUjlVi, l<i,j<K, i^j, (1) where the matrix Hwl G C N i xM i depends on the channel between transmitter j and receiver i. For the rest of the paper, we assume that the are generic, meaning that their entries lie outside of some algebraic 2 hypersurface, which depends only on the parameters di, Mi, and iVj. If the entries are randomly chosen from some non-singular probability distribution, this will be true with probability 1. Our goal is to maximize the signal dimensions di subject to the constraint that there exist vector spaces satisfying ([1]). Yetis et al. H proposed comparing the number of variables and equations in the system of bilinear equations ([T} in order to determine when it has solutions. We make this precise by showing that the feasible solutions are an algebraic variety of the "expected" dimension, when the channel matrices are generic. Thus, we have the following necessary condition for interference alignment: Theorem 1. Fix an integer K and integers di, Mi, and Ni for 1 < i < K and suppose the channel matrices H^l are generic. If, for any subset A C {1, . . . , K}, the quantity t A = Y,( d ^ N i- d i) + d ^ M i- d i))- did r is negative, then there are no feasible strategies. More- over, if there are feasible strategies, then tsx,...,K\ * J me dimension of the variety of solutions. The constraint on t{i was obtained independently and simultaneously by Razaviyayn et al. Q. The dimension of the variety of solutions is important, because when multiple strategies are feasible, we may wish to optimize over the feasible strategies according to some other criterion, such as the robustness of the system. The necessary condition from Theorem [T] is not suffi- cient. One, almost trivial, requirement for there to even exist vector spaces is that di < Mi and di < Ni for each i. In fact, this is the r = case of the following, less obvious constraint: Theorem 2. Fix a non-negative integer r and let , i r +2 be a sequence of indices, such that each consecutive triple consists of three distinct indices, i.e. 7^ ij+if or 1 — 3 — r + l and ij 7^ ij+2 for 1 < j < r. Also, assume that if ij = iy then ij+x 7^ ij'+2- Suppose that Ni. is the same for all 1 < j < r, which we denote N, and similarly M{. = M for 2 < j < r+2. In order for interference alignment to be feasible, we must have: r r+2 di, +^ j d ij < max(riV, (r + 1)M) 3=1 J=2 d 2d 3d 4d Fig. 1 . For a fixed value of d, the feasible region in the M, N plane is white while the infeasible region is shaded. The labels 1, 2, 3, 4, . . . indicate the maximum length of alignment paths for M, N in the corresponding region. When r is positive, we can rewrite the left-hand side: r d i± + d ir+1 + d ir+2 +2^2d ir < max(riV, (r + 1)M) j=2 Symmetrically, Theorem [2] also holds with the roles of M and N reversed. In the r = 1 case, a somewhat stronger constraint, with possibly unequal transmit di- mensions also holds: Theorem 3. For any distinct indices i, j, and k, the feasibility of inteference alignment requires di + dj +d k < max(iVi, Mj + M k ) In the case of 3 users, Theorem [2] simplifies, because the only applicable sequences of indices are cycles through the 3 users. Corollary 4. Suppose that K = 3 and that N\ = N2 = N 3 = N and M x = M 2 = M 3 = M. If interference alignment is feasible, then for any positive integer r, r dx + d r+1 + d r+2 + 2 ^ d r < max(riV, (r + 1)M), i=2 where for i > 3, we define di to be dj, where i is the remainder of i when dividing by 3. Of course, Corollary [4] also holds for any reordering of the three users. Moreover, if we assume that the transmit dimensions di are all equal to some fixed d, 3 then the infeasible parameters correspond to the shaded ares of Figure [T] In fact, in this symmetric case, we have completely characterized the feasible region. Theorem 5. Let K = 3 and without loss of generality, we can assume that N > M. Then interference align- ment is feasible if and only if for each r > 0, (2r + l)d < max(riV, (r + 1)M) (2) Moreover, if, in addition, N + M = Ad, then there is a unique solution if N > M and there are ( 2 ^) solutions ifN = M = 2d. The sufficiency of these conditions has also been independently shown by Amir et al. [8], but only in the zero-dimensional case, when N + M = Ad. Also independently and simultaneously, Wang et al. @ have obtained results very similar to Theorem [5] Their neces- sary condition is information-theoretic, and thus, unlike ours, not limited to linear strategies. Theorem [5] is effective in the sense that the solutions can be obtained from basic operations in linear algebra. The reason that the K = 3 case is easy to analyze is that the constraints ([TJ, which always link a pair of vector space choices, form a cycle in the case of K = 3. When there are more users, we nonetheless have a sufficiency condition in the case when N = M: Theorem 6. Suppose that K > 3 and that d{ = d and Mi = Ni = N for all users i. Then, for generic channel matrices, there is a feasible strategy if and only if 2N > (K + l)d. This theorem was also acheived by Razaviyayn et al. d for the case that d divides N. In fact they found a distinct, but overlapping set of parameters for which they could characterize feasibility. Theorem 7 (Theorem 2 in 0). Suppose that d = di for all i and that Mi and Ni are divisible by d for all i. Then interference alignment is possible if and only if the quantities t& from Theorem [7] are non-negative for all subsets A. Rearranging the inequality of Theorem [6] we have that the number of transmit dimensions satisfies d < 2N K+r Corollary 8 (Fully symmetric achievable dof). The maximum normalized dof is given by max dot = — J N 2N K + l < 2 K K + l < 2. In sharp contrast to the y total normalized dof achiev- able for infinitely many parallel channels in @, for the MIMO case we see that at most two dof (normalized by the single-user performance of N transmit dimensions) are achievable for any number of users K and anten- nas N. Theorem [6] suggests an engineering interpretation for the performance gain from increasing the number of antennas. Depending on whether N < d{K + l)/2 or not, there are two different regimes for the performance benefits of increasing N: (1) alignment gain or (2) MIMO gain. To illustrate these concepts, suppose that there are K = 5 users. If N = 1, i.e. there is only a single antenna at each node, then no alignment can be done and only one user can communicate on a single dimension, giving 1 total degree of freedom. As the number of antennas increases to 2 and 3, the number of degrees of freedom becomes 3 and 5 respectively. Because of alignment, the total degrees of freedom increases more than linearly, which we call alignment gain. However, after N = 3, increasing N affords no additional possibilities for interference alignment, and the total number of degrees of freedom only because more dimensions are available. The MIMO gain has slope 5/3, which is the asymptotic coefficient as in Corollary [8] Unlike Theorem |5J the proof of Theorem [6] does not provide a way of computing the solutions. Instead of linear algebra, it uses Schubert calculus to prove the existence of solutions. In fact, we will see that there cannot be a simple, exact description of the symmetric interference alignment problem in Section [V] Nonethe- less, as we will discuss, solutions may be found using numerical algebraic geometry software. In addition to general algebraic methods of root find- ing, others have proposed heuristic algorithms, mainly iterative in nature (see El, O, EL El, and H3). Some have proofs of convergence, but no performance guarantees are known. Schmidt et al. lfl4l . |[T5l study a refined version of the single-transmit dimension problem, where for the case that alignment is possible, they attempt to choose a good solution among the many possi- ble solutions. Papailiopoulos and Dimakis [13] relax the problem of maximizing degrees of freedom to that of a constrained rank minimization and propose an iterative algorithm. In a different direction of inquiry, Razaviyayn et al. [12] show that checking the feasibility of alignment for general system parameters is NP-hard. Note that their result is not in contradiction to ours, since our simple closed-form expression applies only to the fully symmetric case. Finally, we want to emphasize that our attention has been restricted to vector space interference alignment, where the effect of finite channel diversity can be more 4 easily observed. Interfering signals can also be aligned on the signal scale using lattice codes, which was first proposed in ||T6| with followup work in ifTTI . [18], and |[T9l . However, the understanding of this type of alignment is currently at the stage corresponding to infinite parallel channels in the vector space setting. In other words, essentially "perfect" alignment is possible due at infinite signal-to-noise ratios. See [20] and [21] for recent progress in this direction. The rest of the paper is outlined as follows. In Section Q]] we introduce the MIMO interference channel model and formulate the alignment feasibility problem. Section III derives necessary conditions for alignment, and Section IV gives sufficient conditions. Finally, Sec- tion [V] discusses computing the number of alignment solutions as well as how to compute the solutions them- selves. II. The MIMO interference channel The If- user MIMO interference channel has K trans- mitters and K receivers, with transmitter i having Mi antennas and receiver i having Ni antennas. For i = 1, . . . ,K, receiver i wishes to obtain a message from the corresponding transmitter i. The remaining signals from transmitters j ^ i are undesired interference. The channel is assumed to be constant over time, and at each time-step the input-output relationship is given by l<i<K. (3) ■<Ni Here for each user i we have Xj G C Mi and y,, Zj G with Xj the transmitted signal, yj the received signal, and z,i ~ CJ\f(0,lNi) is additive isotropic white Gaus- sian noise. The channel matrices are given by HM G C NiXM i for 1 < i,j < K, with each entry assumed to be independent and with a continuous distribution. We note that this last assumption on independence can be weakened significantly to a basic non-degeneracy condi- tion but we will not pursue this here. For our purposes this means the channel matrices are generic. Each user E r T\\2\ < P obeys an average power constraint, rj for a block of length T. We restrict the class of coding strategies to (lin- ear) vector space strategies. In this context, degrees-of- freedom has a simple interpretation as the dimensions of the transmit subspaces, described in the next paragraph. However, note that one can more generally define the degrees-of-freedom region in terms of an appropriate high transmit-power limit P — > oo of the Shannon capac- ity region C(P) normalized by logP (ffl, 0). In that general framework, it is well-known and straightforward that vector space strategies give a concrete non-optimal achievable strategy with rates Ri{P) = cUog(P) + O(l), l<i<K. Here di is the dimension of transmitter f s subspace and P is the transmit power. The transmitters encode their data using vector space precoding. Suppose transmitter j wishes to transmit a vector Xj G C dj of dj data symbols. These data symbols are modulated on the subspace Uj C C Mj of dimension dj, giving the input signal XJjXj, where XJj is a Mj x dj matrix whose columns give a basis of Uj. This signal is observed by receiver i through the channel as H^XJjij The dimension of the transmit space, dj, determines the number of data streams, or degrees-of- freedom, available to transmitter j. With this restriction to vector space strategies, the output for receiver i is given by Yi= Yl U ' flS r r J ■ ' l<i<K. (4) l<j<K The desired signal space at receiver i is thus H^C/j, while the interference space is the span of the undesired subspaces, i.e. Ylj^i^ -Uj. In the regime of asymptotically high transmit powers, in order that decoding can be accomplished we impose the constraint at each receiver i that the desired signal space H^Ui is complementary to the interference space S,yjH^i7j. Equivalently, receiver i must have a sub- space V{ with dim Vi = dim U{ such that nMUj±Vi, l<i,j<K, i^j, and dim(Proj l/ .H [l l Ui) =dimC/i. (5) (6) Here, H^C/j _L Vi means that the two vector spaces are orthogonal with respect to the standard Hermitian form on C N \ Equivalently, orthogonality means that all entries of vJh^Uj- are zero, where vj denotes the Hermitian transpose of a matrix whose columns form a basis of Vi. If each direct channel matrix has generic (or i.i.d. continuously distributed) entries, then the second condition ([6]) is satisfied assuming dimVi = di for each i (this can be easily justified — see (22] for some brief remarks). Hence we focus on condition ([5]). Our goal in this paper is to determine when interfer- ence alignment is feasible: given a number of users K, numbers of antennas M\,...,Mk and Ni, . . . ,Nk, and desired transmit subspace dimensions d\, . . . , dx, does there exist a choice of subspaces U\, . . . , Uk and V\,...,Vk with dim U{ = dim Vi = di satisfying ([5])? 5 III. Necessary conditions In this section, we prove the necessary conditions for interference alignment, Theorems [T] [2| and [3] The proof of Theorem [T] is by "counting equations," or, more precisely, by determining the dimension of the relevant algebraic varieties. The proofs of Theorems [2] and [3] use only linear algebra. For background on some of the concepts in algebraic geometry, see the texts by Hartshorne |f23l or Shafarevich ||24| . In practice, interference alignment requires finding the feasible communications strategies given the fixed channel matrices. However, it will be useful to think of the procedure in reverse: we fix the communication strategy and study the set of channels for which the communication strategy is feasible. As we will see in the proof of Lemma 10 the advantage here is that for a fixed strategy, the constraints on the channel matrices are linear. To make this approach precise, we will represent the space of strategies as a product of Grasmannians. Recall (for example from ll24l ) that the Grassmannian G(d, N) is the variety whose points correspond to d-dimensional subspaces of an iV-dimensional vector space C N . Thus, for each i, the transmit subspace Ui corresponds to a point in the Grassmannian, which we also write as Ui € G(di, Mi), and similarly Vi G G(di, Ni), where is the complex conjugate of V{. We choose to parametrize by the complex conjugate because the relation ([I]) is defined by algebraic equations in the basis of Vi, but not in Vi. The strategy space is thus the product of the Grassmannians, K K S = \\G{di,Mi) x Yl G{d h Ni) . i=l i=l Likewise, the relevant channel matrices are a tuple of K(K — 1) matrices, which we can represent as a point in the product U = £ N ^ M >. In the product S x T~L, we define the alignment variety to be the subvariety X C S x T~L of those ordered pairs (s, h) such that s is a feasible strategy for h. The dimensions of S and H are the sums of the dimensions of their factors, so K dimS = ^2(di{M l -di)+di{N i -d i )) , (7) i=i and dim Ti (8) 10 The dimension of X will be computed in Lemma using Theorem [9] which is a rough analogue of the rank nullity theorem from linear algebra. Given a map / : X — ^ Y, the fiber of a point y £ Y is the inverse image of y under the map /: f- l (y) = {xeX :f(x)=y}. A polynomial map is a function whose coordinates are given polynomials. Finally, an irreducible variety is one which can't be written as the union of two proper, closed subvarieties. The following theorem in algebraic geometry can be found, for example, as Theorem 7 on page 76 of d. Theorem 9 (Dimension of fibers). Let f : X — )> Y be a polynomial map between irreducible varieties. Suppose that f is dominant, i.e. its image is dense in Y. Let n and m denote the dimensions of X and Y respectively. Then m < n and: 1) For any y G f(X) C Y and for any component Z of the fiber f~ 1 (y) the dimension of Z is at least n — m. 2) There exists a nonempty open subset U C Y such that dim/ _1 (y) = n — m for y € U. In the proof of Theorem [T] we will apply Theorem [9] twice, for each of the projections from X to the factors S and %. The first of these projections computes the dimension of X. Lemma 10. X is an irreducible variety of dimension K J2(di{M l -di) + d i (Ni-d i ))+ {MiNj-didj). 1=1 l<i,3<K Proof: We consider the projection from our inci- dency variety on the space of strategies p: X S. For any point s = (Ui, . . . , Uk, Vi, . . . , Vk) £ S, we claim that the fiber p~ x (s) is a linear space of dimension dimp _1 (s) = S2 (MiNj-didj l<iJ<K To see this claim, we give local coordinates to each of the subspaces comprising the solution s € S. We write (i) (i) u a for the ath basis element of subspace Ui, where u a has zeros in the first di entries except for a 1 in the ath entry, and similarly for v} ; (this is without loss of generality). The orthogonality condition Vj _L H^C/j can now be written as the condition _L H^-Ua for each 1 < a < di and 1 < b < dj. Writing this out 6 explicitly, we obtain 0= 4 j) (k)H.^(k,l)u^(l) l<k<M i 1<1<Nj = t^(*)HM(fc,0uW(0 1 < k < d i KKdA + ^(*)HW(fc,Q„W(Z) fe>di or Z>(ij = H^(o,6) + ^? ) (fc)H^(fc,0«W(0 . fc>di or i>dj Note that this equation is linear in the entries of ~Hy l K There are didj such linear equations, and each one has a unique variable H^(a, b), so the equations are linearly independent and each equation reduces the dimension by 1. The claim follows from the fact that in total there are Y^i^jdidj equations and we began with dimTi = ^i<*,j<k MiNj dimensions ([8]). We have shown that the fibers of I — > S are vector spaces, and, in particular, irreducible varieties of constant dimension. Thus, since 5 is an irreducible variety, so is X G51 Ex. 14.3]. Moreover, Theorem [9] gives the relation dimX = dini5 + dimp _1 (s) . Since the dimension of S is exactly the first summation in the lemma statement, this proves the lemma. ■ Proof of Theorem VPc We now consider the pro- jection onto the second factor q: X — > %. This map is dominant if and only if the alignment problem is generically feasible. In this case, Theorem [9] tells us that the fiber for a generic h G % has dimension dimg = dimX — dim'H . (9) Using formula ([8]) for the dimension of % and Lemma 10 for the dimension of X, we get that Q is equal to the quantity tu„jn from the theorem statement. Therefore, by Theorem [9| this quantity must be non-negative if there are to be feasible solutions, in which case tu k} * s tne dimension of the set of solutions to the generic alignment problem. Now we turn to the other necessary conditions for other subsets A C {1,...,K}. Any feasible strategy for the full set of K transmitters and receivers, will, in particular be feasible for any subset of trasmitter-reciever pairs. Therefore, a necessary condition for a general set of channel matrices to have a feasible strategy is that the same is true for any subset of the pairs. Since the number tA is the dimension of the variety of solutions when restricted just to the transmitters and receivers indexed by i € A, then tj± must be non-negative in order to have a feasible strategy. ■ We now turn to the second necessary condition, The- orem [2j and the closely related Theorem [3] As we said, Theorem [2] is a generalization of the obvious constraint that di < Mi for each transmitter, and the generalization is formed by considering r + 1 transmitters and r receivers at the same time. We first handle the case of r = 1. Proof of Theorem We define A to be the Ni x (Mj + Mfc) block matrix: (H^l H[* fc l) . For generic channel matrices, A will have full rank, i.e. rank equal to min(iVj, Mj+M^). We consider the vector space U = Uj x of dimension dj + d^ in C j+ k . The orthogonality condition ([5]) implies that Vi _L A1A. If Ni > Mj + Mfc, then A will be injective, and so AU has dimension dj + dk- However, orthogonal vector spaces can have at most complementary dimensions, so we have that di + dj + dk < N. On the other hand, if N < Mj + Mfc, then the Hermitian transpose A^ is injective, and from the orthogonality relation A*Vi _L U, we get that d{ + dj +dk < Mj +Mfc. Thus, we conclude that di + dj + d k < max(iV i , Mj + M k ). ■ A key step in the proof of Theorem [3] was that the matrix A had full rank. For r > 1, we again show that, under appropriate hypotheses, the analogous matrix has full rank. Lemma 11. Let i±, . . . , i r +2 be a sequence as in the statement of Theorem [2] and we assume that Ni = N and Mi = M for all i. For any r > 1 define the rN x (r + 1)M block matrix A r to be /Hi 5 V Jj[*2*3] Hi jj[i r i r+1 ] jj[vir+2] J (10) For generic channel matrices H™, the matrix A r has full rank, min(rA r , (r + 1)M). Proof: In order to prove that A r has full rank for generic channel matrices, it is sufficient to prove that it does so for one particular set of matrices. This is because A r having full rank is equivalent to at least one of its maximal minors being non-zero. If this is true for one specialization of the channel matrices, then it will be true for a dense open set. We specialize to the matrices D H Im 7 and C := W hi where Im denotes the M x M identity matrix and the denotes a block of Os of size (N — M) x M. Note that by our assumptions on the sequence of is, we've made only one assignment for each matrix in ( fTO] ). We will prove that, with these specializations, the block matrix A r from the statement has full rank by simultaneous induction on r, N, and M. If r = 0, then A r is a x M matrix, which trivially has full rank. If N > 2M, then every row vector is a unit vector and all such unit vectors appear in some row, so the matrix has full rank. Now we suppose that N < 2M. We permute the rows and columns of A n as follows. Note that the rows of A n are arranged into r blocks of N rows each. We extract the first block in its entirety, followed by the last N — M rows of each of the subsequent r — 1 blocks. We leave the remaining rows in their induced order, and put extracted rows after them, also in their induced order. We also permute the columns, which are arranged into r + 1 blocks of size M. We take the first block of M columns, followed by the last N — M columns of each of the other r column blocks, and place these to the right of all the other columns. If we divide B and C into blocks by separating off the last N — M rows and columns of each, then we get where B' = B In-m B' B C hu-N C In-m c hM-N Therefore, the rearranged matrix has the form (B C B' B C B< C Im lN-M V In-m) In the lower right, we have a identity matrix of size M+ r(N — M). We can use this identity matrix, together with elementary column operations to clear the C on the left, and with elementary row operations, the B's in the upper right. The transformed matrix is in block diagonal form, with an identity matrix in the lower right. In the upper left, the copies of B and C form our specialized version of A r _i with parameters M and N each decreased by N — M. By the inductive hypothesis, the latter matrix has full rank. Thus, A r is equivalent to a block diagonal matrix, where one block has full rank, and the other block is the identity, so A r has full rank. ■ Proof of Theorem^ We fix the integer r. Define the product of transmit spaces U = Ui 2 x Ui 3 x • • • x Ui r+2 C (C M ) r+1 , and similarly let V = V i% x ... V ir C (C N ) r . Note that U and V have dimensions and dim V = di First, suppose that rN > (r + 1)M. Then Lemma 11 M\r+1 IS implies that the linear map A r : (C injective. By the orthogonality condition ([5]), we have V _L A r U, and thus dim(V) + dim(A r W) r r+2 is at most rN. On the other hand, if (r + 1)M > rN, the Hermitian transpose AJ is an injective linear map AJ : (C N ) r — > (C M ) r+1 . Again, the orthogonality conditions ((5]) imply that Atv 1 U so dimV + dimZY < (r + V)M. This proves the theorem. ■ IV. Sufficient conditions In this section, we give criteria for ensuring the achievability of interference alignment. We have already seen the necessary direction of Theorem [5] and we prove the sufficient direction, first when M = N, and second when M < N. The former case will also be covered by Theorem [6} but we give a specific K = 3 proof because it is effective and to compute the number of solutions in the boundary case. The construction in Proposition 12 has also appeared in (5] Appendix IV]. Proposition 12. If K = 3, and M = N > 2d, then alignment is feasible. Moreover, in the case of equality, the number of solutions is exactly ( 2 ^) for generic channel matrices. Proof: By first restricting our transmit and re- ceive spaces to arbitrary subspaces, we can assume that M = N = 2d. Since the channel matrices are square, generically, they are invertible, so we can define the product B = H 1,2 ( H [3,2])-1 H [3,1] ( H [2,1])-1 H [2,3] ( H [l,3h 8 Again, generically, this matrix will have 2d linearly independent eigenvectors, and we choose V\ to be the span of any d of them. Then we set u 3 x v 2 v 3 (HM)-^ (2d\ These form a feasible strategy, and there are ■ , ble strategies. Before we proceed to the proof in the case when M and N are distinct, we want to informally describe the geometry underlying the construction of solutions. A given vector m in the signal space of transmitter % is said to initiate an alignment path of length r + 1 if there exists a sequence of vectors Uj+i, Ui+2, • • ■ , Ui +r € such that -l,< U: H [»-l,i+l] Ui+1, jj[i+r— 2,i+r— 1] ''i+r—1 H ]i+r-2,i+r] i+r • Here channel indices are interpreted modulo 3. For ex- ample, a vector U2 at transmitter 2 initiating an alignment path of length 3 means that there exist vectors u 3 and ui such that U^u 2 = tt [13] u 3 and U^u 3 = H^m. The feasible region of Figure [T] is divided up into sub-regions labeled with the maximum length of an alignment path; this number depends on M and N through the incidence geometry of the images of the channel matrices Im(H^). We begin by examining sub- region 1, and then look at how things generalize to the other sub-regions. The point of departure is the obvious constraint d < M in order to have a d-dimensional subspace of an M dimensional vector space. Continuing, assuming M > d, suppose 2M < N, so (M, N) lies in sub-region 1 of Figure 111 At receiver one, the images Im(H[ 12 l) and Im(H^l) of the channels from transmitters two and three are in general position and therefore their intersection has dimension [2M — N] + = 0; in other words, alignment is impossible in sub-region 1. Figure [2] shows pictorially that because alignment is not possible here, we have the constraint 3d < N. Moving onward to sub-region 2, we have 2M > N and thus alignment is possible. This means that align- ment paths of length 2 are possible (Fig [3]), with up to 2M — N interference dimensions overlapping at each receiver. Thus, the interference space H' 12 !^ + H' 13 ]^ C M u 9 Im(H [12] \ C N Mi Tx2 Tx3 C M U 3 Im(Ht 13 l) Fig. 2. Sub-region 1: The figure indicates that no alignment is possible when 2M < N, since Im(H [121 ) and Im(H [131 ) are complementary. Since the three subspaces V\, H' 12 '?72, H' 13 't/3 are possi eac ^ q £ dimension d, complementary, and lie in at receiver 1, ' we obtain the constraint 3d < N. Txl Tx2 Tx3 Fig. 3. Sub-region 2: Alignment is possible here. The figure denotes an alignment path of length 2. at receiver one occupies at least 2d — (2M — N) dimen- sions, and we have the constraint 3d < 2M. However, because 3M < 2N, no vector at (say) transmitter three can be simultaneously aligned at both receivers one and two, as indicated in Figure |4| One can also see that no simultaneous alignment is possible by changing perspective to that of a combined receiver one and two. By Lemma [TT] the map H [23] jj[21] (11) from the three transmitters to C is injective; analo- gously to the case in sub-region 1, this is interpreted to mean that no alignment is possible in the com- bined receive space C 2N . Thus, five complementary d- dimensional subspaces lie in C 2N and we obtain the constraint 5d < 2N. As far as achievability goes, the basic rule-of-thumb is to create alignment paths of maximum length. Thus, in sub-region 2, where alignment is possible, the achievable strategy aligns as many vectors as possible and the remaining ones (if d > 2(2M — N)) are not aligned. The achievability arguments extend in a natural way. On the achievability end, alignment paths of maximum 9 Txl Tx2 Tx3 Im(Hl 12 I) Im(Hl 13 h^ ^ Rxl Rx2 Im(Hl 23 l) Im(H[ 21 )) Fig. 4. Sub-region 2: The striped regions at receivers one and two each denote the dimension 2M — N portion of the space in which alignment can occur. From transmitter three's perspective, one sees that simultaneous alignment is not possible for 2(2M — N) < M, or equivalently, 3M < 27V. Txl Tx2 Tx3 Fig. 5. Sub-region 4: Alignment paths of length four are denoted here, initiated by vectors at transmitter 1. length are used. For example, in sub-region 4, alignment paths of length four are used (Fig [5]). For the converse, a generalization of the matrix in ([TTJ is shown to be full-rank in Lemma 1 1 giving the constraints in ([2]). Proposition 13. If K = 3 and M < N and Q holds for each r > 0, then alignment is feasible. In the 0- dimensional case, when N + M = 4d, there is a unique solution. Proof: Let r be the (unique) integer such that rN<(r + l)M and (r + 1)N > (r + 2)M . (12) Note that this implies, from Q, that (2r + 3)d < (r + l)N (13) and (2r+l)d< (r + l)Af. (14) We prove achievability by examining two cases: first d < (r + l)[(r + 1)M - rN] and second, d > (r + l)[(r + 1)M — rN]. Case 1 means that all of the signal space Ui can be obtained from alignment paths of length r+1 (up to integer rounding), whereas in case 2 we must use alignment paths of length r as well in order to attain the required d dimensions. We first establish case 1. Let Ai be the matrix from ( [10] ) for the increasing sequence of indices begin Vi be a the kernel of A* Let d' ning with i. Let W{ be a dimension [^rpyj subspace in d and if (r + i)L4r. d' > let Wi be a 1-dimensional subspace in ker A* \Wi. We define Wij C C M to be the projection of Wi onto its (j — i)th block of coordinates. The spaces wi are required in order to accommodate the remainder left when dividing d by r + 1, and will together contribute d' dimensions to each signal space Uj. We put j-r-l j-d> w (15) i=j-l i=j-l and V j= (HV-l Wj , j+l + I&-l Wj , j+1 j-r j-d'+l n i=j i=j / (16) If all of Uj 's constituent subspaces are complementary, then Uj has dimension (r + 1) L^rrfJ + d' = d. We rigorously justify this in Lemma 14 To see that Vj has dimension (at least) d, we observe that by subadditivity of dimension, dim > N - (r + 2) d r+1 d'-e, (17) where e = if (r + l)\d and e = 1 otherwise. Plugging in the inequality ( fT3"T ) we obtain dim V» > — — -d — d — e 3 ~ r + 1 d + r + 1 r + 1 r+1 e> d. Suppose now that we are in the second case, i.e. d > (r + l)[(r + 1)M - rN]. This means that not all of the signal space Ui can be included in alignment paths of length r + 1, so the remainder will be included in alignment paths of length r. Let d' := d — (r + l)[(r + 1)M - rN] and d" = d' - r [f\ . As before, denote by Wi the kernel of the matrix A* , having dimension (r + l)M — rN. Denote by ir the projection from <£( r+1 ^ M —> C rM to the first rM coordinates. The space 7r(ker A* ) is contained in A*_ x . Let X{ for i = 1, 2, 3 each be a 1^1 dimensional subspace in ker A*_ 1 \7r(Wi), and let Wi be 10 a 1 -dimensional subspace in ker A*_ 1 \ (ir(Wi) + Xj) Put j-r-l j-r j-d" i=j-l i=j—l i=j—l (18) and Vj= in^(W J , j+1 +X jd+1 + w 'i,i+iJ (19) i=j i=j j-d' +1 \ -L As before, a naive count suggests that Uj should have dimension d, and this will again be justified with Lemma [141 To see that Vj has dimension at least d we again use subadditivity of dimension to get d! dim Vj >N-(r + 2)[(r + 1)M - riV] - (r + 1) — d — e\ N - {r + 2)[(r + l)M - rN] - d! - ei, where ei is if r divides d' and e\ is 1 otherwise. Letting e 2 := ^ — |_^rj , we have dim K- > N - (r + 2)[(r + 1)M - riV] - d' + e 2 - ei = N — t±±^ + -[(r + 1)M - rN] r r + e 2 - e\ , (r + 1) w 2r + l , = d + -M d + e 2 - ei . r r Substituting 2T+T^ f° r ^' tne inequality ([14]) implies that dim Vj > d + e 2 — ei . If ei is one then e 2 is strictly positive, so the fact that dim Vj is an integer implies dim Vj > d. ■ Lemma 14. The subspaces Uj and Vj defined in (15), (16), (USl), and \19\ have dimension d. Proof: We first show that U\ has dimension d; by symmetry of the construction, the dimensions of Ui and U-$ will also be d. The subspace U x = Z i= -r W i- i is the sum of r + 1 subspaces Wij, which we claim are independent; sup- pose to the contrary, that there is some set of linearly dependent vectors Wi^w^, . . . ,Wi s , with < i\ < i 2 < ... < i s < r, and Wi € satisfying w i s ~ Y2e=i ^i w i t = 0. Let s be the minimum such value, with all sets of subspaces W^j, Wi 3 j, ■ ■ ■ , Wi s _ u j for j = 1, 2, 3 being complementary. Now, by the definition of the subspaces Wij, for each vector u>i e G W-i u \ there is a sequence of length q := r + 1 — i s -\ satisfying H' 31 ]^ = Hl 3 V , . . . , H[«+ 2 '«]n? = H[«+ 2 ><?+ The linear combination Y2l=i ^i w ie tnus gives rise to a sequence u 1 , . . . , u q+1 defined by u a = Yle=i ^i u i e satisfying h[ 31 ^ = h[ 31 ][|] H [12] n 2 = H [13] u 3 \lWi (20) U [q+2 ' q] u q = U [q+2 ' q+l] u q+1 . Note that by the minimality assumption of s, none of the v? vectors are zero. By the definition of W_j S) i, there is a length-(i s — 1) sequence of vectors preceding w% a satisfying alignment conditions similar to those in d20b; together with wi s and the vectors in ( |20| ), this sequence can be extended to a sequence of vectors of total length q + i s = r + 1 + (i s — is-l) > t + 1, none of which are zero. Stacking the first r + 2 of these vectors produces a nonzero element in the kernel of A* a +1 . However, A* s +1 is full-rank by Lemma 11 (r + l)N] the dimension of the kernel is [(r + 2)M M + d(2r + 1 - 2r - 3) = M - 2d < 0, i.e. the kernel is trivial. This is the desired contradiction. We now check that V\ has dimension d, and again by symmetry, the dimensions of V2 and V3 will also be d. Note that if V\ had dimension greater than d, we could choose a <i-dimensional subspace and this would still satisfy the alignment equations ([5]). But V\ is the orthogonal complement of the sum of r + 2 subspaces Wij of dimension d/[r + 1), so by subadditivity of dimension, we have the lower bound on dimension dim V\ > N - (r + 2) dim Wij = d. ■ We now wish to prove achievability for more than 3 users. We do this under the additional assumption that M = N. Unlike our techniques above, these existence results will not be effective, a characteristic shared by previous existence proofs in Q and CQ. In HI , a proof of Theorem [6] was given using dimen- sion theory for algebraic varieties and linear algebra. Here, we give an intersection-theoretic proof, which 11 involves more advanced machinery, but that machinery allows for a more straightforward computation. More- over, as we'll see in Proposition [TT] the Schubert calculus framework will also allow us to go beyond the existence of solutions and count the number of solutions when that number is finite. Our proof will show that the expected number of solutions, as counted by Schubert calculus, is always positive. Schubert calculus is a method for computing the number of solutions to certain enumerative problems. For algebraic varieties, such as the product of Grassmannians which parametrize alignment strategies, there is a com- mutative ring whose elements correspond to conditions on the paramters (such as the orthogonality relation ([!])), and where the product corresponds to the simultaneous imposition of both conditions. In algebraic geometry, this is known as the Chow ring and in the case of products of Grassmannians, it coincides with the cohomology ring from algebraic topology. The Chow ring of a Grassmannian has an explicit Z- basis indexed by partitions, and the Chow ring of the product of Grassmannians has a basis of tuples of par- titions. Specifically, the Chow ring of the Grasmannian G(d, m) has a basis corresponding to partitions with at most d parts of size at most m — d. Such a partition is a list of integers Aj with m — d > Ai > • • • > > 0, and we write |A| for its size, Ai + • • • + A^. The product between two of these basis elements, known as Schubert classes, is given by an intricate combinatorial process known as the Littlewood-Richardson rule. We will not need the details of the Littlewood-Richardson rule, but only the following simpler facts about multiplication in the Chow ring of G(d,m): Theorem 15. The Schubert classes have the following properties in the Chow ring of the Grassmannian: 1) The product of two partitions is a non-negative sum of other partitions K26\ p. 146, (8)]. 2) If X and p are two partitions with \\ + p\ < d, then the product [X][p] has a coefficient of 1 in front the term \v\ where Vi = \ + v^. 3) Suppose that A has £ parts and p has k parts and that £ + k < m — d. Then [A] [p] has a coefficient of 1 in front of the term [v\ where v is formed by concatenating the parts of A with the parts of p, and then sorting them in decreasing order. The last two facts in this list can each be proved from the Pieri rule (26] p. 146, (9)], and are in fact closely related to each other. Partitions can be depicted as boxes in the upper left corner, such as the depiction of (5, 4, 1) in Figure|6] Such diagrams have an involution by reflecting them along a diagonal so that the conjugate of Fig. 6. The Young diagram of the partition (5, 4, 1). (5, 4, 1) is the partition (3, 2, 2, 2, 1). For any partition A, we write A' to denote the conjugate partition. This conjugation corresponds to the isomorphism between G(d,m) and G(m — d,m), and it is compatible with the multiplication. The last two items are related by this conjugation operation. The Chow ring of a product of Grassmannians has a basis indexed by tuples of partitions, one for each Grassmannian. Moreover, the products can be computed factorwise. Formally, the Chow ring of the product of Grassmannians is the tensor product of the Chow rings of the Grasmannians. Lemma 16. The alignment correspondence defined by H^Uj _L Vi has class £) A [A] <g> [d d - A'] in the Chow ring of G(d, M) x G(d, N). The sum is taken to be over all partitions with at most d parts of size at most d, and d d — A' is the partition whose kth part has size Proof: We compute the class by intersecting with dual Schubert classes to get a zero-dimensional cycle. In particular, we let p, and v be partitions into at most d parts of size at most M — d and N — d respectively, and such that the total size \p\ + \u\ is (M + N — 3d)d, which is the dimension of the correspondence. We first recall the definition of the Schubert cycle in G(d, M) associated to a partition p and a flag F*. A flag in C M is a nested set of vector spaces = Fq C F\ C • • • C Fm = C M such that F has dimension i. The Schubert cycle is the closed subvariety of those vector spaces U such that dim(£7 n Fm-cL-h-^ — * for 1 < i < d. We also fix a flag E* in C , so that v defines a Schubert cycle in G(d, N). By symmetry, we can assume that N is greater than or equal to M and thus a vector space U G G(d, M) defines a unique (N — d) -dimensional subspace (JjlvljJ) 1 - in C N . Likewise, the orthogonal complement (H^Fk) 1 C is an (N - /c)-dimensional vector space, which together form a flag from dimension N—M through N. We can choose a flag of additional vector spaces contained within Fn~m to get a full flag in C , which we denote F*. Then if V is in the Schubert 12 cycle of v if and only if V 1 - is in the Schubert cycle corresponding to and {{N — M) d + v)' , which we denote a. Note that \a\ = + (N — M)d, so a and v together have total size (2M — 3d)d. Thus, rather than consider pairs of U and V, we can consider pairs U = (H.MU) X and V C U satisfying the Schubert conditions dim(£7 n F M -d +i-uj > i, dim(V n E d+ j- a .) > j, (21) where 1 < % < d and 1 < j < N — d. We now fix indices i and j satisfying i + j = N — d+1. Since U has dimension N — d and contains V, this means that unF M - and VDE d +3- must have a non-zero element in common, and thus FM-d+i-n and Ed+j+ aj must intersect non- trivially. The flags are generic, so their intersection means that sum of the dimensions of the vector spaces, which is 2M — d+1 — V{ — Uj, must be greater than the dimension of the ambient space, M. Rearranging, this means that vi + Oj can be at most M — d. Because of their degrees, the only possibility is that vi = M — d — aj^-d+l-i for 1 < i < d and that crj = d for 1 < j < M - 2d. Moreover, for fixed partitions v and a of this type, there is a unique pair of vector spaces V C U satisfying (21 1. We set V to be the vector space generated by the one-dimensional vector spaces F^-d+i-Vi H for 1 < i < d and take U to be generated by V and Fu-2d- What we've shown is that the only Schubert classes which occur in the correspondence class are dual to the classes \i and a above, and these occur with coefficient 1. Since the parts of a have size at most d, this means that the parts of (N — d) d — v have size at most d, and this is the partition A from the lemma statement. Tracing backwards, we see that v is (M — d) d + A', and thus the expression of the correspondence consists of the classes [A] (g> [d d — A'], as in the statement. ■ Proof of Theorem [6|- It will be sufficient to prove that the product of the classes from Lemma 16 over all pairs i ^ j results in a positive multiple of some Schubert class. Moreover, by the first statement of The- orem fT5l it is sufficient to find one combination of terms from each incidence class whose product is non- zero. We shall exhibit such a combination in two separate cases. First, we suppose that K is odd. From the fac- tor for each incidence correspondence, we choose the term based on the cyclic difference (i — j) mod K 6 {1, . . . , K — 1}, where j is the index of the receiver and i is the index of the transmitter. In particular, when this modular difference is between 1 and (K — 1)/2 inclusive, we choose the term where the transmitter partition is d d . Fig. 7. Schematic diagram of the partitions whose product gives a non-zero coefficient in the proof of Theoerm [6] for the case when K and d are even. On top are the partitions for the receiver's Grassmannian and on the bottom is the transmitter's Grassmannian, when the index is odd. Each block represents a single copy of d d ' 2 or (d/2) d , and the arrangement shows a partition with non-zero coefficient in their product. We write a b to denote the partition consisting of b parts of size a. By Lemma 16 the term has the empty partition for the receiver's Grassmannian. When this modular difference is at least [K + l)/2, we choose the term where the receiver partition is d d and the transmitter partition is 0. Thus, for each Grassmannian, we have the product of (K — l)/2 copies of d d . We've assumed that N — d > d(K — l)/2, so this product contains at least one copy the tuple with (d(K — l)/2) d in each spot. On the other hand, suppose that K is even. If, in addition, d is even, we choose the term of each inci- dence relation in which the transmitter's Grassmannian has partition (d/2) d , with the exception that when the transmitter's index j is even and the transmitter's index i is equal to j + 1 or j + 2, modulo K, the transmitter has d d / 2 . In either case, the receiver's partitions are the same. For each receiver, we have the product of K — 2 copies of d d / 2 and one {d/2) d . The product of d d < 2 with itself has a non-zero coefficient in front of d d . Then, the product of (K — 2)/2 copies of d d with (d/2) d has a non-zero coefficient in front of (d(K — l)/2) d , using our assumption that N—d > d(k— 1)/2. At a transmitter with odd index, we are evaluating the product of K — 1 copies of (d/2) d , yielding a non-zero coefficient in front of (d{K — l)/2) d . At an even index, it is similar except two of these copies are replaced by d d l 2 , which themselves multiply to d d , and we get the same result. Finally, when K is even and d is odd, the proof is similar, except that since d/2 is not an integer, we have to round it up or down each time it is used. In particular, for the factor corresponding to the incidence relation between the ith receiver and jth transmitter, we use the same partitions above except that we round down d/2 in the transmitter's partition when i — j is even and round up when i — j is odd. Of course, this causes d/2 in the receiver's partition to round in the opposite direction. Overall, for each Grassmannian we've rounded up half 13 TABLE I Number of solutions to symmetric alignment problem J.- d 1 1 L 3 2 6 20 4 3700 5 216 388,407,960 6 7 1,975,560 8 9 2,355,206,975,800 The table shows the number of solutions to the symmetric alignment problem when N = M = d(K + l)/2 and either d or K + 1 is even. Missing values could not be computed. the time and down half the time and the product works out as above. ■ V. Computing feasible strategies In this section, we discuss the computation of strate- gies from particular channel matrices. In the case of K = 3, the proofs of sufficiency in Propositions [12 and 13 are effective, in that the feasible strategies can be computed via eigenvectors or the kernel of a matrix, respectively. For K > 3, the feasibility problem is not reduced to linear algebra, and the method of Theorem [6] is not effective, but we can still solve the interference alignment problem using general numerical methods for polynomial equations. The method used to prove Theorem [6] was to establish a lower bound on the generic number of solutions using Schubert calculus. It was sufficient to find one product of classes which was positive. However, by computing all terms in the product of the incidence relations, we can compute the number of solutions for a general system in small cases: Proposition 17. Suppose that either d is even or K is odd. Then the number of solutions to the symmetric alignment problem is as given in Table |7| Using very different methods, (27, Sec. IV] counted the approximate number of solutions to some interfer- ence alignment problems. In the common cases, the two methods agree up to their stated margins of error. In particular, we confirm that for M = N = 5, K = 4, and d = 2, there are 3700 solutions, which they could only claim with high confidence. In addition, the first two values in Table [I] for K = 1 were computed in lfl31 using Bernstein's Theorem. The solution counts given in Proposition 17 are rel- evant for computing solutions in two different ways. First, a large number of solutions indicate the difficulties in enumerating all solutions or in using an iterative algorithm. Second, the number of solutions also measures the algebraic complexity of finding a solution, since it is also the degree of the field extension of a solution for random rational parameters. To illustrate this principle, consider the case of Proposition 12 which showed that the solution to the interference alignment problem with d = 3 and N = M = 2d can be found by finding d eigenvectors of a 2d x 2d matrix. Algebraically, finding an eigenvalue and eigenvector of a generic 2d x 2d matrix with rational entries requires solving an irreducible polynomial of degree 2d, and thus the solution lies in a degree 2d extension of the rationals. Finding a second eigenvector requires an extension of degree 2d — 1, and so on, so that the solution lies in a degree {2d)\/d\ extension. A somewhat more refined analysis would show that it lies in a smaller field of degree ( 2 d d ), but in any case the prime divisors of the degree are less than 2d, and likewise the polynomials which had to be factored had degree less than 2d. The structure of the field extension and its degree reflect the structure of the construction of the solution. In contrast, Proposition 17 shows us that when, for example, K = 4, d = 2 and N = M = 5, for sufficiently general rational data, the solution lies in an extension of the rationals of degree 3700 = 2 2 • 5 2 • 37. Thus, an exact solution must (explicitly or implicitly) involve a step in which it finding a root of a polynomial of degree 37, or, worse, some multiple of 37. It seems unlikely that there is any natural construction for such a polynomial. Thus, when K > 3, we turn to numerical methods, such as PHCpack OH, Bertini [291, and HOM4PS E0l . which use homotopy continuation methods to solve arbi- trary algebraic equations. Specialized homotopy methods for Schubert problems in a Grassmannian were intro- duced in 11311 and IT321 . However, at this time, there does seem to be an implementation of these ideas for Schubert problems in a product of Grassmannians, such as our strategy space. To represent the unknown vector spaces in the align- ment problem, we could use Pliicker coordinates. How- ever, computationally, the Pliicker coordinates are inef- ficient and lead to systems with more equations than unknowns, which are more difficult for the numerical solvers. Instead, we choose special coordinates for which our system is square, following ll33l . Under our genericity assumptions, we can assume that each Ui is generated by the rows of a di x TYj matrix with an identity in the leftmost position: / 1 • uli ,1 v° 1 Ui,d,N- UiXN-d UidN-dl 14 and similarly for Vj. The orthogonality conditions be- tween Vi and Uj can be expressed as didj bilinear equa- tions in these variables. Note that in this representation, the expected dimension (tji,...^} i n Theorem |TJ) is the difference between the numbers of variables and the number of equations. Example 18. We consider the symmetric alignment problem with K = 5, M = N = 3, and d = 1. Using Macaulay2 H34\l . we chose the 20 = 5 • (5 — 1) channel matrices Hij as random 3x3 matrices with rational entries. Each of the 1-dimensional vector spaces is given as the span of a vector (1, *, *), and thus there were 10-2 coordinates. In addition, each of the channel matrices gives one condition, so there were also 20 equations of the form: (l Vi,i v i>2 ) H i:j (l Uj t i u j)2 ) far i ^ j We used PHCpack H28\l to solve this system and obtained 216 solutions in about a minute and a half on a laptop, thus confirming the value in Table |7| Acknowledgment We thank Bernd Sturmfels for insightful discussions and the authors of [7 ] for sharing their related manuscript with us before it was publicly available. We also wish to acknowledge Frank Sottile for suggesting the method of proof in Theorem [6j References [1] G. Bresler, D. Cartwright, and D. Tse, "Settling the feasibility of interference alignment for the MIMO interference channel: the symmetric square case," in ITW, 2011. [2] G. Bresler, D. Cartwright, and D. Tse, "Geometry of the 3- user MIMO interference channel," in Allerton Conference on Communication, Control, and Computing, September 2011. arXiv:1110.5092vl. [3] A. Ozgur, O. Leveque, and D. Tse, "Hierarchical cooperation achieves optimal capacity scaling in ad hoc networks," IEEE Trans. Inf. Theory, vol. 53, no. 10, pp. 3549-3572, 2007. [4] M. Maddah-Ali, A. Motahari, and A. Khandani, "Communica- tion over MIMO X channels: Interference alignment, decom- position, and performance analysis," IEEE Trans. Inf. Theory, vol. 54, pp. 3457-3470, August 2008. [5] V. Cadambe and S. Jafar, "Interference alignment and degrees of freedom of the fc-user interference channel," IEEE Trans. Inf. Theory, vol. 54, pp. 3425-3441, August 2008. [6] C. Yetis, T. Gou, S. Jafar, and A. Kayran, "On feasibility of interference alignment in MIMO interference networks," IEEE Trans. Signal Processing, vol. 58, pp. 4771-4782, September 2010. [7] M. Razaviyayn, G. Lyubeznik, and Z.-Q. Luo, "On the degrees of freedom achievable through interference alignment in a MIMO interference channel," IEEE Trans, on Signal Process- ing, vol. 60, February 2012. [8] M. Amir, A. E. Keyi, and M. Nafie, "A new achievable DoF region for the 3-user M x N symmetric interference channel." preprint, arXiv:1105.4026vl, May 2011. [9] C. Wang, T. Gou, and S. Jafar, "Subspace alignment chains and the degrees of freedom of the three-user MIMO interfer- ence channel," IEEE International Symposium on Information Theory, July 2012. [10] K. Gomadam, V. Cadambe, and S. Jafar, "A distributed nu- merical approach to interference alignment and applications to wireless interference networks," IEEE Trans. Inf. Theory, vol. 57, pp. 3309-3322, June 2011. [11] S. Peters and R. Heath, "Interference alignment via alternating minimization," in Acoustics, Speech and Signal Processing, 2009. IEEE International Conference on, pp. 2445-2448, April 2009. [12] M. Razaviyayn, M. Sanjabi Boroujeni, and Z.-Q. Luo, "Lin- ear transceiver design for interference alignment: Complexity and computation," in Signal Processing Advances in Wireless Communications (SPAWC), 2010 IEEE Eleventh International Workshop on, pp. 1-5, June 2010. [13] D. S. Papailiopoulos and A. G. Dimakis, "Interference align- ment as a rank constrained rank minimization," in IEEE GLOBECOM, 2010. [14] I. Santamaria, O. Gonzalez, R. Heath, and S. Peters, "Max- imum sum-rate interference alignment algorithms for MIMO channels," in IEEE GLOBECOM, pp. 1-6, December 2010. [15] D. A. Schmidt, W. Utschick, and M. L. Honig, "Beamforming techniques for single-beam MIMO interference networks," in Allerton Conference on Communication, Control, and Comput- ing, pp. 1182-1187, September 2010. [16] G. Bresler, A. Parekh, and D. Tse, "The approximate capacity of the many-to-one and one-to-many Gaussian interference channels," IEEE Trans. Inf. Theory, vol. 56, September 2010. [17] V. Cadambe, S. Jafar, and S. Shamai, "Interference alignment on the deterministic channel and application to fully connected Gaussian interference networks," IEEE Trans. Inf. Theory, vol. 55, pp. 269-274, January 2009. [18] R. Etkin and E. Ordentlich, "The degrees-of-freedom of the if -user Gaussian interference channel is discontinuous at ra- tional channel coefficients," IEEE Trans. Inf. Theory, vol. 55, pp. 4932^1946, November 2009. [19] A. S. Motahari, S. Gharan, M. Maddah-Ali, and A. K. Khan- dani, "Real interference alignment: Exploiting the potential of single antenna systems." preprint, arXiv:0908.2282, 2009. [20] O. Ordentlich and U. Erez, "Interference alignment at finite SNR for time-invariant channels," in Information Theory Work- shop (ITW), October 2011. [21] Y. Wu, S. Shamai, and S. Verdu, "Degrees of freedom of the interference channel: A general formula," in IEEE International Symposium on Information Theory (ISIT), pp. 1362 -1366, August 2011. [22] K. Gomadam, V. Cadambe, and S. Jafar, "Approaching the capacity of wireless networks through distributed interference alignment," in IEEE GLOBECOM, pp. 1 -6, December 2008. [23] R. Hartshorne, Algebraic Geometry. Graduate Texts in Mathe- matics, Springer, 1st ed., 1977. [24] I. Shafarevich, Basic Algebraic Geometry. Springer, 2nd ed., 1995. [25] D. Eisenbud, Commutative Algebra with a View Toward Alge- braic Geometry, vol. 150 of Graduate Texts in Mathematics. Springer, 2004. [26] W. Fulton, Young Tableaux, vol. 35 of London Mathematical Society Student Texts. Cambridge University Press, 1997. [27] O. Gonzalez and I. Santamaria, "On the number of interfer- ence alignment solutions for the if-user MIMO channel with constant coefficients." preprint, arXiv:1301.6196, 2013. [28] J. Verschelde, "Polynomial homotopy continuation with PHC- pack," ACM Communcations in Computer Algebra, vol. 44, no. 4, pp. 217-220, 2010. 15 [29] D. J. Bates, J. D. Hauenstein, A. J. Sommese, and C. W. Wampler, "Bertini: Software for numerical algebraic geometry." Available at http://www.nd.edu/~sommese/bertini [30] T. L. Lee, T. Y. Li, and C. H. Tsai, "HOM4PS-2.0: A software package for solving polynomial systems by the polyhedral homotopy continuation method," Computing, vol. 83, no. 2-3, pp. 109-133, 2008. [31] B. Huber, F. Sottile, and B. Sturmfels, "Numerical Schubert calculus," Journal of Symbolic Computation, vol. 26, no. 6, pp. 767-788, 1998. [32] F. Sottile, R. Vakil, and J. Verschelde, "Solving Schubert problems with Littlewood-Richardson homotopies ," in Proceed- ings of the 2010 International Symposium on Symbolic and Algebraic Computation, pp. 179-186, 2010. [33] J. D. Hauenstein, N. Hein, and F. Sottile, "Certifiable numerical computations in Schubert calculus." preprint, arXiv:1212.3315, 2012. [34] D. R. Grayson and M. E. Stillman, "Macaulay2, a soft- ware system for research in algebraic geometry." Available at http://www.math.uiuc.edu/Macaulay2/