Linear Network Codes and Systems of Polynomial Equations
Randall L. Dougherty, Chris Freiling, K. Zeger · IEEE Transactions on Information Theory · 2008
If beta and gamma are nonnegative integers and F is a field, then a polynomial collection {p1,hellip,Pbeta} sube Z[alpha1,hellip, alphagamma] is said to be solvable over F if there exist omega1hellip, omegagammaisin F such that for all i = 1,hellip, beta we have pi(omega1hellip, omegagamma) = 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's work implies 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. (Hence, the problems of network scalar-linear solvability and polynomial collection solvability have the same complexity.) The construction of the network is modeled on a matroid construction using finite projective planes, due to MacLane in 1936. A set psi of prime numbers is a set of characteristics of a network if for every q isin psi, 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 psi. 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. Two networks N and N' are Is-equivalent if for any finite field F, N is scalar-linearly solvable over F if and only if N' is scalar- linearly solvable over F. We further show that every network is ls-equivalent to a multiple-unicast matroidal network.