Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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$. –  Davide Giraudo Feb 14 '12 at 10:44
    
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$. –  Davide Giraudo Feb 14 '12 at 10:56
    
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$. –  user506901 Feb 14 '12 at 11:00
    
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. –  cardinal Feb 14 '12 at 12:18
    
Note the edit of the question. Well, obviously, if I solved the first, the second is solved. –  user506901 Feb 14 '12 at 12:30
show 1 more comment

2 Answers

up vote 1 down vote accepted

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

share|improve this answer
    
The diagonal entries of $V$ are $n-1$. –  user506901 Feb 17 '12 at 10:59
add comment

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

share|improve this answer
    
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. –  user506901 Feb 14 '12 at 15:02
    
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$? –  user506901 Feb 15 '12 at 9:14
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.