# How to prove this matrix is rank n?

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.

• 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$. – David Jan 31 at 6:15
• yes, I will update the question – 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$$.

• 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)\|$? – listener Jan 31 at 15:24
• @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. – StubbornAtom Jan 31 at 15:28
• – StubbornAtom Jan 31 at 15:35
• @listener ?? $D-uu^T=D+vv^T$ with $v=-u$. – StubbornAtom Jan 31 at 15:53
• Thanks for the help! It works. – 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$$.

• 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. – Clément Guérin Jan 31 at 6:21