2
$\begingroup$

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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy