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?

  • 1
    $\begingroup$ 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$. $\endgroup$ Jul 29, 2015 at 13:37
  • $\begingroup$ @EmilJeřábek Modified question to be more suitable $\endgroup$
    – user34945
    Jul 29, 2015 at 14:04


Your Answer

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