Linear Network Coding: Effects of Varying the Message Dimension on the Set of Characteristics

Abstract

It is known a vector linear solution may exist if and only if the characteristic of the finite field belongs to a certain set of primes. But, can increasing the message dimension make a network vector linearly solvable over a larger set of characteristics? To the best of our knowledge, there exists no network in the literature which has a vector linear solution for some message dimension if and only if the characteristic of the finite field belongs to a set $P$, and for some other message dimension it has a vector linear solution over some finite field whose characteristic does not belong to $P$. We have found that by \textit{increasing} the message dimension just by $1$, the set of characteristics over which a vector linear solution exists may get arbitrarily larger. However, somewhat surprisingly, we have also found that by \textit{decreasing} the message dimension just by $1$, the set of characteristics over which a vector linear solution exists may get arbitrarily larger. As a consequence of these finding, we prove two more results: (i) rings may be superior to finite fields in terms of achieving a scalar linear solution over a lesser sized alphabet, (ii) existences of $m_1$ and $m_2$ dimensional vector linear solutions guarantees the existence of an $(m_1+m_2)$-dimensional vector linear solution only if the $m_1$ and $m_2$ dimensional vector linear solutions exist over the same finite field.

Submitted to IEEE Transactions on Information Theory