Skip to main content

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/