In vector network coding, the source multi- casts information by transmitting vectors of length L, while intermediate nodes process and combine their incoming packets by multiplying them with L × L coding matrices that play a similar role as coding coefficients in scalar coding. Vector network coding generalizes scalar coding, and thus offers a wider range of solutions over which to optimize. This paper starts exploring the new possibilities vector network coding can offer along two directions. First, we propose a new randomized algorithm for vector network coding. We compare the performance of our proposed algorithm with the existing randomized al- gorithms in the literature over a specific class of networks. Second, we explore the use of structured coding matrices for vector network coding. We present deterministic de- signs that allow to operate using rotation coding matrices and thus result in reduced encoding complexity.