Eigenvectors matrix multiplied by its transpose $\boldsymbol{\chi} \boldsymbol{\chi}^T$

• Let $$V$$ be the set of datapoint and assume that each point can be represented by a vertex. Then, given a similarity matrix $$\mathbf{M}$$, we define a graph $$G = (V, \mathbf{M})$$ generated using $$k$$-nearest neighbors.

• Let $$\mathbf{D}$$ denote the diagonal degree matrix of $$\mathbf{M}$$. Then, we deﬁne the normalized weight matrix $$\mathbf{W}$$ using $$\mathbf{D}$$, so that

$$\begin{equation*} \mathbf{W}= \mathbf{D}^{-\frac{1}{2}} \mathbf{M} \mathbf{D}^{-\frac{1}{2}}. \end{equation*}$$

• Therefore, we define the normalized Laplacian matrix of $$G$$ as $$\begin{equation*} \mathbf{L} = \mathbf{I} - \mathbf{W}= \mathbf{I}- \mathbf{D}^{-\frac{1}{2}} \mathbf{M} \mathbf{D}^{-\frac{1}{2}}, \end{equation*}$$ where $$\mathbf{I}$$ is the identity matrix.

• Since the normalized Laplacian matrix $$\mathbf{L}$$ is a positive semi-definite matrix, the matrix $$\mathbf{L}$$ is decomposed into an orthogonal set of eigenvectors $$\mathbf{U}=[u_1,...u_n]$$ and eigenvalues $$\mathbf{\Lambda}=[\lambda_1,...,\lambda_n]$$ represented as follows $$\begin{equation*} \mathbf{L}= \mathbf{U}\Lambda \mathbf{U}^{T}. \end{equation*}$$

In the graph setting, the eigenvalues of $$\mathbf{L}$$ can be treated as graph frequencies, and are always situated in the interval $$[0, 2]$$ for $$\mathbf{L}$$.

......................

• Now, let $$\mathbf{H}=\mathbf{U} h(\mathbf{\Lambda}) \mathbf{U}^{T}$$ where $$h(\mathbf{\Lambda})$$=diag$$(h(\lambda_1),...,h(\lambda_n))$$.

• I assume that $$h(\mathbf{\lambda})=1$$ if $$\lambda \leq \lambda_k$$ and $$h(\mathbf{\lambda})=0$$ if not.

Therefore, $$\mathbf{U} h(\mathbf{\Lambda}) \mathbf{U}^{T}= \boldsymbol{\chi} \boldsymbol{\chi}^T$$, where $$\boldsymbol{\chi} \in \mathbb{R}^{n\times k}$$ contains the first $$k$$ eigenvectors of the normalized Laplacian $$\mathbf{L}$$.

My questions:

1. I know that $$UU^{T}=\mathbf{I}$$ but what about $$\boldsymbol{\chi} \boldsymbol{\chi}^T$$ that contains the first $$k$$ eigenvectors of the normalized Laplacian $$\mathbf{L}$$ ?

2. Assume that I sum up all elements of the matrix $$\boldsymbol{\chi} \boldsymbol{\chi}^T$$ (call it $$S$$). Is there any condition to ensure that the sum $$S$$ decreases or takes the smallest possible value?

3. Is there any relation between $$S$$, $$\boldsymbol{\chi} \boldsymbol{\chi}^T$$ and the the topology of the graph?

• Presumably, the columns of $\chi$ are meant to be unit vectors Jul 19, 2020 at 18:15
• Also, when you say that the sum decreases, presumably you mean that the sum decreases for increasing values of $k$. Whether or not my guesses are correct, please make it clear what exactly you mean. Jul 19, 2020 at 18:18
• @BenGrossmann sorry for not been clear. I just wanna know how the sum $S$ varies. I would like to know if there is an effect on $S$ if I choose properly the $k$ eigenvectors or the value of $k$. I used the word "decrease" because I am interested on the case where this sum is small.
– Lina
Jul 19, 2020 at 18:23
• For the sum $S$ to vary (or decrease more specifically), something about $\chi$ needs to be changed. What is it that you are changing? Is it $k$, or is it something else? Jul 19, 2020 at 18:25
• I guess it could be $k$, but how to chose it if I want it to decrease $S$? or perhaps find a way to choose only eigenvectors that decreases $S$, but I don't know which ones.
– Lina
Jul 19, 2020 at 18:29

know that $$UU^{T}=\mathbf{I}$$ but what about $$\boldsymbol{\chi} \boldsymbol{\chi}^T$$ that contains the first $$k$$ eigenvectors of the normalized Laplacian $$\mathbf{L}$$ ?

Because $$\chi^T\chi = I_k$$, $$\chi\chi^T$$ is the orthogonal projection onto the span of the columns of $$\chi$$, i.e. the first $$k$$ eigenvectors of L.

Assume that I sum up all elements of the matrix $$\boldsymbol{\chi} \boldsymbol{\chi}^T$$ (call it $$S$$). Is there any condition to ensure that the sum $$S$$ decreases or takes the smallest possible value?

Let $$\chi_k$$ denote the matrix $$\chi$$ constructed above with $$k$$ columns. Let $$e = (1,1,\dots,1)^T$$. The sum of the elements of $$\chi_k\chi_k^T$$ is equal to $$S_k = e^T[\chi_k\chi_k^T]e = [e^T\chi_k][\chi_k^Te] = (\chi_k^Te)^T(\chi_k^Te) = \sum_{j=1}^k (e^Tv_j)^2,$$ where $$v_j$$ denotes the $$j$$th unit eigenvector (i.e. the $$j$$th column of $$\chi_k$$). Note that $$e^Tv_j$$ is the sum of the entries of $$v_j$$. With that, it is clear that $$S$$ increases as $$k$$ increases since each term in the sum is non-negative.

Is there any relation between $$S$$, $$\boldsymbol{\chi} \boldsymbol{\chi}^T$$ and the the topology of the graph?

There is no relation to the topology of the graph that I can see. If you're interested in a more thorough answer, then this question should probably be asked as its own, separate post.

• Thank you for the answer. If I am not wrong, $UU^{T}=I$ but if I select only $k$ eigenvectors then $\chi \chi^{T} \neq I$.
– Lina
Jul 19, 2020 at 18:36
• @Lina Yes. If $k < n$, then $\chi\chi^T \neq I$. Jul 19, 2020 at 18:38
• I though that the multiplicity of eigenvalues is important here. What I actually think is that if I chose for example only eigenvectors that correspond to the same eigenvalue, I will have a small values of $S$. But, if I chose only eigenvectors corresponding to different eigenvalues, the summer will approach 1. What do you think about that?
– Lina
Jul 19, 2020 at 18:54
• @Lina I just thought of something: does the normalized laplacian $L$ have zero row-sums (like the classical graph Laplacian)? If so, then we have $v_j^Te = 0$ for all $j > 1$. Jul 19, 2020 at 18:56
• @Lina As for your comment, I don't have any reason to believe that the multiplicity of the eigenvalues should matter. Jul 19, 2020 at 18:59