2
$\begingroup$

Given any matrix $A$, can one construct a matrix $B$ such that

  1. $B$ is nonnegative and the spectral radius of $B$ is strictly less than 1

  2. the determinant of $A$ is equal to the first entry of $B^*$ where $B^*=(I-B)^{-1}$.

Here, by constructing, I certainly do NOT mean "trivial" ones like first computing the determinant of $A$. From the complexity perspective, I want a Logspace algorithm.

Thanks.

  • 1
    What do you mean by the "first entry" of a matrix?2012-07-17
  • 0
    This would yield an O(log(n)) algorithm for finding the determinant of a square matrix. Is this possible?2012-07-17
  • 0
    @ncmathsadist: How so? You'd still need to invert the matrix to get the determinant. (also I don't think maomao is looking for O(log n) *time*) Still, I'm inclined to think that such an algorithm does not exist. maomao, do you know any similar examples? What leads you to suspect there is such an algorithm?2012-07-17
  • 1
    What does he mean by "logspace"? The stipulation $O(\log(n))$ is my best guess.2012-07-17

0 Answers 0