I am reading a paper about colorization via optimization. Let us say that I can construct a symmetric matrix A with the characteristic that the sum of all elements in any row is 0 and all elements on its diagonal are positive. Well, as the sum of all rows of the A matrix is 0, the rows are linearly dependent and then it is not full rank. The A matrix is then singular. For my problem it's pretty obvious that this matrix is semidefinite positive, but I can't proof.

I've tried using the definition xTAx >= 0 without success. Checking at MATLAB, all the eigenvalues are >= 0, so the matrix is semidefinite positive, but I can't proof by this way too. I think that the right way involves the property that the sum of the rows is zero. Some suggestion?

Another question would involve the same semidefinite A matrix. Let C be a diagonal matrix with only a few elements equal to 1. I'm pretty sure that

A + C

is positive definite, and to answer that, I think the first question would be important.

PS: A + C is not diagonally dominant.

So, some suggestion to proof that A is semidefinite positive and A + C is definite positive with those informations?




$$ \left( \begin{array}{rrr} 1 & 2 & -3 \\ 2 & 1 & -3 \\ -3 & -3 & 6 \end{array} \right) , $$

Eigenvalues are $9,0,-1.$ Eigenvector $(1,-1,0)$ has eigenvalue $-1.$

  • $\begingroup$ Hmmm, thanks. That's a counter example to show that with only this informations it's not possible to proof A is semidefinite positive... $\endgroup$
    – Joao
    Feb 21 '14 at 13:32
  • $\begingroup$ Others informations about it is that A = I - W - Wt + WtW, where I is identity and W is a weighting neighborhood matrix. I mean, as pixels have 8 neighborhood, this matrix aij element contains the value of the influence pixel i has on pixel j according to some weighting function w normalized by the sum of the neighbors elements. So, the rows (not the columns) of W sums 1. For this case, wij = exp -(Y(i) - Y(r))²/2*variance(i), where Y is the intensity of the pixel i and variance the variance in the neighborhood of i. $\endgroup$
    – Joao
    Feb 21 '14 at 13:45
  • $\begingroup$ Oh... I just realize that it's obvious that A is semidefinite positve. $\endgroup$
    – Joao
    Feb 21 '14 at 19:05
  • $\begingroup$ A = I - W - Wt + WtW = (W-I)t(W-I) xt(W-I)t(W-I)x = ((W-I)x)t((W-I)x) >= 0. Thanks! $\endgroup$
    – Joao
    Feb 21 '14 at 19:07

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.