We are considering a matrix $A=(a_{ij})_{i,j=1,\ldots,d}\in\mathbb{R}^{d\times d}$ with the following property: $a_{ii}=-\sum_{j\neq i}a_{ij}$, i.e., the matrix is not only weak diagonal-dominant, but its rows also sum up to $0$. Note that the matrix is not necessarily symmetric (otherwise positive semi-definiteness would follow immediately from the weak diagonal-dominance). Furthermore, the matrix has the property that there are no matrices $B\in\mathbb{R}^{d-k\times d-k}$, $C\in\mathbb{R}^{k\times k}$, $k\in\{1,\ldots,d-1\}$, $R\in\mathbb{GL}(d,\mathbb{R})$ such that $$A=R\cdot\left(\begin{array}{cc}B & 0\\ 0 & C\end{array}\right)\cdot R^T,$$ i.e., we can not rearrange the matrix $A$ by switching two rows and the corresponding columns to obtain a decoupled version of $A$. Two questions arise:

  1. Is $A$ positive semi-definite in the sense that $x^TAx\geq0$ for all $x\in\mathbb{R}^d\backslash\{0\}$?
  2. By the property of the summation of each row to zero, it is immediately clear that $(1,\ldots,1)^T\in \ker(A)$. Is $\dim\ker(A)=1$ or is there another, linearly independent element?

These questions arose when considering the following paper: "Constructing Laplace Operator from Point Clouds in $\mathbb{R}^d$", by Belkin, Sun, and Wang, 2009, where the properties (1) and (2) are claimed for a matrix formulation of a discretization of the Laplace operator, but are not proved there and do not seem trivial to me.

  • 1
    $\begingroup$ Doesn't your "no decoupling" property imply that the matrix has a single size-$d$ Jordan block? Or did you mean to write that $R$ is a permutation matrix? Also, is your matrix by chance a Z-matrix? If so, and with the modified "no decoupling" assumption, then 2. (and probably also something very similar to 1.) is a classical result in the theory of M-matrices. $\endgroup$ May 4, 2016 at 12:22


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.