I want to implement a modular algorithm for computing the determinant of a square Matrix with multivariate polynomials in $\mathbb{Z}$ as components (symbolically). My idea is first to reduce the problem in $\mathbb{Z}[x_1,...,x_n]$ to a bunch of problems in $\mathbb{Z}_p[x_1,...,x_n]$, where p is prime. Next, I want to reduce it again to a problem in $\mathbb{Z}_p$ by substituting random integers for $x_1,...,x_n$ and computing determinants in $\mathbb{Z}_p$. (At the end I have to reconstruct the solution using polynomial interpolation and the chinese remainder theorem).
So now my question is: Is there a way to find a bound on the degree of the determinant in $x_1,...,x_n$? (Since the determinant will be a multivariate polynomial in $x_1,...,x_n$).
Equivalent question: How many images will I need to reconstruct the determinant in $\mathbb{Z}[x_1,...,x_n]$?
If your matrix has entries $a_{ij}$, then a crude bound is to take the largest degree of any entry and multiply it by $k$, the number of rows of the matrix. More cautiously, you could take the degrees of $a_{ij}$ (in each variable), say $$ D_{ij} = (d^{ij}_1, \ldots, d^{ij}_n) $$ and then take the largest sum of these you can find, using one $D_{ij}$ from each row.
Better still, maximize using one $D_{ij}$ from each row and column; that'll give you a pretty tight bound (albeit, just about as expensive to compute as the whole determinant).