Degrees of Freedom and Interference Alignment

Consider any single user $k$. Even with a genie that provides all other users' messages, user $k$'s rate is bounded by the point-to-point capacity: $R_{k} \leq \frac{1}{2}\log(1 + \text{SNR}_{k})$, giving $d_k \leq 1$. Consider any pair $(k, j)$. They share a two-user IC, so their sum DoF is at most 1 (each gets at most 1/2 in the worst case). Summing over all $K$ users gives $d_{\Sigma} \leq K/2$ from this pairwise argument (this can be tightened using the Cadambe-Jafar outer bound).

Use $n = (K-1)^{K-1}$ channel extensions (time slots with generic channel coefficients). For each user $k$, design a precoding matrix $\mathbf{V}_k \in \mathbb{C}^{n \times n/2}$ such that at each receiver $j \neq k$: $$\text{span}(\mathbf{H}_{jk} \mathbf{V}_k) \subseteq \text{span}(\mathbf{H}_{j,k'} \mathbf{V}_{k'})$$ for all other interferers $k'$. This aligns all interference at Rx $j$ into a single $n/2$-dimensional subspace. The desired signal $\mathbf{H}_{jj} \mathbf{V}_j$ must lie outside this interference subspace — which is generically guaranteed for the required dimensions.

For the $K$-user case with $K \geq 3$, the alignment conditions form a system of polynomial equations in the entries of $\{\mathbf{V}_k\}$. Cadambe and Jafar showed that this system has a solution for generic channel coefficients (almost all realizations of time-varying or frequency-selective channels), provided the number of channel extensions $n$ is large enough.