Linearly representable entropy vectors and their relation to network coding solutions

In this work, we address the following question: ¿When can we guarantee the optimality of linear coding at all internal nodes of a network?¿ While sufficient conditions for linear coding throughout the network are known, it is not clear whether relaxing the linearity constraints at the terminal nodes can result in simpler operations at the internal nodes. We present a novel method to analyze the space of network solutions using the constraints resulting from the network topology, and we identify sufficient conditions for an optimal linear solution at all internal nodes. These conditions are also sufficient to characterize the rate region only in terms of Shannon information inequalities.