<p>Theorem 3.2 in this paper: <a href="https://doi.org/10.1007/s00224-003-1077-7" rel="nofollow noreferrer">https://doi.org/10.1007/s00224-003-1077-7</a> says this:</p>
<p>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.</p>
<p>The proof presented there seems convincing to me.  (But then -- I am one of the authors of the paper.)</p>
<p>This would seem to answer your question.</p>

CC BY-SA 4.0
2023-10-31T23:40:28.597Z
2023-10-31T23:40:28.597Z
Eric Allender
<p>Given any matrix of univariate polynomials of degree <span class="math-container">$\leq n^{O(1)}$</span> then prove that the coefficent of <span class="math-container">$x^i$</span> in the determinant of the matrix is in <span class="math-container">$GapL$</span></p>
<p>Hint: Use Mahajan-Vinay's result of converting determinant into  a arithmetic branching program.</p>
<p>Now i thought that first we replace every polynomial in the matrix entry with new variables. So the <span class="math-container">$(i,j)$</span>th entry of the matrix is replaced by a new variable <span class="math-container">$x_{i,j}$</span>. Now using mahajan vinay we can compute the determinant of this new matrix using a arithmetic branching program. Now in that <span class="math-container">$ABP$</span> i am replacing all the <span class="math-container">$x_{i,j}$</span> with the original entry of the the given matrix. Now in the <span class="math-container">$ABP$</span> all the edge weights are univariate polynomial. Now for any edge if the edge weight polynimial has degree <span class="math-container">$k$</span> then we branch that edge into <span class="math-container">$k+1$</span> edges where the <span class="math-container">$i$</span>th branch has weight  <span class="math-container">$x^i$</span> multiplied by coefficient of <span class="math-container">$x^i$</span> in that polynomial. We will do this process for each edge. Now each edge has weight some constant multiplied by some power of <span class="math-container">$x$</span>. Now let any edge has weight <span class="math-container">$cx^k$</span>. Then we will break that edge into consecutive <span class="math-container">$k$</span> edges where the first edge has weight <span class="math-container">$kx$</span> and the next ones has weight <span class="math-container">$x$</span>.</p>
<p>But i am not getting anywhere. I wanted finally to have like sum of <span class="math-container">$i$</span> length paths from source to target in the <span class="math-container">$ABP$</span> is the coefficient of <span class="math-container">$x^i$</span> in the determinant and if finding number of <span class="math-container">$i$</span> length paths in a graph is in <span class="math-container">$GapL$</span> then we are done.</p>
<p>Any ideas what should i do.</p>

<counting-complexity><matrices><polynomials><determinant>
Coefficients of a determinant of a matrix of univariate polynomials is in $GapL$
Sassy Math
# Coefficients of a determinant of a matrix of univariate polynomials is in $GapL$

(Asked by: username_0 on 2023-10-26)

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.

**Tags:** counting-complexity, matrices, polynomials, determinant

---

## 1 answers

### Answer by username_1 on 2023-10-31. Score: 3

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.


---

