[IEEE Trans. on Information Theory, August 2005, pp. 2745-2759]
Insufficieny of Linear Coding in Network Information Flow
Randall Dougherty, Chris Freiling, and Kenneth Zeger
Abstract
It is known that every solvable multicast network has a scalar linear
solution over a sufficiently large finite field alphabet. It is also
known that this result does not generalize to arbitrary networks.
There are several examples in the literature of solvable networks with
no scalar linear solution over any finite field. However, each
example has a linear solution for some vector dimension greater than
one. It has been conjectured that every solvable network has a linear
solution over some finite field alphabet and some vector dimension.
We provide a counterexample to this conjecture. We also show that if
a network has no linear solution over any finite field, then it has no
linear solution over any finite commutative ring with identity. Our
counterexample network has no linear solution even in the more general
algebraic context of modules, which includes as special cases all
finite rings and Abelian groups. Furthermore, we show that the
network coding capacity of this network is strictly greater than the
maximum linear coding capacity over any finite field (exactly 10%
greater), so the network is not even asymptotically linearly solvable.
It follows that, even for more general versions of linearity such as
convolutional coding, filter-bank coding, or linear time sharing, the
network has no linear solution.