CADAMBE AND JAFAR: INTERFERENCE ALIGNMENT AND DEGREES OF FREEDOM OF THE-USER INTERFERENCE CHANNEL3439along the rst row, the linear independence condition boils down to one of the following occurring with nonzero probability: being equal to one of the roots of a linear equation; 1) 2) the coef cients of the above mentioned linear equation being equal to zero. Thus the iterative argument can be extended here, stripping the last row and last column at each iteration and the linear independence condition can be shown to be equivalent to the linear matrix whose rows are of the form independence of a where . Note that this matrix is a more general version of the Vandermonde matrix obtained in Section IV-B. So the argument for case does not extend here. However, the iterative prothe cedure which eliminated the last row and the last column at each iteration, can be continued. For example, expanding the determinant along the rst row, the singularity condition simpli es to one of the following: being equal to one of the roots of a nite degree poly1) nomial; 2) the coef cients of the above mentioned polynomial being equal to zero Since the probability of condition 1 occurring is , condition 2 must occur with nonzero probability. Condition 2 leads to a and thus the iterpolynomial in another random variable ative procedure can be continued until the linear independence macondition is shown to be equivalent almost surely to a trix being equal to . Assuming, without loss of generality, that we placed the in the rst row (this corresponds to the term ), the linear independence condition boils with nonzero probability—an down to the condition that obvious contradiction. Thus, the matrixThe signal received at receiver can be written asAll receivers cancel the interference by zero-forcing and then streams along decode the desired message. To decode the from the components of the rethe column vectors of ceived vector, the dimension of the interference has to be less . The following three interference alignthan or equal to ment equations ensure that the dimension of the interference is at all the receivers. equal to span span (59) (60) (61)where span represents the vector space spanned by the column vectors of matrix We now wish to choose so that the above equations are satis ed. Since have a full rank of almost surely, the above equations can be equivalently represented as span span (62) (63) (64)whereLet to be can be shown to be nonsingular with probability 1. Similarly, the desired signal can be chosen to be linearly independent of the interference at all other receivers almost lies surely. Thus in the degrees of freedom region of the user interference channel and therefore, the user interference channel has degrees of freedom. Then andbe theeigenvectors of. Then we setare found using (62)–(64). Clearly, satisfy the desired interference alignment (59)–(61). Now, to decode the message using zero-forcing, we need the desired signal to be linearly independent of the interference at the receivers. For example, at receiver 1, we to be linearly independendent need the columns of almost surely. i.e., we need the with the columns of matrix below to be of full rank almost surelyAPPENDIX IV PROOF OF THEOREM 3 FOREVEN Substituting values for and in the above matrix, and , the linear indepenmultiplying by full rank matrix dence condition is equivalent to the condition that the column vectors of are linearly independent almost surely, where . is a random (full This is easily seen to be true because rank) linear transformation. To get an intuitive understanding of . the linear independence condition, consider the case of Let represent the line along which lies the rst eigenvectorProof: To prove achievability we rst consider the case is even. Through an achievable scheme, we show that when noninterfering paths between transmitter and there are receiver for each resulting in a total of paths in the network. for receiver using Transmitter transmits message independently encoded streams over vectors , i.e.,Authorized licensed use limited to: Harbin Institute of Technology. Downloaded on June 01,2010 at 01:21:44 UTC from IEEE Xplore. Restrictions apply.