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?

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

0

Reset to default

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.