Let $M = \begin{pmatrix} p_0 (1- p_0) & -p_0 p_1 &\ldots & p_0 p_n\\ -p_1 p_0 & p_1 (1-p_1) & \ldots & p_1 p_n\\ \vdots & & &\vdots\\ -p_np_0 &\ldots&&p_n(1-p_n)\end{pmatrix}$ where $\sum_i p_i = 1$ and $p_i >0$ for all i. How to show this matrix has rank n?

For clarity, $M_{i,j} = p_i(\delta_{ij} - p_j)$ and $\delta_{ij} = 1$ if $i = j$ and 0 otherwise, where $\sum_i p_i = 1$ and $p_i >0$.

I tried random values of $\{p_0, \ldots, p_n\}$ and it consistently returns n, so hoping for the rank be n.

  • 2
    $\begingroup$ The matrix as you have written it is $(n+1)\times(n+1)$. If $n=1$ it's a $2\times2$ matrix with rank $1$. I think you mean to conjecture that the matrix has rank $n$. $\endgroup$ – David Jan 31 at 6:15
  • $\begingroup$ yes, I will update the question $\endgroup$ – listener Jan 31 at 15:13

Your matrix is $$M=D-uu^\top$$

, where $D=\text{diag}(p_0,p_1,\ldots,p_n)$ and $u=(p_0,p_1,\ldots,p_n)^\top$

Consequently, $$\operatorname{rank}(M)\ge |\text{rank}(D)-\operatorname{rank}(uu^\top)|=n+1-1=n$$

The matrix $M$ of order $(n+1)\times(n+1)$ is related to the dispersion matrix of a singular multinomial distribution ('singular' because of the restriction $\sum\limits_{k=0}^n p_k=1$). Hence rank of $M$ is at most $n$.

This is also seen from the fact that $$\det M=\left(\prod_{k=0}^n p_k\right)\left(1-\sum_{k=0}^n p_k\right)=0$$

So, $\operatorname{rank}(M)=n$.

  • 1
    $\begingroup$ Thanks for the solution. Can you elaborate on $rank(M) \geq n$? I agree rank(D) = n+1 and $rank(uu^T) =1$ but how is $rank(M) \geq \| rank(D) - rank(u u^T)\|$? $\endgroup$ – listener Jan 31 at 15:24
  • $\begingroup$ @listener It follows from $$\text{rank}(\color{green}{A-B}+\color{blue}B)\le \text{rank}(\color{green}{A-B})+\text{rank}(\color{blue}B)$$ for any two matrices $A$ and $B$ having the same order. $\endgroup$ – StubbornAtom Jan 31 at 15:28
  • $\begingroup$ @listener math.stackexchange.com/questions/851596/…. $\endgroup$ – StubbornAtom Jan 31 at 15:35
  • $\begingroup$ @listener ?? $D-uu^T=D+vv^T$ with $v=-u$. $\endgroup$ – StubbornAtom Jan 31 at 15:53
  • $\begingroup$ Thanks for the help! It works. $\endgroup$ – listener Jan 31 at 15:57

For a start: if you add every other row to the first row you get a zero row because $$p_0(1-p_0)-p_1p_0-\cdots-p_np_0=p_0-p_0(p_0+p_1+\cdots+p_n)=0$$ in the first column, and similarly for all other columns. So the rank of the $(n+1)\times(n+1)$ matrix is at most $n$.

Sorry but I gotta go now. Hope somebody else can finish the problem by showing that the rank is not less than $n$.

  • $\begingroup$ To complete David answer, once we know the rank is $<n+1$, it suffices to find a $n\times n$ sub-matrix which has a non-zero determinant. $\endgroup$ – Clément Guérin Jan 31 at 6:21

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.