  In this paper we show that a surface in P^3 parametrized over a 2-dimensional
toric variety T can be represented by a matrix of linear syzygies if the base
points are finite in number and form locally a complete intersection. This
constitutes a direct generalization of the corresponding result over P^2
established in [BJ03] and [BC05]. Exploiting the sparse structure of the
parametrization, we obtain significantly smaller matrices than in the
homogeneous case and the method becomes applicable to parametrizations for
which it previously failed. We also treat the important case T = P^1 x P^1 in
detail and give numerous examples.
