The question is simple: We have a symmetric matrix "A" with all diagonal entries 1. Unfortunately Off-diagonal entries are unknown, but we know the row and column sum of A. Now we just need the row and column sum of the "inverse" of A. Who can solve this problem? Does the theory of stochastic matrices help us?

Good! Let me explain more precisely. The matrix "A" is non-singular with the unit norm rows a_i. The main question is to solve the system AA^Tx=e^T, where e^T is the vector of ones. We know the matrix G=AA^T is symmetric with ones on diagonal and off-diagonal less than 1. Also we can compute the inner product of each row of "A" by the vector s=\sigma(a_i) (means the row sum of G). Let the sum of i-th row of G be c_i, means a_is^T=c_i. We want to solve the system with minimal information. "We should not compute" a_i*a_j^T (off-diagonals of G). We just need to row sum of G^{-1}, means "x=G^{-1}*e" by using of row sum of G, (c_i). Actually we have to find an algorithm or method with the order of O(n^2) not O(n^3) to solve it. Therefore for simplicity we can compute some of rows of "G" not all. If this question is solvable a very huge unsolved problem of linear algebra will be resolved.

  • $\begingroup$ This seems like a good question to me -- you might be getting downvotes because of the title of the question. Try something more descriptive and specific to your problem. $\endgroup$ – littleO Feb 16 '15 at 21:58
  • $\begingroup$ Very, very bad title. Even wording of the question is not the best. The question it self could be interesting. But my guess is it does not have unique solution. $\endgroup$ – tom Feb 16 '15 at 21:58
  • $\begingroup$ what do you mean by the row and column sum of A? $\endgroup$ – user795571 Feb 16 '15 at 22:01
  • 1
    $\begingroup$ What does "inverse" of $A$ mean? Is it given that $A$ is invertible? $\endgroup$ – Marc van Leeuwen Feb 16 '15 at 22:05

If the row and column sums are all the same (let's say $s$), that means $A {\bf 1} = s {\bf 1}$, and then of course $(A^{-1}) {\bf 1} = s^{-1} {\bf 1}$ so the row and column sums of the inverse are $s^{-1}$.

If the row and column sums are not all the same, then in general you have not given enough information.

EDIT: For example, the following two matrices satisfy the conditions of the problem and have row sums $1,2,3,4$ and column sums $1,2,3,4$, but the row and column sums of their inverses are different: $10/71,19/71,24/71,41/71$ for the first, $1,-1/2,2,-1/2$ for the second.

$$ \left[ \begin {array}{cccc} 1&-2&-1&3\\ -2&1&3&0 \\ -1&3&1&0\\ 3&0&0&1\end {array} \right],\ \left[ \begin {array}{cccc} 1&-2&0&2\\ -2&1&2&1 \\ 0&2&1&0\\ 2&1&0&1\end {array} \right] $$

  • $\begingroup$ But I don't think the information given implies that $A$ is invertible in the first place. $\endgroup$ – Marc van Leeuwen Feb 16 '15 at 22:03
  • 3
    $\begingroup$ The only reason to think $A$ is invertible is that the problem asks about the inverse of $A$. $\endgroup$ – Robert Israel Feb 16 '15 at 22:10
  • $\begingroup$ The more complete question was moved to upside. $\endgroup$ – Danial Feb 17 '15 at 14:04

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.