MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Assume the following:

• $L\leq K$ .

• $\Gamma\in M_{K,L}$ is a $L$ rank ${ 0,1} $ matrix, without identical rows or the zeros row.

• $N\in M_{K,K}$ is a diagonal matrix, whose diagonal is a distribution: all entries are non-negative and $trace\left(N\right)=1$.

• $\Lambda\in M_{K,K}$ is a diagonal matrix, satisfying $\Lambda_{i,i}=\sum_{j=1}^{L}\Gamma_{i,j}$, or equivalently: $diag\left(\Lambda\right)=diag\left(\Gamma\Gamma^{T}\right)$.


$X=\Gamma^{T}N\Lambda^{-1}\Gamma\qquad=\sum_{i=1}^{K}N_{i,i}\Lambda_{i,i}^{-1}\{ (\Gamma[i,:])^{T}\Gamma[i,:]} $

$Y=\Gamma^{T}N\Gamma\;\;\;\;\;\;\;\;=\sum_{i=1}^{K}N_{i,i}\{ (\Gamma[i,:])^{T}\Gamma[i,:]}$

$Z=\Gamma^{T}N\Lambda\Gamma\;\;\;\;\;\;=\sum_{i=1}^{K}N_{i,i}\Lambda_{i,i}\{ (\Gamma[i,:])^{T}\Gamma[i,:]\} $

I'm interested in showing that the expression $M=X-YZ^{-1}Y$ is small in some sense (under non-singularity assumption of all matrices noted).

Observations so far:

  1. If $K=L$ then we get that $\Gamma$ is invertible and $M=0$.

  2. $M$ is positive semidefinite.

  3. Experiments showed so far that M greatly tends component wise to positive small values.

Has anyone seen something similar?, I'd like to find a tight bound on each entry of $M$, or even understand why it almost always ends up double non-negative.

share|cite|improve this question
Let's start line by line. What is $K$? What is $M_{K,L}$? What is "a $L$ rank 0,1 matrix"? And so on? – Chris Godsil Jan 31 '12 at 15:36
K is a number, Mkl is the matrices size KxL L is a number and a 0,1 matrix is a matrix with entries which are 0 and 1. – ifog Jan 31 '12 at 16:31

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.