[IEEE Trans. on Information Theory, May 2008, pp. 2303-2316 ]

Linear Network Codes and Systems of Polynomial Equations

Randall Dougherty, Chris Freiling, and Kenneth Zeger

Abstract

If β and γ are nonnegative integers and F is a field, then a polynomial collection {p1, … , pβ} ⊆ Z[α1, … , αγ] is said to be solvable over F if there exist ω1, … , ωγ ∈ F such that for all i=1, … , β we have pi(ω1, … , ωγ) = 0. We say that a network and a polynomial collection are solvably equivalent if for each field F the network has a scalar linear solution over F if and only if the polynomial collection is solvable over F. Koetter and Medard showed that for any directed acyclic network, there exists a solvably equivalent polynomial collection. We provide the converse result, namely that for any polynomial collection there exists a solvably equivalent directed acyclic network. The construction of the network is modeled on a matroid construction using finite projective planes, due to MacLane in 1936.

A set Ψ of prime numbers is a set of characteristics of a network if for every q∈Ψ, the network has a scalar linear solution over some finite field with characteristic q and does not have a scalar linear solution over any finite field whose characteristic lies outside of Ψ. We show that a collection of primes is a set of characteristics of some network if and only if the collection is finite or co-finite.