Let $d\in \Delta_n$ (the unit simplex: $\Delta_n=\{x\in R_+^n|\sum_{i=1}^nx_i=1$} ).

Show that the nxn matrix defined by $$A_{ij}= \begin{cases} d_i-d_i^2 , &\text{$i=j$} \\ -d_id_j, &\text{$i\neq j$} \end{cases}$$

Is positive semi-definite. The assignment recommends using the theorem that says "If A is diagonally dominant with non-negative diagonal entries, then A is positive semi-definite."

I can't figure out how to show that A is diagonally dominant, i.e:

$$\lvert{A_{ii}\rvert}\ge\sum_{j\ne i}\lvert A_{ij} \rvert$$

Can anyone help? Thank you so much.

  • $\begingroup$ I am confused here. If $d_k=1/2$ for all $k$ then all elements have absolute value $1/4$, and it looks to me like the claim fails. What am I missing? $\endgroup$ Feb 25 '20 at 21:49

0.) ignoring the hint with diagonal matrix $D = \text{diag}\big(\mathbf d\big)$
note: see 2.) at the end for the way with the hint

you have $A =D - D\mathbf {11}^TD = D^\frac{1}{2}\big(I-D^\frac{1}{2}\mathbf {11}^TD^\frac{1}{2}\big)D^\frac{1}{2}$

specializing to the nonsingular $D$ case, you have $\big(I-D^\frac{1}{2}\mathbf {11}^TD^\frac{1}{2}\big)$
is a matrix with all eigenvalues of 1 except a single eigenvalue of 0 -- why? So $A$ is congruent to this positive semidefinite matrix and the result follows.

for the case of singular $D$ consider the quadratic form
$\mathbf x^T A \mathbf x = \mathbf x^T D^\frac{1}{2}\big(I-D^\frac{1}{2}\mathbf {11}^TD^\frac{1}{2}\big)D^\frac{1}{2}\mathbf x = \mathbf y^T \big(I-D^\frac{1}{2}\mathbf {11}^T D^\frac{1}{2}\big)\mathbf y \geq 0$
with change of variables $\mathbf y:= D^\frac{1}{2}\mathbf x$
and we know
$\mathbf y^T \big(I-D^\frac{1}{2}\mathbf {11}^T D^\frac{1}{2}\big)\mathbf y \geq 0$ because $\big(I-D^\frac{1}{2}\mathbf {11}^T D^\frac{1}{2}\big) \succeq 0$

1.) the original post indicates that $d_i \geq 0$ and $\mathbf 1^T \mathbf d = 1$ but this seems to be the definition of the probability simplex not the unit simplex...
What is the difference between a unit simplex and a probability simplex?

2.) if we wanted to do this with (weak) diagonal dominance / Gerschgorin discs, we could observe that all diagonal components of $A$ are $\geq 0$ and all off diagonal components are $\leq 0$. Given this homogeneity it is enough to look at

$A \mathbf 1 = D\mathbf 1 - D\mathbf {11}^TD\mathbf 1 = D\mathbf 1 - D\mathbf 1 \big(\mathbf 1^TD\mathbf 1\big) = D\mathbf 1 - \beta D\mathbf 1 = (1- \beta)\cdot D\mathbf 1 \geq \mathbf 0$
for some $\beta \in [0,1]$ -- we are told that $\beta = 1$ so $A\mathbf 1 = \mathbf 0$ though as noted in (1) this doesn't seem to be the standard definition for unit simplex. In any case $A$ is real symmetric and the radius of each Gerschgorin disc $r_i \leq a_{i,i}\geq 0$ which proves all eigenvalues are real non-negative and hence $A \succeq 0$


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.