The rate of a network code is the ratio of the block size of the network's messages to that of its edge codewords. We compare the linear capacities and achievable rate regions of networks using finite field alphabets to the more general cases of arbitrary ring and module alphabets. For non-commutative rings, two-sided linearity is allowed. Specifically, we prove the following for directed acyclic networks: (i) The linear rate region and the linear capacity of any network over a finite field depend only on the characteristic of the field. Furthermore, any two fields with different characteristics yield different linear capacities for at least one network. (ii) Whenever the characteristic of a given finite field divides the size of a given finite ring, each network's linear rate region over the ring is contained in its linear rate region over the field. Thus, any network's linear capacity over a field is at least its linear capacity over any other ring of the same size. An analogous result also holds for linear network codes over module alphabets. (iii) Whenever the characteristic of a given finite field does not divide the size of a given finite ring, there is some network whose linear capacity over the ring is strictly greater than its linear capacity over the field. Thus, for any finite field, there always exist rings over which some networks have higher linear capacities than over the field.
We present a framework for information inequalities, namely, inequalities involving only Shannon's information measures, for discrete random variables. A region in IR(2 sup n -1), denoted by spl Gamma *, is identified to be the origin of all information inequalities involving n random variables in the sense that all such inequalities are partial characterizations of spl Gamma *. A product from this framework is a simple calculus for verifying all unconstrained and constrained linear information identities and inequalities which can be proved by conventional techniques. These include all information identities and inequalities of such types in the literature. As a consequence of this work, most identities and inequalities involving a definite number of random variables can now be verified by a software called ITIP which is available on the World Wide Web. Our work suggests the possibility of the existence of information inequalities which cannot be proved by conventional techniques. We also point out the relation between spl Gamma * and some important problems in probability theory and information theory.  We define the routing capacity of a network to be the supremum of all possible fractional message throughputs achievable by routing. We prove that the routing capacity of every network is achievable and rational, we present an algorithm for its computation, and we prove that every non-negative rational number is the routing capacity of some network. We also determine the routing capacity for various example networks. Finally, we discuss the extension of routing capacity to fractional coding solutions and show that the coding capacity of a network is independent of the alphabet used  Vector linear network coding (LNC) is a generalization of the conventional scalar LNC, such that the data unit transmitted on every edge is an L-dimensional vector of data symbols over a base field GF(q). Vector LNC enriches the choices of coding operations at intermediate nodes, and there is a popular conjecture on the benefit of vector LNC over scalar LNC in terms of alphabet size of data units: there exist (singlesource) multicast networks that are vector linearly solvable of dimension L over GF(q) but not scalar linearly solvable over any field of size q' qL. This paper introduces a systematic way to construct such multicast networks, and subsequently establish explicit instances to affirm the positive answer of this conjecture for infinitely many alphabet sizes pL with respect to an arbitrary prime p. On the other hand, this paper also presents explicit instances with the special property that they do not have a vector linear solution of dimension L over GF(2) but have scalar linear solutions over GF(q') for someq' <; 2 L , where q' can be odd or even. This discovery also unveils that over a given base field, a multicast network that has a vector linear solution of dimension L does not necessarily have a vector linear solution of dimension L' > L.  1. The field of values 2. Stable matrices and inertia 3. Singular value inequalities 4. Matrix equations and Kronecker products 5. Hadamard products 6. Matrices and functions. Discrete polymatroids are the multi-set analogue of matroids. In this paper, we explore the connections among linear network coding, linear index coding, and representable discrete polymatroids. We consider the vector linear solutions of networks over a field @math , with possibly different message and edge vector dimensions, which are referred to as linear fractional solutions. It is well known that a scalar linear solution over @math exists for a network if and only if the network is matroidal with respect to a matroid representable over @math . We define a discrete polymatroidal network and show that a linear fractional solution over a field @math exists for a network if and only if the network is discrete polymatroidal with respect to a discrete polymatroid representable over @math . An algorithm to construct the networks starting from certain class of discrete polymatroids is provided. Every representation over @math for the discrete polymatroid, results in a linear fractional solution over @math for the constructed network. Next, we consider the index coding problem, which involves a sender, which generates a set of messages @math , and a set of receivers @math , which demand messages. A receiver @math is specified by the tuple @math , where @math is the message demanded by @math and @math is the side information possessed by @math . We first show that a linear solution to an index coding problem exists if and only if there exists a representable discrete polymatroid, satisfying certain conditions, which are determined by the index coding problem considered. showed that the problem of finding a multi-linear representation for a matroid can be reduced to finding a perfect linear index coding solution for an index coding problem obtained from that matroid. The multi-linear representation of a matroid can be viewed as a special case of representation of an appropriate discrete polymatroid. We generalize the result of , by showing that the problem of finding a representation for a discrete polymatroid can be reduced to finding a perfect linear index coding solution for an index coding problem obtained from that discrete polymatroid.