0
$\begingroup$

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.

$\endgroup$
2
  • 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
    Commented Jan 31, 2019 at 6:15
  • $\begingroup$ yes, I will update the question $\endgroup$
    – listener
    Commented Jan 31, 2019 at 15:13

2 Answers 2

3
$\begingroup$

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$.

$\endgroup$
1
  • $\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$ Commented Jan 31, 2019 at 6:21
2
$\begingroup$

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$.

$\endgroup$
5
  • 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
    Commented Jan 31, 2019 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$ Commented Jan 31, 2019 at 15:28
  • $\begingroup$ @listener math.stackexchange.com/questions/851596/…. $\endgroup$ Commented Jan 31, 2019 at 15:35
  • $\begingroup$ Thanks for the help! It works. $\endgroup$
    – listener
    Commented Jan 31, 2019 at 15:57
  • $\begingroup$ Good point for the connection with covariance matrix (preferable to "confusion matrix") of a multinomial ; for this, refer to page 5 of courses.cs.washington.edu/courses/cse312/20su/files/… $\endgroup$
    – Jean Marie
    Commented May 27, 2022 at 8:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .