3
$\begingroup$

Suppose a square symmetric matrix $V$ is given

$V=\left(\begin{array}{ccccc} \sum w_{1s} & & & & \\ & \ddots & & -w_{ij} \\ & & \ddots & & \\ & -w_{ij} & & \ddots & \\ & & & & \sum w_{ns} \end{array}\right) \in\mathbb{R}^{n\times n},$

with values $w_{ij}> 0$, hence with only positive diagonal entries. Since the above matrix is diagonally dominant, it is positive semi-definite. However, I wonder if it can be proved that

$a\cdot diag(V)-V~~~~~a\in[1, 2]$

is also positive semi-definite. ($diag(V)$ denotes a diagonal matrix whose entries are those of $V$, hence all positive) In case of $a=2$, the resulting

$2\cdot diag(V)-V$

is also diagonally dominant (positive semi-definite), but is it possible to prove for $a\in[1,2]$? .........................................

Note that the above proof would facilitate my actual problem; is it possible to prove

$tr[(X-Y)^T[a\cdot diag(V)-V](X-Y)]\geq 0$,

where $tr(\cdot)$ denotes matrix trace, for $X, Y\in\mathbb{R}^{n\times 2}$ and $a\in[1,2]$ ?

Also note that

$tr(Y^TVY)\geq tr(X^TVX)$ and $tr(Y^Tdiag(V)Y)\geq tr(X^Tdiag(V)X)$.

(if that facilitates the quest., assume $a=1$)

.....................................................

Since the positive semi-definiteness could not generally be guaranteed for $a<2$, the problem casts to: for which restrictions on a does the positive semi-definiteness of a⋅diag(V)−V still hold?

Note the comment from DavideGiraudo, and his claim for case $w_{ij}=1$, for all $i,j$. Could something similar be derived for general $w_{ij}$≥0?

$\endgroup$
6
  • $\begingroup$ If $n=2$ and $a=1$ then $\operatorname{diag}(V)-V=\pmatrix{0&w_{1,2}\\\ w_{1,2}&0}$ which is not positive definite since $\pmatrix{1,-1}^t\pmatrix{0&w_{1,2}\\\ w_{1,2}&0}\pmatrix{1,-1}=\pmatrix{1,-1}^t\pmatrix{-w_{1,2}\\\ w_{1,2}}=-2w_{1,2}<0$. $\endgroup$
    – Davide Giraudo
    Feb 14, 2012 at 10:44
  • $\begingroup$ If we take $w_{i,j}=1$ for all $i$ and $j$ then $a\operatorname{diag}(V)-V$ has the eigenvalues $(a-1)+n-1$ and $(a-1)n-1$ so we needd $a-1\geq \frac 1n$. $\endgroup$
    – Davide Giraudo
    Feb 14, 2012 at 10:56
  • $\begingroup$ I suppose the first implies: in case the vector $x$ considered for the positive semi-definiteness of a matrix $A$, $x^TAx$, has the elements of the same sign, then semi definiteness follows. I'm not sure if I could translate the observation from the second comment to general $w_{ij}>0$. $\endgroup$
    – user506901
    Feb 14, 2012 at 11:00
  • $\begingroup$ Maybe you can tell us more about what you're really trying to solve. $V$ is the graph Laplacian of an undirected graph with no self loops, for example. $\endgroup$
    – cardinal
    Feb 14, 2012 at 12:18
  • $\begingroup$ Note the edit of the question. Well, obviously, if I solved the first, the second is solved. $\endgroup$
    – user506901
    Feb 14, 2012 at 12:30

2 Answers 2

Reset to default
2
$\begingroup$

Claim: For a symmetric real matrix $A$, then $tr(X^TAX)\ge 0$ for all $X$ if and only if $A$ is positive semidefinite.

$\endgroup$
2
  • $\begingroup$ Davide Giraudo already showed that positive semi-definiteness does not hold in general; but he devised interesting condition for $w_{ij}=1$ for all $i,j$. If you set $a=1.5$ for $n>2$, and $w_{ij}=1$, then the resulting matrix $1.5 diag(V)-V$ is positive semidefinite. Now, the question is: does it suffice to prove that $a\cdot diag(V)-V$ is not $diagonally$ $dominant$ to disprove the condition from my last edit. $\endgroup$
    – user506901
    Feb 14, 2012 at 15:02
  • $\begingroup$ Since the positive semi-definiteness could not generally be guaranteed for $a<2$, the problem casts to: for which restrictions on $a$ does the positive semi-definiteness of $a\cdot diag(V)-V$ still hold? Note the comment from DavideGiraudo from above, and his claim for case $w_{ij}=1$. Could something similar be derived for general $w_{ij}\geq 0$? $\endgroup$
    – user506901
    Feb 15, 2012 at 9:14
1
$\begingroup$

In the case $w_{ij}=1$ we have $V=\pmatrix{n&-1&-1&\cdots &-1 \\\ -1&n&-1&\ldots &-1 \\\ \vdots&\vdots&\ddots& &-1\\\ -1&-1&-1&\ldots&n}$ and $$M_a:=a\operatorname{diag}(V)-V=\pmatrix{n(a-1)&1&1&\cdots &1 \\\ 1&n(a-1)&1&\ldots &1 \\\ \vdots&\vdots&\ddots& &1\\\ 1&1&1&\ldots&n(a-1)}.$$ We can compute the determinant $\det(M_a-XI_n)$ adding to the first line all the other one. We get $$\det(M_A-XI_N)=(n(a-1)-(n-1)X)(n(a-1)-1-X)^{n-1},$$ and if we want $M_a$ positive semi-definite we should have $n(a-1)-1\geq 0$ so $a-1\geq\frac 1n$.

$\endgroup$
1
  • $\begingroup$ The diagonal entries of $V$ are $n-1$. $\endgroup$
    – user506901
    Feb 17, 2012 at 10:59

You must log in to answer this question.

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