Special vector x such that L + xx^T and Cholesky.

Question

Information: $G$ be a graph and $L$ be its Laplacian matrix.

1. Find the special vector $x$ such that $L + xx^T$ is the Laplacian matrix of the graph that is obtained by adding edge $(i,k)$ to the graph $G$.

2. Let $B = L + ee^T$ and suppose its Cholesky decomposition is $B = U^TU$. Let $\hat{L} = L + xx^T$ and $\hat{B} = \hat{L} + ee^T$. Here $e$ is a vector of ones. Show that

$$ \hat{B} = B + xx^T = \begin{bmatrix} U \\ x^T \\ \end{bmatrix}^T \begin{bmatrix} U \\ x^T \\ \end{bmatrix}. $$

---

First question:

So I am really struggling on grasping what $x$ is supposed to be. So if I add an edge to a graph, assumed to be connected, it affects it's adjacency matrix at points (i,k) and (k,i). This also affects the Laplacian matrix at points: (i,k),(k,i),(i,i),(k,k). Where i,k is an edge.

So if the new L is supposed to be $L = L + xx^T$ then is x supposed to be a form of a block matrix that only updates the 4 entries of the laplacian matrix?

Second question: How should I approach this? Like what direction/view should I be looking this as?

Answer 1

Part A. $$ x = \begin{bmatrix} x_i \\ ... \\ ... \\ x_k \\ ... \\ \end{bmatrix} \quad \text{Where} \text{ } x_i \text{and} \text{ } x_k \text{ } \text{are entries are 1 and -1 and the rest are zeros} $$

Part B.

$$ \hat{B} = B + xx^T = \begin{bmatrix} U \\ x^T \\ \end{bmatrix}^T \begin{bmatrix} U \\ x^T \\ \end{bmatrix}. $$

$$ \hat{B} = B + xx^T = \begin{bmatrix} U^T & x \\ \end{bmatrix} \begin{bmatrix} U \\ x^T \\ \end{bmatrix}. $$

$$ \begin{bmatrix} U^TU + xx^T \\ \end{bmatrix} \quad \text{Note:} \text{ } B = U^TU $$

Therefore:

$$\hat{B} = U^TU + xx^T \implies B + xx^T $$