# Complexity of a particular determinant

Suppose we have an $n\times n$ matrix $A$ with non-negative integer entries such that $\mathsf{Tr}(A^i)=0$ at every $i\in\{1,2,\dots,n-2,n-1\}$ and $\mathsf{Tr}(A^n)\neq0$, then from Trace-Determinant formula we know that $$|n\cdot\mathsf{det}(A)|=\Big|{\mathsf{Tr}(A^n)}\Big|.$$

We can use a non-monotone formula for determinant from work of S. J. Berkowitz in On computing the determinant in small parallel time using a small number of processors. Inf. Prod. Letters 18, pp. 147–150, 1984 to compute $|n\cdot\mathsf{det}(A)|$.

1. Does Berkowitz formula actually reduce to $\big|{\mathsf{Tr}(A^n)}\big|$ which is actually a monotone formula ($A$ having only non-negative entries is no issue here)?

2. With these matrix types, is complexity of computing $|n\cdot\mathsf{det}(A)|$ the same whether with monotone or with non-monotone formula, or is there a more succint non-monotone formula?

• Berkowitz’s formula works over arbitrary commutative rings: it does not assume characteristic $0$, let alone the invertibility of $n$. Thus, it can’t possibly reduce to anything involving division by $n$. – Emil Jeřábek Jul 29 '15 at 13:37
• @EmilJeřábek Modified question to be more suitable – user34945 Jul 29 '15 at 14:04