# How to show this matrix is diagonally dominant

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.

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