I. Introduction
Network coding has been attracting increasing attention in the last fifteen years. The seminal work of Ahlswede et al. [1] and Li et al. [24] introduced the basic concepts of network coding and how network coding outperforms the well-known routing. The class of networks which are mainly studied is the class of multicast networks and these are also the target of this work. A multicast network is a directed acyclic graph with one source. The source has messages, which are scalars over a finite field . The network has receivers, each one demands all the messages of the source to be transmitted in one round of a network use. An up-to-date survey on network coding for multicast networks can be found for example in [21]. Kötter and Médard [29] provided an algebraic formulation for the network coding problem: for a given network, find coding coefficients for each edge, whose starting vertex has in-degree greater than one. These coding coefficients are multiplied by the symbols received at the starting node of the edge and these products are added together. These coefficients should be chosen in a way that each receiver can recover the messages from its received symbols on its incoming edges. This sequence of coding coefficients at each such edge is called the local coding vector and the edge is called a coding point. Such an assignment of coding coefficients for all such edges in the network is called a solution for the network and the network is called solvable. It is easy to verify that the information on each edge is a linear combination of the messages. The vector of length of these coefficients of this linear combination is called the global coding vector. From the global coding vectors and the symbols on its incoming edges, the receiver should recover the messages, by solving a set of linearly independent equations. The coding coefficients defined in this way are scalars and the solution is a scalar linear solution. Ebrahimi and Fragouli [7] have extended this algebraic approach to vector network coding. In the setting of vector network coding, the messages of the source are vectors of length over and the coding coefficients are matrices over . A set of matrices, which have the role of the coefficients of these vector messages, such that all the receivers can recover their requested information, is called a vector solution. Also in the setting of vector network coding we distinguish between the local coding vectors and the global coding vectors. There is a third type of network coding solution, a scalar nonlinear network code. Again, in each coding point there is a function of the symbols received at the starting node of the coding point. This function can be linear or nonlinear. There is clearly a hierarchy, where a scalar linear solution can be translated to a vector solution, and a vector solution can be translated to a scalar nonlinear solution.