2

Let $P \in [0,1]^{n \times n}$ ($n > 1$) be a matrix such that the diagonal entries $P_{ii} ~~\forall i$ are $0$ and upper diagonal entries $P_{ij} ~~\forall i < j$ $\in (0.5,1)$ and lower diagonal entries $P_{ij} ~~ \forall i > j$ $\in (0,0.5)$.

Is rank($P$) = $n$ always? Or in other words, are the columns of $P$ independent? (This has been answered below in the negative)

What if $P_{ij} + P_{ji} = 1 ~~\forall i \neq j$? Does this restriction help in proving the claim?

Ved
  • 23

1 Answers1

2

Edit. The answer is negative even if the extra condition $p_{ij}+p_{ji}=1$ is imposed. Here is a computer generated counterexample: $$ P=\frac1{40}\pmatrix{ 0&29&39&38\\ 11& 0&37&36\\ 1& 3& 0&22\\ 2& 4&18& 0}. $$ One can verify that $\det(P)=0, \operatorname{rank}(P)=3$ and $\ker(P)$ is spanned by $(-10, -4, 2, 1)^\top$.

user1551
  • 139,064
  • Thanks! I just got a counter example myself for $n =5$ where the rank is $4$. (though it seems much more contrived!)

    $P = $ \begin{array}{ccccc} 0 & 0.51 & 0.51 & 0.51 & 0.99 \ 0.49 & 0 & 0.51 & 0.51 & 0.51 \ 0.49 & 0.49 & 0 & 0.51 & 0.51 \ 0.49 & 0.49 & 0.49 & 0 & 0.51 \ 0.0696 & 0.01 & 0.01 & 0.01 & 0 \end{array}

    The interesting question now is whether it holds with the restriction on $P$ (i.e $P_{ij} + P_{ji} = 1 ~ \forall i \neq j$)

     – Ved Oct 11 '13 at 14:20
  • @Ved What are the precise values of the entries of your $P$? As it stands, $\det(P)=-1344204\times10^{-12}\ne0$. – user1551 Oct 11 '13 at 14:42
  • The line of reasoning that i used to arrive at the solution is this. The sub matrix $Q=P(1:4,1:4)$ is of rank $4$. Lets add a fifth row $[x^{T} 0]$ where $x \in (0,0.5)^4$ and a fifth column $[y 0]^{T}$ where $y \in (0.5,1)^4$. Now for $P$ to have dependent columns means that $\exists \alpha \in {R}^{5}$ such that $P\alpha = 0$. Using the fact $Q$ is invertible and a bit of algebra, one gets the following necessary condition for $P$ to be rank $4$ : $x^{T}Q^{-1}y = 0$. One can pick $x$ and $y$ that satisfy the above condition.But it isn't clear yet if the same can be done for the 2nd question. – Ved Oct 11 '13 at 15:11
  • So for the second question, we have $x= 1 - y$ where $1$ is the vector of ones. Thus the condition to be satisfied is $y^{T}Q^{-1}y = 1^{T}Q^{-1}y$ where $y \in (0.5,1)^4$. But it is not clear to me if such a $y$ will exist because i do not know what properties of $Q^{-1}$ will be required to show the claim. – Ved Oct 11 '13 at 15:26
  • @Ved I see. The way I constructed my counterexample is the same as yours. ;-D – user1551 Oct 11 '13 at 15:32
  • Thanks for the counter example! It turns out these matrices have been studied quite a bit in literature under the name '1-hyper tournaments'. One of the sufficient conditions for such matrices to be non singular is that $|r|^2_2 < \frac{n^2(n-1)}{4}$ where $r$ is the vector of row sums. (google for generalized tournaments for further information). It turns out your example indeed does not satisfy this condition! – Ved Oct 27 '13 at 20:42