Given any matrix of univariate polynomials of degree $\leq n^{O(1)}$ then prove that the coefficent of $x^i$ in the determinant of the matrix is in $GapL$

Hint: Use Mahajan-Vinay's result of converting determinant into a arithmetic branching program.

Now i thought that first we replace every polynomial in the matrix entry with new variables. So the $(i,j)$th entry of the matrix is replaced by a new variable $x_{i,j}$. Now using mahajan vinay we can compute the determinant of this new matrix using a arithmetic branching program. Now in that $ABP$ i am replacing all the $x_{i,j}$ with the original entry of the the given matrix. Now in the $ABP$ all the edge weights are univariate polynomial. Now for any edge if the edge weight polynimial has degree $k$ then we branch that edge into $k+1$ edges where the $i$th branch has weight $x^i$ multiplied by coefficient of $x^i$ in that polynomial. We will do this process for each edge. Now each edge has weight some constant multiplied by some power of $x$. Now let any edge has weight $cx^k$. Then we will break that edge into consecutive $k$ edges where the first edge has weight $kx$ and the next ones has weight $x$.

But i am not getting anywhere. I wanted finally to have like sum of $i$ length paths from source to target in the $ABP$ is the coefficient of $x^i$ in the determinant and if finding number of $i$ length paths in a graph is in $GapL$ then we are done.

Any ideas what should i do.


1 Answer 1


Theorem 3.2 in this paper: https://doi.org/10.1007/s00224-003-1077-7 says this:

Let B be an n × n matrix, whose entries are each polynomials of degree n in Z[x], where the coefficients of each polynomial Bi, j are computable in GapL. Then the coefficients of the polynomial det(B) are computable in GapL.

The proof presented there seems convincing to me. (But then -- I am one of the authors of the paper.)

This would seem to answer your question.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.