Null space of an augmented graph Laplacian matrix

658 Views Asked by At

Let us consider $\mathbf{L}$ is a Laplacian matrix of a connected graph having $n$ nodes. I want to check whether $\mathbf{B} = (\mathbf{L}+\alpha\mathbf{J})$ is a full rank matrix or not. Note that: $\alpha > 0$ and $$ \mathbf{J} = \begin{bmatrix} \mathbf{I}_{n-1} & \textbf{0}_{n-1} \\ \textbf{0}_{n-1}^{\top} & 0 \end{bmatrix}. $$

My try: $\mathbf{L}$ has all one vector $\mathbf{1}^{\top}$ in its null space. $\begin{bmatrix} \mathbf{0}_{n-1}^{\top} 1\end{bmatrix}^{\top}$ is the only vector in the null space of $\mathbf{J}$. $\mathbf{L}$ and $\mathbf{J}$ both are positive semidefinite matrices.

I have noticed that the null space of $\mathbf{L}$ and $\mathbf{J}$ are not orthogonal. After that, I am not getting any clue about how to proceed further.

1

There are 1 best solutions below

0
On BEST ANSWER

Finally, I got the answer to my question. Hopefully, the answer may be useful to others.

Let us consider $\textbf{x} \neq \theta_n$ is in the null space of $\mathbf{B}$, so we can say that:

$$\textbf{x}^{\top} \mathbf{B}\textbf{x}=0.\tag1$$

Let us say:

$$\mathbf{L}= \sum_{i=1}^{n} \lambda_i \textbf{q}_i \textbf{q}_i^{\top}, \text{ and } \mathbf{J}= \sum_{j=1}^{n} \mu_j \textbf{p}_j \textbf{p}_j^{\top}.$$

Now, $(1)$ can be written as follows: $$ \sum_{i=1}^{n} \lambda_i \lVert \textbf{q}_i^{\top} \textbf{x} \rVert_2^2+\sum_{j=1}^{n} \alpha \mu_j \lVert \textbf{p}_j^{\top} \textbf{x} \rVert_2^2 =0.$$ Note that, $\lambda_i$s and $\mu_j$s are positive, except $\lambda_1 = \mu_1 = 0.$ Sum of positive numbers are $0$, that means all terms are $0$. The only possibility is that $\textbf{x} = \beta \textbf{q}_1$ and $\textbf{x}= \gamma \textbf{p}_1$ where $\beta, \gamma$ are non-zero scalars. That is not possible, so our assumption was wrong.

$\mathbf{B}$ is a full rank matrix. (Proof by contradiction.)