Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
What do you mean by the "first entry" of a matrix? –  Gerry Myerson Jul 17 '12 at 0:03
    
This would yield an O(log(n)) algorithm for finding the determinant of a square matrix. Is this possible? –  ncmathsadist Jul 17 '12 at 0:18
    
@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? –  us2012 Jul 17 '12 at 0:29
1  
What does he mean by "logspace"? The stipulation $O(\log(n))$ is my best guess. –  ncmathsadist Jul 17 '12 at 0:32
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.