Linear Network Codes and Systems of Polynomial Equations

• Published in: IEEE transactions on information theory 2008-05, Vol.54 (5), p.2303-2316
• Main Authors: Dougherty, R., Freiling, C., Zeger, K.
• Format: Article
• Language: English
• Subjects: Applied sciences; Beta; Codes; Coding, codes; Collection; Communication networks; Construction; Equations; Equivalence; Exact sciences and technology; Flow; Galois fields; Information theory; Information, signal and communications theory; Linear equations; Mathematical analysis; Mathematical models; Mathematics; matroids; Network coding; Networks; polynomial equations; Polynomials; Prime numbers; Signal and communications theory; Telecommunications and information theory; Wireless communication
• ISSN: 0018-9448; 1557-9654
• DOI: 10.1109/TIT.2008.920209

If beta and gamma are nonnegative integers and F is a field, then a polynomial collection {p 1 , hellip ,P beta } sube Z[alpha 1,hellip , alpha gamma ] is said to be solvable over F if there exist omega 1hellip , omega gamma isin F such that for all i = 1, hellip , beta we have p i (omega 1hellip , omega gamma ) = 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.