We show that the class of integer-valued functions computable by
polynomial-space Turing machines is exactly the class of functions f
for which there is a nondeterministic polynomial-time Turing
machine with a certain order on its paths that on input x outputs a 3x3
matrix with entries from {-1,0,1} on each path such that f(x) is exactly
the upper left entry in the product of all these matrices in the order of
the paths. Along the way we obtain characterizations of FPSPACE in terms
of arithmetic circuits and straight-line programs.